机器学习数学基础 120 章

坐标下降与近端梯度

层级：C｜深入

1. 非光滑正则化需要合适算法

L1 在零点不可微，普通梯度下降不能直接用一个普通梯度处理。坐标下降一次优化一个参数，常得到软阈值闭式更新；近端梯度把光滑损失的梯度步与非光滑正则的“近端”步骤组合。

2. 坐标下降

对

min⁡xF(x1,ldots,xp),\min_xF(x_1,ldots,x_p),

循环或随机选择坐标 jj：

xj←arg⁡min⁡zF(x1,ldots,xj−1,z,xj+1,…,xp).x_j\leftarrow \arg\min_zF(x_1,ldots,x_{j-1},z,x_{j+1},\ldots,x_p).

其余坐标固定。若每个一维子问题易解，单步便宜。

3. Lasso 坐标更新

标准化线性回归：

min⁡w12∥y−Xw∥2+λ∑j∣wj∣.\min_w\frac12\|y-Xw\|^2+\lambda\sum_j|w_j|.

固定其他坐标，部分残差

rj=y−∑k≠jxkwk.r_j=y-\sum_{k\ne j}x_kw_k.

子问题：

min⁡wj12∥rj−xjwj∥2+λ∣wj∣.\min_{w_j}\frac12\|r_j-x_jw_j\|^2+\lambda|w_j|.

解为

wj←Sλ(xjTrj)∥xj∥2,w_j\leftarrow \frac{S_\lambda(x_j^Tr_j)}{\|x_j\|^2},

其中 SS 为软阈值。若列已单位范数，分母为 1。

4. 坐标选择

  • 循环：简单、缓存友好；
  • 随机：理论分析方便，可避免某些周期；
  • Gauss–Southwell：选梯度/潜在改进最大坐标，单步选择成本高；
  • active set：优先更新非零或可能激活的坐标。

高度耦合变量时，一次改一个坐标可能很慢；块坐标下降一次更新一组相关参数。

5. 复合目标

近端梯度针对

min⁡xF(x)=f(x)+g(x),\min_xF(x)=f(x)+g(x),

其中 ff 光滑可微，gg 凸但可能不可微且近端算子易算。

若把 gg 也当普通梯度处理，会在折点遇到问题；近端步骤保留其完整局部结构。

6. 近端算子

prox⁡ηg(v)=arg⁡min⁡x[g(x)+12η∥x−v∥22].\operatorname{prox}_{\eta g}(v) =\arg\min_x \left[g(x)+\frac1{2\eta}\|x-v\|_2^2\right].

它在不偏离 vv 太远的前提下，选择使 gg 小的点。若 gg 是集合 CC 的指示函数（可行内为 0、外为 +∞+\infty），近端算子就是投影 ΠC\Pi_C。

7. 近端梯度更新

先对光滑项做梯度步：

vt=xt−η∇f(xt),v_t=x_t-\eta\nabla f(x_t),

再做：

xt+1=prox⁡ηg(vt).x_{t+1}=\operatorname{prox}_{\eta g}(v_t).

合写为

xt+1=operatornameproxηg(xt−η∇f(xt)).x_{t+1}=operatorname{prox}_{\eta g} (x_t-\eta\nabla f(x_t)).

它最小化 ff 的局部二次上界加精确 gg。

8. L1 的近端是软阈值

若 g(x)=λ∥x∥1g(x)=\lambda\|x\|_1，因坐标可分：

prox⁡ηλ∥⋅∥1(v)=Sηλ(v)\operatorname{prox}_{\eta\lambda\|\cdot\|_1}(v) =S_{\eta\lambda}(v)

逐元素软阈值。这让迭代中参数可精确归零，普通次梯度下降通常只在零附近震荡。

9. ISTA 与 FISTA

Lasso 的基本近端梯度称 ISTA。对凸 LL-光滑 ff，合适步长下目标误差常为 O(1/t)O(1/t)。

FISTA 加 Nesterov 式外推，可达 O(1/t2)O(1/t^2)：

xt+1=prox⁡ηg(yt−η∇f(yt)),x_{t+1}=\operatorname{prox}_{\eta g} (y_t-\eta\nabla f(y_t)),

再用历史 xx 构造 yt+1y_{t+1}。加速序列可能目标非单调，可用 restart 改善实际表现。

10. 其他近端例子

  • 非负约束：逐元素 max⁡(v,0)\max(v,0)；
  • L2 范数（非平方）：向量软阈值，产生整组为零；
  • 核范数：对奇异值做软阈值；
  • box 指示：clip；
  • 单纯形指示：投影到单纯形。

“近端可计算”是结构化正则设计的重要标准。

11. 收敛与停止

可使用 proximal gradient mapping：

Gη(x)=1η[x−prox⁡ηg(x−η∇f(x))].G_\eta(x)=\frac1\eta \left[x-\operatorname{prox}_{\eta g}(x-\eta\nabla f(x))\right].

Gη=0G_\eta=0 是复合问题的一阶最优条件。还可看目标变化、参数变化和 KKT 残差。

12. 何时用哪种方法

  • 特征矩阵适合快速列访问、Lasso/Elastic Net：坐标下降；
  • 光滑损失 + 可分/结构化非光滑正则：近端梯度；
  • 多块变量和可分约束：ADMM；
  • 投影昂贵但线性 oracle 便宜：Frank–Wolfe。

易错点

  1. L1 次梯度法与近端梯度不是同一更新。
  2. prox 的阈值包含步长 η\eta。
  3. 坐标更新公式依特征列范数约定。
  4. FISTA 理论加速不表示每步目标单调。
  5. 非凸 gg 也可定义 prox，但解可能多值且全局保证改变。

常见问答

Q1：软阈值与 hard threshold 有何区别？

软阈值超过阈值后还向零收缩，对应 L1 prox；硬阈值保留大值原幅度、直接删小值，相关于 L0/非凸问题。

Q2：为什么近端步不只是“修正”梯度？

它精确求解正则项加二次邻近代价的子问题，能处理折点和结构约束。

Q3：坐标下降能并行吗？

若坐标耦合弱可并行/异步；强相关时同时更新会互相干扰，需要图着色、块划分或同步策略。

练习

  1. 计算 S1((−2,−0.5,3))S_1((-2,-0.5,3))。
  2. 写出 L1 近端梯度两步。
  3. 集合指示函数的 prox 为什么是投影？
  4. 坐标下降适合什么结构？
  5. ISTA 与 FISTA 的典型凸收敛率分别是什么？

答案与提示

  1. (−1,0,2)(-1,0,2)。
  2. v=x−η∇f(x)v=x-\eta\nabla f(x)，x+=Sηλ(v)x^+=S_{\eta\lambda}(v)。
  3. 可行域外目标无穷，只能在集合内最小化到 vv 的平方距离。
  4. 每个坐标/块子问题便宜，数据可高效按列访问，目标可分或近似可分。
  5. O(1/t)O(1/t) 与 O(1/t2)O(1/t^2)。