Jaka jest asymptotyczna złożoność czasowa regresji Lasso wraz ze wzrostem liczby wierszy lub kolumn?
źródło
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ą .
Znalezienie parametrów można sformułować jako nieograniczony problem optymalizacji, w którym parametry są podane przez
.
W ograniczonym sformułowaniu parametry są podane przez
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.
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 O ( K3)+ K2)n )
Bibliografia:
źródło