随机次梯度方法最后迭代点的新界

New Bounds for the Last Iterate of the Stochastic subGradient Method

arXiv: 2606.24879v1

论文信息

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

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

发布日期: 2026-06-23

arXiv ID: 2606.24879v1

PDF 链接: 下载 PDF

3 分钟速览

  • 研究问题：随机次梯度方法（SsGM）在固定步长 η=Θ(1/n)\eta = \Theta(1/\sqrt{n}) 下，最后迭代点的收敛阶能否达到与平均迭代相同的最优速率 1/n1/\sqrt{n}，还是必然存在额外的 log⁡n\log n 因子？
  • 核心方法：通过对一维凸 Lipschitz 目标构造辅助随机过程，利用 Foster–Lyapunov 漂移不等式和 Markov 链不变测度，证明在噪声独立同分布时最后迭代达到最优阶；同时构造时间同质/状态独立反例，显示只有同时满足两种对称性才能消除对数因子。
  • 关键结果：当加性噪声既是状态独立又是时间同质时，固定步长最后迭代的期望优化误差上界为 C/nC/\sqrt{n}（定理 2）；反之，仅保持方差有界而缺少任一种对称性时，下界至少为 Ω(log⁡n/n)\Omega(\log n/\sqrt{n})（定理 3），从而否定回答 Koren 和 Segal (2020) 的开放问题。
  • 主要局限：结论仅适用于一维问题，且在下界构造中噪声的无界性（幅度达到 Θ(1/η)=Θ(n)\Theta(1/\eta)=\Theta(\sqrt{n})）是必要的；论文未讨论多维或噪声几乎必然有界的情形。
  • 适合读者：从事随机优化理论、收敛性分析的研究生和学者，以及对优化算法最后迭代行为感兴趣的研究者。

论文背景和研究动机

随机次梯度方法（SsGM）是解决如下约束随机凸优化问题的基础算法：

min⁡x∈Xf(x),f 凸且 L-Lipschitz,\min_{x\in\mathcal{X}} f(x), \quad f\ \text{凸且}\ L\text{-Lipschitz},

每次迭代利用一个无偏但含噪声的次梯度估计进行更新，并投影回可行集 X\mathcal{X}。当迭代次数 nn 事先已知时，经典做法是采用固定步长 η=Θ(1/n)\eta = \Theta(1/\sqrt{n})，并输出前 nn 步迭代的平均点 1n∑i=1nXi\frac{1}{n}\sum_{i=1}^{n}X_i，其期望优化误差的阶为 1/n1/\sqrt{n}，达到该类问题的信息论下界。

然而实际应用中人们更常直接使用最后一个迭代点 XnX_n，因为其实现简单，且经验性能往往优于平均点。但最后迭代的理论保证更为困难：已知固定步长下最好的上界为 O(log⁡n/n)O(\log n/\sqrt{n})，比平均点差一个对数因子（Shamir & Zhang, 2013）。这个对数因子是否必要？Koren 和 Segal (2020) 指出，在固定维数，特别是 d=1d=1 时，可能可以将其去除，并将此列为开放问题。本文正是要彻底解决该问题。

核心方法和技术细节

问题设置与算法

考虑一维凸函数 ff 在闭凸集 X⊆R\mathcal{X}\subseteq\mathbb{R} 上极小化。算法从 X1X_1 开始，迭代

Xk+1=ΠX(Xk−η(Gk+Wk)),X_{k+1} = \Pi_{\mathcal{X}}\bigl(X_k - \eta(G_k + W_k)\bigr),

其中 Gk∈∂Xf(Xk)∩[−L,L]G_k \in \partial_{\mathcal{X}} f(X_k)\cap[-L,L] 是 ff 在 XkX_k 的相对次梯度，WkW_k 为加性噪声，满足 E[Wk∣Fk]=0\mathbb{E}[W_k\mid\mathcal{F}_k]=0 和 E[Wk2∣Fk]≤σ2\mathbb{E}[W_k^2\mid\mathcal{F}_k]\le \sigma^2（Assumption 3）。更精细的分析要求噪声由概率核 Qk(x,⋅)Q_k(x,\cdot) 生成，即给定当前状态 xx 时噪声的分布。

