优化理论（二）：光滑性、强凸性与 Nesterov 加速

大量关于优化器的“民间智慧”其实可以归结为三个核心概念：

• 梯度有多陡？ Lipschitz 光滑性（$L$ -smoothness）限制了步长上限。
• 底部有多尖锐？ $\mu$ -强凸性决定了收敛速率，并保证最小值点唯一。
• 能否在不牺牲稳定性的情况下更快到达？ Nesterov 加速和自适应重启将每条件数的代价从 $\kappa$ 降至 $\sqrt{\kappa}$ 。

本文将这三个概念串成一条主线：用最少的不等式建立几何直觉，证明关键定理，最后通过一个最小二乘实验，让 GD、Heavy Ball 和 Nesterov 正面交锋。目标不是堆砌公式——而是让你面对新问题时，能立刻回答：“该用多大步长？收敛速率是多少？加速是否值得？”

调过深度学习超参的人多半都体会过这种循环：把学习率调大一点，loss 上天；调小一点，又慢得让人想砸键盘。这背后其实只有三个量在说话：

• 梯度有多陡？——这就是 Lipschitz 光滑性 $L$ ，它告诉你步长最多能开多大。
• 底部有多尖？——这就是强凸常数 $\mu$ ，它决定收敛是“线性下降”还是“慢慢爬”。
• 能不能不牺牲稳定性还跑得更快？——Nesterov 加速给的答案，把每个条件数 $\kappa$ 的代价从 $\kappa$ 压到 $\sqrt{\kappa}$ 。

这篇文章我想做的事情很具体：先帮你建立 $L$ 和 $\mu$ 的几何感觉，再把 Nesterov 那个看着像魔法的 $\beta_t = (t-1)/(t+2)$ 拆开来看，让你知道它为什么不是凭空冒出来的。看完之后，下次面对一个新的优化问题，你应该能先估一下 $L$ 和 $\mu$ ，再决定要不要请加速出场。

你将学到什么#

• Lipschitz 连续性的几何意义：每个点都位于一个包含函数图像的斜率锥内。
• $L$ -光滑性的等价刻画：函数被一族二次函数从上方夹住（下降引理）。
• 强凸性作为二次 下界，并自然导出最小值点的存在性与唯一性。
• 为何条件数 $\kappa = L/\mu$ 控制 GD 的迭代复杂度，以及 Nesterov 如何将其替换为 $\sqrt{\kappa}$ 。
• 为何即使在强凸情形下仍需自适应重启，并通过最小二乘实验加以验证。

前置知识#

• 多元微积分（梯度、Hessian、泰勒展开）。
• 基础凸分析（凸集、一阶条件）。

Lipschitz 连续性与梯度光滑性#

Lipschitz 连续性的几何图像#

从几何上看，这是一个 双侧锥约束：在任意锚点 $(x_0, f(x_0))$ 处，斜率为 $\pm L$ 的双锥必须完全包含整个函数图像。一旦函数出现近似垂直的切线（例如 $\sqrt{|x|}$ 在原点附近），就不存在有限的 $L$ 能将其包含，此时 $f$ 不再是 Lipschitz 的。

左图：$\sin x$ 是 1-Lipschitz；三个采样锚点处的橙色锥体完全包含图像。右图：$\mathrm{sign}(x)\sqrt{|x|}$ 在原点处斜率发散；红色区域表示候选 $L=2$ 的锥体被穿透的位置。

两个会反复出现的推论：

1. 一致连续性：取 $\delta = \varepsilon / L$ 。
2. 封闭性：Lipschitz 函数在加法、标量乘法和复合下封闭（常数相乘）。这使我们能将复杂模型分解为具有已知常数的 Lipschitz 构件。

梯度-Lipschitz = $L$ -光滑性#

也就是说：$f$ 被一族曲率为 $L$ 的向上抛物线从上方夹住。切线是最坏情况下的下包络；抛物线则是实际的上包络。

蓝色曲线为 $f(x) = \tfrac{1}{2}\sin(2x) + \tfrac{1}{2}x^2$ 。在三个锚点处，虚线二次函数 $f(x_0) + f'(x_0)(x-x_0) + \tfrac{L}{2}(x-x_0)^2$ 全局位于 $f$ 上方，而点线切线仅在 $f$ 局部凸的区域下方。

只要 $\eta \le 1/L$ ，括号内 $\ge 1/2$ ，因此 每一步都严格减小 $f$ ，且减小量至少为常数乘以 $\|\nabla f\|^2$ 。这才是“步长至多为 $1/L$ ”的真正来源——并非传言，而是下降引理的直接推论。

