Was ist die zeitliche Komplexität der Lasso-Regression?

14

Was ist die asymptotische Zeitkomplexität der Lasso-Regression, wenn die Anzahl der Zeilen oder Spalten zunimmt?

user2763361
quelle

Antworten:

4

Denken Sie daran, dass Lasso ein lineares Modell mit einer Regularisierung von .l1

Das Finden der Parameter kann als ein nicht eingeschränktes Optimierungsproblem formuliert werden, bei dem die Parameter durch gegeben sind

argminβ||yXβ||2+α||β||1 .

In der beschränkten Formulierung sind die Parameter durch gegeben

argminβ||yXβ||2s.t.||β||1<α

Welches ist ein quadratisches Programmierproblem und damit Polynom.

Fast alle konvexen Optimierungsroutinen, auch für flexible nichtlineare Objekte wie neuronale Netze, basieren auf der Berechnung der Ableitung Ihrer Ziel-Wrt-Parameter. Sie können jedoch nicht die Ableitung von α||w||1 . Als solche verlassen Sie sich auf verschiedene Techniken. Es gibt viele Methoden, um die Parameter zu finden. Hier ist ein Übersichtsartikel zum Thema Least Squares Optimization mit L1-Norm Regularization . Die zeitliche Komplexität der iterativen konvexen Optimierung ist schwierig zu analysieren, da sie von einem Konvergenzkriterium abhängt. Im Allgemeinen konvergieren iterative Probleme in weniger Epochen, wenn die Beobachtungen zunehmen.

Jessica Collins
quelle
4
Einige Dinge: Zu sagen, dass ein Problem "polynomiell" ist, ist nicht besonders hilfreich, es sei denn, Sie betrachten eine Art kombinatorisches Problem (das normalerweise exponentiell ist). Zweitens ist die Berechnung der Ableitungen so gut wie immer nicht der einschränkende Schritt. Drittens werden bei der Erörterung der zeitlichen Komplexität eines iterativen Algorithmus in der Regel die Kosten pro Schritt betrachtet , und es kommt daher nicht auf die Konvergenzkriterien an. Schließlich ist es normalerweise nicht der Fall, dass mehr Beobachtungen = weniger Iterationen sind.
Cliff AB
13

Während @JacobMick einen breiteren Überblick und einen Link zu einem Übersichtsartikel bietet, möchte ich eine "Shortcut-Antwort" geben (die als Sonderfall seiner Antwort angesehen werden kann).

Die Anzahl der Kandidatenvariablen (Merkmale, Spalten) sei und die Stichprobengröße (Anzahl der Beobachtungen, Zeilen) sei . Betrachten Sie LASSO als mit dem LARS-Algorithmus implementiert ( Efron et al., 2004 ). Die Rechenkomplexität von LASSO ist ( ibid. )n O ( K 3 + K 2 n )KnO(K3+K2n)

  • Für , und die rechnerische Komplexität von LASSO ist , was der einer Regression mit Variablen entspricht ( Efron et al., 2004 , S. 443-444; auch zitiert in Schmidt, 2005 , Abschnitt 2.4; zur rechnerischen Komplexität einer Regression siehe diesen BeitragK<nK3<K2nO(K2n)K ).
  • Für , und die Rechenkomplexität von LASSO ist ( Efron et al., 2004 ).KnK3K2nO(K3)

Verweise:

Richard Hardy
quelle
Richard, können Sie die Komplexität der Iteration für den GLM-Ansatz hier kommentieren ? Stats.stackexchange.com/questions/280304/… ?
Rnoodle
@moodle, ich kann nicht ohne tief in das zu graben (wofür ich momentan keine Zeit habe), sondern +1 für deine Frage.
Richard Hardy
Ich hatte einen Blick, aber es ist nicht klar - wäre gut, ein zweites Paar Augen darauf zu bekommen. Es gibt also Iterationskomplexität und Komplexität der vollständigen Konvergenz, und ich denke, die Literatur ist manchmal etwas vage über die Definitionen. Grundsätzlich habe ich einen Algorithmus, der einen Lasso-Löser in einer sehr kritischen Position verwendet, sodass die Komplexität meines Algorithmus stark vom Löser abhängt. Wäre gut, das zu nageln. Prost! Ich werde ein Kopfgeld für Ihre Eingabe setzen
rnoodle
@rnoodle, ich bezweifle sehr, dass ich dir dort bald helfen kann, aber ein Kopfgeld kann sicherlich andere Leute anziehen, die es besser wissen. Viel Glück!
Richard Hardy