From Mixing to Tearing: Graph Decomposition in Decentralized Optimization via Message Passing

Kuangyu Ding; Gesualdo Scutari

math.OCOct 2, 2026

From Mixing to Tearing: Graph Decomposition in Decentralized Optimization via Message Passing

Authors: Kuangyu Ding, Gesualdo Scutari

Organizations: Edwardson School of Industrial Engineering, Purdue University, West Lafayette, IN. · Edwardson School of Industrial Engineering & Elmore Family School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN.

Abstract

We study decentralized minimization of sums of smooth strongly convex functions, one per agent, with communication restricted to neighbors in a graph. Existing decentralized algorithms typically emulate a {\it centralized} method; {\it the network serves only to exchange information}, from which agents approximate the global quantities that the method needs. This paper breaks with this paradigm. We introduce a {\it graph decomposition framework} that uses the network to design the method, not merely execute it. It jointly determines how agreement is imposed, which variables are optimized jointly (blocks), and which connected subgraphs host the agents solving each block. The convergence analysis quantifies the trade-offs among these choices. GATE (Graph-Tearing message passing) instantiates the framework by assigning one dual variable per edge and partitioning the edges into trees. Agents interleave edge updates with local message passing recursions that summarize optimization within each tree (block). Its surrogate variant, GATE-S, uses tractable local models and compact messages to reduce computation and communication. We establish linear convergence and show that the topology-aware design acts as a preconditioner: the rate depends {\it jointly} on topology and function geometry through the coupling between subproblems defined on the selected subgraphs, whereas consensus-based optimization methods pay the worst case of each separately, the centralized condition number times the inverse spectral gap. On tree-dominant graphs, convergence is provably faster: the rate scales with the tree {\it diameter}, linearly in the number of agents on rings and barbells against quadratically for non-accelerated consensus-optimization methods. Experiments support the predicted scaling and savings in iterations and communication.

Figures & tables

Panel of Figure 1 — Figure 1: Three faithful representations (see ( 1 )) of the same path graph $1-2-3$ induce distinct factor graphs: the generic $\mathsf{A}_{\rm ex}$ couples nonadjacent factors, the Laplacian $\mathsf{L}$ produces a cyclic factor graph, and the incidence matrix $\mathsf{B}$ reproduces the node-edge incidence structure.

Panel of Figure 2 — Figure 2: Example 1 revisited. Top: block factor graphs. Bottom: carrier subgraphs $\mathcal{G}_{r}$ , with the entries of $M_{r}$ on the edges.

Figure 3: Messages on the same tree block: (a) fixing

Y_{e}=y_{e}

separates the minimization into two subgraphs; (b) eliminating

Y_{h_{1}},Y_{h_{2}}

combines the two incoming messages with

f_{i}^{*}

, while the dashed exterior-edge coordinates remain fixed at

Y^{\star}_{\overline{\mathcal{E}}_{r}}


$\displaystyle\vskip-11.38092pt\hat{Y}_{e}^{\nu+1}$	$\displaystyle\in\mathop{\rm argmin}_{y_{e}\in\mathbb{R}^{1\times d}}\left\{\sum_{j\in\mathcal{I}_{e}}\mu_{j\to e}^{\nu}(y_{e})\right\},$	(17a)
$\displaystyle Y_{e}^{\nu+1}$	$\displaystyle=Y_{e}^{\nu}+\tau_{r}^{\nu}\bigl(\hat{Y}_{e}^{\nu+1}-Y_{e}^{\nu}\bigr).$	(17b)

Algorithm 1 GATE: Graph-Tearing message passing


$\displaystyle\hat{Y}_{e}^{\nu+1}$	$\displaystyle\in\mathop{\rm argmin}_{y_{e}\in\mathbb{R}^{1\times d}}\left\{\sum_{j\in\mathcal{I}_{e}}\widetilde{\mu}_{j\to e}^{\nu}(y_{e})\right\},$	(51a)
$\displaystyle Y_{e}^{\nu+1}$	$\displaystyle=Y_{e}^{\nu}+\tau_{r}^{\nu}\bigl(\hat{Y}_{e}^{\nu+1}-Y_{e}^{\nu}\bigr).$	(51b)

Algorithm 2 GATE-S: Graph-Tearing message passing with surrogates

Figure 4: Network-size scaling for quadratic problems on a ring. Panel (a) reports the iteration counts versus the number of agents

m

, while panel (b) presents the same data on log–log axes to make their dependence on

m

more apparent. Panel (c) shows the graph and edge partition. The stopping criterion is

\|X^{\nu}-\mathbf{1}(x^{\star})^{\top}\|<10^{-4}

Figure 5: Network-size scaling for logistic-regression problems on a ring. Panel (a) reports the iteration counts versus the number of agents

m

, while panel (b) presents the same data on log–log axes to make their dependence on

m

more apparent. Panel (c) shows the graph and edge partition. The stopping criterion is

\|X^{\nu}-\mathbf{1}(x^{\star})^{\top}\|<10^{-4}

Figure 6: Network-size and diameter scaling for quadratic problems on a non-ring graph family. Panel (a) reports the iteration counts versus the number of agents

m

for graphs with

D=\Theta(\sqrt{m})

. Panel (b) reports the iteration counts versus

D

at fixed

m=406

