Lasso 的最优性与对偶间隙

残差相关性 $A_j^{T}r$ 衡量沿第 $j$ 列改变拟合能够获得的边际收益。非零系数处，绝对值惩罚有固定斜率，最优时两者必须精确平衡；零系数处，尖角容纳一整段斜率，只要相关性没有超过阈值，该坐标就无需移动。这解释了为何零处是一个不等式，而不是把 $\mathrm{sign}(0)=0$ 代入非零公式。

最优性条件适合验证一个精确答案，计算中的候选却通常只能近似满足它。对偶值提供另一种检查：$P(x)$ 是原最优值的上界，合法的 $D(\theta )$ 是下界，两者之差就是尚未排除的优化误差。原始残差往往已经接近合适的对偶向量，但首先必须缩放到对偶可行域内。

图中第二轮同时出现两件不同的事：第二坐标变成零，对偶下界已经达到最优值。此时第一坐标仍未到解，间隙仍为 $1/36$；找到最优对偶向量并不意味着当前原始系数也已最优。

一个真正耦合的三步计算 ​

取

两列内积为 $1$，不能分别解两个独立的一维问题。记

$Q$ 的特征值为 $3,1$，所以光滑常数 $L=3$，强凸参数 $\mu =1$。用近端梯度法理路近端梯度法Proximal gradient method对复合目标的光滑项取显式梯度步、对非光滑凸项取隐式近端步的算法。，取 $x_0=(0,0)$、$\alpha =1/3$，每轮先算 $z=x+(c-Qx)/3$，再逐坐标施加阈值 $1/3$。

第一轮 $z_0=(1,1/2)$，所以 $x_1=(2/3,1/6)$。此时 $Q{x}_1=(3/2,1)$，第二轮候选为

第二坐标恰等于阈值，属于返回零的闭区间，故 $x_2=(5/6,0)$。接着 $Q{x}_2=(5/3,5/6)$，得到 $z_2=(23/18,2/9)$，再阈值得 $x_3=(17/18,0)$。代回原始目标可逐项核验：

为什么表中用 $5/4$ 作最优值？取 $x^{\ast }=(1,0)$，残差 $r^{\ast }=(1/2,1/2,0)$，于是 $A^T{r}^{\ast }=(1,1/2)$。第一坐标为正且相关性为 $\lambda =1$；第二坐标为零且相关性 $1/2$ 在 $[-1,1]$ 内。因此 $s=(1,1/2)\in \partial \Vert x^{\ast }{\Vert }_1$，且 $\mathrm{\nabla }g(x^{\ast })=-s$，两坐标共同满足最优性。直接算得 $P^{\ast }=\frac{1}{2}(1/4+1/4)+1=5/4$，满列秩保证这是唯一解。

从第二轮起，写 $x_k=(a_k,0)$，有 $a_{k+1}=(a_k+2)/3$。因此

一般凸近端梯度界在此为 $3/(2k)$；本例的实际误差更小，并且第二坐标有限步变零。这是本例的额外结构，不能从一般函数值界推出所有问题都能恢复支持集。

逐轮建立合法的下界 ​

对任意 $x$，令

那么 $\Vert A^T\theta {\Vert }_{\mathrm{\infty }}=\Vert A^{T}r{\Vert }_{\mathrm{\infty }}/\rho \le \lambda$，所以每轮都得到可用的对偶点。对上面的三个候选，精确算术给出：

例如第一行 $b^T\theta =3/2$、$\Vert \theta {\Vert }^2/2=7/27$，故 $D=67/54$；$17/12-67/54=19/108$ 确实大于真实误差 $1/6=18/108$。第二行的缩放点已等于 $r^{\ast }$，因此间隙恰好是真误差，而系数仍相差 $1/6$。

不能省略可行性检查。第一轮直接使用未缩放的 $r$，其相关性最大值为 $3/2>1$；代入表达式得到 $D(r)=5/3>P^{\ast }$，甚至让 $P(x_1)-D(r)=-1/4$。这个负数不是更好的证书，而是使用了非法的对偶向量。

一次阈值为什么通常不够 ​

