加速梯度法 | Codeboy's Blog

形式陈述

给定可微目标 $f$ 、初值 $x_0$ 、有效光滑常数 $L$ 、容差和迭代预算，一种标准凸加速梯度法初始化 $y_1=x_0,t_1=1$ ；对 $k=1,2,\ldots$ 迭代

\begin{aligned} x_k&=y_k-\frac1L\nabla f(y_k),\\ t_{k+1}&=\frac{1+\sqrt{1+4t_k^2}}2,\\ y_{k+1}&=x_k+\frac{t_k-1}{t_{k+1}}(x_k-x_{k-1}). \end{aligned}

第一行是从外推点 $y_k$ 出发的一次梯度步，第三行用相邻主序列差构造下一查询点；首轮系数 $t_1-1=0$ ，所以无需额外定义 $x_{-1}$ 。算法可返回 $x_k$ 、梯度或函数值残差、迭代次数和失败状态； $y_k$ 是查询状态，不应与最终候选点混为一谈。这个更新对任意可微函数都能形式执行，但 $O(1/k^2)$ 的全局结论另需光滑凸假设及正确的 $L$ 。

递推恒等式 $t_{k+1}^2-t_{k+1}=t_k^2$ 是证明中权重望远镜消去的关键。实际未知 $L$ 时可以在每轮回溯，直到以二次上模型检验梯度步；回溯版必须同步维护证明要求的权重，不能只把 $L$ 临时改掉而保留不相容的动量。

直觉

普通梯度下降每轮丢弃上一方向，只保留当前位置。加速法把连续几轮的一致移动解释成“尚未走够”，将查询点向前外推；若新梯度仍支持这个趋势，历史位移便减少低曲率方向的拖延。与此同时，梯度步负责用局部二次模型校正外推，避免动量完全脱离目标。

加速不是保证每一步函数值更低的惯性小技巧。它依靠特定权重把函数值误差与一个辅助点到解的距离组合成势函数；单项可能上升，只要组合量下降即可。系数趋近一意味着后期会保留较长记忆，也解释了模型突然改变、常数错估或有限精度扰动时为何容易过冲。重启会在检测到不良外推时清空记忆，但何时重启是额外策略。

例子与边界

取 $f(x)=x^2/2$ ，真实最小光滑常数为 $1$ ，但假设只掌握安全上界 $L=4$ ，从 $x_0=1$ 开始。前两轮因 $t_1-1=0$ 与梯度下降相同：

x_1=0.75,\qquad x_2=0.5625.

$t_2=(1+\sqrt5)/2\approx1.618$ 、 $t_3\approx2.194$ ，于是

y_3=x_2+\frac{t_2-1}{t_3}(x_2-x_1) \approx0.5097,\qquad x_3\approx0.3823.

相同步长的普通梯度下降第三点是 $0.421875$ 。这条轨迹真实展示外推获得的增益，也展示加速不会凭空修正过度保守的 $L$ ；若使用紧常数 $L=1$ ，两种方法都在一次梯度步到达零，根本没有可加速的余地。

边界同样具体。低估 $L$ 会使梯度校正步越过二次上模型，动量随后可能放大误差；固定目标上的加速函数值也可能短暂上升或越过极小点。非凸目标没有本页势函数，照搬系数只是一种启发式。随机梯度噪声会被长记忆累积，需要不同分析。若停止测试只看 $f(x_k)-f(x_{k-1})$ ，振荡可能制造假停机；应结合梯度映射、预算和最佳已见函数值。

推论与应用

在 $L$ -光滑凸目标上，上述更新满足

f(x_k)-f(x^*)\le\frac{2L\|x_0-x^*\|^2}{(k+1)^2},

其证明与常数见Nesterov 加速率。这把达到函数值精度 $\varepsilon$ 所需的一阶查询从梯度下降的 $O(1/\varepsilon)$ 降到 $O(1/\sqrt\varepsilon)$ ，并在标准黑箱模型中达到最优阶。结论针对函数值，不自动说明主序列或外推序列的每个点都单调收敛。

复合目标把第一行替换成近端梯度步便得到 FISTA 型方法；强凸参数已知时可改用常动量获得 $O(\sqrt{L/\mu}\log(1/\varepsilon))$ 复杂度。两种变体的更新与证明常数不同，本页不把它们伪装成同一行参数开关。实现时最小可审计记录包括当前 $L$ 、回溯次数、 $t_k$ 、主/外推点函数值和停止原因。

参考资料

Yurii Nesterov, “A Method for Solving the Convex Programming Problem with Convergence Rate $O(1/k^2)$ ,” Soviet Mathematics Doklady 27, 1983, 372–376。
Yurii Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Kluwer, 2004，§2.2.2，optimal methods for smooth convex minimization。
Amir Beck and Marc Teboulle, “A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems,” SIAM Journal on Imaging Sciences 2(1), 2009, 183–202，§4，accelerated recurrence and rate。

形式陈述 ​

反向链接

形式陈述