3.4 一阶方法的进展

3.3 节的梯度下降有两个理想化：每步都能计算全体数据上的精确梯度，且收敛速度由条件数直接决定。实际训练中这两条都不成立：数据量使全梯度计算昂贵，条件数在深度网络中动辄成千上万。本节介绍针对这两个问题的四类改进，以及它们在分布式场景下的形态。

改进分两条线。确定性问题的线：动量法与重球法平滑迭代轨迹，Nesterov 加速把条件数依赖从 $\kappa$ 降到 $\sqrt{\kappa }$ 并达到一阶方法的最优速率。随机问题的线：随机梯度下降用小批量估计梯度，把每次迭代的代价降到与样本量无关；方差缩减方法（SVRG、SAGA）通过控制变量把随机方法的线性收敛找回来；自适应步长（AdaGrad、Adam）自动调整每个坐标的有效步长，等价于在线学习一个对角缩放。最后一小节处理规模问题：大批量训练、本地 SGD 与联邦学习，它们的共同主题是把通信与计算重新分配。

本节的分析工具来自 3.3 节：下降引理、光滑性与强凸性给出的二次界、以及条件数。区别只在梯度不再是精确值：随机梯度是真实梯度的无偏估计，噪声的方差成为速率公式中的新参数。

3.4.1 动量法

病态问题中的震荡

梯度下降在条件数大的问题上表现出一对典型症状：沿低曲率方向前进缓慢，在高曲率方向来回震荡。二次函数上可以精确看出原因：第 $i$ 个特征方向的更新因子为 $1-\eta {\lambda }_i$，当 $\eta \approx 1/L$ 且 ${\lambda }_i\approx L$ 时，因子接近零甚至为负，轨迹在该方向上反复跳动；而 ${\lambda }_i\approx m$ 的方向上因子接近 $1$，每步只前进一点点。

动量法在更新中保留历史方向，让低频方向的分量逐步累积，高频方向的分量在振荡中相互抵消。带权重的历史累积称为动量：

$${\mathbf{v}}_{k+1}=\beta {\mathbf{v}}_k-\eta \mathrm{\nabla }f({\mathbf{x}}_k),{\mathbf{x}}_{k+1}={\mathbf{x}}_k+{\mathbf{v}}_{k+1}$$

$\beta \in [0,1)$ 是动量系数。$\beta =0$ 时退化为梯度下降；$\beta$ 接近 $1$ 时更新方向是梯度的指数滑动平均（EMA），相当于对梯度做了低通滤波。深度学习框架中的 SGD with momentum 就是这一形式，默认 $\beta =0.9$。

重球法与收敛条件

动量法的一个经典分析形式是重球法（heavy ball method），把动量写成相邻两步的差：

$${\mathbf{x}}_{k+1}={\mathbf{x}}_k-\eta \mathrm{\nabla }f({\mathbf{x}}_k)+\beta ({\mathbf{x}}_k-{\mathbf{x}}_{k-1})$$

两种写法相差一个 $\beta$ 倍的历史项的重组，行为相近。收敛条件与梯度下降类似但更宽松：$\eta <2/L$ 且 $\beta <1$ 时方法稳定。在强凸二次函数上，取最优参数

$${\eta }^{\ast }=\frac{4}{(\sqrt{L}+\sqrt{m}{)}^2},{\beta }^{\ast }={\left(\frac{\sqrt{L}-\sqrt{m}}{\sqrt{L}+\sqrt{m}}\right)}^2$$

时，距离到最优点的收缩因子为

$$\frac{\sqrt{\kappa }-1}{\sqrt{\kappa }+1},\kappa =\frac{L}{m}$$

达到与共轭梯度法同阶的速率。这一结论有两个限制：参数依赖已知的 $m$ 与 $L$；对一般凸函数（无强凸性）重球法可能不如梯度下降稳定。因此实践中常用的动量系数（$0.9$ 这类经验值）是折衷，而不是上述最优参数。

动量还提供一项与收敛速率无关的实用好处：梯度噪声的方差被平均抑制。随机梯度带噪时，动量对历史梯度做指数平均，等效于把有效批量放大到 $1/(1-\beta )$ 量级，这一作用在 3.4.5 节的 Adam 中再次出现。

3.4.2 Nesterov 加速与一阶方法的最优性

加速梯度法

Nesterov 加速梯度法（accelerated gradient descent，AGD）在动量之外引入外推：梯度不在当前点计算，而在沿动量方向外推得到的点上计算。

$$\begin{array}{rl}{\mathbf{x}}_{k+1}& ={\mathbf{y}}_k-\frac{1}{L}\mathrm{\nabla }f({\mathbf{y}}_k)\\ {\mathbf{y}}_{k+1}& ={\mathbf{x}}_{k+1}+\frac{t_k-1}{t_{k+1}}({\mathbf{x}}_{k+1}-{\mathbf{x}}_k),t_{k+1}=\frac{1+\sqrt{1+4t_k^2}}{2}\end{array}$$

初值取 ${\mathbf{y}}_0={\mathbf{x}}_0$，$t_0=1$。系数的来源是估计序列技巧：序列 $(t_k-1)/t_{k+1}$ 的增长速度为 $1-3/(k+O(1))$，与动量系数逐步逼近 $1$ 的行为一致。外推的含义是：既然迭代正在沿某个方向稳步前进，先走半步再计算梯度，梯度会更接近前方的真实方向。

速率结论分两档。

凸且光滑：

$$f({\mathbf{x}}_k)-f({\mathbf{x}}^{\ast })\le \frac{2L\parallel {\mathbf{x}}_0-{\mathbf{x}}^{\ast }{\parallel }^2}{(k+1{)}^2}$$

$O(1/k^2)$，比梯度下降的 $O(1/k)$ 快一个数量级。达到精度 $ϵ$ 需要 $O(1/\sqrt{ϵ})$ 次迭代，而梯度下降需要 $O(1/ϵ)$。

强凸且光滑：加入强凸系数后（或在加速法上周期性重启），线性收敛速率中的条件数依赖变为 $\sqrt{\kappa }$：

