# Distributed Learning in Non-Convex Environments -- Part II: Polynomial Escape from Saddle-Points

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jul 2019.

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

- [A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2102.06752/) (2021)
- [Networked Signal and Information Processing](https://mlsanity.com/paper/2210.13767/) (2022)
- [Distributed Adaptive Learning Under Communication Constraints](https://mlsanity.com/paper/2112.02129/) (2021)
- [Decentralized Adversarial Training over Graphs](https://mlsanity.com/paper/2303.13326/) (2023)
- [On the Trade-off between Flatness and Optimization in Distributed Learning](https://mlsanity.com/paper/2406.20006/) (2024)
- [Robust and Efficient Aggregation for Distributed Learning](https://mlsanity.com/paper/2204.00586/) (2022)
- [Multi-Agent Adversarial Training Using Diffusion Learning](https://mlsanity.com/paper/2303.01936/) (2023)
- [Quantization Avoids Saddle Points in Distributed Optimization](https://mlsanity.com/paper/2403.10423/) (2024)
- [High-Probability Convergence Guarantees of Decentralized SGD](https://mlsanity.com/paper/2510.06141/) (2025)
- [Exact Subspace Diffusion for Decentralized Multitask Learning](https://mlsanity.com/paper/2304.07358/) (2023)
- [Deep-Relative-Trust-Based Diffusion for Decentralized Deep Learning](https://mlsanity.com/paper/2501.03162/) (2025)
- [On the Escaping Efficiency of Distributed Adversarial Training Algorithms](https://mlsanity.com/paper/2509.11337/) (2025)
- [High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking](https://mlsanity.com/paper/2605.00281/) (2026)

## Abstract (arXiv)

The diffusion strategy for distributed learning from streaming data employs local stochastic gradient updates along with exchange of iterates over neighborhoods. In Part I [2] of this work we established that agents cluster around a network centroid and proceeded to study the dynamics of this point. We established expected descent in non-convex environments in the large-gradient regime and introduced a short-term model to examine the dynamics over finite-time horizons. Using this model, we establish in this work that the diffusion strategy is able to escape from strict saddle-points in O(1/μ) iterations; it is also able to return approximately second-order stationary points in a polynomial number of iterations. Relative to prior works on the polynomial escape from saddle-points, most of which focus on centralized perturbed or stochastic gradient descent, our approach requires less restrictive conditions on the gradient noise process.