# A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning

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

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Oct 2021.

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

- [Exponential Graph is Provably Efficient for Decentralized Deep Training](https://mlsanity.com/paper/2110.13363/) (2021)
- [Topology-aware Generalization of Decentralized SGD](https://mlsanity.com/paper/2206.12680/) (2022)
- [Momentum Benefits Non-IID Federated Learning Simply and Provably](https://mlsanity.com/paper/2306.16504/) (2023)
- [Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression](https://mlsanity.com/paper/2206.03665/) (2022)
- [Communication-Efficient Topologies for Decentralized Learning with O(1) Consensus Rate](https://mlsanity.com/paper/2210.07881/) (2022)
- [Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization](https://mlsanity.com/paper/2210.07863/) (2022)
- [On the Performance of Gradient Tracking with Local Updates](https://mlsanity.com/paper/2210.04757/) (2022)
- [BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning](https://mlsanity.com/paper/2111.04287/) (2021)
- [Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?](https://mlsanity.com/paper/2305.16297/) (2023)
- [Data-heterogeneity-aware Mixing for Decentralized Learning](https://mlsanity.com/paper/2204.06477/) (2022)
- [Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compression](https://mlsanity.com/paper/2305.07612/) (2023)
- [CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence](https://mlsanity.com/paper/2301.05872/) (2023)
- [Distributed Random Reshuffling over Networks](https://mlsanity.com/paper/2112.15287/) (2021)
- [DSGD-CECA: Decentralized SGD with Communication-Optimal Exact Consensus Algorithm](https://mlsanity.com/paper/2306.00256/) (2023)
- [Optimal Complexity in Non-Convex Decentralized Learning over Time-Varying Networks](https://mlsanity.com/paper/2211.00533/) (2022)
- [Distributed Stochastic Optimization under a General Variance Condition](https://mlsanity.com/paper/2301.12677/) (2023)
- [Generalization Error Matters in Decentralized Learning Under Byzantine Attacks](https://mlsanity.com/paper/2407.08632/) (2024)
- [Communication-Efficient Stochastic Distributed Learning](https://mlsanity.com/paper/2501.13516/) (2025)
- [An Efficient Subspace Algorithm for Federated Learning on Heterogeneous Data](https://mlsanity.com/paper/2509.05213/) (2025)
- [Towards Understanding Generalization and Stability Gaps between Centralized and Decentralized Federated Learning](https://mlsanity.com/paper/2310.03461/) (2023)
- [On the Trade-off between Flatness and Optimization in Distributed Learning](https://mlsanity.com/paper/2406.20006/) (2024)
- [Distributed Random Reshuffling Methods with Improved Convergence](https://mlsanity.com/paper/2306.12037/) (2023)
- [Locally Differentially Private Gradient Tracking for Distributed Online Learning over Directed Graphs](https://mlsanity.com/paper/2310.16105/) (2023)
- [Diffusion Stochastic Optimization for Min-Max Problems](https://mlsanity.com/paper/2401.14585/) (2024)
- [Argus: Federated Non-convex Bilevel Learning over 6G Space-Air-Ground Integrated Network](https://mlsanity.com/paper/2505.09106/) (2025)
- [Convergence Theory of Generalized Distributed Subgradient Method with Random Quantization](https://mlsanity.com/paper/2207.10969/) (2022)
- [Optimized Gradient Tracking for Decentralized Online Learning](https://mlsanity.com/paper/2306.06375/) (2023)
- [Online Distributed Learning with Quantized Finite-Time Coordination](https://mlsanity.com/paper/2307.06620/) (2023)
- [Achieving Linear Speedup with ProxSkip in Distributed Stochastic Optimization](https://mlsanity.com/paper/2310.07983/) (2023)
- [Adjacent Leader Decentralized Stochastic Gradient Descent](https://mlsanity.com/paper/2405.11389/) (2024)

## Abstract (arXiv)

We study the consensus decentralized optimization problem where the objective function is the average of n agents private non-convex cost functions; moreover, the agents can only communicate to their neighbors on a given network topology. The stochastic learning setting is considered in this paper where each agent can only access a noisy estimate of its gradient. Many decentralized methods can solve such problem including EXTRA, Exact-Diffusion/D2, and gradient-tracking. Unlike the famed DSGD algorithm, these methods have been shown to be robust to the heterogeneity across the local cost functions. However, the established convergence rates for these methods indicate that their sensitivity to the network topology is worse than DSGD. Such theoretical results imply that these methods can perform much worse than DSGD over sparse networks, which, however, contradicts empirical experiments where DSGD is observed to be more sensitive to the network topology. In this work, we study a general stochastic unified decentralized algorithm (SUDA) that includes the above methods as special cases. We establish the convergence of SUDA under both non-convex and the Polyak-Lojasiewicz condition settings. Our results provide improved network topology dependent bounds for these methods (such as Exact-Diffusion/D2 and gradient-tracking) compared with existing literature. Moreover, our results show that these methods are often less sensitive to the network topology compared to DSGD, which agrees with numerical experiments.