Lasso 基本不等式与预测误差

展开平方后，噪声的影响只剩 $W^{\mathsf{T}}h$：算法若沿某列改变系数，能利用多少噪声，取决于噪声与该列的相关性。惩罚在每个坐标上都收取 $\lambda$ 倍绝对值，因此选择 $\lambda$ 压住全部坐标相关性，就能让结构惩罚承担这项随机扰动。

稀疏性的作用是让惩罚差具有方向。真支持以外原来都是零，新增一个系数一定增加绝对值惩罚；真支持以内，系数向零移动却可能节省惩罚。式(5)比较的正是这两份费用。它并未说算法知道 $S$，只是分析时用真实支持把误差分成两部分。

优化容差 $\delta$ 是算法尚未排除的额外预算。只要容差非零，候选就可能拿其中一部分预算在真支持外放入小系数。因此“目标非常接近最优”和“误差严格处于同一个齐次锥”不能互换。

两次三角不等式完成证明 ​

因为 $Y-X\tilde{\beta }=\epsilon -Xh$，目标比较展开为

平方差等于 $q^2/2-W^{\mathsf{T}}h$，这就证明式(2)。再用$\ell_\infty$–$\ell_1$ Hölder 不等式理路Hölder 不等式Hölder's inequality共轭指数下函数乘积的 L¹ 范数由各自的 Lᵖ 范数乘积控制。

为得到不依赖稀疏性的式(4)，只需用 $\Vert h{\Vert }_1\le \Vert \tilde{\beta }{\Vert }_1+\Vert {\beta }^0{\Vert }_1$，移项并乘以二。为得到式(5)，则用

以及 $\Vert h{\Vert }_1=\Vert h_S{\Vert }_1+\Vert h_{S^c}{\Vert }_1$。支持内的系数由三角不等式控制，支持外则因为 ${\beta }_{S^c}^0=0$ 而得到精确的惩罚增加。证明至此完全是确定性代数；概率只用来说明事件(3)多常发生。

相同的预测，可以对应完全不同的坐标 ​

设两列完全相同且 $\Vert X_1{\Vert }_2^2/n=1$，取 $Y=X_1$、${\beta }^0=(1,0{)}^{\mathsf{T}}$、无噪声、$\lambda =1/4$。目标仅通过 $s={\beta }_1+{\beta }_2$ 使用拟合值。对非负系数，绝对值惩罚也只取决于 $s$，所以全部

都是精确最优解。它们的预测误差全部是 $q^2=(1-3/4{)}^2=1/16$；取 $a=0$ 时，参数误差却是 $h=(-1,3/4{)}^{\mathsf{T}}$，其 ${\ell }_1$ 范数为 $7/4$，支持也选到了另一列。

式(5)没有失效：左侧是 $1/16+(1/4)(3/4)=1/4$，右侧是 $3(1/4)(1)=3/4$。它控制了一项本来就很小的预测误差，却没有把不可区分的两列分开。这正是进一步引入设计条件的原因。

非零 gap 不能省掉松弛量 ​

取 $\mathrm{\Gamma }=X^{\mathsf{T}}X/n=I_2$、$Y=X(1,0{)}^{\mathsf{T}}$、$\lambda =1/10$。精确解是 $\hat{\beta }=(9/10,0{)}^{\mathsf{T}}$。候选 $\tilde{\beta }=(9/10,2/5{)}^{\mathsf{T}}$ 的目标差为

此时 $h=(-1/10,2/5{)}^{\mathsf{T}}$，所以 $\Vert h_{S^c}{\Vert }_1=2/5>3/10=3\Vert h_S{\Vert }_1$，不在精确锥内。令 $0<\lambda <1$ 趋于零，并取候选 $(1-\lambda ,4\lambda )$，目标差变为 $12{\lambda }^2\to 0$，同样的锥违背仍存在。绝对 gap 很小不会自动恢复精确解的几何条件。

训练设计上的预测，何时能迁移 ​

