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

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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=1p=1LU?Comm. Acc.?# of Comm.: p∈(0,1]p\in(0,1]LU?Comm. Acc.?
literature [ 30 , 1 ]this paperthis paperthis paper
(Prox-)NIDS/ED/D2O(κ1−ρlog⁡ϵ−1)\mathcal{O}\left(\frac{\kappa}{1-\rho}\log\epsilon^{-1}\right)✗✗O(κ1−ρlog⁡ϵ−1)→improvedp=1κ(1−ρ)O(κ1−ρlog⁡ϵ−1)\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-EDO(κ1−ρlog⁡ϵ−1)\mathcal{O}\left(\frac{\kappa}{\sqrt{1-\rho}}\log\epsilon^{-1}\right)✗✗O(κ1−ρlog⁡ϵ−1)→improvedp=1κO(κ1−ρlog⁡ϵ−1)\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-GTO(κ(1−ρ)2log⁡ϵ−1)\mathcal{O}\left(\frac{\kappa}{(1-\rho)^{2}}\log\epsilon^{-1}\right)✗✗O(κ(1−ρ)2log⁡ϵ−1)→improvedp=1κ(1−ρ)2O(κ1−ρlog⁡ϵ−1)\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-SONATAO(κ1−ρlog⁡ϵ−1)\mathcal{O}\left(\frac{\kappa}{\sqrt{1-\rho}}\log\epsilon^{-1}\right)✗✗O(κ1−ρlog⁡ϵ−1)→improvedp=1κO(κ1−ρlog⁡ϵ−1)\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.
Algorithmr≠0r\neq 0A\bm{A}B\bm{B}# of Comm.
(Prox-)ED/NIDS/D2✓I−c(I−W)\bm{I}-c(\bm{I}-\bm{W})c(I−W)c(\bm{I}-\bm{W})11
(Prox-)MG-ED✓\nicefrac12(I+WN)\nicefrac{{1}}{{2}}(\bm{I}+\bm{W}^{N})\nicefrac12(I−WN)\nicefrac{{1}}{{2}}(\bm{I}-\bm{W}^{N})NN
(Prox-)ATC-GT✓W2\bm{W}^{2}(I−W)2(\bm{I}-\bm{W})^{2}22
MG-SONATA✓(WN)2(\bm{W}^{N})^{2}(I−WN)2(\bm{I}-\bm{W}^{N})^{2}2N2N
LED-W\bm{W}I−W\bm{I}-\bm{W}pp (periodic)
local-GT-W2\bm{W}^{2}(I−W)2(\bm{I}-\bm{W})^{2}2p2p (periodic)
Table 2: The relation of FlexATC to existing ATC-based distributed algorithms for specific choices of A\bm{A} and B\bm{B} .
AlgorithmB\bm{B}O(σm(B))\mathcal{O}\left(\sigma_{m}(\bm{B})\right)NN# of Iter.: p=1p=1# of Iter.: p∈[(1−ζc)σm(B),1]p\in\left[\sqrt{\frac{(1-\zeta_{c})}{\sigma_{m}(\bm{B})}},1\right]No Iter. Dec.# of Comm.: p=1p=1# of Comm.: p∈[(1−ζc)σm(B),1]p\in\left[\sqrt{\frac{(1-\zeta_{c})}{\sigma_{m}(\bm{B})}},1\right]Acc. Comm.
literaturethis paperthis paperliteraturethis paperthis paper
NIDS/ED/D2c(I−W)c(\bm{I}-\bm{W})1−ρ1-\rho11O(κ1−ρlog⁡\nicefrac1ϵ)\mathcal{O}\left(\frac{\kappa}{1-\rho}\log\nicefrac{{1}}{{\epsilon}}\right)O(κ1−ρlog⁡\nicefrac1ϵ)\mathcal{O}\left(\frac{\kappa}{1-\rho}\log\nicefrac{{1}}{{\epsilon}}\right)✓O(κ1−ρlog⁡\nicefrac1ϵ)\mathcal{O}\left(\frac{\kappa}{1-\rho}\log\nicefrac{{1}}{{\epsilon}}\right)O(κ1−ρlog⁡\nicefrac1ϵ)\mathcal{O}\left(\sqrt{\frac{\kappa}{1-\rho}}\log\nicefrac{{1}}{{\epsilon}}\right) , p=1κ(1−ρ)p=\frac{1}{\sqrt{\kappa(1-\rho)}}✓
MG-ED\nicefrac12(I−WN)\nicefrac{{1}}{{2}}(\bm{I}-\bm{W}^{N})11O(11−ρ)\mathcal{O}\left(\frac{1}{\sqrt{1-\rho}}\right)O(κlog⁡\nicefrac1ϵ)\mathcal{O}\left(\kappa\log\nicefrac{{1}}{{\epsilon}}\right)O(κlog⁡\nicefrac1ϵ)\mathcal{O}\left(\kappa\log\nicefrac{{1}}{{\epsilon}}\right)✓O(κ1−ρlog⁡\nicefrac1ϵ)\mathcal{O}\left(\frac{\kappa}{\sqrt{1-\rho}}\log\nicefrac{{1}}{{\epsilon}}\right)O(κ1−ρlog⁡\nicefrac1ϵ)\mathcal{O}\left(\sqrt{\frac{\kappa}{1-\rho}}\log\nicefrac{{1}}{{\epsilon}}\right) , p=1κp=\frac{1}{\sqrt{\kappa}}✓
ATC-GT(I−W)2(\bm{I}-\bm{W})^{2}(1−ρ)2(1-\rho)^{2}O(1)\mathcal{O}(1)O(κ(1−ρ)2log⁡\nicefrac1ϵ)\mathcal{O}\left(\frac{\kappa}{(1-\rho)^{2}}\log\nicefrac{{1}}{{\epsilon}}\right)O(κ(1−ρ)2log⁡\nicefrac1ϵ)\mathcal{O}\left(\frac{\kappa}{(1-\rho)^{2}}\log\nicefrac{{1}}{{\epsilon}}\right)✓O(κ(1−ρ)2log⁡\nicefrac1ϵ)\mathcal{O}\left(\frac{\kappa}{(1-\rho)^{2}}\log\nicefrac{{1}}{{\epsilon}}\right)O(κ1−ρlog⁡\nicefrac1ϵ)\mathcal{O}\left(\frac{\sqrt{\kappa}}{1-\rho}\log\nicefrac{{1}}{{\epsilon}}\right) , p=1κ(1−ρ)2p=\frac{1}{\sqrt{\kappa(1-\rho)^{2}}}✓
MG-SONATA(I−WN)2(\bm{I}-\bm{W}^{N})^{2}11O(11−ρ)\mathcal{O}\left(\frac{1}{\sqrt{1-\rho}}\right)O(κlog⁡\nicefrac1ϵ)\mathcal{O}\left(\kappa\log\nicefrac{{1}}{{\epsilon}}\right)O(κlog⁡\nicefrac1ϵ)\mathcal{O}\left(\kappa\log\nicefrac{{1}}{{\epsilon}}\right)✓O(κ1−ρlog⁡\nicefrac1ϵ)\mathcal{O}\left(\frac{\kappa}{\sqrt{1-\rho}}\log\nicefrac{{1}}{{\epsilon}}\right)O(κ1−ρlog⁡\nicefrac1ϵ)\mathcal{O}\left(\sqrt{\frac{\kappa}{1-\rho}}\log\nicefrac{{1}}{{\epsilon}}\right) , p=1κ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.
Figure 1: The numerical results over ijcnn1 dataset for communication acceleration are shown, with the relative error ∥xk−x⋆∥/∥x⋆∥\|\bm{x}^{k}-\bm{x}^{\star}\|/\|\bm{x}^{\star}\| plotted against the number of iteration and communication rounds.
More in this topic