本例最小二乘解是 $x_{\mathrm{L}\mathrm{S}}=Q^{-1}c=(3/2,0)$。若直接施加 $S_1$，得到 $(1/2,0)$，其残差相关性为 $(2,1)$，正坐标需要的等式 $A_1^{T}r=1$ 没有成立，目标值为 $3/2$。当 $A^{T}A=I$ 时，可以配方直接得到 $x^{\ast }=S_{\lambda }(A^{T}b)$；若 $A^{T}A=cI$、$c>0$，正确形式是 $S_{\lambda /c}(A^{T}b/c)$。一般耦合矩阵不能沿用这一配方，损失定标也会改变阈值。

对偶从哪里来，间隙为什么有效 ​

引入约束 $r=b-Ax$，按拉格朗日对偶理路拉格朗日对偶Lagrange duality通过拉格朗日函数构造原问题下界的对偶问题，并研究弱对偶、强对偶与最优性条件。构造

关于 $r$ 配方，下确界在 $r=\theta$ 取得，贡献 $-\Vert \theta {\Vert }^2/2$。关于 $x$，若 $\Vert A^T\theta {\Vert }_{\mathrm{\infty }}\le \lambda$，则 $\lambda \Vert x{\Vert }_1-x^T{A}^T\theta \ge 0$，下确界为零；若某个坐标违反约束，沿该坐标合适符号放大 $x_j$，表达式趋于 $-\mathrm{\infty }$。这正是$\ell_1$ 惩罚的共轭理路凸共轭与 Fenchel–Young 不等式Convex conjugate · Fenchel conjugate · Fenchel–Young inequality以线性函数的最佳配对代价定义共轭，并导出原变量与对偶变量间的基本不等式。为无穷范数球指标函数的计算。消去原变量后，便得到最大化 $D(\theta )$ 的对偶问题。

弱对偶已经足够证明 $D(\theta )\le P^{\ast }\le P(x)$，因此可行间隙上界无需先假设强对偶。本问题还能直接展开平方，得到更透明的恒等式

右边第一项是残差与对偶变量的不一致，第二项在对偶可行时非负。若 $x$ 满足坐标最优性，取 $\theta =b-Ax$，第一项为零，第二项按每个非零坐标逐项抵消，零坐标本来就无贡献。于是 gap 为零，同时证明原、对偶最优值相等且均可达；这里的证书是显式构造出来的。

停止标准与计算代价 ​

若所需训练目标误差为 $\epsilon$，计算可行 $\theta$ 后检查 $\mathrm{gap}\le \epsilon$ 即可。比如 $\epsilon ={10}^{-2}$ 时，表中的 $x_3$ 已通过，因为 $1/324<{10}^{-2}$，而 $x_2$ 尚未通过。这是优化目标的保证，不是预测风险或真实变量恢复保证。

若进一步知道 $A^{T}A⪰\mu I$、$\mu >0$，强凸性给出

本例 $\mu =1$，在 $x_2$ 得到系数误差至多 $\sqrt{1/18}$，实际为 $1/6$；界可以保守。没有正的强凸参数或其他误差界时，小 gap 不能自动改写成小系数误差。

每次近端梯度需要 $Ax$、$A^{T}r$ 两次矩阵向量乘法及 $O(n)$ 的阈值操作。计入向量初始化与更新，稠密矩阵下每轮为 $O(1+mn+m+n)$；在 $m,n\ge 1$ 时才简写为 $O(mn)$。稀疏实现利用非零元素，连同向量操作为 $O(1+\mathrm{nnz}(A)+m+n)$。在新点认证间隙，需要重新取得该点的 $r$ 与 $A^{T}r$，随后缩放、计算 $P,D$、检查无穷范数共需 $O(1+m+n)$；这些矩阵乘法可与下一轮梯度共享。以上均为实数算术成本，浮点实现仍应按其数值精度核验可行性和报告容差。

把本页证书交给统计误差分析 ​

Lasso 基本不等式理路Lasso 基本不等式与预测误差Lasso basic inequality · Lasso prediction error bound从带优化容差的目标比较推导预测界与松弛锥，分清噪声事件、稀疏结构、设计条件和可计算证书各自的作用。把观测写成 $b=A{\beta }^0+\epsilon$，并采用损失除以观测数 $m$ 的目标。本页同一个优化问题对应统计惩罚 ${\lambda }_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}}=\lambda /m$；这里可行的 $G=\mathrm{gap}(x,\theta )$ 则提供归一化容差 $\delta =G/m$。两个量都要一起换算。

