PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Kuangyu Ding, Gesualdo Scutari

arXiv:2610.03709v1math.OCcs.LG

TL;DR

Decentralized optimization methods commonly use network structure for communication while prescribing the local updates, leaving open how to jointly design the optimization decomposition and its cooperative execution. This paper develops a graph-decomposition framework and instantiates it as GATE, with edge variables and tree blocks, alongside the surrogate variant GATE-S. The authors establish linear convergence with rates tied to problem regularity, topology, and partition, including O(D) scaling for tree-dominant graphs.

  • Problem

    Existing decentralized methods use the network to mix or route information for prescribed local updates, rather than jointly designing optimization subproblems and their cooperative computation and communication.

    Source: §1 · p. 2

  • Method

    The framework jointly chooses the agreement representation, dual-variable blocks, and connected carriers; GATE uses edge variables and tree blocks solved through recursive messages, while GATE-S uses surrogate models and lightweight message parametrizations.

    Source: §1.1 · pp. 3–4, §5 · p. 24, §7 · p. 39

  • Results

    GATE converges linearly with a rate depending on function regularity, network topology, and partition; for tree-dominant graph families, (1 − ρ)^−1 = O(D).

    Source: §1.1 · p. 5, §7 · p. 39

  • Takeaways & Limitations

    The convergence analysis makes graph decomposition a design choice whose effects on convergence can be quantified, including for tree-dominant graph families.

    Source: §1.1 · p. 5, §4.4 · p. 23

    GATE-S surrogate regularity requires the chosen quadratic metric to majorize the curvature of the local conjugate term.

    Source: §5.2.1 · p. 27

Abstract

from arXiv · show

We study the minimization of sums of smooth strongly convex functions over undirected graphs, with each function held by one agent and communication restricted to neighbors in the graph. Existing decentralized methods, whether based on gossip or on routing over spanning trees, typically use the network to mix or aggregate information to enable {\it prescribed} local optimization updates. What this communication-centered viewpoint lacks is a general framework that uses graph structure to {\it jointly} design the optimization subproblems and the cooperative computation and communication through which agents solve them cooperatively. We develop such a framework from first principles, jointly designing the linear representation of agreement constraints, the blocks of the resulting dual variables (jointly optimized), and connected cluster of agents that cooperatively solve each block subproblem over the assigned subgraph. GATE (Graph-Tearing message passing) is a first instance of this framework: one variable per edge and tree blocks. At each iteration, agents update their assigned edge variables by minimizing the sum of the two endpoint cost-to-go messages and relaxing the result. The messages are updated through local minimizations following the tree recursion. To reduce per-iteration computational and communication costs, we develop GATE-S, a surrogate variant using tractable local models and lightweight message parametrizations. We establish linear convergence with a rate explicit in the interplay among function regularity, network topology, and the chosen partition, revealing the effects of graph decomposition. Numerical experiments are conducted to validate the theoretical results and evaluate the efficiency of our algorithms.

1 Introduction

The introduction argues for treating graph structure as part of decentralized algorithm design, jointly choosing the dual representation, variable blocks, and connected regions that execute them. It presents GATE on tree blocks and reports decomposition-dependent linear convergence, including improved scaling on rings relative to nonaccelerated consensus methods.

