# An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization

arXiv: https://arxiv.org/abs/1505.04824 · HTML: https://mlsanity.com/paper/1505.04824/

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 May 2015.

## Built on by (most cited first, 30 of 38)

- [Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning](https://mlsanity.com/paper/2206.08307/) (2022)
- [Fast Federated Learning in the Presence of Arbitrary Device Unavailability](https://mlsanity.com/paper/2106.04159/) (2021)
- [Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices](https://mlsanity.com/paper/2103.03239/) (2021)
- [Asynchronous Stochastic Optimization Robust to Arbitrary Delays](https://mlsanity.com/paper/2106.11879/) (2021)
- [Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks](https://mlsanity.com/paper/2206.10870/) (2022)
- [AsyncFedED: Asynchronous Federated Learning with Euclidean Distance based Adaptive Weight Aggregation](https://mlsanity.com/paper/2205.13797/) (2022)
- [Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity](https://mlsanity.com/paper/2501.16168/) (2025)
- [Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees](https://mlsanity.com/paper/2109.04522/) (2021)
- [Unbounded Gradients in Federated Learning with Buffered Asynchronous Aggregation](https://mlsanity.com/paper/2210.01161/) (2022)
- [Learning Under Delayed Feedback: Implicitly Adapting to Gradient Delays](https://mlsanity.com/paper/2106.12261/) (2021)
- [The Minimax Complexity of Distributed Optimization](https://mlsanity.com/paper/2109.00534/) (2021)
- [Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling](https://mlsanity.com/paper/2402.11800/) (2024)
- [MindFlayer SGD: Efficient Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Times](https://mlsanity.com/paper/2410.04285/) (2024)
- [Ordered Momentum for Asynchronous SGD](https://mlsanity.com/paper/2407.19234/) (2024)
- [Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity](https://mlsanity.com/paper/2509.22860/) (2025)
- [Distributed stochastic optimization with large delays](https://mlsanity.com/paper/2107.02919/) (2021)
- [Empowering Federated Learning with Implicit Gossiping: Mitigating Connection Unreliability Amidst Unknown and Arbitrary Dynamics](https://mlsanity.com/paper/2404.10091/) (2024)
- [Analysis and Evaluation of Synchronous and Asynchronous FLchain](https://mlsanity.com/paper/2112.07938/) (2021)
- [Asynchronous Training Schemes in Distributed Learning with Time Delay](https://mlsanity.com/paper/2208.13154/) (2022)
- [Convergence Analysis of Decentralized ASGD](https://mlsanity.com/paper/2309.03754/) (2023)
- [Parallel Momentum Methods Under Biased Gradient Estimations](https://mlsanity.com/paper/2403.00853/) (2024)
- [On the Convergence of Federated Learning Algorithms without Data Similarity](https://mlsanity.com/paper/2403.02347/) (2024)
- [Optimal Asynchronous Stochastic Nonconvex Optimization under Heavy-Tailed Noise](https://mlsanity.com/paper/2601.19379/) (2026)
- [Ringmaster LMO: Asynchronous Linear Minimization Oracle Momentum Method](https://mlsanity.com/paper/2605.18174/) (2026)
- [Risk Adversarial Learning System for Connected and Autonomous Vehicle Charging](https://mlsanity.com/paper/2108.01466/) (2021)
- [Dual-Delayed Asynchronous SGD for Arbitrarily Heterogeneous Data](https://mlsanity.com/paper/2405.16966/) (2024)
- [Faster Stochastic Optimization with Arbitrary Delays via Asynchronous Mini-Batching](https://mlsanity.com/paper/2408.07503/) (2024)
- [Asynchronous Policy Gradient Aggregation for Efficient Distributed Reinforcement Learning](https://mlsanity.com/paper/2509.24305/) (2025)
- [A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications](https://mlsanity.com/paper/2512.13547/) (2025)
- [Utilizing Redundancy in Cost Functions for Resilience in Distributed Optimization and Learning](https://mlsanity.com/paper/2110.10858/) (2021)

## Abstract (arXiv)

Mini-batch optimization has proven to be a powerful paradigm for large-scale learning. However, the state of the art parallel mini-batch algorithms assume synchronous operation or cyclic update orders. When worker nodes are heterogeneous (due to different computational capabilities or different communication delays), synchronous and cyclic operations are inefficient since they will leave workers idle waiting for the slower nodes to complete their computations. In this paper, we propose an asynchronous mini-batch algorithm for regularized stochastic optimization problems with smooth loss functions that eliminates idle waiting and allows workers to run at their maximal update rates. We show that by suitably choosing the step-size values, the algorithm achieves a rate of the order O(1/√T) for general convex regularization functions, and the rate O(1/T) for strongly convex regularization functions, where T is the number of iterations. In both cases, the impact of asynchrony on the convergence rate of our algorithm is asymptotically negligible, and a near-linear speedup in the number of workers can be expected. Theoretical results are confirmed in real implementations on a distributed computing infrastructure.