同一二次函数 $f(x) = \tfrac{L}{2}x^2$ （此处 $L = 4$ ）上的三种情形。左：小步长（$\eta = 0.8/L$ ）单调缓慢下降。中：标准步长 $\eta = 1/L$ 从 $x_0 = 1$ 一步直达最优解——无超调下的最快方式。右：超过 $2/L$ 上限后，迭代发散，下降引理失效。区间 $[1/L,\, 2/L]$ 正是收敛最快 且 安全的紧致带；低于此则浪费迭代，高于此则发散。

三个实例详解#

第三行给出了逻辑回归的标准 $L = \tfrac{1}{4n}\sum_i\|x_i\|^2$ —— 关键在于 $\sigma(\cdot)\sigma(-\cdot)\le 1/4$ 。

Hessian 谱范数蕴含梯度 Lipschitz#

定理 1（Hessian 谱范数 $\Rightarrow$ Lipschitz 梯度）。若 $f$ 二阶可微且 $\sup_x \|\nabla^2 f(x)\|_2 \le L$ ，则 $\nabla f$ 是 $L$ -Lipschitz 的。

对于二次函数 $f(x) = \tfrac{1}{2}x^\top H x$ ，这恰好给出 $L = \lambda_{\max}(H)$ —— 与下降引理使用的 $L$ 相同，因此步长规则 $\eta \le 1/\lambda_{\max}(H)$ 是紧致的。

强凸性：存在性、唯一性与二次增长#

三种等价定义#

它有三种等价形式，各自适用于不同场景：

1. 二次下界（上述不等式）：$f$ 位于一族曲率为 $\mu$ 的向上抛物线上方。
2. $f - \tfrac{\mu}{2}\|x\|^2$ 是凸的：减去“$\mu$ -曲率质量”后剩下凸函数。
3. 二阶条件（若 $f$ 是 $C^2$ ）：$\nabla^2 f(x) \succeq \mu I$ 。

左：一个强凸函数及其三个二次下界模型（每个锚点一个）。右：$f(x) = 0.05\,x^4$ 是凸的但 非强凸 —— 在原点过于平坦，无法容纳任何 $\mu>0$ 的抛物线下界。这正是此类目标无法获得线性收敛的原因。

存在性与唯一性#

定理 2（存在性）。若 $f$ 下半连续，且某个次水平集 $\{x : f(x)\le\alpha\}$ 非空且有界，则 $f$ 在该集合上取得最小值。

这只是 Weierstrass 定理：闭且有界 = 紧致，下半连续函数在紧致集上取得下确界。

定理 3（强凸性蕴含唯一性）。$\mathbb{R}^n$ 上的 $\mu$ -强凸函数（$\mu > 0$ ）至多有一个全局最小值点。

但 $f(y^\star) = f(x^\star)$ ，故 $\|y^\star - x^\star\| = 0$ 。$\blacksquare$

即 代价至少以二次速率远离最小值点增长。这是所有后续收敛证明中将“小函数值”转化为“小到最优点距离”的关键杠杆。

$L$ -光滑与 $\mu$ -强凸结合：条件数#

称为 条件数，它控制后续所有收敛速率。大的 $\kappa$ 意味着函数“又长又窄”——最陡方向濒临不稳定，而最平缓方向几乎不提供信号。这正是优化困难的结构性根源。

加速梯度下降：从 $\kappa$ 到 $\sqrt{\kappa}$ #

普通 GD 的两个上界#

达到误差 $\varepsilon$ 需要 $t = \mathcal O(\kappa\log(1/\varepsilon))$ 。条件数线性进入：在 $\kappa = 10^4$ 的最小二乘问题中，精度每提高 10 倍，大约额外需要 $2\times 10^4$ 次迭代。

Nesterov：前瞻将 $\kappa$ 替换为 $\sqrt{\kappa}$ #

直觉：先用动量外推预测落点，再用该点梯度校正。这点预见性足以在所有 $L$ -光滑凸函数上保持加速。

可得 $f(x_t) - f^\star \le \big(1 - \sqrt{1/\kappa}\big)^t (f(x_0) - f^\star)$ ，故 $t = \mathcal O(\sqrt{\kappa}\log(1/\varepsilon))$ 。

