# Distributed Learning in Non-Convex Environments -- Part I: Agreement at a Linear Rate

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

## Key facts

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

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

- [Distributed Adaptive Learning Under Communication Constraints](https://mlsanity.com/paper/2112.02129/) (2021)
- [Optimizing Communication and Device Clustering for Clustered Federated Learning with Differential Privacy](https://mlsanity.com/paper/2507.07320/) (2025)
- [Enforcing Privacy in Distributed Learning with Performance Guarantees](https://mlsanity.com/paper/2301.06412/) (2023)
- [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)
- [Local Model Reconstruction Attacks in Federated Learning and their Uses](https://mlsanity.com/paper/2210.16205/) (2022)
- [Multi-Agent Adversarial Training Using Diffusion Learning](https://mlsanity.com/paper/2303.01936/) (2023)
- [Diffusion Stochastic Optimization for Min-Max Problems](https://mlsanity.com/paper/2401.14585/) (2024)
- [Quantization Avoids Saddle Points in Distributed Optimization](https://mlsanity.com/paper/2403.10423/) (2024)
- [Competing Adaptive Networks](https://mlsanity.com/paper/2103.15664/) (2021)
- [Communication-Efficient {Federated} Learning Using Censored Heavy Ball Descent](https://mlsanity.com/paper/2209.11944/) (2022)
- [Asynchronous Diffusion Learning with Agent Subsampling and Local Updates](https://mlsanity.com/paper/2402.05529/) (2024)
- [Attribute Inference Attacks for Federated Regression Tasks](https://mlsanity.com/paper/2411.12697/) (2024)
- [High-Probability Convergence Guarantees of Decentralized SGD](https://mlsanity.com/paper/2510.06141/) (2025)
- [On the dynamics of multi agent nonlinear filtering and learning](https://mlsanity.com/paper/2309.03557/) (2023)
- [Asynchronous Message-Passing and Zeroth-Order Optimization Based Distributed Learning with a Use-Case in Resource Allocation in Communication Networks](https://mlsanity.com/paper/2311.04604/) (2023)
- [Deep-Relative-Trust-Based Diffusion for Decentralized Deep Learning](https://mlsanity.com/paper/2501.03162/) (2025)
- [Diffusion Stochastic Learning Over Adaptive Competing Networks](https://mlsanity.com/paper/2504.19635/) (2025)
- [On the Escaping Efficiency of Distributed Adversarial Training Algorithms](https://mlsanity.com/paper/2509.11337/) (2025)
- [Stability and Generalization of Adversarial Diffusion Training](https://mlsanity.com/paper/2509.19234/) (2025)
- [Topology-Independent Robustness of the Weighted Mean under Label Poisoning Attacks in Heterogeneous Decentralized Learning](https://mlsanity.com/paper/2601.02682/) (2026)
- [High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking](https://mlsanity.com/paper/2605.00281/) (2026)

## Abstract (arXiv)

Driven by the need to solve increasingly complex optimization problems in signal processing and machine learning, there has been increasing interest in understanding the behavior of gradient-descent algorithms in non-convex environments. Most available works on distributed non-convex optimization problems focus on the deterministic setting where exact gradients are available at each agent. In this work and its Part II, we consider stochastic cost functions, where exact gradients are replaced by stochastic approximations and the resulting gradient noise persistently seeps into the dynamics of the algorithm. We establish that the diffusion learning strategy continues to yield meaningful estimates non-convex scenarios in the sense that the iterates by the individual agents will cluster in a small region around the network centroid. We use this insight to motivate a short-term model for network evolution over a finite-horizon. In Part II [2] of this work, we leverage this model to establish descent of the diffusion strategy through saddle points in O(1/μ) steps and the return of approximately second-order stationary points in a polynomial number of iterations.