随机方差缩减梯度法

形式陈述

固定有限和目标

f(x)=\frac1n\sum_{i=1}^n f_i(x),\qquad x\in\mathbb R^d,\ n\ge1.

SVRG要求可按索引 $i$ 在任意查询点精确获得 $\nabla f_i(x)$ ，并能重新访问同一个分量。仅能获得一个新鲜样本且随后丢弃的流式oracle，不自动提供这种权限。每次分量梯度求值计一次查询；整梯度则要 $n$ 次。

第 $s$ 个阶段以快照 $\widetilde x_{s-1}$ 开始。下面固定采用原始分析中的随机内迭代输出方式：

求 $\widetilde g=n^{-1}\sum_i\nabla f_i(\widetilde x_{s-1})$ ，设置 $x_0=\widetilde x_{s-1}$
对 $t=0,\ldots,m-1$ ，独立于阶段历史均匀抽 $I_t\in\{1,\ldots,n\}$ ，计算

v_t=\nabla f_{I_t}(x_t)-\nabla f_{I_t}(\widetilde x_{s-1})+\widetilde g, \qquad x_{t+1}=x_t-\eta v_t

独立均匀抽 $J_s\in\{0,\ldots,m-1\}$ ，令 $\widetilde x_s=x_{J_s}$ 。运行预定 $S$ 个阶段后输出 $\widetilde x_S$

$m,S\ge1$ 、 $\eta>0$ 与初始快照 $\widetilde x_0$ 在运行前固定。两个分量梯度必须使用同一个 $I_t$ ，并冻结快照和其整梯度直到本阶段结束。均匀输出不包括 $x_m$ ；可以预先抽 $J_s$ ，运行中保存对应点，无需保存整条轨迹。

同一个索引使差分真的变小

给定阶段历史，当前点和快照已经确定，因此

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

它满足SGD的条件无偏接口。把 $\nabla f_{I_t}(\widetilde x)$ 当作控制量，其精确均值 $\widetilde g$ 已经算出，这正是控制变量在向量梯度中的应用。

如果 $x_t=\widetilde x$ ，两个同索引分量逐点抵消， $v_t$ 恰好等于整梯度，方差为零；若两项分别抽独立索引，就失去了这条抵消性质。独立索引版本仍可能无偏，但不是这里的低方差估计器。

一阶段的可用收缩因子

假定每个 $f_i$ 都凸、在全空间有 $L$ -Lipschitz梯度， $L>0$ ，平均函数 $f$ 为$\mu$-强凸， $\mu>0$ 。令 $x^*$ 为其唯一极小点， $\Delta(x)=f(x)-f(x^*)$ 。若 $0<\eta<1/(2L)$ ，并选择 $m$ 使

\rho=\frac1{\mu\eta(1-2L\eta)m} +\frac{2L\eta}{1-2L\eta}<1,\tag{2}

则上述随机输出满足

E\Delta(\widetilde x_S)\le\rho^S\Delta(\widetilde x_0).\tag{3}

例如 $\eta=1/(10L)$ ， $m\ge\lceil50L/\mu\rceil$ 给 $\rho\le1/2$ 。条件只要求平均函数强凸，各分量可以仅凸。

直觉

普通SGD在最优点的分量梯度仍可能互相抵消：平均为零，每一项却不为零，所以随机抽一项仍会抖动。SVRG把快照时看到的那部分分量差异减掉，再补回准确的平均方向。随着当前点和快照都靠近解，剩余差分越来越小，噪声不再保持固定尺度。

快照整梯度由n次调用得到，每个内步用同一分量在当前点和快照点各查询一次，阶段末独立随机选取输出 — 快照与同索引双点查询

这项改善需要先支付整梯度费用。阶段太短时，频繁刷新快照可能比直接SGD更贵；阶段太长时，当前点与快照相距较远，差分噪声可能增大。式(2)给出一个可以核验的折中，而不是把“每步只抽一项”当成全部成本。

例子与边界

从光滑分量到方差随目标差下降

对每个分量定义

q_i(x)=f_i(x)-f_i(x^*)-\langle\nabla f_i(x^*),x-x^*\rangle.

凸性给 $q_i\ge0$ 、 $q_i(x^*)=0$ 。对 $q_i$ 使用下降引理，在 $x-\nabla q_i(x)/L$ 处仍非负，故

\|\nabla f_i(x)-\nabla f_i(x^*)\|^2\le2Lq_i(x).

对 $i$ 平均时， $\nabla f(x^*)=0$ 使线性项消失，于是

\frac1n\sum_i\|\nabla f_i(x)-\nabla f_i(x^*)\|^2\le2L\Delta(x).\tag{4}

写 $a_i(x)=\nabla f_i(x)-\nabla f_i(x^*)$ 。SVRG方向可写为 $a_I(x)-[a_I(\widetilde x)-Ea_I(\widetilde x)]$ 。平方范数的两项上界及中心化不增二阶矩给

E[\|v_t\|^2\mid\mathcal F_t] \le4L[\Delta(x_t)+\Delta(\widetilde x)].\tag{5}

这是关键新信息：右侧随两点接近解而消失。它比一个永远不变的 $G^2$ 噪声预算更适合有限和。

再展开到解的距离，利用式(1)、凸性及式(5)：

E[\|x_{t+1}-x^*\|^2\mid\mathcal F_t] \le\|x_t-x^*\|^2-2\eta(1-2L\eta)\Delta(x_t) +4L\eta^2\Delta(\widetilde x).

