批量随机近端加速的噪声预算

形式陈述

设 $F=g+h$ ， $g:\mathbb R^d\to\mathbb R$ 凸且梯度为 $L$ -Lipschitz， $L>0$ ； $h$ proper、闭凸，最优点 $x^*$ 存在。初始 $x_0\in\operatorname{dom}h$ 固定，已知 $\|x_0-x^*\|\le R$ 。沿用FISTA的主点、外推点及权重，但明确使用较保守曲率 $K=2L$ 。

事先固定轮数 $T\ge1$ 与整数批量 $b_1,\ldots,b_T\ge1$ 。每轮在同一历史可测的 $y_k$ 处查询 $b_k$ 个条件独立的随机梯度；每项条件均值为 $\nabla g(y_k)$ ，中心化条件二阶矩至多 $\sigma^2$ 。取批平均 $v_k=\nabla g(y_k)+\xi_k$ ，因此

\mathbb E[\xi_k\mid\mathcal F_{k-1}]=0, \qquad \mathbb E[\|\xi_k\|^2\mid\mathcal F_{k-1}]\le\sigma^2/b_k.\tag{1}

这采用随机近端梯度的条件噪声模型；不同轮无需无条件独立。初始化 $y_1=x_0,t_1=1$ ，精确执行

\begin{aligned} x_k&=\operatorname{prox}_{h/K}(y_k-v_k/K),\\ t_{k+1}&=(1+\sqrt{1+4t_k^2})/2,\\ y_{k+1}&=x_k+\frac{t_k-1}{t_{k+1}}(x_k-x_{k-1}). \end{aligned}\tag{2}

输出最后主点 $x_T$ 、 $T$ 次 prox、 $N=\sum_kb_k$ 次随机梯度调用与参数。外推点不必在 $\operatorname{dom}h$ ，所以随机梯度 oracle 必须在实际查询的全空间可用且满足式(1)。本文证明

\mathbb E[F(x_T)-F^*] \le\frac{LR^2}{t_T^2} +\frac{\sigma^2}{2Lt_T^2}\sum_{k=1}^T\frac{t_k^2}{b_k}. \tag{3}

这是固定预算期望界，既不是无噪声 $O(T^{-2})$ 的直接继承，也不是已观测点的高概率停止证书。所有 prox 精确；内层近似误差需另加账本。

直觉

加速让早期的进展按增长的权重进入终点，同时也放大梯度噪声。式(3)把这种代价写成 $\sum t_k^2/b_k$ ：后期一份相同方差的误差比早期更昂贵。

留出 $K-L=L$ 的模型曲率余量，可以吸收“新主点已经依赖本轮噪声”的位移项；剩下的噪声内积才与旧历史配对、具有条件均值零。若直接把噪声项与新点的内积取期望为零，会得到不成立的加速结论。

八轮近端对应的真实批量为10、17、22、28、33、39、44、49，分开显示确定项和带权噪声项 — 加速权重决定批量，八轮不等于八个样本

为了减少昂贵的 prox 次数，可以在每个外推点多查一些梯度。它保留少量加速外轮，但没有让统计噪声所需的总样本数也变成 $O(\varepsilon^{-1/2})$ 。

例子与边界

六次样本、三次 prox 的实际轨迹

取 $g(x)=(x-1)^2/2,h(x)=|x|/2$ ， $L=1,K=2,x_0=0$ 。单次 oracle 是 $x-1+$ 独立公平符号，故 $\sigma^2=1$ ；最优点 $x^*=1/2,F^*=3/8$ 。批量为 $(1,2,3)$ ，一次实现的三批噪声分别是

(-1),\quad(-1,+1),\quad(-1,+1,+1),

所以批均值为 $-1,0,1/3$ 。阈值为 $1/4$ 。第一步 $x_1=3/4$ ；首轮动量为零，第二步 $x_2=5/8$ 。令 $\beta=(t_2-1)/t_3\approx0.281753525$ ，则

y_3=\frac58-\frac\beta8,\qquad x_3=\frac{y_3}2+\frac1{12}=\frac{19}{48}-\frac\beta{16} \approx0.378223738.

该点为正，实际目标差是 $(x_3-1/2)^2/2$ ，约0.007414729。总调用是6，prox是3，不是“只用了3个随机梯度”。完整64条等概率符号路径的最终目标期望约0.0565284807；用 $R=1/2$ 代入式(3)的上界约0.4585695388。枚举平均与保守上界是不同产物。

