为随机梯度下降设计了基于轨迹的实时停止规则,无需预设迭代次数。
Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequences
- 用非负超鞅构造可随时验证的置信序列,实现持续监控下的有效停止
- 在凸与非凸优化中分别给出加权次优性与一阶平稳性的时不变保证
- 适用于无先验迭代信息的在线场景,适合实际部署中的自动终止需求
在仅依赖观测轨迹的前提下,以在线方式决定随机梯度下降(SGD)何时停止,是一个具有重要应用意义但理论挑战巨大的问题。传统SGD理论仅在预设的迭代次数上提供保证,无法根据运行轨迹判断是否继续计算。本文通过构建任意时刻有效的置信序列,填补这一长期空白:只要当前性能指标的置信上界低于用户设定容差,即可安全停止。该置信序列基于非负超鞅构造,具有时间一致性,仅依赖可观测的路径数据,无需预知优化周期。在凸优化中,该方法在一般步长策略下,对投影式SGD的加权次优性提供了任意时刻有效的证明,不假设光滑性或强凸性;在非凸情形下,于光滑条件下给出加权一阶平稳性的时不变证书。进一步分析了标准步长策略下停止时间的复杂度。据我们所知,这是首个在凸与非凸设置下均基于轨迹、提供统计有效且时间一致停止规则的框架。
原文摘要 · Abstract (English)
The problem of stopping stochastic gradient descent (SGD) in an online manner, based solely on the observed trajectory, is a challenging theoretical problem with significant consequences for applications. While SGD is routinely monitored as it runs, the classical theory of SGD provides guarantees only at pre-specified iteration horizons and offers no valid way to decide, based on the observed trajectory, when further computation is justified. We address this longstanding gap by developing anytime-valid confidence sequences for stochastic gradient methods, which remain valid under continuous monitoring and directly induce statistically valid, trajectory-dependent stopping rules: stop as soon as the current upper confidence bound on an appropriate performance measure falls below a user-specified tolerance. The confidence sequences are constructed using nonnegative supermartingales, are time-uniform, and depend only on observable quantities along the SGD trajectory, without requiring prior knowledge of the optimization horizon. In convex optimization, this yields anytime-valid certificates for weighted suboptimality of projected SGD under general stepsize schedules, without assuming smoothness or strong convexity. In nonconvex optimization, it yields time-uniform certificates for weighted first-order stationarity under smoothness assumptions. We further characterize the stopping-time complexity of the resulting stopping rules under standard stepsize schedules. To the best of our knowledge, this is the first framework that provides statistically valid, time-uniform stopping rules for SGD across both convex and nonconvex settings based solely on its observed trajectory.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。