第三章：梯度下降与线搜索

3.1.1 迭代算法的一般步骤#

任何迭代优化算法都遵循相同的框架：

1. 输入：初始点 $x^0$，停机精度 $\varepsilon$，迭代计数 $k = 0$
2. 判断停机：若停机准则满足（如 $\|\nabla f(x^k)\| < \varepsilon$），输出 $x^k$ 并停止
3. 确定下降方向：在 $x^k$ 处找一个下降方向 $d_k$
4. 确定步长：选取步长 $\alpha_k > 0$，使得 $f(x^k + \alpha_k d_k) < f(x^k)$（通过线搜索）
5. 更新：$x^{k+1} = x^k + \alpha_k d_k$，$k \leftarrow k + 1$，返回第 2 步

其中下降方向有严格的定义：$d$ 是 $f$ 在 $x$ 处的下降方向，若存在 $\bar{t} > 0$，使得对所有 $t \in (0, \bar{t})$，$f(x + td) < f(x)$。对可微函数，$d$ 是下降方向的充分条件为 $\nabla f(x)^\top d < 0$，即 $d$ 与梯度的夹角大于 $90°$。这个条件的几何含义是：$d$ 在负梯度方向上有正的投影分量，沿 $d$ 移动足够小的步长后函数值必然下降。

不同算法的区别在于第 3、4 步的具体策略：梯度下降取 $d_k = -\nabla f(x^k)$（最简单的选择），共轭梯度法取 $d_k$ 为负梯度的共轭修正方向，牛顿法取 $d_k = -[\nabla^2 f(x^k)]^{-1}\nabla f(x^k)$（利用二阶信息）。本章聚焦于梯度下降。

3.1.2 $L$-光滑性：Lipschitz 连续梯度#

在分析梯度下降的收敛性之前，需要对目标函数的”弯曲程度”做出量化约束。这由 $L$-光滑性给出，它是本章乃至全书最频繁使用的正则性条件。

定义（$L$-光滑性）. 设可微函数 $f: \mathbb{R}^n \to \mathbb{R}$，若存在常数 $L > 0$，使得对任意 $x, y \in \mathbb{R}^n$，

则称 $f$ 的梯度是 Lipschitz 连续的（Lipschitz 常数为 $L$），也称 $f$ 是 $L$-光滑的。

$L$-光滑性对函数施加了一个全局约束：梯度的变化速率不超过 $L$。常数 $L$ 衡量的是梯度变化的剧烈程度——$L$ 越大，梯度在相邻两点之间的差异越大，函数的”弯曲”就越厉害。对于二次函数 $f(x) = \frac{1}{2}x^\top A x$，$L$ 恰好等于 $A$ 的最大特征值 $\lambda_{\max}(A)$，这直接反映了函数沿曲率最大方向的弯曲程度。

$L$-光滑性有三个重要的等价刻画（当 $f$ 额外为凸时）：

(1) 梯度 Lipschitz 连续（常数 $L$）；

(2) 函数 $g(x) = \frac{L}{2}x^\top x - f(x)$ 是凸函数——这等价于 $f(x)$ 的增长不超过二次函数 $\frac{L}{2}\|x\|^2$；

(3) 梯度算子是余强制（cocoercive）的：对任意 $x, y$，

这三个等价条件将在 3.5.1 节中正式陈述并用于证明。此处先给出直觉：条件 (2) 说 $L$-光滑性本质上是一个”函数弯曲程度的上界”——函数被 $\frac{L}{2}\|x\|^2$ 这个二次函数”压住”，不能弯曲得太厉害。条件 (3) 比梯度的单调性更强：不仅梯度差与自变量差的内积非负，还被梯度差的范数平方所下界。

$L$ 对算法设计的直接影响在于：$L$ 越大，函数越”难以预测”——一阶泰勒近似的有效范围越小，梯度下降每一步能安全走的距离就越短，步长上界越小。后面的分析将精确给出步长必须满足 $\alpha_k < 2/L$，最优步长为 $1/L$。

$L$-光滑性的一个直接推论是二次上界：对任意 $x, y$，

