0x00 Preface

本篇分析 mini-batch SGD，沿用 Part 11 的欧氏范数和随机梯度定义，并与 Part 22 的确定性梯度下降比较。

令 $\mathcal F_t$ 为第 $t$ 轮采样前的历史，采用固定步长更新 $w_{t+1}=w_t-\eta g_t$。$g_t$ 是 $b$ 个新样本梯度的平均，假设

$$ \mathbb E[g_t\mid\mathcal F_t]=\nabla f(w_t),\qquad \mathbb E[\|g_t-\nabla f(w_t)\|^2\mid\mathcal F_t]\le\frac{\sigma^2}{b}. $$

这里 $\sigma^2$ 是单样本噪声的方差上界；$1/b$ 缩减依赖 batch 内噪声条件独立或交叉协方差为零。

One-step Descent

$L$-光滑性给出

$$ f(w_{t+1})\le f(w_t)-\eta\langle\nabla f(w_t),g_t\rangle +\frac{L\eta^2}{2}\|g_t\|^2. $$

先在给定 $\mathcal F_t$ 的条件下取期望，此时 $w_t$ 固定：

$$ \mathbb E[f(w_{t+1})\mid\mathcal F_t] \le f(w_t)-\eta\left(1-\frac{L\eta}{2}\right)\|\nabla f(w_t)\|^2 +\frac{L\eta^2\sigma^2}{2b}. $$

再对历史取期望。若 $0<\eta\le1/L$，得到后续共用的递推：

$$ \mathbb E[f(w_{t+1})]\le\mathbb E[f(w_t)] -\frac\eta2\mathbb E\|\nabla f(w_t)\|^2 +\frac{L\eta^2\sigma^2}{2b}. $$

不能在无条件期望的公式中把随机的 $f(w_t)$ 或梯度当作确定量。

0x01 Smooth and Strongly Convex with Mini-batch SGD

defination

若 $f$ 为 $L$-光滑、$\mu$-强凸且最优解存在，定义
$$ \mathcal E_t=\mathbb E[f(w_t)]-f^*,\quad q=1-\eta\mu,\quad C_b=\frac{\eta L\sigma^2}{2\mu b}. $$
对于 $0<\eta\le1/L$，有
$$ \mathcal E_T\le q^T\mathcal E_0+C_b(1-q^T) =C_b+q^T(\mathcal E_0-C_b). $$

证明：由 PL 条件 $\Vert\nabla f(w_t)\Vert^2\ge2\mu(f(w_t)-f^{\ast})$，一步下降变为

$$ \mathcal E_{t+1}\le(1-\eta\mu)\mathcal E_t+\frac{L\eta^2\sigma^2}{2b}. $$

因为 $0\le q<1$，展开递推并对几何级数求和，得到

$$ \mathcal E_T\le q^T\mathcal E_0 +\frac{L\eta^2\sigma^2}{2b}\sum_{s=0}^{T-1}q^s =q^T\mathcal E_0+C_b(1-q^T). $$

What Does the Bound Guarantee?

固定步长下，界中的瞬态项按几何速度减小，但通常只保证 $\limsup_T\mathcal E_T\le C_b$。这是误差的上界，不是算法必然达到的实际误差，也不是到精确最优解的线性收敛保证。

若 $0<q<1$ 且 $\mathcal E_0>\epsilon>C_b$，足够的迭代次数为

$$ T\ge\left\lceil \frac{\log((\mathcal E_0-C_b)/(\epsilon-C_b))}{-\log q} \right\rceil. $$

如果 $\epsilon\le C_b$，这个上界不能保证达到目标。可以减小步长、增大 batch，或使用有适用条件的递减步长方案。$\sigma^2=0$ 时恢复确定性 GD 的结果；$q=0$ 时直接使用递推，不计算 $\log0$。

0x02 Smooth Non-convex with Mini-batch SGD

defination

假设 $f$ 为 $L$-光滑且有有限下界 $f_{\inf}$，随机梯度满足上述条件。对 $0<\eta\le1/L$、$T\ge1$，
$$ \frac1T\sum_{t=0}^{T-1}\mathbb E\|\nabla f(w_t)\|^2 \le\frac{2(f(w_0)-f_{\inf})}{\eta T}+\frac{L\eta\sigma^2}{b}, $$
这里假设起点 $w_0$ 确定；随机起点时，将 $f(w_0)$ 替换为其期望。

证明：对一步下降从 $t=0$ 到 $T-1$ 累加，得到

$$ \frac\eta2\sum_{t=0}^{T-1}\mathbb E\|\nabla f(w_t)\|^2 \le f(w_0)-\mathbb E[f(w_T)]+\frac{TL\eta^2\sigma^2}{2b}. $$

用 $f(w_T)\ge f_{\inf}$，再除以 $\eta T/2$ 即得结论。这个求和从 $w_0$ 开始，因此望远镜端点是 $f(w_0)$ 和 $f(w_T)$。

Step Size and Output

如果 $R$ 独立且均匀分布在 $\lbrace 0,\ldots,T-1\rbrace$，随机输出 $w_R$ 的期望梯度平方等于上述平均值。该结论不能直接改成最后一点 $w_T$ 的保证，也不保证达到全局最优。

记 $A=f(w_0)-f_{\inf}>0$。当 $\sigma^2>0$ 时，为给定运行长度 $T$ 选择

$$ \eta=\min\left\{\frac1L,\sqrt{\frac{2Ab}{L\sigma^2T}}\right\}. $$

当第二项不超过 $1/L$ 时，平均梯度平方的界为

$$ 2\sqrt{\frac{2AL\sigma^2}{bT}}. $$

这是随预定运行长度选择的固定步长，不是每一步都使用 $T$ 替换当前索引。它显示在相应范围内的 $O(1/\sqrt{bT})$ 行为；步长上限限制了这种缩放。没有噪声时，取 $\eta=1/L$，得到 $2LA/T$。

Reference

Sources: 3 4.

  1. Part 1 ↩︎

  2. Part 2 ↩︎

  3. Bottou, L., Curtis, F. E. and Nocedal, J., Optimization Methods for Large-Scale Machine Learning, Section 4, especially Theorems 4.6 and 4.8. ↩︎

  4. Joshi, G., Optimization Algorithms for Distributed Machine Learning, Springer. ↩︎