$$f({\mathbf{x}}_k)-f({\mathbf{x}}^{\ast })\le C{(1-\frac{1}{\sqrt{\kappa }})}^k(f({\mathbf{x}}_0)-f({\mathbf{x}}^{\ast }))$$

迭代次数从 $O(\kappa \log (1/ϵ))$ 降到 $O(\sqrt{\kappa }\log (1/ϵ))$。条件数从 ${10}^4$ 降到 $100$ 量级的收益，在 3.3 节的数值实验中已经看到。

一阶方法的最优性

加速是否已经到顶，由 Nesterov 下界回答。在一阶 oracle 模型下（算法只能访问函数值与梯度，不能访问 Hessian，也不能利用问题结构），存在一个凸光滑函数使任何一阶算法在第 $k$ 步满足

$$f({\mathbf{x}}_k)-f({\mathbf{x}}^{\ast })\ge \frac{3L\parallel {\mathbf{x}}_0-{\mathbf{x}}^{\ast }{\parallel }^2}{32(k+1{)}^2}$$

强凸情形下也有对应的下界，形式为 ${\left(\frac{\sqrt{\kappa }-1}{\sqrt{\kappa }+1}\right)}^{2k}$ 量级。与上界的 $O(1/k^2)$ 相比，两者差一个常数因子，因此 Nesterov 加速在一阶 oracle 模型下是最优的（相差常数），再多的一阶信息也无法突破 $1/k^2$。

oracle 复杂度：优化的抽象计算模型

一阶 oracle 模型把算法能获得的信息限制为每个点的函数值与梯度。复杂度分析在 model 内进行：上界给出算法，下界给出模型内所有算法的共同限制。这一框架把优化算法与问题结构分开：访问 Hessian（二阶 oracle）或利用问题结构（如稀疏、低秩）可以得到更快的算法，而一般的一阶方法已经触及该模型的天花板。这也解释了 3.5 节与 3.7 节的必要性：牛顿法、拟牛顿法与近端方法都在使用一阶 oracle 之外的额外结构。

下列代码在条件数 $100$ 的二次函数上对比三种方法。重球法使用针对该二次函数的最优参数，Nesterov 加速只使用 $L$。

import numpy as np

m, L = 1.0, 100.0
Q = np.diag([m, L])
f = lambda x: 0.5 * x @ (Q @ x)

def gd(kmax=3000):
    x = np.array([1.0, 1.0]); hist = []
    for _ in range(kmax):
        hist.append(f(x))
        x = x - (1 / L) * (Q @ x)
    return np.array(hist)

def heavy_ball(kmax=3000):
    eta = 4 / (np.sqrt(L) + np.sqrt(m)) ** 2
    beta = ((np.sqrt(L) - np.sqrt(m)) / (np.sqrt(L) + np.sqrt(m))) ** 2
    x, x_prev = np.array([1.0, 1.0]), np.array([1.0, 1.0])
    hist = []
    for _ in range(kmax):
        hist.append(f(x))
        x, x_prev = x - eta * (Q @ x) + beta * (x - x_prev), x
    return np.array(hist), eta, beta

def nesterov(kmax=3000):
    x = x_prev = y = np.array([1.0, 1.0])
    t = 1.0
    hist = []
    for _ in range(kmax):
        hist.append(f(x))
        x_new = y - (1 / L) * (Q @ y)
        t_new = (1 + np.sqrt(1 + 4 * t ** 2)) / 2
        y = x_new + ((t - 1) / t_new) * (x_new - x)
        x_prev, x, t = x, x_new, t_new
    return np.array(hist)

h_gd = gd()
h_hb, eta_hb, beta_hb = heavy_ball()
h_nt = nesterov()
print(f"重球法最优参数：eta = {eta_hb:.6f}，beta = {beta_hb:.6f}")
print(f"  距离收缩因子 (sqrt(kappa)-1)/(sqrt(kappa)+1) = {(10 - 1) / (10 + 1):.4f}，函数值收缩 = {((10 - 1) / (10 + 1)) ** 2:.4f}")
for name, h in [("梯度下降", h_gd), ("重球法", h_hb), ("Nesterov", h_nt)]:
    k_star = int(np.argmax(h <= 1e-8))
    print(f"  {name:8s}: f 降到 1e-8 的步数 = {k_star}，k = 200 时 f = {h[200]:.3e}")
# 梯度下降受条件数限制需要近千步；重球法（参数针对该问题调优）与 Nesterov 都在两百步内达到

输出显示：梯度下降需要 $882$ 步把函数值降到 ${10}^{-8}$；重球法（使用针对该二次函数的 ${\eta }^{\ast }$ 与 ${\beta }^{\ast }$）需要 $81$ 步，与收缩因子公式一致；Nesterov 加速在只知道 $L$ 的情况下需要 $163$ 步。三个数字的对比给出两个结论：动量类方法对条件数的改善是实质性的（十倍的差距）；已知 $m$ 与 $L$ 时重球法可以更快，但它的参数依赖问题谱信息，而 Nesterov 的系数只依赖 $L$，其优势在无调参的普适性上。

3.4.3 随机梯度下降

目标与梯度估计

机器学习中的目标函数通常是样本平均：

$$f(\mathbf{w})=\frac{1}{n}\sum _{i=1}^n{f}_i(\mathbf{w})$$

$n$ 可以到 ${10}^8$ 量级，计算全梯度的代价为 $O(n)$，梯度下降每步都要付出这个代价。随机梯度下降（stochastic gradient descent，SGD）用单个样本或小批量的梯度代替全梯度：

$${\mathbf{g}}_B=\frac{1}{|B|}\sum _{i\in B}\mathrm{\nabla }{f}_i(\mathbf{w}),{\mathbf{w}}_{k+1}={\mathbf{w}}_k-{\eta }_k{\mathbf{g}}_B$$

