Polyak–Ruppert 迭代平均

形式陈述

随机逼近生成一串带噪迭代 $x_0,x_1,\ldots$ 。Polyak–Ruppert平均保留原更新，同时输出

\bar x_T=\frac1T\sum_{t=1}^T x_t,\qquad \bar x_t=\bar x_{t-1}+\frac{x_t-\bar x_{t-1}}t.

这里平均的是更新后的 $x_1,\ldots,x_T$ ，不含 $x_0$ 。它不增加oracle查询，只需每轮多一次向量累加，额外 $O(d)$ 状态。普通算术平均给各迭代同样权重；固定遗忘率的指数移动平均保留不同权重，不能据此继承下面的结论。

一个完全可证明的线性版本

先精确限定本页主定理。设 $x_t\in\mathbb R$ ，未知根为 $\theta$ ， $\lambda,c>0$ ，并且

x_t=x_{t-1}-\eta_t[\lambda(x_{t-1}-\theta)+\xi_t], \qquad \eta_t=ct^{-\alpha},\quad\frac12<\alpha<1.

初值固定； $\xi_t$ 独立同分布，均值0，方差 $0<\sigma^2<\infty$ 。于是

\sqrt T(\bar x_T-\theta)\Rightarrow N(0,\sigma^2/\lambda^2),\qquad T E(\bar x_T-\theta)^2\longrightarrow\sigma^2/\lambda^2.\tag{1}

这是一维线性、加性IID噪声的结论。常数不依赖步长系数 $c$ ，却依赖根附近的斜率 $\lambda$ 。一般非线性、多维或相关噪声的平均理论还要核实局部线性化、稳定性、条件协方差和尾部条件；本页先把能完整复算的情况讲清。

为什么平均会留下样本均值的主项

令 $e_t=x_t-\theta$ 、 $v_t=Ee_t^2$ 。独立噪声给

v_t=(1-\lambda\eta_t)^2v_{t-1}+\sigma^2\eta_t^2.

由此有 $v_t=O(t^{-\alpha})$ 。一个直接验证方法是：从足够大的 $t$ 起用 $(1-\lambda\eta_t)^2\le1-\lambda\eta_t$ ，选足够大的 $C$ ，归纳比较 $v_t$ 与 $Ct^{-\alpha}$ 。噪声项和收缩项都为 $t^{-2\alpha}$ 级；相邻包络的差 $C[(t-1)^{-\alpha}-t^{-\alpha}]$ 为 $t^{-\alpha-1}$ 级。由于 $\alpha<1$ ，后者更小，取 $C$ 使 $\lambda c C>\sigma^2c^2$ 并增大起始常数即可完成归纳。

把递推改写为 $\lambda e_{t-1}=-\xi_t+(e_{t-1}-e_t)/\eta_t$ ，求和并整理端点，得到精确恒等式

\lambda T\bar e_T=-\sum_{t=1}^T\xi_t+B_T,

B_T=\frac{e_0}{\eta_1}-\frac{e_T}{\eta_T} +\sum_{t=1}^{T-1}e_t\left(\frac1{\eta_{t+1}}-\frac1{\eta_t}\right) +\lambda(e_T-e_0).\tag{2}

这一步是离散分部求和。由 $\|e_t\|_{L^2}=O(t^{-\alpha/2})$ ，端点项 $e_T/\eta_T$ 的 $L^2$ 范数为 $O(T^{\alpha/2})$ 。和式中倒步长差为 $O(t^{\alpha-1})$ ，用三角不等式得到同样的 $O(T^{\alpha/2})$ 上界。因此

\|B_T/\sqrt T\|_{L^2}=O(T^{(\alpha-1)/2})+O(T^{-1/2})\longrightarrow0.

对式(2)的独立噪声和使用中心极限定理，再用Slutsky定理，得到式(1)的分布极限。余项还在 $L^2$ 中趋零，而主项二阶矩恰为 $\sigma^2/\lambda^2$ ，故同一恒等式也证明式(1)的均方极限。这条证明没有把相关的迭代误当成IID样本。

直觉

单个迭代使用最近的噪声较多，因而还在根附近晃动；平均把不同时间的晃动结合起来。式(2)揭示更准确的机制：递推中的相邻误差大部分互相抵消，最后保留一个噪声样本均值和较小的端点修正。

常步长下一个新噪声进入多个后续迭代，平均后的总权重趋近相同，而早期末点权重已经衰减 — 同一噪声在末点与平均中的权重不同

这里不能直接用“迭代样本标准差除以 $\sqrt T$ ”估计标准误。各点共享过去噪声，协方差项会累积。例如常步长标量递推中， $s\le t$ 时有 $\operatorname{Cov}(e_s,e_t)=r^{t-s}\operatorname{Var}(e_s)$ ，其中 $r=1-\eta\lambda$ ；除非 $r=0$ ，通常并不为零。

例子与边界

常步长二次模型：末点有噪声底，平均却没有

仍取线性加性模型，但让 $0<\eta<2/\lambda$ 固定， $r=1-\eta\lambda$ 。从递推展开再交换有限求和顺序，得到

\bar e_T=\frac{r(1-r^T)}{T(1-r)}e_0 -\frac1{\lambda T}\sum_{j=1}^T(1-r^{T-j+1})\xi_j.\tag{3}

因此

E\bar e_T=\frac{r(1-r^T)}{T(1-r)}e_0,\qquad \operatorname{Var}(\bar e_T) =\frac{\sigma^2}{\lambda^2T^2}\sum_{k=1}^T(1-r^k)^2.\tag{4}

