近端梯度法 (Proximal Gradient Methods) —— 通俗易懂详解

目录

1. 概述
2. 为什么需要近端梯度法？
3. 问题形式：可分解的凸优化
4. 近端算子 (Proximal Operator)
   1. 常见近端算子的闭式解
5. 算法推导与更新公式
   1. 基本近端梯度更新
   2. 线搜索与步长选择
   3. 示例：L1 正则化问题详细推导
6. 收敛性与重要性质
7. 常见变体
   1. 加速近端梯度 (Accelerated Proximal Gradient)
   2. 随机近端梯度 (Stochastic Proximal Gradient)
   3. 坐标近端梯度 (Coordinate Proximal Methods)
   4. Proximal-ADMM 的联系
8. 应用场景示例
9. 总结

---

概述

在现代机器学习和信号处理中，很多凸优化问题都可以写成如下形式：

$$\underset{x\in {\mathbb{R}}^n}{\min }\{F(x)=f(x)+g(x)\},$$

其中：

• $f(x)$ 是可微（且通常假设$\nabla f$是 $L$-Lipschitz 连续）的凸函数；
• $g(x)$ 是不可微但简单结构的凸函数，我们能有效计算其“近端算子”（proximal operator）。

近端梯度法 (Proximal Gradient Methods) 以类似梯度下降的方式处理可微部分 $f$，并用一个近端步骤来处理不可微部分 $g$，从而得到在理论与实践上都非常高效的方法。

---

为什么需要近端梯度法？

1. 处理不可微的正则项
   常见的稀疏正则 $\Vert x{\Vert }_1$、核范数 $\Vert X{\Vert }_{\ast }$ 等都不可微，但其“近端运算”往往有闭式解或易于实现。

2. 保持迭代开销低
   每一步迭代只需要做一次梯度计算与一次近端算子求解（如果有闭式解），比起直接用牛顿法处理不可微项要轻量得多。

3. 理论收敛有保证
   在 $f$ 光滑凸、$g$ 闭凸且可以计算其近端算子时，近端梯度法可以确保全局收敛。若 $f$ 还满足强凸，则可获得更快的线性收敛或加速收敛。

---

问题形式：可分解的凸优化

考虑以下可分解的目标函数：

min ⁡ x ∈ R n { F ( x ) = f ( x ) + g ( x ) } , \min_{x \in \mathbb{R}^n} \left\{ F(x) = f(x) + g(x)\right\}, x∈Rnmin​{F(x)=f(x)+g(x)},

• $f(x)$ 是可微凸函数，且假设它的梯度 $\nabla f$ 是 $L$-Lipschitz 连续，即对任意 $x,y\in {\mathbb{R}}^n$:

  $$\Vert \nabla f(x)-\nabla f(y){\Vert }_2\le L\Vert x-y{\Vert }_2.$$

• $g(x)$ 是不可微凸函数，但可以算它的近端算子。例如 $g(x)=\lambda \Vert x{\Vert }_1$、或指示函数 ${\delta }_C(x)$（当 $x\in C$ 时为 0，否则为 $\infty$）等。

---

近端算子 (Proximal Operator)

定义

给定一个凸函数 $g(x)$，以及一个正数 $\alpha >0$，近端算子 ${\mathrm{prox}}_{\alpha g}(\cdot )$ 定义为：

$${\mathrm{prox}}_{\alpha g}(v)=\arg \underset{x\in {\mathbb{R}}^n}{\min }\left\{g(x)+\frac{1}{2\alpha }\Vert x-v{\Vert }_2^2\right\}.$$

它可以理解为：“在点 $v$ 附近，用平方距离 $\frac{1}{2\alpha }\Vert x-v{\Vert }^2$ 来惩罚和 $v$ 的偏离，同时最小化 $g(x)$。”

若 $g(x)$ 很简单，则该最优化子问题往往有闭式或半闭式解，计算非常高效。

常见近端算子的闭式解

1. $L_1$ 范数：$\lambda \Vert x{\Vert }_1$
   对 $v\in {\mathbb{R}}^n$:

   $${\mathrm{prox}}_{\alpha \lambda \Vert \cdot {\Vert }_1}(v{)}_i=\arg \underset{x_i}{\min }\left\{\lambda |x_i|+\frac{1}{2\alpha }(x_i-v_i{)}^2\right\}=\mathrm{sign}(v_i)\max (|v_i|-\alpha \lambda ,0).$$

   这也叫**软阈值 (soft-thresholding)**操作。

2. 指示函数：${\delta }_C(x)$
   若 $g(x)={\delta }_C(x)$，表示 $x\in C$ 时 $g(x)=0$，否则 $g(x)=\infty$。此时

   $${\mathrm{prox}}_{\alpha {\delta }_C}(v)=\arg \underset{x\in {\mathbb{R}}^n}{\min }\{{\delta }_C(x)+\frac{1}{2\alpha }\Vert x-v{\Vert }^2\}=\arg \underset{x\in C}{\min }\frac{1}{2}\Vert x-v{\Vert }^2={\Pi }_C(v),$$

   即投影到集合 $C$ 上的最近点（欧几里得投影）。

