Jak skaluje się Lasso z rozmiarem matrycy projektowej?

Jeśli mam macierz projektową , gdzie jest liczbą obserwacji wymiaru , jaka jest złożoność rozwiązania dla z Lasso wrt i ? Myślę, że odpowiedź powinna odnosić się do tego, jak jedna iteracja LASSO skaluje się z tymi parametrami, a nie do tego, jak skaluje się liczba iteracji (zbieżności), chyba że czujesz inaczej. $X\in\mathcal{R}^{n\times d}$ $n$ $d$ $\hat{\beta}=\text{argmin}_{\beta}\frac{1}{2n} ||X\beta-y||^{2} + \lambda||\beta||_{1}$ $n$ $d$

Przeczytałem to poprzednie pytanie o złożoność LASSO , ale wydaje się to sprzeczne z dyskusją na temat glmnet tu i tutaj . Zdaję sobie sprawę, że istnieje wiele algorytmów, w tym podejście GLMnet do GLMNeta, ale piszę artykuł o zamianie komponentu LASSO na algorytm nadrzędny i chciałbym zamieścić dyskusję na temat złożoności LASSO w ogóle, szczególnie za pomocą i . Chciałbym również poznać złożoność glmnet w podstawowym nieskomplikowanym przypadku, ale przywołany dokument jest nieco mylący, ponieważ cała złożoność algorytmu nie jest wyraźna. $d$ $n$

optimization lasso regularization time-complexity rnoodle
źródło

Nie jest jasne, dlaczego ta odpowiedź stats.stackexchange.com/a/190717/28666 (w wątku, do którego linkujesz ) nie odpowiada na twoje pytanie. Czy możesz rozwinąć? Co jest z czym sprzeczne?

ameba

Strona 6 w [pdf] [1] stwierdza: „Zatem pełny cykl wszystkich zmiennych d kosztuje ”. Jednak pytanie, które łączysz ze stanami . Czy brakuje mi pętli, aby uzyskać złożoność ? [1]: jstatsoft.org/article/view/v033i01

O (d n)

$O(dn)$

O (d^{2} n)

$O(d^{2}n)$

d^{2}

$d^{2}$

rnoodle

@amoeba Podany przez ciebie link dotyczy algorytmu LARS - chcę wiedzieć o podejściu GLM.

rnoodle

Odniesienia, dla regresji najmniejszego kąta i dla opadania współrzędnych, są poprawne. Różnica polega na tym, że (1) LARS znajduje dokładne rozwiązanie w (i robi to całą ścieżką możliwej ze złożonością równą problemowi OLS do całego problemu, co również skaluje się jako ), podczas gdy (2) zniżanie współrzędnych wykonuje „tylko” pojedynczy krok aproksymacji w , zbliżając się / „schodząc” bliżej minimum Problem LASSO. LARS używa kroków . Ze współrzędnym zejściem ... nikt nie wie.

O (d^{2} n)

$\mathcal{O}(d^2n)$

O (d n)

$\mathcal{O}(dn)$

O (d^{2} n)

$\mathcal{O}(d^2n)$

λ

$\lambda$

O (d^{2} n)

$\mathcal{O}(d^2n)$

O (d n)

$\mathcal{O}(dn)$

d

$d$

Sextus Empiricus

Odpowiedzi:

Odpowiedzi z referencji,

$\mathcal{O}(d^2n)$ dla najmniejszej regresji kąta
$\mathcal{O}(dn)$ dla opadania współrzędnych

, są poprawne.

Różnica jest taka

Równania LARS są zapisane w formie zamkniętej i znajdują dokładne rozwiązanie

(i robiąc to, idąc całą ścieżką możliwego λ, podczas gdy złożoność obliczeniowa jest skalowana tak samo jak znalezienie rozwiązania zwykłego problemu najmniejszych kwadratów, który również skaluje się jako ) $O(d^2n)$

podczas

opadanie współrzędnych to iteracyjny schemat zbliżenia rozwiązania. Odnośny krok (którego koszty obliczeniowe są skalowane jako ) jest „tylko” pojedynczym krokiem aproksymacji, zbliżającym się / „schodzącym” bliżej minimum problemu LASSO. $\mathcal{O}(dn)$

LARS używa (dokładnie) kroków do znalezienia rozwiązania (ze złożonością skalowania k-tego kroku jako , pierwszy termin na znalezienie produktów wewnętrznych w nieaktywnym zestaw i drugi termin na rozwiązanie nowego kąta w aktywnych zmiennych) . Przy opadaniu współrzędnych nikt tak naprawdę nie zna współczynnika konwergencji i liczby wymaganych / oczekiwanych kroków dla „wystarczającej” zbieżności (a przynajmniej nie zostało to dobrze opisane). $d$ $\mathcal{O}((d-k)n+k^2)$ $d-k$ $k$

Z drugiej strony koszt znacznie wzrasta w przypadku dużych wymiarów (chociaż nie ma silnego powodu, aby oczekiwać, że współczynnik zbieżności współrzędnych skaluje się podobnie, = liniowy, jeśli wzrasta). Tak więc intuicyjnie koordynowane zejście będzie działało lepiej powyżej pewnego limitu dla . Pokazały to również studia przypadków (patrz także odniesienie, które pokazuje, że glmnet działa głównie lepiej niż LARS, gdy , podczas gdy dla algorytmy działają podobnie). $d^2n$ $d$ $d$ $d>>100$ $d=100$

Skalowanie LARS jest problemem związanym ze złożonością obliczeniową. Skalowanie opadania współrzędnych jest problemem związanym ze złożonością obliczeniową i konwergencją.

Sextus Empiricus
źródło