# Local adapt-then-combine algorithms for distributed nonsmooth optimization: Achieving provable communication acceleration

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 34 references that are in the map.
- First posted on arXiv 18 Feb 2026.

## Builds on (most cited first, 21 of 21)

- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [D2: Decentralized Training over Decentralized Data](https://mlsanity.com/paper/1803.07068/) (2018)
- [ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!](https://mlsanity.com/paper/2202.09357/) (2022)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017)
- [A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates](https://mlsanity.com/paper/1704.07807/) (2017)
- [Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development](https://mlsanity.com/paper/1702.05122/) (2017)
- [Decentralized Gradient Tracking with Local Steps](https://mlsanity.com/paper/2301.01313/) (2023)
- [Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD](https://mlsanity.com/paper/2105.08023/) (2021)
- [RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates](https://mlsanity.com/paper/2207.12891/) (2022)
- [Local Exact-Diffusion for Decentralized Optimization and Learning](https://mlsanity.com/paper/2302.00620/) (2023)
- [On the Performance of Gradient Tracking with Local Updates](https://mlsanity.com/paper/2210.04757/) (2022)
- [Decentralized Proximal Gradient Algorithms with Linear Convergence Rates](https://mlsanity.com/paper/1909.06479/) (2019)
- [Optimal Gradient Tracking for Decentralized Optimization](https://mlsanity.com/paper/2110.05282/) (2021)
- [Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis](https://mlsanity.com/paper/2002.11534/) (2020)
- [Geometrically Convergent Distributed Optimization with Uncoordinated Step-Sizes](https://mlsanity.com/paper/1609.05877/) (2016)
- [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)
- [Harnessing Smoothness to Accelerate Distributed Optimization](https://mlsanity.com/paper/1605.07112/) (2016)
- [A Proximal Gradient Method With Probabilistic Multi-Gossip Communications for Decentralized Composite Optimization](https://mlsanity.com/paper/2312.11861/) (2023)

## Abstract (arXiv)

This paper is concerned with the distributed composite optimization problem over networks, where agents aim to minimize a sum of local smooth components and a common nonsmooth term. Leveraging the probabilistic local updates mechanism, we propose a communication-efficient Adapt-Then-Combine (ATC) framework, FlexATC, unifying numerous ATC-based distributed algorithms. Under stepsizes independent of the network topology and the number of local updates, we establish sublinear and linear convergence rates for FlexATC in convex and strongly convex settings, respectively. Remarkably, in the strong convex setting, the linear rate is decoupled from the objective functions and network topology, and FlexATC permits communication to be skipped in most iterations without any deterioration of the linear rate. In addition, the proposed unified theory demonstrates for the first time that local updates provably lead to communication acceleration for ATC-based distributed algorithms. Numerical experiments further validate the efficacy of the proposed framework and corroborate the theoretical results.