次梯度与近端方法

概述

在机器学习中，许多损失函数（如 $L_1$ 正则化、hinge loss）是非光滑的，传统的梯度下降法不再适用。次梯度（Subgradient）和近端方法（Proximal Methods）提供了处理非光滑优化问题的强大框架。¹

核心问题：当函数在某点不可微时，如何定义”下降方向”？如何高效地优化包含非光滑项的目标函数？

---

次微分（Subdifferential）

不可微函数示例

在机器学习中常见的非光滑函数：

函数	定义	不可微点
绝对值	$	x
$L_1$ 范数	$\Vert w{\Vert }_1$	$w_i=0$
ReLU	$\max (0,x)$	$x=0$
Hinge Loss	$\max (0,1-yx)$	$yx=1$
$L_{2,1}$ 范数	${\sum }_i\Vert w_i\Vert$	$w_i=0$

次梯度的定义

定义：设 $f:{\mathbb{R}}^n\to \mathbb{R}\cup \{+\infty \}$ 是凸函数。点 $x$ 处的次梯度（Subgradient）是满足以下条件的向量 $g$：

$$f(y)\ge f(x)+g^T(y-x),\forall y$$

所有次梯度的集合称为次微分（Subdifferential），记作 $\partial f(x)$。

几何直观

         f(y)
          │
     f(y) │      ╱
          │     ╱  ← 支撑超平面
          │    ╱
          │   ╱
          │  ╱
     f(x) │ ╱_________________
          │x
          └──────────────────── y
          
          切线在不可微点变成一族支撑超平面

一维示例：绝对值函数

$$f(x)=|x|,x\in \mathbb{R}$$

次微分：

