机器算法验证 - 将对偶和 KKT 条件应用于 LASSO 问题 - 吾爱随笔录

将对偶和 KKT 条件应用于 LASSO 问题

机器算法验证优化套索

2022-03-19 00:46:40

我在理解对偶如何导致 LASSO 问题的常见形式以及被称为互补松弛的 Karush-Kuhn-Tucker 条件时遇到了一些困难。我有两个问题：

我们知道，给定一个优化问题 $\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*}$

解决这个问题相当于解决对偶问题

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

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

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 \}$

在 LASSO 问题中，原始是

\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*}$

所以，如果我的理解是正确的，对于对偶问题，我们应该得到

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

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

但是，LASSO 问题总是指定为

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

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

我错过了什么？它与为空的常数的导数有关吗？

第二个问题是：我看到很多作者通过解决平稳性KKT 条件 $X^{T} (y - X β) = λ s$ $X^T(y-X\beta)=\lambda s$

我理解，由于问题是凸的，因此满足原始和双重可行性条件，无论如何我不明白为什么我们不检查互补松弛条件。

1个回答

1）直接调用对偶性，你走错了方向。要从

$\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$

你只需要调用拉格朗日乘数。（参见，例如[1] 的第 5.1 节）

LM 在教学时经常在对偶的背景下进行讨论，但在实践中，您可以直接从一个切换到另一个，而不考虑对偶问题。

如果您对套索的对偶问题感兴趣，请参阅 [2] 的幻灯片 12 和 13

2) 你可能看到的是 Lasso 的 KKT Stationarity 条件：

$\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$

其中称为范数的次微分。（这本质上只是微积分的标准“导数至少为零”条件，但已针对不可微性进行了调整。） $\partial \|\beta\|_1$ $\ell_1$

我们知道 if所以如果我们知道解的支持和符号，这个方程给出了套索的精确闭式解。即， $|\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}}))$

（除此之外：此解决方案使套索的“收缩”效果（与 OLS 相比）非常明显。）

当然，解决套索的难点在于找到解决方案的支持和迹象，所以这在实践中并不是很有帮助。

然而，它是一个非常有用的理论结构，可以用来证明套索的许多好的特性；最重要的是，它让我们可以使用“原始双重见证”技术来建立套索恢复“真实”变量集的条件。参见 [3] 的第 11.4 节。

[1] S. Boyd 和 L. Vandenberghe。凸优化。可在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。稀疏的统计学习：套索和概括。可在https://web.stanford.edu/~hastie/StatLearnSparsity_files/SLS_corrected_1.4.16.pdf获得

其它你可能感兴趣的问题

上一篇对于严格的正参数，Metropolis-Hastings 的好的建议分布是什么？下一篇p 值和置信区间之间的不一致