随机梯度下降 | Codeboy's Blog

形式陈述

面对最小化问题 $\min_{x\in C}f(x)$ ，有时一次只能读取一条样本的梯度。随机梯度下降把这份廉价、有波动的方向用于更新。设 $C\subseteq\mathbb R^d$ 非空闭凸， $f$ 在其邻域可微，初值 $x_0\in C$ ，预算为整数 $T\ge1$ 。第 $t$ 步开始前的全部信息记为 $\mathcal F_t$ ；当前点 $x_t$ 已由这份历史决定。给定步长 $\eta_t>0$ ，调用随机梯度查询器（oracle）获得 $g_t$ ，再计算

x_{t+1}=P_C(x_t-\eta_t g_t),\qquad t=0,\ldots,T-1.

$P_C$ 是欧氏最近点投影，其存在唯一性见闭凸集投影定理；无约束时它就是恒等映射。输入还包括采样规则、随机源和输出规则。常见输出是末点 $x_T$ ，或更新前点的平均 $\bar x_T=T^{-1}\sum_{t=0}^{T-1}x_t$ ；下面的定理会指明使用哪一个。

无偏性必须相对于已经发生的事

本页的无偏接口是

E[g_t\mid\mathcal F_t]=\nabla f(x_t).\tag{1}

这里用条件期望冻结过去，再平均本次新随机性。 $\nabla f$ 是目标的梯度。各轮 $g_t$ 通常相关，因为后一个查询点由前面的结果决定；式(1)并未要求整列梯度独立。步长也应在本轮查询前确定，不能看完 $g_t$ 再挑一个有利方向并仍沿用原分析。

两个常见实现需要不同的访问权限。

新样本流： $f(x)=E\ell(x,Z)$ ，每轮抽取独立于历史的 $Z_{t+1}$ ，返回 $\nabla_x\ell(x_t,Z_{t+1})$ 。还须核实梯度与期望可以交换，例如在每个查询点的邻域有可积的梯度上界；仅写成期望目标不自动得到式(1)
固定有限和： $f(x)=n^{-1}\sum_{i=1}^n f_i(x)$ ，数据先固定；每轮独立均匀抽取 $I_t\in\{1,\ldots,n\}$ ，返回 $\nabla f_{I_t}(x_t)$ 。这里的概率来自算法抽样，数据本身不必IID

每次分量或样本梯度求值记一次查询。单样本运行 $T$ 步耗 $T$ 次查询；显式向量更新和流式平均另需 $O(Td)$ 算术、 $O(d)$ 状态，投影、采样和模型反向传播的代价分别计入。oracle返回非有限值、投影求解失败或投影误差超出预设容差时，应停止并报告失败，不能继续声称下述精确递推保证。预算耗尽时应返回所约定的点、已用查询数与“预算结束”状态；除非另有证书，不把这个状态改写成“已达到容差”。

一个可直接复算的凸期望界

进一步假设 $f$ 凸、存在极小点 $x^*\in C$ ， $x_0$ 固定且 $\|x_0-x^*\|\le R$ ，并且

E[\|g_t\|^2\mid\mathcal F_t]\le G^2

对每步成立，其中 $R,G>0$ 为已知常数。取固定步长 $\eta>0$ ，输出更新前平均 $\bar x_T$ ，则

E[f(\bar x_T)-f(x^*)]\le \frac{R^2}{2\eta T}+\frac{\eta G^2}{2}.\tag{2}

证明从投影不扩张开始：

\|x_{t+1}-x^*\|^2\le\|x_t-x^*\|^2-2\eta\langle g_t,x_t-x^*\rangle+\eta^2\|g_t\|^2.

冻结历史后，式(1)把交叉项换成 $\langle\nabla f(x_t),x_t-x^*\rangle$ ；凸性又使它至少为 $f(x_t)-f(x^*)$ 。取全期望并把 $T$ 步相加，中间距离消去，得到平均目标差的上界。最后使用Jensen 不等式，把目标值的平均换成平均点的目标值，即得式(2)。有界条件二阶矩同时控制迭代距离的可积性，故这些期望运算有意义。