接下来还须控制噪声相关性 $\Vert A^{\mathsf{T}}\epsilon /m{\Vert }_{\mathrm{\infty }}$，才能获得原设计上的均值预测界；把预测界升级成参数误差还需受限设计条件。支持恢复理路Lasso 支持恢复与不可表示条件Lasso support recovery · Lasso sign consistency · Lasso irrepresentable condition用活动集上的显式候选和非活动集的严格对偶余量证明符号恢复，区分可识别性、参数小误差、变量筛选和坐标推断。进一步要求非零信号和非活动得分余量。安全筛除认证的是这个训练目标的最优系数为零，上述支持定理认证的则是真参数的非零名单；两项证据针对不同对象。

不同求解器共用证书，安全删列另有门槛 ​

本页的对偶可行集只由 $A$和 $\lambda$决定，与候选来自哪个算法无关。坐标下降理路Lasso 坐标下降Lasso coordinate descent · Lasso cyclic coordinate minimization用部分残差和列范数逐坐标精确最小化 Lasso，并保持残差缓存与可行对偶证书一致。通过部分残差逐列最小化；FISTA理路FISTA 复合加速法FISTA · Fast iterative shrinkage-thresholding algorithm以近端主点、外推查询点和递推权重组成复合凸加速，并用势函数而非逐轮下降证明函数值速率。在外推点做近端步。比较它们与本页ISTA时，可统一用同一残差缩放构造 $\theta$，同时分别记坐标访问和全梯度费用。FISTA过冲时，这个构造的下界可能变差，即使原始目标还在下降，gap也可能上升。

本例第二轮的 $G=1/36$还能提供另一项产物。间隙安全筛除理路Lasso 的间隙安全筛除Gap Safe screening for Lasso · Lasso safe sphere screening把可行原对偶间隙转成最优对偶点的安全球，再以严格列判据证明某坐标在所有 Lasso 最优解中为零。给最优对偶点位于半径 $\sqrt{2G}$的球内；第二列的最坏相关性上界为 $1/2+\sqrt{2}\sqrt{1/18}=5/6<1$，所以它在所有最优系数中都为零。这个证明比“当前第二坐标为零”更强，却仍只属于给定训练目标的优化证书；真实变量恢复须另给统计条件。

完整的三算法复算、统一停止门槛、反例和答案见结构化优化终点练习。

若一次选择的单位是预先给定的整组变量，组 Lasso 证书理路组 Lasso 的块收缩与对偶证书Group Lasso proximal certificate · Block soft thresholding · 组软阈值对不相交变量组推导径向近端收缩，以整组残差相关性建立KKT和可行对偶间隙，并在耦合设计上认证停止。将本页的逐坐标绝对值惩罚换成加权组长度：零组受欧氏球约束，活动组还需方向对齐。它给出另一份耦合设计、完整块收缩和对偶间隙；本页的标量路线、定标与支持恢复边界仍原样适用各自的原问题。

精确等式观测对应另一份对偶证书 ​

若任务是无噪声的 $Az=y$，希望在全部可行解中最小化 $\Vert z{\Vert }_1$，应使用基追踪的稀疏恢复证书理路基追踪的稀疏恢复证书Basis pursuit recovery certificate · RIP certificate for sparse recovery · 基追踪与受限等距恢复从无噪声欠定观测建立 ℓ1 解码器，用完整分块证明和可精算的单纯形矩阵分开认证优化最优性与统一稀疏恢复。。其对偶约束为 $\Vert A^{\mathsf{T}}u{\Vert }_{\mathrm{\infty }}\le 1$、目标为 $y^{\mathsf{T}}u$，不含本页的二次项；只有原始候选也满足等式，目标差才是可行上下界的间隙。该页再用独立的全支持矩阵条件证明真稀疏信号恢复。本页 Lasso 的候选无需满足零残差，惩罚尺度和收缩解释仍属于原来的平方损失问题，不能只把惩罚取很小就宣称获得同一份精确恢复定理。