Proximal Gradient Method在L1正则化问题中的加速收敛

1. 理解L1正则化问题的挑战

明确 优化目标：求解形如 $\min_{x} f(x) + \lambda \|x\|_1$ 的问题，其中 $f(x)$ 是光滑凸函数（例如最小二乘损失函数），$\lambda \|x\|_1$ 是L1惩罚项。该问题在机器学习中用于特征选择，能产生稀疏解。

识别 主要难点：L1范数 $\|x\|_1$ 不可微（在零点不可导），导致传统的梯度下降法无法直接应用。解决此问题的核心是将“光滑”的损失函数部分与“非光滑”的正则化部分分开处理。

拆解 标准优化框架：将问题视为两个函数之和。一个函数是 $f(x)$，它光滑且梯度 $\nabla f$ 容易计算；另一个函数是 $g(x) = \lambda \|x\|_1$，它虽然不光滑，但拥有一个高效的“近端算子”。

2. 掌握基础算法：近端梯度法

理解 算法思想：在每一步迭代中，先沿着光滑部分 $f(x)$ 的负梯度方向前进，然后利用近端算子对结果进行“修正”或“投影”，以处理非光滑部分 $g(x)$。

执行 标准迭代公式：算法的关键更新步骤为：
$$ x_{k+1} = \text{prox}_{\eta g}\left( x_k - \eta \nabla f(x_k) \right) $$
其中 $\eta > 0$ 是步长（学习率），$\text{prox}$ 是近端算子。

计算 L1范数的近端算子：对于 $g(x) = \lambda \|x\|_1$，其近端算子就是著名的软阈值算子。对于向量 $v$ 的每个分量 $v_i$，该算子操作定义为：
$$ \left( \text{prox}_{\eta g}(v) \right)_i = \text{sign}(v_i) \cdot \max(|v_i| - \eta\lambda, 0) $$
这个操作的意义是，将向量每个分量向零收缩 $\eta\lambda$，但不会越过零点。

执行 一次迭代：对于当前点 $x_k$，先计算梯度步 $z = x_k - \eta \nabla f(x_k)$，然后对 $z$ 的每一个分量独立地应用上述软阈值操作，得到 $x_{k+1}$。这种处理方式高效且能产生稀疏解。

3. 引入加速思想：Nesterov动量

观察 基础算法的收敛速度：标准的近端梯度法具有次线性收敛速度，即误差随迭代次数 $k$ 以 $O(1/k)$ 的速度下降。这意味着在接近最优解时，收敛会变得缓慢。

采用 Nesterov加速技巧：该技巧通过引入一个“动量项”来修正迭代过程，能显著提升收敛速度至 $O(1/k^2)$。核心思想是利用前一次的更新方向来“预判”和加速当前的更新。

理解 加速算法的更新流：与标准方法不同，加速版本会维护两个序列：一个用于计算梯度（动量序列 $y_k$），另一个用于存储当前估计（解序列 $x_k$）。更新顺序变为“先用动量估计计算梯度，再更新解，最后更新动量”。

4. 实现加速近端梯度法的具体步骤

初始化 算法参数：

1. 选择 合理的步长 $\eta$，例如可以尝试 $\eta = 1/L$，其中 $L$ 是 $\nabla f$ 的Lipschitz常数。如果未知，可通过线搜索确定。
2. 设定 初始点 $x_0$ 和 $y_1 = x_0$。动量系数 $\theta_k$ 通常初始化为 $\theta_1 = 1$。
3. 设置 算法的最大迭代次数 max_iter 和收敛容差 tol。

执行 加速迭代循环（对于 $k=1, 2, \dots, \text{max\_iter}$）：

1. 计算 动量序列 $y_k$ 处的梯度：$\nabla f(y_k)$。
2. 执行 梯度步并软阈值：计算 $z_k = \text{prox}_{\eta g}(y_k - \eta \nabla f(y_k))$。
3. 更新 解序列：$x_{k+1} = z_k$。
4. 更新 动量系数：$\theta_{k+1} = \frac{2}{k+2}$ （一种常用策略）。
5. 更新 动量序列：$y_{k+1} = x_{k+1} + \frac{\theta_{k+1}(1-\theta_k)}{\theta_k} (x_{k+1} - x_k)$。
6. 检查 收敛条件：例如，判断 $\|x_{k+1} - x_k\|$ 是否小于 tol。若满足则跳出循环。

检查 代码实现要点：在编程实现时，确保软阈值操作是对向量的每个分量独立进行的。梯度计算函数 grad_f 和近端算子函数 prox（即软阈值）应分别封装，以保持主循环的清晰。

def soft_threshold(v, threshold):
    """软阈值操作，即L1范数的近端算子。"""
    return np.sign(v) * np.maximum(np.abs(v) - threshold, 0)

def accelerated_prox_grad(grad_f, prox, x0, eta, lam, max_iter, tol):
    x = x0.copy()
    y = x0.copy()
    theta = 1.0
    for k in range(1, max_iter + 1):
        grad = grad_f(y)
        # 梯度步 + 软阈值
        x_new = prox(y - eta * grad, eta * lam)
        # 更新动量系数
        theta_new = 2.0 / (k + 1)
        # 更新动量序列
        y = x_new + (theta_new * (1 - theta) / theta) * (x_new - x)
        # 检查收敛
        if np.linalg.norm(x_new - x) < tol:
            break
        # 为下次迭代准备
        x = x_new
        theta = theta_new
    return x

调整 与调优：

1. 监控 目标函数值：绘制目标函数 $f(x) + \lambda \|x\|_1$ 随迭代次数的下降曲线，可以直观看到加速版本下降更快。
2. 调节 正则化参数 $\lambda$：$\lambda$ 越大，解越稀疏。通常使用交叉验证来选择最优的 $\lambda$ 值。
3. 处理 非凸变体：对于某些问题，L1正则项可能与其他非凸项结合。此时，需要确保近端算子仍然可计算，或者使用近端线性化等近似方法。