$B$ 是从 $\{1,\dots ,n\}$ 均匀抽取的小批量。${\mathbf{g}}_B$ 是全梯度的无偏估计：$E[{\mathbf{g}}_B]=\mathrm{\nabla }f(\mathbf{w})$，方差为 ${\sigma }_1^2/|B|$，其中 ${\sigma }_1^2$ 为单样本梯度的方差。批量翻倍，方差减半。后文把批量梯度的方差记为 ${\sigma }^2={\sigma }_1^2/|B|$，速率公式中的噪声项都按它书写。

三档速率

噪声改变了收敛分析的结论，速率公式中多出噪声项。

强凸且光滑，递减步长：取 ${\eta }_k=\frac{1}{mk}$（或对应的常数倍数），

$$E[f({\mathbf{w}}_k)-f({\mathbf{w}}^{\ast })]=O\left(\frac{1}{k}\right)$$

比全梯度的线性收敛慢，但对每次迭代只花 $O(|B|)$ 的算法这是合理代价。

凸且光滑，递减步长：取 ${\eta }_k\propto 1/\sqrt{k}$，

$$E[f({\mathbf{w}}_k)-f({\mathbf{w}}^{\ast })]=O\left(\frac{1}{\sqrt{k}}\right)$$

$O(1/\sqrt{k})$ 是随机凸优化的基本速率，它比全梯度的 $O(1/k)$ 更慢，这一差距在选择小批量与步长时反复出现。

非凸且光滑，固定步长：取 $\eta \le 1/L$，则

$$\frac{1}{K}\sum _{k=1}^{K}E[\parallel \mathrm{\nabla }f({\mathbf{w}}_k){\parallel }^2]\le \frac{2(f({\mathbf{w}}_0)-f({\mathbf{w}}^{\ast }))}{\eta K}+\eta L{\sigma }^2$$

右端第一项随 $K$ 下降，第二项与 $K$ 无关：噪声地板（${\sigma }^2$ 为批量梯度的方差）。固定步长的 SGD 无法把梯度范数降到 $\sqrt{\eta L{\sigma }^2}$ 以下，要突破它必须减小步长或减小方差（后者是下一小节的主题）。实践中观察到的训练后期损失震荡与不再下降，多数由这一项解释。

小批量的作用与噪声的意义

小批量 $|B|$ 在两个方向上作用于速率：方差按 $1/|B|$ 下降，单步代价按 $|B|$ 上升。在噪声主导的区间里，增大批量并按比例增大步长可以保持相同的下降速率与相同的总代价，这就是线性缩放规则；当批量增大到单步代价超过收益时，继续增大只剩代价（临界批量现象）。3.4.6 节回到这一主题。

噪声也有正面作用。梯度噪声使迭代轨迹偏离精确的下降路径，从而有机会离开尖锐的极小点与鞍点，这一效应与泛化性能的关联是深度学习中讨论较多的话题（3.8 节）。无论动机如何，噪声在速率公式中始终以 $\eta {\sigma }^2$ 的形式出现，所有关于它的讨论都建立在这一项上。

3.4.4 方差缩减

控制变量

固定步长 SGD 的噪声地板促使人们寻找方差更小的梯度估计。方差缩减（variance reduction）的基本工具是控制变量（control variate）：为随机变量 $X$ 找一个期望已知的相关量 $Y$（$E[Y]={\mu }_Y$），则 $X-Y+{\mu }_Y$ 仍是 $E[X]$ 的无偏估计，方差为 $\mathrm{Var}(X-Y)$。选择合适的 $Y$ 可以大幅降低方差。

SVRG（stochastic variance reduced gradient）取 $Y=\mathrm{\nabla }{f}_i(\tilde{\mathbf{w}})$，其中 $\tilde{\mathbf{w}}$ 是一个周期性更新的参考点（称为快照点）。内层迭代的梯度估计为

$${\mathbf{g}}_k=\mathrm{\nabla }{f}_{i_k}({\mathbf{w}}_k)-\mathrm{\nabla }{f}_{i_k}(\tilde{\mathbf{w}})+\mathrm{\nabla }f(\tilde{\mathbf{w}})$$

三项的含义：前两项的差在全梯度下为零（同一批样本，两个点），因此 ${\mathbf{g}}_k$ 无偏；第三项是快照点的全梯度，在每个外层开始时计算一次，内层重复使用。方差的关键性质是 $\mathrm{Var}({\mathbf{g}}_k)\propto \parallel {\mathbf{w}}_k-\tilde{\mathbf{w}}{\parallel }^2$：迭代点离快照点越近，梯度估计越准。外层周期性重置快照点，使方差周期性回落，整体效果是把线性收敛找回来。

SAGA 用梯度表实现同一思想：为每个样本保存最近一次计算的梯度，更新时用新旧梯度之差修正。两者的速率都可写成

$$O((n+\kappa )\log \frac{1}{ϵ})$$

单样本梯度计算次数。与全梯度下降的 $O(n\kappa \log (1/ϵ))$ 相比，因子 $\kappa$ 从乘法变成了加法，条件数的惩罚被大幅削弱。代价是需要存储 $n$ 个梯度或周期性计算全梯度（内存或计算），并且当 $\kappa$ 不大时优势有限。

数值对比

下列代码在条件数约 $50$ 的最小二乘问题上对比四种方法，横轴统一为梯度计算次数（全梯度下降每步 $n$ 次，SGD 与 SVRG 内层每步 $1$ 次，SVRG 外层每轮 $n$ 次）。

import numpy as np

rng = np.random.default_rng(0)
n, d = 4000, 40
scales = 0.85 ** np.arange(d)                     # 让特征量纲不同，制造条件数
X = rng.normal(size=(n, d)) * scales
w_true = rng.normal(size=d)
y = X @ w_true + 0.5 * rng.normal(size=n)
lam = 0.02
H = X.T @ X / n + lam * np.eye(d)
Lg, mg = np.linalg.eigvalsh(H).max(), np.linalg.eigvalsh(H).min()
w_star = np.linalg.solve(H, X.T @ y / n)
f_star = 0.5 * np.mean((X @ w_star - y) ** 2) + 0.5 * lam * np.sum(w_star ** 2)
print(f"L = {Lg:.4f}，m = {mg:.4f}，kappa = {Lg / mg:.1f}")

