第 16 课:Nesterov 加速梯度法——为什么 GD 的 O(1/k) 可以提升到 O(1/k²)?

2026 年 11 月 4 日|第 3 周·第 2 天|讲授约 18 分钟(自测另计)

上一课证明:对于存在最优点的凸、可微、(L)-Smooth 函数,步长 (1/L) 的普通 GD 满足 [ f(x_k)-f^\le \frac{L|x_0-x^|^2}{2k}. ] 今天研究一个更深的问题:不使用 Hessian,只保留每步一次梯度计算,能否把函数值误差改善为 (O(1/k^2))?

Nesterov 加速梯度法(AGD)可以做到,但不是“随便加一个 momentum”就必然加速。我们要给出一套参数明确、证明完整的三序列 AGD,而不是把经验性动量误写成理论保证。

一、问题、假设与加速目标

研究无约束问题: [ \min_{x\in\mathbb R^n}f(x),\qquad f^=\min f(x). ] 整个主定理要求:(1)(f) 凸且可微;(2)梯度 (L)-Lipschitz,(L>0);(3)存在全局最优解 (x^)。不要求强凸,也不要求 Hessian 存在。

(L)-Smooth 给出下降引理: [ f(v)\le f(u)+\langle\nabla f(u),v-u\rangle+\frac L2|v-u|^2. ] 取 (v=u-\nabla f(u)/L),得到 [ \boxed{f!\left(u-\frac1L\nabla f(u)\right)\le f(u)-\frac1{2L}|\nabla f(u)|^2.}\tag{1} ] 凸性给出另一个方向的不等式: [ \boxed{f(w)\ge f(u)+\langle\nabla f(u),w-u\rangle.}\tag{2} ]

AGD 的证明必须同时利用 (1) 的曲率上界与 (2) 的全局线性下界。只使用充分下降,通常得到的是 GD 的 (O(1/k)) 证明。

二、什么叫“加速”?先区分 GD、重球法与 AGD

普通 GD 每轮从当前点沿梯度移动: [ x_{k+1}=x_k-\eta\nabla f(x_k). ] 一种常见的重球动量(Heavy-ball)是 [ x_{k+1}=x_k-\eta\nabla f(x_k)+\beta(x_k-x_{k-1}). ] 这里的 (\beta) 表示利用上次位移,但是任意 (\eta,\beta) 没有通用加速保证。

Nesterov 方法则会在一个结合历史信息的外推点计算梯度,并严格规定外推系数。今天采用便于完整证明的三序列(linear-coupling 形式)Nesterov AGD:它与常见的双序列动量写法属于同一类加速一阶方法,但我们只证明下面明确写出的版本。

方法 典型迭代特点 在适当假设下的目标函数值保证
GD 从当前点做梯度步 凸 Smooth:(O(1/k))
Heavy-ball 梯度步 + 上一步位移 依赖额外参数与问题假设;不能仅凭动量断言 (O(1/k^2))
本课 AGD 外推点算梯度 + 辅助序列控制 凸 Smooth:最后一步 (O(1/k^2))
强凸专用加速方法 结合 (\mu,L) 调整参数 可得到相应加速几何收敛,但不是今天这一定理

三、三序列 AGD:算法每一步具体做什么?

初始化 [ \boxed{A_0=0,\quad y_0=z_0=x_0.} ] 第 (k+1) 步先选择唯一的正数 (a_{k+1}),满足 [ \boxed{La_{k+1}^2=A_k+a_{k+1}=:A_{k+1}.}\tag{3} ] 显式解为 [ a_{k+1}=\frac{1+\sqrt{1+4LA_k}}{2L}. ] 设 (\theta_{k+1}=a_{k+1}/A_{k+1}\in(0,1])。然后依次计算: [ \boxed{ \begin{aligned} u_{k+1}&=(1-\theta_{k+1})y_k+\theta_{k+1}z_k,
g_{k+1}&=\nabla f(u_{k+1}),
y_{k+1}&=u_{k+1}-\frac1L g_{k+1},
z_{k+1}&=z_k-a_{k+1}g_{k+1}. \end{aligned}}\tag{4} ] 第一个序列 (y) 是对外输出的实际迭代结果;(z) 是用来累计梯度信息的辅助点;(u) 是计算梯度的外推点。每轮只需要一次新梯度计算。

第一步:因为 (A_0=0),所以 (a_1=1/L)、(\theta_1=1)、(u_1=x_0),等价于普通 GD 的第一步;从后面的迭代开始,(z) 和 (y) 才逐渐分开,体现加速。

算法运行时不需要知道 (x^*)。最优点只在分析收敛界时使用。

四、关键创新:构造能下降的势函数

我们想证明的不是“每一步 (f(y_k)) 都下降”,而是某个包含函数值误差与辅助点距离的量下降。

