# On Nonconvex Decentralized Gradient Descent

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

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Aug 2016.

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

- [Decentralized Federated Averaging](https://mlsanity.com/paper/2104.11375/) (2021)
- [Semi-Decentralized Federated Learning with Collaborative Relaying](https://mlsanity.com/paper/2205.10998/) (2022)
- [NET-FLEET: Achieving Linear Convergence Speedup for Fully Decentralized Federated Learning with Heterogeneous Data](https://mlsanity.com/paper/2208.08490/) (2022)
- [1-Bit Compressive Sensing for Efficient Federated Learning Over the Air](https://mlsanity.com/paper/2103.16055/) (2021)
- [Decentralized Optimization Over the Stiefel Manifold by an Approximate Augmented Lagrangian Function](https://mlsanity.com/paper/2112.14949/) (2021)
- [Decentralized Nonconvex Optimization with Guaranteed Privacy and Accuracy](https://mlsanity.com/paper/2212.07534/) (2022)
- [GT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex Learning](https://mlsanity.com/paper/2105.01231/) (2021)
- [Distributed Random Reshuffling over Networks](https://mlsanity.com/paper/2112.15287/) (2021)
- [Decentralized Riemannian Conjugate Gradient Method on the Stiefel Manifold](https://mlsanity.com/paper/2308.10547/) (2023)
- [The Effectiveness of Local Updates for Decentralized Learning under Data Heterogeneity](https://mlsanity.com/paper/2403.15654/) (2024)
- [Learning to Coordinate in Multi-Agent Systems: A Coordinated Actor-Critic Algorithm and Finite-Time Guarantees](https://mlsanity.com/paper/2110.05597/) (2021)
- [Federated Semi-Supervised Learning with Class Distribution Mismatch](https://mlsanity.com/paper/2111.00010/) (2021)
- [Theoretically Principled Federated Learning for Balancing Privacy and Utility](https://mlsanity.com/paper/2305.15148/) (2023)
- [Coordination-free Decentralised Federated Learning on Complex Networks: Overcoming Heterogeneity](https://mlsanity.com/paper/2312.04504/) (2023)
- [Robust Federated Learning with Connectivity Failures: A Semi-Decentralized Framework with Collaborative Relaying](https://mlsanity.com/paper/2202.11850/) (2022)
- [DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over Graphs](https://mlsanity.com/paper/2208.13810/) (2022)
- [Collaborative Learning over Wireless Networks: An Introductory Overview](https://mlsanity.com/paper/2112.05559/) (2021)
- [A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic Composite Optimization](https://mlsanity.com/paper/2302.09766/) (2023)
- [From promise to practice: realizing high-performance decentralized training](https://mlsanity.com/paper/2410.11998/) (2024)
- [A Variance-Reduced Stochastic Gradient Tracking Algorithm for Decentralized Optimization with Orthogonality Constraints](https://mlsanity.com/paper/2208.13643/) (2022)
- [Distributed Online Non-convex Optimization with Composite Regret](https://mlsanity.com/paper/2209.10105/) (2022)
- [Accelerating Parallel Stochastic Gradient Descent via Non-blocking Mini-batches](https://mlsanity.com/paper/2211.00889/) (2022)
- [A Penalty-Based Method for Communication-Efficient Decentralized Bilevel Programming](https://mlsanity.com/paper/2211.04088/) (2022)
- [Quantization Avoids Saddle Points in Distributed Optimization](https://mlsanity.com/paper/2403.10423/) (2024)
- [DeCAF: Decentralized Consensus-And-Factorization for Low-Rank Adaptation of Foundation Models](https://mlsanity.com/paper/2505.21382/) (2025)
- [Decentralized Statistical Inference with Unrolled Graph Neural Networks](https://mlsanity.com/paper/2104.01555/) (2021)
- [Distributed Sparse Regression via Penalization](https://mlsanity.com/paper/2111.06530/) (2021)
- [Decentralized Weakly Convex Optimization Over the Stiefel Manifold](https://mlsanity.com/paper/2303.17779/) (2023)
- [Asynchronous Distributed Optimization with Delay-free Parameters](https://mlsanity.com/paper/2312.06508/) (2023)
- [Convergence of Decentralized Stochastic Subgradient-based Methods for Nonsmooth Nonconvex functions](https://mlsanity.com/paper/2403.11565/) (2024)

## Abstract (arXiv)

Consensus optimization has received considerable attention in recent years. A number of decentralized algorithms have been proposed for convex consensus optimization. However, to the behaviors or consensus nonconvex optimization, our understanding is more limited. When we lose convexity, we cannot hope our algorithms always return global solutions though they sometimes still do sometimes. Somewhat surprisingly, the decentralized consensus algorithms, DGD and Prox-DGD, retain most other properties that are known in the convex setting. In particular, when diminishing (or constant) step sizes are used, we can prove convergence to a (or a neighborhood of) consensus stationary solution under some regular assumptions. It is worth noting that Prox-DGD can handle nonconvex nonsmooth functions if their proximal operators can be computed. Such functions include SCAD and ℓq quasi-norms, q∈[0,1). Similarly, Prox-DGD can take the constraint to a nonconvex set with an easy projection. To establish these properties, we have to introduce a completely different line of analysis, as well as modify existing proofs that were used the convex setting.