Research map / Optimization / Distributed and compressed
Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamics
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.
Introduces a universal computation model for worker speeds and derives tight time-complexity lower bounds and matching optimal methods (Rennala SGD, Malenia SGD) for homogeneous and heterogeneous parallel stochastic optimization under arbitrary computation dynamics.
Problem
Determining optimal time complexities of parallel and asynchronous stochastic optimization when workers have arbitrary, time-varying, possibly disconnected computation speeds.
Approach
A universal computation model where each worker's computation power is a non-negative function of time, with the number of stochastic gradients given by the floor of the integral of power; this yields implicit lower bounds (via time-indexed recursions) that are matched by Rennala SGD (homogeneous) and Malenia SGD (heterogeneous).
Key results
- Establishes a tight implicit time-complexity lower bound in the homogeneous setup under the universal computation model, matched up to constants by Rennala SGD.
- Establishes a tight lower bound in the heterogeneous setup (via random function construction) matched up to constants by Malenia SGD, removing logarithmic factors present in the deterministic-construction bound.
- Explicit closed forms recovered for fixed, nonlinear trend, and random outage computation models.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Rennala SGD with batch size S = max{ceil(σ²/ε), 1} under arbitrary time-varying worker computation powers | Homogeneous stochastic optimization · Homogeneous nonconvex stochastic optimization; universal computation model | time complexity | Helped |
| Use Malenia SGD with batch size S = max{ceil(σ²/ε), n} under arbitrary time-varying worker computation powers | Heterogeneous stochastic optimization · Heterogeneous nonconvex stochastic optimization; universal computation model | time complexity | Helped |
| Allow computation powers to vary over time as v_i(t) = v_i × g(t) | Rennala SGD · Homogeneous nonconvex stochastic optimization; nonlinear computation trend | time complexity | Mixed |
| Introduce worker outages through intermittently zero computation power | Rennala SGD · Homogeneous nonconvex stochastic optimization; random outages | time complexity | Hurt |
| Replace fixed worker computation speeds with arbitrary computation powers | Rennala SGD · Homogeneous nonconvex stochastic optimization; universal computation model | time complexity | Mixed |
| Use random local functions in the heterogeneous lower-bound construction instead of predefined deterministic functions | Heterogeneous lower-bound analysis · Heterogeneous stochastic optimization | time complexity lower bound | Helped |
| Set Malenia SGD batch size to S = max{ceil(σ²/ε), n} | Malenia SGD · Heterogeneous nonconvex stochastic optimization | stationarity guarantee: K ≥ 24 Δ L / ε; 1/K sum ... ≤ ε | Helped |
| Set Rennala SGD batch size to S = max{ceil(σ²/ε), 1} | Rennala SGD · Homogeneous nonconvex stochastic optimization | stationarity guarantee: K ≥ 24 L Δ / ε; 1/K sum ... ≤ ε | Helped |
Surprising findings
- Rennala SGD attains the optimal time complexity without prior knowledge of the computation powers.
- Workers that are sufficiently slow may not contribute to the time complexity at all (they can be ignored by the min operation).
Limitations
- Lower bounds are implicit, lacking closed-form expressions in general.
- Heterogeneous deterministic-construction bound is tight only up to logarithmic factors; tight version requires random construction.
- Assumes computation powers are independent of stochastic gradient randomness.
Experimental setup
Metrics: time complexity
Baselines: Minibatch SGD Asynchronous SGD Picky SGD
Builds on: Rennala SGD Malenia SGD Asynchronous SGD Picky SGD zero-chain construction of Carmon et al.
Closest papers by meaning
- On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimization (NeurIPS 2024 · 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.89)
- Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity (NeurIPS 2024 · similarity 0.88)
- Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity (NeurIPS 2026 · similarity 0.87)
- Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity (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.