# ASAGA: Asynchronous Parallel SAGA

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2016.

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

- [Federated Learning with Buffered Asynchronous Aggregation](https://mlsanity.com/paper/2106.06639/) (2021)
- [Pufferfish: Communication-efficient Models At No Extra Cost](https://mlsanity.com/paper/2103.03936/) (2021)
- [Secure Bilevel Asynchronous Vertical Federated Learning with Backward Updating](https://mlsanity.com/paper/2103.00958/) (2021)
- [Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices](https://mlsanity.com/paper/2103.03239/) (2021)
- [Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees](https://mlsanity.com/paper/2109.04522/) (2021)
- [Decoupled Greedy Learning of CNNs for Synchronous and Asynchronous Distributed Learning](https://mlsanity.com/paper/2106.06401/) (2021)
- [Elastic Consistency: A General Consistency Model for Distributed Stochastic Gradient Descent](https://mlsanity.com/paper/2001.05918/) (2020)
- [Sum-Rate-Distortion Function for Indirect Multiterminal Source Coding in Federated Learning](https://mlsanity.com/paper/2101.08696/) (2021)
- [Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity](https://mlsanity.com/paper/2605.13434/) (2026)
- [Finite-Time Consensus Learning for Decentralized Optimization with Nonlinear Gossiping](https://mlsanity.com/paper/2111.02949/) (2021)
- [Distributed Dynamic Safe Screening Algorithms for Sparse Regularization](https://mlsanity.com/paper/2204.10981/) (2022)
- [Scaling up Stochastic Gradient Descent for Non-convex Optimisation](https://mlsanity.com/paper/2210.02882/) (2022)
- [Distributed Stochastic Gradient Descent with Staleness: A Stochastic Delay Differential Equation Based Framework](https://mlsanity.com/paper/2406.11159/) (2024)
- [A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications](https://mlsanity.com/paper/2512.13547/) (2025)
- [Tight Analysis of Decentralized SGD: A Markov Chain Perspective](https://mlsanity.com/paper/2601.07021/) (2026)
- [Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization](https://mlsanity.com/paper/2109.15292/) (2021)
- [Asynchronous Decentralized SGD under Non-Convexity: A Block-Coordinate Descent Framework](https://mlsanity.com/paper/2505.10322/) (2025)
- [Simpler Methods Work Better for L1 Penalized Logistic Models and Large Datasets](https://mlsanity.com/paper/2609.23995/) (2026)

## Abstract (arXiv)

We describe ASAGA, an asynchronous parallel version of the incremental gradient algorithm SAGA that enjoys fast linear convergence rates. 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 thereby prove that ASAGA 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 speedup as well as the hardware overhead.