KKT kontra nieograniczone sformułowanie regresji lasso

20

Regresja penalizowana przez L1 (aka lasso) jest prezentowana w dwóch formulacjach. Niech dwie funkcje celu to

Q1=12||YXβ||22Q2=12||YXβ||22+λ||β||1.
Następnie dwie różne formulacje to
argminβQ1
zastrzeżeniem
||β||1t,
i równoważnie
argminβQ2.
Korzystając z warunków Karush-Kuhn-Tucker (KKT), łatwo jest zobaczyć, w jaki sposób warunek stacjonarności dla pierwszego preparatu jest równoważny z wzięciem gradientu drugiego preparatu i ustawieniem go na wartość 0. Czego nie mogę znaleźć, ani się domyślić , jest to, w jaki sposób komplementarny warunek luźności dla pierwszego preparatu,λ(||β||1t)=0 , jest zapewniony przez rozwiązanie dla drugiego preparatu.
goodepic
źródło

Odpowiedzi:

16

Oba preparaty są równoważne w tym sensie, że dla każdej wartości t w pierwszym preparacie istnieje wartość λ dla drugiego preparatu, tak że oba preparaty mają ten sam minimalizator β .

Oto uzasadnienie:

Rozważmy sformułowanie lasso: Niech minimalizator będzieβi niechb=| | β| | 1. Moje twierdzenie jest takie, że jeśli ustawiszt=bw pierwszym preparacie, wówczas rozwiązaniem pierwszego preparatu będzie równieżβ. Oto dowód:

f(β)=12||YXβ||22+λ||β||1
βb=||β||1t=bβ

beta | | beta | | 1 < | | β | | 1 = b f ( β ) < f ( β * ) β * β *

min12||YXβ||22 s.t.||β||1b
β^||β^||1<||β||1=bf(β^)<f(β)ββ

Ponieważ , uzupełniający warunek luzu jest spełniony w punkcie rozwiązania .β t=bβ

Tak więc, biorąc pod uwagę formułę lasso z , konstruujesz formułę ograniczoną za pomocą równego wartości normy rozwiązania lasso. I odwrotnie, biorąc pod uwagę ograniczoną formułę z , znajdziesz taką, że rozwiązanie lasso będzie równe rozwiązaniu ograniczonej formulacji.t l 1 t λλtl1tλ

(Jeśli wiesz o podgradientach, możesz znaleźć to , rozwiązując równanie , gdzieX T ( y - X β ) = λ z λXT(yXβ)=λzz||β||1)

elexhobby
źródło
1
Doskonały. Gdy zobaczysz rozwiązanie, zawsze czujesz się głupi, że sam się tam nie dostałeś. Zakładam, że masz na myśli, znajdując sprzeczność, przypuszczamy, że znajdujemy taki, że ? | | beta | | 1<| | β| | 1=bβ^||β^||1<||β||1=b
goodepic
Uważaj flagową odpowiedź za poprawną
bdeonovic
2
można opracować dlaczego f(β^)<f(β)
goofd
Dowodzi to, że rozwiązanie pierwszego preparatu musi również mieć normę l1 wynoszącą b. W jaki sposób dowodzi, że oba rozwiązania są rzeczywiście takie same?
broncoAbierto
1
Ponadto Lasso nie zawsze ma unikalne rozwiązanie, więc nie możemy odnosić się do minimalizatora. arxiv.org/pdf/1206.0313.pdf . Mogliśmy jednak zapoznać się z zestawem minimizers i pokazują, że niektóre betabeta * muszą należeć do tego zbioru. β^β
broncoAbierto
3

Myślę, że pomysł Elexhobby'ego na ten dowód jest dobry, ale nie sądzę, aby był całkowicie poprawny.

β^β= β *β = β *β^<ββ^=ββ^=β

Zamiast tego sugeruję, abyśmy postępowali w następujący sposób:

Dla wygody oznaczmy odpowiednio przez i pierwsze i drugie sformułowanie. Załóżmy, że ma unikalne rozwiązanie, , z . Niech znajdzie rozwiązanie, . Mamy więc ten(nie może być większy z powodu ograniczenia), a zatem . Jeśli to nie jest rozwiązaniem , co jest sprzeczne z naszymi założeniami. JeśliP 2 P 2 β *β *= b P 1 ββ *βP1P2P2ββ=bP1β^βF ( β ) f ( β * ) f ( β ) < f ( β * ) β * P 2 f ( β )β^βf(β^)f(β)f(β^)<f(β)βP2β = β *f(β^)=f(β)następnie , ponieważ założyliśmy, że rozwiązanie jest unikalne.β^=β

Może się jednak zdarzyć, że Lasso ma wiele rozwiązań. Z lematu 1 arxiv.org/pdf/1206.0313.pdf wiemy, że wszystkie te rozwiązania mają tę samą -norm (i oczywiście tę samą wartość minimalną). Ustawiamy tę normę jako ograniczenie dla i kontynuujemy.P 11P1

Oznaczmy przez zbiorem rozwiązań z . Niech ma rozwiązanie, . Mamy więc ten , a zatem . Jeśli dla niektórych (a stąd dla wszystkich), to , co jest sprzeczne z naszymi założeniami. Jeśli dla niektórych to nie jest zbiorem rozwiązańP 2β = b β S P 1 βS βf ( β ) < f ( β ) β S S P 2 P 1 S P 1 P 2SP2β=b βSP1β^Sβ^ββSf(β^)f(β)βSf(β^)=f(β)βSβ^Sf(β^)<f(β)βSSP2 . Dlatego każde rozwiązanie jest w , tzn. Każde rozwiązanie jest również rozwiązaniem . Pozostałoby udowodnić, że komplementarne również ma miejsce.P1SP1P2

broncoAbierto
źródło