取 $\eta=R/(G\sqrt T)$ ，两项平衡为 $RG/\sqrt T$ 。要保证期望目标差至多 $\varepsilon>0$ ，充分预算为 $T\ge\lceil R^2G^2/\varepsilon^2\rceil$ 。它需要先知道预算；它既不是每条轨迹的确定界，也没有声称末点同样满足这个常数。

距离势函数与在线梯度下降共用同一代数机制。区别在于本页将固定目标的随机oracle条件化；在线方法逐轮比较已经揭示的不同损失。新样本IID模型还可通过Online-to-Batch转换得到风险保证，但重复抽取固定训练集只是在优化经验目标。

直觉

精确梯度把你拉向谷底，随机误差会不断把你推开。距离远时，前者占优势；走到谷底附近时，真梯度变小，噪声却可能照旧。因此大步长能较快消除初值影响，也可能留下较大的长期波动。

常步长二次递推中，初值误差衰减而新噪声不断累积，末点期望目标差趋向正噪声底 — 末点的误差由初值与噪声两部分组成

确定梯度下降在合适光滑条件和步长下逐步下降；随机梯度即使条件无偏，一条路径的目标值仍可能上升。平均是一种输出选择，减小步长是一种更新选择，小批量是一种查询选择；三者改变不同的误差项，不能只看迭代次数就判断哪一种更省。

例子与边界

带噪二次模型的精确噪声底

取 $f(x)=\lambda x^2/2$ ， $\lambda>0$ ，oracle 为 $g_t=\lambda x_t+\xi_{t+1}$ ；噪声独立同分布，均值0、方差 $\sigma^2$ ，初值固定。常步长 $0<\eta<2/\lambda$ 下令 $r=1-\eta\lambda$ ，则

x_T=r^Tx_0-\eta\sum_{j=1}^T r^{T-j}\xi_j.

独立性消掉交叉项，所以

Ex_T=r^Tx_0,\qquad \operatorname{Var}(x_T)=\eta^2\sigma^2\frac{1-r^{2T}}{1-r^2},

E[f(x_T)-f(0)] =\frac\lambda2r^{2T}x_0^2+ \frac{\eta\sigma^2}{2(2-\eta\lambda)}(1-r^{2T}).\tag{3}

因此末点期望目标差的极限为 $\eta\sigma^2/[2(2-\eta\lambda)]$ 。这是精确值，不是松上界；只要 $\sigma>0$ 、步长固定，增加轮数不会把它压到零。

例如 $\lambda=1,x_0=2,\eta=1/4,\sigma^2=1$ ，有 $r=3/4$ ，于是

E f(x_T)=\frac1{14}+\frac{27}{14}(9/16)^T.

两步后的均值为 $9/8$ 、方差 $25/256$ 、二阶矩 $349/256$ ，期望目标值 $349/512$ 。如果这两次噪声恰为 $(1,-1)$ ，实际轨迹却是 $2\to5/4\to19/16$ ；一次实现值与总体期望承担不同的描述任务。

取 $\eta=2/\lambda$ 时， $r=-1$ ，有噪声时方差每步增加 $\eta^2\sigma^2$ ；更大的步长还会放大初值。因此稳定区间的端点也不能纳入式(3)的有限噪声底结论。

小批量：先固定同一个查询点

在同一个 $x_t$ 处取 $b$ 个条件独立、条件无偏梯度再平均。如果每个噪声条件二阶矩至多 $\sigma^2$ ，批平均噪声的条件二阶矩至多 $\sigma^2/b$ 。这只缩小噪声项；完整梯度二阶矩是

E[\|\bar g_t\|^2\mid\mathcal F_t] =\|\nabla f(x_t)\|^2+E[\|\bar g_t-\nabla f(x_t)\|^2\mid\mathcal F_t],

所以不能把式(2)中的整个 $G^2$ 无条件除以 $b$ 。

对固定向量 $a_1,\ldots,a_n$ ，记 $\bar a=n^{-1}\sum_i a_i$ 、 $v=n^{-1}\sum_i\|a_i-\bar a\|^2$ 。有放回独立抽 $b$ 项的均值方差为 $v/b$ 。若均匀无放回抽一个大小 $b\le n$ 的子集，且 $n>1$ ，则

