Research map / Optimization / Nonconvex and smooth optimization
Tighter Convergence Bounds for Shuffled SGD via Primal-Dual Perspective
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.
Analyzes shuffled SGD (IG, SO, RR) through a primal-dual cyclic-coordinate view and introduces new data-dependent smoothness constants that give convergence bounds up to O(√n) tighter than prior work.
Problem
Existing convergence bounds for shuffled SGD (without replacement) are overly pessimistic, depending on the global max component smoothness and forcing tiny step sizes, so they fail to explain the empirical success of shuffling over sampling with replacement.
Approach
Reformulates shuffled SGD as a primal-dual method performing cyclic updates on the dual side, and tracks cumulative dual bias within an epoch to derive new permutation-dependent smoothness constants (for general finite sums and for linear predictors/GLMs) that replace the max component smoothness in the step size and complexity bounds.
Key results
- Theoretical bounds improve over prior RR/SO bounds by a factor sqrt(Lmax/L-hat), with Lmax/L-hat reported as roughly 3.5 to 194 across 15 datasets (e.g., 194 for real-sim, 111 for rcv1, 42.1 for news20).
- Step size from the new analysis (1/(n sqrt(L-hat L-tilde))) is larger than prior 1/(sqrt(2) n Lmax) and yields faster empirical convergence of shuffled SGD on logistic regression (Fig. 1).
- Gap between new bound and prior bound on the Gaussian data example is up to a factor of n in the smoothness constant.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use data-dependent smoothness parameters ˆL and ˜L for shuffled SGD on linear predictors | Shuffled SGD convergence bound · Convex smooth finite-sum problems with linear predictors | individual gradient oracle complexity: O(√n) | Helped |
| Use the data-dependent parameter ˆL instead of Lmax | Shuffled SGD convergence bound · LIBSVM, MNIST, CIFAR10, and BBBC datasets | Lmax/Lhat: 5.50; 5.49; 18.3; 7.04; 10.0; 38.0; 5.35; 3.52; 32.8; 19.1; 42.1; 111; 194; 6.26; 10.9 | Helped |
| Use the larger step size derived from the new smoothness parameters rather than the prior-work step size | Random-reshuffling SGD for logistic regression · LIBSVM luke, leu, and a9a | optimality gap | Helped |
Surprising findings
- Under the new smoothness constant, the permutation-dependent quantity concentrates around its mean over random permutations, suggesting bounds could depend on the mean rather than the worst case.
Limitations
- Results are for convex settings; no strongly convex analysis is provided.
- The new bounds depend on worst-case permutation constants; the mean-based version is left for future work.
- Only RR and SO are presented in the main body; IG results are deferred to the appendix.
Experimental setup
Datasets: LIBSVM (luke, leu, a9a, a1a, gisette, rcv1, real-sim, news20, e2006train, duke, sonar, tmc2007) MNIST CIFAR10 BBBC005 BBBC010
Benchmarks: LIBSVM datasets (luke, leu, a9a) 15 ML datasets for Lmax/L-hat ratio (a1a, a9a, BBBC005, BBBC010, CIFAR10, duke, e2006train, gisette, leu, MNIST, news20,
Metrics: optimality gap over epochs ratio Lmax/L-hat convergence complexity (gradient oracle calls)
Baselines: Mishchenko et al. (RR/SO bounds) Nguyen et al. (RR bounds) Cha et al. (RR bounds) Shamir (RR/SO nonsmooth bound) full gradient descent
Builds on: Mishchenko et al. shuffled SGD analysis Nguyen et al. shuffled SGD analysis Cha et al. shuffled SGD lower bounds randomized dual coordinate methods (Shalev-Shwartz & Zhang)
Closest papers by meaning
- Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond (ICML 2023 · similarity 0.93)
- On the Convergence to a Global Solution of Shuffling-Type Gradient Algorithms (NeurIPS 2023 · similarity 0.92)
- Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems (NeurIPS 2021 · similarity 0.91)
- Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems (ICML 2025 · similarity 0.91)
- On Convergence of Incremental Gradient for Non-convex Smooth Functions (ICML 2024 · similarity 0.90)
- Towards Stability and Generalization Bounds in Decentralized Minibatch Stochastic Gradient Descent (AAAI 2024 · similarity 0.89)
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.