从0加到 $m-1$ ，丢掉末点的非负平方距离。由于随机输出的条件平均目标差等于这 $m$ 项的平均，再用强凸给 $\|\widetilde x-x^*\|^2\le2\Delta(\widetilde x)/\mu$ ，得到

2\eta(1-2L\eta)mE\Delta(\widetilde x_s) \le[2/\mu+4Lm\eta^2]E\Delta(\widetilde x_{s-1}).

除以左侧系数就是式(2)，跨阶段递推得到式(3)。这里的平均目标差来自随机输出，不是声称最后一个内迭代满足同一证明。

两分量模型的完整调用账

取 $f_1(x)=(x-1)^2/2$ 、 $f_2(x)=3(x+1)^2/2$ 。平均为 $f(x)=x^2+x+1$ ，最优点 $x^*=-1/2$ ， $\Delta(x)=(x+1/2)^2$ ，可取 $L=3,\mu=2$ 。

快照为0，两个快照梯度为 $(-1,3)$ ，整梯度为1。于是校正方向在分量1和2下分别为 $x+1$ 、 $3x+1$ 。取 $\eta=1/12,m=2$ ，首步无论抽谁都得到 $x_1=-1/12$ ；若第二步抽分量2，则 $v_1=3/4$ ， $x_2=-7/48$ 。

在 $x_1$ ，两种校正方向为 $11/12,3/4$ ，均值 $5/6$ 、方差 $1/144$ 。普通分量梯度却是 $-13/12,11/4$ ，均值仍为 $5/6$ ，方差 $529/144$ 。同一均值并不意味着同一噪声。

随机输出从 $x_0=0,x_1=-1/12$ 中等概率选择，其期望目标差为

\tfrac12(1/4+25/144)=61/288.

基线实现支付2次快照梯度及4次内步梯度，共6次查询；这个演示用很短阶段，式(2)给 $\rho=7>1$ ，所以它不满足几何收缩参数条件。若要应用式(3)，可改用 $\eta=1/30,m=75$ ，此时 $\rho=1/2$ ，每阶段152次查询。算法能运行与这组定理常数合格是两个可分别检查的问题。

哪些改变需要重做分析

若把精确快照梯度换成 $\widetilde g+e$ ，本阶段条件均值变为 $\nabla f(x_t)+e$ 。增加内步不会消除同一个冻结误差。比如 $n=1,f(x)=x^2/2$ 时，方向就是 $x+e$ ，固定步长稳定迭代趋向 $-e$ ，原目标差为 $e^2/2$ 。

若两个分量不凸，式(4)所用的 $q_i\ge0$ 可失效，即使平均函数仍强凸，也不能直接使用上述证明。若输出改成 $x_m$ ，或每个阶段只打乱一次后顺序用分量，也分别改变输出或抽样条件。需要对应版本的分析，不能只保留SVRG名称便沿用式(3)。

推论与应用

把几何率换成总查询预算

在不缓存分量梯度的基线实现中，每阶段恰有 $n+2m$ 次查询，额外状态为 $O(d)$ ，向量运算为 $O((n+m)d)$ 。若在快照阶段保存全部 $n$ 个梯度，每个内步只需一次新梯度，总查询降为 $n+m$ ，却需 $O(nd)$ 梯度表存储。部分线性模型可用更小的表示，但那是利用模型结构后的另一份账。

若已知初始上界 $\Delta(\widetilde x_0)\le\Delta_0$ ，且 $\Delta_0>\varepsilon>0$ ，取

S\ge\left\lceil\frac{\log(\Delta_0/\varepsilon)}{\log(1/\rho)}\right\rceil

便保证期望目标差不超过 $\varepsilon$ 。选择上述常数后总查询为 $O((n+L/\mu)\log(\Delta_0/\varepsilon))$ 。这里不是每轮的误差观测证书；如果不知道 $\Delta_0$ ，还需另一个合法上界。oracle非有限、快照不完整或超出预算时应报告对应失败状态，不能输出这条定理认证。

非均匀抽样若按 $p_i>0$ 选择分量，保持无偏的方向应改为

\frac{\nabla f_I(x)-\nabla f_I(\widetilde x)}{np_I}+\nabla f(\widetilde x).

少了 $1/(np_I)$ ，条件均值实际变为

\sum_i p_i[\nabla f_i(x)-\nabla f_i(\widetilde x)]+\nabla f(\widetilde x),

通常不等于 $\nabla f(x)$ 。仍用两分量例、快照0、 $p=(3/4,1/4)$ ，这个均值为 $3x/2+1$ ，原目标梯度为 $2x+1$ ；快照项使它也不只是加权目标的梯度 $3x/2$ 。重新加权后恢复无偏，新的方差和步长常数仍要重算，不能直接复制式(2)。

参考资料

Rie Johnson、Tong Zhang，Accelerating Stochastic Gradient Descent using Predictive Variance Reduction，NeurIPS 2013，Figure 1 的Option II与Theorem 1；本文沿用同一输出索引、条件和收缩因子，并完整展开证明
Sébastien Bubeck，Convex Optimization: Algorithms and Complexity，2015，§6.3，有限和随机方法与方差缩减的复杂度比较

形式陈述 ​

同一个索引使差分真的变小 ​

一阶段的可用收缩因子 ​

从光滑分量到方差随目标差下降 ​

两分量模型的完整调用账 ​

哪些改变需要重做分析 ​

把几何率换成总查询预算 ​

反向链接