---
title: "Random Reshuffling Dominates SGD in Convex Optimization: A Decades-Old Mystery Resolved"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2606.32005v1"
permalink: "https://feed.astralor.com/items/itm_a465d0213665d997ab2ea34c"
published: "2026-06-30T17:38:22.000Z"
score: 57
channel: "ai"
tags: ["Convex Optimization","Theoretical Proof","Stochastic Gradient Descent","Shuffling SGD"]
---

# Random Reshuffling Dominates SGD in Convex Optimization: A Decades-Old Mystery Resolved

## At a glance

A paper on arXiv proves for the first time that Random Reshuffling (RR), a popular variant of shuffling SGD, dominates standard SGD in smooth convex optimization under any reasonable stepsize after any finite number of epochs. Previous theory required a stepsize threshold of O(1/n) and predicted worse rates for smaller epochs, contradicting empirical success. This work resolves a long-standing open question and provides rigorous theoretical justification for RR's superiority.

## Key points

- Standard SGD theory assumes i.i.d. sampling, but practice uses shuffling (RR) without replacement; RR lacked theoretical backing for decades.
- Prior theory required step size ≤ 1/n for RR convergence and predicted worse rates than SGD when epochs < n, contradicting experiments.
- This work overcomes both restrictions, proving RR dominates SGD under any reasonable stepsize and any finite epoch count with faster convergence.

## Full text

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.

---

Verify against the original before citing; curated by Astral Feed: https://feed.astralor.com/items/itm_a465d0213665d997ab2ea34c