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 · Forward-backward splitting对复合目标的光滑项取显式梯度步、对非光滑凸项取隐式近端步的算法。，取 $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(mn)$；稀疏实现利用非零元素，连同向量操作为 $O(\mathrm{nnz}(A)+m+n)$。在新点认证间隙，需要重新取得该点的 $r$ 与 $A^{T}r$，随后缩放、计算 $P,D$、检查无穷范数共需 $O(m+n)$；这些矩阵乘法可与下一轮梯度共享。以上均为实数算术成本，浮点实现仍应按其数值精度核验可行性和报告容差。