Research map / Optimization / Nonconvex and smooth optimization
Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond
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 |
|---|---|---|---|
| Replace with-replacement minibatch SGD sampling with random reshuffling | Minibatch SGD · PL-smooth objectives, sufficiently large K | objective suboptimality convergence rate: \tilde{\mc O}(\frac{L^2 \nu^2}{\mu^3 MNK^2}) versus \Theta (\frac{\nu^2}{\mu MNK}) | Helped |
| Replace with-replacement local SGD sampling with random reshuffling | Local SGD · PL-smooth objectives, K \gtrsim \kappa | objective suboptimality convergence rate: \tilde {\mc O} (\frac{L\nu^2}{\mu^2 MNK}+\frac{L^2 \nu^2 B}{\mu^3 N^2K^2}+\frac{L^2\tau^2 B^2}{\mu^3 N^2 K^2}) versus \t | Helped |
| Use local updates instead of aggregating a minibatch at the shared iterate | Minibatch RR · PL-smooth objectives | objective suboptimality convergence rate: \frac{\nu^2 B}{N^2K^2}+\frac{\tau^2 B^2}{N^2K^2} | Mixed |
| Increase local synchronization interval to B = \Theta(N) | Local RR · Homogeneous objectives | objective suboptimality convergence rate: \tilde{\mc O}(\frac{1}{NK^2}) | Hurt |
| Coordinate machine permutations by broadcasting shifted versions of a shared random permutation | Minibatch RR · Component-wise near-homogeneous objectives | objective suboptimality convergence rate: \frac{\nu^2}{MNK^2} -> \frac{\nu^2}{M^2NK^2} | Helped |
| Coordinate machine permutations by broadcasting shifted versions of a shared random permutation | Local RR · Component-wise near-homogeneous objectives, frequent communication | objective suboptimality convergence rate: \frac{\nu^2}{MNK^2} -> \frac{\nu^2}{M^2NK^2} | Helped |
| Increase the number of machines M under synchronized shuffling and near-homogeneity | Minibatch RR with SyncShuf · Component-wise near-homogeneous objectives | total cost: \frac{1}{M} | Helped |
| Increase minibatch size B | Minibatch RR · PL-smooth objectives | total cost | Helped |
| Increase synchronization interval B | Local RR · PL-smooth objectives | local-update error contribution to convergence rate: \frac{\nu^2 B}{N^2K^2}+\frac{\tau^2 B^2}{N^2K^2} | Hurt |
| Set B = 1 so local RR makes no multi-step local-update divergence | Local RR · Homogeneous objective | convergence behavior relative to minibatch RR | No clear effect |
Closest papers by meaning
- Tighter Convergence Bounds for Shuffled SGD via Primal-Dual Perspective (NeurIPS 2024 · similarity 0.91)
- SLowcalSGD : Slow Query Points Improve Local-SGD for Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.89)
- Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization (ICML 2025 · similarity 0.89)
- Towards Stability and Generalization Bounds in Decentralized Minibatch Stochastic Gradient Descent (AAAI 2024 · similarity 0.89)
- Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness (ICML 2025 · similarity 0.89)
- On the Last-Iterate Convergence of Shuffling Gradient Methods (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.