# Decentralized Proximal Gradient Algorithms with Linear Convergence Rates

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

## Key facts

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

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

- [An Improved Analysis of Gradient Tracking for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03836/) (2022)
- [Decentralized Riemannian Gradient Descent on the Stiefel Manifold](https://mlsanity.com/paper/2102.07091/) (2021)
- [Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD](https://mlsanity.com/paper/2105.08023/) (2021)
- [A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2102.06752/) (2021)
- [Finite-Bit Quantization For Distributed Algorithms With Linear Convergence](https://mlsanity.com/paper/2107.11304/) (2021)
- [Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization](https://mlsanity.com/paper/2104.02596/) (2021)
- [Networked Signal and Information Processing](https://mlsanity.com/paper/2210.13767/) (2022)
- [Decentralized Composite Optimization with Compression](https://mlsanity.com/paper/2108.04448/) (2021)
- [Decentralized Riemannian Conjugate Gradient Method on the Stiefel Manifold](https://mlsanity.com/paper/2308.10547/) (2023)
- [DISA: A Dual Inexact Splitting Algorithm for Distributed Convex Composite Optimization](https://mlsanity.com/paper/2209.01850/) (2022)
- [Decentralized Inexact Proximal Gradient Method With Network-Independent Stepsizes for Convex Composite Optimization](https://mlsanity.com/paper/2302.03238/) (2023)
- [Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization](https://mlsanity.com/paper/2111.03820/) (2021)
- [Distributed Random Reshuffling Methods with Improved Convergence](https://mlsanity.com/paper/2306.12037/) (2023)
- [A Proximal Gradient Method With Probabilistic Multi-Gossip Communications for Decentralized Composite Optimization](https://mlsanity.com/paper/2312.11861/) (2023)
- [Diffusion Stochastic Optimization for Min-Max Problems](https://mlsanity.com/paper/2401.14585/) (2024)
- [Optimized Gradient Tracking for Decentralized Online Learning](https://mlsanity.com/paper/2306.06375/) (2023)
- [Decentralized Optimization on Compact Submanifolds by Quantized Riemannian Gradient Tracking](https://mlsanity.com/paper/2506.07351/) (2025)
- [MUSIC: Accelerated Convergence for Distributed Optimization With Inexact and Exact Methods](https://mlsanity.com/paper/2403.02589/) (2024)
- [Local adapt-then-combine algorithms for distributed nonsmooth optimization: Achieving provable communication acceleration](https://mlsanity.com/paper/2602.16148/) (2026)

## Abstract (arXiv)

This work studies a class of non-smooth decentralized multi-agent optimization problems where the agents aim at minimizing a sum of local strongly-convex smooth components plus a common non-smooth term. We propose a general primal-dual algorithmic framework that unifies many existing state-of-the-art algorithms. We establish linear convergence of the proposed method to the exact solution in the presence of the non-smooth term. Moreover, for the more general class of problems with agent specific non-smooth terms, we show that linear convergence cannot be achieved (in the worst case) for the class of algorithms that uses the gradients and the proximal mappings of the smooth and non-smooth parts, respectively. We further provide a numerical counterexample that shows how some state-of-the-art algorithms fail to converge linearly for strongly-convex objectives and different local non-smooth terms.