这正是下降引理的内容（3.3 节将给出完整证明）。二次上界进一步蕴含了梯度范数对函数值差的控制：若 $f$ 存在全局极小点 $x^*$，在上式中对 $y$ 取下确界，取 $y = x - \frac{1}{L}\nabla f(x)$ 时右端达到最小，得到

即 $f(x) - f(x^*) \geq \frac{1}{2L}\|\nabla f(x)\|^2$。这个不等式在收敛性分析中反复出现：它将梯度范数（算法可计算的量）与函数值差（我们关心的量）联系起来。

3.1.3 梯度下降算法#

在一般框架中取 $d_k = -\nabla f(x^k)$（负梯度方向）时，迭代格式变为梯度下降算法（Gradient Descent）：

负梯度方向是局部下降最快的方向，这一点可由一阶泰勒展开看出：在 $\|d\| = 1$ 的约束下，$f(x + \epsilon d) \approx f(x) + \epsilon \nabla f(x)^\top d$ 的下降量 $-\nabla f(x)^\top d$ 在 $d = -\nabla f(x)/\|\nabla f(x)\|$ 时取最大值。

梯度下降的核心任务是分析该算法在不同函数类上的收敛性与收敛速度，而这需要对步长 $\alpha_k$ 的选取策略做出恰当的规定。

步长 $\alpha_k$ 的选取是梯度下降中最微妙的问题。一个极端是取固定步长 $\alpha_k = 1/L$，优点是不需要额外计算，但要求事先知道 $L$ 的值。另一个极端是精确线搜索，每步都求解一维优化问题来获取最优步长，代价高但步长最优。实际中最常用的折中方案是非精确线搜索（如回退法配合 Armijo 准则），不需要知道 $L$，每步只需几次函数求值。

3.2.1 精确线搜索与最速下降法#

最理想的做法是求解一维优化问题：

这称为精确线搜索。当下降方向取 $d_k = -\nabla f(x^k)$ 时，精确线搜索配合负梯度方向构成最速下降法（Steepest Descent）。

最速下降法有一个有趣的性质：相邻两步的下降方向互相垂直。证明如下：对 $\phi(\alpha) = f(x^k + \alpha d_k)$ 求导并令其为零，由精确线搜索的最优性条件得

即 $\nabla f(x^{k+1})^\top \nabla f(x^k) = 0$，故 $d_{k+1} \perp d_k$。

这一正交性导致了锯齿现象：迭代轨迹呈锯齿形，初期远离最优点时下降很快，接近最优点后锯齿越来越密集、步长越来越小，收敛变慢。

以二次函数 $f(x, y) = x^2 + 10y^2$ 为例，最速下降法的迭代轨迹会在椭圆等高线之间来回折返。等高线越扁（条件数越大），锯齿越密集，收敛越慢。

对于正定二次函数 $f(x) = \frac{1}{2}x^\top A x - b^\top x$，可以精确推导最速下降法的收敛率。梯度为 $\nabla f(x) = Ax - b$，精确线搜索的步长通过 $\frac{d}{d\alpha}f(x^k - \alpha \nabla f(x^k)) = 0$ 求得：

记误差向量 $e^k = x^k - x^*$，则 $\nabla f(x^k) = Ae^k$，迭代格式变为 $e^{k+1} = (I - \alpha_k A)e^k$。在 $A$-范数 $\|x\|_A = \sqrt{x^\top Ax}$ 下，

将 $e^k$ 展开到 $A$ 的特征基 $\{v_i\}$ 下，$e^k = \sum_i c_i v_i$，代入 $\alpha_k$ 的表达式并化简，可以证明

其中 $\lambda_1, \lambda_n$ 分别是 $A$ 的最大、最小特征值。最后一个等号成立的原因是：对固定的 $\alpha$，$(1 - \alpha\lambda)^2$ 在 $\lambda = \lambda_n$ 和 $\lambda = \lambda_1$ 处取极值，选取使二者绝对值相等的 $\alpha = 2/(\lambda_1 + \lambda_n)$ 即得到上述最坏情形公比。条件数 $\kappa = \lambda_1/\lambda_n$ 越大，公比 $\left(\frac{\kappa - 1}{\kappa + 1}\right)^2$ 越接近 $1$，收敛越慢。

