# An improved convergence analysis for decentralized online stochastic non-convex optimization

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

## Key facts

- Cited by 53 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Aug 2020.

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

- [Exponential Graph is Provably Efficient for Decentralized Deep Training](https://mlsanity.com/paper/2110.13363/) (2021)
- [DecentLaM: Decentralized Momentum SGD for Large-batch Deep Training](https://mlsanity.com/paper/2104.11981/) (2021)
- [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)
- [Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks](https://mlsanity.com/paper/2206.10870/) (2022)
- [Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD](https://mlsanity.com/paper/2105.08023/) (2021)
- [Accelerating Gossip SGD with Periodic Global Averaging](https://mlsanity.com/paper/2105.09080/) (2021)
- [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)
- [A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2102.06752/) (2021)
- [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)
- [Improving the Transient Times for Distributed Stochastic Gradient Methods](https://mlsanity.com/paper/2105.04851/) (2021)
- [NET-FLEET: Achieving Linear Convergence Speedup for Fully Decentralized Federated Learning with Heterogeneous Data](https://mlsanity.com/paper/2208.08490/) (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)
- [On Generalization of Decentralized Learning with Separable Data](https://mlsanity.com/paper/2209.07116/) (2022)
- [Distributed Random Reshuffling over Networks](https://mlsanity.com/paper/2112.15287/) (2021)
- [The Effectiveness of Local Updates for Decentralized Learning under Data Heterogeneity](https://mlsanity.com/paper/2403.15654/) (2024)
- [Federated Learning for Diffusion Models](https://mlsanity.com/paper/2503.06426/) (2025)
- [Heavy-Tail Phenomenon in Decentralized SGD](https://mlsanity.com/paper/2205.06689/) (2022)
- [Distributed Learning over Networks with Graph-Attention-Based Personalization](https://mlsanity.com/paper/2305.13041/) (2023)
- [DSGD-CECA: Decentralized SGD with Communication-Optimal Exact Consensus Algorithm](https://mlsanity.com/paper/2306.00256/) (2023)
- [PRECISION: Decentralized Constrained Min-Max Learning with Low Communication and Sample Complexities](https://mlsanity.com/paper/2303.02532/) (2023)
- [Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning](https://mlsanity.com/paper/2509.26442/) (2025)
- [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)
- [A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic Composite Optimization](https://mlsanity.com/paper/2302.09766/) (2023)
- [Variance reduced stochastic optimization over directed graphs with row and column stochastic weights](https://mlsanity.com/paper/2202.03346/) (2022)

## Abstract (arXiv)

In this paper, we study decentralized online stochastic non-convex optimization over a network of nodes. Integrating a technique called gradient tracking in decentralized stochastic gradient descent, we show that the resulting algorithm, GT-DSGD, enjoys certain desirable characteristics towards minimizing a sum of smooth non-convex functions. In particular, for general smooth non-convex functions, we establish non-asymptotic characterizations of GT-DSGD and derive the conditions under which it achieves network-independent performances that match the centralized minibatch SGD. In contrast, the existing results suggest that GT-DSGD is always network-dependent and is therefore strictly worse than the centralized minibatch SGD. When the global non-convex function additionally satisfies the Polyak-Lojasiewics (PL) condition, we establish the linear convergence of GT-DSGD up to a steady-state error with appropriate constant step-sizes. Moreover, under stochastic approximation step-sizes, we establish, for the first time, the optimal global sublinear convergence rate on almost every sample path, in addition to the asymptotically optimal sublinear rate in expectation. Since strongly convex functions are a special case of the functions satisfying the PL condition, our results are not only immediately applicable but also improve the currently known best convergence rates and their dependence on problem parameters.