1 Introduction

  • The introduction identifies a gap in consensus-centered methods: topology typically serves as a communication medium, while uniform updates can make mixing the convergence bottleneck measured by the global spectral gap.It contrasts this with opening a ring into a path that can be optimized jointly in O(m) steps.Source: §1 · p. 3
  • The proposed framework jointly chooses a faithful constraint representation, blocks of dual coordinates, and connected carriers that host each block subproblem.The representation creates variables and dependencies, blocks determine what is optimized jointly, and carriers determine where it is executed.Source: §1.1 · pp. 3–4
  • GATE assigns one dual variable to each physical edge and partitions edges into tree blocks whose endpoint agents jointly optimize their variables.For an edge, endpoint cost-to-go messages are computed recursively on the two subtrees formed by removing that edge; the edge variable minimizes their sum, with relaxed updates.Source: §1.1 · p. 4
  • GATE’s linear convergence rate depends explicitly on function regularity, local network structure, and the chosen decomposition; on rings, the iteration scale is O(m), versus O(m^2) for nonaccelerated consensus methods.For tree-dominant graphs of diameter D, the rate discussion gives (1 − ρ)^−1 = O(D).Source: §1.1 · p. 5
  • The paper develops GATE-S with tractable local surrogate models and lightweight message parametrizations to reduce per-iteration computational and communication costs.The introduction says it provides practical surrogate choices and an analogous linear convergence rate and scalability analysis; experiments evaluate iteration and communication efficiency against consensus-based methods.Source: §1.1 · p. 5

2 Graph Decomposition Framework

The framework treats consensus optimization as a joint graph-design problem: choose the agreement representation, jointly optimized dual blocks, and connected carriers that host each block computation.

2.1 Problem and graph setting

  • The problem assigns each node a smooth strongly convex cost and assumes an undirected, connected, simple communication graph.Source: §2.1 · p. 6

2.2.1 Representations and their factor graphs

  • Faithful representations enforce the same consensus constraint but create different dual coordinates and dependencies, producing distinct factor graphs and potential algorithms.For example, the incidence matrix mirrors node-edge incidence, while other choices can couple nonadjacent agents.Source: §2.2.1 · pp. 6–7

2.2.2 Block covers and conditional responses

  • A block cover groups dual coordinates for joint minimization, but touched agents may be disconnected, so computing a response can require relay agents.Source: §2.2.2 · pp. 7–8

2.2.3 Carriers and realizability

  • Each block receives a connected carrier containing all agents whose conjugates enter its subproblem; realizability characterizes when these couplings can be represented over a connected physical subgraph.Carrier-only agents can relay information without contributing a term to the block subproblem.Source: §2.2.3 · pp. 8–9

2.2 Graph decomposition

  • A graph decomposition jointly selects a faithful representation, dual-coordinate blocks, and connected carriers, which determine variables, joint updates, and where computation occurs.Source: §2.2.3 · p. 9

3 Graph Tearing Along Edges: Message Passing on Tree Blocks

GATE uses edge-indexed dual variables grouped into tree blocks, then computes block responses through local message passing. Its node-owned implementation updates edges and messages using only neighbor communication.

3 Graph Tearing Along Edges: Message Passing on Tree Blocks

  • GATE uses one dual coordinate per physical edge and groups edges into connected blocks, with each carrier equal to the block’s agents.Finer partitions make smaller block subproblems but may require more rounds to resolve coupling between blocks.Source: §3 · p. 11

3.1 Tree-block responses and message equations

  • Tree blocks make each conditional response unique; minimizing over a spanning tree’s edge variables preserves the block’s optimal value.Source: §3.1 · p. 12
  • Fixing an edge variable splits a tree block into independent subproblems; endpoint cost-to-go messages combine to determine its optimal value, computed recursively from the leaves inward.Source: §3.1 · pp. 12–13

3.2 The node-owned GATE algorithm

  • In node-owned GATE, agents relax updates for assigned edges using both endpoint messages, then locally recompute messages and communicate only with neighbors.Source: §3.2 · p. 15

4 Convergence Analysis

The analysis establishes linear convergence for GATE by relating its tree-recursive updates to delayed block-Jacobi optimization and bounding progress across the chosen partition. Its rate depends on function regularity, network topology, and partition structure, with sharper scaling possible for favorable graph-partition regimes.

4.1 Image variables and block error bound

  • On loopy graphs, the analysis uses image variables because the edge-variable dual objective is constant along the incidence map's kernel and is not strongly convex there.The block error bound controls the full gap by the aggregate exact block gaps; for a single-block tree partition, its constant is 1.Source: §4.1 · pp. 16–17