锯齿现象是最速下降法的固有缺陷，也是促使人们寻找更好步长策略（如 Barzilai-Borwein 方法）或更好搜索方向（如共轭梯度法、牛顿法）的动因。

3.2.2 非精确线搜索#

精确线搜索每步都要求解一维优化问题，计算代价高。实际中更常用非精确线搜索——只要求步长满足两个基本要求：

1. 保下降：$f(x^{k+1}) < f(x^k)$
2. 不太小：步长不能趋于零（否则算法不前进）

满足这两个要求的经典准则有 Armijo 准则、Goldstein 准则和 Wolfe 准则，其中 Armijo 准则和 Wolfe 准则最为常用。

3.2.3 Armijo 准则#

若 $d_k$ 是 $x^k$ 处的下降方向，步长 $\alpha$ 满足 Armijo 条件：

右端的几何含义是一条过 $(0, f(x^k))$ 的直线，斜率为 $c_1\,\nabla f(x^k)^\top d_k$。由于 $d_k$ 是下降方向，$\nabla f(x^k)^\top d_k < 0$，因此右端第二项为负，Armijo 条件保证了函数值的严格下降：$f(x^k + \alpha d_k) \leq f(x^k) + \text{负数} < f(x^k)$。

参数 $c_1$ 控制了下降的充分程度。$c_1$ 越接近 $0$，条件越宽松；$c_1$ 越接近 $1$，要求的下降量越接近线性近似预测的下降量。实际中常取 $c_1 = 10^{-4}$ 一类的小值。

Armijo 准则的一个缺陷是 $\alpha = 0$ 总满足条件，因此仅靠 Armijo 准则无法排除步长过小的情况。需要配合回退法（取最小 $m_k$）或其他准则（如 Wolfe 的曲率条件）来保证步长不会退化为零。

仅使用 Armijo 准则而不加保护会导致算法失败的例子并不难构造。考虑一维问题 $f(x) = x^2$，若选取 $\alpha_k$ 使得迭代点交替为 $x^k = (-1)^k / k$，函数值 $f(x^k) = 1/k^2$ 确实单调下降且满足 Armijo 条件，但迭代点在原点两侧振荡，不收敛到极小点。这说明”函数值下降”本身不足以保证收敛，还需要步长不能太小。

3.2.4 Wolfe 准则#

Wolfe 准则在 Armijo 条件的基础上增加了一个曲率条件，用于排除步长过小的情况。步长 $\alpha$ 满足 Wolfe 准则，若同时满足：

其中 $c_1, c_2 \in (0, 1)$ 且 $c_1 < c_2$。实际中常取 $c_1 = 10^{-4}$，$c_2 = 0.9$。

第一个条件就是 Armijo 条件。第二个条件的含义是：记 $\phi(\alpha) = f(x^k + \alpha d_k)$，则 $\phi'(\alpha) = \nabla f(x^k + \alpha d_k)^\top d_k$，曲率条件要求 $\phi'(\alpha) \geq c_2 \phi'(0)$。由于 $\phi'(0) < 0$（下降方向），曲率条件要求 $\phi$ 在 $\alpha$ 处的斜率不能太负——换言之，函数在该点处不能还在急剧下降，否则说明步长还可以更大。

Wolfe 准则与 Armijo 准则的区别在于：Armijo 只管”步长不能太大”（函数值要充分下降），Wolfe 还管”步长不能太小”（曲率条件排除了函数还在快速下降的点）。精确线搜索的最优步长 $\alpha^*$ 处 $\phi'(\alpha^*) = 0$，总是满足曲率条件，因此 Wolfe 准则在大多数情况下包含精确线搜索的解。