f_all = lambda w: 0.5 * np.mean((X @ w - y) ** 2) + 0.5 * lam * np.sum(w ** 2)
g_all = lambda w: X.T @ (X @ w - y) / n + lam * w
g_i = lambda w, i: X[i] * (X[i] @ w - y[i]) + lam * w
Lmax = float(np.max(np.sum(X ** 2, axis=1)) + lam)

budget = 10 ** 6

# 全梯度下降：每步 n 次梯度计算
w, evals_gd, gaps_gd = np.zeros(d), [], []
ev = 0
while ev < budget:
    evals_gd.append(ev); gaps_gd.append(f_all(w) - f_star)
    w = w - (1 / Lg) * g_all(w); ev += n

# SGD：递减步长
w, evals_sgd, gaps_sgd = np.zeros(d), [], []
for k in range(1, budget + 1):
    i = rng.integers(n)
    w = w - (0.05 / np.sqrt(k)) * g_i(w, i)
    if k % 5000 == 0:
        evals_sgd.append(k); gaps_sgd.append(f_all(w) - f_star)

# SGD：固定步长（观察噪声地板）
w, evals_fix, gaps_fix = np.zeros(d), [], []
for k in range(1, budget + 1):
    i = rng.integers(n)
    w = w - 0.01 * g_i(w, i)
    if k % 5000 == 0:
        evals_fix.append(k); gaps_fix.append(f_all(w) - f_star)

# SVRG：外层全梯度 + 内层 n 步方差缩减
w, evals_sv, gaps_sv = np.zeros(d), [], []
eta_s, ev = 1 / (4 * Lmax), 0
while ev < budget:
    w_tilde = w.copy(); full = g_all(w_tilde); ev += n
    evals_sv.append(ev); gaps_sv.append(f_all(w) - f_star)
    for _ in range(n):
        i = rng.integers(n)
        w = w - eta_s * (g_i(w, i) - g_i(w_tilde, i) + full)
        ev += 1

print("在相同梯度计算次数下的 f - f*：")
print("方法         10^4        10^5        10^6")
for name, evs, gs in [("全梯度", evals_gd, gaps_gd), ("SGD-递减", evals_sgd, gaps_sgd),
                      ("SGD-固定", evals_fix, gaps_fix), ("SVRG", evals_sv, gaps_sv)]:
    row = []
    for M in [10 ** 4, 10 ** 5, 10 ** 6]:
        idx = int(np.searchsorted(evs, M, side="right")) - 1
        row.append(f"{gs[idx]:.2e}" if idx >= 0 else "----")
    print(f"{name:10s}   " + "   ".join(f"{v:>8s}" for v in row))

输出：

L = 1.0146，m = 0.0200，kappa = 50.7
在相同梯度计算次数下的 f - f*：
方法         10^4        10^5        10^6
全梯度         2.07e-01    1.01e-02    1.29e-08
SGD-递减      3.73e-02    6.44e-03    8.27e-05
SGD-固定      3.28e-03    1.87e-03    4.36e-03
SVRG        2.11e+00    1.67e-15    5.55e-17

表格中的四行对应四种典型行为。全梯度下降前期昂贵（一万次梯度计算只完成 $2.5$ 步），后期借助线性收敛补上，达到 ${10}^{-8}$。递减步长的 SGD 遵循 $O(1/\sqrt{k})$ 的次线性速率，一百万次梯度计算后停在 ${10}^{-4}$ 量级，与线性收敛的差距清晰可见。固定步长的 SGD 停在地板 ${10}^{-3}$ 附近，从 ${10}^4$ 到 ${10}^6$ 没有改善，对应公式中的 $\eta L{\sigma }^2$ 项。SVRG 在第一个外层（$4000$ 次梯度计算）内表现平平（$2.11$，快照点尚未发挥作用），之后迅速下降到机器精度 ${10}^{-15}$ 量级，总代价比全梯度下降低两个数量级。方差缩减把随机方法的收敛性质从 $O(1/\sqrt{k})$ 恢复到线性，这是它在条件数可控的中等规模问题上的核心优势。

3.4.5 自适应步长

对角预条件

3.3 节的数值实验说明：条件数由坐标选择决定，缩放坐标可以让收敛速度改善几个数量级。自适应方法把这个缩放内置到算法里：为每个坐标维护一个尺度估计，用梯度的历史信息逐步学习它。

AdaGrad 累积梯度平方并按其平方根缩放：

$${\mathbf{w}}_{k+1}={\mathbf{w}}_k-\frac{\eta }{\sqrt{\sum _{t=1}^k{\mathbf{g}}_t^2}+ϵ}{\mathbf{g}}_k$$

累积量只增不减，因此有效步长单调下降。这一行为对稀疏特征有利（出现频率低的坐标保留较大步长），但在稠密问题上步长衰减过快，训练后期几乎停滞。

RMSProp 把累积改为指数滑动平均，去掉单调衰减：

$${\mathbf{v}}_k={\beta }_2{\mathbf{v}}_{k-1}+(1-{\beta }_2){\mathbf{g}}_k^2,{\mathbf{w}}_{k+1}={\mathbf{w}}_k-\frac{\eta }{\sqrt{{\mathbf{v}}_k}+ϵ}{\mathbf{g}}_k$$

Adam 在二阶矩之外再加一阶矩（动量）与偏差校正：

$${\mathbf{m}}_k={\beta }_1{\mathbf{m}}_{k-1}+(1-{\beta }_1){\mathbf{g}}_k,{\mathbf{v}}_k={\beta }_2{\mathbf{v}}_{k-1}+(1-{\beta }_2){\mathbf{g}}_k^2$$$${\mathbf{w}}_{k+1}={\mathbf{w}}_k-\eta \frac{{\hat{\mathbf{m}}}_k}{\sqrt{{\hat{\mathbf{v}}}_k}+ϵ},{\hat{\mathbf{m}}}_k=\frac{{\mathbf{m}}_k}{1-{\beta }_1^k},{\hat{\mathbf{v}}}_k=\frac{{\mathbf{v}}_k}{1-{\beta }_2^k}$$

