Nesterov 加速率

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

动量序列本身可以越过极小点，$f(x_{k+1})$ 也可能大于 $f(x_k)$；势函数中未展示的距离项会为这次上升付款。因此用“每步都更低”解释加速率是错误的。这里所用的最优性比较是标准的一阶线性张成模型：每次查询点位于初值与此前梯度张成的仿射空间中，初值到某个最优点的距离至多为 $R$。当维数可随查询次数增长时，光滑凸最坏问题族需要 $\mathrm{\Omega }(\sqrt{L{R}^2/\epsilon })$ 次查询，本算法在常数外匹配该阶；Bubeck 的 Theorem 3.14 明确要求查询次数 $t\le (n-1)/2$。这个下界不能原样解释为固定低维问题、任意附加 oracle 或每个单独函数的困难度。

对 $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函数在一阶凸下界之外还保留统一二次增长量的曲率性质。，已知 $0<\mu \le L$ 时可以周期重启。强凸二次增长给 $\Vert x-x^{\ast }{\Vert }^2\le 2(f(x)-f^{\ast })/\mu$，所以每隔 $m$ 步重新初始化动量，只要 $m+1\ge \sqrt{8L/\mu }$，一块后的函数值误差至多是块初误差的一半。令 ${\mathrm{\Delta }}_0=f(x_0)-f^{\ast }>\epsilon >0$，总查询复杂度因而为

这里的平方根条件数优于普通梯度下降的 $O((L/\mu )\log \left({\mathrm{\Delta }}_0/\epsilon \right))$；初始误差已达标时直接结束。强凸结果是额外结构下的推论，不是一般凸定理偷偷假设唯一解。

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