Research map / Optimization / Nonconvex and smooth optimization
Random Reshuffling: Simple Analysis with Vast Improvements
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| reshuffle the data without replacement each epoch rather than sample with replacement | finite-sum optimization · Strongly convex objectives | gradient evaluations to ε-accuracy: K_{\mathrm{RR}} \geq \frac{ L \sqrt{n}}{\e^2} ( \sqrt{n}+ \frac{\sigma}{\e} ); K_{\mathrm{SGD}} \geq \frac{L}{\e^2} (1+ | Helped |
| shuffle the data once and reuse the permutation rather than reshuffle every epoch | Random Reshuffling (RR) · Strongly convex objectives | squared distance to optimum | No clear effect |
| use a deterministic fixed ordering rather than a randomized permutation | data-permutation optimization · regularized logistic regression on real-sim, w8a, and RCV1 | convergence | Hurt |
| use minibatches of size τ | Random Reshuffling (RR) versus SGD · Finite-sum optimization | variance: σ_*^2 decreases as O(1/τ) and σ̃_* as O(1/τ^2) | Helped |
| use the shuffling variance instead of the standard variance at the optimum to characterize RR | Random Reshuffling (RR) · Strongly convex objectives | convergence neighborhood: \frac{\gamma\mu n}{8}\sigma_{\ast}^2 \le \tilde{\sigma}_{\ast} \leq \frac{\gamma L n}{4} \sigma_{\ast}^2 | Helped |
Closest papers by meaning
- Don't Compress Gradients in Random Reshuffling: Compress Gradient Differences (NeurIPS 2024 · similarity 0.90)
- Reshuffling Resampling Splits Can Improve Generalization of Hyperparameter Optimization (NeurIPS 2024 · similarity 0.88)
- Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization (ICML 2025 · similarity 0.88)
- Stochastic Optimization with Arbitrary Recurrent Data Sampling (ICML 2024 · similarity 0.88)
- Demystifying SGD with Doubly Stochastic Gradients (ICML 2024 · similarity 0.88)
- Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity (NeurIPS 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.