偏差校正是为了消除 ${\mathbf{m}}_0={\mathbf{v}}_0=\mathbf{0}$ 导致的初期低估：前几步的滑动平均只看到很少样本，不校正会使初始更新过小。默认参数 ${\beta }_1=0.9$、${\beta }_2=0.999$、$ϵ={10}^{-8}$ 在各框架中通用，学习率 $\eta$ 成为唯一需要调节的参数（典型值 ${10}^{-3}$）。

与条件数的关系

自适应更新可以写成对角预条件形式：${\mathbf{w}}_{k+1}={\mathbf{w}}_k-\eta {\mathbf{D}}_k^{-1}{\mathbf{g}}_k$，其中 ${\mathbf{D}}_k$ 是逐坐标的尺度矩阵。在二次函数上，$\sqrt{\hat{v}}$ 近似每个坐标的梯度量级（正比于该方向的曲率乘坐标值），除以它相当于把每个坐标的曲率归一化。这正是 3.3 节缩放实验想达到的效果，区别在于缩放是算法自动估计的，不需要事先知道问题的谱信息。

下列代码在条件数 ${10}^3$ 的病态二次函数上对比梯度下降与 Adam。梯度下降需要知道 $L$ 才能取步长，Adam 只使用梯度的历史。

import numpy as np

Q = np.diag([1.0, 1000.0])
f = lambda x: 0.5 * x @ (Q @ x)

# 梯度下降：步长 1/L = 1e-3
x, hist = np.array([1.0, 1.0]), []
for k in range(200001):
    hist.append(f(x))
    x = x - 1e-3 * (Q @ x)
print(f"梯度下降（步长 1/L）：f 降到 1e-8 的步数 = {int(np.argmax(np.array(hist) <= 1e-8))}")

# Adam：lr = 0.05，默认 beta
x = np.array([1.0, 1.0])
m_k = np.zeros(2); v_k = np.zeros(2)
b1, b2, eps, lr = 0.9, 0.999, 1e-8, 0.05
hist = []
for k in range(1, 20001):
    hist.append(f(x))
    g = Q @ x
    m_k = b1 * m_k + (1 - b1) * g
    v_k = b2 * v_k + (1 - b2) * g ** 2
    m_hat = m_k / (1 - b1 ** k)
    v_hat = v_k / (1 - b2 ** k)
    x = x - lr * m_hat / (np.sqrt(v_hat) + eps)
hist = np.array(hist)
print(f"Adam（lr = 0.05，beta = 0.9/0.999）：f 降到 1e-8 的步数 = {int(np.argmax(hist <= 1e-8))}")
# 梯度下降受最小曲率限制：慢方向每步只收缩千分之一，需要近万步
# Adam 不需要知道 L 与 m，用两个坐标的梯度量级自动完成尺度校正

输出：梯度下降需要 $8860$ 步，Adam 需要 $192$ 步。Adam 不知道 $L$（也就无法取 $1/L$ 的步长），它的每个坐标的有效步长由该坐标自身的梯度历史决定，两个坐标因此以相近的速率收敛。

Adam 的代价是失去部分理论保证：原始版本存在不收敛的反例（AMSGrad 等修正版本针对这一点），最优解附近的震荡使最终精度通常低于精调的 SGD 加动量。工程上的常见做法是训练中用 Adam，收尾切换 SGD，或者在 Adam 中使用解耦的权重衰减（AdamW）以避免惩罚项被自适应缩放干扰。

3.4.6 大批量训练、本地 SGD 与联邦学习

大批量与线性缩放

随机梯度的方差随批量按 $1/|B|$ 下降，因此增大批量是减小噪声的直接手段。线性缩放规则：批量增大 $k$ 倍时，学习率按比例增大 $k$ 倍，则每次迭代的下降量不变、迭代次数减少 $k$ 倍。规则在噪声主导区间成立；批量增大到梯度噪声被平均掉之后，继续增大只剩单步代价的上升，收益消失（临界批量）。

线性缩放在训练初期不成立：初始参数下梯度方向不稳定，放大后的步长会使训练发散。常用对策是预热（warmup）：前若干步把学习率从很小的值线性升到目标值，之后再按余弦或其他调度衰减。学习率调度（阶梯衰减、余弦退火）的作用是让后期步长足够小以适应噪声地板的下降。

并行方式与通信

数据并行把批量分配到多个设备，每个设备计算局部梯度后求和。同步数据并行每步需要一次全归约（AllReduce）通信，通信量与模型参数量成正比；Ring AllReduce 通过环形拓扑把单点带宽需求降到 $2\times$ 参数量，是分布式训练的基础设施。

异步 SGD 允许设备不等其他设备，用略旧的参数计算梯度。它消除了同步等待，但引入了延迟梯度带来的偏差：更新的信息越旧，有效步长越难控制，实践中需要更小的步长与稀疏化更新（只传输被修改的坐标）。

通信压缩在网络带宽受限时使用：把梯度量化到低精度（如 1-bit、4-bit）或只传输最大的若干分量（稀疏化）。压缩引入的误差用误差反馈补偿：把本次丢弃或量化的残差保留，累加到下一次传输中。误差反馈使压缩后的序列在期望意义上仍然无偏，避免误差累积改变收敛点。

本地 SGD 与联邦学习

本地 SGD（local SGD）把通信频率降低：每个设备在本地做 $H$ 步梯度更新后，才与其他设备做一次平均。$H=1$ 时就是同步数据并行；$H$ 增大时通信次数按 $1/H$ 下降，代价是各设备在局部数据上走得更远、模型分叉更多，平均后的进展会损失一部分（分叉误差）。总通信量对总计算量的折衷由 $H$ 控制，这一折衷是所有分布式 SGD 变体的核心参数。

