随机重排梯度法 | Codeboy's Blog

形式陈述

给定固定有限和 $f(x)=n^{-1}\sum_{i=1}^n f_i(x)$ ，各 $f_i$ 在全空间可微，随机重排每一轮（epoch）都访问所有分量一次。设轮数预算 $K\ge1$ 、步长 $\eta>0$ 、初值 $x_0\in\mathbb R^d$ ，算法为：

在第 $k$ 轮开始时，独立于过去均匀抽取一个排列 $\pi_k$ ，设置 $x_{k,0}=x_k$
按 $j=0,\ldots,n-1$ 依次更新 $x_{k,j+1}=x_{k,j}-\eta\nabla f_{\pi_k(j+1)}(x_{k,j})$
令 $x_{k+1}=x_{k,n}$ ，最后输出轮末点 $x_K$

每一轮 $n$ 次分量梯度查询， $K$ 轮共 $Kn$ 次。显式均匀洗牌需 $O(n)$ 操作和 $O(n)$ 索引存储；另保存 $O(d)$ 向量状态，模型与梯度计算成本单列。程序按预算、梯度非有限等情况输出正常结束或失败状态，不从“已经看完全部数据”推断达到了目标精度。

协议决定概率空间：每轮重新独立抽排列是随机重排；只在开头洗一次、随后重复同一顺序是shuffle-once；始终按预定顺序是循环增量法。三者每轮都看每个分量一次，却有不同的跨轮随机结构。下面将它们放在同一个模型中比较。

每个位置均匀，不等于每一步条件无偏

有放回SGD在每个当前点都从全部分量独立抽样。重排则会记住哪些分量已经使用：给定已揭示的排列前缀，下一项在剩余索引中均匀，因此

E[\nabla f_{\pi_k(j+1)}(x_{k,j})\mid\text{当前历史}] =\frac1{n-j}\sum_{i\text{尚未使用}}\nabla f_i(x_{k,j}).\tag{1}

这通常不是整梯度 $\nabla f(x_{k,j})$ 。这里的条件历史记录已用索引和当前点，未提前揭示排列后缀；若把整个排列提前加入历史，下一索引已经确定，条件无偏也同样不成立。两种信息口径均不能套有放回SGD的逐步证明。

直觉

一轮内不会漏掉任何分量，所以某些分量间的误差有机会相互抵消。但每访问一个分量，查询点都发生变化；本轮实际求和的是不同位置上的梯度，而不是同一点的精确整梯度。这就是“覆盖完整”与“方向精确”之间的差别。

同一点无放回批量与边访问边更新的重排对照：前者在同一点求均值，后者的第二次梯度在移动后的位置计算 — 访问集合相同，查询位置与条件分布不同

一整轮的行为往往比单步更容易理解。下面两分量模型会把第一步和第二步的噪声合成一个较小的轮级扰动，同时展示为什么只洗牌一次不能当成每轮独立重排。

例子与边界

两个相反的二次分量

令 $a>0$ ，

f_+(x)=\tfrac12(x-a)^2,\quad f_-(x)=\tfrac12(x+a)^2, \quad f(x)=\tfrac12x^2+\tfrac12a^2.

最优点为0，目标差 $\Delta(x)=x^2/2$ 。取 $0<\eta<2$ 、 $r=1-\eta$ ，故 $|r|<1$ 。若顺序为先 $+$ 后 $-$ ，一轮实际更新为

x\longmapsto rx+\eta a\longmapsto r^2x-\eta^2a.

反顺序则为 $r^2x+\eta^2a$ 。两次梯度求值并未给出同一点整梯度步；由于第二个点已经移动，留下了 $\eta^2a$ 的余量。

每轮重新公平选顺序时，轮末递推因此恰为

x_{k+1}=r^2x_k+\eta^2a\varepsilon_{k+1},\qquad \varepsilon_k\overset{\mathrm{IID}}\sim\operatorname{Unif}\{-1,1\}.

固定 $x_0$ 时，

Ex_K=r^{2K}x_0,\qquad \operatorname{Var}(x_K)=\eta^4a^2\frac{1-r^{4K}}{1-r^4}.\tag{2}

目标差期望为均值平方与方差之和的一半。这个模型中，单步有条件偏差，一整轮却得到一个精确、均值零且独立的新扰动；两件事并不矛盾。

同样2K次查询，有放回会怎样