定义 [ \boxed{ E_k=A_k[f(y_k)-f^]+\frac12|z_k-x^|^2. }\tag{5} ] 因为 (A_k\ge0) 且 (f(y_k)\ge f^*),有 (E_k\ge0)。我们将证明 [ \boxed{E_{k+1}\le E_k.}\tag{6} ]

4.1 将一步更新改写成短符号

为简洁起见,记 [ A=A_k,\quad a=a_{k+1},\quad A^+=A+a, \quad u=u_{k+1},\quad g=\nabla f(u). ] 由算法: [ A^+u=Ay_k+az_k,\qquad La^2=A^+.\tag{7} ]

4.2 用 Smooth 控制新的函数值

由式 (1): [ f(y_{k+1})\le f(u)-\frac1{2L}|g|^2. ] 因此 [ \begin{aligned} &A^+[f(y_{k+1})-f^]-A[f(y_k)-f^]
&\le A[f(u)-f(y_k)]+a[f(u)-f^*] -\frac{A^+}{2L}|g|^2. \end{aligned}\tag{8} ]

4.3 用凸性把函数值差转成梯度内积

由式 (2) 在 (y_k) 与 (x^) 处分别应用: [ f(u)-f(y_k)\le\langle g,u-y_k\rangle, \quad f(u)-f^\le\langle g,u-x^\rangle. ] 故式 (8) 右侧不超过 [ \left\langle g,A(u-y_k)+a(u-x^)\right\rangle -\frac{A^+}{2L}|g|^2.\tag{9} ]

4.4 再展开辅助点的距离平方

由 (z_{k+1}=z_k-ag): [ \begin{aligned} &\frac12|z_{k+1}-x^|^2-\frac12|z_k-x^|^2
&=-a\langle g,z_k-x^*\rangle+\frac{a^2}{2}|g|^2. \end{aligned}\tag{10} ]

将式 (9) 和式 (10) 相加,得到 [ \begin{aligned} E_{k+1}-E_k &\le \left\langle g,A(u-y_k)+a(u-z_k)\right\rangle
&\quad+\frac12\left(a^2-\frac{A^+}{L}\right)|g|^2. \end{aligned} ] 第一项因 (A^+u=Ay_k+az_k) 恰好为 0;第二项因 (La^2=A^+) 也恰好为 0,所以 [ \boxed{E_{k+1}-E_k\le0.}\tag{11} ]

这就是加速证明的核心机制:外推点的组合系数与权重 (A_k) 特别配合,使一阶项抵消;参数方程 (La^2=A^+) 使梯度平方项抵消。

参数不是随意挑选的。它们是为构造这种可递减的势函数而设计的。

五、严格推出最后一步 O(1/k²)

因为 (A_0=0)、(z_0=x_0),所以 [ E_0=\frac12|x_0-x^|^2. ] 再由 (E_k\le E_0): [ A_k[f(y_k)-f^]\le \frac12|x_0-x^*|^2.\tag{12} ] 现在只差证明 (A_k) 至少按 (k^2) 增长。

令 (t_k=\sqrt{LA_k})。由 (La_{k+1}^2=A_{k+1}),有 (La_{k+1}=t_{k+1})。于是 [ A_{k+1}=A_k+a_{k+1} \quad\Longrightarrow\quad t_{k+1}^2=t_k^2+t_{k+1}. ] 取正根: [ \boxed{ t_{k+1}=\frac{1+\sqrt{1+4t_k^2}}2. }\tag{13} ] 因为 (\sqrt{1+4t_k^2}\ge2t_k), [ t_{k+1}\ge t_k+\frac12. ] 从 (t_1=1) 出发,对 (k\ge1) 得 [ t_k\ge\frac{k+1}{2}, \qquad A_k=\frac{t_k^2}{L}\ge\frac{(k+1)^2}{4L}. ] 代入式 (12): [ \boxed{ f(y_k)-f^* \le\frac{2L|x_0-x^*|^2}{(k+1)^2}, \qquad k\ge1. }\tag{14} ] 这是一条最后一步函数值误差界,不是“历史最好迭代”的界。

对精度目标 (f(y_k)-f^\le\varepsilon),这给出迭代复杂度量级 [ k=O!\left(\sqrt{\frac{L|x_0-x^|^2}{\varepsilon}}\right). ] 对比上一课 GD 的 (O(1/\varepsilon)),理论上加速到 (O(1/\sqrt\varepsilon)),前提是两者使用各自定理要求的完整假设和参数。

特别注意: 此处 (O(1/k^2)) 衡量的是函数值误差;它不直接说 (|y_k-x^*|) 也是 (O(1/k^2)),也不意味着函数值每步单调下降。

六、具体迭代:相同二次函数下 GD 和 AGD