E\|\widehat a-\bar a\|^2=\frac{n-b}{b(n-1)}v.\tag{4}

证明只需展开均值平方：每项中心化平方期望为 $v$ ，两项不同抽取的内积期望为 $-v/(n-1)$ ，因为所有不同索引内积之和等于 $-\sum_i\|a_i-\bar a\|^2$ 。相加便得有限总体修正； $n=b=1$ 时直接为零。

例如四个标量梯度为 $(-1,1,3,5)$ ，均值2、 $v=5$ ， $b=2$ 。有放回方差 $5/2$ ，无放回方差 $5/3$ 。若抽一项后复制两次，方差仍为5：复制并未产生新信息。逐个样本更新并改变 $x$ 的随机重排也不满足“固定同一个查询点”的推导。

批量 $b$ 、轮数 $T$ 消耗 $N=bT$ 次梯度查询。把式(3)的 $\sigma^2$ 换成 $\sigma^2/b$ ，仍需同时把轮数换成 $N/b$ ；噪声底降低的代价，是同预算下初值衰减的轮数更少。并行设备可能缩短墙钟时间，但这需要另报硬件与吞吐量。

无偏如何真的失效

边际均值零还不够。例如只抽一次公平符号 $Z$ ，然后每轮都令 $\xi_t=Z$ 。每项单独都有均值零，但从 $x_0=0$ 做首步后 $x_1=-\eta Z$ 已揭示该符号，下一步有 $E[\xi_2\mid\mathcal F_1]=Z$ ；平方递推中的噪声交叉项不能再消掉。新鲜随机性或真正的条件均值假设在这里承担实质工作。

若 $E[g_t\mid\mathcal F_t]=\nabla f(x_t)+b_t$ ，假设 $C$ 直径至多 $D$ 、 $\|b_t\|\le\beta_t$ ，其中 $\beta_t$ 为确定上界，而总二阶矩仍不超过 $G^2$ ，重复式(2)的证明得到

E[f(\bar x_T)-f(x^*)] \le\frac{R^2}{2\eta T}+\frac{\eta G^2}2+ \frac D T\sum_{t=0}^{T-1}\beta_t.\tag{5}

增加样本只压低随机波动，不自动压低最后一项。例如 $g=x+\beta+\xi$ 的二次模型会围绕 $-\beta$ 而不是0波动；均值偏移给原目标留下 $\beta^2/2$ 的误差。

裁剪也能引入偏差。在某一点，未裁剪梯度以概率 $3/4$ 取 $-1$ 、以概率 $1/4$ 取3，其均值为0；裁到 $[-1,1]$ 后均值为 $-1/2$ 。DP-SGD需要逐样本裁剪来限制隐私灵敏度，随后加均值零的噪声也不会恢复被裁掉的均值。隐私核算与本页的优化保证须分别检查。

只有p阶矩时，裁剪要同时付偏差与方差

还可以从式(5)得到一个简单的重尾版本。令 $1<p\le2$ ，原始oracle $G_t$ 条件无偏，并假设的是原始梯度的非中心矩 $E[\|G_t\|^p\mid\mathcal F_t]\le M^p$ ， $M>0$ 。这比只限制噪声的中心矩更强，要逐点核实。将它裁成

g_t=G_t\min\{1,\tau/\|G_t\|\},

零向量规定保持为零，阈值 $\tau>0$ 。逐点使用 $r\mathbf1_{r>\tau}\le r^p/\tau^{p-1}$ 与 $\min(r,\tau)^2\le\tau^{2-p}r^p$ ，便有

\|E[g_t-G_t\mid\mathcal F_t]\|\le\frac{M^p}{\tau^{p-1}},\qquad E[\|g_t\|^2\mid\mathcal F_t]\le M^p\tau^{2-p}.

在直径 $D$ 的闭凸集上，式(5)因此变成

E[f(\bar x_T)-f(x^*)]\le \frac{R^2}{2\eta T}+\frac{\eta M^p\tau^{2-p}}2+ \frac{DM^p}{\tau^{p-1}}.

