Random Reshuffling Dominates Stochastic Gradient Descent

Zijian Liu

math.OCJun 30, 2026

Random Reshuffling Dominates Stochastic Gradient Descent

Authors: Zijian Liu

Organizations: Stern School of Business, New York University

Abstract

Stochastic Gradient Descent ( $\textsf{SGD}$ ) is one of the most classical optimization algorithms with favorable theoretical guarantees, yet the practical implementation of $\textsf{SGD}$ differs subtly from its well-known form and is often referred to as Shuffling Stochastic Gradient Descent ( $\textsf{Shuffling SGD}$ ). A particularly popular strategy in $\textsf{Shuffling SGD}$ is Random Reshuffling ( $\textsf{RR}$ ), which has achieved great empirical success across numerous experiments. Despite its strong performance, $\textsf{RR}$ has long been considered a heuristic due to a lack of theoretical support. Over the last decade, people have finally established provable convergence rates for $\textsf{RR}$ , thus justifying its observed superiority. However, for smooth convex optimization, two clouds over the convergence theory of $\textsf{RR}$ remain to this day. More precisely, according to the current theory, $\textsf{Shuffling SGD}$ under $\textsf{RR}$ converges only when the stepsize is smaller than a threshold proportional to $1/n$ , where $n$ is the number of summands in the objective (or the number of data points). Consequently, the optimally tuned theoretical rate of $\textsf{Shuffling SGD}$ under $\textsf{RR}$ is strictly worse than that of $\textsf{SGD}$ when the number of epochs is smaller than another threshold proportional to $n$ . These two restrictions heavily limit the applicability of existing theories and leave a critical mismatch with practice. In this work, for the first time, we prove that $\textsf{RR}$ dominates $\textsf{SGD}$ in smooth convex optimization under any reasonable stepsize after any finite number of epochs, thereby addressing a longstanding open question.

Explore similar work

Sep 8, 2026math.OC

The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives

We study the time-uniform convergence of the raw iterate of standard stochastic gradient descent (SGD) for unconstrained smooth convex objectives. We prove that, under standard noise assumptions, the time-uniform convergence rate gets arbitrarily close to

\sqrt{\log n / n}

but never reaches it. More specifically, we prove that for every positive, eventually nondecreasing sequence

h

satisfying

h(n) = o(\sqrt{n})

, a bound of order

h(n)/\sqrt{n}

, holding simultaneously for all

n

with probability at least

1-α

and uniformly over the problem class, is achievable if and only if

\sum_{j = 1}^{\infty} \frac{1}{h(2^j)^2} < \infty.

The constructive sufficiency result follows from a dyadic horizon-free schedule together with an additive conditional-restart inequality. The necessity counterpart applies to every deterministic nonnegative schedule and holds even for a one-dimensional analytic smooth convex objective with Gaussian noise.

Ruijie Li, Kang Chen, Tianyu Wang

Stochastic Gradient Descent Stochastic Objectives

Ask PDF

Jul 16, 2026cs.LG

What's in a Smoothness Constant? Tighter Rates for Local SGD with Bounded Second-order Heterogeneity

Local SGD, also known as Federated Averaging, is a widely used distributed optimization algorithm. Although Local SGD often outperforms alternatives such as Mini-batch SGD in practice, theory still only partially explains when and why local updates help under realistic data heterogeneity. Recent work by [Patel et al., 2025] shows that a bounded second-order heterogeneity assumption captures the efficiency of Local SGD for strongly convex objectives, and conjectures that the same principle extends to the general convex setting. In this paper, we prove this conjecture by establishing an improved convergence guarantee for Local SGD on general convex objectives under bounded second-order heterogeneity. We also improve the best-known lower bounds for Local SGD in this setting, showing that our upper bounds are nearly tight. Together, these results provide a sharper, more fine-grained convergence theory for Local SGD. As a further application of our techniques, we provide a lower bound for serial SGD with replacement, showing how second-order heterogeneity captures the impact of rare high-curvature clients.

Kumar Kshitij Patel, Rustem Islamov, Sebastian U Stich +3

Stochastic Gradient Descent Smoothing Federated Averaging Heterogeneity

Ask PDF

May 30, 2026math.OC

In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise

Many stochastic gradient methods are believed not to converge when the noise in stochastic gradients has only a finite

p

-th moment for

p\in\left(1,2\right)

, a setting known as the heavy-tailed noise assumption. However, some recent studies have found that Stochastic Gradient Descent (

\textsf{SGD}

), without any modification to its update rule, can surprisingly converge in expectation for convex problems with bounded domains, highlighting the potential of classical stochastic gradient methods. Inspired by this recent progress, we provide a comprehensive study of stochastic optimization under heavy-tailed noise and establish new in-expectation convergence results for Stochastic Mirror Descent (

\textsf{SMD}

) and Accelerated Stochastic Mirror Descent (

\textsf{ASMD}

) in convex optimization, and for

\textsf{SGD}

and Stochastic Gradient Descent with Momentum (

\textsf{SGDM}

) in nonconvex optimization. Notably, our results not only hold without algorithmic changes but also avoid restrictive assumptions, such as bounded domains, imposed in prior work. More importantly, our analysis provides a new, elegant, and powerful framework for studying heavy-tailed stochastic optimization, opening a new route to understanding first-order stochastic gradient methods.

Zijian Liu

Stochastic Smooth Convex Optimization Stochastic Gradient Descent Convex Optimization Stochastic

Ask PDF