# Improved asynchronous parallel optimization analysis for stochastic incremental methods

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jan 2018.

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

- [Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning](https://mlsanity.com/paper/2206.08307/) (2022)
- [Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays](https://mlsanity.com/paper/2206.07638/) (2022)
- [Asynchronous Stochastic Optimization Robust to Arbitrary Delays](https://mlsanity.com/paper/2106.11879/) (2021)
- [Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates](https://mlsanity.com/paper/2103.02351/) (2021)
- [Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees](https://mlsanity.com/paper/2109.04522/) (2021)
- [Delay-adaptive step-sizes for asynchronous learning](https://mlsanity.com/paper/2202.08550/) (2022)
- [Asynchronous Federated Learning with Bidirectional Quantized Communications and Buffered Aggregation](https://mlsanity.com/paper/2308.00263/) (2023)
- [FADAS: Towards Federated Adaptive Asynchronous Optimization](https://mlsanity.com/paper/2407.18365/) (2024)
- [DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization](https://mlsanity.com/paper/2208.00779/) (2022)
- [Learning Under Delayed Feedback: Implicitly Adapting to Gradient Delays](https://mlsanity.com/paper/2106.12261/) (2021)
- [Decoupled Greedy Learning of CNNs for Synchronous and Asynchronous Distributed Learning](https://mlsanity.com/paper/2106.06401/) (2021)
- [Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity](https://mlsanity.com/paper/2509.22860/) (2025)
- [Distributed Methods with Absolute Compression and Error Compensation](https://mlsanity.com/paper/2203.02383/) (2022)
- [Asynchronous speedup in decentralized optimization](https://mlsanity.com/paper/2106.03585/) (2021)
- [On the Practicality of Differential Privacy in Federated Learning by Tuning Iteration Times](https://mlsanity.com/paper/2101.04163/) (2021)
- [Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity](https://mlsanity.com/paper/2605.13434/) (2026)
- [Proactive DP: A Multple Target Optimization Framework for DP-SGD](https://mlsanity.com/paper/2102.09030/) (2021)
- [Optimizing the Numbers of Queries and Replies in Federated Learning with Differential Privacy](https://mlsanity.com/paper/2107.01895/) (2021)
- [AET-SGD: Asynchronous Event-triggered Stochastic Gradient Descent](https://mlsanity.com/paper/2112.13935/) (2021)
- [Distributed Dynamic Safe Screening Algorithms for Sparse Regularization](https://mlsanity.com/paper/2204.10981/) (2022)
- [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)
- [A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications](https://mlsanity.com/paper/2512.13547/) (2025)
- [Distributed Learning and its Application for Time-Series Prediction](https://mlsanity.com/paper/2106.03211/) (2021)
- [Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization](https://mlsanity.com/paper/2109.15292/) (2021)
- [Federated Learning with Superquantile Aggregation for Heterogeneous Data](https://mlsanity.com/paper/2112.09429/) (2021)
- [Layer-wise Adaptive Step-Sizes for Stochastic First-Order Methods for Deep Learning](https://mlsanity.com/paper/2305.13664/) (2023)
- [Stragglers Can Contribute More: Uncertainty-Aware Distillation for Asynchronous Federated Learning](https://mlsanity.com/paper/2511.19966/) (2025)
- [Bringing Order to Asynchronous SGD: Towards Optimality under Data-Dependent Delays with Momentum](https://mlsanity.com/paper/2605.02043/) (2026)
- [Stochastic convergence of parallel asynchronous adaptive first-order methods](https://mlsanity.com/paper/2606.01787/) (2026)

## Abstract (arXiv)

As datasets continue to increase in size and multi-core computer architectures are developed, asynchronous parallel optimization algorithms become more and more essential to the field of Machine Learning. Unfortunately, conducting the theoretical analysis asynchronous methods is difficult, notably due to the introduction of delay and inconsistency in inherently sequential algorithms. Handling these issues often requires resorting to simplifying but unrealistic assumptions. Through a novel perspective, we revisit and clarify a subtle but important technical issue present in a large fraction of the recent convergence rate proofs for asynchronous parallel optimization algorithms, and propose a simplification of the recently introduced "perturbed iterate" framework that resolves it. We demonstrate the usefulness of our new framework by analyzing three distinct asynchronous parallel incremental optimization algorithms: Hogwild (asynchronous SGD), KROMAGNON (asynchronous SVRG) and ASAGA, a novel asynchronous parallel version of the incremental gradient algorithm SAGA that enjoys fast linear convergence rates. We are able to both remove problematic assumptions and obtain better theoretical results. Notably, we prove that ASAGA and KROMAGNON can obtain a theoretical linear speedup on multi-core systems even without sparsity assumptions. We present results of an implementation on a 40-core architecture illustrating the practical speedups as well as the hardware overhead. Finally, we investigate the overlap constant, an ill-understood but central quantity for the theoretical analysis of asynchronous parallel algorithms. We find that it encompasses much more complexity than suggested in previous work, and often is order-of-magnitude bigger than traditionally thought.