KKT kontra nieograniczone sformułowanie regresji lasso

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

Q_{1} = \frac{1}{2} | | Y - X β | |_{2}^{2} Q_{2} = \frac{1}{2} | | Y - X β | |_{2}^{2} + λ | | β | |_{1} .

$Q_1 = \frac{1}{2}||Y - X\beta||_2^2 \\ Q_2 =\frac{1}{2}||Y - X\beta||_2^2 + \lambda ||\beta||_1.$ Następnie dwie różne formulacje to

{argmin}_{β} Q_{1}

$\text{argmin}_\beta \; Q_1$ zastrzeżeniem

| | β | |_{1} \leq t,

$||\beta||_1 \leq t,$ i równoważnie

{argmin}_{β} Q_{2} .

$\text{argmin}_\beta \; Q_2.$ 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,

λ (| | β | |_{1} - t) = 0

$\lambda\left(||\beta||_1 - t\right) = 0$ , jest zapewniony przez rozwiązanie dla drugiego preparatu.

regression lasso penalized

— goodepic
źródło

Odpowiedzi:

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

Oto uzasadnienie:

Rozważmy sformułowanie lasso: Niech minimalizator będziei niech. Moje twierdzenie jest takie, że jeśli ustawiszw pierwszym preparacie, wówczas rozwiązaniem pierwszego preparatu będzie również. Oto dowód:

f (β) = \frac{1}{2} | | Y - X β | |_{2}^{2} + λ | | β | |_{1}

$f(\beta)=\frac{1}{2}||Y - X\beta||_2^2 + \lambda ||\beta||_1$

β^{*}

$\beta^*$

b = | | β^{*} | |_{1}

$b=||\beta^*||_1$

t = b

$t=b$

β^{*}

$\beta^*$

min \frac{1}{2} | | Y - X β | |_{2}^{2} s.t. | | β | |_{1} \leq b

$\min \frac{1}{2}||Y - X\beta||_2^2 \text{ s.t.} ||\beta||_1\leq b$

\hat{β}

$\hat{\beta}$

| | \hat{β} | |_{1} < | | β^{*} | |_{1} = b

$||\hat{\beta}||_1<||\beta^*||_1=b$

f (\hat{β}) < f (β^{*})

$f(\hat{\beta})<f(\beta^*)$

β^{*}

$\beta^*$

β^{*}

$\beta^*$

Ponieważ , uzupełniający warunek luzu jest spełniony w punkcie rozwiązania . $t=b$ $\beta^*$

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. $\lambda$ $t$ $l_1$ $t$ $\lambda$

(Jeśli wiesz o podgradientach, możesz znaleźć to , rozwiązując równanie , gdzie $\lambda$ $X^T(y-X\beta^*)=\lambda z^*$ $z^* \in \partial ||\beta^*||_1)$

— elexhobby
źródło

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 ?

\hat{β}

$\hat{\beta}$

| | \hat{β} | |_{1} < | | β^{*} | |_{1} = b

$||\hat{\beta}||_1 < ||\beta^*||_1 = b$

— goodepic

Uważaj flagową odpowiedź za poprawną

— bdeonovic

można opracować dlaczego

f (\hat{β}) < f (β^{*})

$f(\hat{\beta}) < f(\beta^*)$

— 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

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

muszą należeć do tego zbioru.

\hat{β} \neq β^{*}

$\hat{\beta} \neq \beta^*$

— broncoAbierto

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

$\hat{\beta}$ $\|\hat{\beta}\| < \|\beta^*\|$ $\|\hat{\beta}\| = \|\beta^*\|$ $\hat{\beta} = \beta^*$

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śli $P_1$ $P_2$ $P_2$ $\beta^*$ $\|\beta^*\|=b$ $P_1$ $\hat{\beta} \neq \beta^*$ $\|\hat{\beta}\| \leq \|\beta^*\|$ $f(\hat{\beta}) \leq f(\beta^*)$ $f(\hat{\beta}) < f(\beta^*)$ $\beta^*$ $P_2$ $f(\hat{\beta}) = f(\beta^*)$ następnie , ponieważ założyliśmy, że rozwiązanie jest unikalne. $\hat{\beta} = \beta^*$

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. $\ell 1$ $P_1$

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ń $S$ $P_2$ $\|\beta\|=b \mbox{ } \forall \beta \in S$ $P_1$ $\hat{\beta} \notin S$ $\|\hat{\beta}\| \leq \|\beta\| \forall \beta \in S$ $f(\hat{\beta}) \leq f(\beta) \forall \beta \in S$ $f(\hat{\beta}) = f(\beta)$ $\beta \in S$ $\hat{\beta} \in S$ $f(\hat{\beta}) < f(\beta)$ $\beta \in S$ $S$ $P_2$ . 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. $P_1$ $S$ $P_1$ $P_2$

— broncoAbierto
źródło