Research map / Optimization / Nonconvex and smooth optimization
Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness
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.
Proves convergence of shuffling-type gradient methods (random reshuffling and arbitrary shuffling) under ℓ-smoothness, a sub-quadratic Hessian-norm relaxation of Lipschitz smoothness, across nonconvex, strongly convex, and non-strongly convex settings.
Problem
Existing convergence guarantees for shuffling-type gradient methods require Lipschitz smoothness, which fails for common ML models such as phase retrieval, DRO, and deep language models.
Approach
Replace global Lipschitz smoothness with ℓ-smoothness (Hessian norm bounded by a sub-quadratic non-decreasing function of the gradient norm), and use a stopping-time argument plus a stepsize choice to keep the trajectory in a region where local Lipschitz constants are bounded with high probability, obtaining rates matching the Lipschitz case up to polynomial factors in n and dependence on δ.
Key results
- Under ℓ-smoothness with bounded variance, the nonconvex random-reshuffling method achieves total complexity O(n^{(p+1)/2} ε^{-3}), matching the Lipschitz-case rate when p=0.
- For strongly convex objectives, random reshuffling achieves Õ(n^{(p+1)/2} ε^{-1/2}) total gradient evaluations, matching the Lipschitz result when p=0.
- Numerical experiments on synthetic convex functions, phase retrieval, DRO and CIFAR-10 ResNet18 show shuffling variants converging faster than SGD in several settings (e.g., fixed shuffling on DRO and CIFAR-10 test accuracy).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use fixed, shuffle-once, or uniform reshuffling instead of SGD | Shuffling-type gradient algorithm · Synthetic convex objective | objective value convergence speed | Helped |
| Use fixed, shuffle-once, or uniform reshuffling instead of SGD | Shuffling-type gradient algorithm · Synthetic strongly convex objective | objective value convergence speed | Helped |
| Use shuffle-once or uniform reshuffling instead of SGD | Shuffling-type gradient algorithm · Phase retrieval | objective value convergence speed | Helped |
| Use fixed shuffling instead of SGD | Shuffling-type gradient algorithm · DRO life expectancy data | objective value convergence speed | Helped |
| Use fixed shuffling instead of SGD | Shuffling-type gradient algorithm · CIFAR-10 train and test | loss and classification accuracy | Helped |
| Use shuffle-once or uniform shuffling instead of SGD | Shuffling-type gradient algorithm · CIFAR-10 training data | loss and classification accuracy | Helped |
Limitations
- Polynomial dependence on the failure probability δ (T scales as δ^{-3/2-p/(2-p)}), which is worse than Lipschitz settings.
- Constant G' depends on p and may be very large, so the strongly convex arbitrary-scheme bound cannot be directly compared with others.
- Does not achieve the O(1/(nT^2)) single-shuffling rate under ℓ-smoothness.
Experimental setup
Datasets: life expectancy (WHO) dataset CIFAR-10
Benchmarks: CIFAR-10
Metrics: objective value training loss test accuracy
Baselines: SGD
Builds on: (L0,L1)-smoothness ℓ-smoothness random reshuffling
Closest papers by meaning
- On the Last-Iterate Convergence of Shuffling Gradient Methods (ICML 2024 · similarity 0.92)
- Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization (ICML 2025 · similarity 0.90)
- Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimization (NeurIPS 2024 · similarity 0.89)
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · similarity 0.88)
- Tighter Convergence Bounds for Shuffled SGD via Primal-Dual Perspective (NeurIPS 2024 · similarity 0.88)
- On Convergence of Incremental Gradient for Non-convex Smooth Functions (ICML 2024 · similarity 0.88)
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.