优化理论（十）：随机优化与方差缩减

随机梯度下降（SGD）每步只采样单个分量梯度，计算代价远低于全梯度方法——但噪声的代价是什么？能否在保持随机采样优势的同时获得确定性方法的快速收敛？本文从「噪声预算」视角出发，量化这一权衡，并推导解决方案。

确定性梯度下降（full GD）每步计算代价为 $O(n)$ ，但收敛步数为 $O(\kappa \log(1/\epsilon))$ 。随机梯度下降（SGD）每步仅需 $O(1)$ 计算量，但在凸情形下收敛步数为 $O(1/\epsilon^2)$ ，强凸情形下为 $O(\kappa^2 \log(1/\epsilon))$ 。究竟哪种更快，取决于 $n$ 、条件数 $\kappa$ 和精度 $\epsilon$ 。

一类现代算法——方差缩减型 SGD（variance-reduced SGD）——在仅使用随机采样的前提下，达到了与确定性方法相当的收敛速率 $O((n + \kappa) \log(1/\epsilon))$ 。它们填补了关键空白，使得随机方法在有限和问题上严格优于全梯度下降。

本文内容如下：

1. 从「噪声预算」（noise budget）视角推导基础 SGD 的收敛速率；
2. 解释小批量（mini-batching）与学习率衰减（learning rate decay）的作用；
3. 推导 SVRG 算法，并证明其在强凸目标函数上的线性收敛性；
4. 简述 SAGA 与 Katyusha，并介绍催生这些算法的下界结果。

随机梯度下降（SGD）每步只看一个样本的梯度。这显然便宜——但便宜的代价是什么？是不是有办法既享受“每步只采一个样本”的低开销，又拿到全梯度方法那种快收敛？

这是这一篇要回答的问题。我会用“噪声预算”的视角把它讲清楚：每一步的随机梯度都是真梯度加上一团噪声，算法跑得越快，能容忍的噪声就越少。

全梯度下降每步要花 $O(n)$ ，但只需要 $O(\kappa \log(1/\epsilon))$ 步；SGD 每步只要 $O(1)$ ，但凸情形要 $O(1/\epsilon^2)$ 步。哪个划算？看你的 $n$ 、$\kappa$ 、$\epsilon$ 。

方差缩减类算法（SVRG、SAGA、Katyusha）填上了这个空隙：在只用随机采样的前提下做到 $O((n + \kappa) \log(1/\epsilon))$ ，严格优于全梯度下降。本文把这条收敛速率的“升级路径”讲明白。

你将学到什么#

1. SGD 的两类收敛行为：凸情形下的 $O(1/\sqrt{T})$ 速率，以及强凸情形下的 $O(1/T)$ 速率；
2. SGD 的方差控制界，为何步长 $\eta = 1/L$ 过于激进，以及 $\eta_t = 1/(\mu t)$ 这一调度策略的来源；
3. SVRG 算法及其线性收敛性；
4. SAGA、Katyusha，以及下界结果 $\Omega((n + \sqrt{n \kappa}) \log(1/\epsilon))$ ；
5. 实践考量：小批量、动量（momentum），以及 SGD 与方差缩减方法各自适用的场景。

前置知识#

第 02 篇 （光滑性、强凸性）、第 03 篇 （梯度下降与 SGD）。

SGD 框架#

关于随机梯度 $\nabla f_{i_t}(x_t)$ ，有两个基本事实：

• 无偏性（Unbiased）：$\mathbb{E}[\nabla f_{i_t}(x_t) \mid x_t] = \nabla f(x_t)$ ；
• 有界方差（Bounded variance）：通常假设
  $ \mathbb{E}\big[ \|\nabla f_{i_t}(x_t) - \nabla f(x_t)\|_2^2 \mid x_t \big] \leq \sigma^2, $ 其中 $\sigma^2$ 称为梯度方差预算（gradient variance budget）。

这两条假设（无偏性 + 有界方差）构成了 SGD 的公理基础。由此导出的收敛界强度，取决于目标函数 $f$ 所具备的额外结构（如凸性、强凸性、光滑性等）。

凸情形收敛率：$O(1/\sqrt{T})$ #

定理。设 $f$ 是凸函数，且满足上述方差界。取常数步长 $\eta = R / (\sigma \sqrt{T})$ ，并从满足 $\|x_0 - x^\star\|_2 \leq R$ 的初始点 $x_0$ 出发，则经过 $T$ 轮迭代后，有

其中 $\bar x_T = \frac{1}{T} \sum_{t=0}^{T-1} x_t$ 为迭代点的运行平均。