联邦学习是本地 SGD 的极端形态：数据分布在用户设备上，任何一条数据都不能离开本地，通信由设备主动发起且可能不可用（设备掉线）。FedAvg 就是每轮选取一部分设备做本地训练、上传参数、服务器加权平均的流程，$H$ 常取几十到几百。数据分布在不同设备间不同（非独立同分布）时，各设备的局部最优方向互相冲突，平均后的模型可能偏离全局最优；FedProx 在本地目标中加入近端项 $\frac{\mu }{2}\parallel \mathbf{w}-{\mathbf{w}}_{\text{global}}{\parallel }^2$ 限制设备偏离当前全局模型，SCAFFOLD 用控制变量（与 SVRG 同一思想）修正各设备局部更新的方向偏差。这两个方法都直接借用了 3.4.4 节与 3.7 节的工具，说明同一个方差缩减工具箱在集中式与分布式场景下同时有效。

3.4.7 本节小结

从精确梯度到实际训练

本节把 3.3 节的梯度法推向实际训练。动量法用梯度历史平滑迭代，重球法在已知谱信息时把条件数依赖降到 $\sqrt{\kappa }$；Nesterov 加速通过外推达到 $O(1/k^2)$（凸）与 $(1-1/\sqrt{\kappa }{)}^k$（强凸），并且在一阶 oracle 模型下被下界证明为最优（相差常数）。随机梯度下降把每步代价降到与样本量无关，速率为 $O(1/\sqrt{k})$（凸）与带噪声地板的 $O(1/K)+\eta L{\sigma }^2$（非凸），批量与步长按线性缩放规则配合。方差缩减用控制变量把 SVRG、SAGA 的收敛恢复到线性，单样本梯度计算次数的复杂度从 $O(n\kappa )$ 降到 $O(n+\kappa )$，数值对比显示相同计算预算下两个数量级的差距。自适应步长（AdaGrad、RMSProp、Adam）在迭代中学习对角缩放，免去了对条件数的先验知识，代价是部分理论保证与最终精度。分布式场景下，本地 SGD 用通信换计算，联邦学习在其上叠加数据不出本地与非独立同分布的约束，近端项与控制变量把 3.4.4 节的工具迁移过来。

一阶方法处理的目标都是光滑的：梯度处处存在且 Lipschitz 连续。下一组方法（近端与分裂算法）处理非光滑目标，它们的最优性条件与收敛分析需要 3.2 节的次微分工具。在进入那里之前，3.5 节先补齐二阶方法：牛顿法、拟牛顿法与信赖域，它们把方向的选择从梯度扩展到曲率估计。

练习题

第 1 题 概念推导

$f$ 为 $m$-强凸、$L$-光滑函数。写出用 Nesterov 加速达到 $ϵ$ 精度所需的迭代次数，与梯度下降对比；说明为什么一阶 oracle 下界意味着不能期待更快的普适算法；并解释加速方法的收益边界：它对哪些问题结构收益有限。

参考答案

迭代次数对比：强凸光滑下，梯度下降的速率为 ${(1-\frac{m}{L})}^k$，达到精度 $ϵ$ 需要

$$k_{\text{GD}}\approx \frac{L}{m}\log \frac{1}{ϵ}=\kappa \log \frac{1}{ϵ}$$

Nesterov 加速（配强凸系数或重启）的速率为 ${(1-\frac{1}{\sqrt{\kappa }})}^k$，需要

$$k_{\text{AGD}}\approx \sqrt{\kappa }\log \frac{1}{ϵ}$$

条件数 $\kappa$ 大时两者相差 $\sqrt{\kappa }$ 倍：$\kappa ={10}^4$ 时是 $100$ 倍。

下界与最优性：Nesterov 下界说明存在凸光滑函数使任何一阶算法满足 $f({\mathbf{x}}_k)-f({\mathbf{x}}^{\ast })\ge \frac{3L\parallel {\mathbf{x}}_0-{\mathbf{x}}^{\ast }{\parallel }^2}{32(k+1{)}^2}$。由于加速法的上界也是 $O(1/k^2)$，两者只差常数，一阶 oracle 模型内的改进空间已经被穷尽：任何算法的迭代次数都不可能低于 $\mathrm{\Omega }(1/\sqrt{ϵ})$ 量级。要更快必须跳出模型，例如访问 Hessian（二阶方法，3.5 节）、利用稀疏或低秩结构（3.7 节）、或在问题有额外结构（强凸的稀疏解、单纯形上的线性优化）时使用专门算法。

加速的收益边界：下界是存在性结论（有一个坏函数），不是普适的悲观结论。对已经良态的问题（$\kappa$ 小、初值与最优值不远），加速带来的常数因子收益有限，还可能因为系数带来的震荡使行为变差；对噪声大的随机问题，加速方法会放大噪声（外推使有效步长增大），此时普通动量的表现反而更稳。判断是否使用加速的经验标准是看条件数与噪声水平：条件数大且梯度较准时收益最大，这也是它主要用于确定性凸优化与近端算法（3.7 节的 FISTA）的原因。

第 2 题 计算推理

某训练任务使用小批量 SGD，固定步长 $\eta =0.01$，当前批量的梯度方差为 ${\sigma }^2=4$，光滑常数 $L=10$。计算噪声地板（梯度平方的期望下界）$\eta L{\sigma }^2$。若要把地板降低两个数量级，给出三种方案并分别计算所需的变化（步长、批量、方差缩减各算一种）；说明三种方案各自的代价。

参考答案

噪声地板：

$$\eta L{\sigma }^2=0.01\times 10\times 4=0.4$$

即 $\frac{1}{K}\sum E\parallel \mathrm{\nabla }f{\parallel }^2$ 的期望下界为 $0.4$，梯度范数的均方根约 $0.63$。

三种方案：

其一，减小步长。地板与 $\eta$ 成正比，把 $\eta$ 从 $0.01$ 降到 ${10}^{-4}$ 使地板降到 $0.004$（降低两个数量级）。代价是每步的下降量按比例缩小，前段收敛变慢：到达同一精度的迭代次数增加约 $100$ 倍。步长不能无限减小：小于 ${ϵ}_{\text{mach}}$ 相关尺度后数值上不再推进。

