随机优化：同一梯度预算下的完整核验 ​

形式陈述 ​

本单元的终点是一份可重算的优化报告：目标和oracle是什么，何时抽新随机数，输出哪一个点，花了多少次梯度查询，以及结论究竟约束期望目标差、真实梯度还是高概率事件。以下题目既给任务，也给完整核对答案。

核心主线为确定梯度理路梯度下降法Gradient descent method · Euclidean steepest descent method反复沿当前负梯度方向取步以降低可微目标的基础一阶算法。 → 随机oracle与噪声底理路随机梯度下降Stochastic gradient descent · SGD · 随机梯度法在已知历史下用无偏随机梯度更新，推导凸目标期望界与二次噪声底，并按真实梯度查询比较批量和停止保证。 → 递减步长求根理路Robbins–Monro 随机逼近Robbins–Monro stochastic approximation · Robbins-Monro algorithm · 随机逼近求根只观察带噪函数值时逐步寻找向量方程的根，用衰减步长和补偿上鞅证明收敛，并检验稳定性与偏差条件。 → 平均输出理路Polyak–Ruppert 迭代平均Polyak–Ruppert averaging · Ruppert–Polyak averaging · 迭代平均平均带噪递推的相关迭代，在线性模型中证明根号样本量极限，精算常步长平均，并展示不合适的步长与非线性偏差。 → SVRG快照理路随机方差缩减梯度法Stochastic variance reduced gradient · SVRG · 随机方差缩减梯度为可重复访问的有限和使用快照控制变量，证明随机内迭代输出的几何收敛，并逐项核算梯度调用和存储代价。 → SAGA梯度表理路SAGA 梯度表法SAGA · SAGA gradient table method逐项维护历史梯度表，以一次新分量查询形成条件无偏方向，证明表误差与迭代误差共同收缩，并核验更新顺序和存储成本。 → 优化误差的交付理路近似 ERM 与优化误差approximate ERM · optimization error刻画训练目标未被精确最小化时，经验次优量如何进入总体超额风险。。已能独立完成某题的读者，可以跳过对应补课。

按需补课：看不清“给定过去”时读条件期望理路条件期望Conditional expectation以信息分组的加权平均建立条件期望直觉，再连接测度定义、最小均方预测、塔式性质和可计算反例。和滤过理路滤过与适应过程Filtration · Adapted process · Natural filtration以递增 σ-代数表示信息积累，并刻画过程在每一时刻不使用未来信息。；方差交叉项不熟悉时读协方差理路协方差Covariance两个随机变量中心化乘积的期望，衡量线性共同变化。；不清楚凸平均为何成立时读Jensen理路Jensen 不等式Jensen's inequality凸函数作用于平均值不超过函数值的相同加权平均。；想核对失败概率时读Markov理路Markov 不等式Markov's inequality非负随机变量超过阈值的概率由其期望除以阈值控制。和次高斯尺度理路次高斯随机变量Sub-Gaussian random variable · 次高斯尺度 · Subgaussian variance proxy用全实数上的中心化指数矩上界定义次高斯尺度，计算独立加权平均的尾界，并区分方差、尺度代理与条件次高斯假设。。

进阶分支各有独立出口：重排理路随机重排梯度法Random reshuffling · Random reshuffling gradient method · 随机重排每轮重新排列有限和分量再依次更新，区分单步条件偏差与整轮抵消，并精算重排、固定顺序和有放回抽样的误差。负责一轮内依赖；非凸驻点理路随机梯度的非凸驻点保证Nonconvex stochastic gradient stationarity · Randomized stochastic gradient · 非凸随机梯度驻点界在光滑有下界的非凸目标上证明随机迭代的期望梯度平方界，区分驻点与最优，并把验证和高概率声明纳入查询预算。改变输出与误差指标；AdaGrad理路AdaGrad 对角自适应梯度法AdaGrad · Diagonal AdaGrad · 对角自适应梯度法按每个坐标累积梯度平方调整步长，完整推导盒约束下的路径式遗憾界，并通过稀疏序列和条件化检验其随机优化保证。改变坐标尺度并从路径式遗憾进入随机保证。它们不是完成核心七站前必须穿过的额外前置链。