若将 $G^2 + \sigma^2$ 简化为 $\sigma^2$ （或视 $G$ 为噪声的一部分），即得前述形式。$\blacksquare$

该 $O(1/\sqrt{T})$ 速率是经典 SGD 的标准收敛速率。注意它只依赖于方差 $\sigma^2$ ，而与函数的光滑常数 $L$ 或条件数 $\kappa$ 无关。因此，只要步长选取恰当，SGD 对噪声具有鲁棒性，但收敛速度较慢。

强凸情形下的收敛速率：$O(1/T)$ #

定理。假设 $f$ 是 $\mu$ -强凸函数，且满足方差界 $\mathbb{E}[\|\nabla f_i(x) - \nabla f(x)\|_2^2] \leq \sigma^2$ 。取步长 $\eta_t = 2 / (\mu (t + 1))$ ，则经过 $T$ 次迭代后，

其中最后一项源于对梯度模长的界：对 $L$ -光滑且强凸的 $f$ ，有 $\|\nabla f(x_t)\|_2 \leq L \|x_t - x^\star\|_2$ 。当 $\eta_t = 2/(\mu(t+1))$ 足够小时，$L^2$ 项可忽略，通过归纳法即得 $a_t = O(1/(\mu^2 t))$ 。

最优步长按 $1/t$ 衰减——这正是 Robbins–Monro（1951）提出的经典步长调度方案，也是所有现代自适应 SGD 步长策略（如 AdaGrad、Adam）的理论基础。

为何在强凸函数上 SGD 不能使用常数步长？#

若采用常数步长 $\eta_t = \eta$ ，上述递推式存在不动点 $a^\star = \eta \sigma^2 / (2 \mu)$ 。此时迭代点 $x_t$ 并不收敛至最优解 $x^\star$ ，而是收敛到一个以 $x^\star$ 为中心、半径为 $O(\sqrt{\eta \sigma^2 / \mu})$ 的「噪声球」内。若希望将该球半径压缩至 $\epsilon$ ，需设 $\eta = O(\epsilon \mu / \sigma^2)$ ，进而总迭代次数为 $T = O(\sigma^2 / (\epsilon \mu^2))$ —— 其对 $\epsilon$ 的依赖（$1/\epsilon$ ）虽与衰减步长 SGD 相同，但需针对每个目标精度 $\epsilon$ 手动重设 $\eta$ 。

在深度学习中，我们实际上并不追求精确收敛至 $x^\star$ ：泛化误差通常在优化间隙仍较大时便已停止下降；因此常数步长完全可行。这是经典优化理论与深度学习实践之间的一个关键结构性差异。

小批量（Mini-batching）：方差随批大小线性衰减#

则其方差降为 $\sigma^2 / B$ （假设各样本独立）。换言之，小批量线性地降低了噪声预算。

该量随 $B$ 线性增长——因此小批量本身并不节省总计算量！其实际优势在于更大的批次更易于在 GPU 上高效并行化。

线性缩放律（Goyal 等，2017）——「批大小扩大 $k$ 倍，学习率同步扩大 $k$ 倍」——正源于此分析：噪声项 $\eta^2 \sigma^2 / B$ 在 $\eta \propto B$ 时保持恒定，故更大批次允许采用更大步长。但该规律仅在「临界批大小」（critical batch size）以内成立；超过该阈值后，噪声不再是最主要瓶颈（McCandlish 等，2018）。

方差缩减：SVRG#

只要我们仅用单个 $\nabla f_{i_t}$ 作为梯度估计，SGD 的方差项 $\sigma^2$ 就不可避免。方差缩减（variance reduction） 引入额外的控制变量（control variates）——即额外的计算开销，以在极限下将估计方差降至零。

SVRG 算法#

（随机方差缩减梯度法，Stochastic Variance-Reduced Gradient，Johnson & Zhang，2013）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

SVRG（epoch 长度为 m，学习率为 η）：
初始化 w̃_0
for s = 0, 1, 2, ...:                        # 外层 epoch
    g̃_s = ∇f(w̃_s) = (1/n) Σ ∇f_i(w̃_s)        # 在快照点 w̃_s 处计算全梯度
    x_0 = w̃_s
    for t = 0, ..., m-1:                     # 内层迭代
        均匀采样 i_t ∈ {1, ..., n}
        g_t = ∇f_{i_t}(x_t) - ∇f_{i_t}(w̃_s) + g̃_s
        x_{t+1} = x_t - η g_t
    w̃_{s+1} = x_m  （或在该 epoch 中随机选取某个 x_t）

