math.OCFeb 19, 2026

Adaptive Decentralized Composite Optimization via Three-Operator Splitting

Authors: Xiaokai Chen, Ilya Kuruzov, Gesualdo Scutari

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

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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.

Figures & tables

 Xk+1/2=WXk,Dk+1/2=W(∇F(Xk)+Sk+Dk);\mathbf{X}^{k+1/2}=W\mathbf{X}^{k},\quad\mathbf{D}^{k+1/2}=W(\nabla F(\mathbf{X}^{k})+\mathbf{S}^{k}+\mathbf{D}^{k}); 
Algorithm 1 Decentralized Adaptive Three Operator Splitting
Figure 2
 Xk+1/2=WXk,Dk+1/2=W(∇F(Xk)+Sk+Dk);\mathbf{X}^{k+1/2}=W\mathbf{X}^{k},\quad\mathbf{D}^{k+1/2}=W(\nabla F(\mathbf{X}^{k})+\mathbf{S}^{k}+\mathbf{D}^{k}); 
Algorithm 3 Decentralized Adaptive Three Operator Splitting with local min-consensus (local_DATOS)
Figure 1: Logistic regression with ℓ1\ell_{1} -regularization: 1m∑i=1mu(xi)−u(x∗){\frac{1}{m}\sum_{i=1}^{m}u(x_{i})-u(x^{*})} v.s. # iterations. Comparison of PG-EXTRA, SONATA, adaPDM, adaPDM2, global_DATOS and local_DATOS on Erdos-Renyi graphs with edge-probability p=0.1p=0.1 (left); p=0.5p=0.5 (middle); and p=0.9p=0.9 (right).
Figure 2: ML estimate of the covariance matrix: 1m∑i=1mu(xi)−u(x∗){\frac{1}{m}\sum_{i=1}^{m}u(x_{i})-u(x^{*})} v.s. # iterations. Comparison of PG-EXTRA, SONATA, adaPDM, adaPDM2, global_DATOS and local_DATOS on Erdos-Renyi graphs with edge-probability: p=0.1p=0.1 (left); p=0.5p=0.5 (middle); and p=0.9p=0.9 (right).
Figure 3: Linear regression with elastic net regularization: ∥Xk−X∗∥2{\|\mathbf{X}^{k}-\mathbf{X}^{*}\|^{2}} v.s. # iterations. Comparison of PG-EXTRA, SONATA, adaPDM, adaPDM2, global_DATOS and local_DATOS on Erdos-Renyi graphs with edge-probability: p=0.1p=0.1 (left); p=0.5p=0.5 (middle); and p=0.9p=0.9 (right).
More in this topic

Decentralized Optimization

Decentralized optimization develops methods for agents connected by networks to solve shared problems using local data and peer-to-peer communication.

See all 60 papers

Explore similar work

CardsList

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

    Jul 2, 2026Siyuan Zhang, Nachuan Xiao, Xin LiuStochastic OptimizationNonconvex Optimization

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

    Feb 18, 2026Luyao Guo, Xinli Shi, Wenying Xu +1Distributed OptimizationNonsmooth Convex Optimization

    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

  3. Near-Optimal Decentralized Stochastic Convex Optimization over Networks

    Jun 3, 2026Nitai Kluger, Amit Attia, Tomer KorenStochastic Optimization ConvergenceAccelerated Gradient Methods

    Blavatnik School of Computer Science, Tel Aviv University · Google Research Tel Aviv