本文引入三种结构性对称假设：

  • 时间同质（Assumption 5）：Qk(x,⋅)Q_k(x,\cdot) 不依赖 kk；
  • 状态独立（Assumption 6）：Qk(x,⋅)Q_k(x,\cdot) 不依赖 xx；
  • 同时满足：存在同一个中心化分布 μ\mu 使得 Qk(x,⋅)≡μQ_k(x,\cdot)\equiv\mu，此时噪声序列独立同分布（i.i.d.）。

上界证明（定理 2）

当噪声满足时间同质和状态独立时，证明最后迭代误差为 O(1/n)O(1/\sqrt{n})。证明的核心思路是：

  1. 通过经典的 regret 分解，存在某个中间时刻 k⋆k_\star 使得 E[Δ(Xk⋆)]\mathbb{E}[\Delta(X_{k_\star})] 已达 O(1/n)O(1/\sqrt{n}) 阶（类似于平均点分析）。
  2. 证明从 k⋆k_\star 往后的迭代不会显著退化，即 E[(f(Xk)−f(Xk⋆))+]≤(L+σ)2η\mathbb{E}[(f(X_k)-f(X_{k_\star}))_+]\le (L+\sigma)^2\eta 对所有 k≥k⋆k\ge k_\star 成立（见引理 10 和式 (4)）。
  3. 该退化控制是通过在条件期望下研究从 Xk⋆X_{k_\star} 出发的 Markov 链，构造一左一右两个支配随机过程 Zk(1),Zk(2)Z_k^{(1)},Z_k^{(2)}，它们各自在一个半无限区间上演化，且满足一个精心设计的 Foster–Lyapunov 漂移不等式： PB(z)−B(z)≤−∫0zm(s) ds+Cη,PB(z) - B(z) \le -\int_0^z m(s)\,\mathrm{d}s + C\eta, 其中 B(z)=z2/(2η)+2LzB(z)=z^2/(2\eta)+2Lz 为 Lyapunov 函数，C=σ2/2+LσC= \sigma^2/2 + L\sigma（见命题 6 和 claim 8）。
  4. 利用链的 Feller 性和紧性，存在不变测度 π\pi，对漂移不等式积分得到 ∫(∫0zm(s)ds) π(dz)≤Cη\int (\int_0^z m(s)ds)\,\pi(dz) \le C\eta，再通过单调性与初始状态比较，最终推出对所有 k≥k⋆k\ge k_\star 的期望退化被 η\eta 控制。

因为 η=Θ(1/n)\eta = \Theta(1/\sqrt{n})，退化量 O(η)O(\eta) 正好是 O(1/n)O(1/\sqrt{n})，不会破坏 k⋆k_\star 处的收敛阶。因此最后迭代 XnX_n 的误差阶与 Xk⋆X_{k_\star} 相同，均为 1/n1/\sqrt{n}。

下界构造（定理 3）

下界分为两部分，分别展示仅时间同质或仅状态独立时，O(log⁡n/n)O(\log n/\sqrt{n}) 的下界不可避免。两种构造共享一个基本思想：

  • 设置 f(x)=max⁡{x,0}f(x)=\max\{x,0\}，可行域 [−2,1][-2,1]，最优解集为 [−2,0][-2,0]。
  • 设计一个标签 j=1,…,Mj=1,\dots,M（M≈1/(16η)=Θ(n)M\approx 1/(16\eta)=\Theta(\sqrt{n})），每个标签对应一个 罕见大幅噪声 −4j-4j，发生的概率约为 1/(64j2)1/(64j^2)。
  • 当该罕见噪声在距离结束还剩约 jj 步时被采样，会将当前迭代点推向正半轴，且之后所有噪声为 00，次梯度为 11，最终在终止时产生 2ηj2\eta j 的误差。
  • 对所有 jj 求和，得到期望误差至少为 ∑j(1/j2)⋅ηj≈ηlog⁡(1/η)=Ω(log⁡n/n)\sum_j (1/j^2) \cdot \eta j \approx \eta \log(1/\eta) = \Omega(\log n/\sqrt{n})。

