# Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization

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

## Key facts

- Cited by 116 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jun 2015.

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

- [Federated Learning with Buffered Asynchronous Aggregation](https://mlsanity.com/paper/2106.06639/) (2021)
- [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)
- [Byzantine Machine Learning Made Easy by Resilient Averaging of Momentums](https://mlsanity.com/paper/2205.12173/) (2022)
- [Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays](https://mlsanity.com/paper/2206.07638/) (2022)
- [Decentralized Federated Learning: Balancing Communication and Computing Costs](https://mlsanity.com/paper/2107.12048/) (2021)
- [FederatedScope: A Flexible Federated Learning Platform for Heterogeneity](https://mlsanity.com/paper/2204.05011/) (2022)
- [Multiplayer Performative Prediction: Learning in Decision-Dependent Games](https://mlsanity.com/paper/2201.03398/) (2022)
- [Anarchic Federated Learning](https://mlsanity.com/paper/2108.09875/) (2021)
- [Secure Bilevel Asynchronous Vertical Federated Learning with Backward Updating](https://mlsanity.com/paper/2103.00958/) (2021)
- [Mobility-Aware Cluster Federated Learning in Hierarchical Wireless Networks](https://mlsanity.com/paper/2108.09103/) (2021)
- [Asynchronous Stochastic Optimization Robust to Arbitrary Delays](https://mlsanity.com/paper/2106.11879/) (2021)
- [DataLens: Scalable Privacy Preserving Training via Gradient Compression and Aggregation](https://mlsanity.com/paper/2103.11109/) (2021)
- [HET: Scaling out Huge Embedding Model Training via Cache-enabled Distributed Framework](https://mlsanity.com/paper/2112.07221/) (2021)
- [DoCoFL: Downlink Compression for Cross-Device Federated Learning](https://mlsanity.com/paper/2302.00543/) (2023)
- [FLUTE: A Scalable, Extensible Framework for High-Performance Federated Learning Simulations](https://mlsanity.com/paper/2203.13789/) (2022)
- [Asynchronous Local-SGD Training for Language Modeling](https://mlsanity.com/paper/2401.09135/) (2024)
- [Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization](https://mlsanity.com/paper/2102.07245/) (2021)
- [SWIFT: Rapid Decentralized Federated Learning via Wait-Free Model Communication](https://mlsanity.com/paper/2210.14026/) (2022)
- [Epidemic Learning: Boosting Decentralized Learning with Randomized Communication](https://mlsanity.com/paper/2310.01972/) (2023)
- [AsyncFedED: Asynchronous Federated Learning with Euclidean Distance based Adaptive Weight Aggregation](https://mlsanity.com/paper/2205.13797/) (2022)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees](https://mlsanity.com/paper/2109.04522/) (2021)
- [Persia: An Open, Hybrid System Scaling Deep Learning-based Recommenders up to 100 Trillion Parameters](https://mlsanity.com/paper/2111.05897/) (2021)
- [A General Theory for Federated Optimization with Asynchronous and Heterogeneous Clients Updates](https://mlsanity.com/paper/2206.10189/) (2022)
- [Truly Sparse Neural Networks at Scale](https://mlsanity.com/paper/2102.01732/) (2021)
- [On the Role of Server Momentum in Federated Learning](https://mlsanity.com/paper/2312.12670/) (2023)
- [Maximizing Communication Efficiency for Large-scale Training via 0/1 Adam](https://mlsanity.com/paper/2202.06009/) (2022)
- [Citadel: Protecting Data Privacy and Model Confidentiality for Collaborative Learning with SGX](https://mlsanity.com/paper/2105.01281/) (2021)
- [DORA: A Scalable Asynchronous Reinforcement Learning System for Language Model Training](https://mlsanity.com/paper/2604.26256/) (2026)

## Abstract (arXiv)

Asynchronous parallel implementations of stochastic gradient (SG) have been broadly used in solving deep neural network and received many successes in practice recently. However, existing theories cannot explain their convergence and speedup properties, mainly due to the nonconvexity of most deep learning formulations and the asynchronous parallel mechanism. To fill the gaps in theory and provide theoretical supports, this paper studies two asynchronous parallel implementations of SG: one is on the computer network and the other is on the shared memory system. We establish an ergodic convergence rate O(1/√K) for both algorithms and prove that the linear speedup is achievable if the number of workers is bounded by √K (K is the total number of iterations). Our results generalize and improve existing analysis for convex minimization.