Distributed Optimization

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

See all 92 papers

Explore similar work

CardsList
Feb 19, 2026

Adaptive Decentralized Composite Optimization via Three-Operator Splitting

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.

Xiaokai Chen, Ilya Kuruzov, Gesualdo Scutari

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

Decentralized OptimizationNonsmooth Convex Optimization
AskPDF
Jul 2, 2026

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

In this paper, we consider the nonsmooth nonconvex decentralized optimization problem, where inter-agent communication is compressed. We propose a general framework that unifies various decentralized stochastic subgradient-type methods with unbiased compression and contractive compression with error compensation. By relating the consensus-error iterates and the averaged iterates to the trajectories of continuous-time differential inclusions, we establish global convergence for all methods encompassed by our framework when the objective functions are nonsmooth and lack Clarke regularity. Based on our framework, we further develop several compression-based methods, including decentralized stochastic subgradient methods utilizing sign-based regularization and gradient-tracking momentum. Preliminary numerical experiments empirically support our theoretical results and highlight the communication-accuracy trade-off of the newly developed methods.

Siyuan Zhang, Nachuan Xiao, Xin Liu

Stochastic OptimizationNonconvex OptimizationStochastic Optimization ConvergenceNonsmooth Convex OptimizationDecentralized Optimization
AskPDF
Feb 27, 2026

A distributed semismooth Newton based augmented Lagrangian method for distributed optimization

This paper proposes a novel distributed semismooth Newton based augmented Lagrangian method for solving a class of optimization problems over networks, where the global objective is defined as the sum of locally held cost functions, and communication is restricted to neighboring agents. Specifically, we employ the augmented Lagrangian method to solve an equivalently reformulated constrained version of the original problem. Each resulting subproblem is solved inexactly via a distributed semismooth Newton method. By fully leveraging the structure of the generalized Hessian, a distributed accelerated proximal gradient method is proposed to compute the Newton direction efficiently, eliminating the need to communicate with full Hessian matrices. Theoretical results are also obtained to guarantee the convergence of the proposed algorithm. Numerical experiments demonstrate the efficiency and superiority of our algorithm compared to state-of-the-art distributed algorithms.

Qihao Ma, Chengjing Wang, Peipei Tang +2

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

Distributed OptimizationAugmented Lagrangian MethodConstrained Optimization
AskPDF