直觉 ​

一次迭代、一条样本、一项分量梯度和一次独立重复实验不是同一种计数。小批量的一轮可能查询四个梯度；SVRG的一步可能查询两次，还先花一整轮算快照；同一轨迹上的24个点也不是24个独立输出。

先固定这份账，再比较偏差和方差，才能判断算法是否真正更有效。报告概率时也一样：期望误差小可以与某些运行明显失败同时存在，必须用选定的概率工具把二者接起来。

例子与边界 ​

任务一：24次查询，四种选择 ​

给定 $f(x)=x^2/2$，$x_0=2$。每次样本梯度为 $x+\xi$，其中 $\xi$ 是独立公平符号 $\pm 1$。总预算固定为24次梯度查询，比较：

• A：步长 $1/4$，24步后返回末点
• B：同样的24步，返回更新后 $x_1,\dots ,x_{24}$ 的算术平均
• C：第 $t$ 次更新使用步长 $1/t$（$t=1,\dots ,24$），返回末点
• D：每轮在同一点平均4个新梯度，步长 $1/4$，做6轮后返回末点

要求给出均值、方差、期望目标差，并说明能否达到期望目标差0.05。

答案令 $r=3/4$。A的均值为 $2r^{24}$，方差 $(1-r^{48})/7$。B的均值为 $(1-r^{24})/4$，方差为

$$\frac{24-6(1-r^{24})+(9/7)(1-r^{48})}{{24}^2}.$$

C首步消掉初值，末点为 $-{24}^{-1}\sum _{j=1}^{24}{\xi }_j$，均值0、方差 $1/24$。D仅走6次，其均值为 $2r^6$，方差 $(1-r^{12})/28$。每种期望目标差均为 $({\text{均值}}^2+\text{方差})/2$。

方法	更新轮数	梯度查询	输出均值	输出方差	期望目标差
A 常步长末点	24	24	0.002006783	0.142856999	0.071430513
B 常步长平均	24	24	0.249749152	0.033492593	0.047933616
C 递减步长末点	24	24	0	1/24	1/48≈0.020833333
D 四项批量末点	6	24	729/2048	2320825/67108864	10823881/134217728≈0.080644198

因此B、C满足所给期望目标差要求，A、D不满足。D每轮噪声方差降为四分之一，却只走了六步，留下较大的初值偏差。B平均减小方差，也保留更多早期偏差。本例C最好，因为步长恰好适配斜率1；这不是它对未知曲率问题普遍优于其他方案的证明。

A的长期期望目标差为 $1/14>0.05$，所以仅延长相同步长的末点运行永远无法达到这个期望阈值。B在线性加性模型中可通过平均持续降低误差；一般非线性目标还应检查平均偏差。

任务二：期望合格，是否意味着95%运行合格 ​

对C，目标差超过0.05等价于 $|\sum _{j=1}^{24}{\xi }_j|>24\sqrt{0.1}$。和只能取偶数，因此失败事件为绝对值至少8。精确概率为

$$\frac{2\sum _{k=0}^8(\genfrac{}{}{0ex}{}{24}{k})}{2^{24}}=\frac{635813}{4194304}\approx 0.151589632.$$

所以尽管期望目标差只有约0.0208，实际通过率约84.84%，并非95%。这个精确二项计算直接反驳了把期望数值当成覆盖声明的做法。

若仍用递减步长方案并预先固定预算 $N$，公平符号是尺度1的次高斯变量，故以至少 $1-\delta$ 的概率有

$$f(x_N)\le \frac{\log \left(2/\delta \right)}{N}.$$

要求 $\delta =0.05$、目标差0.05，充分条件为 $N\ge \lceil \log 40/0.05\rceil =74$。这是充分预算，不是声称74为精确最小值。只用方差与Markov，则由 $Ef(x_N)=1/(2N)$ 得更保守的 $N\ge 200$。

