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

Luyao Guo; Xinli Shi; Wenying Xu; Jinde Cao

math.OCFeb 18, 2026

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

Authors: Luyao Guo, Xinli Shi, Wenying Xu, Jinde Cao

Organizations: School of Computer Science and Engineering, Suzhou University of Technology, Suzhou 215500, China · School of Mathematics, Southeast University, Nanjing 210096, China · School of Cyber Science and Engineering, Southeast University, Nanjing 210096, China

Abstract

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.

Figures & tables

Algorithm	# of Comm.: $p=1$	LU?	Comm. Acc.?	# of Comm.: $p\in(0,1]$	LU?	Comm. Acc.?
Algorithm	literature [ 30 , 1 ]			this paper	this paper	this paper
(Prox-)NIDS/ED/D2	$\mathcal{O}\left(\frac{\kappa}{1-\rho}\log\epsilon^{-1}\right)$	✗	✗	$\mathcal{O}\left(\frac{\kappa}{1-\rho}\log\epsilon^{-1}\right)\xrightarrow[\text{{improved}}]{p=\frac{1}{\sqrt{\kappa(1-\rho)}}}\mathcal{O}\left(\sqrt{\frac{\kappa}{1-\rho}}\log\epsilon^{-1}\right)$	✓	✓
(Prox-)MG-ED	$\mathcal{O}\left(\frac{\kappa}{\sqrt{1-\rho}}\log\epsilon^{-1}\right)$	✗	✗	$\mathcal{O}\left(\frac{\kappa}{\sqrt{1-\rho}}\log\epsilon^{-1}\right)\xrightarrow[\text{{improved}}]{p=\frac{1}{\sqrt{\kappa}}}\mathcal{O}\left(\sqrt{\frac{\kappa}{1-\rho}}\log\epsilon^{-1}\right)$	✓	✓
(Prox-)ATC-GT	$\mathcal{O}\left(\frac{\kappa}{(1-\rho)^{2}}\log\epsilon^{-1}\right)$	✗	✗	$\mathcal{O}\left(\frac{\kappa}{(1-\rho)^{2}}\log\epsilon^{-1}\right)\xrightarrow[\text{{improved}}]{p=\frac{1}{\sqrt{\kappa(1-\rho)^{2}}}}\mathcal{O}\left(\frac{\sqrt{\kappa}}{1-\rho}\log\epsilon^{-1}\right)$	✓	✓
MG-SONATA	$\mathcal{O}\left(\frac{\kappa}{\sqrt{1-\rho}}\log\epsilon^{-1}\right)$	✗	✗	$\mathcal{O}\left(\frac{\kappa}{\sqrt{1-\rho}}\log\epsilon^{-1}\right)\xrightarrow[\text{{improved}}]{p=\frac{1}{\sqrt{\kappa}}}\mathcal{O}\left(\sqrt{\frac{\kappa}{1-\rho}}\log\epsilon^{-1}\right)$	✓	✓

Table 1: Comparison with existing ATC-based algorithm frameworks. LU = Local Updates, Comm. = Communication, Acc. = Acceleration.

Algorithm	$r\neq 0$	$\bm{A}$	$\bm{B}$	# of Comm.
(Prox-)ED/NIDS/D2	✓	$\bm{I}-c(\bm{I}-\bm{W})$	$c(\bm{I}-\bm{W})$	$1$
(Prox-)MG-ED	✓	$\nicefrac{{1}}{{2}}(\bm{I}+\bm{W}^{N})$	$\nicefrac{{1}}{{2}}(\bm{I}-\bm{W}^{N})$	$N$
(Prox-)ATC-GT	✓	$\bm{W}^{2}$	$(\bm{I}-\bm{W})^{2}$	$2$
MG-SONATA	✓	$(\bm{W}^{N})^{2}$	$(\bm{I}-\bm{W}^{N})^{2}$	$2N$
LED	-	$\bm{W}$	$\bm{I}-\bm{W}$	$p$ (periodic)
local-GT	-	$\bm{W}^{2}$	$(\bm{I}-\bm{W})^{2}$	$2p$ (periodic)

