High Probability Guarantees for Random Reshuffling

arXiv:2311.11841v4 Announce Type: replace-cross Abstract: We consider the stochastic gradient method with random reshuffling (mathsf{RR}) for tackling smooth nonconvex optimization problems. mathsf{RR} finds broad applications in practice, notably in training neural networks. In this work, we provide high probability complexity guarantees for this method. First, we establish a high probability ergodic sample complexity result (without taking expectation) for finding an arepsilon-stationary point. Our derived complexity matches the best existing in-expectation one up to a logarithmic term while imposing no additional assumptions nor modifying mathsf{RR}'s updating rule. Second, building on this analysis, we propose a simple stopping criterion embedded with a computable stopping test for mathsf{RR} (denoted as mathsf{RR}-mathsf{sc}). This criterion is guaranteed to be triggered after a finite number of iterations, enabling us to prove the same order high probability complexity for the returned last iterate. The fundamental ingredient in deriving the aforementioned results is a new concentration property for random reshuffling, which could be of independent interest. Finally, we conduct numerical experiments on small neural network training to support our theoretical findings.

Related

• Gradient Descent's Last Iterate is Often (slightly) Suboptimal
• Fisher-Geometric Diffusion in Stochastic Gradient Descent: Optimal Rates, Oracle Complexity, and Information-Theoretic Limits
• Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis
• Momentum Further Constrains Sharpness at the Edge of Stochastic Stability
• Large Spikes in Stochastic Gradient Descent: A Large-Deviations View
• A short proof of near-linear convergence of adaptive gradient descent under fourth-order growth and convexity

Source: arXiv cs.LG | 2026-04-17