High-Probability Convergence of SGD via Batched Updates

arXiv:2609.12765v1 Announce Type: cross 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

• High Probability Guarantees for Random Reshuffling
• The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives
• Accelerating SGDM via Learning Rate and Batch Size Schedules: A Lyapunov-Based Analysis

Source: arXiv cs.LG | 2026-09-14