左：在 $\kappa = 30$ 的旋转二次函数上运行 80 次迭代。GD（蓝色，$\eta = 1.9/L$ 以放大效果）在陡峭方向超调，在狭窄山谷中来回振荡，沿平坦轴净进展缓慢。Nesterov（紫色，$\eta = 1/L$ ）沿山谷积累动量，几乎不激发陡峭模式。右：到 $x^\star$ 距离的对数尺度图 —— 斜率差异正是定理 5 和 7 所预测的 $\kappa$ 与 $\sqrt{\kappa}$ 速率差距的几何体现。

左（$\kappa=100$ ）：对数坐标下三种算法均线性下降，但 Nesterov（紫色）和 Heavy Ball（橙色）斜率比 GD（蓝色）更陡 —— 这正是 $\sqrt{\kappa}$ 与 $\kappa$ 差距的可视化。虚线为理论包络；与实证轨迹吻合。右：聚焦前 80 次迭代，Nesterov 非单调 —— 在下包络内振荡。这是加速的代价。

自适应重启修复加速的副作用#

加速的缺点是 非单调性 —— 函数值周期性上升。这在两种情况下尤为痛苦：

• $\mu$ 未知：定理 7 需要 $\sqrt{1/\kappa}$ 作为动量；估计错误会破坏速率。
• 局部强凸：$f$ 全局仅凸但在 $x^\star$ 附近强凸；使用凸速率的 Nesterov 表现不佳。

自适应重启（O’Donoghue & Candès, 2015）：每当 梯度方向反转（$\langle\nabla f(y_t), x_{t+1}-x_t\rangle > 0$ ）或 函数值上升 时，重置动量并将迭代计数器归零 $t \leftarrow 1$ 。

定理 8（重启 Nesterov 在未知 $\mu$ 下仍达最优速率）。对 $\mu$ -强凸 + $L$ -光滑函数 $f$ ，重启 Nesterov 仍实现 $\mathcal O(\sqrt{\kappa}\log(1/\varepsilon))$ 次迭代，无需知道 $\mu$ 。

证明概要：两次重启之间运行凸速率 Nesterov，间隙以 $\mathcal O(1/k^2)$ 下降。结合二次增长推论，可得“每次重启至少将间隙减半”。几何减半 $\log(1/\varepsilon)$ 次即可达到 $\varepsilon$ 。每段长度约 $\sim \sqrt{\kappa}$ ，故总迭代次数为 $\sim \sqrt{\kappa}\log(1/\varepsilon)$ 。

$\kappa$ 实际影响有多大#

左（双对数坐标）：在合成最小二乘问题上，达到 $10^{-6}$ 相对间隙所需的迭代次数，GD 严格随 $\kappa$ 增长，Nesterov 则随 $\sqrt{\kappa}$ 增长。右：加速比 $T_{\text{GD}}/T_{\text{AGD}}$ 几乎精确跟踪 $\sqrt{\kappa}$ 。当 $\kappa = 10^4$ 时加速比约 100 倍；$\kappa = 100$ 时约 10 倍。条件越差，加速收益越大。

决策表#

最小二乘实验#

问题与精确常数#

关键提醒。条件数是 $A$ 条件数的 平方。因此一个看似正常的 $A$ （$\kappa(A) = 100$ ）会变成最小二乘中的困难实例（$\kappa = 10^4$ ）—— 对正规方程梯度而言尤其如此。

实现#

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

import numpy as np

def gd(A, b, n_iter, eta=None):
    """Gradient descent with step 1/L."""
    L = np.linalg.eigvalsh(A.T @ A).max()
    eta = eta or 1.0 / L
    x = np.zeros(A.shape[1])
    hist = []
    for _ in range(n_iter):
        g = A.T @ (A @ x - b)
        hist.append(np.linalg.norm(g))
        x -= eta * g
    return x, hist

def nesterov_strongconvex(A, b, n_iter):
    """Nesterov AGD using known mu, L (constant-momentum form)."""
    eigs = np.linalg.eigvalsh(A.T @ A)
    L, mu = eigs.max(), max(eigs.min(), 1e-12)
    eta = 1.0 / L
    sk = np.sqrt(mu / L)
    beta = (1 - sk) / (1 + sk)
    x_prev = x = np.zeros(A.shape[1])
    hist = []
    for _ in range(n_iter):
        y = x + beta * (x - x_prev)
        g = A.T @ (A @ y - b)
        hist.append(np.linalg.norm(A.T @ (A @ x - b)))
        x_prev, x = x, y - eta * g
    return x, hist

