Anwenden von Dualitäts- und KKT-Bedingungen auf das LASSO-Problem

Ich habe einige Schwierigkeiten zu verstehen, wie Dualität zu der häufigen Form des LASSO-Problems und der Karush-Kuhn-Tucker-Bedingung führt, die als komplementäre Schlaffheit bezeichnet wird. Ich habe zwei Fragen:

Wir wissen das angesichts eines Optimierungsproblems $\begin{aligned} min_{x} f (x) \\ s . t . h_{i} (x) \leq 0, i = 1, \dots, m \end{aligned}$ $\begin{align*} &\min_x f(x)\\ &s.t. \quad h_i(x) \leq 0 \, ,\quad i=1,\dots, m \end{align*}$

Das Lösen dieses Problems entspricht dem Lösen des doppelten Problems

\begin{aligned} max_{λ} g (λ) \\ s . t . λ \geq 0 \end{aligned}

$\begin{align*} &\max_\lambda \,\, g(\lambda) \\ &s.t. \quad \lambda \geq 0 \end{align*}$ mit

g (λ) = m i n_{λ} {f (x) + \sum_{i = 1}^{m} λ_{i} h_{i} (x)}

$g(\lambda) = min_\lambda \bigr\{f(x) + \sum_{i=1}^m \lambda_i h_i(x)\bigr \}$

Im LASSO-Problem ist das Primal

\begin{aligned} | | y - X β | |_{2}^{2} \\ s . t . | | β | |_{1} \leq t \end{aligned}

$\begin{align*} &||y-X\beta ||_2^2 \\ &s.t. \,\,\,\, ||\beta ||_1 \leq t \end{align*}$

Wenn mein Verständnis richtig ist, sollten wir für das doppelte Problem

g (λ) = min_{β} | | y - X β | |_{2}^{2} + λ (| | β | |_{1} - t)

$g(\lambda) = \min_\beta ||y-X\beta ||_2^2 + \lambda( ||\beta ||_1 -t)$

Das LASSO-Problem wird jedoch immer als

min_{β} | | y - X β | |_{2}^{2} + λ | | β | |_{1}

$\min_\beta ||y-X\beta ||_2^2 + \lambda ||\beta ||_1$

Was vermisse ich? Bezieht es sich auf die Ableitung einer Konstanten, die null ist?

Die zweite Frage lautet: Ich habe viele Autoren gesehen, die die Lösung des LASSO-Problems vorgestellt haben, indem sie nur die Stationaritäts- KKT-Bedingung $X^{T} (y - X β) = λ s$ $X^T(y-X\beta)=\lambda s$

Ich verstehe, dass, da das Problem konvex ist, die ursprünglichen und doppelten Durchführbarkeitsbedingungen erfüllt sind, ich verstehe jedoch nicht, warum wir nicht nach komplementären Schlaffheitsbedingungen suchen .

optimization lasso Roberto
quelle

Antworten:

1) Sie gehen in die falsche Richtung, indem Sie die Dualität direkt aufrufen. Erhalten aus

$\text{arg min}_{\beta: \|\beta\|_1 \leq t} \|y - X\beta\|_2^2$

$\text{arg min}_{\beta} \|y - X\beta\|_2^2 + \lambda\|\beta\|_1$

Sie müssen nur Lagrange-Multiplikatoren aufrufen. (Siehe z. B. Abschnitt 5.1 von [1])

LMs werden beim Unterrichten häufig im Kontext der Dualität diskutiert. In der Praxis können Sie jedoch direkt von einem zum anderen wechseln, ohne das duale Problem zu berücksichtigen.

Wenn Sie sich für das doppelte Problem des Lassos interessieren, wird es auf den Folien 12 und 13 von [2] ausgearbeitet.

2) Was Sie wahrscheinlich gesehen haben, ist die KKT-Stationaritätsbedingung für das Lasso:

$\text{arg min}\frac{1}{2}\|y - X\beta\|_2^2 + \lambda \|\beta\|_1 \Longleftrightarrow -X^T(y - X\hat{\beta}) + \lambda s = 0 \text{ for some } s \in \partial \|\hat{\beta}\|_1$

Dabei wird als Subdifferenz der Norm bezeichnet. (Dies ist im Wesentlichen nur die Standardbedingung "Ableitung gleich Null bei Minimum" aus dem Kalkül, jedoch angepasst an die Nichtdifferenzierbarkeit.) $\partial \|\beta\|_1$ $\ell_1$

Wir kennen die Subdifferenz von if Diese Gleichung liefert also eine exakte Lösung in geschlossener Form für das Lasso, wenn wir die Unterstützung und das Vorzeichen der Lösung kennen . Nämlich, $|\beta_i| = \text{sign}(\beta_i)$ $\beta_i \neq 0$

$\hat{\beta}_{\hat{S}} = (X_{\hat{S}}^TX_{\hat{S}})^{-1}(X_{\hat{S}}^Ty - \lambda * \text{sign}(\hat{\beta}_{\hat{S}}))$

(Nebenbei: Diese Lösung macht den "Schrumpfeffekt" des Lassos (im Vergleich zu OLS) sehr deutlich.)

Natürlich besteht der schwierige Teil beim Lösen des Lassos darin, die Unterstützung und die Anzeichen der Lösung zu finden, daher ist dies in der Praxis nicht besonders hilfreich.

Es ist jedoch ein sehr nützliches theoretisches Konstrukt und kann verwendet werden, um viele schöne Eigenschaften des Lassos zu beweisen; Am wichtigsten ist jedoch, dass wir mithilfe der "Primal-Dual-Zeuge" -Technik Bedingungen festlegen können, unter denen das Lasso den "wahren" Satz von Variablen wiederherstellt. Siehe Abschnitt 11.4 von [3].

[1] S. Boyd und L. Vandenberghe. Konvexe Optimierung. Verfügbar unter https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

[2] http://www.stat.cmu.edu/~ryantibs/convexopt-F15/lectures/13-dual-corres.pdf

[3] T. Hastie, R. Tibshirani, M. Wainwright. Statistisches Lernen mit Sparsamkeit: Das Lasso und Verallgemeinerungen. Verfügbar unter https://web.stanford.edu/~hastie/StatLearnSparsity_files/SLS_corrected_1.4.16.pdf

mweylandt
quelle