Research map / Optimization / Nonconvex and smooth optimization

Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batching

ICML 2025 · Optimization › Nonconvex and smooth optimization · approach: Stochastic gradient last-iterate analysis

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.

Transforms any standard stochastic first-order method into an asynchronous method whose rates depend on a chosen delay quantile via asynchronous mini-batching, plus a quantile-adaptive variant needing no delay knowledge.

Problem

Asynchronous stochastic optimization where stale stochastic gradients arrive with arbitrary (possibly adversarial) delays; prior rates depend on average delay or number of machines, and lack accelerated convex-smooth rates or require known delay bounds.

Approach

Asynchronous mini-batching: the server accumulates for each query only gradients whose delay guarantees they were computed at the queried point, with batch size set from the q-quantile delay; a doubling-sweep variant adapts to all quantiles simultaneously by choosing batch sizes from the underlying optimizer's rate rather than delays.

Key results

• Async-MB-SGD reaches 0.8737 test accuracy vs 0.8623 for Async-SGD with 640 workers and 120,000 steps.
• Async-MB-SGD beats Async-SGD by 0.35% at 160 workers and 1.1% at 640 workers; the two are roughly tied at 40 workers (0.8457 vs 0.8449).
• Theory: non-convex rate O(tau_q/(qT)+sigma/sqrt(qT)) and accelerated convex-smooth rate O(tau_q^2/(qT)^2+sigma/sqrt(qT)); the quantile-adaptive variant matches the infimum over quantiles without knowing delays.

Measured effects reported in the paper

Surprising findings

• Under the stated lower bound, vanilla asynchronous SGD with fixed stepsize degrades with the maximal delay even when the average delay is small.

Limitations

• Results for the quantile-adaptive variant rely on batch sizes tuned to the optimizer's rate, and the experiments are limited to one small fully connected network on Fashion-MNIST.
• Delay model assumes an oblivious adversary, with delays independent of the stochastic gradients.
• Practical variant modifies the filtering condition and introduces a small amount of staleness not covered by the theory.

Experimental setup

Datasets: Fashion-MNIST

Benchmarks: Fashion-MNIST

Metrics: test accuracy theoretical convergence rate

Baselines: Async-SGD

Builds on: SGD AC-SA (accelerated SGD) Rennala SGD picky SGD AdaGrad-norm

Closest papers by meaning

• Asynchronous Stochastic Optimization Robust to Arbitrary Delays (NeurIPS 2021 · similarity 0.92)
• Think out of the "Box": Generically-Constrained Asynchronous Composite Optimization and Hedging (NeurIPS 2019 · similarity 0.90)
• Delay-Adaptive Distributed Stochastic Optimization (AAAI 2020 · similarity 0.90)
• Distributed Asynchronous Optimization with Unbounded Delays: How Slow Can You Go? (ICML 2018 · similarity 0.89)
• Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity (NeurIPS 2026 · similarity 0.88)
• Stochastic Optimization with Arbitrary Recurrent Data Sampling (ICML 2024 · similarity 0.88)