. Panel (c) shows the graph and edge partition. The stopping criterion is

\|X^{\nu}-\mathbf{1}(x^{\star})^{\top}\|<10^{-4}

Panel of Figure 7 — Figure 7: Effect of the partition on GATE for quadratic problems on a ring ( $d=10$ ). Panel (a) reports the iteration counts versus the number of agents $m$ for P1, P2, and P3. Panels (b)–(d) show the corresponding partitions on a representative ring. The stopping criterion is $\|X^{\nu}-\mathbf{1}(x^{\star})^{\top}\|<10^{-4}$ .

Figure 8: Performance comparison for quadratic problems on two barbell graphs. Panels (a)–(c) use

L=10

, while panels (d)–(f) use

L=100

. Panels (a) and (d) report the primal error versus iteration count, while panels (b) and (e) report it versus cumulative communication. Panels (c) and (f) show the corresponding graphs and partitions; red edges form the dominant tree cluster and blue edges form singleton-edge clusters. The stopping criterion is

\|X^{\nu}-\mathbf{1}(x^{\star})^{\top}\|\leq 10^{-6}

Figure 9: Logistic-regression comparison on two barbell graphs. Panels (a)–(c) use

L=10

, while panels (d)–(f) use

L=100

. Panels (a) and (d) report the error versus iteration count, while panels (b) and (e) report it versus cumulative communication; GATE-S2 (exact Hessian) is omitted from the communication panels. Panels (c) and (f) show the corresponding graphs and partitions; red edges form the dominant tree cluster and blue edges form singleton-edge clusters. The stopping criterion is

\|X^{\nu}-\mathbf{1}(x^{\star})^{\top}\|\leq 10^{-6}

Figure 10: Performance comparison for quadratic and logistic-regression problems on a multi-cycle network. Panels (a)–(c) show the quadratic results with

d=200

, while panels (d)–(f) show the logistic-regression (LR) results with

d=50

. Panels (a) and (d) report the error versus iteration count, while panels (b) and (e) report it versus cumulative communication; GATE-S2 (exact Hessian) is omitted from panel (e). Panels (c) and (f) show the common graph and partition; red edges form the message-passing cluster and the blue edge forms the singleton-edge cluster. The stopping criterion is

\|X^{\nu}-\mathbf{1}(x^{\star})^{\top}\|\leq 10^{-6}

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

Jun 3, 2026

Near-Optimal Decentralized Stochastic Convex Optimization over Networks

We study decentralized stochastic smooth convex optimization, where

M

workers minimize an average objective using local stochastic gradients and neighbor-only communication over a fixed gossip network. A central question in this setting is to determine the largest number of workers that can be used under a total budget of

N

gradient samples while still preserving the centralized

O(1/\sqrt N)

statistical rate. We introduce an accelerated decentralized method that preserves this rate for up to

\smash{M\lesssim \sqrtρ\,N^{3/4}}

workers, where

ρ

is the spectral gap of the gossip network, improving the best prior maximal scaling of

\smash{M\lesssim ρ\sqrt N}

. The method is based on a one-step-delayed stochastic acceleration scheme that enables workers to interleave minibatching with accelerated gossip while controlling residual disagreement, and its guarantee depends only logarithmically on the optimum-local heterogeneity. We also establish a matching lower bound for linear-span decentralized first-order methods, showing that the method is optimal up to logarithmic factors.

Nitai Kluger, Amit Attia, Tomer Koren

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

Stochastic Optimization Convergence Accelerated Gradient Methods Decentralized Optimization

Ask PDF

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 Optimization Nonsmooth Convex Optimization

Ask PDF

Jun 5, 2026

Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization

Decentralized stochastic optimization is a fundamental paradigm for large-scale learning over networks, where agents communicate only with their neighbors and no central coordinator is required. For strongly convex problems, communication efficiency is mainly determined by the condition number

κ=L/μ

and the network spectral gap

1-β

. Although deterministic decentralized methods can simultaneously achieve accelerated

\sqrtκ

and

1/\sqrt{1-β}

dependences, no existing stochastic method attains both improvements at once. In this paper, we propose Multi-Gossip Accelerated DSGD (MG-ADSGD), a decentralized stochastic algorithm that combines Nesterov-type primal--dual extrapolation with multi-round fast gossip averaging. The key idea is to couple the gossip depth with the mini-batch size so that additional communication rounds simultaneously improve consensus accuracy and reduce gradient variance. We show that MG-ADSGD achieves the communication complexity

\widetilde{\mathcal O}\!\left( \frac{σ^2}{μnε}\log\frac{1}ε + \sqrt{\fracκ{1-β}}\log\frac{1}ε \right),

where

ε

denotes the target accuracy,

n

is the number of nodes, and

σ^2

is the gradient variance. To the best of our knowledge, this bound yields the best currently available communication complexity for decentralized stochastic strongly convex optimization, up to logarithmic factors that are independent of

ε

Ming Sun, Kun Yuan

Center for Machine Learning Research Peking University

Gradient Descent Accelerated Gradient Methods Decentralized Optimization Stochastic Gradient Descent

Ask PDF

Abstract

Decentralized Optimization

Explore similar work

Near-Optimal Decentralized Stochastic Convex Optimization over Networks

Adaptive Decentralized Composite Optimization via Three-Operator Splitting

Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization