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

14

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

użytkownik2763361
źródło

Odpowiedzi:

4

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

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

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

W ograniczonym sformułowaniu parametry są podane przez

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

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.α||w||1

Jessica Collins
źródło
4
Kilka rzeczy: powiedzenie, że problemem jest „wielomian”, nie jest szczególnie pomocne, chyba że patrzysz na jakiś problem kombinatoryki (który jest zwykle wykładniczy). Po drugie, obliczanie pochodnych prawie zawsze nie jest ograniczającym krokiem. Po trzecie, zwykle przy omawianiu złożoności czasowej algorytmu iteracyjnego zwykle analizuje się koszt na krok , a zatem nie zależy od kryteriów konwergencji. Wreszcie, zazwyczaj nie jest tak, że więcej obserwacji = mniej iteracji.
Cliff AB
13

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 )KnO(K3+K2n)

  • 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<nO ( K 2 n ) KK3<K2nO(K2n)K
  • Dla , a złożoność obliczeniowa LASSO to ( Efron i in., 2004 ).KnO ( K 3 )K3K2nO(K3)

Bibliografia:

Richard Hardy
źródło
Richard, czy możesz skomentować złożoność iteracji dla podejścia GLM tutaj stats.stackexchange.com/questions/280304/... ?
rnoodle
@moodle, nie mogę nie zagłębić się głęboko w to (na co w tej chwili nie mam czasu), ale daje +1 dla twojego pytania.
Richard Hardy,
Spojrzałem, ale nie jest jasne - dobrze byłoby spojrzeć na to z drugą parą oczu. Istnieje więc złożoność iteracyjna i pełna złożoność konwergencji, i myślę, że literatura jest nieco niejasna w stosunku do definicji. Zasadniczo mam algorytm, który wykorzystuje solver lasso w bardzo krytycznej pozycji, tak że złożoność mojego algorytmu jest silnie zależna od solvera. Byłoby dobrze, aby to przybić. Twoje zdrowie!
Dodam
@ rnoodle, mocno wątpię, czy będę w stanie ci pomóc w najbliższym czasie, ale nagroda może z pewnością przyciągnąć innych ludzi, którzy wiedzą lepiej. Powodzenia!
Richard Hardy,