Research map / Optimization / Distributed and compressed

Do We Need Asynchronous SGD? On the Near-Optimality of Synchronous Methods

NeurIPS 2026 · Optimization › Distributed and compressed · approach: Local and asynchronous SGD · 0 citations (OpenAlex)

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.

Shows that synchronous SGD and its m-synchronous variant (ignoring stragglers via backup workers) achieve time complexity within a log factor of optimal asynchronous methods across fixed, random, and universal computation models, and under partial participation.

Problem

Asynchronous SGD methods are assumed to be needed for time-efficient distributed stochastic optimization under heterogeneous and random worker computation times; it is unclear whether synchronous methods are fundamentally suboptimal.

Approach

Synchronous SGD that aggregates one gradient from only the first m workers to finish (m-Synchronous SGD) is nearly optimal (up to log(n+1)) in time complexity for fixed computation times, with m chosen by minimizing tau_m * max{1, sigma^2/(m eps)}; the analysis extends to random sub-exponential times, universal computation powers, and adversarial partial participation.

Key results

• m-Synchronous SGD with m=10 matches the convergence speed of optimal asynchronous methods on a quadratic task with n=1000 and tau_i=sqrt(i), while plain Synchronous SGD is slow.
• On CIFAR-10 with random computation times and equal means, Synchronous SGD converges as fast as Rennala SGD and is at most 1.45x slower than Asynchronous SGD.
• Numerically, under chaotic universal computation powers with n=50, the time complexity of m-Synchronous SGD is within a factor of 1.85 of the lower bound.

Surprising findings

• Synchronous SGD using only the fastest m workers is nearly optimal (up to log n) for arbitrary heterogeneous fixed computation times.
• Plain Synchronous SGD is nearly optimal under random times with equal means, such as exponential distributions.

Limitations

• Asynchronicity may be needed under rapid computation-time changes.
• Heterogeneous data setting requires all workers, limiting m-Synchronous SGD.
• R log n noise term can dominate when variance is large.

Experimental setup

Datasets: CIFAR-10 NanoGPT training data

Benchmarks: CIFAR-10 NanoGPT

Metrics: wall-clock time to epsilon-stationary point convergence speed time complexity ratio

Baselines: Asynchronous SGD Rennala SGD Ringmaster ASGD Synchronous SGD Malenia SGD

Builds on: Asynchronous SGD Rennala SGD Ringmaster ASGD Malenia SGD

Closest papers by meaning

• Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamics (ICLR 2025 · similarity 0.92)
• On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimization (NeurIPS 2024 · similarity 0.92)
• Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity (NeurIPS 2024 · similarity 0.90)
• Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity (NeurIPS 2026 · similarity 0.89)
• Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity (ICML 2025 · similarity 0.88)
• Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations (NeurIPS 2024 · similarity 0.88)