每步独立抽 $+$ 或 $-$ 的普通SGD满足 $z_{t+1}=rz_t+\eta a\varepsilon_{t+1}$ 。同样 $2K$ 次查询给

Ez_{2K}=r^{2K}x_0,\qquad \operatorname{Var}(z_{2K})=\eta^2a^2\frac{1-r^{4K}}{1-r^2}.

初值偏差相同，而重排方差与有放回方差之比恰为

\frac{\eta^2}{1+r^2}.\tag{3}

当 $0<\eta<1$ 时比值小于1； $\eta=1$ 时相同； $1<\eta<2$ 时重排反而更差。即使在这一个很规则的二次模型上，“重排总更好”也不是无条件结论。

取 $a=1,\eta=1/2,x_0=0,K=2$ 。四种独立轮顺序给末点 $-5/16,-3/16,3/16,5/16$ ，各概率 $1/4$ ；均值0、方差 $17/256$ 。四步有放回SGD方差为 $85/256$ ，正好大五倍。两者的目标差期望分别为 $17/512$ 和 $85/512$ 。

一次洗牌与固定循环保留了顺序偏置

若固定使用先 $+$ 后 $-$ 的顺序，每轮扰动恒为 $-\eta^2a$ ，所以

x_K=r^{2K}x_0-\eta^2a\frac{1-r^{2K}}{1-r^2}, \qquad x_\infty=-\frac{\eta a}{2-\eta}.\tag{4}

反顺序得到正的极限。shuffle-once只是开始时随机选定正负号，此后一直复用；在 $x_0=0$ 时无条件均值为0，但每条轨迹仍趋向两个错误位置之一。均值为0并不能让均方误差也为0。

仍取 $a=1,\eta=1/2$ 。shuffle-once两轮后只可能是 $\pm5/16$ ，方差 $25/256$ ；极限平方误差为 $1/9$ 。每轮新重排的极限方差则为 $1/15$ ，来自式(2)。前者是固定随机顺序的长期偏差，后者是每轮新随机性的平稳波动，不能用同一个“噪声方差”解释。

单步无偏性失败可以当场看见

在上例 $x_0=0$ 、 $\eta=1/2$ 时，若第一项为 $+$ ，首步到 $1/2$ 。第二项必为 $-$ ，梯度为 $3/2$ ；然而当前位置的整梯度只是 $1/2$ 。另一种历史得到 $-3/2$ 对 $-1/2$ 。第二位置的索引在未条件化时仍然均匀，但它与查询点联动，已不能消掉证明中的交叉项。

这也说明不能把无放回小批量的有限总体修正直接搬来：小批量先固定 $x$ ，在该点同时评价若干分量，再更新一次；重排在两次评价之间就移动了 $x$ 。方差公式中的对象不同。

推论与应用

如何报告重排实验

至少记录每轮是否重新洗牌、随机源、分量数 $n$ 、已完成的完整轮数与最后一轮余下步数、每次更新的步长、输出位置。若预算 $N$ 不是 $n$ 的倍数，可以预先规定只用 $\lfloor N/n\rfloor$ 轮并报告未用额度；若继续执行不完整轮，轮末保证不能直接用于那个中间点。

式(2)–(4)是所给等曲率两分量模型的精确答案。不同曲率、多维不对易更新以及非凸分量会留下不同的整轮误差；一般收敛率需要相应光滑性、凸性、步长和分量梯度尺度。原论文研究这些更广的范围，本页不把一个模型的改善倍数升级为通用定理。

一个迁移自测是将步长改成 $3/2$ ，保持同样分量。此时 $r=-1/2$ ，式(3)给方差比 $9/5$ ，所以两种算法都处于稳定区间，重排的轮末方差却更大。稳定性与相对效率是两道分别要算的题。

参考资料

Konstantin Mishchenko、Ahmed Khaled、Peter Richtárik，Random Reshuffling: Simple Analysis with Vast Improvements，NeurIPS 2020，所阅arXiv v3（2021-04-05），§1–2及Algorithm 1，区分RR、shuffle-once、循环增量法与条件偏差；本文两分量递推及有限预算比较由正文直接推导

形式陈述 ​

每个位置均匀，不等于每一步条件无偏 ​

两个相反的二次分量 ​

同样2K次查询，有放回会怎样 ​

一次洗牌与固定循环保留了顺序偏置 ​

单步无偏性失败可以当场看见 ​

如何报告重排实验 ​