在拟牛顿法（BFGS、L-BFGS）等算法中，Wolfe 准则是必需的——这些算法依赖曲率条件来保证 Hessian 近似矩阵的正定性。Wolfe 准则也是 Zoutendijk 定理的前提条件：该定理保证在梯度 Lipschitz 连续的下有界函数上，满足 Wolfe 准则的线搜索算法必然有 $\sum_{k=0}^{\infty}\cos^2\theta_k\|\nabla f(x^k)\|^2 < +\infty$（其中 $\theta_k$ 为下降方向与负梯度的夹角），进而当 $\theta_k$ 有远离 $\pi/2$ 的一致下界时，$\nabla f(x^k) \to 0$。

Armijo vs Wolfe 小结. Armijo 准则实现简单（配合回退法即可），足以保证梯度下降的收敛性，是本章分析的默认步长策略。Wolfe 准则条件更强，保证精确线搜索解被包含，是拟牛顿法等高阶方法的标配。在读论文时遇到”步长满足 Wolfe 条件”的假设，可以理解为”步长既不太大也不太小”。

3.2.5 回退法（Backtracking）#

回退法是寻找满足 Armijo 准则步长的标准算法。设 $\alpha_k = \beta \cdot \gamma^{m_k}$，其中 $\beta > 0$ 为初始步长，$\gamma \in (0, 1)$ 为缩减因子。

算法流程：从 $m_k = 0$（即 $\alpha = \beta$）开始，逐步增大 $m_k$（即逐步缩小 $\alpha$），直到找到最小正整数 $m_k$ 使 Armijo 条件成立。

回退法同时满足了”保下降”和”不太小”两个要求：Armijo 条件保证下降，取最小正整数 $m_k$ 保证步长不会被不必要地缩小——一旦满足条件就立即停止回退。

回退法的局限在于它无法保证找到满足 Wolfe 准则的步长，因为曲率条件 $\phi'(\alpha) \geq c_2\phi'(0)$ 不一定在回退过程中被满足。需要 Wolfe 步长时，需使用更复杂的线搜索算法（如 Fletcher 的 zoom 算法），该算法在满足 Armijo 条件的区间内进一步搜索满足曲率条件的点。

回退法的另一个实际问题是对初始步长 $\beta$ 和缩减因子 $\gamma$ 的敏感性。$\gamma$ 过大（如 $0.9$）时每次缩减幅度小，需要多次试探；$\gamma$ 过小（如 $0.1$）时可能跳过较好的步长。一种改进是基于多项式插值的线搜索：利用已知的函数值和梯度信息构造二次插值函数，用其极小点作为下一个试探步长，比指数缩减更高效。

至此，梯度下降的算法框架和步长选取策略已经完整。接下来转向收敛性分析：梯度下降在什么条件下收敛？收敛有多快？回答这些问题的核心工具是下降引理。

3.3.1 引理陈述#

引理（下降引理）. 设 $f: \mathbb{R}^n \to \mathbb{R}$ 是 $L$-光滑函数（即连续可微且梯度 $L$-Lipschitz 连续），则对任意 $x, y \in \mathbb{R}^n$，有

等价地，去掉绝对值后有上界形式（最常用的形式）：

这个不等式与泰勒展开的关系非常直接。回忆函数 $f$ 在 $x$ 处的一阶泰勒展开为 $f(y) \approx f(x) + \nabla f(x)^\top(y - x)$，余项是 $f(y) - f(x) - \nabla f(x)^\top(y-x)$。对于二阶可微的函数，余项等于 $\frac{1}{2}(y-x)^\top \nabla^2 f(\xi)(y-x)$，其大小取决于 Hessian 矩阵。下降引理的意义在于：即使不假设二阶可微，只要梯度 Lipschitz 连续，余项就可以被 $\frac{L}{2}\|y-x\|^2$ 统一控制。因此，$L$-光滑函数在每一点都被一个开口为 $L$ 的二次函数从上方”罩住”。

当 $f$ 额外满足凸性时，由一阶条件 $f(y) \geq f(x) + \nabla f(x)^\top(y-x)$，下降引理给出双侧夹逼：

左侧不等式来自凸性（二次下界），右侧来自 $L$-光滑性（二次上界）。凸性提供下界，光滑性提供上界——两者互补，共同刻画了函数值与线性近似之间的精确偏差范围。