4.2 Step 1: Equivalence to a delayed block-Jacobi scheme

  • Expanding the tree-recursive messages makes GATE's edge updates equivalent to delayed block-Jacobi updates once the iteration index reaches the maximum tree-block diameter.The equivalence follows by recursively substituting local node factors and incoming messages while keeping exterior edge variables at delayed iterates.Source: §4.2 · p. 17, §4.1 · p. 17

4.3 Step 2: Convergence of the delayed block-Jacobi scheme

  • GATE converges linearly under Assumptions 1, 3, and 4, with its rate depending explicitly on the block error bound, block overlap, delay diameter, and mismatch coefficient.The rate also reflects function regularity, network topology, and the chosen partition.Source: §4.3 · p. 22, §4.4 · p. 23
  • The stepsize restriction reflects active-node overlap, delay through block diameter, and delayed-update mismatch; with a tree communication graph and one block, message passing terminates in finitely many rounds.For that single-block tree case, the algorithm reduces to ordinary min-sum message passing.Source: §4.3 · pp. 18, 22

4.4 Rate discussions

  • For tree-dominant graphs, assigning the dominant tree to one block and remaining edges to singleton blocks yields a rate bound with (1 − ρ)^−1 = O(diam(Tm)).For the ring and barbell examples with tree diameter Θ(m), the bound is O(m); equal-length ring partitions instead yield O(m^3/2), while the long-path partition gives O(m).Source: §4.4 · pp. 23–24

5 Surrogate enhancement

This section presents GATE-S, using tractable local surrogates and lightweight quadratic messages to reduce computation and communication while retaining linear convergence under stated conditions. It examines when surrogate choices preserve tree-partition scaling or recover consensus spectral-gap scaling on general graphs.

5 Surrogate enhancement

  • GATE-S replaces exact local minimizations with tractable surrogates, reducing per-iteration computation and communication while inducing lightweight message parametrizations.The surrogate terms replace exact local terms in both edge-variable and message updates; choosing the exact local conjugate recovers Algorithm 1.Source: §5 · p. 24

5.1 Surrogate regularity conditions

  • Surrogate convergence assumes differentiable local models with strong convexity and smoothness, and measures their rate price through relative block progress.When surrogate progress is at least an η fraction of exact progress, the surrogate block error-bound constant is at most κP/η; bounded η preserves network-size scaling up to a constant.Source: §5.1 · pp. 25–26

5.2 Surrogate examples

  • Two practical surrogate choices satisfy the stated conditions: a fixed-metric first-order model and a center-dependent second-order model.The quadratic metric must majorize the curvature of the local conjugate on the relevant region for majorization to hold.Source: §5.2 · p. 26, §5.2.1 · p. 27

5.2.1 Regularity and block error bound comparison

  • For fixed metrics, the surrogate and exact block error bounds retain the same network scaling when local curvature ratios are graph- and partition-independent.When the surrogate Hessian matches the conjugate Hessian well, degradation is small; in the scalar case, the bound retains network scaling up to a local condition number.Source: §5.2.1 · p. 27

5.2.2 Quadratic message implementation

  • Quadratic surrogates yield quadratic messages, while slice-wise Hessian communication avoids repeatedly sending dense, time-varying matrices.Fixed-metric Hessians stabilize after finitely many sweeps, and scalar metrics avoid matrix communication; slice-wise updates send one Hessian slice per round and caches match stabilized Hessians within a bounded number of rounds under the stated usage condition.Source: §5.2.2 · p. 28

5.3 Convergence analysis

  • Under Assumptions 1, 3, 5, and 6 with p > 1, Algorithm 2 converges linearly, with its rate reflecting block progress, active-set overlap, delays, and surrogate mismatch.The analysis bounds surrogate mismatch through perturbations in boundary values and surrogate centers; less exact block progress can increase the rate constant relative to GATE.Source: §5.3 · pp. 30–31