Table 2: The relation of FlexATC to existing ATC-based distributed algorithms for specific choices of

\bm{A}

and

\bm{B}

Algorithm	$\bm{B}$	$\mathcal{O}\left(\sigma_{m}(\bm{B})\right)$	$N$	# of Iter.: $p=1$	# of Iter.: $p\in\left[\sqrt{\frac{(1-\zeta_{c})}{\sigma_{m}(\bm{B})}},1\right]$	No Iter. Dec.	# of Comm.: $p=1$	# of Comm.: $p\in\left[\sqrt{\frac{(1-\zeta_{c})}{\sigma_{m}(\bm{B})}},1\right]$	Acc. Comm.
Algorithm	$\bm{B}$	$\mathcal{O}\left(\sigma_{m}(\bm{B})\right)$	$N$	literature	this paper	this paper	literature	this paper	this paper
NIDS/ED/D2	$c(\bm{I}-\bm{W})$	$1-\rho$	$1$	$\mathcal{O}\left(\frac{\kappa}{1-\rho}\log\nicefrac{{1}}{{\epsilon}}\right)$	$\mathcal{O}\left(\frac{\kappa}{1-\rho}\log\nicefrac{{1}}{{\epsilon}}\right)$	✓	$\mathcal{O}\left(\frac{\kappa}{1-\rho}\log\nicefrac{{1}}{{\epsilon}}\right)$	$\mathcal{O}\left(\sqrt{\frac{\kappa}{1-\rho}}\log\nicefrac{{1}}{{\epsilon}}\right)$ , $p=\frac{1}{\sqrt{\kappa(1-\rho)}}$	✓
MG-ED	$\nicefrac{{1}}{{2}}(\bm{I}-\bm{W}^{N})$	$1$	$\mathcal{O}\left(\frac{1}{\sqrt{1-\rho}}\right)$	$\mathcal{O}\left(\kappa\log\nicefrac{{1}}{{\epsilon}}\right)$	$\mathcal{O}\left(\kappa\log\nicefrac{{1}}{{\epsilon}}\right)$	✓	$\mathcal{O}\left(\frac{\kappa}{\sqrt{1-\rho}}\log\nicefrac{{1}}{{\epsilon}}\right)$	$\mathcal{O}\left(\sqrt{\frac{\kappa}{1-\rho}}\log\nicefrac{{1}}{{\epsilon}}\right)$ , $p=\frac{1}{\sqrt{\kappa}}$	✓
ATC-GT	$(\bm{I}-\bm{W})^{2}$	$(1-\rho)^{2}$	$\mathcal{O}(1)$	$\mathcal{O}\left(\frac{\kappa}{(1-\rho)^{2}}\log\nicefrac{{1}}{{\epsilon}}\right)$	$\mathcal{O}\left(\frac{\kappa}{(1-\rho)^{2}}\log\nicefrac{{1}}{{\epsilon}}\right)$	✓	$\mathcal{O}\left(\frac{\kappa}{(1-\rho)^{2}}\log\nicefrac{{1}}{{\epsilon}}\right)$	$\mathcal{O}\left(\frac{\sqrt{\kappa}}{1-\rho}\log\nicefrac{{1}}{{\epsilon}}\right)$ , $p=\frac{1}{\sqrt{\kappa(1-\rho)^{2}}}$	✓
MG-SONATA	$(\bm{I}-\bm{W}^{N})^{2}$	$1$	$\mathcal{O}\left(\frac{1}{\sqrt{1-\rho}}\right)$	$\mathcal{O}\left(\kappa\log\nicefrac{{1}}{{\epsilon}}\right)$	$\mathcal{O}\left(\kappa\log\nicefrac{{1}}{{\epsilon}}\right)$	✓	$\mathcal{O}\left(\frac{\kappa}{\sqrt{1-\rho}}\log\nicefrac{{1}}{{\epsilon}}\right)$	$\mathcal{O}\left(\sqrt{\frac{\kappa}{1-\rho}}\log\nicefrac{{1}}{{\epsilon}}\right)$ , $p=\frac{1}{\sqrt{\kappa}}$	✓