3. 核范数：$\lambda \Vert X{\Vert }_{\ast }$
   对矩阵 $X$，其近端算子对应对奇异值进行软阈值（奇异值软阈值化——SVT）。在低秩矩阵学习、矩阵补全中常见。

---

算法推导与更新公式

基本近端梯度更新

我们想最小化

$$F(x)=f(x)+g(x),$$

其中 $f$ 光滑可微。考虑在点 $x_k$ 处做一次迭代，先用一阶近似逼近 $f$，再在周围加一个二次正则项：

1. 一阶近似：
   $$f(x)\approx f(x_k)+\nabla f(x_k{)}^T(x-x_k).$$

2. 二次正则项：
   $$\frac{1}{2{\alpha }_k}\Vert x-x_k{\Vert }_2^2,$$
   用来保证收敛并控制更新幅度。

这样，令

$$Q_{{\alpha }_k}(x,x_k)=f(x_k)+\nabla f(x_k{)}^T(x-x_k)+g(x)+\frac{1}{2{\alpha }_k}\Vert x-x_k{\Vert }_2^2.$$

为了更新 $x_{k+1}$，我们做如下最小化：

$$x_{k+1}=\arg \underset{x}{\min }\{Q_{{\alpha }_k}(x,x_k)\}.$$

因为 $f(x_k)$ 对 $x$ 不依赖，是常数，可以省略；这就变成了找

$$x_{k+1}=\arg \underset{x}{\min }\{\nabla f(x_k{)}^T(x-x_k)+g(x)+\frac{1}{2{\alpha }_k}\Vert x-x_k{\Vert }_2^2\}.$$

注意到 $\nabla f(x_k{)}^T(x-x_k)=\frac{1}{{\alpha }_k}(x-x_k{)}^T\cdot (-{\alpha }_k\nabla f(x_k))$。令

$$v_k=x_k-{\alpha }_k\nabla f(x_k).$$

于是我们得到：

$$x_{k+1}=\arg \underset{x}{\min }\left\{g(x)+\frac{1}{2{\alpha }_k}\Vert x-v_k{\Vert }_2^2\right\}={\mathrm{prox}}_{{\alpha }_{k}g}\left(v_k\right).$$

因此，$\boxed{x_{k+1}={\mathrm{prox}}_{{\alpha }_{k}g}(x_k-{\alpha }_k\nabla f(x_k))}$。

线搜索与步长选择

• 固定步长：若 $\nabla f$ 是 $L$-Lipschitz 连续，常取 ${\alpha }_k=\frac{1}{L}$ 或 ${\alpha }_k\le \frac{1}{L}$。
• Armijo 线搜索：也可用带“回溯”的方式调整 ${\alpha }_k$，直到满足某些充分下降条件：
  $$F({\mathrm{prox}}_{\alpha g}(x_k-\alpha \nabla f(x_k)))\le F(x_k)-\eta \Vert \nabla f(x_k){\Vert }^2,$$
  等等。实际中，为节省计算，也可以做简单的几何衰减线搜索 (backtracking line search)。

示例：L1 正则化问题详细推导

考虑最经典的 LASSO 回归：
$$\underset{x\in {\mathbb{R}}^n}{\min }\left\{\frac{1}{2}\Vert y-Ax{\Vert }_2^2+\lambda \Vert x{\Vert }_1\right\},$$
令
$$f(x)=\frac{1}{2}\Vert y-Ax{\Vert }_2^2,g(x)=\lambda \Vert x{\Vert }_1.$$

1. 梯度：
   $$\nabla f(x)=-A^T(y-Ax)=A^T(Ax-y).$$
2. 近端更新：
   在第 $k$ 步，假设步长固定为 $\alpha$，则
   $$x_{k+1}={\mathrm{prox}}_{\alpha \lambda \Vert \cdot {\Vert }_1}(x_k-\alpha \nabla f(x_k)).$$
3. 软阈值操作：
   记
   $$v_k=x_k-\alpha A^T(A{x}_k-y).$$
   则
   $$x_{k+1,i}=\mathrm{sign}(v_{k,i})\max (|v_{k,i}|-\alpha \lambda ,0),$$
   这在坐标层面上就等价于对每个分量做一次“软阈值”。

形象解释：每一步先做梯度下降 (减少残差 $\Vert y-Ax\Vert$ )，再对解进行软阈值 (让某些分量变 0)，从而产生稀疏解。

---

收敛性与重要性质

在凸设置下，若 $f$ 为 $L$-Lipschitz 光滑凸、$g$ 为闭凸且$\mathrm{prox}$可计算，则近端梯度法具有以下收敛结论：

