# A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates

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

## Key facts

- Cited by 51 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Apr 2017.

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

- [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)
- [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)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning](https://mlsanity.com/paper/2111.04287/) (2021)
- [Finite-Bit Quantization For Distributed Algorithms With Linear Convergence](https://mlsanity.com/paper/2107.11304/) (2021)
- [Improving the Transient Times for Distributed Stochastic Gradient Methods](https://mlsanity.com/paper/2105.04851/) (2021)
- [Innovation Compression for Communication-efficient Distributed Optimization with Linear Convergence](https://mlsanity.com/paper/2105.06697/) (2021)
- [Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks](https://mlsanity.com/paper/2106.07243/) (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)
- [CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence](https://mlsanity.com/paper/2301.05872/) (2023)
- [Beyond Exponential Graph: Communication-Efficient Topologies for Decentralized Learning via Finite-time Convergence](https://mlsanity.com/paper/2305.11420/) (2023)
- [Decentralized Composite Optimization with Compression](https://mlsanity.com/paper/2108.04448/) (2021)
- [DSGD-CECA: Decentralized SGD with Communication-Optimal Exact Consensus Algorithm](https://mlsanity.com/paper/2306.00256/) (2023)
- [Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable](https://mlsanity.com/paper/2503.20117/) (2025)
- [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)
- [Fast and Robust Sparsity Learning over Networks: A Decentralized Surrogate Median Regression Approach](https://mlsanity.com/paper/2202.05498/) (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)
- [Enhancing Privacy in Federated Learning through Local Training](https://mlsanity.com/paper/2403.17572/) (2024)
- [Understanding A Class of Decentralized and Federated Optimization Algorithms: A Multi-Rate Feedback Control Perspective](https://mlsanity.com/paper/2204.12663/) (2022)
- [Communication Compression for Decentralized Learning with Operator Splitting Methods](https://mlsanity.com/paper/2205.03779/) (2022)
- [Distributed Random Reshuffling Methods with Improved Convergence](https://mlsanity.com/paper/2306.12037/) (2023)

## Abstract (arXiv)

This paper proposes a novel proximal-gradient algorithm for a decentralized optimization problem with a composite objective containing smooth and non-smooth terms. Specifically, the smooth and nonsmooth terms are dealt with by gradient and proximal updates, respectively. The proposed algorithm is closely related to a previous algorithm, PG-EXTRA citeshi2015proximal, but has a few advantages. First of all, agents use uncoordinated step-sizes, and the stable upper bounds on step-sizes are independent of network topologies. The step-sizes depend on local objective functions, and they can be as large as those of the gradient descent. Secondly, for the special case without non-smooth terms, linear convergence can be achieved under the strong convexity assumption. The dependence of the convergence rate on the objective functions and the network are separated, and the convergence rate of the new algorithm is as good as one of the two convergence rates that match the typical rates for the general gradient descent and the consensus averaging. We provide numerical experiments to demonstrate the efficacy of the introduced algorithm and validate our theoretical discoveries.