若未来输入 $x_{\ast }$ 与拟合资料独立，且二阶矩矩阵为 ${\mathrm{\Sigma }}_{\ast }=\mathbb{E}[x_{\ast }{x}_{\ast }^{\mathsf{T}}]$，给定候选后的未来均值预测误差是 $h^{\mathsf{T}}{\mathrm{\Sigma }}_{\ast }h$。这里重新记 $\mathrm{\Gamma }=X^{\mathsf{T}}X/n$。若存在有限的 $C\ge 0$ 满足矩阵序关系 ${\mathrm{\Sigma }}_{\ast }⪯C\mathrm{\Gamma }$，便得到

没有这样的覆盖条件，式(4)只回答原设计上的问题。上面的重复列训练资料只看到系数之和，新输入 $(1,0)$ 却单独读取第一坐标；在这个新输入上，训练不可识别的方向会重新出现。新增响应噪声还须另计，不能把均值误差当成完整预测损失。

用尾部条件选择惩罚 ​

假设给定 $X$ 后，噪声 ${\epsilon }_i$ 相互独立、均值为零，且是共同尺度上界为 $\sigma >0$ 的次高斯随机变量理路次高斯随机变量Sub-Gaussian random variable · 次高斯尺度 · Subgaussian variance proxy用全实数上的中心化指数矩上界定义次高斯尺度，计算独立加权平均的尾界，并区分方差、尺度代理与条件次高斯假设。： $\mathbb{E}[e^{t{\epsilon }_i}\mid X]\le e^{{\sigma }^2{t}^2/2}$。再假定每列 $\Vert X_j{\Vert }_2^2/n\le 1$。线性组合的指数矩相乘，对 $u>0$ 给

对 $p$ 列作并集界理路并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。，不要求不同 $W_j$ 独立。给定 $0<a<1$，选择

便以至少 $1-a$ 的条件概率保证事件(3)，从而同时保证式(4)、(5)。若列范数上界为 $\sqrt{n}L$，式(6)再乘 $L$；未经归一化便沿用原数值 $\lambda$ 会改变结论。只有有限方差时，不能直接使用这条指数尾公式。

例如 $n=100,p=10,a=0.05,\sigma =1$，式(6)给 $\lambda \approx 0.692327$。若已知 $\Vert {\beta }^0{\Vert }_1\le 2$ 且 $\delta \le 0.01$，式(4)给 $q^2\le 6\lambda +0.02\approx 4.173964$。这份界可能保守，但每个条件和尺度都能核对；“看起来噪声不大”不能替代式(3)的概率保证。

近似稀疏与计算预算 ​

对任意事先指定的坐标集 $T$，同样分解得到

这里 $\Vert {\beta }_{T^c}^0{\Vert }_1$ 是被忽略的真实尾部，来自 $\Vert {\beta }^0{\Vert }_1-\Vert {\beta }^0+h{\Vert }_1\le \Vert h_T{\Vert }_1-\Vert h_{T^c}{\Vert }_1+2\Vert {\beta }_{T^c}^0{\Vert }_1$。它与优化误差是两项不同的费用；继续迭代只能减少后者。

在真稀疏情形，受限特征值与兼容常数理路受限特征值与稀疏可识别性Restricted eigenvalue condition · Compatibility condition for Lasso · Lasso 兼容条件在稀疏误差锥上定量比较预测与参数范数，精确定标兼容常数和受限特征值，并处理非零优化容差。把式(5)进一步变为 ${\lambda }^2|S|$ 量级的预测界和 $\lambda |S|$ 量级的参数界，并给出非零 $\delta$ 时如何放大锥。支持恢复理路Lasso 支持恢复与不可表示条件Lasso support recovery · Lasso sign consistency · Lasso irrepresentable condition用活动集上的显式候选和非活动集的严格对偶余量证明符号恢复，区分可识别性、参数小误差、变量筛选和坐标推断。还需检查最小信号和非活动列的得分余量。反方向看，小对偶间隙能验证式(1)，却不能计算含未知真参数的 $q$、$S$ 或噪声事件；它是统计证明的一个输入，不是其余条件的替代品。

完整的同设计、重复列与有限迭代比较见正则化学习保证终点练习。