arXiv：cs.LG· Zijun Chen, Zihan Zhang·· 4 小时前
RR-SGD 大步长最后迭代收敛性获证：步长限制去掉 1/n 因子
Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent
AI 导读
研究为 RR-SGD 在无约束问题上的最后迭代建立了期望目标间隙界，常量分量步长满足 0<η≲1/(L(1+log(nK)))，K 为 epoch 数。通过在随机比较点保留采样偏差，步长限制中显式的 1/n 因子被移除。结合已有小步长界，该结果在忽略对数因子后与对应的平均迭代收敛速率持平。
正文
Abstract:Random reshuffling stochastic gradient descent (RR-SGD) is widely used for finite-sum optimization in machine learning. For convex $L$-smooth components, recent work establishes convergence guarantees for an averaged iterate with component stepsizes as large as order $1/L$. However, the final iterate is a natural output in practice, and existing last-iterate guarantees in this setting require stepsizes that scale inversely with the number of components $n$. We establish an expected objective-gap bound for the last iterate of standard RR-SGD on unconstrained problems with a constant component stepsize satisfying $0<\eta\lesssim 1/(L(1 + \log(nK)))$, where $K$ is the number of epochs. By retaining the sampling bias at random comparison points, we remove the explicit $1/n$ factor from the stepsize restriction. Combined with existing small-step bounds, our result matches the corresponding averaged-iterate convergence rate up to logarithmic factors.
| Subjects: | Optimization and Control (math.OC); Machine Learning (cs.LG); Machine Learning (stat.ML) |
| Cite as: | arXiv:2610.19444 [math.OC] |
| (or arXiv:2610.19444v1 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2610.19444 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Zijun Chen [view email]
[v1]
Wed, 14 Oct 2026 02:34:06 UTC (31 KB)
来源：arXiv：cs.LG · arxiv.org