Research map / Optimization / Distributed and compressed
Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
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 Ringmaster ASGD, an asynchronous SGD variant that ignores gradients with delay ≥ R (R chosen independent of worker speeds), and proves it attains the optimal time complexity under fixed and universal computation models.
Problem
Asynchronous SGD under heterogeneous and time-varying worker computation times has suboptimal time complexity, and prior analyses showed no existing asynchronous SGD method reaches the optimal time lower bound.
Approach
Discard stochastic gradients whose delay reaches a threshold R (equivalently, an adaptive stepsize of zero for stale gradients) and restart the worker at the current iterate; with R set to max(1, ceil(sigma^2/epsilon)), the method matches the optimal time complexity without knowing worker speeds.
Key results
- Theory: Ringmaster ASGD with R = max(1, ceil(sigma^2/epsilon)) achieves time complexity min_m [(1/m sum 1/tau_i)^{-1}(L Delta/eps + sigma^2 L Delta/(m eps^2))], matching the Rennala SGD lower bound up to constants.
- Simulated quadratic experiment with n=6174 workers, d=1729: Ringmaster ASGD converges faster than Delay-Adaptive ASGD and Rennala SGD.
- Small 2-layer ReLU network on MNIST reported as more robust and faster than Delay-Adaptive ASGD and Rennala SGD.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Ringmaster ASGD with an appropriately chosen delay threshold | Asynchronous SGD · Fixed computation model | time complexity | Helped |
| Use Ringmaster ASGD with an appropriately chosen delay threshold | Asynchronous SGD · Universal computation model | time complexity | Helped |
| Use Ringmaster ASGD instead of Delay-Adaptive ASGD | Distributed quadratic optimization with heterogeneous worker speeds · Synthetic convex quadratic | convergence rate | Helped |
| Use Ringmaster ASGD instead of Rennala SGD | Distributed quadratic optimization with heterogeneous worker speeds · Synthetic convex quadratic | convergence rate | Helped |
| Use Ringmaster ASGD instead of Delay-Adaptive ASGD | 20-layer ReLU neural network · MNIST | performance | Helped |
| Use Ringmaster ASGD instead of Rennala SGD | 20-layer ReLU neural network · MNIST | performance | Helped |
| Select the fastest workers using an optimal fixed subset instead of using all workers | Naive Optimal ASGD · Fixed computation model | time complexity | Helped |
| Select workers once at initialization and keep the selection fixed | Naive Optimal ASGD · Time-varying worker speeds | robustness | Hurt |
| Ignore gradients whose delay is at least the threshold | Ringmaster ASGD · Nonconvex stochastic optimization | convergence guarantee | Helped |
| Terminate outdated computations rather than waiting for them to finish | Ringmaster ASGD with calculation stops · Distributed optimization | efficiency | Helped |
Surprising findings
- The optimal delay threshold R does not depend on the individual worker computation times.
- Previous asynchronous SGD analyses (with all gradients used) are not optimal in time complexity even though they are the standard practical method.
Limitations
- Experiments are simulated with a convex quadratic and a small MNIST network rather than large-scale training.
- Optimal R depends on sigma^2 and epsilon, which must be known or estimated; the tighter constant-level R requires the tau_i values.
- Analysis is for nonconvex stationary-point convergence with homogeneous data distribution across workers.
Experimental setup
Datasets: MNIST
Benchmarks: MNIST
Metrics: convergence versus time (simulated seconds) squared gradient norm
Baselines: Asynchronous SGD Delay-Adaptive ASGD Rennala SGD Naive Optimal ASGD
Builds on: Asynchronous SGD Rennala SGD Delay-Adaptive ASGD
Closest papers by meaning
- Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity (ICLR 2026 · similarity 0.94)
- Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning (NeurIPS 2022 · similarity 0.92)
- Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity (NeurIPS 2026 · similarity 0.92)
- Stability and Generalization of Asynchronous SGD: Sharper Bounds Beyond Lipschitz and Smoothness (NeurIPS 2024 · similarity 0.89)
- Ordered Momentum for Asynchronous SGD (NeurIPS 2024 · similarity 0.88)
- Do We Need Asynchronous SGD? On the Near-Optimality of Synchronous Methods (NeurIPS 2026 · 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.