近端梯度下降：高效处理L1正则与稀疏模型优化

1. 为什么梯度下降在最常见的稀疏模型上突然失效了

先聊个非常实际的场景。你在做机器学习模型，目标函数是损失项加正则项，其中正则项用了L1范数。L1正则的好处大家都知道，能压出稀疏解，特征选择利器。我们习惯性掏出梯度下降就开始迭代，结果发现更新到某个分量附近时，梯度方向总在来回跳动，收敛速度肉眼可见地慢，甚至在一些点上压根停不下来。

原因不复杂。L1范数在原点处不可导，标准梯度下降要求目标函数处处可微，一旦遇到不可微点，梯度要么不存在，要么只能用次梯度来代替。次梯度法虽然理论上有收敛保证，但实际速度非常慢，收敛率通常只有O(1/√k)的量级，对大规模问题来说基本是不能忍的。

这时就需要换一种思路。既然目标函数本身可以拆成“光滑部分”和“非光滑部分”，那我们为什么还要用一把“钝刀”去同时处理这两部分呢？能不能对光滑部分继续用梯度下降的成熟思路，对非光滑部分单独设计一个简单高效的算子来处理？这就是近似梯度下降（Proximal Gradient Descent）的核心动机。

近似梯度下降最大的魅力在于：它的每一步计算成本通常和一次普通梯度下降差不多，却能把不可导的正则项处理得干净利落。尤其是当非光滑项是L1范数、L2范数、指示函数这类常见形式时，对应的近端算子都有显式公式，写代码特别简单。这篇文章我会从原理讲到代码，再讲收敛性和加速版本，最后分享一些实际调参中踩过的坑。

2. 目标函数的拆解与近端算子：一个被低估的关键设计

2.1 把目标函数写成“光滑+非光滑”结构

近似梯度下降面对的问题形式非常明确：

min f(x) = g(x) + h(x)

其中g(x)是光滑的凸函数，也就是梯度Lipschitz连续，这是保证算法稳定性的核心条件；h(x)可以是非光滑凸函数，甚至可以是那种取值正无穷的指示函数，用来表示约束条件。

这种写法不是为了数学上的美观，而是算法设计的起点。常见的组合包括：

• 岭回归/逻辑回归加L1正则：g是平方损失或对数损失，h是λ||x||₁
• 带约束的优化问题：h是某个集合的指示函数
• 低秩矩阵恢复：h是核范数乘以系数
• 图像去噪中的全变分模型：h是TV范数

把问题拆成两部分之后，我们就不用再对h求梯度，转而使用近端算子来处理它。

2.2 近端算子的直觉：先迈一小步，再被拉回来

近端算子的定义是：

prox_{t h}(x) = argmin_z [ h(z) + (1/(2t)) ||z - x||² ]

理解这个式子有个特别直观的方式。公式里有两股力量在拉扯变量z：一股力量来自h(z)，它希望z落在h比较小的地方；另一股力量来自||z - x||²，它希望z不要离x太远。t在这里起一个平衡作用，t越大，h对z的牵引力占比越大，z就越可能被拉到h的“低值区域”；t越小，z就越贴近原来的x。

我用个生活化的类比：你站在一个位置，发现前面有个坑（h很低的地方），但你又不想走太远。每次只往坑的方向迈一步，又因为“别离原点太远”这个约束被拉回来一点。来回几次之后，你就稳定在一个平衡点。这个平衡点就是prox算子的输出。

那为什么叫“近端”呢？因为它本质上是在做一种带有惩罚的投影。普通的投影是找到集合里离你最近的点，而近端算子是找到“让h尽量小且离x不太远”的点。h如果是一个集合的指示函数，近端算子就退化成了普通的欧氏投影，这时你会发现近端梯度下降和“梯度下降+投影”的投影梯度法完全一致。

2.3 最常用的几个近端算子，要能随手写出来

实际应用里，90%的情况你只需要记住下面这几个近端算子的闭式解。

第一个是L1范数的近端算子，也就是软阈值操作：

prox_{t λ||·||₁}(x) = sign(x) · max(|x| - tλ, 0)

逐分量操作。这个公式极其重要，它是LASSO、稀疏编码、压缩感知里一切迭代软阈值类算法的基础。

第二个是L2范数平方的近端算子，也就是收缩：

prox_{tλ||·||²}(x) = x / (1 + 2tλ)

第三个是指示函数的近端算子，也就是投影。比如约束条件是x ≥ 0，近端算子就是把负分量置零；约束条件是某个凸集C，近端算子就是把点投影到C上。

第四个是核范数的近端算子，涉及矩阵奇异值软阈值：先对矩阵做SVD，然后把奇异值做软阈值处理。低秩矩阵恢复里大量用这个。

这些算子都有一个共同特点：计算代价低，形式简单。这也是近似梯度下降能应用到大规模问题上的根本原因。

