随机次梯度方法最终迭代的新界限

论文信息

标题: New Bounds for the Last Iterate of the Stochastic subGradient Method

作者: Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni, et al.

发布日期: 2026-06-23

PDF 链接: 下载 PDF

一维随机次梯度方法最后迭代点的精确界：破解长期开放问题

研究背景与动机

随机次梯度方法（Stochastic subGradient Method, SsGM）是约束随机优化领域最经典的算法之一。在固定迭代次数（finite-horizon）的设置下，传统分析通常关注平均迭代点（average iterate）的优化误差：当采用固定步长 $\eta = \Theta(1/\sqrt{n})$ 时，平均迭代点能达到 $1/\sqrt{n}$ 的最优收敛速率。

然而在实践中，人们通常直接使用最后迭代点（last iterate），因为它更简单且往往具有更好的经验性能。但分析最后迭代点远比平均迭代点困难。在标准的固定步长策略下，已知最后迭代点的最佳上界为 $(\log n)/\sqrt{n}$ ，比平均迭代点多出一个对数因子。这个对数因子是否真有必要，成为了困扰学界的开放问题。

Koren 和 Segal 在 2020 年明确提出：在一维固定维度下，最后迭代点是否能达到 $1/\sqrt{n}$ 的最优速率？本文给出了否定答案，并进一步揭示了两种噪声结构对称性在去除对数因子中的关键作用。

核心方法与技术框架

问题设定

论文考虑一维约束凸优化问题：

\min_{x \in \mathcal{X}} f(x)

其中 $f$ 是 $L$ -Lipschitz 连续凸函数， $\mathcal{X} \subseteq \mathbb{R}$ 是闭凸集。SsGM 的迭代更新为：

X_{k+1} = \Pi_{\mathcal{X}}(X_k - \eta \cdot (G_k + W_k))

其中 $G_k \in \partial_{\mathcal{X}} f(X_k) \cap [-L, L]$ 是相对次梯度， $W_k$ 是加性噪声项。

论文精细地区分了三种噪声假设层级：

基础方差条件（假设 3）： $W_k$ 条件均值为 0，条件二阶矩不超过 $\sigma^2$
中心化加性核 oracle（假设 4）：噪声存在核表示 $Q_k(x, \cdot)$
时间齐次性（假设 5）： $Q_k$ 不依赖时间 $k$
状态独立性（假设 6）： $Q_k$ 不依赖查询状态 $x$

当三个核条件同时成立时，噪声序列是独立同分布的。

正面结果：去除对数因子

定理 2建立了正面结果：在状态独立且时间齐次（即噪声 i.i.d.）的设置下，对于任意固定步长 $\eta > 0$ ，最后迭代点满足：

\mathbb{E}[\Delta(X_n)] \leq \frac{\text{dist}(x_1, \mathcal{X}_\star)^2}{2\eta n} + \left((L+\sigma)^2 + \frac{L^2+\sigma^2}{2}\right)\eta

当取 $\eta = c_n/\sqrt{n}$ （ $0 < \underline{c} \leq c_n \leq \overline{c} < \infty$ ）时，立即得到：

\mathbb{E}[\Delta(X_n)] \leq C \cdot \frac{1}{\sqrt{n}}

其中常数 $C$ 仅依赖于问题参数和步长常数的上下界，完全不依赖 $n$ 。这成功去除了对数因子，证明在一维 i.i.d.噪声下最后迭代点确实最优。

核心技术创新：证明的核心是建立 “一次良好迭代后误差不会过度退化” 的单调性估计。具体而言：

存在良好迭代点：经典平均分析保证存在某个时刻 $k_\star$ 使得 $\mathbb{E}[\Delta(X_{k_\star})]$ 已经达到 $1/\sqrt{n}$ 量级。
误差退化控制（引理 10）：对于所有 $k \geq k_\star$ ，证明
$\mathbb{E}[(f(X_k) - f(X_{k_\star}))_+] \leq (L+\sigma)^2 \eta$
这意味着良好迭代之后的期望优化误差增加量被严格限制在 $O(\eta) = O(1/\sqrt{n})$ 。
Foster-Lyapunov 漂移参数构造：为证明误差退化界，作者精巧地定义了变换 $T_{\mathcal{I}, m, \eta}$ 和势函数 $B(z) = z^2/(2\eta) + 2Lz$ ，建立了关键漂移不等式（命题 6）：
$PB(z) - B(z) \leq -\int_0^z m(s)ds + \left(\frac{\sigma^2}{2} + L\sigma\right)\eta$
这实质上控制了随机过程在 “错误区域” 中累积的代价不会太大。