用更直观的方式理解：$f(y)$ 的值被夹在两个二次函数之间。下方的二次函数是 $f(x) + \nabla f(x)^\top(y-x)$（一阶泰勒近似，即切平面），上方的是 $f(x) + \nabla f(x)^\top(y-x) + \frac{L}{2}\|y-x\|^2$（切平面加一个开口为 $L$ 的抛物面）。$L$ 越小，两个二次函数越贴近，对函数值的定位越精确。这就是为什么 $L$ 小的函数”更好优化”——每一步的线性近似质量更高，可以走更大的步长。

3.3.2 证明#

证明的核心思路是构造辅助函数 + 积分 + Lipschitz 条件放缩。

第一步：构造辅助函数并积分。 定义

其关键性质为：$g(0) = f(x)$，$g(1) = f(y)$，$g'(t) = \nabla f(x + t(y-x))^\top (y - x)$。由微积分基本定理：

注意 $g'(0) = \nabla f(x)^\top(y - x)$，因此

第二步：取绝对值并用 Cauchy-Schwarz 不等式放缩。 对积分取绝对值，利用 $\left|\int_0^1 h(t)\,dt\right| \leq \int_0^1 |h(t)|\,dt$，再对被积函数应用 Cauchy-Schwarz 不等式：

第三步：利用 Lipschitz 连续性。 由 $\nabla f$ 的 Lipschitz 连续性：

代入积分：

证毕。$\blacksquare$

证明的模式识别。 这个证明展示了一种在分析中反复出现的模式：将多元函数的问题归结为一元函数（通过辅助函数 $g(t)$），利用微积分基本定理将函数值差表示为积分，再用 Lipschitz 条件对被积函数做逐点放缩。同样的技巧在后续章节分析近端梯度法和加速方法时还会用到。

3.3.3 下降引理与梯度下降步长的联系#

下降引理直接解释了梯度下降中步长为何受限于 $2/L$。将引理中的 $y$ 替换为 $x^{k+1} = x^k - \alpha_k \nabla f(x^k)$，得

代入 $x^{k+1} - x^k = -\alpha_k \nabla f(x^k)$，整理得

要保证函数值严格下降（右端增量为负），需要

进一步，当 $\alpha_k \leq 1/L$ 时，$1 - L\alpha_k/2 \geq 1/2$，上式化为更常用的形式：

不等式 ($\star$) 是后续收敛性分析的起点：它说明函数值序列 $\{f(x^k)\}$ 单调不增，每一步至少下降 $\frac{\alpha_k}{2}\|\nabla f(x^k)\|^2$。只要梯度不为零，函数值就严格下降。

这里可以看到 $L$ 对步长的直接约束：$L$ 越大（函数弯曲越厉害），允许的步长 $\alpha_k$ 就越小。最优常数步长为 $\alpha_k = 1/L$，此时每步下降量为 $\frac{1}{2L}\|\nabla f(x^k)\|^2$。

值得将下降引理的含义与 3.1.2 节中 $L$-光滑性的直觉对照：$L$-光滑性说函数被二次函数”罩住”，下降引理将这个抽象性质转化为可直接使用的不等式工具。在算法分析中，下降引理扮演的角色是：在不知道函数二阶信息的情况下，用 $L$ 这个单一参数为函数值的变化提供定量的上界控制。

3.4.1 定理陈述#

定理. 设 $f(x)$ 是凸函数，且 $f$ 是 $L$-光滑的。设 $f^* = f(x^*) = \inf_x f(x)$ 存在且可达。若步长取常数 $\alpha_k = \alpha$，满足

则梯度下降迭代 $x^{k+1} = x^k - \alpha \nabla f(x^k)$ 产生的序列满足

即收敛速度为 $O(1/k)$（次线性收敛）。取最优步长 $\alpha = 1/L$ 时，上界变为 $\frac{L\|x^0 - x^*\|^2}{2k}$，可以看出 $L$ 越大（函数越不光滑）、初始点越远离最优解，收敛所需的迭代次数就越多。

