lasso 的理论证明

浏览本文需要预先查看： lasso 的理论证明-约束lasso的估计误差界.

lasso相关证明：

约束lasso的估计误差界证明.

拉格朗日lasso的估计误差界证明.

预测误差界的证明.

接下来将对拉格朗日形式的lasso的估计误差界以及lasso误差的锥形约束进行说明。

定理2：对拉格朗日形式的lasso，假设 λ ≥ 2 ∥ X T w ∥ ∞ / N \lambda \geq 2\|X^Tw\|_{\infty}/N λ≥2∥XTw∥∞​/N, 其最优解 β ^ \widehat{\beta} β ​ 满足： ∥ β ^ − β ∗ ∥ 2 ≤ 3 γ k N N λ . \left\|\widehat{\beta}-\beta^{*}\right\|_{2} \leq \frac{3}{\gamma} \sqrt{\frac{k}{N}} \sqrt{N} \lambda. ∥∥∥​β ​−β∗∥∥∥​2​≤γ3​Nk​ ​N ​λ.

证明：该证明较定理1的证明复杂，但并不困难，我们首先想到的是通过构造一个类似定理1证明的基本不等式，进而证明。

如下：

v = β ^ − β ∗ v=\widehat{\beta}-\beta^{*} v=β ​−β∗, 构造函数： G ( v ) = 1 2 N ∥ y − X ( β ∗ + v ) ∥ 2 + λ ∥ β ∗ + v ∥ 1 . G(v)=\frac{1}{2N}\|y-X(\beta^{*}+v)\|^2+\lambda\|\beta^{*}+v\|_1. G(v)=2N1​∥y−X(β∗+v)∥2+λ∥β∗+v∥1​.

显然： G ( v ) ≤ G ( 0 ) G(v) \leq G(0) G(v)≤G(0) 将定理1证明中的基本不等式代入上式，我们有： ∥ X v ∥ 2 / ( 2 N ) ≤ λ ∥ β ∗ ∥ 1 − λ ∥ β ∗ + v ∥ 1 + w T X v / N . \|Xv\|^2/(2N) \leq \lambda\|\beta^{*}\|_1-\lambda\|{\beta^{*}+v}\|_1+w^TXv/N. ∥Xv∥2/(2N)≤λ∥β∗∥1​−λ∥β∗+v∥1​+wTXv/N.

利用假设条件以及三角不等式将右边与 ∥ v ∥ 2 \|v\|_2 ∥v∥2​ 建立联系 λ ∥ β ∗ ∥ 1 − λ ∥ β ∗ + v ∥ 1 + w T X v / N ≤ λ ∥ β ∗ ∥ 1 − ( λ ∥ β ∗ ∥ 1 − λ ∥ v ∥ 1 ) + λ ∥ v ∥ 1 / 2 = 3 2 λ ∥ v ∥ 1 ≤ k 3 2 λ ∥ v ∥ 2 \lambda\|\beta^{*}\|_1-\lambda\|{\beta^{*}+v}\|_1+w^TXv/N \leq \lambda\|\beta^{*}\|_1-(\lambda\|\beta^{*}\|_1-\lambda\|v\|_1)+\lambda\|v\|_1/2 = \frac{3}{2}\lambda\|v\|_1 \leq \sqrt{k}\frac{3}{2}\lambda\|v\|_2 λ∥β∗∥1​−λ∥β∗+v∥1​+wTXv/N≤λ∥β∗∥1​−(λ∥β∗∥1​−λ∥v∥1​)+λ∥v∥1​/2=23​λ∥v∥1​≤k ​23​λ∥v∥2​

合并上面两个式子 r ∥ v ∥ 2 / 2 ≤ k 3 2 λ ∥ v ∥ 2 r\|v\|^2/2 \leq \sqrt{k}\frac{3}{2}\lambda\|v\|_2 r∥v∥2/2≤k ​23​λ∥v∥2​ 得： ∥ v ∥ 2 ≤ 3 k λ / r \|v\|_2 \leq 3\sqrt{k}\lambda/r ∥v∥2​≤3k ​λ/r 证毕。

最后，对 ∥ v S ∥ 1 \left\|v_{S}\right\|_{1} ∥vS​∥1​ 与 ∥ v S c ∥ 1 \left\|v_{S^{c}}\right\|_{1} ∥vSc​∥1​ 的关系进行说明：

由 ∥ X v ∥ 2 / ( 2 N ) ≤ λ ∥ β ∗ ∥ 1 − λ ∥ β ∗ + v ∥ 1 + w T X v / N \|Xv\|^2/(2N) \leq \lambda\|\beta^{*}\|_1-\lambda\|{\beta^{*}+v}\|_1+w^TXv/N ∥Xv∥2/(2N)≤λ∥β∗∥1​−λ∥β∗+v∥1​+wTXv/N： λ ∥ β ∗ ∥ 1 − λ ∥ β ∗ + v ∥ 1 + λ ∥ v ∥ 1 / 2 ≥ 0 \lambda\|\beta^{*}\|_1-\lambda\|{\beta^{*}+v}\|_1+\lambda\|v\|_1/2 \geq 0 λ∥β∗∥1​−λ∥β∗+v∥1​+λ∥v∥1​/2≥0

进一步的： λ ∥ β ∗ ∥ 1 − λ ∥ β ∗ + v ∥ 1 + λ ∥ v ∥ 1 / 2 = λ ∥ β S ∗ ∥ 1 + λ ∥ β S ∗ + v S ∥ 1 − λ ∥ v S c ∥ 1 + λ ∥ v ∥ 1 / 2 \lambda\|\beta^{*}\|_1-\lambda\|{\beta^{*}+v}\|_1+\lambda\|v\|_1/2 = \lambda\|\beta^{*}_S\|_1+\lambda\|{\beta^{*}_{S}+v_{S}}\|_1-\lambda\|v_{S^c}\|_1+\lambda\|v\|_1/2 λ∥β∗∥1​−λ∥β∗+v∥1​+λ∥v∥1​/2=λ∥βS∗​∥1​+λ∥βS∗​+vS​∥1​−λ∥vSc​∥1​+λ∥v∥1​/2

化简： ∥ v S c ∥ 1 ≤ 3 ∥ v S ∥ 1 . \left\|v_{S^{c}}\right\|_{1} \leq 3\left\|v_{S}\right\|_{1}. ∥vSc​∥1​≤3∥vS​∥1​. 有了上述关系后，我们称误差 v v v 属于锥集 C ( S , 3 ) C(S,3) C(S,3)，该式在lasso预测误差界的证明中会起到一定作用。

至此，两种形式的lasso的估计误差界证毕。

参考文献： Trevor Hastie, Robert Tibshirani and Martin Wainwright: Statistical Learning with Sparsity: The Lasso and Generalizations.

下一篇：拉格朗日形式的lasso 预测误差界的证明。

如有错误，欢迎指出！