# Second-order Guarantees of Distributed Gradient Algorithms

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Sep 2018.

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

- [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)
- [Quantization Avoids Saddle Points in Distributed Optimization](https://mlsanity.com/paper/2403.10423/) (2024)
- [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)

## Abstract (arXiv)

We consider distributed smooth nonconvex unconstrained optimization over networks, modeled as a connected graph. We examine the behavior of distributed gradient-based algorithms near strict saddle points. Specifically, we establish that (i) the renowned Distributed Gradient Descent (DGD) algorithm likely converges to a neighborhood of a Second-order Stationary (SoS) solution; and (ii) the more recent class of distributed algorithms based on gradient tracking--implementable also over digraphs--likely converges to exact SoS solutions, thus avoiding (strict) saddle-points. Furthermore, new convergence rate results to first-order critical points is established for the latter class of algorithms.