Research map / Optimization / Nonconvex and smooth optimization
Optimal Time Complexities of Parallel Stochastic Optimization Methods Under a Fixed Computation Model
Alexander Tyurin, Peter Richtárik
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 |
|---|---|---|---|
| Use Rennala SGD (ignore stale gradients, batch size S=max(sigma^2/eps,1)) instead of Asynchronous SGD | Parallel nonconvex SGD under fixed computation model · Homogeneous nonconvex, time complexity | time complexity to eps-stationary point | Improved |
| Use Rennala SGD instead of Minibatch SGD | Parallel nonconvex SGD · Homogeneous nonconvex, time complexity | time complexity to eps-stationary point | Improved |
| Let workers start asynchronously instead of synchronized start | Optimal parallel methods · Homogeneous nonconvex, time complexity | time complexity | Improved |
| Use Asynchronous SGD instead of Minibatch SGD | Parallel nonconvex SGD · Fixed computation model | time complexity | Improved |
| Use Malenia SGD (per-worker estimators) instead of Minibatch SGD | Heterogeneous nonconvex parallel SGD · Heterogeneous nonconvex, time complexity | time complexity | Improved |
| Ignore workers with delays beyond the optimal m* (done automatically by Rennala SGD) | Rennala SGD · Homogeneous nonconvex | time complexity | Improved |
| Use the new time-based lower bound instead of the Woodworth et al. graph-oracle bound | Convex fixed computation model lower bound · Convex homogeneous case | lower bound tightness | Improved |
| Add Nesterov-style acceleration to Rennala SGD in the smooth convex case | Rennala SGD · Convex smooth case | time complexity | Improved |
Closest papers by meaning
- Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamics (ICLR 2025 · similarity 0.92)
- Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization (NeurIPS 2018 · similarity 0.92)
- On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimization (NeurIPS 2024 · similarity 0.91)
- Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations (NeurIPS 2024 · similarity 0.89)
- Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batching (ICML 2025 · similarity 0.88)
- Do We Need Asynchronous SGD? On the Near-Optimality of Synchronous Methods (NeurIPS 2026 · 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.