$O(1/k)$ 的收敛速度意味着：要使函数值误差 $f(x^k) - f^*$ 降至 $\varepsilon$ 以下，需要的迭代次数为 $O(1/\varepsilon)$。具体地，迭代 $100$ 次时误差大约是初始误差的 $1/100$；要再降低一个数量级（到 $1/1000$），需要 $1000$ 次迭代。每多一位精度都需要 $10$ 倍的迭代次数。

3.4.2 证明#

证明分四步，分别利用下降引理、凸性一阶条件、配方消项和单调性。

第一步：利用下降引理建立单步递推。 由 3.3.3 节的不等式 ($\star$)：

第二步：利用凸性建立与最优值的联系。 由 $f$ 的凸性（一阶条件），对任意 $x, y$：

取 $y = x^*$，移项得

这一步的作用是将梯度与函数值差联系起来——凸性保证了梯度指向的方向上函数值确实在下降，而且下降量可以用 $f(x^k) - f^*$ 来控制。

第三步：配方与累和消项。 将不等式 ($\star$) 两边减去 $f^*$，并结合凸性，注意到

这一步的动机是构造望远镜结构：右端恰好是 $\|x^k - x^*\|^2 - \|x^{k+1} - x^*\|^2$ 的形式，对 $k$ 求和后会大量消项。配方的具体验证：将右端展开，$\|x^k - x^*\|^2 - \|x^k - \alpha\nabla f(x^k) - x^*\|^2 = 2\alpha\nabla f(x^k)^\top(x^k - x^*) - \alpha^2\|\nabla f(x^k)\|^2$，再除以 $2\alpha$ 即得左端。

由于 $x^{k+1} = x^k - \alpha\nabla f(x^k)$，上式变为

因此

对 $i = 1, 2, \ldots, k$ 求和，右端发生望远镜消项（telescoping）：

最后一个不等号是因为 $\|x^k - x^*\|^2 \geq 0$。

第四步：利用单调性得到次线性收敛率。 由不等式 ($\star$)，$\{f(x^k)\}$ 单调不增，因此 $f(x^k) \leq f(x^i)$ 对所有 $i = 1, \ldots, k$ 成立。于是

从而

证毕。$\blacksquare$

收敛性也可以从另一个角度看：对不等式 ($\star$) 从 $k=0$ 到 $\infty$ 求和，右端有界（因 $f$ 下有界），说明级数 $\sum_{k=0}^{\infty}\|\nabla f(x^k)\|^2$ 收敛。由级数收敛的必要条件，通项 $\|\nabla f(x^k)\|^2 \to 0$，从而 $f(x^k) \to f^*$。

关于 $O(1/k)$ 速度的紧性。 $O(1/k)$ 对于一般凸函数上的梯度下降是不可改进的——存在 $L$-光滑凸函数使得梯度下降恰好以 $\Theta(1/k)$ 的速度收敛。不过，通过引入动量项（如 Nesterov 加速方法），可以将凸函数上的收敛速度提升至 $O(1/k^2)$，这是一阶方法在此函数类上的最优速度。梯度下降的 $O(1/k)$ 与 Nesterov 方法的 $O(1/k^2)$ 之间的差距，本质上源于梯度下降只利用当前点的梯度信息，而加速方法额外利用了历史迭代点的信息来修正搜索方向。

从梯度范数角度看收敛。 利用 3.1.2 节的不等式 $f(x^k) - f^* \geq \frac{1}{2L}\|\nabla f(x^k)\|^2$，$O(1/k)$ 的函数值收敛率蕴含了 $\min_{0 \leq i \leq k}\|\nabla f(x^i)\|^2 = O(1/k)$，即 $k$ 步迭代中最小梯度范数以 $O(1/\sqrt{k})$ 的速率趋于零。这个结论对非凸函数也成立（只需 $L$-光滑性），下一小节将给出完整的陈述和证明。

3.4.3 非凸函数上的收敛性#

在深度学习等应用中，目标函数通常是非凸的。此时不能期望收敛到全局最优解，但梯度下降仍然可以保证收敛到驻点（梯度为零的点）。这个结论只依赖 $L$-光滑性，不需要凸性。