负面结果：对数因子的不可避免性

定理 3提供了两个精心构造的反例，证明任一对称性的缺失都会导致对数因子回归：

反例 1：状态依赖但时间齐次。在目标函数 $f(x)=\max\{x,0\}$ 上，构造概率核 $Q(x,\cdot)$ ，在特殊状态 $s_j = -(j+1)\eta\lambda$ （ $j=1,\ldots,M$ ， $M \approx 1/(16\eta)$ ）处赋予大噪声 $-4j$ 以 $1/(64j^2)$ 的概率。这导致：

\mathbb{E}[f(X_n)-f_\star] \geq \frac{1}{512}\eta\log\frac{1}{\eta} \geq \frac{\underline{c}}{2^{11}}\frac{\log n}{\sqrt{n}}

反例 2：状态独立但时间非齐次。将标签 $j$ 与特定时刻 $k_j=n-j$ 关联，在时刻 $k_j$ 使噪声以 $1/(64j^2)$ 概率取 $-4j$ 。同样产生 $(\log n)/\sqrt{n}$ 的下界。

两个下界都利用了调和级数求和结构：每个标签 $j$ 贡献 $\eta/j$ 的期望误差， $j=1$ 到 $M$ 求和得到 $\eta \log M \approx \eta \log(1/\eta)$ 。这在标准步长下恰好对应 $(\log n)/\sqrt{n}$ 。

创新点与贡献

完全解决开放问题：明确回答 Koren 和 Segal (2020)的 Open Problem 1，证明即使在维度 $d=1$ ，标准方差假设下最后迭代点仍可能是次优的。
对称性的精确刻画：揭示时间齐次性和状态独立性在去除对数因子中各自都是必要条件——任缺其一，对数因子就会重现。这为噪声模型的设计和算法分析提供了精确指导。
新的分析工具：发展的 Foster-Lyapunov 型漂移参数构造和基于区间投影的支配链技术，为处理约束优化的最后阶段行为提供了新的方法论。
紧致的常数：正面结果给出了确切的常数依赖关系，并允许通过优化步长系数 $c$ 来最小化误差界：
$c_\star = \frac{\text{dist}(x_1, \mathcal{X}_\star)}{\sqrt{3L^2+4L\sigma+3\sigma^2}}$

实践应用建议

噪声结构评估：在实际部署 SsGM 时，应评估随机梯度的噪声是否近似 i.i.d.。如果是（例如使用独立同分布的小批量采样），则可以直接使用最后迭代点，无需平均。
步长调优：本文给出的精确常数允许根据问题参数（初始距离、Lipschitz 常数、噪声方差）计算理论最优步长系数，为超参数选择提供指导。
高维场景的谨慎使用：虽然本文集中在一维，但对于维度固定但不太大的问题，若噪声近似 i.i.d.，最后迭代点可能仍表现良好；但若维度随迭代次数增长或噪声结构复杂，则平均迭代或特殊步长策略（如 Jain et al., 2021; Liu and Zhou, 2024 提出的方案）会更稳妥。
对于非 i.i.d.噪声的应对：当噪声具有状态依赖或时间异质性时（如强化学习中的策略评估、在线广告中的分布漂移），应考虑使用平均值或采用更保守的步长衰减策略。

未来研究方向

高维扩展：固定维度 $d>1$ 时，确定性的多变量设置中最后迭代点是否最优？这是论文明确提出的开放问题。
有界噪声模型：本文构造的反例利用了数量级为 $\Theta(1/\eta) = \Theta(\sqrt{n})$ 的大噪声值。若噪声被一致有界（uniformly bounded），对数因子是否还能避免？
自适应步长：在非固定步长（如递减步长或自适应步长）下，噪声结构的对称性是否仍起关键作用？
更弱的结构假设：是否存在介于 “仅二阶矩控制” 和 “完全 i.i.d.” 之间的中间假设（如某种弱相依性或局部时间齐次性），也足以保证最优速率？

总结

本文通过对一维随机次梯度方法最后迭代点的深入分析，给出了最优收敛速率的精确条件：当且仅当噪声同时满足时间齐次性和状态独立性时，最后迭代点才能在标准固定步长下达到 $1/\sqrt{n}$ 的最优速率，否则对数因子不可避免。这一结果不仅从理论上澄清了长期争议，也为实践中是否使用平均迭代提供了明确的决策依据。论文所发展的分析技术，如基于区间投影的支配链构造和 Foster-Lyapunov 漂移参数设计，为约束随机优化的精细分析开辟了新路径。