arXiv:2608.25551cs.LGmath.OC2026-08

为随机优化设计可自适应停止的置信区间,让SGD提前停机仍保证精度。

Beyond Optimal Rates in Stochastic Optimization: Trajectory-Adaptive Stopping Rules

论文配图:Beyond Optimal Rates in Stochastic Optimization: Trajectory-Adaptive Stopping Rules
图 1 · 摘自论文原文
  • 基于梯度轨迹构建动态置信序列,实时评估优化误差。
  • 在最坏情况下仍保持1/t的最优衰减速率,实际中更快收敛。
  • 适合需要高效停止策略的机器学习实践者,如调参与资源受限场景。

随机梯度下降(SGD)通常在运行前设定固定迭代次数,但实际停止决策依赖于动态轨迹。这种差异导致经典固定时间分析无法适用于数据驱动的停止时间,而基于最坏情况推导的确定性时长往往过于保守。本文针对强凸随机优化问题,构建了完全可观测的、轨迹自适应的上界置信序列,同时覆盖最后迭代点到最优解的平方距离和加权平均的次优性。这些边界在时间上统一成立,最坏情况下达到最优的1/t衰减率(仅含对数因子),并能适应实际梯度波动,使算法可在认证精度达标时立即停止,且统计有效性不受影响。方法将演化中的SGD轨迹视为序贯实验,利用观测数据累积关于未知优化误差的证据。为此,提出新的递归置信序列构造技术,以及适用于条件均值和可预测范围随时间变化、可能无界过程的一般时间一致经验伯恩斯坦不等式。进一步将该方法扩展至小批量SGD,利用每批次内真实二阶矩结构提升效率。数值实验表明,所提停止规则所需迭代次数比自然确定性时长少多个数量级。

原文摘要 · Abstract (English)

Stochastic gradient descent (SGD) is typically analyzed at a deterministic horizon chosen before the algorithm is run, even though practical stopping decisions are made adaptively by inspecting the evolving trajectory. This mismatch creates a fundamental certification problem: fixed-time guarantees do not generally remain valid at data-dependent stopping times, while deterministic horizons derived from worst-case bounds can be highly conservative. We address this problem for strongly convex stochastic optimization by constructing fully observable, trajectory-adaptive upper confidence sequences for the squared distance of the last iterate to the optimizer and the suboptimality of a weighted average. These bounds hold simultaneously over time, attain the optimal $1/t$ decay rate up to iterated-logarithmic factors in the worst case, and adapt to the realized stochastic gradients, allowing SGD to stop as soon as a prescribed accuracy is certified without sacrificing statistical validity. Our approach treats the evolving SGD trajectory as a sequential experiment whose observations provide evidence about the unknown optimization error. To formalize this perspective, we develop new recursive confidence-sequence techniques and a general time-uniform empirical Bernstein inequality for adapted processes with time-varying conditional means and predictable ranges that may grow without bound. We further extend these confidence-sequence constructions to minibatch SGD, with the empirical Bernstein bounds exploiting the realized second-moment structure within each minibatch. Numerical experiments show that the resulting stopping rules can require several orders of magnitude fewer iterations than natural deterministic horizons.

随机优化自适应停止置信序列SGD改进

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。