# Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and Network-Independent Performance for Strongly Convex Functions

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2018.

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

- [Communication-efficient SGD: From Local SGD to One-Shot Averaging](https://mlsanity.com/paper/2106.04759/) (2021)
- [Improving the Transient Times for Distributed Stochastic Gradient Methods](https://mlsanity.com/paper/2105.04851/) (2021)
- [Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization](https://mlsanity.com/paper/2104.02596/) (2021)
- [CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence](https://mlsanity.com/paper/2301.05872/) (2023)
- [Efficient Federated Learning against Heterogeneous and Non-stationary Client Unavailability](https://mlsanity.com/paper/2409.17446/) (2024)
- [PersA-FL: Personalized Asynchronous Federated Learning](https://mlsanity.com/paper/2210.01176/) (2022)
- [DRACO: Decentralized Asynchronous Federated Learning over Row-Stochastic Wireless Networks](https://mlsanity.com/paper/2406.13533/) (2024)
- [Log-Scale Quantization in Distributed First-Order Methods: Gradient-based Learning from Distributed Data](https://mlsanity.com/paper/2406.00621/) (2024)
- [Empowering Federated Learning with Implicit Gossiping: Mitigating Connection Unreliability Amidst Unknown and Arbitrary Dynamics](https://mlsanity.com/paper/2404.10091/) (2024)
- [Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization](https://mlsanity.com/paper/2111.03820/) (2021)
- [Variance reduced stochastic optimization over directed graphs with row and column stochastic weights](https://mlsanity.com/paper/2202.03346/) (2022)
- [Robust Fully-Asynchronous Methods for Distributed Training over General Architecture](https://mlsanity.com/paper/2307.11617/) (2023)
- [Asynchronous Distributed Optimization with Delay-free Parameters](https://mlsanity.com/paper/2312.06508/) (2023)
- [A Bias-Correction Decentralized Stochastic Gradient Algorithm with Momentum Acceleration](https://mlsanity.com/paper/2501.19082/) (2025)
- [Fast and Robust State Estimation and Tracking via Hierarchical Learning](https://mlsanity.com/paper/2306.17267/) (2023)
- [Network Fault-tolerant and Byzantine-resilient Social Learning via Collaborative Hierarchical Non-Bayesian Learning](https://mlsanity.com/paper/2307.14952/) (2023)
- [Asynchronous Decentralized SGD under Non-Convexity: A Block-Coordinate Descent Framework](https://mlsanity.com/paper/2505.10322/) (2025)
- [Machine Learning and CPU (Central Processing Unit) Scheduling Co-Optimization over a Network of Computing Centers](https://mlsanity.com/paper/2510.25176/) (2025)
- [Optimizing Stochastic Gradient Push under Broadcast Communications](https://mlsanity.com/paper/2604.15549/) (2026)
- [Using Non-Lipschitz Signum-based Functions for Distributed Optimization and Machine Learning: Trade-off Between Con-vergence Rate and Optimality Gap](https://mlsanity.com/paper/2608.01220/) (2026)

## Abstract (arXiv)

We consider the standard model of distributed optimization of a sum of functions F(bz) = sumi=1n fi(bz), where node i in a network holds the function fi(bz). We allow for a harsh network model characterized by asynchronous updates, message delays, unpredictable message losses, and directed communication among nodes. In this setting, we analyze a modification of the Gradient-Push method for distributed optimization, assuming that beginenumerate*[label=(roman*)] item node i is capable of generating gradients of its function fi(bz) corrupted by zero-mean bounded-support additive noise at each step, item F(bz) is strongly convex, and item each fi(bz) has Lipschitz gradients. We show that our proposed method asymptotically performs as well as the best bounds on centralized gradient descent that takes steps in the direction of the sum of the noisy gradients of all the functions f1(bz), ldots, fn(bz) at each step.