Nesterov 加速率

梯度下降的证明只积累“已经减少的函数值”，总预算来自初始距离，因此得到一次反比。加速势函数给第 $k$ 轮函数值误差乘上不断增长的权重 $t_k^2\asymp k^2$，同时用辅助向量的平方范数吸收外推产生的交叉项。只要总势能不增，函数值误差就必须以 $1/t_k^2$ 缩小。

动量序列本身可以越过极小点，$f(x_{k+1})$ 也可能大于 $f(x_k)$；势函数中未展示的距离项会为这次上升付款。因此用“每步都更低”解释加速率是错误的。最优性是关于仅访问一阶 oracle 的最坏问题族：在 $L$-光滑凸类上，任何方法一般都需要 $\mathrm{\Omega }(\sqrt{L{R}^2/\epsilon })$ 次查询，本定理在常数外匹配该阶。

对 $f(x)=x^2/2$，以安全但不紧的 $L=4$ 和 $x_0=1$ 执行标准递推，可复算

故 $f(x_3)\approx 0.0731$。定理在 $k=3$ 给

实际值远小于上界并不奇怪：一维二次函数不是构造一阶下界所需的最坏高维目标，而且使用的是松 $L$。这个例子能核对更新和上界，却不能用来“实证”最坏阶；同理，有限轮实验比梯度下降快也不是定理证明。

若 $L$ 被低估，二次上模型不成立，势函数的一步不等式从根部断裂。若梯度带系统误差，误差项会按增长权重累积，不能保留无噪声的无限精度率。即使函数值按 $1/k^2$ 收敛，普通凸性允许多个解，点序列不必收敛到指定 $x^{\ast }$。加速还可能产生明显振荡；单调 FISTA、阻尼或自适应重启能改善轨迹，但各自需要新的不变量，不能无条件继承这里的常数。

要使函数值误差不超过 $\epsilon$，只需

即 $O(\sqrt{L{R}^2/\epsilon })$ 次梯度查询。若目标还有$\mu$-强凸性公理库强凸性Strong convexity · Strongly convex function函数在一阶凸下界之外还保留统一二次增长量的曲率性质。，使用已知参数的常动量或周期重启，可把复杂度加强为

这里的平方根条件数优于普通梯度下降的 $O((L/\mu )\log \left(1/\epsilon \right))$；强凸结果是额外结构下的推论，不是一般凸定理偷偷假设唯一解。

势函数方法也迁移到近端加速、线性耦合和估计序列分析。迁移时真正要保留的是“一步模型不等式、权重递推、非负距离项”三件事，而不是照抄动量系数。报告算法性能应分别给函数值、梯度映射和点误差；本定理只直接控制第一项。