5.4 Comparison with consensus-based methods

  • On ring and barbell graphs, exact GATE has O(m) rate scaling versus O(m^2) for consensus baselines, while sufficiently accurate surrogates can accelerate tree-dominant families.The comparison names DGD, EXTRA, and SONATA as consensus baselines; a proximal-linear surrogate can recover their spectral-gap scaling on general graphs.Source: §5.4 · pp. 31–32
  • If surrogate block progress is at least an η fraction of exact progress for network-independent η, then κP ≤ eκP ≤ κP/η.A quadratic surrogate satisfying the Hessian sandwich inequality (45) gives eκP ≤ ρmaxκP with network-independent ρmax.Source: §5.4 · p. 32
  • For tree-dominant families and partitions, eA=O(m), matching the exact method’s O(m) scaling for the ring and barbell examples.The stated ring and barbell scaling uses eD=diam(Tm)−1=Θ(m).Source: §5.4 · p. 32
  • On general graphs, a direct proximal-linear surrogate recovers O(1/λ_min(BB^T)) consensus spectral-gap scaling when L and the coefficients c_i,e+c_j,e are network-size bounded.This surrogate is outside the structured subclass (37), and the resulting rate matches classical consensus-based methods.Source: §5.4 · p. 32

6 Numerical experiments

Experiments on quadratic and logistic-regression problems across ring, non-ring, barbell, and multi-cycle graphs assess scaling, partition effects, and performance. The results report iteration and communication advantages for GATE variants over consensus baselines in several settings.

6.1 Scaling verification and partition effects

  • For quadratic ring problems, GATE variants scale linearly in iteration count, while consensus baselines scale quadratically as network size grows.GATE and GATE-S1 are faster than EXTRA and SONATA, with the gap widening as m grows.Source: Figure 4 · p. 33, §6.1 · p. 33
  • For logistic-regression ring problems, GATE surrogates scale near-linearly in iteration count, while consensus baselines approach quadratic scaling over the upper range.GATE-S1 and GATE-S2 remain faster than EXTRA and SONATA, with the gap widening as m grows.Source: Figure 5 · p. 34, §6.1 · p. 34
  • For non-ring quadratic graphs with D = Θ(√m), iteration counts exhibit m^1/2 and m^3/4 scalings for GATE and GATE-S1, respectively.The reported scalings are described as further confirming the theoretical scaling.Source: §6.1 · p. 34, Figure 6 · p. 35
  • On quadratic ring problems, partitions P1 and P2 substantially outperform P3, while P1 is modestly faster than P2.The reported ordering is consistent with the sharper O(m) rate for the long-path partition.Source: §6.1 · p. 34, Figure 7 · p. 35

6.2 Performance comparison

  • 31 and 114 iterations: exact GATE reaches the target on barbell graphs with L = 10 and L = 100, respectively, and has the lowest cumulative communication.CTA and ATC do not reach 10^-6 within 10^5 iterations.Source: Figure 8 · p. 36, §6.2 · p. 36
  • On barbell logistic-regression problems, GATE-S2 (cache Hessian) uses about one third as much communication as either GATE-S1 or EXTRA for L = 100.The cache variant is second only to GATE-S2 (exact Hessian) in iteration count and requires the least communication among other methods that reach the target.Source: Figure 9 · p. 37, §6.2 · p. 37
  • On the multi-cycle network, GATE variants outperform consensus baselines in iteration count and communication, with the diagonal GATE-S1 variant faster than all consensus baselines on both problems.The cache variant requires the least communication among displayed methods for both problems; the scalar GATE-S1 variant is less competitive on logistic regression.Source: Figure 10 · p. 38, §6.2 · p. 38

7 Conclusion

The paper presents a graph-decomposition framework and GATE, with GATE-S as a surrogate variant. It establishes linear convergence guarantees and reports experimental improvements over consensus-based baselines.