3. 近似梯度下降的完整算法：从公式到像样的代码

3.1 迭代格式的逻辑推导

近似梯度下降的迭代式长这样：

x_{k+1} = prox_{t h}( x_k - t ∇g(x_k) )

每一步做的事情可以拆成两步理解。第一步，x_k - t∇g(x_k)就是普通梯度下降对光滑部分g的一次更新；第二步，把更新后的点丢进近端算子，用h对结果做修正。

这个格式在设计上有几个巧妙之处。

首先，它保留了梯度下降对光滑部分的高效性。g的梯度信息被充分利用，迭代方向不再是粗糙的次梯度方向，因此收敛速度快很多。

其次，近端算子每次只处理非光滑部分，而且不要求h可微，这解决了L1等正则项带来的麻烦。

最后，整个迭代可以证明是单调下降的，而且在步长设置得当的前提下，目标函数值会稳定收敛到最优值。

3.2 步长选择和Lipschitz常数估计

近端梯度下降有一个关键参数：步长t。理论要求是步长满足t ≤ 1/L，其中L是∇g的Lipschitz常数，这时算法具有O(1/k)的收敛率。

实际操作中，L很少能被精确算出来。一种做法是直接用回溯线搜索：每次迭代先取一个较大的t，如果发现目标函数值没有下降，就把t乘以一个小于1的系数（比如0.5）缩小，直到满足下降条件。这种做法在实践中非常稳健。

如果g是平方损失这类简单函数，L可以直接算。以线性回归为例，g(x) = (1/2)||Ax - b||²，∇g(x) = Aᵀ(Ax - b)，其Lipschitz常数就是AᵀA的最大特征值。用幂迭代法或者直接算最大奇异值就能得到，然后令t = 1/L即可。

3.3 一个可以直接复用的Python实现

以LASSO为例，目标函数是(1/2)||Ax - b||² + λ||x||₁。下面是完整的近端梯度下降实现，注释写得很细。

import numpy as np def soft_threshold(x, threshold): """软阈值算子：L1范数的近端映射""" return np.sign(x) * np.maximum(np.abs(x) - threshold, 0.0) def proximal_gradient_lasso(A, b, lam, x0, max_iter=1000, tol=1e-6): # 计算 Lipschitz 常数：A^T A 的最大特征值 # 实际工程中可以用幂迭代法避免显式构造 A^T A L = np.linalg.eigvalsh(A.T @ A).max() t = 1.0 / L x = x0.copy() history = [] for k in range(max_iter): grad = A.T @ (A @ x - b) # 先沿梯度方向走一步 y = x - t * grad # 再用软阈值算子处理 L1 正则项 x_new = soft_threshold(y, t * lam) # 记录目标函数值，用于观察收敛 obj = 0.5 * np.linalg.norm(A @ x_new - b) ** 2 + lam * np.abs(x_new).sum() history.append(obj) if np.linalg.norm(x_new - x) < tol: break x = x_new return x, history def objective(X, y, w, lam): return 0.5 * np.linalg.norm(X @ w - y) ** 2 + lam * np.abs(w).sum()

用这份代码跑一个合成数据的小实验，你会看到目标函数值一路下降，并且稀疏解的特征非常明显。很多分量会精确地变成0，这正是软阈值算子的功劳——它不像次梯度法那样“磨磨蹭蹭”地接近0，而是直接一刀切。

3.4 停止准则不能只看梯度范数

用近似梯度下降时，最常见的停止准则错误是沿用普通梯度下降的习惯，去看梯度范数。但在近端梯度下降里，目标函数不可微，梯度范数在最优解处不一定趋于0。

正确的做法是看近端梯度（proximal gradient）的大小，定义为：

G_t(x) = (x - prox_{t h}(x - t∇g(x))) / t

这个量在x是最优解时恰好为0。所以在实际实现中，可以计算||G_t(x)||，当它小于某个阈值时认为算法已收敛。另一种更省事的做法是直接看相邻迭代点之间的距离||x_{k+1} - x_k||，工程上这样用的很多，虽然理论上稍微弱一点，但配合目标函数值监控一般是够用的。

4. 收敛性：为什么它能同时做到高效和稳定

4.1 收敛率的直观解释

近似梯度下降的关键性质是：当步长t满足0 < t ≤ 1/L时，目标函数值以O(1/k)的速度收敛到最优值。这个结论比次梯度法的O(1/√k)要好得多。

理解这个差距，可以从迭代的行为来看。次梯度法因为使用的是不可微点的次梯度，方向往往不是最陡下降方向，甚至可能和真实下降方向差得很远，所以走得很“犹豫”。近似梯度下降则不同，它的更新方向等价于一个“带正则修正的梯度方向”，这个方向在光滑部分的意义下是下降方向，同时又把非光滑部分的作用精确地融合了进来。