定理. 设 $f: \mathbb{R}^n \to \mathbb{R}$ 是 $L$-光滑函数（不要求凸性），且 $f$ 下有界，即 $f^* = \inf_x f(x) > -\infty$。若步长取常数 $\alpha \leq 1/L$，则梯度下降迭代 $x^{k+1} = x^k - \alpha \nabla f(x^k)$ 产生的序列满足

即 $k$ 步迭代中最小梯度范数的平方以 $O(1/k)$ 的速率趋于零。等价地，要找到一个 $\varepsilon$-近似驻点（$\|\nabla f(x)\|^2 \leq \varepsilon$），需要 $O(1/\varepsilon)$ 次迭代。

证明. 证明只需要下降引理，不涉及凸性。由 3.3.3 节的不等式 ($\star$)（该不等式的推导不使用凸性），当 $\alpha \leq 1/L$ 时

对 $k = 0, 1, \ldots, K-1$ 求和（望远镜消项）：

移项并利用 $f(x^K) \geq f^*$：

由于左端有 $K$ 项非负求和，最小项不超过平均值：

取 $\alpha = 1/L$ 时上界为 $\frac{2L(f(x^0) - f^*)}{K}$。证毕。$\blacksquare$

这个定理说明：即使没有凸性，梯度下降也能在 $O(1/\varepsilon)$ 步内找到一个梯度足够小的点。注意结论的度量是 $\min_{0 \leq i \leq k}\|\nabla f(x^i)\|^2$ 而非 $\|\nabla f(x^k)\|^2$——我们只能保证迭代过程中存在某个梯度小的点，但不保证最后一个迭代点的梯度就小。在实际中，通常记录迭代过程中梯度范数最小的点作为输出。

对于 AI 研究者来说，这一结论是理解 SGD 训练神经网络收敛行为的起点：虽然深度学习中的目标函数是非凸的，但梯度下降仍然可以有效地找到驻点。当然，从”找到驻点”到”找到好的局部极小”还需要额外的分析（如鞍点逃逸理论），这超出了本章的范围。

3.5.1 等价条件引理#

在分析强凸情况前，需要一个关于 Lipschitz 连续梯度的等价条件引理，它提供的余强制性是证明的关键工具。

引理. 设 $f(x)$ 是 $\mathbb{R}^n$ 上的凸且可微函数，则以下三个条件等价：

(1) $\nabla f$ 是 Lipschitz 连续的（常数为 $L$）；

(2) 函数 $g(x) = \frac{L}{2}x^\top x - f(x)$ 是凸函数；

(3) $\nabla f$ 是余强制（cocoercive）算子，即对任意 $x, y \in \mathbb{R}^n$：

证明.

(1) $\Rightarrow$ (2)：需证 $g(x) = \frac{L}{2}x^\top x - f(x)$ 是凸函数。由凸性的梯度单调性判据，只需验证 $\nabla g$ 是单调算子。对任意 $x, y$，

由 Cauchy-Schwarz 不等式和 $\nabla f$ 的 $L$-Lipschitz 连续性，$(\nabla f(x) - \nabla f(y))^\top(x-y) \leq \|\nabla f(x) - \nabla f(y)\|\cdot\|x-y\| \leq L\|x-y\|^2$。因此上式 $\geq 0$，即 $\nabla g$ 单调，$g$ 是凸函数。

(3) $\Rightarrow$ (1)：由余强制性和 Cauchy-Schwarz 不等式，

两端除以 $\|\nabla f(x) - \nabla f(y)\|$（若其为零则 Lipschitz 条件自动成立），得 $\|\nabla f(x) - \nabla f(y)\| \leq L\|x-y\|$。

(2) $\Rightarrow$ (3)：这是最关键的一步。构造辅助函数

$f_x$ 仍然是凸函数（$f$ 凸，减去线性函数不改变凸性），且 $\nabla f_x(z) = \nabla f(z) - \nabla f(x)$，所以 $\nabla f_x(x) = 0$，即 $x$ 是 $f_x$ 的全局最小值点。

