Research map / Optimization / Distributed and compressed

Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity

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.

Proposes Rescaled ASGD, which keeps the plain asynchronous SGD template but scales each worker's stepsize proportional to its computation time so every worker contributes equal aggregate step per cycle, provably converging to the equal-weighted global objective with time complexity matching the lower bound in the leading term.

Problem

Asynchronous SGD under data heterogeneity and heterogeneous worker speeds is biased toward a frequency-weighted average of local objectives (objective inconsistency), while existing fixes require gathering phases, buffering, or extra memory.

Approach

Rescale worker-specific stepsizes in proportion to computation times (gamma_i proportional to tau_i) so each worker's aggregate learning rate over a cycle is equal; under a harmonic-periods assumption on computation times, this neutralizes objective inconsistency without gathering, idling, or memory overhead.

Key results

• Theorem gives time complexity O(Delta L sigma^2 tau_A/(n eps^2) + ... + Delta L tau_max/eps) whose leading and last terms match the known lower bound, with the leading term scaling with arithmetic mean tau_A rather than tau_max.
• Vanilla ASGD with equal stepsizes is shown to converge to a frequency-weighted average of local objectives with leading complexity scaling with harmonic mean tau_H.
• On heterogeneous-label MNIST with 10 workers and computation times in {1,2,4,8,16}, Rescaled ASGD converges to the correct objective and is competitive with Malenia SGD and Ringleader ASGD, and is unaffected by fluctuating computation times while the baselines slow down.

Surprising findings

• Vanilla ASGD's leading complexity term scales with the harmonic mean of computation times, meaning the rescaled method is slower in that term than vanilla ASGD despite being unbiased.

Limitations

• Theory relies on fixed computation times with harmonic periods assumption, which may not hold in practice.
• Experiments are limited to a small two-layer network on MNIST.
• Bounded heterogeneity assumption with rho and zeta still required; convergence only shown for cycle iterates.

Experimental setup

Datasets: MNIST

Benchmarks: MNIST

Metrics: training loss cumulative stepsize over time expected squared gradient norm (theory)

Baselines: Malenia SGD Ringleader ASGD Vanilla ASGD Naive Minibatch SGD Concurrent ASGD Delay-Adaptive ASGD

Builds on: Asynchronous SGD Malenia SGD Ringleader ASGD Delay-Adaptive ASGD

Closest papers by meaning

• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning (NeurIPS 2022 · similarity 0.93)
• Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity (ICLR 2026 · similarity 0.92)
• Sharper Generalization Guarantees for Asynchronous SGD: Beyond Lipschitzness, Smoothness and Data Homogeneity (ICML 2026 · similarity 0.92)
• Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity (ICML 2025 · similarity 0.92)
• Stability and Generalization of Asynchronous SGD: Sharper Bounds Beyond Lipschitz and Smoothness (NeurIPS 2024 · similarity 0.91)
• SLowcalSGD : Slow Query Points Improve Local-SGD for Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.89)