因为 $|r|<1$ ，和式等于 $T+O(1)$ ，故 $T\operatorname{Var}(\bar e_T)\to\sigma^2/\lambda^2$ ，平均偏差平方为 $O(T^{-2})$ 。这解释了为什么SGD末点的正噪声底与平均的 $1/T$ 均方误差能够同时成立；输出已经变了。

取 $\lambda=1,\eta=1/4,e_0=2,\sigma^2=1,T=2$ 。平均均值为 $21/16$ ，噪声系数分别为 $-7/32,-1/8$ ，所以方差为 $65/1024$ ，均方误差为 $1829/1024$ 。对应二次目标期望为 $1829/2048$ ，比两步末点的 $349/512$ 还大：短预算中，平均保留了较多初始误差。渐近优势不等于每个预算都占优。

对已经调好的1/t递推，再平均会损失常数

取 $\eta_t=1/(\lambda t)$ 。首步后

e_t=-\frac1{\lambda t}\sum_{j=1}^t\xi_j,

因此末点均方误差恰为 $\sigma^2/(\lambda^2T)$ 。再次平均得到每个噪声的权重 $-(H_T-H_{j-1})/(\lambda T)$ ，其中 $H_T=\sum_{t=1}^T1/t$ 。利用 $\operatorname{Cov}(e_s,e_t)=\sigma^2/(\lambda^2t)$ （ $s\le t$ ），逐列相加可得

\operatorname{Var}(\bar e_T) =\frac{\sigma^2}{\lambda^2T^2} \left(\sum_{t=1}^T\frac1t+2\sum_{t=2}^T\frac{t-1}{t}\right) =\frac{\sigma^2(2T-H_T)}{\lambda^2T^2}.\tag{5}

它渐近是末点方差的两倍。 $T=4$ 时，两者分别为 $71\sigma^2/(192\lambda^2)$ 与 $\sigma^2/(4\lambda^2)$ ，方差比 $71/48$ 。主定理排除 $\alpha=1$ 有实质意义；平均并不是对任意步长都免费的效率提升。

非线性常步长可以平均到错误位置

在 $C=[-1,1]$ 上从 $x_0\in C$ 出发，取

h(x)=x+\frac{1-x^2}{4},\qquad x^*=2-\sqrt5.

$h'(x)=1-x/2\in[1/2,3/2]$ ，故根唯一、方向强单调。给定当前 $x$ ，令随机数 $Y\in\{-1,1\}$ 满足

P(Y=1\mid x)=\frac{3+x^2}{8},\qquad P(Y=-1\mid x)=\frac{5-x^2}{8}.

每步用新的独立随机数实现这两个条件概率。于是 $E[Y\mid x]=-(1-x^2)/4$ ，oracle $H=x-Y$ 对 $h(x)$ 条件无偏且有界。步长取1，更新为 $x'=x-H=Y$ ，不需要投影就一直留在 $C$ 。

首步以后， $x=\pm1$ ，两种转移概率都等于 $1/2$ 。所以从第二个迭代起就是独立公平符号，大数律给 $\bar x_T\to0$ ，但真根为 $2-\sqrt5\approx-0.2361$ 。若令 $f(x)=x^2/2+x/4-x^3/12$ ，则 $f'=h$ ，它在 $C$ 上强凸；平均输出对根的偏差仍不消失。

失败位置很具体： $Eh(X)=0$ 不推出 $h(EX)=0$ 。线性加性模型中可以交换这两个操作，非线性模型中不行。因而常步长平均的式(3)–(4)应连同线性条件一起使用。

推论与应用

成本、置信声明与可执行比较

$T$ 个迭代只消耗原递推的 $T$ 次oracle调用。若要去掉前 $B$ 个“热身”点，应事先固定 $B<T$ ，实际查询仍为 $T$ 次，平均样本数则是 $T-B$ ；式(3)的权重必须重新求和，不能同时把费用与方差都当成只运行了 $T-B$ 步。

式(1)支持的是渐近正态近似。有限样本覆盖还需已知噪声尺度、精确权重或额外验证；从一条高度相关的轨迹计算普通IID标准误并不能完成这一步。在式(3)的独立次高斯噪声模型中，可以直接按权重平方和计算有限样本尾界，而不必等待CLT近似。

一个有用的比较顺序是先写相同的样本梯度预算，再分开初值偏差与方差，最后指定输出。完整的24次查询比较见随机优化终点任务。如果固定数据可反复查询，SVRG改变的是每步噪声估计器；平均则保留更新而改变最后交付的点，两种机制可以分别分析。

参考资料

B. T. Polyak、A. B. Juditsky，Acceleration of Stochastic Approximation by Averaging，1992，§2 Theorem 1与§3 Theorem 2，尤其区分线性常步长、慢衰减步长和非线性条件。本文只对所述标量IID版本给出自足证明
Léon Bottou、Frank E. Curtis、Jorge Nocedal，Optimization Methods for Large-Scale Machine Learning，2018，§5.4，迭代平均及其适用背景

形式陈述 ​

一个完全可证明的线性版本 ​

为什么平均会留下样本均值的主项 ​

常步长二次模型：末点有噪声底，平均却没有 ​

对已经调好的1/t递推，再平均会损失常数 ​

非线性常步长可以平均到错误位置 ​

成本、置信声明与可执行比较 ​