令 [ f(x_1,x_2)=\frac12(x_1^2+4x_2^2),\qquad \nabla f=(x_1,4x_2). ] Hessian 为 (\operatorname{diag}(1,4)),所以本例 (\mu=1,\ L=4),最优点 ((0,0))。尽管本例也强凸,我们今天仅使用一般凸 Smooth 的 AGD 参数。

初始化: [ y_0=z_0=(4,2),\quad A_0=0. ] 第一次: (a_1=1/4,\ u_1=(4,2)),(g_1=(4,8)),因此 [ y_1=(3,0),\quad z_1=(3,0),\quad f(y_1)=4.5. ] 第二次: (a_2=(1+\sqrt5)/8\approx0.4045085),(A_2\approx0.6545085),外推点 (u_2=(3,0)),所以 [ y_2=(2.25,0),\quad z_2\approx(1.786475,0),\quad f(y_2)=2.53125. ] 第三次: (a_3\approx0.548382),(\theta_3\approx0.455887), [ u_3\approx(2.038685,0),\quad y_3\approx(1.529014,0), ] 从而 (f(y_3)\approx1.168941)。

步数 (k) AGD 输出 (y_k) AGD 的 (f(y_k)) 同起点、步长 (1/4) 的 GD 函数值
0 ((4,2)) 16.000000 16.000000
1 ((3,0)) 4.500000 4.500000
2 ((2.25,0)) 2.531250 2.531250
3 ((1.529014,0)) 1.168941 1.423828

这一数值比较只是一个示例:不能从单个问题的第 3 步表现,推出 AGD 对所有函数在每一步都必定优于 GD。定理说的是跨整个函数类的最坏情况收敛上界。

七、失败反例与三个易错判断

7.1 错误参数的动量法可能发散

考虑最简单的强凸 Smooth 函数 [ f(x)=\frac12x^2,\qquad \mu=L=1. ] 使用重球法 [ x_{k+1}=x_k-\eta x_k+\beta(x_k-x_{k-1}). ] 取 (\eta=4,\ \beta=0.9,\ x_{-1}=x_0=1),则 [ x_1=1-4=-3, ] [ x_2=-3-4(-3)+0.9(-3-1)=5.4. ] 它的迭代矩阵存在模大于 1 的特征值,后续出现发散模态。因此即使目标强凸,随意添加 momentum 也不能获得稳定性与加速保证。

7.2 非凸函数不能照搬本课势函数证明

上面的证明在式 (9) 关键使用了 [ f(u)-f(x^)\le \langle\nabla f(u),u-x^\rangle, ] 这是凸函数一阶下界的推论。对于一般非凸函数它可能失败,所以不能仅因为函数 (L)-Smooth 就声称最后一步全局误差 (O(1/k^2))。

7.3 AGD 函数值未必每步单调

我们证明的是 (E_k) 下降,而不是 (f(y_k)) 下降。势函数中还有距离项,可能在不同迭代之间交换。因此不应把“势函数递减”等同于“原始目标函数值每一步都严格下降”;若需要单调性,应采用另有证明的相应变体。

八、把 AGD 与 KKT / 约束问题联系起来

前两周一直强调:对于约束问题,最优点不一定满足 (\nabla f(x^*)=0)。

例如 (\min_{x\le1}\frac12(x-2)^2),最优点 (x^=1) 满足 (f’(1)=-1\neq0),但 KKT 的活跃约束乘子是 (\lambda^=1)。本课的 AGD 是无约束算法;直接用式 (4) 更新可能走出可行域,不能原封不动声称它能解决任意约束问题。下周学习投影与 Prox 时,我们将讨论如何把可行性条件引入更新,并需要重新建立收敛证明。

九、逻辑关系图

flowchart TD
    A["凸 + L-Smooth + 最优解存在"] --> B["下降引理与凸一阶下界"]
    B --> C["三序列:外推点 u / 输出 y / 辅助点 z"]
    C --> D["设计 La² = A+"]
    D --> E["势函数 E = A·函数值误差 + 距离平方/2"]
    E --> F["证明 E 后一步 ≤ E 前一步"]
    F --> G["证明 A_k ≥ (k+1)²/(4L)"]
    G --> H["最后一步函数值误差 O(1/k²)"]
    I["仅 Smooth,非凸"] -. "缺少凸性关键不等式" .-> B
    J["任意 momentum 参数"] -. "不自动有定理" .-> C

核心公式复盘: [ \boxed{La_{k+1}^2=A_{k+1}=A_k+a_{k+1}},\qquad \boxed{E_{k+1}\le E_k},\qquad \boxed{f(y_k)-f^\le\frac{2L|x_0-x^|^2}{(k+1)^2}}. ]

下一讲(2026-11-05,第 17 课):加速为什么可能振荡?重启策略、强凸加速与条件数。 将比较 GD 的 (1-\mu/L) 与强凸专用 Nesterov 方法的典型加速率,讨论动量重启何时有理论保证、何时只是启发式。