打个比方，次梯度法像在凹凸不平的路面上靠感觉摸索前进，每一步都很谨慎，但方向容易偏；近似梯度下降则像先对照地图走到大致方向，再把路障挨个处理掉，步骤之间有明确的目标。

4.2 证明中最重要的不等式链条

虽然完整证明比较复杂，但核心逻辑值得了解，因为理解它有助于你调试算法。

基本思路是构造一个关于点列{x_k}的递推不等式。利用梯度Lipschitz连续性，可以得到g(x_{k+1})的一个上界，把g的变化用二次项控制住；再利用近端算子的性质，可以推出h(x_{k+1})和h(x_k)之间的关系。把两者合在一起，就能得到类似下面的形式：

f(x_{k+1}) ≤ f(x_k) - (1/(2t))||x_{k+1} - x_k||²

或者是更精细的带任意参考点x*的界。这里注意，近端算子的“收缩性”和不光滑项的“足够下降”性质是整个证明的关键。

再结合凸函数的最优性条件，可以构造出f(x_k) - f(x*)的上界正比于1/k，这就得到了O(1/k)的收敛率。整个过程不需要假设h可微，只需要h是凸函数。

4.3 和普通梯度下降、投影梯度法的关系

近似梯度下降其实是一个很广的框架，很多算法是它的特例。

当h(x)恒等于0时，近端算子就是恒等映射，算法退化为标准梯度下降。

当h是某个凸集C的指示函数时，prox算子变成向C的投影，算法变成投影梯度法。

当g(x)恒等于0时，算法退化为纯粹的近端点算法（Proximal Point Algorithm），这个算法本身有更好的收敛性质。

理解这些关系，对你判断算法行为很有帮助。比如你写了一个投影梯度法来求解带约束的问题，它其实就是一个近端梯度下降的特例，所有关于步长、收敛率的分析同样适用。

5. 加速版本：Nesterov动量为什么能让它更快

5.1 从O(1/k)到O(1/k²)的跳跃

近似梯度下降的标准版本虽然好用，但O(1/k)的收敛率在精度要求高时还是偏慢。好消息是，我们可以借鉴Nesterov加速梯度法的思想，把收敛率提升到O(1/k²)。加速后的算法就是著名的FISTA（Fast Iterative Shrinkage-Thresholding Algorithm）。

加速的代价非常小，只在迭代格式里多加一个“外推点”。工程上经常说“免费的午餐”，这个算是教科书级别的例子。

5.2 FISTA的具体形式和注意事项

FISTA的迭代格式如下：

y_k = x_k + ((α_{k-1} - 1) / α_k) (x_k - x_{k-1}) x_{k+1} = prox_{t h}(y_k - t∇g(y_k))

其中α_k的更新方式是：

α_{k+1} = (1 + sqrt(1 + 4α_k²)) / 2

初始时α_0 = 1。可以注意到，外推系数(α_{k-1} - 1)/α_k在迭代初期约为0.5，随着迭代逐渐趋于1。也就是说，算法在后期越来越倾向于在原有方向的基础上继续往前走，而不是每次从头开始修正。

FISTA的实现代码很简单，只需要在普通近端梯度下降的基础上加两行：

alpha_new = (1 + np.sqrt(1 + 4 * alpha_old ** 2)) / 2 y = x + ((alpha_old - 1) / alpha_new) * (x - x_old) alpha_old = alpha_new

但有几个使用上的要点必须注意。

第一，FISTA的目标函数值不一定单调下降。迭代过程中偶尔会出现目标函数值反弹的情况，这是正常现象，不要误以为算法发散了。如果实在需要单调版本，可以对每次迭代的结果做一次回退判断：计算出x_{k+1}后，如果f(x_{k+1}) > f(x_k)，就退回使用不加外推的普通近端梯度更新。

第二，Lipschitz常数或者回溯线搜索的初始值如果不准确，加速版本的震荡幅度会比普通版本大得多。建议先用普通版本跑几百步，粗略估计一个合理的t，再切换到FISTA。

5.3 实际加速效果

我在一组中等规模的LASSO问题上做过对比。样本量大约数万，特征维度数千，用普通近端梯度下降跑到目标函数值降到某个精度大约需要两千次迭代，FISTA只需要三百次左右。加速效果非常明显，尤其是在迭代初期，FISTA的下降曲线几乎是垂直下落的。

不过也要泼一盆冷水：如果问题本身的条件数很差，也就是L很大但最优点的附近很“平坦”，那么FISTA的加速效果会被明显削弱。这种情况下可以考虑用对角预条件或者更高级的预处理技术。

6. 真实项目里的坑：近端梯度下降的调参笔记

6.1 先估计L，再谈调参