同批三次返回若只是复制同一个符号，方差仍为1，不能填 $1/3$ 。所有批次复用同一个固定噪声还会破坏条件无偏。这两种故障都不能靠加大账面 $b_k$ 修复。

按所需精度先安排批量

设 $R,\sigma,\varepsilon>0$ 。先选 $T$ 使

\frac{LR^2}{t_T^2}\le\frac\varepsilon2.

一个不需试算权重的充分选择是 $T=\max\{1,\lceil\sqrt{8LR^2/\varepsilon}\rceil-1\}$ ，因为 $t_T\ge(T+1)/2$ 。权重恒等式还给 $A=\sum_{k=1}^Tt_k=t_T^2$ ：将 $t_k=t_k^2-t_{k-1}^2$ 从第2轮求和，再加 $t_1=t_1^2=1$ 即得。因而可取

b_k=\max\left\{1,\left\lceil \frac{\sigma^2t_k}{L\varepsilon} \right\rceil\right\}.\tag{4}

这使式(3)的噪声项至多 $\varepsilon/2$ 。正 $\sigma$ 下括号内严格正，因此

N\le T+\frac{\sigma^2t_T^2}{L\varepsilon} \le T+\frac{\sigma^2T^2}{L\varepsilon}.\tag{5}

由递推可知 $t_k\le k$ ，得到最后一步。于是 prox 次数为 $O(1+\sqrt{LR^2/\varepsilon})$ ，在 $0<\varepsilon\le LR^2$ 的精度区间中样本数为 $O(\sqrt{LR^2/\varepsilon}+\sigma^2R^2/\varepsilon^2)$ 。式(5)及取整公式才是全参数有效的具体账本。 $\sigma=0$ 时直接每轮取一项； $R=0$ 且知道其确为到最优点距离上界时，可返回初值。

例如 $L=R=\sigma=1,\varepsilon=0.1$ ，上述充分规则给 $T=8$ 。按真实权重计算的批量是 $(10,17,22,28,33,39,44,49)$ ，总 $N=242$ ；确定项约0.0417579531，噪声项约0.0494860922，总界约0.0912440453。后期较大批量由权重账本决定。

固定批量不能凭名称得到无噪声率

若始终使用同一个 $b$ ，式(3)的噪声项为 $\sigma^2\sum t_k^2/(2Lbt_T^2)$ ，其量级为 $\sigma^2T/(Lb)$ 。这表示本证明不能认证无限增加外轮仍持续改善，不表示真实误差必定按这个上界线性增长。

在最简单的 $h=0,g(x)=Lx^2/2,x_0=0$ 模型中，第一轮主点为 $-\xi_1/(2L)$ ，期望目标差已经是 $\sigma^2/(8Lb_1)>0$ 。若错误沿用只含初始距离的无噪声界，右侧是零，第一步就产生矛盾。准确的噪声模型必须在第一轮开始计费。

推论与应用

新点依赖噪声，如何正确消去

记一次查询点为 $y$ 、主点为 $x$ 、批噪声为 $\xi$ 。精确 prox 的最优性、 $g$ 的凸下界与光滑上界相加，任取 $z\in\operatorname{dom}h$ 得

\begin{aligned} F(x)\le F(z)&+\frac K2(\|z-y\|^2-\|z-x\|^2) -\frac{K-L}{2}\|x-y\|^2 -\langle\xi,x-z\rangle. \end{aligned}

拆开 $x-z=(x-y)+(y-z)$ ，并用

-\langle\xi,x-y\rangle \le\frac{K-L}{2}\|x-y\|^2+\frac{\|\xi\|^2}{2(K-L)},

便得到保留可预测内积的一步式

F(x)\le F(z)+\frac K2(\|z-y\|^2-\|z-x\|^2) +\frac{\|\xi\|^2}{2L}-\langle\xi,y-z\rangle,\tag{6}

其中已代入 $K=2L$ 。与本轮噪声有关的新点位移已经支付完，不能再重复声称它独立。

带噪加速势的完整累计

设 $\Delta_k=F(x_k)-F^*$ ， $u_k=t_kx_k-(t_k-1)x_{k-1}-x^*$ ，并记 $u_0=x_0-x^*$ 。第 $k$ 轮取

