随机梯度的非凸驻点保证

形式陈述

目标非凸时，梯度很小仍是可核验的一阶性质，却不再自动意味着目标接近全局最优。设 $f:\mathbb R^d\to\mathbb R$ 有下界 $f_{\inf}>-\infty$ ，具有全局$L$-Lipschitz梯度， $L>0$ 。从固定 $x_0$ 出发，以常步长 $0<\eta\le1/L$ 做 $T\ge1$ 步无约束随机梯度更新

x_{t+1}=x_t-\eta g_t.

相对于查询前历史 $\mathcal F_t$ ，要求

E[g_t\mid\mathcal F_t]=\nabla f(x_t),\qquad E[\|g_t-\nabla f(x_t)\|^2\mid\mathcal F_t]\le\sigma^2.

再独立均匀抽取 $J\in\{0,\ldots,T-1\}$ ，输出 $x_J$ 。它可以在训练前独立抽好，并在运行到该位置时保存；算法不需要知道哪个迭代的真实梯度最小。若已知 $f(x_0)-f_{\inf}\le\Delta_0<\infty$ ，则

E\|\nabla f(x_J)\|^2 \le\frac{2\Delta_0}{\eta T}+L\eta\sigma^2.\tag{1}

概率同时来自训练oracle和独立输出索引。式(1)约束的是梯度范数的平方，不是函数值差，也不是指定末点的梯度。

下降引理给出完整证明

记 $a_t=\nabla f(x_t)$ 。将随机更新代入下降引理并条件化，有

E[f(x_{t+1})\mid\mathcal F_t] \le f(x_t)-\eta\|a_t\|^2+ \frac{L\eta^2}{2}(\|a_t\|^2+\sigma^2).

步长 $\eta\le1/L$ 使负的梯度项至少保留一半，故

\frac\eta2E\|a_t\|^2 \le Ef(x_t)-Ef(x_{t+1})+\frac{L\eta^2\sigma^2}{2}.

把 $T$ 步相加，目标差望远镜消去；末项 $Ef(x_T)\ge f_{\inf}$ 。最后独立均匀索引满足 $E\|\nabla f(x_J)\|^2=T^{-1}\sum_tE\|a_t\|^2$ ，从而得到式(1)。全局Lipschitz梯度、固定初值和条件噪声二阶矩通过递推保证每个有限时刻点的二阶矩及这些函数值期望有限。

如果每步在同一点平均 $b$ 个条件独立梯度，式(1)中的噪声项可换成 $L\eta\sigma^2/b$ 。与此同时总梯度查询为 $N=bT$ ，第一项变为 $2b\Delta_0/(\eta N)$ ，不能只记方差改善而忘掉减少的更新次数。

直觉

有下界的函数不可能永远大幅下降，因此平均来看，梯度最终不能一直很大。随机方向却会支付一个额外的曲率代价，正是式(1)中的噪声项。减小步长压低这笔代价，也让有限预算中的初始目标差更难被消除。

输出随机迭代，是把“平均每步的梯度平方受控”变成一个明确可执行的交付规则。直接选观察到的最小噪声梯度会偏向偶然抵消；直接平均参数在非凸几何中也可能走到更差的位置。

例子与边界

精度指的是范数，还是范数平方

若要求 $E\|\nabla f(x_J)\|^2\le\varepsilon^2$ ，其中 $\varepsilon>0$ 是梯度范数精度，且 $\sigma>0$ ，可取

\eta=\min\{1/L,\ \varepsilon^2/(2L\sigma^2)\}, \qquad T\ge\left\lceil\frac{4\Delta_0}{\eta\varepsilon^2}\right\rceil.

两项各不超过 $\varepsilon^2/2$ 。在噪声主导区间，充分预算为 $8L\sigma^2\Delta_0/\varepsilon^4$ 级，因此是 $O(\varepsilon^{-4})$ 次查询。如果作者把精度符号定义为“梯度范数平方至多 $\epsilon$ ”，同一结论会写成 $O(\epsilon^{-2})$ ；指标不同，不能直接比较指数。

例如 $L=\sigma^2=\Delta_0=1$ 、 $\varepsilon=0.1$ ，选择 $\eta=1/200$ 、 $T=80000$ 。式(1)两项均为 $0.005$ ，总计 $0.01$ 。这能经Cauchy–Schwarz推出 $E\|\nabla f(x_J)\|\le0.1$ ，却不是“以95%概率梯度不超过0.1”。若 $\sigma=0$ ，取 $\eta=1/L$ 后式(1)变为 $2L\Delta_0/T$ ，不需沿用含 $1/\sigma^2$ 的公式。

驻点可以是极大点，平均极小点也会出错