固定预算后取 $\tau=MT^{1/p}$ 、 $\eta=R/(MT^{1/p})$ ，得到 $(R+D)M T^{-(p-1)/p}$ 。例如 $p=3/2,M=R=1,D=2,T=1000$ ，阈值100、步长0.01，三项分别为0.05、0.05、0.2，总上界0.3。原始二阶矩此时可能不存在，裁剪使实际更新有可控二阶矩，同时必须保留非零偏差项。

这一小节提供固定预算期望界；更精细的重尾高概率算法还需要相应集中分析和阈值方案。它与DP-SGD为了控制每条记录隐私灵敏度而裁剪的用途不同，不能从阈值有限直接推断已有隐私或置信保证。

推论与应用

停止时到底承诺了什么

若某个非负目标差 $Z_T$ 满足 $EZ_T\le B_T$ ，Markov不等式给 $P(Z_T>\varepsilon)\le B_T/\varepsilon$ 。要把失败概率压到 $\delta$ ，充分条件是 $B_T\le\delta\varepsilon$ ，不是 $B_T\le\varepsilon$ 。例如式(2)平衡后，这条朴素转换要求 $T\ge R^2G^2/(\delta^2\varepsilon^2)$ 。它保守，却确实是一个有限样本高概率声明。

二次模型若还有条件次高斯噪声，便能利用更多信息。具体要求对所有实数 $u$ 有 $E[e^{u\xi_j}\mid\mathcal F_{j-1}]\le e^{u^2s^2/2}$ 。逐次条件化可知式(3)中的加权噪声具有次高斯平方尺度

v_T=\eta^2s^2\sum_{j=0}^{T-1}r^{2j}.

所以对预先固定的 $T$ ，以至少 $1-\delta$ 的概率有

|x_T|\le |r|^T|x_0|+\sqrt{2v_T\log(2/\delta)}.\tag{6}

取右侧平方再乘 $\lambda/2$ ，得到目标差的高概率上界。只知道噪声方差有限时，不能使用这个指数尾式。

一个噪声梯度碰巧等于零不能认证停止。例如真梯度为1、噪声为公平 $\pm1$ ，一次返回零的概率为 $1/2$ 。若要在训练后检验某个随机候选，应冻结候选，再花预算抽独立验证梯度并给其均值置信半径；若反复挑时间查看，还需同时有效的界或事先分配失败概率。完整预算核算见单元终点。

选择下一条路线

希望末点随时间真正逼近根，可继续读Robbins–Monro随机逼近；希望利用已有迭代减小输出波动，可读迭代平均。固定有限和且能重访同一分量时，SVRG用快照梯度改变噪声本身。若目标非凸，输出和误差对象应转到随机梯度的驻点保证，而不是把凸平均的目标差结论直接延用。

若原始条件 $p$ 阶矩与有界域信息已经有效，裁剪镜像的高概率保证分别控制裁剪平方和与方向噪声，用两份 Freedman 预算补足本页期望版本；中心矩和无界域局部化仍需不同条件。固定有限和则可进入非均匀采样预算，验证梯度包络、概率下限及每个分量的实际费用。

参考资料

Sébastien Bubeck，Convex Optimization: Algorithms and Complexity，2015，§6.1–6.3：随机oracle、随机镜像下降、批量与有限和方法。本文欧氏界、二次递推与采样算例均逐项推导
Léon Bottou、Frank E. Curtis、Jorge Nocedal，Optimization Methods for Large-Scale Machine Learning，2018，§4：随机梯度的噪声、步长和工作量
Eduard Gorbunov、Marina Danilova、Alexander Gasnikov，Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping，NeurIPS 2020，§1.1–1.2及§3，有限方差重尾与裁剪SGD的背景；本页非中心p阶矩期望界由正文逐点不等式独立推导，不借用该文加速高概率结论

形式陈述 ​

无偏性必须相对于已经发生的事 ​

一个可直接复算的凸期望界 ​

带噪二次模型的精确噪声底 ​

小批量：先固定同一个查询点 ​

无偏如何真的失效 ​

只有p阶矩时，裁剪要同时付偏差与方差 ​

停止时到底承诺了什么 ​

选择下一条路线 ​

反向链接