两种声明均用于预先固定的预算。如果每一步查看结果、第一次看起来足够好就停，必须对整个检查过程另给保证；本题没有把固定时刻界升级为任意停止时刻界。

任务三：复用噪声与固定偏差 ​

把噪声改成“开始时抽一次公平符号 $Z$，以后每次都复用它”。C此时从首步起就是 $x_t=-Z$，目标差始终为 $1/2$。各次噪声的边际均值仍为零，但首步后历史已知道 $Z$，下一次条件均值不再为零。

再保持独立噪声，却把oracle改为 $x+\beta +\xi$。C末点为 $-\beta -N^{-1}\sum _j{\xi }_j$，期望目标差变成

$$\frac{{\beta }^2}{2}+\frac{1}{2N}.$$

例如 $\beta =1/2,N=24$，结果为 $7/48\approx 0.145833$。第一种失败来自历史依赖，第二种来自系统性偏差；单纯增加独立查询数只能解决后式第二项。

如果只知道原始无偏梯度的非中心 $p$阶条件矩，$1<p<2$，二阶矩甚至可能不存在。使用SGD页的裁剪方案，$p=3/2,M=R=1,D=2,T=1000$ 时阈值100、步长0.01，距离项、二阶矩项、裁剪偏差项依次为0.05、0.05、0.2，总期望界0.3。这个答案使用有限p阶矩，不能冒称指数尾高概率结论，也不能把裁剪偏差项删去。

任务四：有限和的查询权限和表状态 ​

固定 $f_1(x)=(x-1{)}^2/2$、$f_2(x)=3(x+1{)}^2/2$，所以 $f(x)=x^2+x+1$，$x^{\ast }=-1/2$，目标差 $\mathrm{\Delta }(x)=(x+1/2{)}^2$。请分别给SVRG和SAGA的两步账，再检查漏权抽样。

SVRG取快照0，花2次调用得到快照梯度 $(-1,3)$ 及平均1。步长 $1/12$，两个内步中第二步抽分量2，则 $x_1=-1/12$、$x_2=-7/48$。原始随机输出从 $x_0,x_1$ 中等概率选择，期望目标差为 $61/288$。无缓存实现总调用为 $2+2\cdot 2=6$，这个很短阶段的理论收缩因子为7，没有通过 $\rho <1$ 门槛。

若改用 $\eta =1/30,m=75$，$L=3,\mu =2$ 代入公式得到 $\rho =1/2$；每阶段 $2+150=152$ 次。初始目标差 $1/4$，要让期望目标差不超过 $1/1024$，8阶段足够，总查询1216次。缓存两项快照梯度时变为每阶段77次，总616次，但增加梯度表存储。两份成本不能混写。

SAGA取步长 $1/18$，同样初始化表 $(-1,3)$、均值1，花2次调用。依次抽分量1、2，首步到 $-1/18$；第二步新梯度为 $17/6$，校正方向 $5/6$，到 $-11/108$。更新后表 $(-1,17/6)$、均值 $11/12$，总调用4次。第三步两种可能方向为 $22/27,7/9$，平均 $43/54$ 恰为当前整梯度，方差 $1/2916$。这项检查同时验证了旧表校正、替换顺序与缓存均值不变量。

若SVRG改为以 $p=(3/4,1/4)$ 抽样而遗漏 $1/(n{p}_I)$，在快照0处其方向条件均值为 $3x/2+1$，不是 $2x+1$。它还含快照校正，不只是某个未校正加权损失的梯度。正确重加权能恢复无偏，但方差常数及安全步长仍要重算。

任务五：把整轮重排与同点小批量区分开 ​

取 $f_{\pm }(x)=(x\mp 1{)}^2/2$，$x_0=0,\eta =1/2$，每轮两个分量。每轮新重排的两步合成为 $x_{k+1}=x_k/4\pm 1/4$。两轮后四个值为 $\pm 3/16,\pm 5/16$，等概率，方差 $17/256$。同样四次有放回查询的方差为 $85/256$；一次洗牌后固定复用顺序则只得 $\pm 5/16$，方差 $25/256$。

