Lasso 坐标下降

部分残差是先把这一列已有的贡献放回去，再问“这一列独自应解释多少”。原问题的列可以彼此相关，其他列的当前系数通过 $r_{-j}$ 进入答案；所以式(1)并没有假设设计正交。

固定其余系数，相关的一维目标为

利用绝对值的近端软阈值理路近端算子Proximal operator · Proximity operator在降低凸函数值与保持靠近输入点之间取得精确平衡的单值算子。，最小点是 $S_{\lambda /q_j}(A_j^T{r}_{-j}/q_j)=S_{\lambda }(A_j^T{r}_{-j})/q_j$。列范数既缩放中心，也缩放阈值；只除中心而保持阈值为 $\lambda$ 会解错问题。

近端梯度法理路近端梯度法Proximal gradient method对复合目标的光滑项取显式梯度步、对非光滑凸项取隐式近端步的算法。一次线性化全部平方损失，再对全部坐标软阈值。这里每次对单个坐标的真实平方损失精确求解。两种方法共享软阈值运算，但一个全向量梯度步与一轮顺序扫掠有不同中间状态和成本。

同一耦合设计，两种访问顺序 ​

取

两列范数平方均为 $2$，内积为 $1$。先访问第一列：$A_1^{T}r=3$，所以 $x_1=S_1(3)/2=1$；缓存变为 $(1/2,1/2,0)$。接着 $A_2^{T}r=1/2$，所以 $x_2=0$。一轮结果是 $(1,0)$。其相关性 $(1,1/2)$ 满足两坐标 KKT，$P=D=5/4$，gap 为零。

把顺序改为第二列再第一列。第一步 $x_2=S_1(3/2)/2=1/4$，残差为 $(5/4,3/2,-1/4)$；第一列的部分相关性变为 $11/4$，故 $x_1=7/8$。这一轮结果为 $(7/8,1/4)$，残差 $(3/8,5/8,-1/4)$，$A^{T}r=(1,1/8)$，原始目标 $P=91/64$、对偶值 $D=77/64$，gap 为 $7/32$。第二轮先把第二坐标置零，再把第一坐标改为 $1$，这才得到零 gap。顺序改变有限预算答案，并未改变优化问题。

列缩放、零列与截距 ​

仅有一列 $A_1=(2,0{)}^T$，$b=(3,0{)}^T$、$\lambda =1$ 时，$q_1=4$、相关性为 $6$，正确解为 $5/4$。误用单位列公式会给出 $5$。若把特征缩放但希望保持同一个拟合惩罚问题，还需同步变换系数和惩罚权重；只为了数值好看而标准化列，会改变原参数下的正则化偏好。

加入不受惩罚的截距 $c$ 时，目标变为 $\Vert b-c\mathbf{1}-Ax{\Vert }^2/2+\lambda \Vert x{\Vert }_1$。固定 $x$，精确更新 $c=\mathrm{mean}(b-Ax)$，并相应更新残差；等价地，先中心化各列与 $b$，解系数后恢复 $c$。截距不能套软阈值。带截距的合法对偶还要求 ${\mathbf{1}}^T\theta =0$：若刚更新斜率后残差均值已非零，单纯缩放并不能满足这一条件，应先更新截距或使用中心化问题的证书。零列的系数仍取零，但若把截距当作“零惩罚列”，它与这里 $\lambda >0$ 的零列处理是不同情况。

某轮 $x_j=0$ 只说明当前一维子问题的阈值通过。其他坐标改变后它可以再次非零。若要永久删列，应使用可行 gap 导出的安全筛除理路Lasso 的间隙安全筛除Gap Safe screening for Lasso · Lasso safe sphere screening把可行原对偶间隙转成最优对偶点的安全球，再以严格列判据证明某坐标在所有 Lasso 最优解中为零。；它认证给定数据和 $\lambda$ 的优化解，仍不认证未知真实支持。

精确循环更新为什么到达最优值 ​

先剔除零列。每个单坐标目标是 $q_j$-强凸的，故一次精确更新产生的下降至少为 $q_j|x_j^{+}-x_j{|}^2/2$。因为 $P\ge 0$，把所有访问的下降相加，得到各步位移平方可求和，因而每步位移趋于零。又有 $\lambda \Vert x{\Vert }_1\le P(x^0)$，所有中间点有界。

取扫掠起点的一条收敛子列，极限为 $\overline{x}$。一轮只有有限的 $n$ 次更新，每个位移趋零，所以这条子列对应的所有轮内点也趋于同一个 $\overline{x}$。式(1)是当前其他坐标的连续函数，因此取极限后，$\overline{x}$ 对每个坐标都已经满足式(1)的固定点条件。由绝对值次微分的三个分支理路次梯度与次微分Subgradient · Subdifferential以全局仿射下界刻画凸函数在不可微点的支撑斜率集合。，这些条件恰是 $A_j^T(b-A\overline{x})\in \lambda \partial |{\overline{x}}_j|$。把坐标合起来就是完整凸最优性，故 $\overline{x}$ 最优。

目标值单调且连续，所以沿这条子列趋于 $P^{\ast }$，整列目标值也趋于 $P^{\ast }$；每个聚点同样最优。若 $A$ 满列秩，解唯一，有界序列的所有聚点相同，整个系数序列收敛。没有唯一性时，这份证明只宣布目标收敛与聚点最优，不把它夸大为已经证明所有非唯一问题的点收敛。

这个推导用了可分的绝对值惩罚。对一般耦合非光滑函数，各坐标最优不必整体最优。例如 $F(x_1,x_2)=max\{x_1,x_2\}$ 在原点沿任何单独负坐标方向都不下降，但沿 $(-1,-1)$ 下降。它不能继承上面的“拼合各坐标次梯度”步骤。

计算账本 ​

初始残差和列范数需一次扫描。缓存残差后，每次稠密列访问为 $O(m)$，一轮 $O(mn)$；稀疏列为 $O(1+\mathrm{nnz}(A_j))$，一轮 $O(n+\mathrm{nnz}(A))$。除矩阵外保存残差、系数与列范数需 $O(m+n)$。每次完整 gap 检查还要对所有列求相关性；不能把证书成本隐藏在“一个坐标很便宜”中。浮点累计残差应定期用 $b-Ax$ 重建，避免缓存漂移冒充 KKT 改善。

本例一轮即解是数据与顺序的巧合；一般不能由此宣称坐标下降总快于 FISTA。对照实验应同时列扫掠数、列访问数、矩阵读写和证书次数，并对所有候选使用相同的可行下界构造。

两道短自测 ​

1. 单列 $A=(3,0{)}^T$、$b=(2,0{)}^T$、$\lambda =3$，从零更新结果是多少？答案：列范数平方9、相关性6，故 $x=S_3(6)/9=1/3$；不能用单位列阈值返回3。
2. 带截距时残差相关性已全部小于 $\lambda$，但残差均值为1，可以直接宣布对偶可行吗？答案：不可以；还需 ${\mathbf{1}}^T\theta =0$，缩放非零均值并不能变成零。