1. 单调减少性：若步长 ${\alpha }_k$ 合理（${\alpha }_k\le 1/L$），则 $F(x_{k+1})\le F(x_k)$。
2. 全局收敛： { x k } \{x_k\} {xk​} 收敛到问题的全局最优解 $\hat{x}$。
3. 收敛速率：
   • 一般凸：$F(x_k)-F(x^{\ast })=O(\frac{1}{k})$。
   • 若 $f$ 强凸（或者 $f+g$ 强凸），则有更快的线性收敛或可通过加速技巧达到更优速度（下节会提到 Nesterov 加速可达 $O(\frac{1}{k^2})$ 的最优级别）。

---

常见变体

加速近端梯度 (Accelerated Proximal Gradient)

Nesterov 加速思想可用在“$f+g$”形式的优化里。其核心是对当前解与历史解形成一种“动量”预测，然后再做近端梯度，能大幅提升收敛效率。

• 典型公式（简化版）:
  $$y_k=x_k+{\beta }_k(x_k-x_{k-1}),$$
  $$x_{k+1}={\mathrm{prox}}_{\alpha g}(y_k-\alpha \nabla f(y_k)).$$
  其中 ${\beta }_k$ 与 $\alpha$ 取特定公式，使得对光滑凸问题可保证 $O(\frac{1}{k^2})$ 的最优收敛速率（非强凸情形）；若是强凸情形，还可实现近似的线性收敛。

随机近端梯度 (Stochastic Proximal Gradient)

当 $f(x)$ 是一个大规模数据集上的平均损失（如

$$f(x)=\frac{1}{N}\sum _{i=1}^N{\varphi }_i(x),$$

${\varphi }_i$ 可微），计算全部梯度 $\nabla f(x)$ 代价高。可采用随机的或小批量的近似梯度 $\hat{g}(x_k)$，并仍在每步进行近端运算。

• 更新公式与之前类似，只是把 $\nabla f(x_k)$ 换成 $\hat{g}(x_k)$。
• 确保期望意义上或大样本情形下也能收敛到最优解。
• 在机器学习中非常常见（如稀疏深度学习、在线学习等）。

坐标近端梯度 (Coordinate Proximal Methods)

高维情形下，可能一次更新全部坐标很昂贵。坐标近端梯度法在某个坐标或一小块坐标上做近端运算，其余坐标保持不变。

• 典型公式：选取坐标 $i_k$，做
  $$x_{k+1,i_k}={\mathrm{prox}}_{\alpha g_{i_k}}(x_{k,i_k}-\alpha {\nabla }_{i_k}f(x_k)),$$
  其余维度不变或做类似操作。
• 收敛性需要一定的随机化或循环策略，但在实际大规模问题中常表现良好。

Proximal-ADMM 的联系

ADMM（交替方向乘子法）可视为在分块可分问题上，每次针对一个变量做近端（或子问题最小化）操作，并更新乘子。

• 若问题能写成
  $$\underset{x,z}{\min }f(x)+g(z),\text{subject to }Ax+Bz=c,$$
  ADMM 每个子步就像做一个带约束的近端更新。
• 在实际工程里，Proximal Gradient 与 ADMM 是两种常见“大杀器”，常能相互启发，也可在分布式或并行化时结合使用。

---

应用场景示例

1. LASSO 回归
   $$\underset{x}{\min }\frac{1}{2}\Vert y-Ax{\Vert }_2^2+\lambda \Vert x{\Vert }_1,$$
   用近端梯度法，梯度部分对应 $\nabla f(x)=A^T(Ax-y)$，近端算子对应软阈值操作。迭代开销低，适合大规模回归。

2. Logistic 回归 + $L_1$ 正则
   $$\underset{w}{\min }\sum _{i=1}^N\log (1+\exp (-b_i{w}^T{x}_i))+\lambda \Vert w{\Vert }_1,$$
   用随机近端梯度可在大数据集上高效求解稀疏分类模型。

3. 矩阵补全 (Matrix Completion)
   $$\underset{X}{\min }\frac{1}{2}\Vert P_{\Omega }(X-M){\Vert }_F^2+\lambda \Vert X{\Vert }_{\ast },$$
   其中 $\Vert X{\Vert }_{\ast }$ 为核范数 (trace norm)。近端算子是对奇异值做软阈值 (SVT)；在推荐系统、图像修复中广泛应用。

4. 多项约束 + 简单集合的投影
   如果 $g$ 是多个指示函数之和或附加多种正则项，只要能写成可分形式并能分别计算近端，都可运用近端梯度迭代。

---

总结

近端梯度法可视为“梯度下降 + 不可微项近端处理”的强大结合，让大量本来因不可微正则或约束而棘手的凸问题，得以轻松、高效、稳定地求解。其主要特点包括：

• 算法易实现：核心更新公式
  $$x_{k+1}={\mathrm{prox}}_{{\alpha }_{k}g}(x_k-{\alpha }_k\nabla f(x_k))$$
  非常简洁；只要能有效计算近端算子，迭代计算量就不大。
• 收敛性强：在凸设置下保证全局收敛；能结合线搜索或加速技巧进一步提高效率。
• 可扩展性：可与随机梯度、坐标下降、ADMM、并行化/分布式方法等灵活结合，处理大规模或复杂结构问题。