Jaka jest złożoność czasowa regresji Lasso?

Jaka jest asymptotyczna złożoność czasowa regresji Lasso wraz ze wzrostem liczby wierszy lub kolumn?

Przypomnij sobie, że lasso jest modelem liniowym z regulacją .$l_1$

Znalezienie parametrów można sformułować jako nieograniczony problem optymalizacji, w którym parametry są podane przez

$\arg \min_\beta ||y - X\beta||^2 + \alpha||\beta||_1$ .

W ograniczonym sformułowaniu parametry są podane przez

$\arg \min_\beta ||y - X\beta||^2 s.t.||\beta||_1 < \alpha$

Który jest kwadratowym problemem programistycznym, a zatem wielomianowym.

Prawie wszystkie wypukłe procedury optymalizacji, nawet dla elastycznych nieliniowych rzeczy, takich jak sieci neuronowe, polegają na obliczeniu pochodnej docelowych parametrów wrt. Nie można jednak przyjąć pochodnej . Jako takie polegasz na różnych technikach. Istnieje wiele metod wyszukiwania parametrów. Oto artykuł przeglądowy na ten temat, Optymalizacja najmniejszych kwadratów z regulacją L1-Norm . Złożoność czasowa iteracyjnej optymalizacji wypukłej jest dość trudna do analizy, ponieważ zależy od kryterium zbieżności. Zasadniczo problemy iteracyjne zbiegają się w mniejszych epokach wraz ze wzrostem obserwacji.$\alpha||w||_1$

Podczas gdy @JacobMick zapewnia szerszy przegląd i link do artykułu przeglądowego, pozwól, że podam „odpowiedź na skrót” (co można uznać za szczególny przypadek jego odpowiedzi).

Niech liczba zmiennych kandydujących (cechy, kolumny) będzie równa a wielkość próby (liczba obserwacji, wierszy) będzie wynosić . Rozważ użycie LASSO za pomocą algorytmu LARS ( Efron i in., 2004 ). Złożoność obliczeniowa LASSO to ( ibid. )n O ( K 3 + K 2 n $K$$n$$\mathcal{O}(K^3 + K^2 n)$

• Dla , a złożoność obliczeniowa LASSO wynosi , co jest takie samo jak regresja ze zmiennymi ( Efron i in., 2004 , s. 443-444; cytowany również w Schmidt, 2005 , sekcja 2.4; złożoność regresji obliczeniowej, patrz ten post ).$K<n$O ( K 2 n ) $K^3 < K^2 n$$\mathcal{O}(K^2 n)$$K$
• Dla , a złożoność obliczeniowa LASSO to ( Efron i in., 2004 ).$K \geqslant n$O ( K 3$K^3 \geqslant K^2 n$$\mathcal{O}(K^3)$

Bibliografia:

• Efron, Bradley i in. „Regresja najmniejszego kąta”. The Annals of Statistics 32.2 (2004): 407-499.
• Schmidt, Mark. „Optymalizacja metodą najmniejszych kwadratów z regularyzacją według normy 1”. Raport projektu CS542B (2005).