# Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Feb 2020.

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

- [Finite-Bit Quantization For Distributed Algorithms With Linear Convergence](https://mlsanity.com/paper/2107.11304/) (2021)
- [Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework](https://mlsanity.com/paper/2503.14353/) (2025)
- [CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence](https://mlsanity.com/paper/2301.05872/) (2023)
- [Hierarchical Federated Learning with Multi-Timescale Gradient Correction](https://mlsanity.com/paper/2409.18448/) (2024)
- [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)
- [A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic Composite Optimization](https://mlsanity.com/paper/2302.09766/) (2023)
- [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)
- [Federated Composite Saddle Point Optimization](https://mlsanity.com/paper/2305.15643/) (2023)
- [Estimation Network Design framework for efficient distributed optimization](https://mlsanity.com/paper/2404.15273/) (2024)
- [Contractivity and linear convergence in bilinear saddle-point problems: An operator-theoretic approach](https://mlsanity.com/paper/2410.14592/) (2024)
- [Diffusion Learning with Partial Agent Participation and Local Updates](https://mlsanity.com/paper/2505.11307/) (2025)
- [Local adapt-then-combine algorithms for distributed nonsmooth optimization: Achieving provable communication acceleration](https://mlsanity.com/paper/2602.16148/) (2026)
- [A distributed semismooth Newton based augmented Lagrangian method for distributed optimization](https://mlsanity.com/paper/2602.23854/) (2026)

## Abstract (arXiv)

We study distributed composite optimization over networks: agents minimize a sum of smooth (strongly) convex functions, the agents' sum-utility, plus a nonsmooth (extended-valued) convex one. We propose a general unified algorithmic framework for such a class of problems and provide a unified convergence analysis leveraging the theory of operator splitting. Distinguishing features of our scheme are: (i) When the agents' functions are strongly convex, the algorithm converges at a linear rate, whose dependence on the agents' functions and network topology is decoupled, matching the typical rates of centralized optimization; the rate expression improves on existing results; (ii) When the objective function is convex (but not strongly convex), similar separation as in (i) is established for the coefficient of the proved sublinear rate; (iii) The algorithm can adjust the ratio between the number of communications and computations to achieve a rate (in terms of computations) independent on the network connectivity; and (iv) A by-product of our analysis is a tuning recommendation for several existing (non accelerated) distributed algorithms yielding the fastest provably (worst-case) convergence rate. This is the first time that a general distributed algorithmic framework applicable to composite optimization enjoys all such properties.