取 $f(x)=1-\cos x$ 。它非负、梯度 $\sin x$ 是1-Lipschitz，完全符合目标假设。但 $x=\pi$ 的梯度为零，目标值为2，是一个极大点；从该点使用精确梯度会永远停在那里。式(1)可以成立，同时全局最优差一点也没有下降。

同一个函数在0和 $2\pi$ 处都达到最小值0，它们的算术平均 $\pi$ 却是极大点。凸SGD中用Jensen把平均目标值转成平均点目标值的步骤，在这里已经失效。这也是本页选择随机输出而非默认参数平均的原因。

有偏oracle留下另一种底

设条件均值为 $a_t+b_t$ ， $\|b_t\|\le\beta_t$ ，其中 $\beta_t$ 为确定上界；中心化噪声条件二阶矩仍至多 $\sigma^2$ 。取 $\eta\le1/(4L)$ ，利用

-\langle a_t,b_t\rangle\le\tfrac14\|a_t\|^2+\beta_t^2, \qquad \|a_t+b_t\|^2\le2\|a_t\|^2+2\beta_t^2,

同一下降展开给

E\|\nabla f(x_J)\|^2 \le\frac{2\Delta_0}{\eta T}+L\eta\sigma^2+ \frac5{2T}\sum_{t=0}^{T-1}\beta_t^2.\tag{2}

因为梯度平方系数为 $-3\eta/4+L\eta^2\le-\eta/2$ ，偏差项系数为 $\eta+L\eta^2\le5\eta/4$ ，所以常数可逐项复算。

在 $f(x)=x^2/2$ 、无随机噪声而oracle为 $x+\beta$ 时，稳定更新趋向 $-\beta$ ，真实梯度范数趋向 $|\beta|$ 。它没有因查询次数增加而消失。裁剪、压缩、近似内部求解都应先查它们是否改变条件均值，再决定能否使用式(1)。

推论与应用

用新查询验证一个已经选定的候选

冻结训练输出 $\widehat x$ 后，在该点独立查询 $m$ 次无偏梯度，令均值为 $\widehat g$ 。若每次中心化噪声条件二阶矩至多 $\sigma^2$ ，则条件于全部训练结果，

E[\|\widehat g-\nabla f(\widehat x)\|^2\mid\text{训练}]\le\frac{\sigma^2}{m}.

Markov不等式作用于平方范数：给定 $r>0$ 、 $0<\delta<1$ ，取 $m\ge\max\{1,\lceil\sigma^2/(\delta r^2)\rceil\}$ ，就以至少 $1-\delta$ 的概率有

\|\nabla f(\widehat x)\|\le\|\widehat g\|+r.

观察到右侧不超过 $\varepsilon$ 时，才给出这份驻点证书；否则报告“未认证”，不等于已经证明候选不好。例如 $\sigma^2=1,\delta=0.05,r=0.02$ 需要50000次额外查询。若观察 $\|\widehat g\|=0.07$ ，上界为0.09；这50000次不能藏在前面的80000次训练预算之外不报告。

若比较多个候选或反复查看并停止，要为所有检查分配总失败概率，或使用同时有效的方法。同一固定候选的一次界，不自动覆盖“看到满意结果才停”的选择。

也可以不验证，直接由式(1)令其右侧至多 $\delta\varepsilon^2$ ，再用Markov给 $P(\|\nabla f(x_J)\|>\varepsilon)\le\delta$ 。这是另一种预先固定预算的高概率保证，代价一般更保守。两条路径都应说明置信来自哪一部分计算。

返回量和工作量

运行需 $T$ 次训练梯度，若额外验证再加 $m$ ；显式向量更新及验证累加为 $O((T+m)d)$ ，保存当前点和随机选中的点为 $O(d)$ 。异常梯度、超预算或数值溢出应终止并报告，不能用“最后仍有一个点”替代证书。即使成功认证驻点，它仍没有给出全局最优、统计泛化、隐私或参数识别保证。

参考资料

Saeed Ghadimi、Guanghui Lan，Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming，2013，§2.1 Theorem 2.1与§2.2：随机迭代输出、驻点复杂度及后优化验证。本文使用常步长特例并直接证明式(1)，验证采用单候选有限方差界
Léon Bottou、Frank E. Curtis、Jorge Nocedal，Optimization Methods for Large-Scale Machine Learning，2018，§4.3，光滑有下界目标的随机梯度分析

形式陈述 ​

下降引理给出完整证明 ​

精度指的是范数，还是范数平方 ​

驻点可以是极大点，平均极小点也会出错 ​

有偏oracle留下另一种底 ​

用新查询验证一个已经选定的候选 ​

返回量和工作量 ​