Research map / Optimization / Nonconvex and smooth optimization
A Unified Analysis of Stochastic Gradient Descent with Arbitrary Data Permutations and Beyond
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a unified convergence framework for permutation-based SGD based on a new inter-epoch order-error assumption, covering arbitrary, random-reshuffling, one-permutation and GraB orderings, and extends it to regularized-participation federated learning with client ordering.
Problem
Convergence of permutation-based SGD and federated learning with regularized participation depends on example/client orders, but existing unified analyses cannot cover dependent permutations such as GraB, where orders across epochs are correlated.
Approach
Replaces the per-epoch order-error bound with a recursive assumption that bounds the squared order error at epoch q by weighted sums of earlier-epoch order errors and gradient norms, which captures inter-epoch permutation dependence and yields a unified theorem applicable to AP, RR, OP and GraB variants; the framework is then adapted to client ordering in FL.
Key results
- Proves a unified convergence bound under the new inter-epoch order-error assumption that recovers AP, RR, IG/SO/NP and GraB-family rates.
- Shows OP with a nice initial permutation can match or beat RR's rate when parameter drift is small (rate tilde-O((1/(NQ))^{2/3}) in the reported comparison).
- Experiments on one-dimensional quadratics with N=1000 show GraB variants outperform RR and SO in both SGD and FL.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GraB-style example ordering instead of Random Reshuffling or Shuffle Once | Permutation-based SGD · One-dimensional quadratic functions | distance to optimum | Helped |
| Use GraB-style client ordering instead of Random Reshuffling or Shuffle Once | Regularized-participation FL · One-dimensional quadratic functions | distance to optimum | Helped |
| Use a meticulously designed initial permutation and reuse it across epochs | One Permutation SGD · Finite-sum SGD | min gradient norm squared | Helped |
| Use a meticulously designed initial client permutation and reuse it across epochs | One-Permutation regularized-participation FL · Regularized-participation FL | min gradient norm squared | Helped |
Surprising findings
- A nice initial permutation (NP) under One Permutation can converge faster than Random Reshuffling when parameter change is small.
Limitations
- Experiments only on one-dimensional quadratic functions, not real data in the main text.
- FL analysis uses gradient descent as the local solver and regularized participation only.
- OP bound requires a bounded parameter-drift assumption that may be restrictive.
Experimental setup
Metrics: squared gradient norm distance to optimum order error
Baselines: Arbitrary Permutations Random Reshuffling Shuffle Once GraB-proto FL-AP FL-RR
Builds on: Random Reshuffling GraB PairGraB FlipFlop Incremental Gradient
Closest papers by meaning
- Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems (ICML 2025 · similarity 0.89)
- Tighter Convergence Bounds for Shuffled SGD via Primal-Dual Perspective (NeurIPS 2024 · similarity 0.88)
- A General Analysis of Example-Selection for Stochastic Gradient Descent (ICLR 2022 · similarity 0.88)
- Asymptotic theory of SGD with a general learning-rate (NeurIPS 2025 · similarity 0.87)
- Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent (ICML 2025 · similarity 0.86)
- Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity (NeurIPS 2026 · similarity 0.86)
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.