# Robust Fully-Asynchronous Methods for Distributed Training over General Architecture

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 52 references that are in the map.
- First posted on arXiv 21 Jul 2023.

## Builds on (most cited first, 28 of 28)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://mlsanity.com/paper/1706.02677/) (2017)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Horovod: fast and easy distributed deep learning in TensorFlow](https://mlsanity.com/paper/1802.05799/) (2018)
- [A Survey on Distributed Machine Learning](https://mlsanity.com/paper/1912.09789/) (2019)
- [Asynchronous Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1710.06952/) (2017)
- [Stochastic Gradient Push for Distributed Deep Learning](https://mlsanity.com/paper/1811.10792/) (2018)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [D2: Decentralized Training over Decentralized Data](https://mlsanity.com/paper/1803.07068/) (2018)
- [Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization](https://mlsanity.com/paper/1506.08272/) (2015)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018)
- [Push-Pull Gradient Methods for Distributed Optimization in Networks](https://mlsanity.com/paper/1810.06653/) (2018)
- [Staleness-aware Async-SGD for Distributed Deep Learning](https://mlsanity.com/paper/1511.05950/) (2015)
- [Asynchronous Decentralized SGD with Quantized and Local Updates](https://mlsanity.com/paper/1910.12308/) (2019)
- [A linear algorithm for optimization over directed graphs with geometric convergence](https://mlsanity.com/paper/1803.02503/) (2018)
- [Distributed Training of Deep Learning Models: A Taxonomic Perspective](https://mlsanity.com/paper/2007.03970/) (2020)
- [Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and Network-Independent Performance for Strongly Convex Functions](https://mlsanity.com/paper/1811.03982/) (2018)
- [Achieving Linear Convergence in Distributed Asynchronous Multi-agent Optimization](https://mlsanity.com/paper/1803.10359/) (2018)
- [Distributed stochastic optimization with gradient tracking over strongly-connected networks](https://mlsanity.com/paper/1903.07266/) (2019)
- [Towards Efficient and Stable K-Asynchronous Federated Learning with Unbounded Stale Gradients on Non-IID Data](https://mlsanity.com/paper/2203.01214/) (2022)
- [A Robust Gradient Tracking Method for Distributed Optimization over Directed Networks](https://mlsanity.com/paper/2003.13980/) (2020)
- [Decentralized Asynchronous Non-convex Stochastic Optimization on Directed Graphs](https://mlsanity.com/paper/2110.10406/) (2021)
- [Asynchronous Decentralized Successive Convex Approximation](https://mlsanity.com/paper/1909.10144/) (2019)
- [FedBC: Calibrating Global and Local Models via Federated Learning Beyond Consensus](https://mlsanity.com/paper/2206.10815/) (2022)

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

- [Unity is Power: Semi-Asynchronous Collaborative Training of Large-Scale Models with Structured Pruning in Resource-Limited Clients](https://mlsanity.com/paper/2410.08457/) (2024)
- [Asynchronous Decentralized SGD under Non-Convexity: A Block-Coordinate Descent Framework](https://mlsanity.com/paper/2505.10322/) (2025)

## Abstract (arXiv)

Perfect synchronization in distributed machine learning problems is inefficient and even impossible due to the existence of latency, package losses and stragglers. We propose a Robust Fully-Asynchronous Stochastic Gradient Tracking method (R-FAST), where each device performs local computation and communication at its own pace without any form of synchronization. Different from existing asynchronous distributed algorithms, R-FAST can eliminate the impact of data heterogeneity across devices and allow for packet losses by employing a robust gradient tracking strategy that relies on properly designed auxiliary variables for tracking and buffering the overall gradient vector. More importantly, the proposed method utilizes two spanning-tree graphs for communication so long as both share at least one common root, enabling flexible designs in communication architectures. We show that R-FAST converges in expectation to a neighborhood of the optimum with a geometric rate for smooth and strongly convex objectives; and to a stationary point with a sublinear rate for general non-convex settings. Extensive experiments demonstrate that R-FAST runs 1.5-2 times faster than synchronous benchmark algorithms, such as Ring-AllReduce and D-PSGD, while still achieving comparable accuracy, and outperforms existing asynchronous SOTA algorithms, such as AD-PSGD and OSGP, especially in the presence of stragglers.