$$\partial f(x)=\{\begin{array}{ll}\{-1\}& x<0\\ [-1,1]& x=0\\ \{+1\}& x>0\end{array}$$

Python验证：

import numpy as np
 
def subdiff_abs(x):
    """绝对值函数的次微分"""
    if x < 0:
        return np.array([-1.0])
    elif x > 0:
        return np.array([1.0])
    else:
        return np.array([-1.0, 1.0])  # 区间
 
for x in [-1, 0, 1]:
    print(f"∂|x| at x={x}: {subdiff_abs(x)}")

次梯度的性质

性质	描述
存在性	凸函数在内部点次梯度存在
唯一性	函数光滑点次梯度唯一
极值条件	$0\in \partial f(x^{\star })⟺x^{\star }$ 最优
链式法则	$\partial (g\circ h)(x)\supseteq \partial g(h(x))\cdot \partial h(x)$

---

次梯度下降法

算法

次梯度下降法（Subgradient Method）：

$$x^{k+1}=x^k-{\alpha }^k{g}^k$$

其中 $g^k\in \partial f(x^k)$ 是任意次梯度，${\alpha }^k>0$ 是步长。

与梯度下降的区别

特性	梯度下降	次梯度下降
收敛性	保证收敛到驻点	不保证单调下降
步长选择	线搜索可用	需要预定义步长序列
收敛速度	$O(1/{ϵ}^2)$	$O(1/{ϵ}^2)$
实用性	光滑问题	非光滑问题

收敛性分析

定理：设步长满足 ${\sum }_k{\alpha }^k=\infty$ 和 ${\sum }_k({\alpha }^k{)}^2<\infty$（例如 ${\alpha }^k=1/k$），则次梯度方法收敛：

$$\underset{k\to \infty }{\lim }f(x^k)=f^{\star }$$

但收敛速度较慢：$O(1/\sqrt{k})$。

固定步长次梯度法

对于有界域问题，使用固定步长 $\alpha$：

$$f(x^k)-f^{\star }\le \frac{\Vert x^0-x^{\star }{\Vert }^2}{2k\alpha }+\frac{\alpha G^2}{2}$$

其中 $G$ 是次梯度的界。第二项是”噪声底”，存在最优步长 ${\alpha }^{\star }\propto \sqrt{k}$。

---

近端算子（Proximal Operator）

定义

对于凸函数 $g$，近端算子（Proximal Operator）定义为：

$${\text{prox}}_g(x)=\arg \underset{y}{\min }\left\{g(y)+\frac{1}{2}\Vert y-x{\Vert }^2\right\}$$

直观理解：$y$ 是 $x$ 的”软投影”——在最小化 $g(y)$ 的同时保持与 $x$ 的接近。

几何直观

                    约束可行域 {y: g(y) ≤ c}
                         ╱╲
                        ╱  ╲
                       ╱    ╲
                      ╱      ╲
                     ╱        ╲
                    ╱    x    ╲ ← 当前点
                   ╱      ↓    ╲
                  ╱        ↓    ╲
                 ╱          ↓    ╲
                ╱          prox_g(x) ← 软投影点
               ╱            ↗    ╲
              ╱                      ╲
             ─────────────────────────────

近端算子的性质

性质	公式	说明
幂等性	${\text{prox}}_g({\text{prox}}_g(x))={\text{prox}}_g(x)$	投影两次等于一次
对偶性	$x\in {\text{prox}}_g(z)⟺z-x\in \partial g(x)$	与次梯度联系
组合	${\text{prox}}_{g+h}\ne {\text{prox}}_g\circ {\text{prox}}_h$	一般不能分离
线性组合	${\text{prox}}_{\lambda g}(x)={\text{prox}}_{g/\lambda }(x/\lambda )\cdot \lambda$	缩放性质

常见近端算子

函数 $g$	近端算子 ${\text{prox}}_g(x)$	形式
$L_2$ 范数	${\text{prox}}_{\lambda \Vert \cdot {\Vert }_2}(x)$	$(1-\lambda /\Vert x{\Vert }_2{)}_{+}x$
$L_1$ 范数	${\text{prox}}_{\lambda \Vert \cdot {\Vert }_1}(x)$	$\text{sign}(x)\odot \max (0,\Vert x\Vert -\lambda )$
指示函数	${\text{prox}}_{{\delta }_C}(x)$	$P_C(x)$（欧氏投影）
二次函数	${\text{prox}}_{\lambda /2\Vert \cdot {\Vert }^2}(x)$	$\frac{x}{1+\lambda }$

软阈值算子（Soft-Thresholding）

对于 $L_1$ 正则化，近端算子就是软阈值（Soft-Thresholding）或收缩算子：

$${\text{prox}}_{\lambda \Vert \cdot {\Vert }_1}(x{)}_i=\text{sign}(x_i)\cdot \max (0,|x_i|-\lambda )$$

import numpy as np
 
def soft_threshold(x, threshold):
    """软阈值算子（ shrinkage operator）"""
    return np.sign(x) * np.maximum(np.abs(x) - threshold, 0)
 
# 示例
x = np.array([3.0, -2.0, 0.5, -0.3])
threshold = 1.0
print(f"原向量: {x}")
print(f"软阈值(λ={threshold}): {soft_threshold(x, threshold)}")

---

近端梯度法（Proximal Gradient Method）

问题形式

考虑复合优化问题：

$$\underset{x}{\min }\{F(x)=f(x)+g(x)\}$$

其中：

• $f$：光滑凸函数，可微分，梯度 $\nabla f$ Lipschitz 连续（常数 $L$）
• $g$：非光滑凸函数，近端算子 ${\text{prox}}_g$ 易计算

典型应用

应用	$f(x)$	$g(x)$
LASSO	$\frac{1}{2}\Vert Ax-b{\Vert }^2$	$\lambda \Vert x{\Vert }_1$
弹性网	$\frac{1}{2}\Vert Ax-b{\Vert }^2$	${\lambda }_1\Vert x{\Vert }_1+{\lambda }_2\Vert x{\Vert }_2^2$
Group LASSO	$\frac{1}{2}\Vert Ax-b{\Vert }^2$	$\lambda {\sum }_g\Vert x_g{\Vert }_2$
约束优化	$\ell (x)$	${\delta }_C(x)$

算法

近端梯度法（Proximal Gradient Method, PGM）：

$$x^{k+1}={\text{prox}}_{{\alpha }^{k}g}\left(x^k-{\alpha }^k\nabla f(x^k)\right)$$

其中 ${\alpha }^k\in (0,1/L]$ 是步长。

收敛速度

定理：对于 $L$-Lipschitz 连续梯度，使用固定步长 $\alpha =1/L$：

$$F(x^k)-F^{\star }=O\left(\frac{1}{k}\right)$$

加速近端梯度法（Accelerated Proximal Gradient Method, APGM）达到 $O(1/k^2)$：

$$\begin{array}{rl}{y}^{k+1}& =x^k+\frac{k-1}{k+2}(x^k-x^{k-1})\\ x^{k+1}& ={\text{prox}}_{\alpha g}\left(y^{k+1}-\alpha \nabla f(y^{k+1})\right)\end{array}$$

Python实现

import numpy as np
 
def proximal_gradient_method(f, grad_f, prox_g, x0, alpha, max_iter=1000, tol=1e-6):
    """
    近端梯度法
    
    Args:
        f: 目标函数
        grad_f: f的梯度
        prox_g: g的近端算子
        x0: 初始点
        alpha: 步长
        max_iter: 最大迭代次数
        tol: 收敛容差
    
    Returns:
        x: 最优解
        losses: 损失历史
    """
    x = x0.copy()
    losses = [f(x)]
    
    for k in range(max_iter):
        # 近端梯度步
        x_new = prox_g(x - alpha * grad_f(x), alpha)
        
        # 记录损失
        losses.append(f(x_new))
        
        # 收敛检查
        if np.linalg.norm(x_new - x) < tol:
            print(f"在第 {k+1} 步收敛")
            break
        
        x = x_new
    
    return x, losses
 
def accelerated_pgm(f, grad_f, prox_g, x0, alpha, max_iter=1000, tol=1e-6):
    """
    加速近端梯度法 (FISTA)
    """
    x = x0.copy()
    y = x0.copy()
    t = 1.0
    losses = [f(x)]
    
    for k in range(max_iter):
        # 保存上一步
        x_old = x.copy()
        
        # 近端梯度步
        x = prox_g(y - alpha * grad_f(y), alpha)
        
        # 加速项
        t_new = (1 + np.sqrt(1 + 4 * t**2)) / 2
        y = x + (t - 1) / t_new * (x - x_old)
        t = t_new
        
        losses.append(f(x))
        
        if np.linalg.norm(x - x_old) < tol:
            print(f"在第 {k+1} 步收敛")
            break
    
    return x, losses
 
# 示例：LASSO
from scipy.linalg import lstsq
 
def lasso_prox(A, b, lambda_reg, x0, alpha, max_iter=1000):
    """LASSO: min 1/2||Ax - b||^2 + λ||x||_1"""
    m, n = A.shape
    
    def f(x):
        r = A @ x - b
        return 0.5 * np.sum(r**2)
    
    def grad_f(x):
        return A.T @ (A @ x - b)
    
    def prox_g(x, alpha):
        # soft_threshold
        return np.sign(x) * np.maximum(np.abs(x) - alpha * lambda_reg, 0)
    
    return proximal_gradient_method(f, grad_f, prox_g, x0, alpha, max_iter)
 
# 测试
np.random.seed(42)
m, n, k = 100, 50, 10
A = np.random.randn(m, n)
x_true = np.zeros(n)
x_true[:k] = np.random.randn(k)
b = A @ x_true + 0.1 * np.random.randn(m)
 
x0 = np.zeros(n)
alpha = 1.0 / (np.linalg.norm(A, ord=2)**2)  # 步长上界
 
x_opt, losses = lasso_prox(A, b, 0.1, x0, alpha)
print(f"非零分量数量: {np.sum(np.abs(x_opt) > 1e-4)}")

---

ADMM（交替方向乘子法）

形式

ADMM用于可分离的约束优化问题：

$$\begin{array}{rl}\underset{x,z}{\min }& f(x)+g(z)\\ \text{s.t.}& Ax+Bz=c\end{array}$$

算法

$$\begin{array}{rl}{x}^{k+1}& =\arg \underset{x}{\min }f(x)+\frac{\rho }{2}\Vert Ax+B{z}^k-c+u^k{\Vert }_2^2\\ z^{k+1}& =\arg \underset{z}{\min }g(z)+\frac{\rho }{2}\Vert A{x}^{k+1}+Bz-c+u^k{\Vert }_2^2\\ u^{k+1}& =u^k+A{x}^{k+1}+B{z}^{k+1}-c\end{array}$$

其中 $u$ 是缩放对偶变量。

与近端方法的关系

ADMM可以看作近端方法的扩展：

• 交替优化 $x$ 和 $z$
• 用增广拉格朗日惩罚约束

ADMM的收敛

ADMM在以下条件下收敛：

1. $f,g$ 是闭凸函数
2. 拉格朗日函数有鞍点
3. $A$ 或 $B$ 列满秩（某种形式）

收敛速度：$O(1/k)$（原始-对偶残差）。

---

近端方法在机器学习中的应用

1. LASSO回归

def lasso_admm(A, b, lambda_reg, rho=1.0, max_iter=1000, tol=1e-4):
    """
    ADMM求解LASSO: min 1/2||Ax - b||^2 + λ||z||_1
    s.t. x = z
    """
    m, n = A.shape
    x = np.zeros(n)
    z = np.zeros(n)
    u = np.zeros(n)  # 对偶变量
    
    # 预计算
    Atb = A.T @ b
    # (A^T A + ρI)^{-1} 缓存
    Q = A.T @ A + rho * np.eye(n)
    
    for k in range(max_iter):
        # x-更新（线性求解）
        x_new = np.linalg.solve(Q, Atb + rho * (z - u))
        
        # z-更新（近端算子）
        z_new = soft_threshold(x_new + u, lambda_reg / rho)
        
        # 对偶更新
        u_new = u + x_new - z_new
        
        # 收敛检查
        primal_res = np.linalg.norm(x_new - z_new)
        dual_res = np.linalg.norm(rho * (z_new - z))
        
        if primal_res < tol and dual_res < tol:
            print(f"ADMM在第{k+1}步收敛")
            break
        
        x, z, u = x_new, z_new, u_new
    
    return x

2. Group LASSO

def group_lasso_prox(x, groups, lambda_reg):
    """
    Group LASSO近端算子
    min λ∑_g ||z_g||_2 + 1/2||z - x||^2
    """
    z = np.zeros_like(x)
    for g_idx, group in enumerate(groups):
        x_g = x[group]
        norm_g = np.linalg.norm(x_g)
        if norm_g > 0:
            z[group] = x_g * max(0, 1 - lambda_reg / norm_g)
    return z

3. 总变差（Total Variation）正则化

def tv_prox_1d(x, lambda_reg):
    """
    一维总变差近端算子
    min λ||Dz||_1 + 1/2||z - x||^2
    其中 D 是差分算子
    """
    n = len(x)
    
    # 构建差分矩阵
    D = np.zeros((n-1, n))
    for i in range(n-1):
        D[i, i] = -1
        D[i, i+1] = 1
    
    # 使用闭式解： isotonic regression
    # 实际上 TV prox 可以通过 pool adjacent violators 算法求解
    y = x.copy()
    n = len(y)
    
    # 简化实现
    for _ in range(100):  # 迭代
        for i in range(n-1):
            if abs(y[i] - y[i+1]) > lambda_reg:
                # 需要合并区间
                pass
    
    return y  # 简化版本

---

总结

方法	适用场景	收敛速度
次梯度法	非光滑凸函数	$O(1/\sqrt{k})$
近端梯度法	光滑+非光滑复合	$O(1/k)$
加速PGM (FISTA)	同上	$O(1/k^2)$
ADMM	可分离约束问题	$O(1/k)$

近端方法是现代优化算法的基石：

• LASSO/弹性网的快速求解
• 图像处理中的TV正则化
• 联邦学习中的分布式优化

理解次梯度和近端算子对于设计高效的机器学习优化算法至关重要。

---

参考

Footnotes

1. Beck, A. (2017). First-Order Methods in Optimization. SIAM. ↩