随机近端梯度

随机梯度保留光滑损失的平均方向，prox保留惩罚的尖角或约束。SGD理路随机梯度下降Stochastic gradient descent · SGD · 随机梯度法在已知历史下用无偏随机梯度更新，推导凸目标期望界与二次噪声底，并按真实梯度查询比较批量和停止保证。的条件oracle结构在这里继续有用，但经过非线性prox后，“无偏梯度”不会变成“无偏下一点”。证明必须把随机误差与新点之间的依赖显式处理。

写 ${\xi }_k=v_k-\mathrm{\nabla }g(x_k)$。${\xi }_k$对旧历史均值为零，可是 $x_{k+1}$已经使用了它，通常 $\mathbb{E}⟨{\xi }_k,x_{k+1}-x^{\ast }⟩\ne 0$。下面把这个内积拆成旧点项和本轮位移项：旧点项可条件消去，位移项由二次稳定项付账。这是随机复合分析中不可跳过的一步。

阈值之后为什么有偏 ​

取 $g(x)=(x-1{)}^2/2$、$h(x)=|x|/2$，$x_0=0$、$\alpha =1/2$。每轮噪声取独立公平 $\xi =\pm 1$，使用 $v=x-1+\xi$，因此满足式(1)，$L=1,{\sigma }^2=1$。

第一轮 $v$为 $0$ 或 $-2$，梯度候选为 $0$ 或 $1$；阈值为 $\alpha /2=1/4$，所以 $x_1$为 $0$ 或 $3/4$，均值 $3/8$。若先用均值梯度 $-1$再做prox，结果为 $S_{1/4}(1/2)=1/4$。$3/8\ne 1/4$说明不能交换期望和软阈值。

本问题最优点为 $x^{\ast }=1/2$、$F^{\ast }=3/8$。两个随机输出的目标分别是 $1/2$和 $13/32$，一步期望超额为 $5/64$。零输出不是统计意义上变量消失的证据，也不说明惩罚后的最优点为零。

若只掌握 $\Vert x_0-x^{\ast }\Vert \le 1$，要求一个通用预算例，取 $T=100$、$\alpha =1/\sqrt{200}<1/2$，式(3)给期望超额不超过 $\sqrt{2/100}\approx 0.141421356$。这只是所列上界；它不声称例中100轮实际误差等于这个数。

有限和的定标和完整检查 ​

对于不除以样本数的平方损失 $g(x)=\frac{1}{2}\sum _{i=1}^m(a_i^{T}x-b_i{)}^2$，均匀有放回抽行 $I$时，正确oracle是 $v=m{a}_I(a_I^{T}x-b_I)$。漏掉 $m$会把目标的损失部分缩小，相对于固定 $\lambda \Vert x{\Vert }_1$改变了问题。若改为平均损失，oracle才不用这个 $m$。

行梯度方差可能随 $x$增大，无约束Lasso不自动满足全程统一 ${\sigma }^2$。要使用式(3)，必须证明轨道所在区域的方差界，或将有界约束纳入 $h$并精确计算相应prox。只写“有限数据所以方差有界”不足以覆盖无限参数空间。

若需Lasso可行对偶证书理路Lasso 的最优性与对偶间隙Lasso optimality conditions · Lasso duality gap · Lasso primal-dual certificate从残差相关性核验 Lasso 的零与非零坐标，并用可行对偶值认证剩余优化误差。，应在实际返回点计算完整 $r=b-Ax$和所有列的相关性；一个抽样梯度或抽样KKT残差不能证明所有对偶约束成立。这些完整检查的成本不包含在每次随机行查询中。

噪声如何进入三点不等式 ​

简写 $x=x_k,z=x_{k+1},\xi ={\xi }_k$。精确prox给

用其次梯度不等式、凸性和下降引理理路下降引理Descent lemma · Quadratic upper-bound lemma以 Lipschitz 梯度常数给出函数相对一阶模型的全局二次上界。，对 $u=x^{\ast }$得到

因为 $\alpha \le 1/(2L)$，位移平方的系数至少是 $1/(4\alpha )$。拆开最后的内积，用

消去这一位移项，剩下 $-⟨\xi ,x-x^{\ast }⟩$。条件于历史，它的期望为零，而 $\mathbb{E}[\Vert \xi {\Vert }^2\mid {\mathcal{F}}_k]\le {\sigma }^2$。求全期望并对 $T$轮求和，距离项望远镜消去，再由Jensen不等式理路Jensen 不等式Jensen's inequality凸函数作用于平均值不超过函数值的相同加权平均。处理平均点，就得到式(3)。没有把依赖噪声的新点冒充旧历史可测量。

如果距离有效上界为 $D>0$且 $\sigma >0$，在步长限制内平衡两项可选 $\alpha =min\{1/(2L),D/(\sigma \sqrt{2T})\}$；当第二项被选中，界为 $\sqrt{2}D\sigma /\sqrt{T}$。噪声为零时可取 $1/(2L)$得到 $O(1/T)$，但本证明的保守常数不替代确定近端页的更紧版本。

不同误差需要不同预算 ​

每轮有一次随机oracle、一次精确prox和 $O(n)$平均累加；$T$轮的prox总成本必须另报。独立同点小批量把方差上界缩小为 ${\sigma }^2/b$，却使用 $b$次oracle；相关批量不能自动除以 $b$。随机小批量与内层近似prox理路近似近端梯度的误差预算Inexact proximal gradient · Proximal subproblem residual budget用可核验的近端子问题次梯度残差分配内层精度，并把累计误差传到外层平均目标差。也不是同一个误差来源，后者会再加一份确定或可控残差项。

FISTA理路FISTA 复合加速法FISTA · Fast iterative shrinkage-thresholding algorithm以近端主点、外推查询点和递推权重组成复合凸加速，并用势函数而非逐轮下降证明函数值速率。的无噪声加速势对增长权重很敏感。将式(1)oracle直接代入它，不能宣称仍有无噪声 $O(1/T^2)$。本页以平均输出换取清楚的随机保证；最后一点、强凸加速和高概率停止是另需条件的任务。

两道短自测 ​

1. $D=1,\sigma =2,T=200,L=1$，取 $\alpha =D/(\sigma \sqrt{2T})$，它有效吗，式(3)是多少？答案：$\alpha =1/40\le 1/2$，两项各0.1，总界0.2。
2. 不归一化的10行平方损失，只抽到第3行，oracle应为哪一项？答案：$10a_3(a_3^{T}x-b_3)$；若只用原行梯度，均值是目标梯度的十分之一，固定惩罚下改变了目标。

随机复合镜像下降理路随机复合镜像下降Stochastic composite mirror descent · 随机复合 Bregman 更新在非欧氏几何中分开随机次梯度和精确结构项，证明更新前平均的有限预算界，并计算熵正则单纯形的真实更新。使用可能不光滑的损失、原始对偶二阶矩与更新前平均，并为结构项首尾差付账；本页使用光滑项中心化方差、欧氏 prox 与更新后平均。相同形式的更新不使两份保证互换。需要减少昂贵 prox 次数时，批量随机近端加速理路批量随机近端加速的噪声预算Batched accelerated stochastic proximal gradient · 带权批量 FISTA以放大的安全曲率吸收随机位移，证明加速势中的加权噪声和，再分配批量大小以分别认证近端次数与样本梯度成本。另以放大曲率和带权噪声势证明最后主点界，给出8次 prox、242次样本的预算；它不是直接继承无噪声 FISTA。