由条件 (2)，$g_x(z) = \frac{L}{2}z^\top z - f_x(z)$ 是凸函数。对 $g_x$ 使用凸性的一阶条件 $g_x(z_2) \geq g_x(z_1) + \nabla g_x(z_1)^\top(z_2 - z_1)$，整理后得到 $f_x$ 的二次上界：

在上式中取 $z_1 = y$，并对 $z_2$ 取使右端最小的 $z_2 = y - \frac{1}{L}\nabla f_x(y)$，代入得

由于 $x$ 是 $f_x$ 的全局最小值点，$f_x(x) \leq f_x\!\left(y - \frac{1}{L}\nabla f_x(y)\right)$，因此

即

对 $f_y(z) = f(z) - \nabla f(y)^\top z$ 做完全对称的分析，得到

将 (I) 和 (II) 两式相加，左端为 $(\nabla f(x) - \nabla f(y))^\top(x - y)$，右端为 $\frac{1}{L}\|\nabla f(x) - \nabla f(y)\|^2$，这正是余强制性。$\blacksquare$

余强制性比单纯的 Lipschitz 条件更强：它不仅控制了梯度差的大小，还要求梯度差与自变量差之间有正相关性。直觉上，Lipschitz 条件给出的是上界（梯度差 $\leq L \cdot$ 自变量差），余强制性给出的是下界（内积 $\geq \frac{1}{L} \cdot$ 梯度差的平方）。两者结合意味着梯度差和自变量差之间存在双向的定量控制。这个性质在强凸函数收敛性证明中起关键作用。

值得注意的是，余强制性仅在 $f$ 为凸时与 Lipschitz 条件等价。对于非凸函数，Lipschitz 条件不蕴含余强制性。这解释了为什么本章的收敛性分析需要凸性假设——不仅仅是为了保证极小点的存在，更是为了启用余强制性这一更强的分析工具。

3.5.2 定理陈述#

定理. 设 $f(x)$ 是 $\mu$-强凸函数（$\mu$ 为强凸参数），且 $f$ 是 $L$-光滑的。设 $f^* = f(x^*) = \inf_x f(x)$ 存在且可达。若步长 $\alpha$ 满足

则梯度下降迭代产生的序列 $\{x^k\}$ 收敛到 $x^*$，且为 Q-线性收敛：

$O(c^k)$ 的收敛速度意味着：误差以几何级数衰减，每迭代一步误差都乘以一个小于 $1$ 的常数 $c$。取最优步长 $\alpha = 2/(\mu+L)$ 时，$c = \left(\frac{L-\mu}{L+\mu}\right)^2 = \left(\frac{\kappa - 1}{\kappa + 1}\right)^2$，其中 $\kappa = L/\mu$ 是条件数。当 $\kappa = 10$ 时，$c \approx 0.67$，迭代 $100$ 次误差衰减为初始值的 $c^{100} \approx 10^{-17}$；当 $\kappa = 100$ 时，$c \approx 0.96$，迭代 $100$ 次误差仅衰减为 $c^{100} \approx 0.017$。条件数对收敛速度的影响极为显著。

3.5.3 证明#

第一步：构造辅助函数并建立加强版余强制不等式。

定义辅助函数

构造这个辅助函数的动机是将强凸函数”剥去”强凸的部分：由于 $f$ 是 $\mu$-强凸的，减去凸的二次项 $\frac{\mu}{2}x^\top x$ 后，$g(x)$ 仍然是凸的（恰好将强凸性用尽）。其梯度为 $\nabla g(x) = \nabla f(x) - \mu x$。

另一方面，$\frac{L}{2}x^\top x - f(x) = \frac{1}{2}(L-\mu)x^\top x - g(x)$ 也是凸函数（由 3.5.1 节等价条件引理中条件 (2)），因此 $\nabla g$ 是 $(L-\mu)$-Lipschitz 连续的。由余强制性（条件 (3)），有

将 $\nabla g(x) = \nabla f(x) - \mu x$，$\nabla g(y) = \nabla f(y) - \mu y$ 代入。为简化符号，记 $u = \nabla f(x) - \nabla f(y)$，$v = x - y$，$\Delta = u^\top v$。