其二，增大批量。批量梯度方差按批量的反比下降，把批量增大 $100$ 倍使方差从 $4$ 降到 $0.04$，地板随之降到 $0.004$。代价是单步计算量增大 $100$ 倍。需要注意批量与步长的配合：若同时按线性缩放把步长也增大 $100$ 倍以保持前段下降速度，地板中步长与方差的乘积不变，地板回到原位。地板正比于步长与批量梯度方差的乘积，两者都能压低地板，前提是不做相互抵消的调整（做大批量训练时通常保持步长不变或只按 $\sqrt{|B|}$ 缩放，而不是完全按线性缩放）。

其三，方差缩减。SVRG 一类的估计器把方差从 ${\sigma }^2$ 降到与 $\parallel \mathbf{w}-\tilde{\mathbf{w}}{\parallel }^2$ 成正比的量，接近最优解时趋于零，地板消失，收敛恢复为线性。代价是每个外层需要一次全梯度计算（$O(n)$）与额外的内存或存储；在 $n$ 极大或模型规模受限的场景（联邦学习、显存紧张）不适用。

选择建议：训练后期需要高精度时优先方差缩减；批量与步长的组合主要用于控制训练速度而非最终精度；对无法使用方差缩减的大规模场景，用递减步长与学习率调度让后期步长自然变小，效果等价于第一种方案但按调度而非手动。

第 3 题 代码验证

用 3.4.1 与 3.4.2 节的代码框架验证三个结论：其一，重球法在条件数 ${10}^4$ 的二次函数上取最优参数时，距离收缩因子是否等于 $(\sqrt{\kappa }-1)/(\sqrt{\kappa }+1)$；其二，Nesterov 加速在同样的问题上（只用 $L$）达到 ${10}^{-8}$ 需要的步数是多少，与 $O(1/k^2)$ 的保守界相差多少；其三，交换两个坐标的缩放是否改变 Nesterov 的步数，说明这一对称性的含义。给出代码、输出与结论。

参考答案

import numpy as np

m, L = 1.0, 10000.0
Q = np.diag([m, L])
f = lambda x: 0.5 * x @ (Q @ x)

# 重球法：最优参数
eta = 4 / (np.sqrt(L) + np.sqrt(m)) ** 2
beta = ((np.sqrt(L) - np.sqrt(m)) / (np.sqrt(L) + np.sqrt(m))) ** 2
x, x_prev = np.array([1.0, 1.0]), np.array([1.0, 1.0])
dists = []
for k in range(8000):
    dists.append(np.linalg.norm(x))
    x, x_prev = x - eta * (Q @ x) + beta * (x - x_prev), x
dists = np.array(dists)
r_theory = (np.sqrt(L) - np.sqrt(m)) / (np.sqrt(L) + np.sqrt(m))
print(f"重球法：eta = {eta:.8f}，beta = {beta:.6f}")
print(f"  第 200 步局部比值 = {dists[200] / dists[199]:.6f}")
print(f"  窗口平均收缩因子（2000 到 8000 步）= {(dists[7999] / dists[1999]) ** (1 / 6000):.6f}")
print(f"  理论收缩因子 = {r_theory:.6f}，降到 1e-8 的步数 = {int(np.argmax(dists <= 1e-8))}")

# Nesterov：只用 L（梯度在 y 处求值）
def run_nesterov(fun, grad, kmax=200000):
    x, y = np.array([1.0, 1.0]), np.array([1.0, 1.0])
    t = 1.0
    hist = []
    for _ in range(kmax):
        hist.append(fun(x))
        x_new = y - (1 / L) * grad(y)
        t_new = (1 + np.sqrt(1 + 4 * t ** 2)) / 2
        y = x_new + ((t - 1) / t_new) * (x_new - x)
        x, t = x_new, t_new
    return np.array(hist)

h1 = run_nesterov(f, lambda y: Q @ y)                            # 原始坐标：Q = diag(1, 10000)
f2 = lambda x: 0.5 * (10000.0 * x[0] ** 2 + x[1] ** 2)
h2 = run_nesterov(f2, lambda y: np.array([10000.0 * y[0], y[1]]))  # 交换后的谱与一致的梯度
print(f"Nesterov：f 降到 1e-8 的步数 = {int(np.argmax(h1 <= 1e-8))}")
print(f"Nesterov（交换坐标）：f2 降到 1e-8 的步数 = {int(np.argmax(h2 <= 1e-8))}")

输出：

重球法：eta = 0.00039212，beta = 0.960788
  第 200 步局部比值 = 0.985111
  窗口平均收缩因子（2000 到 8000 步）= 0.980425
  理论收缩因子 = 0.980198，降到 1e-8 的步数 = 1315
Nesterov：f 降到 1e-8 的步数 = 699
Nesterov（交换坐标）：f2 降到 1e-8 的步数 = 699

结论：其一，重球法的窗口平均收缩因子 $0.980425$ 与理论值 $0.980198$ 相差 $0.02\mathrm{\%}$，验证了速率公式；但第 $200$ 步的局部比值是 $0.985111$，明显偏大。原因是最优参数下两个特征方向的特征方程都取重根，误差按 $k{r}^k$ 的形式衰减（多出一个线性因子），局部比值按 $1+1/k$ 的速度从上方逼近 $r$。这一细节说明实测的逐步比值与渐近收缩因子在有限步数下可以差出百分之几，比较速率时用窗口平均而不是单步比值。

其二，Nesterov 需要 $699$ 步。按 $O(1/k^2)$ 的界估算：$2L\parallel {\mathbf{x}}_0-{\mathbf{x}}^{\ast }{\parallel }^2/(k+1{)}^2\le {10}^{-8}$ 给出 $k\ge 2\times {10}^6$，比实测大三四个数量级。原因是本题的谱只有两个不同特征值，结构简单，界的最坏情形构造不适配；界给出的是任何凸光滑函数上的保证，而不是这个具体函数的速度。