def nesterov_restart(A, b, n_iter):
    """Adaptive-restart Nesterov: reset momentum on function-value uptick."""
    L = np.linalg.eigvalsh(A.T @ A).max()
    eta = 1.0 / L
    x_prev = x = np.zeros(A.shape[1])
    t = 1
    f_prev = 0.5 * np.linalg.norm(A @ x - b) ** 2
    hist = []
    for _ in range(n_iter):
        beta = (t - 1) / (t + 2)
        y = x + beta * (x - x_prev)
        g = A.T @ (A @ y - b)
        x_new = y - eta * g
        f_new = 0.5 * np.linalg.norm(A @ x_new - b) ** 2
        if f_new > f_prev:               # restart trigger
            t = 1
            x_new = x - eta * (A.T @ (A @ x - b))
            f_new = 0.5 * np.linalg.norm(A @ x_new - b) ** 2
        else:
            t += 1
        hist.append(np.linalg.norm(A.T @ (A @ x_new - b)))
        x_prev, x, f_prev = x, x_new, f_new
    return x, hist

观察结果#

在合成实例上（$m = 200, n = 100$ ，$\kappa(A) \approx 100$ ，故 $\kappa(A^\top A) \approx 10^4$ ）：

• GD：需约 $4\times 10^4$ 次迭代达到 $10^{-6}$ 相对梯度范数；平滑但缓慢。
• Nesterov（恒定动量）：约 400 次迭代；轨迹如图 4（右）所示在谷底振荡。
• 重启 Nesterov：约 500 次迭代且几乎完全单调 —— 三者中最稳健。

实证加速比与图 5 的 $\sqrt{\kappa}$ 预测一致（$10^4 \to 100\times$ ）。

总结与后续方向#

速查表#

面对新问题的三个反射#

当一个新目标函数摆在面前时，走以下循环：

1. 有多陡？ 估计 $L$ （最大特征值或回溯线搜索）。它立即给出步长上限。
2. 底部有多尖锐？ 估计 $\mu$ （最小特征值或 PL 常数）。它告诉你是否可能线性收敛。
3. 加速是否值得？ 看 $\kappa = L/\mu$ 。$\kappa < 50$ ：GD 足够。$\kappa \in [50, 10^4]$ ：切换到 Nesterov。 $\kappa > 10^4$ ：考虑预条件或二阶方法。

故事的延续#

• 非凸 + PL 条件。放弃强凸性；若 $\tfrac{1}{2}\|\nabla f\|^2 \ge \mu(f - f^\star)$ 成立，GD 仍线性收敛。这是“为何过参数化深度网络能线性训练”的理论种子（Karimi et al., 2016）。
• 含噪声的加速。原始 Nesterov 对随机梯度不鲁棒。SAG / SVRG / Katyusha 通过方差缩减将强凸随机速率拉回 $\sqrt{\kappa}$ 区间。
• 二阶加速。Sophia 和 Shampoo 通过（块）对角 Hessian 预条件，有效重写条件数 —— 这是 2024 年大规模预训练的活跃前沿。

参考文献#

1. Nesterov, Y. (1983). A method of solving a convex programming problem with convergence rate $\mathcal O(1/k^2)$ . Soviet Mathematics Doklady, 27(2), 372–376.
2. Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
3. Bubeck, S. (2015). Convex Optimization: Algorithms and Complexity. Foundations and Trends in Machine Learning, 8(3-4), 231–357.
4. O’Donoghue, B., & Candès, E. (2015). Adaptive restart for accelerated gradient schemes. Foundations of Computational Mathematics, 15(3), 715–732.
5. Karimi, H., Nutini, J., & Schmidt, M. (2016). Linear convergence of gradient and proximal-gradient methods under the Polyak-Łojasiewicz condition. ECML-PKDD.

下一步#

把这一章的工具内化之后，下一篇会继续往前推：本章给你的几个新概念会变成下一章证明的“顺手抄起就用”的工具。如果遇到术语觉得卡住，回到本文 H2 标题对应的小节再读一遍——这些概念后面会反复出现，第一遍不必全懂，第二三遍自然会熟。

如果你想立刻动手验一下今天学到的东西，最划算的练习是：找一个你熟悉的优化问题，把本文的关键不等式（凸性、$L$ -光滑、强凸、对偶界）逐一在它身上验一遍——很快你就会发现哪些假设是真的成立，哪些只是“纸面上成立”。这种习惯比多读两篇 paper 更有用。