很多初学者拿到问题，第一件事是设步长为0.01或者0.001，然后慢慢试。这种做法效率很低。

正确的起点是先估计Lipschitz常数L。对于线性模型，直接算最大特征值；对于非线性模型，用回溯线搜索自动确定步长。我个人的经验是：手动调参时，宁可步长偏小也不要偏大。近端梯度下降在步长超过1/L时会出现目标函数值震荡上升，非常不好排查。

如果发现迭代过程中目标函数值不降反升，优先检查是不是步长太大，而不是怀疑代码写错。

6.2 稀疏解“差一点点”的常见原因

使用L1正则时有一个非常常见的现象：算法跑完，大部分分量都收敛了，但有少数分量在0附近来回跳动，数值始终达不到精确的0。很多人以为是软阈值写错了，其实原因往往是停止准则太松或者步长太保守。

如果步长太小，软阈值操作中乘上的系数tλ太小，导致分量虽然被压缩但还没有被压到0，此时需要更多迭代才能把分量精确置零。解决思路是：要么适当增大步长到接近1/L，要么提高迭代次数上限，要么将最终输出做一次额外的“精确置零”操作，即对绝对值小于某个阈值的分量直接赋0。

另外，特征之间的尺度差异也会影响稀疏模式。如果某一列特征的尺度远大于其他列，对应的系数会被过度惩罚或欠惩罚。建议在建模前先对特征做标准化。

6.3 从L1到TV：近端梯度的更大舞台

近端梯度下降不只在稀疏回归里好用。图像处理中的全变分去噪模型形式是min ||x - y||² + λ·TV(x)，其中TV项的全变分范数是不可微的。用近端梯度下降处理时，需要用到TV范数的近端算子，没有简单的逐分量软阈值公式，通常要在对偶空间里迭代求解。这也是近端梯度框架威力最大的地方：只要你能写出或算出一个近端算子，这个算法框架就能套上去。

我在一个模拟图像去噪任务中实现过这个思路，效果远好于直接对TV项做次梯度处理。收敛速度从几千步缩短到几百步，而且重建图像的边缘保持效果更好。

6.4 非精确近端算子的处理经验

实际项目中还有一个容易被忽视的问题：有些近端算子本身没有闭式解，需要通过内层迭代来求近似解。这时如果内层迭代精度不够，外层近端梯度下降的收敛性会受影响。

我的经验是：在算法初期，可以适当放宽内层迭代精度，因为此时外层还在“大踏步”前进，精确求解近端算子的收益不高；但在算法后期，尤其是接近收敛时，必须提高内层精度，否则外层算法会出现锯齿状的波动，迟迟不收敛。

这个“前期粗糙、后期精细”的策略，在很多实际问题里能把总计算时间减少一半以上。

7. 面向初学者的选型建议：什么时候该用近端梯度下降

如果你在犹豫某个问题该不该用近端梯度下降，可以参考下面几条判断标准。

第一，目标函数是否自然拆成光滑部分和非光滑部分。比如“损失函数+L1正则”“损失函数+约束”“损失函数+核范数”，这些都是近端梯度下降的典型适用场景。如果目标函数本身就是处处光滑的，那直接用普通的梯度下降或者牛顿法往往更合适。

第二，非光滑部分的近端算子是否容易计算。如果近端算子没有闭式解且内层求解代价非常高，那么近端梯度下降的优势会被削弱。

第三，问题规模是否足够大，以至于次梯度法的收敛速度无法接受。小规模问题上，次梯度法虽然慢但也不是不能用；大规模问题上，O(1/√k)和O(1/k)的差距会被放大到难以跨越。

下面用一张表总结不同算法在相似条件下的表现：

这份表格基本就是选型地图。如果你发现自己的问题里有不可微的正则项，而且光滑部分还好处理，那近端梯度下降大概率是正确选择。

8. 我的使用体会与一个实用小技巧

近端梯度下降是我在实际项目里用到最多的优化算法之一，不是因为它花哨，而是因为它把“处理不可微项”这件事模块化了。以前遇到L1正则，要么拖着沉重的次梯度法跑，要么手动搞一套坐标下降，坐标循环在大规模问题上的并行性又很差。近端梯度下降解决了这两个痛点，收敛快、代码简单、支持模块化替换近端算子。

最后分享一个我自己摸索出来的小技巧。实际工程中经常需要在一个模型上测试多个不同的正则系数λ，比如做正则路径或者交叉验证。这时候不要每次都用同一个初始点从头跑，而是用上一个λ的解作为当前λ的初始点，也就是常说的热启动（warm start）。

因为相邻λ下的最优解通常非常接近，热启动可以让近端梯度下降在很少的迭代次数内收敛。我在做稀疏模型的正则路径扫描时，用了这个技巧后总计算时间减少了一个数量级。如果你正好在做类似的事情，强烈建议试一下。