Research map / Optimization / Nonconvex and smooth optimization
Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
Blake E Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, Nati Srebro
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 A-MB-SGD on the layer graph with gradient queries | Layer(T,M) optimization · layer(T,M) | expected suboptimality | Improved |
| Allow prox queries for sufficiently smooth objectives | Layer(T,M) optimization · layer(T,M) | optimal complexity | No clear effect |
| Use prox queries to compute gradients of the Moreau envelope, then apply accelerated mini-batch SGD | Layer(T,M) optimization on non-smooth or insufficiently smooth objectives · layer(T,M) | expected suboptimality | Improved |
| Use delayed SGD updates instead of a wait-and-collect schedule | Delayed update optimization · delay(T,τ) | expected suboptimality: O\left( \frac{H}{T/\tau^2} + \frac{L}{\sqrt{T}} \right) | Hurt |
| Batch τ gradients at one point and wait for their results before updating | Delayed update optimization · delay(T,τ) | expected suboptimality | Improved |
| Use mini-batch SGD over all KM queries per round rather than exploiting local sequential computation | Intermittent communication optimization · intermittent(T,K,M) | optimization term in expected suboptimality: H/T^2 vs. H/(T^2K^2) | Hurt |
| Use only one chain for sequential SGD | Intermittent communication optimization · intermittent(T,K,M) | expected suboptimality: O\parens{\frac{L}{\sqrt{T K}}} | Improved |
| Use active queries and SVRG instead of pure stochastic queries | Intermittent communication optimization · intermittent(T,K,M) | expected suboptimality: O\parens{\parens{ \frac{H}{T K} + \frac{L}{\sqrt{T K M} }}\log\parens{ \frac{T K M}{ L}}} | Improved |
Closest papers by meaning
- Optimal Time Complexities of Parallel Stochastic Optimization Methods Under a Fixed Computation Model (NeurIPS 2023 · similarity 0.92)
- Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamics (ICLR 2025 · similarity 0.88)
- Lower Bounds for Parallel and Randomized Convex Optimization (JMLR 2020 · similarity 0.88)
- Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations (NeurIPS 2024 · similarity 0.86)
- On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimization (NeurIPS 2024 · similarity 0.86)
- Accelerating Matroid Optimization through Fast Imprecise Oracles (NeurIPS 2024 · similarity 0.83)
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.
