提出最优偏差界，揭示SGD在任意固定步长下的理论极限。
Bias-Optimal Bounds for SGD: A Computer-Aided Lyapunov Analysis
- 构造简单李雅普诺夫能量函数，分析收敛性
- 在所有常数步长下实现与确定梯度下降相同的偏差率
- 适用于临界和大步长情形，无需额外方差假设
随机梯度下降（SGD）的非渐近分析通常将误差分解为偏差项与方差项。本文聚焦于偏差部分，研究在仅假设目标函数强凸且光滑的前提下，SGD能否达到确定性梯度下降的最优收敛速率。我们推导出新的偏差最优界，即偏差项与梯度下降的最坏情况速率一致。该结果对所有常数步长 $γL \in (0,2)$ 成立，涵盖此前未被探索的临界与大步长区域，无需额外方差假设。通过构造一个简单的李雅普诺夫能量函数并利用其单调性获得紧致收敛保证。参数设计基于性能估计问题框架，并用数值证据支持对应方差项的最优性。
原文摘要 · Abstract (English)
The non-asymptotic analysis of Stochastic Gradient Descent (SGD) typically yields bounds that decompose into a bias term and a variance term. In this work, we focus on the bias component and study the extent to which SGD can match the optimal convergence behavior of deterministic gradient descent. Assuming only (strong) convexity and smoothness of the objective, we derive new bounds that are bias-optimal, in the sense that the bias term coincides with the worst-case rate of gradient descent. Our results hold for the full range of constant step-sizes $γL \in (0,2)$, including critical and large step-size regimes that were previously unexplored without additional variance assumptions. The bounds are obtained through the construction of a simple Lyapunov energy whose monotonicity yields sharp convergence guarantees. To design the parameters of this energy, we employ the Performance Estimation Problem framework, which we also use to provide numerical evidence for the optimality of the associated variance terms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。