arXiv:2604.10373math.OCcs.LG2026-04中稿 · ICLR被引 1

组合数据重排与迭代外推,显著降低常步长SGD的偏差。

Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD

论文配图:Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD
图 1 · 摘自论文原文
  • 通过数据重排与外推结合,优化常步长SGD的收敛性。
  • 理论证明偏差呈立方级下降,且均方误差更优。
  • 适用于对抗鲁棒性、多智能体学习等非单调变分问题。

从对抗鲁棒性到多智能体学习,许多机器学习任务可建模为有限和极小极大优化或更一般的变分不等式问题(VIPs)。尽管存在常数阶收敛误差,常步长随机梯度方法因其简洁性和可扩展性仍被广泛应用。实践中两类经典技巧近期受到关注:数据随机重排(Random Reshuffling)和基于迭代的Richardson-Romberg外推。前者改善估计解的均方误差(MSE),后者在偏向上实现二阶修正。本文首次证明二者结合能带来更强效果:不仅保持更优的MSE,还使偏差实现立方级提升。我们从两步分析:(i) 淡化重排引入的离散噪声,借助连续状态马尔可夫链工具建立新的大数定律与中心极限定理;(ii) 利用谱张量技术证明外推可消除由重排梯度算子带来的偏差,改善渐近行为。大量实验验证理论,实际中表现出显著加速。

原文摘要 · Abstract (English)

From adversarial robustness to multi-agent learning, many machine learning tasks can be cast as finite-sum min-max optimization or, more generally, as variational inequality problems (VIPs). Owing to their simplicity and scalability, stochastic gradient methods with constant step size are widely used, despite the fact that they converge only up to a constant term. Among the many heuristics adopted in practice, two classical techniques have recently attracted attention to mitigate this issue: \emph{Random Reshuffling} of data and \emph{Richardson--Romberg extrapolation} across iterates. Random Reshuffling sharpens the mean-squared error (MSE) of the estimated solution, while Richardson-Romberg extrapolation acts orthogonally, providing a second-order reduction in its bias. In this work, we show that their composition is strictly better than both, not only maintaining the enhanced MSE guarantees but also yielding an even greater cubic refinement in the bias. To the best of our knowledge, our work provides the first theoretical guarantees for such a synergy in structured non-monotone VIPs. Our analysis proceeds in two steps: (i) we smooth the discrete noise induced by reshuffling and leverage tools from continuous-state Markov chain theory to establish a novel law of large numbers and a central limit theorem for its iterates; and (ii) we employ spectral tensor techniques to prove that extrapolation debiases and sharpens the asymptotic behavior even under the biased gradient oracle induced by reshuffling. Finally, extensive experiments validate our theory, consistently demonstrating substantial speedups in practice.

SGD优化理论随机梯度偏差分析

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