7 Conclusion

  • The framework jointly designs the representation, block cover, and carriers for decentralized optimization.GATE specializes it to the incidence representation and tree-structured edge blocks, using a single-loop decentralized message-passing algorithm.Source: §7 · p. 39
  • For strongly convex and smooth local objectives, GATE has linear convergence rates explicitly dependent on network topology and the chosen partition.For tree-dominant graph families, (1 − ρ)^−1 = O(D); GATE-S uses tractable local models and lightweight message parametrizations and has analogous guarantees.Source: §7 · p. 39
  • Experiments on quadratic and logistic-regression problems corroborate the theoretical scaling and demonstrate improved iteration and communication efficiency over consensus-based baselines.The paper identifies extensions to non-strongly convex objectives and stochastic settings as future directions.Source: §7 · p. 39

A Proofs for Section 4

These proofs establish the message and graph-structure identities underlying Section 4 and derive error and convergence bounds for specific graph partitions, relating them to subtree sensitivity, block size, and ring structure. They also transfer a block-error bound to the transformed objective using a quadratic reference, smoothness, and strong convexity.

A.1 Proof of Proposition 5

  • The Proposition 5 proof establishes subtree message identities by induction and applies them at the root to sum the block messages.The argument assumes the iteration index is at least the maximum tree-block diameter, so the expanded messages have no initial-message terms.Source: §A.1 · pp. 39–40

A.2 Proof of Lemma 3

  • For fixed boundary data, the block minimization yields a common primal variable determined by the aggregate boundary vector and a unique graph-compliant solution for the edge variables.The uniqueness follows from the tree incidence system; each edge variable is determined by summing the constraint residuals over either component formed by removing that edge.Source: §A.2 · pp. 40–41

A.3 Proof of Lemma 4

  • Lemma 4’s proof combines rooted-tree counting bounds and boundary-value sensitivity estimates to control accumulated edge and image-variable increments.The estimates are summed over rooted depth shells and delay windows to obtain the stated bound (31).Source: §A.3 · pp. 41, 42, 44

A.4 Proof of Proposition 6

  • For partition P = {E0} ∪ {{h} : h ∈ E0}, since q is fixed and α∂/α∂ = O(1), the block error bound proves κP = O(1).Source: §A.4 · p. 45

A.5 Proof of Proposition 7

  • For ring path blocks, the proof bounds the block error constant using the block diameter D and the number of blocks p, with the displayed bounds depending on sin²(π/p).The upper-bound argument uses a disjoint partition of ring nodes into sets of size D+1; the lower-bound construction assigns a common vector to each set.Source: §A.5 · pp. 46–47

A Proofs for Section 4

  • The proof defines bG(W) = G(WR^1/2) and the block gap ∆r(W) relative to minimization over W + Ur.It invokes Hessian bounds for bG.Source: §A.5 · p. 47
  • For the quadratic reference G0(V) = 1/2 ∥V∥², minimizing over V + Ur gives V − PrV.The resulting quadratic gap is 1/2 ∥PrV∥².Source: §A.5 · p. 47
  • Since Ur ⊆ S implies PrPS = Pr, the proof uses smoothness and strong convexity to transfer the quadratic block-error bound to bG.The supplied passage does not preserve the resulting bound's full expression.Source: §A.5 · p. 47

B Proofs for Section 5

The appendix proofs relate surrogate message updates to delayed block updates and use local slice properties and delay estimates to establish convergence results.

B Proofs for Section 5

  • Theorem 2's proof combines a one-step surrogate recursion with a delayed mismatch estimate, then applies a delay-window inequality to obtain the stated result.The appendix says it first rewrites Algorithm 2 as a delayed block update.Source: §B.3 · pp. 53–54
  • Under Theorem 2's assumptions, Algorithm 2 is equivalent to a delayed block update after iterations reach the maximum tree-block diameter.The proof states this representation for all ν ≥ max_r diam(T_r).Source: §B.3 · p. 53
  • For a fixed block update, outside coordinates remain unchanged, and majorization and touching are used to bound progress on the surrogate slice.The proof then invokes slice smoothness and strong convexity in its surrogate progress bounds.Source: §B.3 · p. 53
Loading 2610.03709v1…