Research map / Optimization / Distributed and compressed
On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimization
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 time-complexity lower bounds for decentralized asynchronous stochastic nonconvex optimization with computation and communication delays, and proposes Fragile SGD (homogeneous, nearly optimal) and Amelie SGD (heterogeneous, optimal) that match them.
Problem
Finding the optimal physical-time complexity for asynchronous stochastic optimization over decentralized multigraphs where workers have heterogeneous computation and communication times, which prior gossip-based analyses did not capture.
Approach
Model the network by shortest-path communication times and computation upper bounds, derive a matching time lower bound via an equilibrium-time formula, and design spanning-tree-based asynchronous methods (Fragile SGD, Amelie SGD) that ignore stragglers and achieve that bound without knowing the speeds.
Key results
- Fragile SGD matches the derived time lower bound up to a log n factor in the homogeneous setting (Corollary 1 vs Theorem 1).
- Amelie SGD achieves the heterogeneous lower bound up to a constant factor (Corollary 2 vs Theorem 7).
- On MNIST with 100 workers under slow communication, Fragile SGD is much faster and reaches better test accuracy than Minibatch SGD.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Fragile SGD instead of Minibatch SGD | Homogeneous decentralized nonconvex optimization · Homogeneous decentralized nonconvex | worst-case time complexity | Helped |
| Use Amelie SGD instead of Minibatch SGD | Heterogeneous decentralized nonconvex optimization · Heterogeneous decentralized nonconvex | worst-case time complexity | Helped |
| Use Fragile SGD with a pivot and shortest-path spanning trees | Homogeneous decentralized nonconvex optimization · Homogeneous decentralized nonconvex | worst-case time complexity | Helped |
| Use Amelie SGD for heterogeneous local functions without requiring function similarity | Heterogeneous decentralized optimization · Heterogeneous decentralized nonconvex | time complexity | Helped |
| Use Fragile SGD instead of Minibatch SGD | MNIST logistic regression with 100 workers and slow communication · MNIST test | accuracy | Helped |
| Increase the participating worker set only when communication and computation costs permit | Fragile SGD on line graphs · Line graph | time complexity | Mixed |
Surprising findings
- Only a subset of workers should contribute to optimization; slow or distant workers are optimally ignored.
- In a line graph, for slow communication, the optimal strategy is effectively to use only one worker.
Limitations
- Optimal performance requires choosing the right pivot worker and spanning trees based on knowledge of time bounds.
- Homogeneous method is optimal only up to a log n factor; lower bound has an extra log n factor from technical analysis.
- Analysis assumes upper bounds on computation and communication times are static (dynamic case handled separately).
Experimental setup
Datasets: MNIST
Benchmarks: MNIST
Metrics: time to epsilon-stationary point test accuracy objective value vs time
Baselines: Minibatch SGD SWIFT Asynchronous SGD RelaySGD Gradient Tracking
Builds on: Rennala SGD Malenia SGD Asynchronous SGD Minibatch SGD
Closest papers by meaning
- Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamics (ICLR 2025 · similarity 0.92)
- Do We Need Asynchronous SGD? On the Near-Optimality of Synchronous Methods (NeurIPS 2026 · similarity 0.92)
- Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations (NeurIPS 2024 · similarity 0.90)
- Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks (NeurIPS 2024 · similarity 0.89)
- Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity (NeurIPS 2024 · similarity 0.89)
- Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batching (ICML 2025 · similarity 0.87)
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.