十、今日四级自测(100 分)

首次发送不提供答案、不透露选项正确性及开放题评分细则;独立答案只保存在测验 JSON 中,请作答前不要查看,避免泄题。

Lv1|AGD 定理的假设与充分结论|15 分|预计 2 分钟|单选

对一个存在全局最优点的凸、可微且 (L)-Smooth 函数,使用本课给定参数的 Nesterov 三序列加速梯度法。下面哪项有严格的通用保证?

A. 不需要凸性,也能保证最后一步全局函数值误差为 (O(1/k^2))。

B. 只要函数值下降一次,以后每一步都必须继续下降。

C. 可以证明最后一步函数值误差为 (O(1/k^2)),但该界本身不要求每步函数值单调下降。

D. 只要有 (L)-Smooth,就自动得到乘子唯一以及 KKT 充分性。

提示:区分凸性用于加速证明的作用、最后一步误差界,以及单步函数值单调性。

Lv2|一次三序列 AGD 的数值更新|20 分|预计 3 分钟|数值

设 (f(u,v)=\tfrac12(u^2+4v^2)),(L=4),三序列 AGD 初始化 (A_0=0)、(y_0=z_0=(2,1))。按本课公式做第一次迭代((a_1=1/L)、(x_1=z_0)、(y_1=x_1-\nabla f(x_1)/L)),计算 (f(y_1))。仅填写一个数,保留三位小数。

作答格式: 一个数字,允许绝对误差 0.001。

提示:第一次迭代没有外推;先得到 y1 的两个坐标。

Lv3|不当动量参数的两步反例|25 分|预计 5 分钟|单选

考虑带动量的重球迭代 (x_{k+1}=x_k-\eta f’(x_k)+\beta(x_k-x_{k-1}))。令 (f(x)=x^2/2),(x_{-1}=x_0=1),(\eta=4),(\beta=0.9)。关于前两次迭代和收敛保证,哪项正确?

A. (x_1=-3,\ x_2=5.4);该例表明随意选用动量和步长,即使目标强凸且 Smooth,也可能发散。

B. (x_1=-3,\ x_2=0);因此第二步必到最优点。

C. (x_1=1,\ x_2=1);因为初始动量项为零,所以之后永远不移动。

D. 重球法和本课证明过的 Nesterov 三序列法完全相同,因此不论参数取何值都具有 (O(1/k^2)) 保证。

提示:把数值代入两步递推,注意第二步动量项来自 x1−x0。

Lv4|势函数收缩证明、复杂度与反例|40 分|预计 12 分钟|开放证明

对凸、可微且 (L)-Smooth 的 (f:\mathbb R^n\to\mathbb R),假设存在最优点 (x^*)。考虑本课三序列加速梯度法,初始化 (A_0=0,\ y_0=z_0=x_0),令每步 (a=a_{k+1}>0) 满足 (La^2=A_k+a=:A_{k+1}),并设置 (u=(A_ky_k+az_k)/A_{k+1})、(g=\nabla f(u))、(y_{k+1}=u-g/L)、(z_{k+1}=z_k-ag)。

A(16 分):定义势函数 (E_k=A_k[f(y_k)-f^]+\tfrac12|z_k-x^|^2)。逐行利用 Smooth 上界、凸函数一阶下界与平方距离展开,证明 (E_{k+1}\le E_k),并指出哪个等式使梯度平方项恰好抵消。

B(10 分):令 (t_k=\sqrt{LA_k}),推导 (t_{k+1}=(1+\sqrt{1+4t_k^2})/2) 并证明 (t_k\ge(k+1)/2)((k\ge1));由此得到明确的最后一步 (O(1/k^2)) 函数值界。

C(8 分):对 (f(u,v)=\tfrac12(u^2+4v^2))、(L=4),取 (y_0=z_0=(4,2)),计算第二次迭代后的 (y_2) 与 (f(y_2)),给出 (a_2) 的准确表达式或四位小数。

D(6 分):说明为什么本证明不能在不修改假设时直接推广到一般非凸函数;再举出一组重球法动量和步长不当的数值反例(可使用本课反例),解释失败的原因。

*提示:A 中先用 f(y+)≤f(u)−   g   ²/(2L),再用 f(u)−f(yk)≤⟨g,u−yk⟩、f(u)−f≤⟨g,u−x⟩;与 z 更新的距离差合并。B 利用 La²=A+ 并归纳。*

十一、下一讲与评分

第 17 课|2026-11-05:加速与振荡:强凸加速、重启及条件数。

本课四题总分 (15+20+25+40=100)。你作答后会逐题评分与反馈:80 分及以上继续;60–79 分补充针对性例子;低于 60 分优先复习 Smooth、凸性与势函数证明。自测不会改变按日期计算的课号。