这里第一步若用了 $+$，到 $1/2$ 后第二个梯度必为 $3/2$，而整梯度为 $1/2$。每轮抵消必须通过整轮递推来证明，不能引用每步条件无偏。把步长改成 $3/2$ 后，两种方法仍稳定，但重排方差与有放回方差之比变为 $9/5$，显示效率还依赖步长。

任务六：非凸和自适应更新换了哪一份保证 ​

对 $f(x)=1-\cos x$，$x=\pi$ 的梯度为零而目标差为2；0与 $2\pi$ 都最优，平均却正好为 $\pi$。因此非凸任务应交付随机迭代的梯度平方界，不能继承凸平均的目标差结论。

在 $L={\sigma }^2={\mathrm{\Delta }}_0=1$ 的一般光滑非凸模型中，$\eta =1/200,T=80000$ 给 $E\Vert \mathrm{\nabla }f(x_J){\Vert }^2\le 0.01$。若另用50000次独立验证、失败概率0.05、半径0.02，观察到验证梯度范数0.07，可给真实梯度范数不超过0.09的95%证书；总查询是130000。该证书仍不证明全局最优。

AdaGrad则通过累积梯度平方改变各坐标步长。用本轮梯度设置分母后，缩放方向未必条件无偏；它的凸保证来自路径式遗憾，再做在线到批转换。100维盒 $[-1,1{]}^{100}$、100轮全为 $e_1$、平滑常数0.001时，所给对角界约28.56，普通OGD已知预算界为200；若各轮轮流触发不同坐标，对角界反而约282.84。请把这个差别解释成累计坐标能量分布，不能只说“每轮稀疏所以一定更好”。

推论与应用 ​

最后的交付检查 ​

一份合格报告应能回答下面六个问题。

1. 随机性来自新总体样本、固定数据的索引，还是算法的输出抽签？是否在本轮查询前已经选定当前点？
2. 方差界控制整个梯度、中心化噪声，还是裁剪后的二阶矩？有没有剩余偏差？
3. 实際输出是末点、更新前平均、更新后平均、随机内迭代，还是轮末点？
4. 初始化、快照、每步双点查询、热身和独立验证是否全部计费？
5. 保证是期望、渐近分布、固定时刻高概率，还是允许反复检查的过程保证？
6. 优化目标是经验风险还是总体风险，是否还需单独的泛化分析？

例如固定训练集上的随机优化器若以失败概率 ${\delta }_{\mathrm{o}\mathrm{p}\mathrm{t}}$ 给出经验目标差 ${\epsilon }_{\mathrm{o}\mathrm{p}\mathrm{t}}$，再与失败概率 ${\delta }_{\mathrm{g}\mathrm{e}\mathrm{n}}$ 的统一泛化事件结合，近似ERM理路近似 ERM 与优化误差approximate ERM · optimization error刻画训练目标未被精确最小化时，经验次优量如何进入总体超额风险。给超额风险至多 $2u+{\epsilon }_{\mathrm{o}\mathrm{p}\mathrm{t}}$，总失败概率至多两者之和。若目前只有期望优化差，就先完成合法的概率转换；把期望值直接放进高概率事件会丢失报告最重要的含义。

非欧氏与复合任务可继续到随机几何终点：执行熵正则更新、优化分量采样包络，或按需完成重尾95%预算和8次近端的加速批量计划。这些任务保留各自输出与矩条件，不改变本页24次查询比较。

参考资料 ​

• 随机梯度下降理路随机梯度下降Stochastic gradient descent · SGD · 随机梯度法在已知历史下用无偏随机梯度更新，推导凸目标期望界与二次噪声底，并按真实梯度查询比较批量和停止保证。及本页各wiki链接提供逐步证明、oracle条件和来源
• Sébastien Bubeck，Convex Optimization: Algorithms and Complexity，2015，Chapter 6
• Rie Johnson、Tong Zhang，SVRG原论文，2013，Figure 1、Theorem 1
• Aaron Defazio等，SAGA原论文，2014；John Duchi等，AdaGrad原论文，2011