z_k=(1-1/t_k)x_{k-1}+x^*/t_k.

它只依赖旧历史及固定最优点；凸性给 $F(z_k)-F^*\le(1-1/t_k)\Delta_{k-1}$ 。外推和权重恒等式给

t_k(z_k-y_k)=-u_{k-1},\quad t_k(z_k-x_k)=-u_k,\quad t_k(t_k-1)=t_{k-1}^2\quad(k\ge2).

令 $P_k=(2/K)t_k^2\Delta_k+\|u_k\|^2$ 。式(6)乘 $2t_k^2/K$ ，得到

P_k\le P_{k-1} +\frac{t_k^2}{KL}\|\xi_k\|^2 -\frac{2t_k}{K}\langle\xi_k,u_{k-1}\rangle,\qquad k\ge2.\tag{7}

第一轮同样成立，只把 $P_0$ 定义为 $\|x_0-x^*\|^2$ ；因为 $t_1=1$ ，此时比较点就是 $x^*$ ，没有初始目标差项。 $u_{k-1}$ 历史可测，式(1)使最后内积的条件期望为零。有限二阶矩与非扩张 prox 保证所用有限轮状态及交叉项可积。求和得到

\mathbb EP_T\le R^2+\frac{\sigma^2}{KL}\sum_k\frac{t_k^2}{b_k}.

丢掉末端平方范数，再乘 $K/(2t_T^2)$ ，就是式(3)。这一步完整保留随机误差，没有调用确定 FISTA 结论来替代分析。

为什么批量正比于权重

暂时允许连续正批量，固定总查询数 $N$ 。由Cauchy–Schwarz，

\left(\sum_kt_k\right)^2 \le\left(\sum_k\frac{t_k^2}{b_k}\right)\left(\sum_kb_k\right).

等号在 $b_k\propto t_k$ 取得。因此应让后期批量线性随权重增长，而不是按 $t_k^2$ 分配。整数、每批至少1、固定 $N$ 的精确最优离散分配可另外求解；式(4)选择向上取整，提供可直接执行的安全预算。它不声称在每个小整数预算都达到精确最优。

若有未知曲率、近似 prox、带偏 oracle 或根据当前噪声接受回溯，都改变式(6)或条件可测性。确定内层残差预算不能未经增长权重分析直接搬来。实际可行对偶 gap 仍可另行计算，其费用也不包含在式(5)的 oracle 数中。

实现账本与失败状态

可在一个固定 $y_k$ 处流式累加批量，不必保存每个样本梯度；常数个 $d$ 维向量需要 $O(d)$ 状态。批量累加与重加权工作为 $O(Nd)$ ，外推等外层向量运算为 $O(Td)$ ； $T$ 次精确 prox 的内部费用及采样器费用另计。非有限 oracle、无法完成精确 prox、或剩余调用预算不足以完成计划批量时，应报告失败或未完成，并保留已花费用；不能把少跑的批量填入原计划证书。

自测与答案

只有一轮， $L=R=\sigma=1,b_1=10$ ，式(3)是多少？答案： $t_1=1$ ，界为 $1+1/20=1.05$ 。它是最坏上界，不能用观察到的较小误差倒推出条件更强。
若将连续预算加倍且保持 $b_k$ 的比例，噪声项与 prox 次数怎样变化？答案：同一个固定 $T$ 下噪声项减半，prox 次数不变；这不保证墙钟时间减半，也没有改善确定项。

参考资料

Mark Schmidt、Nicolas Le Roux、Francis Bach，Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization，NeurIPS 2011，§4、Proposition 2 展示加速误差的增长权重。本文另证条件无偏批量噪声、放大曲率与式(7)，不把该文确定误差参数当作方差
Sébastien Bubeck，Convex Optimization: Algorithms and Complexity，2015 v2，§5.1（印刷页310–311）给出 ISTA/FISTA，§6.2（印刷页332–334）分析光滑随机优化与小批量；本文的放大曲率加速噪声势和具体批量不是该两节原样陈述的定理，已在正文独立证明

形式陈述 ​

六次样本、三次 prox 的实际轨迹 ​

按所需精度先安排批量 ​

固定批量不能凭名称得到无噪声率 ​

新点依赖噪声，如何正确消去 ​

带噪加速势的完整累计 ​

为什么批量正比于权重 ​

实现账本与失败状态 ​

自测与答案 ​

反向链接