# A Linearly Convergent Proximal Gradient Algorithm for Decentralized Optimization

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2019.

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

- [Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization](https://mlsanity.com/paper/2102.07245/) (2021)
- [Decentralized Composite Optimization with Compression](https://mlsanity.com/paper/2108.04448/) (2021)
- [Dynamic Privacy Allocation for Locally Differentially Private Federated Learning with Composite Objectives](https://mlsanity.com/paper/2308.01139/) (2023)
- [A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic Composite Optimization](https://mlsanity.com/paper/2302.09766/) (2023)
- [Decentralized Sum-of-Nonconvex Optimization](https://mlsanity.com/paper/2402.02356/) (2024)
- [Diffusion Learning with Partial Agent Participation and Local Updates](https://mlsanity.com/paper/2505.11307/) (2025)

## Abstract (arXiv)

Decentralized optimization is a powerful paradigm that finds applications in engineering and learning design. This work studies decentralized composite optimization problems with non-smooth regularization terms. Most existing gradient-based proximal decentralized methods are known to converge to the optimal solution with sublinear rates, and it remains unclear whether this family of methods can achieve global linear convergence. To tackle this problem, this work assumes the non-smooth regularization term is common across all networked agents, which is the case for many machine learning problems. Under this condition, we design a proximal gradient decentralized algorithm whose fixed point coincides with the desired minimizer. We then provide a concise proof that establishes its linear convergence. In the absence of the non-smooth term, our analysis technique covers the well known EXTRA algorithm and provides useful bounds on the convergence rate and step-size.