其性质如下：

• 无偏性：$\mathbb{E}[g_t \mid x_t] = \nabla f(x_t) - \nabla f(\tilde w_s) + \nabla f(\tilde w_s) = \nabla f(x_t)$ 。
• 最优解附近方差趋零：当 $\tilde w_s, x_t \to x^\star$ 时，有 $\nabla f_{i_t}(x_t) - \nabla f_{i_t}(\tilde w_s) \to 0$ ，故噪声消失。

正是这一特性赋予了 SVRG 线性收敛速率。

SVRG 收敛性分析#

定理（Johnson–Zhang，2013）：假设每个 $f_i$ 是 $L$ -光滑的，且 $f$ 是 $\mu$ -强凸的。取步长 $\eta = \frac{1}{10 L}$ ，并令 epoch 长度 $m$ 足够大（具体地，$m \geq 100 L / \mu$ ），则 SVRG 几何收敛：

此即共轭光滑性（co-coercivity）引理。将其代入标准 SGD 分析框架（参见第 2 节 ），但将此处所得的 $\sigma^2$ 上界代入，并仔细追踪一个 SVRG epoch 的全过程，即可导出关于 $f(\tilde w_s) - f^\star$ 的收缩不等式。

总计算代价#

对比其他方法：

• 全梯度下降（Full GD）：$O(n \kappa \log(1/\epsilon))$ —— $n$ 与 $\kappa$ 相乘；
• SGD：$O(\kappa^2 / \epsilon)$ —— 对于小 $\epsilon$ ，可能远差于 SVRG；
• SVRG：$O\big((n + \kappa) \log(1/\epsilon)\big)$ —— $n$ 与 $\kappa$ 相加。

当 $n \approx \kappa$ （典型正则化机器学习场景）时，SVRG 比全梯度下降快约 $\kappa$ 倍；相比 SGD，在小 $\epsilon$ 下快约 $\kappa^2 / (\kappa \log(1/\epsilon)) = \kappa / \log(1/\epsilon)$ 倍。

SAGA、Katyusha 与下界#

SAGA（Defazio, Bach & Lacoste-Julien, 2014）与 SVRG 类似，但为每个 $i$ 维护一张表，记录最新计算的 $\nabla f_i$ ，每次迭代仅更新对应条目。它避免了快照开销，但需 $O(nd)$ 额外内存。收敛速率同为 $O\big((n + \kappa) \log(1/\epsilon)\big)$ 。

当 $\kappa \gg n$ 时优于 SVRG。

定理（下界，Woodworth & Srebro, 2016）：任意随机一阶有限和（finite-sum）算法，至少需要 $\Omega\big((n + \sqrt{n \kappa}) \log(1/\epsilon)\big)$ 次梯度计算。

因此，Katyusha 在强凸有限和问题中是最优的。

实践启示#

在深度学习中，朴素 SGD + 动量 + 学习率调度仍普遍优于各类方差缩减方法。其原因尚未完全阐明，主流猜测包括：（a）随机性有助于泛化；（b）损失下降时噪声尺度自然衰减；（c）SGD 的隐式偏差倾向于导向平坦极小值（flat minima）。

总结#

随机优化以每步计算代价的降低为代价，引入了噪声。经典 SGD 的收敛速率（凸函数下为 $O(1/\sqrt{T})$ ，强凸函数下为 $O(1/T)$ ）可直接由“噪声预算”分析得出。方差缩减技术则将 SGD 的单步效率提升至确定性优化的速率量级，其中 Katyusha 算法达到了匹配的理论下界。

第 11 篇文章标志着下一前沿：非凸优化问题——此时全局收敛不可保证，但仍存在局部性质保障（例如：逃离鞍点、收敛至平坦极小值点）。

参考文献#

• Bottou, Curtis & Nocedal, Optimization Methods for Large-Scale Machine Learning, SIAM Review 60, 2018 —— 关于 SGD 及其变体的全面综述。
• Johnson & Zhang, Accelerating Stochastic Gradient Descent using Predictive Variance Reduction, NeurIPS 2013 —— SVRG 原始论文。
• Defazio, Bach & Lacoste-Julien, SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives, NeurIPS 2014 —— SAGA 原始论文。
• Allen-Zhu, Katyusha: The First Direct Acceleration of Stochastic Gradient Methods, JMLR 18, 2017 —— 首个直接加速的方差缩减算法。
• Woodworth & Srebro, Tight Complexity Bounds for Optimizing Composite Objectives, NeurIPS 2016 —— 匹配的复杂度下界分析。