其三，交换坐标后步数完全不变（同为 $699$）。Nesterov 方法以 $L$ 为步长基准，两个坐标各自的更新因子由曲率决定，交换它们不改变曲率的集合，因此步数对称。这一对称性说明加速方法对坐标的排列不敏感，但对曲率的分布敏感：若把两个方向的曲率差异继续拉大（$\kappa$ 更大），步数将按 $\sqrt{\kappa }$ 增长；加速改善的是对 $\kappa$ 的依赖形式，不消除它。

第 4 题 综合应用

某团队在一个 ${10}^8$ 参数、${10}^9$ 样本的推荐模型上训练。当前方案：单机 8 卡同步数据并行，批量 $8192$，SGD 加动量，学习率固定 $0.1$。训练到后期损失不再下降，验证指标震荡。请分析问题的来源；给出至少三种改进方案并说明各自的原理与代价；若团队计划扩展到 64 卡并把批量增大到 $65536$，给出配套的参数调整与需要注意的风险。

参考答案

问题定位：后期损失不降、验证指标震荡对应噪声地板。用 3.4.3 节的公式，地板为 $\eta L{\sigma }^2/|B|$（按批量归一化后的形式），当前批量 $8192$ 的方差约为单样本方差的 $1/8192$，在 $\eta =0.1$ 下地板仍然可观。验证指标震荡还叠加了固定学习率导致的参数在最优解附近随机游走。判断依据：记录训练损失的移动平均与梯度范数的滑动平均，若梯度范数稳定在非零平台且损失围绕均值波动，即为地板现象；再看地板是否随学习率线性变化（学习率减半后地板也减半）以确认。

三种改进方案：

其一，学习率调度（余弦退火或阶梯衰减）。原理是随训练进程减小步长，让噪声地板按 $\eta$ 线性下降。代价是后期每步进展变小、总迭代数增加；需要重新调参（衰减周期、最小学习率）。

其二，增大批量并配合线性缩放与预热。原理是方差按批量下降，批量翻倍配步长翻倍可以保持下降速度并减少迭代次数。代价是计算资源与通信量上升；风险是超过临界批量后收益消失（可以扫描批量-步长曲线找临界点），以及大学习率导致的初期不稳定（用预热缓解）。

其三，切换优化器或改用方差缩减/自适应方法。原理是用 SVRG 类方法消除噪声地板（代价是每轮全梯度），或改用 Adam 类自适应方法使后期震荡减小（代价是最终精度可能低于精调 SGD）。对 ${10}^9$ 样本的推荐模型，全梯度代价过高，实用性有限；更现实的是后期切换到 Adam 或减小动量的 SGD，并配合解耦权重衰减。

扩展到 64 卡、批量 65536 的配套调整：按线性缩放把学习率从 $0.1$ 提高到 $0.8$（$8$ 倍），并延长预热步数（批量增大后初期不稳定更明显）；检查通信是否成为瓶颈（参数 ${10}^8$、64 卡、每步全归约的通信量为 $8\times {10}^8$ 字节量级，需要 Ring AllReduce 或梯度压缩），必要时改用本地 SGD（每 $H$ 步通信一次）并接受分叉误差；验证批量增大后的收益：在固定总计算量下对比批量 $8192$ 与 $65536$ 的验证指标，确认没有落入饱和区；监控每个 epoch 的有效学习率（学习率 × 步数 / 批量）保持一致，避免因为迭代次数减少导致的总学习量不足。

常见错误

错误 1 · 在固定步长的 SGD 上期待损失降到零

原因：固定步长的随机梯度下降存在噪声地板 $\eta L{\sigma }^2$（${\sigma }^2$ 为批量梯度的方差，批量增大时它按反比下降），梯度范数与损失都无法降到地板以下。把训练停滞解释为模型容量不足或数据问题，会导向错误的改进方向（加参数、换数据）。

解决：先用公式估算地板量级，与观察到的波动幅度对照。需要更低损失时减小步长、增大批量（并同步调整步长）或改用方差缩减。训练脚本中记录梯度范数的滑动平均，它比损失更能反映是否到达地板：梯度范数稳定在非零平台时提高精度只能靠上述手段。

错误 2 · 认为动量系数越大越好

原因：动量系数接近 $1$ 时历史梯度权重过大，方向更新的响应变慢，遇到噪声或非平稳的目标时轨迹会过冲与振荡。重球法的最优参数依赖 $m$ 与 $L$，无脑调大 $\beta$ 不满足这一依赖关系；深度学习中 $\beta =0.9$ 左右的默认值是在稳定性与加速之间的折衷。

解决：把动量系数作为需要验证的超参数：在固定学习率下扫描 $\beta \in \{0.5,0.9,0.95,0.99\}$，观察训练损失与验证指标的稳定性。动量与学习率存在耦合（动量放大有效步长），同时调整两者时用预热与学习率扫描降低耦合带来的噪声。

错误 3 · 把加速方法当作无条件更快的选择

原因：Nesterov 加速的收益依赖条件数与噪声水平。在噪声大的随机场景中，外推会放大梯度噪声，实际表现可能不如普通动量；在条件数已经接近 $1$ 的问题上，加速的常数因子收益有限，甚至因为系数的震荡更差。加速方法的证明依赖精确梯度与 $(m,L)$ 参数，还要求步长匹配。

解决：在确定性凸问题上（或近端算法的光滑部分）优先使用加速；随机场景中把加速与方差缩减配合，或在有重启机制时使用。引入前做对照实验：同样的计算预算下比较加速与普通动量，若收益不足 $10\mathrm{\%}$ 则不值得增加复杂度与参数敏感性。

错误 4 · 把学习率与批量的线性缩放当作精确规则

原因：线性缩放（批量翻倍、学习率翻倍）只在噪声主导的区间近似成立：批量很小时随机梯度的方向噪声大，放大步长会发散；批量很大时（超过临界批量）方差已经被平均掉，放大步长只会带来不稳定而不增加下降量。把规则当作精确公式会在两个端点上出错。

解决：把线性缩放作为起始点而不是终点：先按规则设置，再在批量改变后的头几百步监控是否发散，必要时增加预热步数。用批量扫描确定临界批量（固定总计算量，比较不同批量下的最终损失，损失开始变差的点即临界批量附近），超过它之后不再按比例增大学习率。