High-Probability Convergence of SGD via Batched Updates
Abstract
Stochastic gradient descent (SGD) is the primary workhorse for large-scale optimization. While the average behavior of its iterates, typically characterized by mean-squared error bounds, is well-understood, obtaining high-probability guarantees for the last iterate remains challenging. Prior approaches to this problem have either imposed restrictive assumptions (such as bounded domains or gradients) or relied on complex proofs involving auxiliary sequences. In this work, we propose Batched SGD, a simple variant that partitions online samples into epochs and performs a single update per epoch using a refined, low-variance gradient estimate. Our main contribution demonstrates that this batching mechanism enables a surprisingly simple high-probability analysis that avoids both restrictive assumptions and auxiliary sequences. Under standard smoothness and norm-sub-Gaussian noise assumptions, we establish near-optimal rates for both strongly convex and non-convex objectives. Furthermore, we show that our batching idea extends naturally to federated learning (FL). We provide the first high-probability guarantees for FL, achieving logarithmic communication complexity, linear speedup in the number of agents, and resilience to data heterogeneity.
Related
- Online adaptive non-intrusive model reduction via manifold interpolation and subspace updates: application to FSI convergence acceleration
- Structural conditions on trust-region radius updates. Part I: first-order convergence and complexity
- Structural conditions on trust-region radius updates. Part II: second-order convergence and asymptotic radius behaviour
- Quantum Message Passing Convergence and Vanishing Block-Error Probability for Random LDPC Codes
- Dynamics of Stochastic Momentum with Sparse Updates in High Dimensions
BibTeX
@misc{zhu2026highprobability,
title = {{High-Probability Convergence of SGD via Batched Updates}},
author = {Feng Zhu and Robert W. Heath Jr. and Aritra Mitra},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.12765},
eprint = {2609.12765},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.12765},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - High-Probability Convergence of SGD via Batched Updates
AU - Feng Zhu
AU - Robert W. Heath Jr.
AU - Aritra Mitra
PY - 2026
DA - 2026/09/11
PB - arXiv
DO - 10.48550/arxiv.2609.12765
UR - https://arxiv.org/abs/2609.12765
AB - Stochastic gradient descent (SGD) is the primary workhorse for large-scale optimization. While the average behavior of its iterates, typically characterized by mean-squared error bounds, is well-understood, obtaining high-probability guarantees for the last iterate remains challenging. Prior approaches to this problem have either imposed restrictive assumptions (such as bounded domains or gradients) or relied on complex proofs involving auxiliary sequences. In this work, we propose Batched SGD, a simple variant that partitions online samples into epochs and performs a single update per epoch using a refined, low-variance gradient estimate. Our main contribution demonstrates that this batching mechanism enables a surprisingly simple high-probability analysis that avoids both restrictive assumptions and auxiliary sequences. Under standard smoothness and norm-sub-Gaussian noise assumptions, we establish near-optimal rates for both strongly convex and non-convex objectives. Furthermore, we show that our batching idea extends naturally to federated learning (FL). We provide the first high-probability guarantees for FL, achieving logarithmic communication complexity, linear speedup in the number of agents, and resilience to data heterogeneity.
ER -