时间同质但状态依赖的构造：在不同的 “标记状态” sj=−(j+1)ηλs_j = -(j+1)\eta\lambda 上定义不同的噪声分布，罕见噪声仅在这类状态上采样。通过普通噪声 −λ-\lambda 将过程逐步从 sn−1s_{n-1} 向下驱动到 sjs_j，一旦到达 sjs_j，以正概率出现 −4j-4j，其他状态噪声为零。由于过程依赖状态，噪声核是时间同质但不是状态独立的。

状态独立但时间非齐次的构造：将噪声分布与特定时刻 kj=n−jk_j=n-j 绑定。在这些时刻，WkjW_{k_j} 以正概率取 −4j-4j，其余时刻噪声为零。开始时 X1=0X_1=0，在所有特殊时刻之前噪声为零，过程保持在 00；到达 kjk_j 时，以正概率出现罕见噪声，使最终误差变大。此时核是状态独立但不是时间同质的。

两种构造均满足零均值和一致有界方差（例如分别 σ2=3\sigma^2=3 和 σ2=1/2\sigma^2=1/2），且只有同时要求时间同质与状态独立才能消除对数因子。

创新点和贡献

  1. 最优上界：首次在同时具备时间同质性和状态独立性的假设下，证明一维 SsGM 的最后迭代在固定步长 O(1/n)O(1/\sqrt{n}) 下的期望优化误差精确为 O(1/n)O(1/\sqrt{n})，不存在额外对数因子，且常数仅依赖于初始距离、Lipschitz 常数和噪声方差（定理 2）。该结果推广了 Koren 和 Segal (2020) 对绝对值函数的特例。

  2. 精细下界：通过显式构造两个反例，严格证明了仅满足方差有界（甚至再加上时间同质或状态独立之一）时，最后迭代的下界至少为 Ω(log⁡n/n)\Omega(\log n/\sqrt{n})，从而否定了在一般噪声条件下的 O(1/n)O(1/\sqrt{n}) 猜想（定理 3）。这揭示了最后迭代收敛性研究中噪声结构的重要性。

  3. 分析方法论创新：引入 Markov 链的 Foster–Lyapunov 漂移技巧，通过设计合适的 Lyapunov 函数和不变测度来控制退化量，避免了传统分析中依赖平均的局限性。该方法为后续研究提供了新的工具。

局限与待解决问题

  1. 维度限制：所有结果均针对一维情形。论文未讨论 d≥2d\ge 2 时最后迭代的精确阶。作者在结尾指出，一个有趣的开问题是确定固定维数（d>1d>1）下最后迭代是否最优，这暗示多维推广并非平凡。

  2. 噪声无界性：下界构造中罕见噪声的幅度为 Θ(1/η)=Θ(n)\Theta(1/\eta)=\Theta(\sqrt{n})，对应方差虽有限但无界。若额外要求噪声几乎必然有界（如 ∣Wk∣≤B|W_k|\le B），对数因子是否仍然必要？论文未有结论。

  3. 仅考虑固定步长：本文专注于标准固定步长 η=Θ(1/n)\eta=\Theta(1/\sqrt{n})，未涉及递减步长或其他自适应步长在前述对称性假定下的表现。

  4. 常数依赖性：上界中的常数直接依赖于 LL 和 σ\sigma，未讨论是否可达到最小可能常数。

  5. 实践建议部分缺失：由于本文为纯理论工作，没有直接的系统实现或数值验证，因此无法给出具体的实践建议。但结论可为算法设计者提供指导：若对噪声的统计结构有额外了解（如 i.i.d.），则可放心使用最后迭代；否则，为保底最优性或许仍需考虑平均或特定步长策略。

总体而言，这篇论文对随机次梯度方法最后迭代的收敛性给出了清晰、完整的刻画，厘清了一维情况下的理论极限，并为未来多维或更复杂噪声结构的研究奠定了基础。