Table 3: Comparison with existing strongly convex convergence rates of SOTA ATC-based distributed algorithms. Iter. = Iteration, Comm. = Communication, Dec. = Deceleration, Acc. = Acceleration.

Panel of Figure 1 — Figure 1: The numerical results over ijcnn1 dataset for communication acceleration are shown, with the relative error $\|\bm{x}^{k}-\bm{x}^{\star}\|/\|\bm{x}^{\star}\|$ plotted against the number of iteration and communication rounds.

Distributed Optimization

Distributed optimization coordinates computation across multiple agents or machines while balancing convergence, communication, privacy, and reliability.

See all 92 papers

Adaptive Decentralized Composite Optimization via Three-Operator Splitting
Feb 19, 2026Xiaokai Chen, Ilya Kuruzov, Gesualdo ScutariDecentralized Optimization Nonsmooth Convex Optimization
Edwardson School of Industrial Engineering, Purdue University, West Lafayette, IN 47906 USA
Decentralized Stochastic Subgradient-type Methods with Communication Compression for Nonsmooth Nonconvex Optimization
Jul 2, 2026Siyuan Zhang, Nachuan Xiao, Xin LiuStochastic Optimization Nonconvex Optimization
A distributed semismooth Newton based augmented Lagrangian method for distributed optimization
Feb 27, 2026Qihao Ma, Chengjing Wang, Peipei Tang +2Distributed Optimization Augmented Lagrangian Method
School of Mathematics, Southwest Jiaotong University, No.999, Xian Road, West Park, High-tech Zone, Chengdu 611756, China · School of Computer and Computing Science, Hangzhou City University, Zhejiang Key Laboratory of Big Data Intelligent Computing, Hangzhou, 310015, China · Department of Control Science and Engineering, College of Electronics and Information Engineering, National Key Laboratory of Autonomous Intelligent Unmanned Systems, Tongji University, Shanghai 201804, China +1

Feb 19, 2026J/K move · Enter open · S save

Adaptive Decentralized Composite Optimization via Three-Operator Splitting

Xiaokai Chen, Ilya Kuruzov, Gesualdo Scutari

Edwardson School of Industrial Engineering, Purdue University, West Lafayette, IN 47906 USA

Decentralized Optimization Nonsmooth Convex Optimization

Open paper AskPDF arXiv

The paper studies decentralized optimization over networks, where agents minimize a sum of {\it locally} smooth (strongly) convex losses and plus a nonsmooth convex extended value term. We propose decentralized methods wherein agents {\it adaptively} adjust their stepsize via local backtracking procedures coupled with lightweight min-consensus protocols. Our design stems from a three-operator splitting factorization applied to an equivalent reformulation of the problem. The reformulation is endowed with a new BCV preconditioning metric (Bertsekas-O'Connor-Vandenberghe), which enables efficient decentralized implementation and local stepsize adjustments. We establish robust convergence guarantees. Under mere convexity, the proposed methods converge with a sublinear rate. Under strong convexity of the sum-function, and assuming the nonsmooth component is partly smooth, we further prove linear convergence. Numerical experiments corroborate the theory and highlight the effectiveness of the proposed adaptive stepsize strategy.

Abstract

Distributed Optimization

Explore similar work

Adaptive Decentralized Composite Optimization via Three-Operator Splitting

Decentralized Stochastic Subgradient-type Methods with Communication Compression for Nonsmooth Nonconvex Optimization

A distributed semismooth Newton based augmented Lagrangian method for distributed optimization