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

Journal Name manuscript No. (will be inserted by the editor)

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

arXiv:2610.03709v1 [math.OC] 2 Oct 2026

Kuangyu Ding · Gesualdo Scutari

Abstract 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 prescribed local optimization updates. What this communication-centered viewpoint lacks is a general framework that uses graph structure to 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.

K. Ding Edwardson School of Industrial Engineering, Purdue University, West Lafayette, IN. E-mail: ding433@purdue.edu. G. Scutari Edwardson School of Industrial Engineering & Elmore Family School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN. E-mail: gscutari@purdue.edu. The work of Ding and Scutari has been supported by the ONR Grant # N00014-24-1-2751.

2

Kuangyu Ding, Gesualdo Scutari

1 Introduction The paper studies decentralized optimization over an undirected, connected, and simple graph G = (V, E), where V is the set of nodes (hereafter, agents), with |V| = m, and E is the set of edges; neighboring agents can exchange information over single-hop links. Each agent i ∈ V knows only its own cost function fi : Rd → R, assumed strongly convex and smooth on Rd . The agents seek to solve cooperatively the following optimization problem min F (x) :=

x∈Rd

X

fi (x).

(P)

i∈V

This class of problems and setting arise in several applications of interest, including signal processing, machine learning, multi-agent systems, and communications. Early proposals in the literature solved (P) via decentralizations of the gradient algorithm; examples include the Distributed Gradient Descent (DGD), introduced in [9] for least squares and later generalized to nonquadratic functions in [10], with a refined rate analysis in [23]. These schemes share a common structure: each iteration couples a weighted average of the neighbors’ variables–each representing its owner’s estimate of the solution–with a local gradient step controlled by a stepsize, the schemes differing in how the two operations are interleaved. The stepsize governs a dilemma between speed and accuracy: a constant stepsize α achieves a linear rate, but only to an O(α)-neighborhood of the solution [10,15,23], whereas exact convergence requires a vanishing stepsize, inducing a sublinear rate. The speed–accuracy dilemma motivated a second generation of schemes converging to the exact solution with a constant stepsize. Two routes have been followed. Both assign each agent a local copy xi of x; they differ in how the local gradient direction is corrected. (i) The first acts in the primal domain, either by tracking the global gradient ∇F [4, 12, 14, 17, 20, 22], or through correction terms based on past iterates and gradients [1, 19]. (ii) The second explicitly enforces consensus among the local copies xi ’s through linear constraints; the multipliers of a suitable (augmented) Lagrangian then adjust the local gradient direction [2, 6, 7, 16, 18].. Methods from both routes converge linearly to the minimizer of F , with different dependence on network and optimization parameters. We refer to the tutorials [11, 21] and the monograph [15] for further discussion. These two routes are not independent: several primal exact methods also admit a dual interpretation [8]. The common approach is to rewrite (P) as a centralized problem with linear consensus constraints, making centralized optimization techniques readily applicable. The constraints are chosen to support implementation over the network; the resulting formulation also determines the dual variables on which the algorithm operates. Specifically, stack the agents’ copies m×q ⊤ X = [x⊤ faithful if ker(A⊤ ) = span{1} (1 is the 1 ; . . . ; xm ], and call A ∈ R ⊤ all-ones vector). Then, A X = 0 enforces exactly consensus. With a suitable sign convention for the multipliers, the lifted problem of (P) and its dual read X fi (xi ) s.t. A⊤ X = 0, min X∈Rm×d

min

Y ∈Rq×d

i∈V

gA (Y ) :=

X i∈V

fi∗ (AY )i .

(D)

Graph Decomposition in Decentralized Optimization via Message Passing

3

Here, fi∗ is the Fenchel conjugate of fi , and each column j of A introduces one multiplier row Yj ∈ Rd . A dual solution Y ⋆ recovers the primal solution through x⋆i = ∇fi∗ ((AY ⋆ )i ), i ∈ V. Faithful choices used in the decentralized methods discussed above include (i) A = I − W , for a synmmetric gossip matrix W with ker(I − W ) = span{1} [4,8,10, 12,14,17,19,20,22]; (ii) the graph Laplacian or operators built from it [6,7,16];and (iii) edge-indexed choices–the oriented node-edge incidence matrix B of G, or that of a spanning tree. These representations all enforce the same consensus constraint among the xi ’s in (D), but generally induce different algorithms. Each column j of A creates a dual variable Yj , and its support identifies the conjugates fi∗ that depend on it; grouping columns determines which dual variables are optimized jointly. This is a design layer preceding the block partition, and not present in classical (centralized) block-coordinate methods (e.g., of Jacobi or Gauss-Seidel type), where the variables are given and only their grouping is a design choice. Here the representation A first determines the variables available for grouping and their dependencies. Choosing A must therefore be part of algorithm design, not merely a mean of enforcing consensus or selecting the communication protocol. An unexplored design layer. This design layer is unexplored in the literature: once A is fixed to enforce consensus, the network serves only as a communication medium over which algorithmic variables are exchanged, mixed, or reconciled. Agents may have different neighbors and employ different weights, but they all perform the same type of update, irrespective of their position in the graph: the topology never determines how the optimization is decomposed (long paths, dense regions, and sparse interfaces are assigned no distinct optimization roles). This uniformity can impose a severe cost: mixing becomes the convergence rate bottleneck, and the network enters the guarantees through one global scalar–the spectral gap–which measures how fast averaging propagates information, but does not reveal what optimization structure particular subgraphs may offer. Graphs like paths or rings make this price concrete: stationary nearest-neighbor mixing has inverse gap Θ(m2 ) [13], and (non-accelerated) consensus-based optimization methods inherit this quadratic iteration growth [16]–becoming the bottleneck for non accelerated optimization shemes. Yet the ring itself suggests a different decomposition. Instead of treating every edge as an averaging link, let “open” the ring into a path: one long path of edges is optimized jointly, with the remaining edges defining separate, individual subproblems. As it will be shown by our new design in Sec. ?, the path subproblem can be solved exactly by eliminating one node after another in O(m) steps–structural grounds for O(m) overall complexity, rather than O(m2 ).

1.1 From algorithm execution on a graph to graph decomposition over the graph We rethink decentralized decomposition methods from the foundations, accounting for the graph as part of the algorithm rather than its medium. Building it is the novel path taken in this paper. The major contributions are summarized next. (i) graph decomposition. We introduce a formal paradigm of algorithmic decomposition over graphs, as unified framework to device decentralized algorithms solving (P) on networks. Two observations shape the construction.

4

Kuangyu Ding, Gesualdo Scutari

(a) The algebraic factor graph: The representation A determines which dual coordinates Yj enter each conjugate term fi∗ ((AY )i )–this dependency is itself a graph: the bipartite factor graph induced by A:
HA := V ⊔ {1, . . . , q}, {(i, j) : Aij ̸= 0} ,

with one factor node per conjugate fi∗ , one variable node per dual coordinate Yj , and an edge exactly when Yj enters fi∗ . An algebraic decomposition is then obtained by selecting p nonempty blocks of dual coordinates: a block Jr ⊆ {1, . . . , q} specifies the coordinates optimized jointly, while its neighborhood in HA identifies the conjugate terms entering the resulting block subproblem. (b) Blocks on the physical network: The factor graph records algebraic dependencies, not communication links. Because HA need not respect adjacency in G, the agents touched by a block need not induce a connected subgraph of G. Connectivity of G nevertheless guarantees a connected set containing them—at worst, all of V—but such a support may be highly nonlocal, inducing an unaffordable communication overhead. We therefore assign to each block a connected carrier Cr ⊆ V: a connected region of the network hosting its subproblem, which contains all agents involved in the block. The joint choice of the three–representation, blocks, and carriers–is a graph decomposition of  (P) over G: a triple   

A |{z}

,

{Jr }pr=1 | {z }

,

{Cr }p | {zr=1}

 .

representation dual-coordinate blocks physical carriers

Here, A is faithful and has no zero column; the nonempty blocks Jr cover {1, . . . , q} and need not be disjoint; and each carrier Cr ⊆ V contains every agent i such that Ai,Jr ̸= 0 and induces a connected subgraph of G. The three layers have distinct roles: the representation creates the variables and their dependencies; the blocks fix what is optimized jointly; the carriers fix where it is executed. Sec. 2 develops this definition and its algebraic consequences. (ii) GATE as an instance. Within the graph decomposition framework above, we propose a decentralized algorithm GATE (Graph-Tearing message passing). (a) Choice of the graph decomposition: The representation is chosen so that the agents whose conjugate terms share a dual variable can communicate directly. Therefore, we associate one dual variable with each physical edge and let it enter only the conjugate terms of the two endpoint agents, which is achieved by choosing A = B, where B is the node–edge incidence matrix of G. The edge set E is partitioned into disjoint nonempty edge sets P = {Er }pr=1 , with each subgraph (Vr , Er ) required to be a tree, where Vr is the set of endpoints of Er . With dual coordinates indexed by edges, Jr = Er and Cr = Vr : the variables indexed by Er are optimized jointly by the agents in Vr . (b) Solving block subproblems via message passing: Starting from the block fixed-point decomposition, we fix an edge variable and minimize over the remaining variables in each of the two subtrees obtained by removing that edge. Their cost-to-go functions define the two endpoint messages, which can be computed recursively along the tree to the leaves. Then, each edge variable minimizes the sum of the two messages from its endpoints. Iterating the message recursion and edge minimizations, with relaxed edge updates, yields GATE.

Graph Decomposition in Decentralized Optimization via Message Passing

5

(iii) Convergence analysis, surrogate variant, and numerical validation. (a) Linear convergence with an explicit decomposition-dependent rate: We establish linear convergence of GATE with a rate ρ explicit in the interplay among function regularity, the local structure of the network, and the graph decomposition P. This rate quantifies how convergence depends on graph decomposition, a design layer unexplored by consensus-based methods, where mixing can limit convergence through the global spectral gap. For tree-dominant graphs of diameter D, the explicit rate guides partition selection to achieve (1−ρ)−1 = O(D). For example, on rings, this becomes O(m), compared with O(m2 ) for the (nonaccelerated) consensus-based methods, with such improved scalability arising as a byproduct of graph decomposition. (b) Surrogate variant: To reduce per-iteration computational and communication costs, we propose GATE-S, a surrogate variant of GATE. We present practical surrogate choices and their message implementations, and provide an analogous linear convergence rate and scalability analysis. (c) Numerical experiments: We conduct numerical experiments to validate the theoretical results and evaluate the iteration and communication efficiency of GATE and its surrogate variants relative to consensus-based methods.

1.2 Notation F For a positive integer q, write [q] := {1, . . . , q}, and use for disjoint union. For functions F (x, y) and G(x, y), write F ∼x G when F − G is independent of x. When the variable is clear from context, we write F ∼ G. We use row-stacked matrices for d-vectors. If the rows of a matrix A are indexed by a finite set J , then Aα denotes the row indexed by α ∈ J , and AS denotes the submatrix of rows indexed by S ⊆ J . For matrices with both row and column indices, AI,S denotes the submatrix with rows I and columns S. Whenever such a row vector appears as an argument of fi∗ , in an inner product, or in a norm, it is identified with the corresponding vector in Rd . For node variables (xi )i∈V , X denotes the row-stacked matrix whose i-th row is x⊤ i . Inner products between rowstacked matrices use the Frobenius convention. For scalar functions on row-stacked matrices, ∇Φ(A)⊤ denotes the row-stacked gradient. We write Sd for the space of d×d symmetric matrices, and Sd+ and Sd++ for its positive semidefinite and positive definite cones. For a scalar differentiable function ϕ, ∇ϕ is the column gradient and ∇2 ϕ is the Hessian. For a vector-valued map F = (F1 , . . . , Fk ) : Rd → Rk , we set ∇F (x) := [∇F1 (x), . . . , ∇Fk (x)] ∈ Rd×k ; hence ∇F (x)⊤ is the Jacobian and ∇F (x)⊤ h is the directional variation along h. For a matrix-valued map H, ∇H(x)[h] denotes the directional derivative in direction h. Organization. The remainder of the paper is organized as follows. Section 2 develops the graph decomposition framework. Section 3 specializes it to the incidence representation and tree blocks to derive GATE. Section 4 establishes linear convergence and partition-dependent rate bounds. Section 5 develops the surrogate variant of GATE and establishes its convergence. Section 6 presents numerical experiments, and Section 7 concludes.

6

Kuangyu Ding, Gesualdo Scutari

2 Graph Decomposition Framework 2.1 Problem and graph setting We study (P) over the graph G under the following standard assumptions.

Assumption 1 (problem class) For every i ∈ V, fi : Rd → R is µfi -strongly convex and Lfi -smooth for some µfi , Lfi > 0. Define L µ := min µfi , L := max Lfi , κ := . i∈V i∈V µ Consequently, each fi∗ is finite-valued, differentiable, 1/Lfi -strongly convex and 1/µfi -smooth. Assumption 2 (Network) The graph G = (V, E) is undirected, connected, and simple. Fix an arbitrary orientation of E and let B ∈ Rm×|E| be the node–edge incidence matrix, with   if v is the tail of e, 1, Bve := −1, if v is the head of e,   0, otherwise. For v ∈ V and e ∈ E, let Av := {e ∈ E : e is incident to v}

and

Ie := {v ∈ V : v is an endpoint of e}.

The node-edge incidence graph of a graph is the bipartite graph on its nodes and edges in which a node and an edge are adjacent exactly when the node is an endpoint of the edge. For a physical subgraph Gs ⊆ G, write V (Gs ) and E(Gs ) for its vertex and edge sets; for S ⊆ V, G[S] denotes the subgraph of G induced by S. 2.2 Graph decomposition This section builds the proposed decompositon framework. 2.2.1 Representations and their factor graphs Recall from Sec. 1 that a matrix A ∈ Rm×q is faithful if ker(A⊤ ) = span{1}, so ⊤ that A⊤ X = 0 holds exactly for consensual stacked copies X = [x⊤ 1 ; . . . ; xm ]. As derived there, the lifted consensus form of the problem has the dual from (D), with one multiplier row Yj ∈ Rd per column j of A. Every faithful A represents the same consensus set, but the dual (D) depends on A itself: the columns create the dual coordinates, and the sparsity pattern of A decides which coordinates enter which conjugate. This dependency structure is captured by the factor graph. Definition 1 (Factor graph) The factor graph induced by A is the bipartite graph
HA := V ⊔ {1, . . . , q}, {(i, j) : Aij ̸= 0} , whose factor node i represents the term fi∗ ((AY )i ) and whose variable node j represents the dual coordinate Yj .

Graph Decomposition in Decentralized Optimization via Message Passing

7

The two sides of HA are not symmetric: each factor node is anchored at a physical agent, whereas a variable node need not have a prescribed phisical location on G. Consequently, a single variable Yj –column A:,j –may enter the conjugates of nonadjacent agents. Example 1 Given the path graph 1 − 2 − 3, with both edges oriented from left to right (Figure 1(a)), consider the following three faithful choices of A:   1 1 1 A = Aex :=  0 −2 , A = L := BB⊤ , or A = B. (1) 3 −1 1 Here, B is the incidence matrix of G, and L is its scaled Laplacian. The three matrices enforce the same consensus constraint, yet they induce the distinct factor graphs of Figure 1(b)-(d). 1 For Aex , the coordinate Y1 enters the factors of the nonadjacent agents 1 and 3. For L, Y1 and Y2 both enter f1∗ and f2∗ , so HL contains a cycle although G is a path. For B, each coordinate corresponds to one physical edge and enters exactly its endpoint factors, so HB is the node-edge incidence graph of G, that is, the bipartite graph on V ⊔ E in which i and e are adjacent exactly when i ∈ Ie . This distinction matters when the dual coordinates are grouped and optimized jointly: a group of coordinates of B is a set of physical edges, one per coordinate; whereas a group under L or Aex may couple nonadjacent agents. 2.2.2 Block covers and conditional responses To minimize gA blockwise, we group the dual coordinates into (possibly overlapping) blocks. Each block-subproblem minimizes gA over its block coordinates, holding the remaining coordinates fixed. Definition 2 (Block cover and conditional responses) For a fixed A, a block cover is a family {Jr }pr=1 of nonempty subsets covering [q] (the index set of the dual coordinates). Let J r := [q] \ Jr . For each block Jr , define its touched factor set and block factor graph by VA,r := {i ∈ V : Ai,Jr ̸= 0},

FA,r := HA [VA,r ⊔ Jr ].

Here, HA [S] denotes the subgraph of HA induced by the vertex set S. The conditional response of block r is  X ∗ BRA,r (YJ r ) := argmin fi Ai,Jr W + Ai,J r YJ r . W ∈R|Jr |×d i∈V

(2)

(3)

A,r

Under Assumption 1, BRA,r (YJ r ) is nonempty for every r ∈ [p] and YJ r , but need not be a singleton. When A is fixed, we suppress it and write Vr , Fr , and BRr . Thus Jr identifies the coordinates optimized jointly, VA,r the agents whose conjugates enter the block subproblem, and FA,r records which block coordinates enter each conjugate. Proposition 1 (Block fixed points) Let Assumption 1 hold, let A be faithful, and let {Jr }pr=1 be a block cover. Then, Y ⋆ ∈ argmin gA (Y ) Y ∈Rq×d

⇐⇒

YJ⋆r ∈ BRr (YJ⋆ r )

∀r ∈ [p].

(4)

1 In panels (b) and (c), the subscripts of Y index the columns of A ex and L, respectively; in panel (d), Y12 and Y23 are indexed by the physical edges (1, 2) and (2, 3).

8

Kuangyu Ding, Gesualdo Scutari

f1∗ 1

2

f2∗

f3∗

3 Y1

(b) HAex

(a) physical path G

f1∗

f2∗

f3∗

Y1

Y2

Y3

(c) HL

Y2

f1∗

f2∗

Y12

f3∗

Y23

(d) HB

Fig. 1: Three faithful representations (see (1)) of the same path graph 1 − 2 − 3 induce distinct factor graphs: the generic Aex couples nonadjacent factors, the Laplacian L produces a cyclic factor graph, and the incidence matrix B reproduces the node-edge incidence structure. Proposition 1 holds for every faithful A and every block cover: optimality restricts neither choice. Different choices produce different response maps BRA,r (YJ r )–hence, potentially, different algorithms–but the algebraic decomposition (A, {Jr }) does not specify where these responses are computed on G. Since fi∗ is available only at agent i, computing BRr requires the agents indexed by Vr to exchange information over the links of G. These exchanges can be confined to the agents of Vr only if G[Vr ] is connected, which Definition 2 does not guarantee. In Example 1, the subproblem of the block {1} (the variable Y1 ) of Aex contains the conjugates f1∗ and f3∗ , stored at the nonadjacent agents 1 and 3, which can communicate only through agent 2, whose conjugate does not enter the subproblem. The computation of a block response thus involves, besides the agents of Vr , those that relay between them; the set of all agents taking part in it must induce a connected subgraph containing Vr . This is formalized next. 2.2.3 Carriers and realizability We associate with each block Jr a set of agents Cr that enable the joint computation of the conditional response BRr of the block on G. This set, called the carrier of Jr , must induce a connected subgraph of G and contain the agents in Vr , whose conjugates enter the block subproblem (3). We formalize the joint choice of representation, block cover, and carriers as a graph decomposition.

Graph Decomposition in Decentralized Optimization via Message Passing

9

Definition 3 (Graph decomposition) A graph decomposition over G is a triple
D := A, {Jr }pr=1 , {Cr }pr=1 ,

(5)

where A is faithful, {Jr }pr=1 is a block cover of gA , and the set ∅ ̸= Cr ⊆ V is the carrier of block r satisfying Vr ⊆ Cr

and

G[Cr ] is connected.

(6)

The three components have distinct roles: A creates the dual coordinates and their dependencies, Jr fixes what is optimized jointly, and Cr specifies the subgraph on which that computation is performed. The agents indexed by Cr \ Vr contribute no term to the subproblem (3): their only role is to relay information between agents of Vr that are not adjacent in G (as agent 2 does for the block {1} of Aex in Example 1). When G[Vr ] is connected, the carrier can be taken equal to Vr and no additional relay agents are required. For a subgraph Gs = (Vs , Es ) ⊆ G, let BGs ∈ Rm×|Es | be the matrix obtained from B by retaining the columns indexed by Es . The rows indexed by V \Vs are zero. The carrier conditions (6) admit the following equivalent matrix factorization. Proposition 2 (realizability) Fix r ∈ [p]. Let A be faithful, let ∅ ̸= Jr ⊆ [q], and let ∅ ̸= Cr ⊆ V. Conditions (6) hold if and only if there exist a connected subgraph Gr ⊆ G, with V(Gr ) = Cr , and a matrix Mr ∈ R|Jr |×|E(Gr )| such that A:,Jr = BGr Mr⊤ .

(7)

Proposition 2 decomposes the linear couplings recorded by adjacency in the block factor graph Fr (see (2))–which agents’ conjugate terms depend on each dual coordinate Yj –into couplings between adjacent agents in the connected physical subgraph Gr (with vertex set Cr ). This opens the way to design methods that compute BRr through neighbor-to-neighbor communication within the carrier. To make the connection explicit, recall from (3) that each block coordinate Yj enters the argument of fi∗ with coefficient Aij . By (7), A:,j is a linear combination of the columns of B indexed by the edges of Gr , with coefficients given by the corresponding row of Mr ; its nonzero entries are the agents whose factor nodes are adjacent to the variable node j in Fr . If the row of Mr corresponding to Yj has a single nonzero entry, Yj appears only in the conjugates fi∗ of the two endpoint agents of one physical edge, which are neighbors in G and can communicate directly. If that row has several nonzero entries, Yj may appear in the conjugates of nonadjacent agents or of more than two agents; these agents can exchange information along the edges of Gr , with intermediate agents relaying it when needed. At agents in Cr \ Vr , the linear combinations in (7) vanish for every block coordinate: their conjugate terms are independent of the block variables, and these agents can serve as relays. Example 1 revisited and Figure 2 illustrate these distinctions. Example 1 revisited. Let e1 = {1, 2} and e2 = {2, 3}, with both edges oriented from left to right. For each representation in Example 1, choose the singleton block cover, with one block per dual coordinate. We examine the blocks {1} and

10

Kuangyu Ding, Gesualdo Scutari f1∗

f3∗

f1∗

f2∗

f3∗

f1∗

f2∗ conjugate of an agent Ye 1

Y1

Y2

(a) FAex ,{1}

(b) FL,{2}

dual coordinate (c) FB,{e1 }

touched agent relay agent

1

1

2

1

3

1

(d) Gr for block {1} of Aex Vr = {1, 3}, Cr = {1, 2, 3}

− 13

2

1 3

3

1

(e) Gr for block {2} of L Vr = Cr = {1, 2, 3}

1

2

3

outside the carrier

(f) Gr for block {e1 } of B Vr = Cr = {1, 2}

Fig. 2: Example 1 revisited. Top: block factor graphs. Bottom: carrier subgraphs Gr , with the entries of Mr on the edges. {2} of Aex , the block {2} of L, and the block {e1 } of B. Their conditional responses, with terms in gA independent of W omitted, are  BRAex ,{1} (Y2 ) = argmin f1∗ (W + Y2 ) + f3∗ (−W + Y2 ) , W  BRAex ,{2} (Y1 ) = argmin f1∗ (Y1 + W ) + f2∗ (−2W ) + f3∗ (−Y1 + W ) , W


 BRL,{2} (Y1 , Y3 ) = argmin f1∗ 31 (Y1 − W ) + f2∗ 31 (2W − Y1 − Y3 ) + f3∗ 31 (Y3 − W ) , W  BRB,{e1 } (Ye2 ) = argmin f1∗ (W ) + f2∗ (Ye2 − W ) . W

The factor sets touched by the four blocks, read off from the responses, are Vr = {1, 3} for the first, as in Figure 2(a); {1, 2, 3} for the second and third, with the Laplacian case shown in panel (b); and {1, 2} for the last, as in panel (c). Only the first fails to induce a connected subgraph of G. Its carrier must therefore contain agent 2, giving Cr = {1, 2, 3} (panel (d)): this agent relays between agents 1 and 3 without contributing a conjugate to the subproblem. For the other three blocks, choose Cr = Vr ; panels (e),(f) illustrate the Laplacian and incidence cases. Taking Gr = G[Cr ] gives the whole path for the first three blocks and the single edge e1 for the last, so that BGr = B:,e1 there. The corresponding factorizations from Proposition 2 are (Aex ):,1 = B:,e1 + B:,e2 , L:,2 = 13

−B:,e1 + B:,e2 ,

(Aex ):,2 = B:,e1 − B:,e2 , B:,e1 = BGr .

(8)

The matrices Mr are respectively (1, 1), (1, −1), 31 (−1, 1), and (1); their entries label the physical edges in Figure 2(d)–(f) for the illustrated blocks. In the first identity, the two columns of B have opposite entries at agent 2, which cancel. Thus f2∗ (−2Y2 ) is independent of W : agent 2 is absent from the block factor graph but present in the physical subgraph as a relay. The second and third combinations have nonzero entries at all three agents, so every agent contributes a conjugate to the response. For the last block, Mr = (1) uses only e1 , whose endpoint agents are neighbors and communicate directly. Here f3∗ is absent because e1 is not incident to agent 3, rather than through cancellation.

Graph Decomposition in Decentralized Optimization via Message Passing

11

3 Graph Tearing Along Edges: Message Passing on Tree Blocks Proposition 1 holds for every faithful A and every block cover, while Proposition 2 characterizes the admissible carriers (i.e., satisfying (6)). The framework leaves these choices and the methods for computing the block responses open, with different communication and computation costs. Choices range from Laplacian-type representations in which a coordinate couples an agent with all its neighbors, to the incidence representation, in which a coordinate couples one pair of neighbors. We now use this freedom to design a decentralized algorithm, termed GATE (Graph-Tearing message passing). We choose a graph decomposition in which selecting dual coordinates amounts to selecting edges of G, so that each coordinate appears in the conjugates of two neighboring agents, and a block response can be computed by exchanges between the neighboring agents whose conjugates enter it, without relay agents. More formally we have the following. (i) Representation: We choose A so that, for each block, the factorization (7) admits a matrix Mr with one nonzero entry per row and with different rows selecting distinct edges. Each coordinate then enters exactly the conjugates at the two endpoints of its selected edge, avoiding redundant coordinates on the same edge. Let Er denote the set of these edges. Indexing the coordinates by Er and absorbing each nonzero coefficient into its coordinate (a change of variables in the dual (D)) gives A:,Jr = B:,Er . (ii) Partition: We retain one coordinate for every physical edge, leaving the whole network available for block selection. We partition the edge-set E into nonempty sets P := {Er }pr=1 , so that each variable receives one block update. Write Tr := (Vr , Er ) for the subgraph selected by block r; by Definition 2, Vr , s the set of endpoints of Er . We take each Tr to be connected, without loss of generality (the response (3) of a disconnected Tr separates into independent responses on its connected components, which can be taken as separate blocks.). (iii) Carriers: We use only the agents whose conjugates enter the response: take Cr := Vr . Connectivity of Tr makes G[Vr ] connected, so the carrier conditions (6) hold, and no additional relay agents are needed. The three design choices are summarized by A:,Jr = B:,Er ,

p G r=1

Er = E,

Cr = Vr ,

r ∈ [p].

(9)

After ordering the columns, A = B, with ker(B⊤ ) = span{1} (under Assumption 2); hence A is faithful. Since {Er }pr=1 is a block cover and (6) holds with Cr = Vr , (9) defines a graph decomposition over G (Definition 3): the block factor graph Fr is the node-edge incidence graph of Tr , that is, the bipartite graph on Vr ⊔ Er in which i and e are adjacent exactly when i ∈ Ie ; and (7) holds with Gr = Tr and Mr = I. The partition remains a design choice: finer partitions give smaller block subproblems but may need more rounds to resolve the coupling between blocks. The convergence analysis in Sec. 4 will quantify the effect of the partition on the rate and guide this computation-communication tradeoff. The remainder of this section derives the algorithm GATE: the structure of the blocks is specified, and the block fixed-point conditions of Proposition 1 are rewritten as relations for individual edge variables and local messages. Their relaxed parallel iteration yields GATE.

12

Kuangyu Ding, Gesualdo Scutari

3.1 Tree-block responses and message equations Fix a block r ∈ [p] and the exterior coordinates YE r ; under (9), the conditional response becomes X ∗
BRr (YE r ) = argmin (10) fi Bi,Er W + Bi,E r YE r . W ∈R|Er |×d i∈V

r

The conjugates in (10) are held by different agents. We seek subgraphs Tr that enable the computation of BRr through exchanges between neighboring agents only. Fixing the coordinate Ye separates the remaining minimization in (10) into two independent subproblems whenever removing e disconnects Tr . Trees permit this separation at every edge. They also eliminate coordinate redundancy: minimizing over the |Vr | − 1 edge variables of a spanning tree, while fixing those on the other edges of Tr , gives the same optimal value as minimizing over the entire block. This is established in the following proposition. Proposition 3 Let Tr be connected and let Er′ be the edge set of any spanning tree of Tr . Then Range(B:,Er′ ) = Range(B:,Er ) and ker(B:,Er′ ) = {0}. Furthermore, under Assumption 1, the response BRr (YE r ) is a singleton for every fixed YE r if and only if Tr is a tree. We therefore choose each Tr to be a tree. Assumption 3 For every block r ∈ [p], the accociated subgraph Tr is a tree. We now express the block-optimality conditions (4) through quantities that the two endpoints of each edge can form and exchange. To distinguish edges inside and outside the block, define, for i ∈ Vr , A◦i := Ai ∩ Er ,

A∂i := Ai ∩ E r ,

Vr◦ := {i ∈ Vr : A∂i = ∅},

Vr∂ := Vr \ Vr◦ .

Relative to Tr , agents in Vr◦ are interior : all their incident edges belong to Er . Agents in Vr∂ are boundary: they also have incident edges outside Er . In (10), only the conjugate terms of boundary agents depend on the exterior coordinates; these terms may also depend on several block variables. Splitting at the edge. For each block r, uniqueness of the conditional response (Proposition 3) gives the following equivalent conditions: YE⋆r ∈ BRr (YE⋆r ) ⇐⇒

Ye⋆ ∈ argmin ye ∈R1×d

(

) min

X

YEr Ye =ye i∈Vr

fi∗

Bi,Er YEr + Bi,E r YE⋆r

∀e ∈ Er .

(11)

By Proposition 1, Y ⋆ solves (D) if and only if these conditions hold for every block. To decompose the inner minimization in (11), fix Ye = ye . Removing e from Tr separates this minimization into two decoupled subproblems, one on each resulting connected subgraph. We solve them recursively from the leaves toward e. For each endpoint i ∈ Ie of e, let Ve (i) and Ee (i) denote the vertex and edge sets of the resulting connected subgraph containing i. Figure 3(a) illustrates the two resulting subgraphs. Every block edge other than e lies in one of these two

Graph Decomposition in Decentralized Optimization via Message Passing

(a) Splitting at the edge (Ve (i), Ee (i)) j1 i

j2

µi′ →e (ye )

e Ye = ye

i′ j′

YE⋆r fixed on dashed exterior edges

(b) Recursive elimination at i (Vh1 (j1 ), Eh1 (j1 )) j1

(Ve (i′ ), Ee (i′ ))

µi→e (ye ) h1 h2

13

µj1 →h1 (Yh1 ) µi→e (ye ) h1 h2

i

e Ye = ye

i′

j2 j′ ⋆ YA∂ fixed (Vh2 (j2 ), Eh2 (j2 )) µj →h (Yh ) i 2 2 2  ∗ µi→e (ye ) = min fi (· · · ) + µj1 →h1 (Yh1 ) + µj2 →h2 (Yh2 ) Yh1 ,Yh2

Fig. 3: Messages on the same tree block: (a) fixing Ye = ye separates the minimization into two subgraphs; (b) eliminating Yh1 , Yh2 combines the two incoming messages with fi∗ , while the dashed exterior-edge coordinates remain fixed at YE⋆ . r

subgraphs. Thus, with Ye = ye , no remaining block variable enters conjugates from both subgraphs, and X ∗
min fk Bk,Er YEr + Bk,E r YE⋆r YEr ∈R|Er |×d k∈Vr Ye =ye

=

X i∈Ie

min

YEe (i) ∈R|Ee (i)|×d

|

X k∈Ve (i)

fk∗ Bk,Ee (i) YEe (i) + Bk,e ye + Bk,E r YE⋆r . {z =: µi→e (ye )

(12)

}

The sum over Ie in (12) reads µi→e (ye )+µi′ →e (ye ), where i and i′ are the two endpoints of e; µi→e (ye ) [resp. µi′ →e (ye )] represents the cost-to-go for the subgraph (Ve (i), Ee (i)) [resp. (Ve (i′ ), Ee (i′ ))]; together, they determine Ye⋆ through (11). We call them messages, as this information is exchanged between the endpoints of e; the arrows in Figure 3(a) indicate the two messages. Their dependence on YE⋆ is r suppressed for notational convenience. Computing µi→e via recursive elimination along the subtrees. We evaluate the minimization defining µi→e (ye ) by successively eliminating the edge variables YEe (i) of the subgraph (Ve (i), Ee (i)), proceeding from its leaves toward e (through the endpoint i), while Ye = ye and YE⋆ remain fixed. r

14

Kuangyu Ding, Gesualdo Scutari

(i) Leaves. If Ve (i) = {i}, then Ee (i) = ∅, and

µi→e (ye ) = fi∗ Bi,e ye + Bi,E r YE⋆r .

(13)

The message is finite-valued and strongly convex by Assumption 1, since Bi,e = ±1. (ii) Remaining agents. Otherwise, |Ve (i)| > 1. Removing i from (Ve (i), Ee (i)) leaves |A◦i | − 1 connected subgraphs, one for each edge h ∈ A◦i \ {e}. For each such h, let j be its endpoint other than i, so that {j} = Ih \ {i}. The resulting subgraph containing j is (Vh (j), Eh (j)): its agents k are exactly those whose unique path from i to k in Tr begins with h. As h varies over A◦i \ {e}, the sets Vh (j), are pairwise disjoint and, together with {i}, form a partition of Ve (i). The corresponding edge sets {h} ∪ Eh (j) partition Ee (i): any additional edge would join two distinct subgraphs (Vh (j), Eh (j)) and create a cycle in Tr . Hence, G Ve (i) = {i} ⊔ Vh (j), h∈A◦ i \{e} j∈Ih \{i}

Ee (i) =

G h∈A◦ i \{e} j∈Ih \{i}

(14)

{h} ⊔ Eh (j) .

We proceed by induction on |Ve (i)|, starting from the leaf case (13). For each h ∈ A◦i \ {e}, let {j} = Ih \ {i}. Since |Vh (j)| < |Ve (i)|, the induction hypothesis ensures that µj→h is finite-valued and strongly convex, and its defining minimum is uniquely attained for every fixed Yh . In the minimization defining µi→e (ye ) in (12), first hold YA◦i \{e} fixed. By (14), the sum of conjugates on each Vh (j) can be minimized independently over YEh (j) , giving µj→h (Yh ), since every block edge of an agent of Vh (j) lies in {h} ∪ Eh (j). Minimizing the sum of these messages and agent i’s conjugate over YA◦i \{e} , while Ye = ye and YE⋆ remain fixed, gives r (
µi→e (ye ) = min fi∗ Bi,e ye + Bi,A◦i \{e} YA◦i \{e} + Bi,E r YE⋆r YA◦ \{e} i

(15)

) +

X

X

h∈A◦ i \{e} j∈Ih \{i}

µj→h (Yh ) ,

i ∈ Vr ,

e ∈ A◦i .

Figure 3(b) illustrates this recursion for two edges incident to i other than e. The objective in this recursion is finite-valued and jointly strongly convex in (ye , YA◦i \{e} ). For each ye , its minimum is therefore uniquely attained, and partial minimization yields a finite-valued, strongly convex µi→e . Once the minimizing values Yh , h ∈ A◦i \ {e}, are fixed, the induction hypothesis uniquely determines the minimizing YEh (j) , where {j} = Ih \ {i}. By (14), these variables constitute the unique minimizer YEe (i) in (12), completing the induction. The same induction shows that any family satisfying (15) coincides with the messages defined in (12). Proposition 4 (Message fixed points) Under Assumptions 1, 2, and 3, consider the decomposition (9). For Y ⋆ ∈ R|E|×d , let µi→e be the messages defined in (12), with YE⋆ fixed in each block. Then Y ⋆ solves (D) if and only if r X {Ye⋆ } = argmin µi→e (ye ), e ∈ Er , r ∈ [p]. (16) ye ∈R1×d i∈I

e

Graph Decomposition in Decentralized Optimization via Message Passing

15

Algorithm 1: GATE: Graph-Tearing message passing p Input: Edge assignment a with ownership sets {Aa i }i∈V ; edge partition {Er }r=1 ; initial edge variables Y 0 ; finite-valued strongly convex initial messages µ0i→e , e ∈ E, i ∈ Ie ; relaxation parameters τrν ∈ [0, 1]; N ≥ 1. for ν = 0, 1, . . . , N − 1 do Each node i ∈ V executes the following steps, in parallel with the other nodes:

(1) Assigned edge-variable update. foreach r ∈ [p] and e ∈ Aa i ∩ Er , compute ν+1

Ŷe

Send Yeν+1

 X

ye ∈R1×d j∈I

ν+1

Ye

∈ argmin ν

ν

e

  ν µj→e (ye ) , 

ν+1

= Ye + τr Ŷe

(17a)

ν
− Ye .

(17b)

to the other endpoint of e.

(2) Node-to-edge message update: foreach r ∈ [p] and e ∈ Ai ∩ Er , compute (   ν+1 ν+1 ∗ µi→e (ye ) = min fi Bi,e ye + Bi,A◦i \{e} YA◦i \{e} + Bi,A∂i YA∂ YA◦ \{e}

i

i

) +

X

X

(18)

ν

µj→h (Yh ) .

h∈A◦ \{e} j∈Ih \{i} i

Send µν+1 i→e

to the other endpoint of e.

∗ N Primal recovery. Each node i ∈ V computes xN )i ). i := ∇fi ((BY

The message recursion (15) and the edge conditions (16) form the fixed-point system whose relaxed parallel iteration defines GATE. This is formalized next.

3.2 The node-owned GATE algorithm GATE iterates the edge conditions (16) and the recursion (15), with relaxed edge updates, as summarized in Algorithm 1. To avoid an edge-level coordinator, an edge-node assignment is introduced, a : E → V with a(e) ∈ Ie . Define Aai := {e ∈ Ai : a(e) = i}. These sets are pairwise disjoint and cover E. Node i updates Ye for e ∈ Aai , while both endpoint-nodes retain a copy. For each edge e, r denotes its block index, and A◦i , A∂i are understood relative to that block. GATE is fully decentralized: each agent computes locally and communicates only with its neighbors, without a central coordinator. This is discussed next. Initialization. For each edge e, its owner a(e) chooses Ye0 arbitrarily and sends it to the other endpoint. Each node i then selects a finite-valued strongly convex message µ0i→e for every e ∈ Ai and sends it to the other endpoint of e. For intance,
one local choice is µ0i→e (ye ) = fi∗ Bi,e ye + Bi,Ai \{e} YA0 i \{e} . Local computations and communications. Step (1): Each node updates only its assigned edges, using the two endpoint messages at round ν. Relaxation damps the edge update, which is then shared with the other endpoint. Step (2): Each node updates a message on every incident edge, whether or not it owns that edge. The local minimization uses its conjugate and the incoming messages µν , with incident exterior coordinates fixed at the newly available Y ν+1 . Its minimizing variables are local to this computation and do not overwrite the stored edge iterates. The outgoing messages are sent to the other endpoints for round ν + 1.

16

Kuangyu Ding, Gesualdo Scutari

Nodes work in parallel within each step, once the required data have arrived. Each round advances every message once, and sends one d-vector and two functions per edge. Primal recovery uses only the incident edge coordinates. 4 Convergence Analysis In this section, we establish convergence of Algorithm 1. We begin with the quantities the analysis is built on. 4.1 Image variables and block error bound For the incidence representation A = B, write g := gB and define X ∗ G(W ) := fi (Wi ), W ∈ Rm×d . i∈V

Under Assumption 1, G is strongly convex. On loopy graphs, however, the incidence map is not injective and g(Y ) = G(BY ) is constant along ker B: it is not strongly convex in the edge variables Y . The analysis therefore runs in the image variable Z := BY , which ranges over the subspace S := {BY : Y ∈ R|E|×d } ⊆ R|V|×d . Changing YEr alone moves Z along the affine subspace Z + Ur , where US := {BV,S H : H ∈ R|S|×d } ⊆ S. In particular, we write Ur := UEr . For Z ∈ S, let Or (Z) denote the unique minimizer Or (Z) = argmin G(U ),

(19)

U ∈Z+Ur

which is well defined and unique because G is strongly convex and Z +Ur is closed, and let ∆r (Z) := G(Z) − G(Or (Z)) ≥ 0 be the progress of one exact minimization of block r from Z; it vanishes exactly when Z minimizes G over Z + Ur . Let G⋆ := minU ∈S G(U ), attained because G is strongly convex and S is closed. The analysis rests on the following condition, which bounds the optimality gap G(Z) − G⋆ by the progress of all blocks. Assumption 4 (block error bound) There exists a partition-dependent constant κP < ∞ such that p X G(Z) − G⋆ ≤ κP ∆r (Z), Z ∈ S. (20) r=1

Equivalently, the same condition can be written in edge variables. For Y , choose ȲEr ∈ BRr (YE r ),

δr (Y ) := g(Y ) − g(ȲEr , YE r ).

Then δr (Y ) = ∆r (BY ). Hence, with g ⋆ := minY g(Y ) = G⋆ , (20) is equivalently g(Y ) − g ⋆ ≤ κP

p X r=1

δr (Y ),

Y ∈ R|E|×d .

Graph Decomposition in Decentralized Optimization via Message Passing

17

Remark 1 The block error bound is tailored to the decomposition underlying Algorithm 1: it controls the full gap g(Y ) − g ⋆ by the aggregate exact block gap Pp r=1 δr (Y ), thereby capturing the coupling among the blocks under the partition P. The smallest admissible constant in Assumption 4 is κP =

g(Y ) − g ⋆ Pp . Y ∈R|E|×d : g(Y )>g ⋆ r=1 δr (Y ) sup

κP admits a generic bound based on global curvature estimates for F and spectral estimates for B, which, however, does not exploit the partition underlying Algorithm 1 and is therefore often conservative. For example, with the single-block partition P = {E} on a tree, block minimization solves the dual problem exactly, so δ1 (Y ) = g(Y ) − g ⋆ and κP = 1, which is independent of the curvature of F and the spectral properties of B. Exploiting this partition dependence can yield substantially sharper bounds in favorable graph/partition regimes, as shown in Section 4.4. The proof separates into two steps. Step 1 eliminates the recursive tree messages and identifies the implemented update as a delayed block-Jacobi step; Step 2 proves linear convergence of the resulting delayed block-Jacobi scheme.

4.2 Step 1: Equivalence to a delayed block-Jacobi scheme The delayed block-Jacobi scheme is obtained by recursively expanding the messages in the edge update (17a) using the node-to-edge recursion (18). Each substitution replaces one message by the corresponding local node factor and the incoming messages from the preceding round; iterating this expansion along the tree eliminates the recursive messages, while the exterior edge variables entering at boundary nodes remain fixed at the corresponding delayed iterates. This yields the following delayed block-Jacobi representation. Proposition 5 Suppose Assumptions 1 and 3 hold. Then, for all ν ≥ maxr∈[p] diam(Tr ), Algorithm 1 can be rewritten in the equivalent form: for any e ∈ Er and r ∈ [p], Yeν+1 = Yeν + τrν (Ŷeν+1 − Yeν ),    X  X ν−δ Ŷeν+1 ∈ argmin min fi∗ Bi,A◦i YA◦i + Bi,h Yh e,i  . YEr \{e}   Ye ∂ i∈Vr

(21a) (21b)

h∈Ai

The delay is defined by δe,i := Proof See Appendix A.1.

distFr (e, i) − 1 , 2

e ∈ Er ,

i ∈ Vr∂ .

(22) ⊓ ⊔

18

Kuangyu Ding, Gesualdo Scutari

4.3 Step 2: Convergence of the delayed block-Jacobi scheme We now establish convergence for the delayed block-Jacobi scheme in (21). For r ∈ [p], introduce the virtual non-delayed block update: ȲEν+1 ∈ argmin g(YEr , YEνr ) r YEr

Throughout, if i ∈ V is a node index, Ziν := (Z ν )i denotes the i-th row of Z ν . For the block index r, write Z ν := BY ν ,

Zrν := BV,Er YEνr ,

Ẑrν+1 := BV,Er ŶEν+1 , r

Z̄rν+1 := BV,Er ȲEν+1 . r

Varying YEr with YEν fixed maps, under Y 7→ BY , onto the slice Z ν + Ur . Since r g = G ◦ B, the non-delayed block replacement satisfies Z ν − Zrν + Z̄rν+1 = BV,Er ȲEν+1 + BV,E r YEνr = Or (Z ν ) ∈ argmin G(U ). r U ∈Z ν +Ur

The stepsize bounds below depend on the overlap of active node sets: ωP := max {r ∈ [p] : i ∈ Vr } .

(23)

i∈V

It satisfies 1 ≤ ωP ≤ min{p, maxi∈V |Ai |}. The first result is the descent of G along the iterates {Z ν }, summarized next. Lemma 1 Under Assumptions 1 and 4, if 0 ≤ τrν ≤ 1/ωP for every r ∈ [p], then G(Z ν+1 ) ≤ G(Z ν ) −

p X r=1

τrν ∆r (Z ν ) +

p X τrν

2µr r=1

∥Ẑrν+1 − Z̄rν+1 ∥2 ,

(24)

where Z̄rν+1 is the exact non-delayed image-space block minimizer. Proof Since Z ν − Zrν + Z̄rν+1 minimizes G over Z ν + Ur , the first-order condition gives E D ∇G(Z ν − Zrν + Z̄rν+1 )⊤ , H = 0, H ∈ Ur . Since Ẑrν+1 − Z̄rν+1 ∈ Ur , 1/µr -smoothness and the preceding condition give G(Z ν − Zrν + Ẑrν+1 ) ≤ G(Z ν − Zrν + Z̄rν+1 ) +

1 ∥Ẑrν+1 − Z̄rν+1 ∥2 . 2µr

/ Vr . Hence, Note that (Ẑrν+1 − Zrν )i = 0 for every i ∈     X X Ziν+1 = 1 − τrν  Ziν + τrν Z ν − Zrν + Ẑrν+1 . r∈[p]: i∈Vr

r∈[p]: i∈Vr

i

(25)

Since τrν ≤ 1/ωP , applying Jensen’s inequality to (25) gives     X X fi∗ (Ziν+1 ) ≤ 1 − τrν  fi∗ (Ziν ) + τrν fi∗ (Z ν − Zrν + Ẑrν+1 )i . r∈[p]: i∈Vr

r∈[p]: i∈Vr

Graph Decomposition in Decentralized Optimization via Message Passing

19

For i ∈ / Vr , (Z ν − Zrν + Ẑrν+1 )i = Ziν . Hence, i X h ∗ ν+1 G(Z ν+1 ) − G(Z ν ) = fi (Zi ) − fi∗ (Ziν ) i∈V

≤ =

X

h

fi∗

i∈V r∈[p]: i∈Vr p X r=1

=

τrν

X

p X r=1

τrν

  i (Z ν − Zrν + Ẑrν+1 )i − fi∗ (Ziν )

 i X h ∗ ν fi (Z − Zrν + Ẑrν+1 )i − fi∗ (Ziν )

i∈Vr

h i τrν G(Z ν − Zrν + Ẑrν+1 ) − G(Z ν ) .

Combining this inequality with the definition of ∆r (Z ν ) gives G(Z ν+1 ) − G(Z ν ) ≤ −

p X

τrν ∆r (Z ν ) +

r=1

p X τrν

2µr r=1

∥Ẑrν+1 − Z̄rν+1 ∥2 . ⊔ ⊓

This completes the proof.

Applying Assumption 4 to (24) yields a global-gap contraction, a descent term in the block increments, and a delay-induced mismatch term. Lemma 2 Under Assumptions 1 and 4, assume 0 < τrν ≤ 1/ωP for every r ∈ [p], and let τ ν := minr∈[p] τrν . Then G(Z

ν+1

  p
X τν 1 )−G ≤ 1− G(Z ν ) − G⋆ − ∥Zrν+1 − Zrν ∥2 ν 2κP 8L r τr r=1 ⋆

+

p X r=1

Proof Split

(26)

2/µr + 1/Lr ν+1 − Z̄rν+1 ∥2 . τrν ∥Ẑr 4

Pp

ν ν r=1 τr ∆r (Z ) in (24) into two halves. By Assumption 4, p

1X ν τν τr ∆r (Z ν ) ≥ G(Z ν ) − G⋆ . 2 r=1 2κP Since Z ν − Zrν + Z̄rν+1 minimizes G over Z ν + Ur , 1/Lr -strong convexity on this slice gives ∆r (Z ν ) ≥

1 1 1 ∥Z̄rν+1 − Zrν ∥2 ≥ ∥Ẑrν+1 − Zrν ∥2 − ∥Ẑrν+1 − Z̄rν+1 ∥2 . 2Lr 4Lr 2Lr

Multiplying the last bound by τrν /2, using Zrν+1 − Zrν = τrν (Ẑrν+1 − Zrν ), and substituting both estimates into Lemma 1 gives (26). ⊓ ⊔ Tree-cluster mismatch estimate. Lemma 2 leaves the delayed mismatch ∥Ẑrν+1 − Z̄rν+1 ∥2 to control. By Proposition 5, it is driven by delayed boundaryedge variables and can therefore be bounded by recent increments ∥Yhℓ+1 − Yhℓ ∥

20

Kuangyu Ding, Gesualdo Scutari

from the neighboring blocks containing those edges. For block r, define the exterior edge set and the neighboring-block set by [ ∂ ∂r := Ai , Mr := {s ∈ [p] \ {r} : Es ∩ ∂r ̸= ∅}, i∈Vr

write Jr := |∂r |, and set Dr := maxe∈Er , i∈Vr∂ δe,i if ∂r ̸= ∅, and Dr := 0 otherwise. Then Dr ≤ diam(Tr ) − 1. To index the boundary values, define ∂br := {(i, h) : i ∈ Vr∂ , h ∈ A∂i },

Jbr := |∂br |.

b For a boundary value b ∈ RJr ×d with rows indexed by ∂br , define the solution mapping   X ∗ X Yr (b) ∈ argmin fi Bi,A◦i YA◦i + Bi,h bi,h  , (27) YEr

i∈Vr

h∈A∂ i

and define Yr,e (b) := (Yr (b))e ,

Zr,v (b) := BVr ,Er Yr (b) v ,

e ∈ Er , v ∈ Vr .

The mismatch estimate compares the two minimizers by changing the boundary argument of Yr (·). For ν ≥ maxr∈[p] diam(Tr ), let (bνr )(i,h) := Yhν and (bbνr,e )(i,h) := ν−δe,i Y for (i, h) ∈ ∂br . Then Ȳ ν+1 = Yr (bνr ), Ŷeν+1 = Yr,e (bbνr,e ), where Ȳ ν+1 h

Er

Er

is the non-delayed block minimizer and Ŷeν+1 is the delayed edge minimizer in Proposition 5. For e ∈ Er , extend Ve (i) in (12) from i ∈ Ie to i ∈ Vr by taking the vertex set of the component of Tr \ {e} containing i, and set V e (i) := Vr \ Ve (i). We now quantify how a boundary perturbation propagates through the solution mapping Yr (·). For T : Rd → Rd , write Lip(T ) := supη̸=η′ ∥T (η) − T (η ′ )∥/∥η − η ′ ∥ for its global Lipschitz modulus. Let !−1 X χr (η) := ∇fi (η), i∈Vr

P

where χr is well defined because i∈Vr ∇fi is strongly monotone. For nonempty S ⊆ Vr , set X Lr,S (η) := ∇fi (χr (η)). i∈S

Consider the following family of vertex subsets:   Rr := {v} : (i, h) ∈ ∂br , v ∈ Vr \ {i} ∪ V e (i) : e ∈ Er , (i, h) ∈ ∂br . Write Nr := |Vr |. If ∂r = ∅, set κ∂,r = 0. Otherwise, let κ∂,r := max

Nr

S∈Rr |S|

Lip(Lr,S ), .

(28)

The factor Nr /|S| offsets the 1/Nr scale of χr , which comes from inverting the sum of Nr strongly monotone node maps. Hence κ∂,r can remain O(1) in the network size, and can be much smaller than local condition-number bounds. The smooth and quadratic cases below make this sharper behavior explicit.

Graph Decomposition in Decentralized Optimization via Message Passing

21

Remark on κ∂,r . The constant κ∂,r measures how boundary perturbations propagate through the tree cluster. When fi ∈ C 2 , for every η ∈ Rd , ∇Lr,S (η)⊤ =

X i∈S

X
Hi (η) HΣ (η)−1 , Hi (η) := ∇2 fi (χr (η)), HΣ (η) := Hi (η), i∈Vr

and hence, Nr κ∂,r ≤ sup max η S∈Rr |S|

! X

Hi (η) HΣ (η)−1 .

(29)

i∈S

For quadratic fi (x) = 12 x⊤ Qi x − c⊤ i x, Qi ≻ 0, i ∈ Vr , the modulus is the normalized matrix quotient constant     −1 −1    X X X Nr     . max max Q , max N Q Q r Qv  j j j e |V (i)|  (i,h)  (i,h) e j∈V e (i)

j∈Vr

j∈Vr

v̸=i

From (29), a crude bound of κ∂,r can be given in terms of the condition number of local functions, which can be much larger than the matrix quotient constant. For example, if Qi = Q for all i ∈ Vr , then the right-hand side of (29) is independent (Q) of Q, while λλmax can be arbitrarily large. min (Q) The resulting boundary sensitivity estimate is as follows. Lemma 3 Suppose Assumptions 1 and 3 hold. For every block r, the block solution mapping Yr (·) is single-valued. If two boundary vectors b, b′ differ only in coordinate (i, h), then |V e (i)| ′ ∥bi,h − bi,h ∥, Nr 1 ′ ∥Zr,v (b′ ) − Zr,v (b)∥ ≤ κ∂,r ∥bi,h − bi,h ∥, v ̸= i. Nr

∥Yr,e (b′ ) − Yr,e (b)∥ ≤ κ∂,r

(30a) (30b) ⊓ ⊔

Proof See Appendix A.2.

For s ∈ [p], the tree-block structure gives full column rank of BV,Es . For s ∈ Mr , let Br,s := Es ∩ ∂r collect the edges of block s touching block r, which contribute delayed boundary values in Proposition 5, and set Λr,s := Diag(|Ih ∩ Vr | : h ∈ Br,s ). To count each exterior increment once per boundary incidence, define  h i −1 γr,s := λmax (Λr,s )1/2 (B⊤ V,Es BV,Es )

Br,s ,Br,s

 (Λr,s )1/2 ,

Γr := max γr,s , s∈Mr

with Γr = 0 if Mr = ∅. For single-contact interfaces, Λr,s = I.

22

Kuangyu Ding, Gesualdo Scutari

Lemma 4 Under Assumptions 1 and 3, for every block r and every iteration ν ≥ maxr∈[p] diam(Tr ), ∥Ẑrν+1 − Z̄rν+1 ∥2 ≤ 4κ2∂,r Jbr Γr

ν−1 X

X

ℓ=ν−Dr s∈Mr

∥Zsℓ+1 − Zsℓ ∥2 .

(31)

The sum over ℓ is understood to be zero when Dr = 0. ⊓ ⊔

Proof See Appendix A.3.

Combining this mismatch estimate with the delayed recursion gives the main convergence theorem. Theorem 1 Suppose Assumptions 1, 3, and 4 hold, with p > 1. Define    X 1 2 A := max + κ2∂,r Jbr Γr , D := max Dr . µr Lr s∈[p] r∈[p]

(32)

r∈[p]: Dr >0, s∈Mr

Let X ⋆ = 1(x⋆ )⊤ be the consensus primal optimizer. If τrν ≡ τ and s ( ) 1 1 2κP τ ≤ min , , , ωP 2D + 1 8L(2D + 1)A

(33)

then, for some constant C ∈ (0, ∞) and all ν ≥ maxr∈[p] diam(Tr ), τ . (34) ∥X ν − X ⋆ ∥2 ≤ Cρν , ρ := 1 − 2κP Proof Lemmas 2 and 4, after regrouping delayed increments by block index, give   p
1 X ν+1 τ G(Z ν ) − G⋆ − ∥Zr − Zrν ∥2 G(Z ν+1 ) − G⋆ ≤ 1 − 2κP 8Lτ r=1 + τA

ν−1 X

p X

ℓ=ν−D r=1

∥Zrℓ+1 − Zrℓ ∥2 .

Invoking the standard delay-window inequality (e.g., [5, Lemma 5]) under (33) from this starting index yields, for some C0 > 0 depending on the finite initial history, g(Y ν ) − g ⋆ = G(Z ν ) − G⋆ ≤ C0 ρν . (35) ⋆ Let Z minimize G over S, and let X ⋆ be given by x⋆i = ∇fi∗ (Zi⋆ ), i ∈ V. Since G is 1/L-strongly convex on S, and each ∇fi∗ is 1/µ-Lipschitz, ∥X ν − X ⋆ ∥2 ≤ Absorbing constants gives (34).

2LC0 ν 1 ∥Z ν − Z ⋆ ∥2 ≤ ρ . µ2 µ2

⊓ ⊔

Remark 2 Theorem 1 gives linear convergence with a rate ρ explicit in function regularity, network topology, and the chosen partition. The works on consensusbased methods typically give rates with explicit spectral-gap dependence, which however captures only global topology rather than local structure. The stepsize restriction (33) has three components: the overlap of active node sets through 1/ωP , delay/diameter through (2D + 1)−1 , and mismatch through A. If the communication graph is a tree, take E1 = E and τ1ν ≡ 1. Then Algorithm 1 reduces to ordinary min-sum message passing on F1 and terminates in finitely many rounds.

Graph Decomposition in Decentralized Optimization via Message Passing

23

4.4 Rate discussions Theorem 1 gives a convergence rate with explicit dependence on the block errorbound constant κP , the overlap ωP , the delay diameter D, and the mismatch coefficient A. Taking the largest admissible constant stepsize gives ) ( 1 1 2κP 1 . (36) ρ=1− min , , p 2κP ωP 2D + 1 8L(2D + 1)A The discussion below examines how the graph and the chosen partition determine these quantities and, consequently, the network-size scaling of the rate. Scaling of tree-dominant graph. By (36), if κP = O(1), ωP = O(1), and A = O(D), then (1 − ρ)−1 = O(D). One typical class is tree-dominant graphs, with the partition taking the dominant tree as one block and every remaining edge as a singleton. Exact minimization over the tree block removes the large connected component, so only the O(1) singleton edges carry the remaining coupling. Thus one obtains network-size independent constants κP = O(1) and A = O(1), as made precise below with proof in Appendix A.4. Proposition 6 Consider a connected graph sequence Gm = (Vm , Em ), |Vm | = m, each containing a tree subgraph Tm = (V0,m , E0,m ). Write E 0,m := Em \ E0,m and suppose, for a fixed q, |E 0,m | ≤ q. Let S Pm := {E0,m } ∪ {{h} : h ∈ E 0,m } be the2 edge partition. Set I∂,m := h∈E 0,m Ih . Under Assumption 3, assume fi ∈ C for i ∈ I∂,m , and there are constants 0 < α∂,m ≤ α∂,m and a positive definite matrix R∂,m such that, α∂,m R∂,m ⪯ ∇2 fi (x) ⪯ α∂,m R∂,m ,

i ∈ I∂,m ,

α∂,m /α∂,m = O(1),

and assume that L and µ−1 1 are uniformly bounded, where block 1 denotes the dominant tree block. Then κPm = O(1) and A = O(1), and (1 − ρ)−1 = O(diam(Tm )). Note that diam(Tm ) ≤ m − 1 and can be much smaller than m for low-diameter dominant trees. The two examples below have diam(Tm ) = Θ(m), hence (1 − ρ)−1 = O(m): – Ring. For a ring G = (V, E) with |E| = m, choose one path block with |E1 | = m−q and q = O(1) singleton edge blocks. The Hessian bounds in Proposition 6 are required only on the O(q) nodes incident to the singleton edges, and diam(Tm ) = Θ(m − q); hence κP = O(1), A = O(1), and (1 − ρ)−1 = O(m). – Barbell. For two O(1)-node cliques connected by a Θ(m)-length path, let Tm be this path, and put all clique edges in singleton blocks. Then the off-tree edges and interface nodes are O(1), diam(Tm ) = Θ(m), and Proposition 6 yields κP = O(1), A = O(1), and (1 − ρ)−1 = O(m). Scaling of ring with equal-length partitions. For a ring partitioned into p ≥ 2 consecutive equal-length path blocks, κP admits the following estimate, proved in Appendix A.5.

24

Kuangyu Ding, Gesualdo Scutari

Proposition 7 Let Pm be an edge partition of a ring with m edges into p = m/(D + 1) ≥ 2 consecutive path blocks, each with graph diameter D + 1. Assume fi ∈ C 2 for i ∈ V, and there are constants 0 < αm ≤ αm and a positive definite matrix Rm such that αm Rm ⪯ ∇2 fi (x) ⪯ αm Rm ,

i ∈ V,

αm /αm = O(1).
Then the block error bound (20) holds with κPm = O m2 /D . By Proposition 7, (32), and ωP = 2, (36) gives    2 m2 m , D, √ . (1 − ρ)−1 = O max D D Substituting D = Θ(mγ ), γ ∈ [0, 1], into the bound above shows that γ = 1 minimizes this upper bound, and hence D = Θ(m) and (1 − ρ)−1 = O(m3/2 ), whereas Proposition 6 gives the sharper O(m) bound for the long-path partition. 5 Surrogate enhancement In this section, we introduce a surrogate variant of GATE to reduce per-iteration computational and communication costs. The updates in (17a) and (18) of Algorithm 1 require solving local minimization problems exactly, and each intra-cluster message µνi→e (·) is a function of the receiving edge variable Ye , which can be expensive to compute and transmit. This is particularly acute in the nonquadratic case, where messages need not admit compact finite-dimensional parametrizations; even in the quadratic case, exact messages may carry dense matrix parameters. Our approach is to replace each gi (YAi ) = fi∗ ((BY )i ) by a tractable surrogate: this makes the block subproblems cheaper to solve and induces messages with lightweight parametrizations. More formally, for each node i ∈ V, let gei : R|Ai |d × R|Ai |d → R, (YAi , ȲAi ) 7→ gei (YAi ; ȲAi ), be a surrogate of gi (YAi ) = fi∗ (Bi,Ai YAi ). While we can directly work on the general gei , we mainly focus on a structured choice obtained from a surrogate of the local conjugate fi∗ : choose fei∗ : Rd × Rd → R, (Ui , Zi ) 7→ fei∗ (Ui ; Zi ), and set gei (YAi ; ȲAi ) := fei∗ (Bi,Ai YAi ; Bi,Ai ȲAi ),

(37)

where Bi,Ai only gives the composition with the edge variables YAi and their center ȲAi ; fei∗ is chosen from the local conjugate fi∗ alone and is graph-independent. At iteration ν, write Z ν := BY ν and Ziν := (Z ν )i . Replacing the exact local terms in the edge-variable update (17a) and the message update (18) by these surrogates gives Algorithm 2. When fei∗ (U ; Z) ≡ fi∗ (U ), Algorithm 1 is recovered. 5.1 Surrogate regularity conditions We impose the mild regularity conditions on the local surrogates to guarantee the convergence of Algorithm 2. Assumption 5 For each node i ∈ V, the local surrogate fei∗ is differentiable and satisfies the following conditions:

Graph Decomposition in Decentralized Optimization via Message Passing

25

Algorithm 2: GATE-S: Graph-Tearing message passing with surrogates p Input: Edge assignment a with ownership sets {Aa i }i∈V ; edge partition {Er }r=1 ; initial edge variables Y 0 ; finite-valued strongly convex initial messages µ e0i→e , e ∈ E, i ∈ Ie ; local surrogates fei∗ (·; ·); relaxation parameters τrν ∈ [0, 1]; N ≥ 1. for ν = 0, 1, . . . , N − 1 do Each node i ∈ V executes the following steps, in parallel with the other nodes:

(1) Assigned edge-variable update. foreach r ∈ [p] and e ∈ Aa i ∩ Er , compute ν+1

Ŷe

ν+1

Ye

∈ argmin

 X

ye ∈R1×d j∈I ν

ν

e

  ν µ ej→e (ye ) , 

ν+1

= Ye + τr Ŷe

(38a)

ν
− Ye .

(38b)

Send Yeν+1 to the other endpoint of e. (2) Node-to-edge message update. foreach r ∈ [p] and e ∈ Ai ∩ Er , compute (   ν+1 ∗ ν+1 ν+1 µ ei→e (ye ) = min fei Bi,e ye + Bi,A◦i \{e} YA◦i \{e} + Bi,A∂i YA∂ ; Bi,Ai YAi YA◦ \{e}

i

i

(39)

) X

+

ν

X

µ ej→h (Yh ) .

h∈A◦ \{e} j∈Ih \{i} i

Send µ eν+1 i→e

to the other endpoint of e.

∗ N Primal recovery. Each node i ∈ V computes xN )i ). i := ∇fi ((BY

(i) (touching and gradient consistency). For all Zi ∈ Rd , fei∗ (Zi ; Zi ) = fi∗ (Zi ),

∇U fei∗ (Zi ; Zi ) = ∇fi∗ (Zi ).

(ii) (majorization). For all Ui , Zi ∈ Rd , fi∗ (Ui ) ≤ fei∗ (Ui ; Zi ). e ∗i ∈ (iii) (strong convexity and smoothness in Ui ). There exist constants µ e∗i , L ∗ ∗ (0, +∞) such that, for every center Zi , the map Ui 7→ fei (Ui ; Zi ) is µ ei -strongly ∗ e convex and Li -smooth. e ∗i . For a center Z ∈ S, e ∗r := maxi∈V L e∗i , L For each block r, define µ e∗r := mini∈Vr µ r er (Z) denote the unique minimizer let O X ∗ er (Z) = argmin G(U e ; Z) := O fei (Ui ; Zi ), U ∈Z+Ur

i∈V

and define the corresponding surrogate block progress er (Z) := G(Z) − ∆

min

U ∈Z+Ur

e ; Z) = G(Z) − G( e O er (Z); Z) ≥ 0. G(U

(40)

As a counterpart of the exact block error bound in Assumption 4, we impose the er . following surrogate variant, where the exact block progress ∆r is replaced by ∆ Assumption 6 There exists κ eP < ∞ such that, with G⋆ := minU ∈S G(U ), G(Z) − G⋆ ≤ κ eP

p X r=1

er (Z), ∆

Z ∈ S.

(41)

26

Kuangyu Ding, Gesualdo Scutari

Equivalently, the same condition can be written in edge variables. For Y , set er (BY ). δer (Y ) := ∆ Hence, with g ⋆ = G⋆ , Assumption 6 is equivalently g(Y ) − g ⋆ ≤ κ eP

p X r=1

δer (Y ),

Y ∈ R|E|×d .

As in the exact case, we take κ eP to be the smallest admissible constant, namely κ eP :=

G(Z) − G⋆ . Pp e Z∈S: G(Z)>G⋆ r=1 ∆r (Z) sup

(42)

This constant enters the rate of Algorithm 2; it plays for the surrogate method a similar role as κP for Algorithm 1, and as a condition number in classical first-order methods. The explicit surrogate rate is given later in Theorem 2. By touching, optimality, and majorization, er (Z) ≤ G(Z) − G(O er (Z)) ≤ ∆r (Z). 0≤∆ Consequently, κP ≤ κ eP whenever both constants are finite. If there exists η ∈ (0, 1] such that er (Z) ≥ η ∆r (Z), ∀Z ∈ S, r ∈ [p], ∆ then κ eP ≤ κP /η. Thus, the price of using surrogate block updates is captured by this relative progress fraction: if η remains bounded away from zero, the networksize scaling of the exact block error bound is preserved up to a constant factor.

5.2 Surrogate examples The following are two practical choices of fei∗ satisfying Assumption 5: a first-order surrogate with fixed metric, and a second-order surrogate that uses second-order information and allows the preconditioner to vary with the center. Example 2 (First-order surrogate) For a fixed Mi ∈ Sd++ , set 1 fei∗ (Ui ; Zi ) := fi∗ (Zi ) + ∇fi∗ (Zi ), Ui − Zi + ⟨Ui − Zi , Mi (Ui − Zi )⟩ . 2

(43)

A special case is the scalar metric: Mi = αi−1 Id , with αi > 0. Example 3 (Second-order surrogate) Let Hi (Zi ) ∈ Sd++ be chosen from secondorder information, for instance Hi (Zi ) = ∇2 fi∗ (Zi ) + ζi Id with ζi ≥ 0, and define 1 fei∗ (Ui ; Zi ) := fi∗ (Zi ) + ∇fi∗ (Zi ), Ui − Zi + ⟨Ui − Zi , Hi (Zi )(Ui − Zi )⟩ . 2

Graph Decomposition in Decentralized Optimization via Message Passing

27

5.2.1 Regularity and block error bound comparison Surrogate regularity. Let Hi (Zi ) denote the quadratic metric in the surrogate, with Hi (Zi ) ≡ Mi in Example 2 and center-dependent Hi in Example 3. Touching and gradient consistency are immediate. Majorization holds whenever the chosen quadratic metric Hi (Zi ) majorizes the curvature of fi∗ on the relevant region. Assumption 5(iii) holds with µ e∗i := inf Zi ∈Rd λmin (Hi (Zi )) and ∗ ∗ e e ∗i < ∞. Li := supZi ∈Rd λmax (Hi (Zi )) whenever 0 < µ ei ≤ L Block error bound comparison. Given a partition P, we next compare κ eP in (42) with the exact constant κP for the fixed-metric surrogate in Example 2. Fix r and write a block variation as U = Z + P with P ∈ Ur . By (40) and the change of er (Z) = G(Z)−minP ∈U G(Z e +P ; Z). For i ∈ variables U = Z +P , ∆ / Vr , Bi,Er = 0, r so every P ∈ Ur satisfies Pi = 0. Hence (43) gives D E X e + P ; Z) = G(Z) + (∇G(Z)⊤ )V , PV + 1 ⟨Pi , Mi Pi ⟩ . G(Z r r 2 i∈Vr

Substituting this identity into the definition gives

er (Z) = − min ∆

( D

P ∈Ur

⊤

(∇G(Z) )Vr , PVr

E

) 1 X ⟨Pi , Mi Pi ⟩ , + 2

(44)

i∈Vr

If the fixed metrics on Vr satisfy the curvature sandwich 2 ∗ ρ−1 i Mi ⪯ ∇ fi (z) ⪯ Mi ,

∀z ∈ Rd ,

i ∈ Vr ,

(45)

with ρi ≥ 1 and ρr := maxi∈Vr ρi , then the lower curvature bound in (45) implies ∆r (Z) ≤ − min

( D

P ∈Ur

(∇G(Z) )Vr , PVr

" = ρr − min

⊤

Q∈Ur

( D

⊤

E

1 X + ⟨Pi , Mi Pi ⟩ 2ρr

(∇G(Z) )Vr , QVr

)

i∈Vr

E

1 X ⟨Qi , Mi Qi ⟩ + 2

)#

i∈Vr

er (Z), = ρr ∆ where the equality uses P = ρr Q, the linearity of Ur , and (44). Hence κP ≤ κ eP ≤ ρmax κP ,

ρmax := max ρr . r∈[p]

Note that ρmax is independent of graph and partition. Hence κ eP and κP have the same network scaling. If the surrogate Hessian Mi matches ∇2 fi∗ well (i.e., ρi ≈ 1), the resulting degradation from κP to κ eP is only a small factor. In the scalar case, choosing Mi = µ−1 I ensures (45) with ρi = Lfi /µfi , thereby retaining fi d the network scaling of the block error bound up to a local condition number.

28

Kuangyu Ding, Gesualdo Scutari

5.2.2 Quadratic message implementation The surrogates in Examples 2 and 3 are quadratic in Ui . Therefore, under the updates in Algorithm 2, the messages remain quadratic and can be encoded by a vector and a Hessian matrix. Concretely, each message can be written as µ eνi→e (Ye ) ∼

1 ν ν ⟨Ye , Hi→e Ye ⟩ + ⟨Pi→e , Ye ⟩ , 2

ν Hi→e ∈ Sd+ ,

ν Pi→e ∈ Rd .

(46)

For h, h′ ∈ Ai , ∇2Yh Yh′ gei = Bi,h Bi,h′ Mi in Example 2, and ∇2Yh Yh′ gei = Bi,h Bi,h′ Hi (Ziν ) in Example 3. These Hessians can be dense, and so can the mesν sage Hessians Hi→e . Stabilization of message Hessians. In Example 2, the Hessian recursion does not depend on the surrogate centers. On the tree cluster, it is time-independent and stabilizes after finitely many sweeps. After this stabilization phase, the Hessian matrices no longer need to be transmitted; subsequent iterations update and send ν only the vectors Pi→e . Scalar-metric messages. The scalar metric even avoids matrix-valued Hessian communication entirely. Take Mi = αi−1 Id , with αi > 0, then ∇2Yh Yh′ gei = αi−1 Bi,h Bi,h′ Id , and Schur complements preserve this isotropic form. Therefore every message has the scalar-quadratic form µ eνi→e (Ye ) ∼

hνi→e ν ∥Ye ∥2 + ⟨Pi→e , Ye ⟩ , 2

hνi→e ∈ R+ ,

ν Pi→e ∈ Rd .

Only one scalar Hessian coefficient and one d-vector are needed to transmit. Slice-wise Hessian communication. The communication bottleneck is dense ν Hessian transmission. In both Examples 2 and 3, Hi→e in (46) can be a full d × d matrix. In Example 2, full-matrix transmission is confined to a finite Hessianstabilization phase. In contrast, Example 3 has no such finite stabilization guarantee: Hi (Ziν ) varies with the center, so the message Hessians can remain dense and time-varying. To avoid this repeated full-matrix transmission in practice, we propose the following slice-wise Hessian communication strategy, in which only a slice of the Hessian is sent at each round. ν Using the quadratic message representation (46), the vector Pi→e is sent every ν round, while the receiving node maintains a Hessian cache H . Decompose Sd i→e LK d as the direct sum S = k=1 Sk , where each Sk is chosen to admit a low-cost parametrization for communication and Πk denotes the projection onto Sk . Examples include diagonal bands, matrix rows or columns, and low-rank subspaces. When node i computes µ eν+1 eνj→h in the local i→e by (39), each incoming message µ ν minimization is evaluated with the current vector Pj→h and the cached Hessian ν+1 Hνj→h . After this minimization, node i has computed the full Hessian Hi→e of ν+1 µ ei→e , but sends only the slice indexed by s(ν) ∈ [K]. The receiving node then updates only that slice of its cache: ν+1 Πs(ν) Hν+1 i→e = Πs(ν) Hi→e ,

ν Πk Hν+1 i→e = Πk Hi→e

(k ̸= s(ν)).

Thus each round sends one slice of each dense message Hessian, while the receiving node keeps the remaining slices from its Hessian cache. For the fixed-metric surrogate (43), if the updates are well defined and each slice is used at least once

Graph Decomposition in Decentralized Optimization via Message Passing

29

in every S consecutive rounds, all Hessian caches in cluster r equal the stabilized message Hessians after at most    diam(Fr ) S +1 2 rounds. Note that the cached Hessians may be indefinite. In practice, if necessary, we can add δId to each cache with δ > 0 chosen to keep the local subproblem well defined. 5.3 Convergence analysis We now establish the convergence of Algorithm 2. As in the tree-cluster mismatch estimate in Section 4.3, we control the surrogate mismatch by perturbing the solution map defined later in its boundary vector and surrogate centers. Fix a block r. For e ∈ Er , extend the delays in (22) to all i ∈ Vr by δe,i :=

distFr (e, i) − 1 , 2

e ∈ Er ,

i ∈ Vr ,

(47)

e r := maxe∈E , i∈V δe,i , and D e := maxr∈[p] D e r . For a boundary value b and D r r centers ϑ = (ϑi )i∈Vr , define   X ∗ X fei Bi,A◦i YA◦i + Bi,h bi,h ; ϑi  . Yer (b, ϑ) ∈ argmin YEr

i∈Vr

h∈A∂ i

Set e r,e (b, ϑ) := [Yer (b, ϑ)]e , Y

e r,v (b, ϑ) := (BV ,E Yer (b, ϑ))v . Z r r

b At iteration ν, define bνr ∈ RJr ×d by (bνr )(i,h) := Yhν for (i, h) ∈ ∂br , and let ZVν r ν denote the restriction of Z = BY ν to Vr . For e ∈ Er and ν ≥ maxr∈[p] diam(Tr ), let ν−δ ν−δ ν := (Zi e,i )i∈Vr . (bνr,e )(i,h) := Yh e,i ((i, h) ∈ ∂br ), Zr,e

Set the nondelayed image block and write the edge updates generated by Algorithm 2 as ν Z̄rν+1 := BV,Er Yer (bνr , ZVν r ), Ŷeν+1 := [Yer (bνr,e , Zr,e )]e , Ẑrν+1 := BV,Er ŶEν+1 . r

We now introduce the frozen-center counterparts of κ∂,r . For fixed centers ϑ, let χ er (·; ϑ) be defined by X
−1 (χ er (η; ϑ)) = η, ∇u fei∗ (·; ϑi ) i∈Vr

where χ er (·; ϑ) is well defined by strong monotonicity. For nonempty S ⊆ Vr , set X
−1 Ler,S (η; ϑ) := ∇u fei∗ (·; ϑi ) (χ er (η; ϑ)). (48) i∈S

The relevant boundary subsets are   Rr := {v} : (i, h) ∈ ∂br , v ∈ Vr \ {i} ∪ V e (i) : e ∈ Er , (i, h) ∈ ∂br .

30

Kuangyu Ding, Gesualdo Scutari

If ∂r = ∅, set κ e∂,r = 0. Otherwise, let κ e∂,r :=

sup

max

Nr

ϑ∈RNr ×d S∈Rr |S|

Lip Ler,S (·; ϑ) .

(49)

As in (28), the factor Nr /|S| in (49) offsets the 1/Nr scale that comes from inverting the sum of Nr strongly monotone frozen surrogate node maps. Hence κ e∂,r can remain O(1) in the network size. For a map F (η; ϑ), let Lipϑi F (η; ϑ) denote its Lipschitz modulus in the i-th center coordinate of ϑ, with η and the other center coordinates fixed. Define the normalized center-coordinate modulus 
Nr Lipϑi Ler,V e (i) (η; ϑ) , κ ec,r := sup max max max e∈Er |V e (i)| d Nr ×d i∈Vr η∈R , ϑ∈R  (50)

e e Lipϑi Lr,{i} (η; ϑ) , max Nr Lipϑi Lr,{v} (η; ϑ) . v∈Vr \{i}

As with κP and κ eP , we assume κ ec,r < ∞ for every r ∈ [p]. The modulus κ ec,r measures the center sensitivity of the aggregate maps and can reflect the surrogate approximation quality. It vanishes for the exact surrogate fei∗ (Ui ; Zi ) = fi∗ (Ui ). A more detailed interpretation is given in Appendix B.1. The resulting surrogate sensitivity estimate is as follows. Lemma 5 Suppose Assumptions 3 and 5 hold. For every block r, the frozen surrogate tree oracle Yer (·, ·) is single-valued. If two boundary vectors b, b′ differ only in coordinate (i, h), then, for any center ϑ, |V e (i)| ′ e r,e (b′ , ϑ) − Y e r,e (b, ϑ)∥ ≤ κ ∥bi,h − bi,h ∥, ∥Y e∂,r Nr 1 ′ e r,v (b′ , ϑ) − Z e r,v (b, ϑ)∥ ≤ κ ∥Z e∂,r ∥bi,h − bi,h ∥, v ̸= i. Nr

(51a) (51b)

If two centers ϑ, ϑb differ only in coordinate i, then, for any boundary vector b, |V e (i)| b e r,e (b, ϑ) b −Y e r,e (b, ϑ)∥ ≤ κ ∥ϑi − ϑi ∥, ∥Y ec,r Nr e r,i (b, ϑ) b −Z e r,i (b, ϑ)∥ ≤ κ ∥Z ec,r ∥ϑbi − ϑi ∥, e r,v (b, ϑ) b −Z e r,v (b, ϑ)∥ ≤ ∥Z

κ ec,r b ∥ϑi − ϑi ∥, Nr

v ̸= i.

Proof See Appendix B.1.

(52a) (52b) (52c) ⊓ ⊔

As in Lemma 4, these sensitivity bounds yield the following image-space mismatch estimate for the surrogate update. Lemma 6 Under Assumptions 3 and 5, for each block r, define   fr,∂ := Γr 8e e r )e M κ2∂,r Jbr + 8Jr (Nr + D κ2c,r , fr,c := 8(Nr + D e r )e M κ2c,r .

Graph Decomposition in Decentralized Optimization via Message Passing

31

Then, for every iteration ν ≥ maxr∈[p] diam(Tr ), fr,∂ ∥Ẑrν+1 − Z̄rν+1 ∥2 ≤ M

ν−1 X

X

e r s∈Mr ℓ=ν−D

fr,c ∥Zsℓ+1 − Zsℓ ∥2 + M

ν−1 X er ℓ=ν−D

∥Zrℓ+1 − Zrℓ ∥2 . (53)

e r = 0. The sums over ℓ are understood to be zero when D ⊓ ⊔

Proof See Appendix B.2. Using this mismatch estimate, we obtain the following convergence theorem.

Theorem 2 Suppose Assumptions 1, 3, 5, and 6 hold, with p > 1. Define µ e∗ := ∗ minr∈[p] µ er and   ∗ ∗ ∗ X e e ∗r + µ 2 L + µ e 2 L e s s f  r f e := max  A Mr,∂ + 1{D Ms,c . (54) e s >0} 4 4 s∈[p] e r >0, s∈Mr r∈[p]: D

Let X ⋆ = 1(x⋆ )⊤ be the consensus primal optimizer. If τrν ≡ τ and s ) ( µ e∗ 1 2e κP , τ ≤ min , , e +1 e + 1)A e ω P 2D 8(2D

(55)

then, for some constant C ∈ (0, ∞) and all ν ≥ maxr∈[p] diam(Tr ), ∥X ν − X ⋆ ∥2 ≤ C ρeν ,

ρe := 1 −

Proof See Appendix B.3.

τ . 2e κP

(56) ⊓ ⊔

Remark 3 Theorem 2 parallels Theorem 1: Algorithm 2 converges linearly, with contraction factor ρe now given by (56). Relative to the exact case (Theorem 1), the stepsize restriction (55) retains the same three-way structure as (33): the overlap of e +1)−1 , and mismatch active node sets through 1/ωP , delay/diameter through (2D e through A. The main differences are that the exact constants (1/Lr , 1/µr , A) are e and that κP is replaced by κ e ∗r , A), eP , which may be larger when replaced by (e µ∗r , L the surrogate captures less exact block progress. The resulting deviation from the exact constants is the rate price for cheaper local computation and communication. 5.4 Comparison with consensus-based methods We now compare the convergence rate of Algorithm 2 with those of consensusbased methods, such as DGD [24], EXTRA [19], and SONATA [20], in terms of network-size scaling. We show that, for a class of tree-dominant graphs, sufficiently accurate surrogates yield an acceleration in network-size scaling relative to these consensus baselines; moreover, for general graphs, their spectral-gap scaling can be recovered by a proximal-linear surrogate. Acceleration in tree-dominant graphs. For tree-dominant graph families equipped with a partition P that has a dominant tree block and only O(1) remaining singleton edge blocks, the analysis in Section 4.4 gives κP = O(1), A = O(1).

32

Kuangyu Ding, Gesualdo Scutari

Theorem 1 then yields (1 − ρ)−1 = O(D). For the ring and barbell examples, the exact rate scaling is O(m). In contrast, consensus baselines have O(m2 ) rate scaling ⊤ on these graphs through the inverse spectral-gap factor 1/λ+ min (BB ). The exact O(m) rate scaling therefore gives network-size acceleration over those baselines. The constant κ eP preserves the network-size scaling of κP whenever the surrogate block progress captures the exact block progress up to a constant fraction. Indeed, if, for some network-independent η ∈ (0, 1], δer (Y ) ≥ η δr (Y ) holds for all r ∈ [p], then κP ≤ κ eP ≤ κP /η. For example, once a quadratic surrogate satisfies the Hessian sandwich inequality (45), it gives κ eP ≤ ρmax κP with network-independent ρmax . Consequently, for the tree-dominant families and pare titions above, κ ep P = O(1) and Lemma 6 gives A = O(m). then Theorem 2 gives e by Theorem 2, with D e = diam(Tm ) − 1. This matches the (1 − ρe)−1 = O( mD) e = Θ(m). exact method’s O(m) scaling for the ring and barbell examples, where D Consensus scaling recovery. On general graphs, the consensus scaling is recovered by choosing a direct proximal-linear surrogate for gi (YAi ) = fi∗ (Bi,Ai YAi ), outside the structured subclass (37). Specifically, for sufficiently large ci,e > 0, set X 1 X ci,e ∥Ye − Yeν ∥2 . gei (YAi ; YAνi ) := gi (YAνi ) + ⟨∇Ye gi (YAνi ), Ye − Yeν ⟩ + 2 e∈Ai

e∈Ai

(57) Since (57) is separable in {Ye : e ∈ Ai }, the message update satisfies D E c i,e ∗ ν+1 µ eν+1 )i ), Ye − Yeν+1 + ∥Ye − Yeν+1 ∥2 . i→e (Ye ) ∼ Bi,e ∇fi ((BY 2 For ν ≥ 1 and e ∈ Er with Ie = {i, j}, the edge update is the dual-gradient step ∗

ν

∗

ν

Bi,e ∇fi (Zi ) + Bj,e ∇fj (Zj ) Ybeν+1 = Yeν − , ci,e + cj,e followed by Yeν+1 = Yeν + τrν (Ybeν+1 − Yeν ). The associated surrogate block progress is X ∥∇Y g(Y )∥2 e , ∇Ye g(Y ) = Bi,e ∇fi∗ ((BY )i ) + Bj,e ∇fj∗ ((BY )j ). δer (Y ) = 2(ci,e + cj,e ) e∈Er

Consequently, the corresponding block error bound constant is κ eP =

sup

g(Y ) − g ⋆

, 1 P −1 ∥∇ g(Y )∥2 Ye g(Y )>g ⋆ 2 e∈E (ci,e + cj,e )

and is independent of the partition P. Since ∇g(Y )⊤ = B⊤ ∇G(BY )⊤ , strong convexity and smoothness of G on S give g(Y ) − g ⋆ ≤

L ∥∇g(Y )∥2 . + 2λmin (BB⊤ )

If L and the coefficients ci,e + cj,e are bounded independently of network size, then   1 κ eP = O , (58) ⊤ λ+ min (BB ) where λ+ min is the smallest positive eigenvalue. Thus, on general graphs, this sur⊤ rogate recovers the usual consensus spectral-gap rate scaling O(1/λ+ min (BB )), matching classical consensus-based methods.

Graph Decomposition in Decentralized Optimization via Message Passing

33

6 Numerical experiments In this section, we evaluate GATE and its surrogate variants on strongly convex quadratic and regularized logistic regression problems over various graphs, with and without a dominant tree structure. The quadratic instances have the form 1 ⊤ x Hi x + qi⊤ x, 2

fi (x) =

Hi ≻ 0.

The non-quadratic instances have the form Ni    1 1 X log 1 + exp −bij a⊤ + x⊤ Ri x − h⊤ ij x i x, Ni 2

fi (x) =

j=1

Ri ≻ 0.

Performance is measured by the primal error X ν − 1(x⋆ )⊤ . 6.1 Scaling verification and partition effects In this part, we verify the scaling with network size and dominant-tree diameter and examine the effect of the partition. Network-size scaling on rings. We first verify network-size scaling for quadratic problems on ring networks with d = 20. Each Hi is generated as a random symmetric Gaussian matrix with a positive diagonal correction chosen so that κ(Hi ) = 2. The edge partition consists of one (m−2)-edge path cluster and two singleton-edge clusters. GATE-S1 uses the fixed diagonal metric Mi = Diag(Hi−1 ) + δId , with δ tuned. Figure 4(a) shows that GATE and GATE-S1 are faster than EXTRA and SONATA, with the gap widening as m grows. Figure 4(b) indicates linear scaling for the GATE variants and quadratic scaling for the consensus baselines, which is consistent with the theoretical comparison in Section 5.4. #10

5

10 GATE GATE-S1 EXTRA SONATA O(m)

2.5

Iterations to reach kX 8 ! 1(x? )> k < 10!4

Iterations to reach kX 8 ! 1(x? )> k < 10!4

3

2

O(m )

2

1500

1000

1.5

500

0

50

100

150

200

250

300

350

400

1

0.5

0

5 20 40

80

120

160

200

300

Number of agents m

(a) Iteration-count.

400

6

10

5

10

4

10

3

10

2

10

1

GATE GATE-S1 EXTRA SONATA O(m) O(m2)

5

10

20

40

80

160

400

Number of agents m

(b) Iteration-count (log–log).

(c) Graph and partition.

Fig. 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 ν − 1(x⋆ )⊤ ∥ < 10−4 . To test whether the scaling observed above persists beyond the quadratic setting, we next consider the non-quadratic logistic regression problem, for which

34

Kuangyu Ding, Gesualdo Scutari

neither GATE surrogate is exact. We use d = 10, Ni = 40, and the same partition as in the quadratic experiment. The Hessian condition number is set to five. The quadratic-surrogate metrics are ∇2 fi∗ (Ziν ) + δId for GATE-S2 and Diag(∇2 fi∗ (Ziν )) + δId for GATE-S1, with δ tuned separately for each method. Figure 5(a) shows that GATE-S1 and GATE-S2 remain faster than EXTRA and SONATA, with the gap widening as m grows. Figure 5(b) indicates near-linear scaling for the GATE surrogates, whereas the consensus baselines approach quadratic scaling over the upper range. #10

4

2

O(m )

5

4

3

10

GATE-S2 GATE-S1 EXTRA SONATA O(m)

6

Iterations to reach kX 8 ! 1(x? )> k < 10!4

Iterations to reach kX 8 ! 1(x? )> k < 10!4

7

1000 800 600 400 200 0 0

50

100

150

200

2

1

0

510 20

40

60

80

100

150

Number of agents m

(a) Iteration-count.

200

5

10

4

10

3

10

2

10

1

GATE-S2 GATE-S1 EXTRA SONATA O(m) O(m2)

5

10

20

40

60

80 100

150

200

Number of agents m

(b) Iteration-count (log–log).

(c) Graph and partition.

Fig. 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 ν − 1(x⋆ )⊤ ∥ < 10−4 .

Dependence on the dominant-tree diameter. We next study the dependence of the convergence rate on the diameter D for a quadratic problem over a nonring graph. The graph consists of two three-node cliques connected by a growing non-path tree, with the partition containing one dominant tree cluster and six singleton-edge clusters. We set Hi = H0 ∈ S5++ for all i, where H0 is dense and κ(H0 ) P = 2. For GATE-S1, we use a diagonal metric with entries (Mi )kk = (H0−1 )kk + ℓ̸=k |(H0−1 )kℓ |, so Mi ⪰ H0−1 . √ With m fixed, Figure 6(b) indicates the O(D) and O( Dm) rate scalings for GATE and GATE-S1, respectively, consistent with Theorems 1 and 2. Figure 6(a) √ then considers D = Θ( m) as m varies and exhibits the corresponding m1/2 and m3/4 scalings for GATE and GATE-S1, respectively, further confirming the theoretical scaling. Effect of the partition. We next examine the effect of the partition for a quadratic problem on a ring. For each network size, we compare three partitions: P1 contains one (m − 2)-edge path and two singleton-edge clusters; P2 arranges √ √ two paths of length (m/2 − 1); and P3 contains m consecutive path blocks of m edges each. Figure 7 shows that P1 and P2 substantially outperform P3, while P1 is modestly faster than P2. This ordering is consistent with the discussion following Proposition 7: D = Θ(m) minimizes the rate bound for equal-length partitions of the ring, whereas Proposition 6 gives the sharper O(m) rate for the long-path partition.

GATE GATE-S1 O(m1/2) O(m3/4)

Iterations to reach X 1(x ) < 10 4

Iterations to reach X 1(x ) < 10 4

Graph Decomposition in Decentralized Optimization via Message Passing

102

20

40

80

160

320

640

103

35

GATE GATE-S1 O(D) O(m1/2D 1/2)

102 60

100

200

400

Dominant-tree diameter, D

Number of agents, m

(a) Scaling in m.

(b) Scaling with m fixed.

(c) Graph and partition.

Iterations to reach kX 8 ! 1(x? )> k < 10!4

Fig. 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 = Θ( m). Panel (b) reports the iteration counts versus the dominant-tree diameter D at fixed m = 406. Panel (c) shows the graph and edge partition. The stopping criterion is ∥X ν − 1(x⋆ )⊤ ∥ < 10−4 . P1 P2 P3

103

(b) P1: one path and two singleton edges.

102

(c) P2: two paths.

16

36

64

100

144

196 256

400

Number of agents, m (a) Iteration-count comparison across partitions.

(d) P3:

√

m paths.

Fig. 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 ν − 1(x⋆ )⊤ ∥ < 10−4 . 6.2 Performance comparison In this part, we compare the algorithms in terms of iteration count and cumulative communication on tree-dominant barbell networks and a multi-cycle network. Communication is measured by the total number of scalars transmitted over directed links, normalized by d. Tree-dominant barbell networks. We consider barbell graphs formed by two fournode cliques connected by a path of L ∈ {10, 100} edges. The partition contains one dominant tree cluster formed by the path and a three-edge star centered at the

36

Kuangyu Ding, Gesualdo Scutari

path endpoint in each clique, while each of the six remaining clique edges forms a singleton-edge cluster. For the quadratic problems, we set d = 100 and use dense Hi generated from Gaussian Gram matrices with a diagonal correction, yielding κ(Hi ) ≈ 100. GATE uses exact quadratic messages, while GATE-S1 and GATE-S2 (cache Hessian) use a fixed diagonal metric and a slice-wise Hessian cache, respectively. Figure 8 shows that GATE is markedly faster than all other methods, reaching the target in only 31 and 114 iterations for L = 10 and L = 100, respectively. Although GATE initially transmits dense message Hessians, these matrices stabilize after finitely many rounds and only the message vectors are sent thereafter; consequently, GATE also has the lowest cumulative communication. GATE-S2 (cache Hessian) sends only message vectors and d-vector Hessian slices. Once its cache has recovered the stabilized message Hessians, its tail follows essentially the same linear rate as GATE, consistent with the finite cache-recovery property in Section 5.2.2. GATES1 is comparable to EXTRA, the fastest consensus baseline on these instances. CTA and ATC do not reach 10−6 within 105 iterations.

0

0

kX ! 1(x? )> k

10

kX ! 1(x? )> k

10

-2

-2

10

10

-4

-4

10

10

-6

-6

10

10 0

500

1000

1500

2000

2500

3000

0

Iteration

1

1.5

2

2.5

Communication (b) Communication comparison.

(a) Iteration comparison. 0

-6

-6

-2

#10

5

(c) Barbell, L = 10.

0

kX ! 1(x? )> k

10

kX ! 1(x? )> k

10

0.5

-2

10

10

-4

-4

10

"""

10

10

10 0

2000

4000

6000

8000

10000

12000

14000

Iteration (d) Iteration comparison.

0

1

2

3

4

5

Communication (e) Communication comparison.

6 #10

6

(f) Barbell, L = 100.

GATE

GATE-S2 (cache Hessian.)

CTA

DIGing

GATE-S1

EXTRA

ATC

SONATA

Fig. 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 ν − 1(x⋆ )⊤ ∥ ≤ 10−6 . We next test logistic-regression problems on the same graphs and partitions, with d = 100 and Ni = 80. GATE-S2 (exact Hessian), GATE-S1, and GATE-S2

Graph Decomposition in Decentralized Optimization via Message Passing

37

(cache Hessian) use the full center-dependent Hessian, its diagonal, and a slicewise Hessian cache, respectively. The exact-Hessian variant is included only in the iteration plots because it transmits dense Hessian matrices at every iteration. Figure 9 shows that the cache variant is second only to GATE-S2 (exact Hessian) in iteration count and requires the least communication among all other methods that reach the target. For L = 100, GATE-S2 (cache Hessian) requires about one third as much communication as either GATE-S1 or EXTRA. 10

kX ! 1(x? )> k

kX ! 1(x? )> k

2

2

10

10

0

10

-2

0

-2

10

10

-4

-4

10

10

-6

-6

10

10 0

500

1000

1500

2000

2500

3000

0

Iteration

1.5

2

2.5

10

kX ! 1(x? )> k

kX ! 1(x? )> k

-6

-6

0

10

-2

#10

5

(c) Barbell, L = 10.

2

2

10

1

Communication (b) Communication comparison.

(a) Iteration comparison. 10

0.5

0

-2

10

10

-4

"""

-4

10

10

10

10 0

500

1000

1500

2000

2500

3000

3500

Iteration (d) Iteration comparison.

4000

0

5

10

15

Communication (e) Communication comparison.

#10

5

(f) Barbell, L = 100.

GATE-S2 (exact Hessian)

GATE-S1

CTA

DIGing

GATE-S2 (cache Hessian.)

EXTRA

ATC

SONATA

Fig. 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 ν − 1(x⋆ )⊤ ∥ ≤ 10−6 .

A multi-cycle network. We next test whether the gains persist on the network in Figure 10, which contains several cycles but no pronounced long-tree structure. We consider partitions beyond Assumption 3 to assess the empirical robustness of GATE to the choice of partition. The quadratic problem uses d = 200 and dense local Hessians with condition number eight, while the logistic-regression problem uses d = 50 and Ni = 80. For the quadratic problem, we compare exact GATE, two GATE-S1 variants, and GATE-S2 (cache Hessian) against the consensus baselines. For logistic regression, we replace exact GATE with GATE-S2 (exact Hessian) and retain the remaining methods.

38

Kuangyu Ding, Gesualdo Scutari

Figure 10(a) shows that exact GATE converges fastest for the quadratic problem. GATE-S2 (cache Hessian) follows essentially the same tail rate, and Figure 10(b) shows that it requires the least communication. The scalar and diagonal GATE-S1 variants also outperform all consensus baselines in both iteration count and communication. For logistic regression, Figure 10(d) shows that GATE-S2 (exact Hessian) is fastest, followed by the cache variant; Figure 10(e) shows that the cache variant again requires the least communication among the displayed methods. The diagonal GATE-S1 variant remains faster than all consensus baselines in both measures, whereas the scalar GATE-S1 variant is less competitive on this instance. EXTRA is the strongest consensus baseline in both problems; DIGing and SONATA require more communication, while CTA and ATC do not reach the target. Thus, the practical gains observed on the barbell graphs persist on this multi-cycle network.

2

2

10

10

0

0

10

kX ! 1(x? )> k

kX ! 1(x? )> k

10

-2

-2

10

10

-4

-4

10

10

-6

-6

10

10 0

200

400

600

800

0

0.5

Iteration

(a) QP: iteration.

1.5

2

2.5

3

3.5 #10

4

(b) QP: communication.

(c) Graph and partition.

2

2

10

10

0

10

0

10

kX ! 1(x? )> k

kX ! 1(x? )> k

1

Communication

-2

-2

10

10

-4

-4

10

10

-6

-6

10

10 0

200

400

600

800

0

Iteration

0.5

1

1.5

2

2.5

3

3.5

Communication

(d) LR: iteration.

4 #10

4

(e) LR: communication.

(f) Graph and partition.

GATE

GATE-S2 (exact Hessian)

GATE-S1 (scalar)

GATE-S1

GATE-S2 (cache Hessian.)

EXTRA

CTA

ATC

DIGing

SONATA

Fig. 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 ν − 1(x⋆ )⊤ ∥ ≤ 10−6 .

Graph Decomposition in Decentralized Optimization via Message Passing

39

7 Conclusion In this work, we developed a graph-decomposition framework for the joint design of the representation, block cover, and carriers in decentralized optimization. Specializing this framework to the incidence representation and tree-structured edge blocks, we proposed GATE : a single-loop decentralized message-passing algorithm derived from the block fixed-point decomposition. For strongly convex and smooth local objectives, we established linear convergence rates with explicit dependence on the network topology and the chosen partition. For the tree-dominant graph families, the contraction factor satisfies (1 − ρ)−1 = O(D). To reduce periteration computational and communication costs, we develop GATE-S, a surrogate variant using tractable local models and lightweight message parametrizations, and established analogous linear convergence guarantees. Numerical experiments on quadratic and logistic-regression problems corroborate the theoretical scaling, demonstrate improved iteration and communication efficiency over consensus-based baselines. Future directions include extending the framework to non-strongly convex objectives and stochastic settings.

A Proofs for Section 4 A.1 Proof of Proposition 5 Fix a block r, an edge e ∈ Er , and an iteration ν ≥ maxr∈[p] diam(Tr ). Since e ∈ Er is a vertex of the factor graph Fr , root Fr at e. For every vertex v ̸= e, let pa(v) be its parent. For i ∈ Vr , let Ti be the component of Fr \ {(i, pa(i))} containing i, and denote by Vi and Ei its vertices in Vr and Er , respectively. Thus pa(i) ∈ / Ei , where Ei consists exactly of the active edge variables strictly below i. For ℓ ∈ Vr , define the rooted local factor  X ν−δ   Bℓ,h Yh e,ℓ  , Ψℓν,e (YA◦ ) := fℓ∗ Bℓ,A◦ YA◦ + 

ℓ

ℓ

ℓ

h∈A∂ ℓ

where the second term is absent when ℓ ∈ Vr◦ . Step 1: Subtree message identity. For each i ∈ Vr , set qi := (distFr (e, i) − 1)/2. Thus qi = δe,i for boundary nodes. Since qi + 1 ≤ diam(Tr ) ≤ ν, every message in the expansion has index ν − qi ≥ 1 and satisfies (18); no initial message function remains. We prove that X ν,e
ν−qi µi→pa(i) Ypa(i) = min Ψℓ (YA◦ ). YEi

(59)

ℓ

ℓ∈Vi

We prove (59) by induction on the height of Ti . Base case. If Vi = {i}, then Ei = ∅ and A◦i = {pa(i)}. Evaluating (18) with ν + 1 replaced by ν − qi gives
ν−qi µi→pa(i) Ypa(i) = Ψiν,e (YA◦ ), i

which is (59) for the base case. Inductive step. Assume now that (59) holds for all strict descendants of i. The same substitution in (18) gives (
ν−qi µi→pa(i) Ypa(i) =

min

YA◦ \{pa(i)} i

) Ψiν,e (YA◦ ) + i

X

X

h∈A◦ i \{pa(i)} j∈Ih \{i}

ν−q −1

µj→hi

(Yh ) .

(60)

40

Kuangyu Ding, Gesualdo Scutari

For each pair (h, j) in the double sum, pa(h) = i, pa(j) = h, and qj = qi + 1. The induction hypothesis therefore gives X ν,e ν−qj ν−q −1 (Ypa(j) ) = min Ψℓ (YA◦ ). µj→hi (Yh ) = µj→pa(j) YEj

ℓ

ℓ∈Vj

Since h = pa(j), the pairs (h, j) correspond one-to-one to j ∈ Vi \ {i} with pa(pa(j)) = i. The sets A◦i \ {pa(i)} and these Ej partition Ei ; hence substituting into (60), reindexing by j, and merging the minimizations gives ( ) X X ν,e
ν−qi µi→pa(i) Ypa(i) = min Ψiν,e (YA◦ ) + Ψℓ (YA◦ ) . i

YEi

Using Vi = {i} ⊔

F

ℓ

j∈Vi \{i} ℓ∈Vj pa(pa(j))=i

j∈Vi \{i} Vj , we obtain pa(pa(j))=i

X ν,e
ν−qi µi→pa(i) Ypa(i) = min Ψℓ (YA◦ ). YEi

ℓ

ℓ∈Vi

Step 2: Sum of messages at the root. Applying the identity to (17a), we can write   X  ν+1 ν Ŷe ∈ argmin µi→e (Ye ) .   Ye i∈Ie

For i ∈ Ie , one has qi = 0, so (59) applies with pa(i) = e. The sets Vi , i ∈ Ie , partition Vr , and the corresponding sets Ei partition Er \ {e}. Therefore X ν,e Ŷeν+1 ∈ argmin min Ψℓ (YA◦ ). Ye

YEr \{e}

ℓ

ℓ∈Vr

⊔ ⊓

This is exactly (21b).

A.2 Proof of Lemma 3 The next two lemmas isolate the two ingredients for Lemma 3: for each fixed boundary vector, the minimization over YEr generates a common primal variable on Tr , and the linear system BVr ,Er YEr = q admits an explicit graph-compliant solution. For the block r and b ∈ RJr ×d with rows indexed by (i, h) ∈ ∂br , define X X X ci (b) := Bi,h bi,h , ηr (b) := ci (b) = Bi,h bi,h . b

i∈Vr

h∈A∂ i

br (i,h)∈∂

Also write, for a minimizer Yr (b) in (27), X fi∗ ((BVr ,Er YEr )i + ci (b)), Ψr (YEr ; b) := i∈Vr

x̄i (b) := ∇fi∗ (BVr ,Er Yr (b))i + ci (b) ,

i ∈ Vr .

Lemma 7 Under Assumptions 1 and 3, the vectors x̄i (b), i ∈ Vr , have a common value, which depends on b only through ηr (b); write it as χr (ηr (b)). Hence x̄i (b) = χr (ηr (b)), X ∇fi (χr (ηr (b))) = ηr (b),

i ∈ Vr ,

(61a) (61b)

i∈Vr

(BVr ,Er Yr (b))i = ∇fi (χr (ηr (b))) − ci (b),

i ∈ Vr .

(61c)

Graph Decomposition in Decentralized Optimization via Message Passing

41

Proof Fix b and a minimizer Yr (b). For e = (u, v) ∈ Er , the optimality condition gives
0 = ∇Ye Ψr (Yr (b); b) = Bu,e x̄u (b) + Bv,e x̄v (b) = Bu,e x̄u (b) − x̄v (b) . Thus x̄u (b) = x̄v (b) for every e = (u, v) ∈ Er . Since Tr is connected, all x̄i (b) are equal. Because ∇fi and ∇fi∗ are inverse maps, ∇fi (x̄i (b)) = (BVr ,Er Yr (b)) Pi + ci (b) for i ∈ Vr . Summing over i ∈ Vr and using the zero column sums of BVr ,Er gives i∈Vr ∇fi (x̄i (b)) = ηr (b). Since all x̄i (b) are equal, this equation identifies their common value as χr (ηr (b)). Thus the common value depends on b only through ηr (b), and (61a)–(61b) hold. Rearranging the first identity before summation gives (61c). ⊔ ⊓

P Lemma 8 For any q = (qi )i∈Vr with qi ∈ Rd and i∈Vr qi = 0, the equation BVr ,Er YEr = q has a unique solution. If e ∈ Er and S is one of the two connected components of Tr \ {e}, P then Ye = εe,S i∈S qi for some sign εe,S ∈ {±1}. Proof Each column of BVr ,Er sums to zero. Since Tr is a tree, rank(BVr ,Er ) = |Er | = |Vr | − 1, P hence Range(BVr ,Er ) = {q ∈ R|Vr |×d : i∈Vr qi = 0}. Thus BVr ,Er YEr = q has a unique solution. Fix one component S of Tr \ {e}. Summing the rows indexed by S gives  X i∈S

qi =

X

 X

 a∈Er



Bi,a  Ya = 

i∈S

 X

Bi,e  Ye ,

i∈S

X

Bi,e ∈ {±1},

i∈S

where the terms with a ̸= e vanish because those edges do not cross from S to Vr \ S. This gives the formula. ⊓ ⊔ b Proof of Lemma 3. For b ∈ RJr ×d with rows indexed by P (i, h) ∈ ∂br , set qi (b) := ∇fi (χr (ηr (b))) − ci (b). Lemma 7 gives BVr ,Er Yr (b) = q(b), and i∈Vr qi (b) = 0. Lemma 8 gives a unique solution of BVr ,Er YEr = q(b). Hence Yr (b) is single-valued. It also gives, for a boundary incidence (i, h) ∈ ∂br and the component V e (i) not containing i,

Yr,e (b) = εe,i

X

∇fj (χr (ηr (b))) − cj (b) ,

εe,i ∈ {±1}.

(62)

j∈V e (i)

Let b, b′ differ only in coordinate (i, h). Since i ∈ / V e (i), the boundary terms cj (·) in (62) are unchanged for all j ∈ V e (i). Also ηr (b′ ) − ηr (b) = Bi,h (b′i,h − bi,h ). Hence
Yr,e (b′ ) − Yr,e (b) = εe,i Lr,V e (i) (ηr (b′ )) − Lr,V e (i) (ηr (b)) , and (30a) follows from the definition of κ∂,r . For v ̸= i, the coordinate (i, h) does not enter cv , so cv (b′ ) = cv (b). By (61c) and the definition of Zr,v , Zr,v (b) = ∇fv (χr (ηr (b))) − cv (b). Since Lr,{v} (η) = ∇fv (χr (η)), we obtain Zr,v (b′ ) − Zr,v (b) = Lr,{v} (ηr (b′ )) − Lr,{v} (ηr (b)). Then, (30b) follows from the definition of κ∂,r .

⊓ ⊔

A.3 Proof of Lemma 4 The next three results isolate the ingredients for Lemma 4: the first gives the rooted counting bounds used to sum edge sensitivities over active nodes, the second applies Lemma 3 to the specialized boundary values that generate ŶEν+1 and ȲEν+1 , and the third converts Y -increments r r into image-variable Z-increments.

42

Kuangyu Ding, Gesualdo Scutari

Lemma 9 Fix (i, h) ∈ ∂br and root the active tree Tr at the boundary node i. For v ∈ Vr , set δr,i (v) := max{distTr (i, v) − 1, 0}.

(63)

For v ̸= i, let Chr,i (v) be the set of active edges from v to its children in this rooted tree; set Chr,i (i) := ∅. Let p(v) be the active edge from v ̸= i to its parent, and set nr,i (i) := Nr ,

nr,i (v) := |V p(v) (i)|,

|V e (i)| ≤ nr,i (v) − 1,

X

v ̸= i.

Then X e∈Chr,i (v)

distTr (i,v)=t

(nr,i (v) − 1)2 ≤ 1, Nr2

t ≥ 0.

(64)

Proof For the first bound in (64), take v ̸= i and put p = p(v). The components V e (i) with e ∈ Chr,i (v) are pairwise disjoint, and their union is V p (i) \ {v}. Hence equality holds in the first bound of (64) for v ̸= i. If v = i, then Chr,i (v) = ∅, and the displayed inequality is immediate. Fix t ≥ 1. If two distinct nodes v, w have distTr (i, v) = distTr (i, w) = t, then V p(v) (i) ∩ V p(w) (i) = ∅: otherwise some node u would have both v and w on the unique path from i to u, and the two vertices at depth t on this path would have to coincide. Hence X

nr,i (v) ≤ Nr .

distTr (i,v)=t

2

 X

(nr,i (v) − 1)2 ≤ 

distTr (i,v)=t

X

(nr,i (v) − 1) ≤ Nr2 ,

distTr (i,v)=t

The same conclusion is immediate for t = 0, since nr,i (i) = Nr . This proves the second bound in (64). ⊓ ⊔ Lemma 10 Under Assumptions 1 and 3, for every block r and all ν ≥ maxs∈[p] diam(Ts ), ∥Ẑrν+1 − Z̄rν+1 ∥2 ≤ 4κ2∂,r Jbr

ν−1 X

X

∥Yhℓ+1 − Yhℓ ∥2 .

ℓ=ν−Dr (i,h)∈∂ br

Proof Note that ȲEν+1 = Yr (bνr ) with (bνr )(i,h) = Yhν , and Ŷeν+1 = Yr,e (b bνr,e ) with (b bνr,e )(i,h) = r ν−δe,i Y for (i, h) ∈ ∂br . For v ∈ Vr , define the node mismatch h

mv := (Ẑrν+1 − Z̄rν+1 )v . The vector b bνr,e depends on the incident edge e, whereas mv fixes the node v. To estimate mv , insert the auxiliary node-aligned boundary vector ν−δr,i (v)

(bνr,v )(i,h) := Yh

,

(i, h) ∈ ∂br .

For e ∈ A◦v , the definition of δe,i gives δe,i = δr,i (v) unless e ∈ Chr,i (v), in which case δe,i = δr,i (v) + 1. At v = i, both delays are zero for every incident edge. Thus bνr,v uses, in each boundary coordinate (i, h), the freshest value seen by any active edge incident to v. P ν+1 bν Since (Ẑrν+1 )v = )v = Zr,v (bνr ), inserting and subtracting ◦ Bv,e Yr,e (br,e ) and (Z̄r e∈Av ν Zr,v (br,v ) gives mv =

  Bv,e Yr,e (b bνr,e ) − Yr,e (bνr,v ) + Zr,v (bνr,v ) − Zr,v (bνr ) . | {z } e∈A◦ v =:qv | {z } X

=:pv

Graph Decomposition in Decentralized Optimization via Message Passing

43

Write ∆Yhℓ := Yhℓ+1 − Yhℓ . Estimate of pv . Fix an ordering of the boundary coordinates (i, h) ∈ ∂br . For each incident edge e ∈ A◦v , telescope the difference from bνr,v to b bνr,e by changing one boundary coordinate at a time. In the step that changes coordinate (i, h), let b− and b+ denote the two e,(i,h) e,(i,h) consecutive boundary vectors. Then X
Yr,e (b+ ) − Yr,e (b− ) , Yr,e (b bνr,e ) − Yr,e (bνr,v ) = e,(i,h) e,(i,h) br (i,h)∈∂

where the (i, h)-summand is zero if (b bνr,e )(i,h) = (bνr,v )(i,h) . The preceding observation shows that this coordinate difference is zero unless e ∈ Chr,i (v). If e ∈ Chr,i (v), then ν−(δr,i (v)+1) . (b bνr,e )(i,h) − (bνr,v )(i,h) = −∆Yh

Therefore pv =

X

Bv,e Yr,e (b+ ) − Yr,e (b− ) . e,(i,h) e,(i,h)

X

br e∈Chr,i (v) (i,h)∈∂

|

{z

}

=:pv,(i,h)

If Chr,i (v) = ∅, then pv,(i,h) = 0. Otherwise, using the sensitivity bound (30a) and the first bound in (64), nr,i (v) − 1 ν−(δr,i (v)+1) ∥pv,(i,h) ∥ ≤ κ∂,r ∥∆Yh ∥. Nr By Cauchy-Schwarz over the Jbr boundary coordinates, ∥pv ∥2 ≤ Jbr κ2∂,r

X br (i,h)∈∂ Chr,i (v)̸=∅

(nr,i (v) − 1)2 ν−(δr,i (v)+1) 2 ∥ . ∥∆Yh Nr2

(65)

Summing (65) over v and exchanging the v- and (i, h)-sums gives X

∥pv ∥2 ≤ Jbr κ2∂,r

v∈Vr

X

X

br (i,h)∈∂

v∈Vr Chr,i (v)̸=∅

(nr,i (v) − 1)2 ν−(δr,i (v)+1) 2 ∥∆Yh ∥ . Nr2

For fixed (i, h), group the inner sum by rooted depth t = distTr (i, v). On the nodes with Chr,i (v) ̸= ∅, one has v ̸= i and 1 ≤ δr,i (v) + 1 = t ≤ Dr . Thus all nodes in the same depth shell use the same increment ∆Yhν−t , and the second bound in (64) gives X v∈Vr Chr,i (v)̸=∅

Dr X (nr,i (v) − 1)2 ν−(δr,i (v)+1) 2 ∥∆Yh ∥ ≤ ∥∆Yhν−t ∥2 . 2 Nr t=1

Summing over (i, h) gives X

∥pv ∥2 ≤ Jbr κ2∂,r

v∈Vr

ν−1 X

X

∥∆Yhℓ ∥2 .

(66)

ℓ=ν−Dr (i,h)∈∂ br

Estimate of qv . Telescope the difference from bνr to bνr,v by changing one boundary coordinate at a time. If v = i, then δr,i (v) = 0, so the corresponding coordinate difference is zero. Hence only coordinates (i, h) with v ̸= i remain, and the sensitivity bound (30b) applies: ∥qv ∥2 ≤ Jbr κ2∂,r

X br : i̸=v (i,h)∈∂

1 ν−δr,i (v) ∥Y − Yhν ∥2 . Nr2 h

(67)

44

Kuangyu Ding, Gesualdo Scutari

For every integer t ≥ 0, ∥Yhν−t − Yhν ∥2 ≤ t

t X

∥∆Yhν−m ∥2 .

m=1

P Substituting this into (67) and summing over v, the bound v∈Vr δr,i (v) ≤ Nr Dr , which follows from 0 ≤ δr,i (v) ≤ Dr , together with Dr /Nr ≤ 1, yields X

∥qv ∥2 ≤ Jbr κ2∂,r

v∈Vr

ν−1 X

X

∥∆Yhℓ ∥2 .

(68)

ℓ=ν−Dr (i,h)∈∂ br

Finally, X

∥Ẑrν+1 − Z̄rν+1 ∥2 =

∥mv ∥2 ≤ 2

v∈Vr

X

∥pv ∥2 + 2

v∈Vr

X

∥qv ∥2 .

v∈Vr

⊓ ⊔

Combining (66) and (68) proves the lemma.

Proof of Lemma 4. For s ∈ Mr , set ∆Ysℓ := YEℓ+1 − YEℓs and ∆Zsℓ := Zsℓ+1 − Zsℓ = BV,Es ∆Ysℓ . s Let Rr,s be the row selector satisfying Rr,s YEs = YBr,s . Full column rank gives ∆Ysℓ =

B†V,Es ∆Zsℓ , and hence X br (i,h)∈∂ h∈Es

X

∥∆Yhℓ ∥2 =

h∈Br,s

|Ih ∩ Vr |∥∆Yhℓ ∥2 = ∥(Λr,s )1/2 Rr,s B†V,Es ∆Zsℓ ∥2

≤ γr,s ∥∆Zsℓ ∥2 ≤ Γr ∥∆Zsℓ ∥2 . Since {Br,s : s ∈ Mr } is a disjoint partition of ∂r , summing the displayed estimate over s and over the delay window, and then applying Lemma 10, proves (31). ⊓ ⊔

A.4 Proof of Proposition 6 Fix m, relabel the tree block as block 1, and suppress the subscript m: write T0 = (V0 , E0 ), E 0 , I∂ , P, and (α∂ , α∂ , R∂ ) for the corresponding objects. For Z ∈ S, put xi := ∇fi∗ (Zi ). We first express the block progress terms in (19). Let h = {i, j} ∈ E 0 be a singleton edge block, and write ∆h for the progress of this block. Changing only Yh by s changes the image coordinates to Zi + Bi,h s and Zj + Bj,h s. Since Bi,h + Bj,h = 0 and |Bi,h | = 1, the singleton block minimization in (19) reduces to min

ui +uj =Zi +Zj

fi∗ (ui ) + fj∗ (uj ).

h ∗ h ∗ h Let (uh i , uj ) be its minimizer. The first-order condition gives ∇fi (ui ) = ∇fj (uj ) = ph . Thus h h ui = ∇fi (ph ) and uj = ∇fj (ph ), where ph is the unique solution of ∇fi (ph ) + ∇fj (ph ) = Zi + Zj . By the definition of the block progress and this identity, ∗ h ∆h (Z) = fi∗ (Zi ) + fj∗ (Zj ) − fi∗ (uh i ) − fj (uj ) X = [fk∗ (Zk ) − fk∗ (∇fk (ph )) − ⟨ph , Zk − ∇fk (ph )⟩] . k∈{i,j}

By the definition of xk , ∇fk (xk ) = Zk . Fenchel’s identity gives fk (xk ) + fk∗ (Zk ) = ⟨Zk , xk ⟩ ,

fk (ph ) + fk∗ (∇fk (ph )) = ⟨∇fk (ph ), ph ⟩ .

Substituting these identities yields, for k ∈ {i, j}, fk∗ (Zk ) − fk∗ (∇fk (ph )) − ⟨ph , Zk − ∇fk (ph )⟩ = fk (ph ) − fk (xk ) − ⟨∇fk (xk ), ph − xk ⟩ .

Graph Decomposition in Decentralized Optimization via Message Passing

45

Define the Bregman divergence Dfi (u, v) := fi (u) − fi (v) − ⟨∇fi (v), u − v⟩. Then ∆h (Z) = Dfi (ph , xi ) + Dfj (ph , xj ). The lower Hessian bound in Proposition 6 yields ∆h (Z) ≥

α∂ α ∥ph − xi ∥2R∂ + ∥ph − xj ∥2R∂ ≥ ∂ ∥xi − xj ∥2R∂ . 2 4

(69)

The same argument applied to (19) for the P tree block yields ui = ∇fi (p0 ), i ∈ V0 , where p0 is P the unique solution of i∈V0 ∇fi (p0 ) = i∈V0 Zi . The corresponding progress ∆1 satisfies X

∆1 (Z) =

Dfi (p0 , xi ) ≥

i∈V0

X α∂ ∥xi − p0 ∥2R∂ . 2 i∈I ∩V ∂

(70)

0

We next compare the global gap with the block progress. By Fenchel’s identity, * X

Dfi (p, xi ) =

X

(fi (p) − fi (xi ) − ⟨Zi , p − xi ⟩) = G(Z) +

i∈V

i∈V

X

fi (p) −

i∈V

+ X

Zi , p

.

i∈V

P Since Z ∈ S = Range(B), i∈V Zi = 0. Taking P p = p0 , using V \ V0 ⊆ I∂ , and applying weak duality for (P) and (D), which gives −G⋆ ≤ i∈V fi (p0 ), we obtain G(Z) − G⋆ ≤ G(Z) +

X

fi (p0 ) =

Dfi (p0 , xi ) = ∆1 (Z) +

i∈V

i∈V

≤ ∆1 (Z) +

X

X

Dfi (p0 , xi )

i∈V\V0

α∂ X ∥xi − p0 ∥2R∂ . 2 i∈I ∂

It remains to bound the finite boundary term by block progress. Extending T0 to a spanning tree of G gives |V \ V0 | ≤ |E 0 | ≤ q. Each vertex outside V0 has a path to V0 with at most q edges in E 0 , ending at a vertex of I∂ ∩ V0 . Applying Cauchy’s inequality along these paths and summing gives, with Cq := 1 + q(q + 1),  X

∥xi − p0 ∥2R∂ ≤ Cq 

 X

∥xi − p0 ∥2R∂ +

i∈I∂ ∩V0

i∈I∂

X

∥xi − xj ∥2R∂  .

{i,j}∈E 0

Combining the last two bounds with (70) and (69) gives

⋆

G(Z) − G ≤



α∂ 1 + 2Cq α∂



 ∆1 (Z) +

 X

∆h (Z) ,

h∈E 0

which is exactly the block error bound for the partition P = {E0 } ∪ {{h} : h ∈ E 0 }. Since q is fixed and α∂ /α∂ = O(1), this proves κP = O(1). Finally we bound the constants in Theorem 1. The partition has p = 1 + |E 0 | ≤ q + 1. Singleton blocks have no interior propagation, so Dr = 0 for them; only block 1 can contribute to A. For block 1, Jb1 ≤ 2|E 0 | ≤ 2q.√Every neighboring block is a singleton edge Es = {h}, and its incidence column has norm 2, so γ1,s = |Ih ∩PV1 |/2 ≤ 1 and Γ1 ≤ 1. Moreover, for P −1 is (N µ )−1 -Lipschitz. S ⊆ V1 , the map 1 1 i∈S ∇fi is |S|L-Lipschitz, while ( i∈V1 ∇fi ) Hence κ∂,1 ≤ L/µ1 = O(1). Together with the uniform bounds on µ−1 and L, the definition 1 of A gives A = O(1). Finally, D ≤ diam(T0 ) − 1; substituting ωP ≤ p = O(1), κP = O(1), and −1 A = O(1) into (36) gives (1 − ρ) = O(diam(T0 )). ⊔ ⊓

46

Kuangyu Ding, Gesualdo Scutari

A.5 Proof of Proposition 7 Fix m and abbreviate P := Pm , R := Rm , α := αm , and α := αm . For Z ∈ S, set (0)

G0 (Z) := 21 tr(ZR−1 Z ⊤ ). Let κP be its block error-bound constant and set W := ZR−1/2 . This bijection maps S and each Ur onto themselves, so block error-bound constants are invariant under the corresponding change of objective. Moreover, G0 (W R1/2 ) = 12 ∥W ∥2 . Below, we write Z for W and work with G0 (Z) = 21 ∥Z∥2 . We first prove D+2 3(D + 1) (0) ≤ κP ≤ 1 + , 4 sin2 (π/p) 2 sin2 (π/p)



(0)

κP = Θ

m2 D

 ,

(71)

For a path block Er , the incidence matrix has rank |Vr | − 1, and hence     X m×d Ur = U ∈ R : supp(U ) ⊆ Vr , Ui = 0 .   i∈Vr

(0)

By definition, ∆r (Z) = 12 ∥Z∥2 − minU ∈Ur 12 ∥Z + U ∥2 . The minimum is attained when P Zi + Ui = Z̄Vr := |Vr |−1 j∈Vr Zj for i ∈ Vr . Hence (0)

∆r (Z) =

1 X ∥Zi − Z̄Vr ∥2 . 2 i∈V r

Relabel the blocks by r = 0, . . . , p − 1 and index the ring nodes cyclically as v0 , . . . , vm−1 . Let Qr := {vr(D+1)+j : 0 ≤ j ≤ D},

br := v(r+1)(D+1) ,

where indices are taken modulo m. The sets Qr form a disjoint partition of V, with |Qr | = D+1. Since br is the first P node of Qr+1 , the nodes incident to block r are Vr = Qr ∪ {br }. With ξr := (D + 1)−1 i∈Qr Zi , then (0)

2∆r (Z) =

X

∥Zi − ξr ∥2 +

i∈Qr

Thus

X

(0)

∥Zi − ξr ∥2 ≤ 2∆r (Z),

D+1 ∥Zbr − ξr ∥2 . D+2 (0)

∥Zbr − ξr ∥2 ≤ 4∆r (Z).

(72)

i∈Qr

Since br ∈ Qr+1 , (72) gives (0)

(0)

∥ξr+1 − ξr ∥2 ≤ 2∥ξr − Zbr ∥2 + 2∥Zbr − ξr+1 ∥2 ≤ 8∆r (Z) + 4∆r+1 (Z). Summing cyclically yields p−1 X r=0

∥ξr+1 − ξr ∥2 ≤ 12

p−1 X

(0)

∆r (Z).

(73)

r=0

Since Z ∈ S and the sets Qr form a partition of V, ⊤ )⊤ ∈ Rp×d and Ξ := (ξ0⊤ , . . . , ξp−1

Pp−1

r=0 ξr = (D + 1)

−1

P

i∈V Zi = 0. Set

  −1 1   .. ..   . . Cp :=  .  −1 1  1 −1 2 ⊤ The cycle spectrum satisfies λ+ min (Cp Cp ) = 4 sin (π/p); see, e.g., [3]. Therefore, p−1 X r=0

∥ξr+1 − ξr ∥2 = ∥Cp Ξ∥2F ≥ 4 sin2 (π/p)∥Ξ∥2F = 4 sin2 (π/p)

p−1 X r=0

∥ξr ∥2 .

(74)

Graph Decomposition in Decentralized Optimization via Message Passing

47

Combining (72), (73), and (74) yields

2

∥Z∥ =

p−1 X



 X

 r=0

2

2

∥Zi − ξr ∥ + (D + 1)∥ξr ∥

i∈Qr

 p−1  X (0) 3(D + 1) ∆r (Z). ≤2 1+ 2 sin2 (π/p) r=0

This proves the upper bound in (71). For the lower bound, choose a nonzero Ξ ∈ Rp×d whose columns lie in the eigenspace of Cp⊤ Cp associated with 4 sin2 (π/p), and denote its rows by ξr . Then p−1 X

p−1 X

ξr = 0,

r=0

∥ξr+1 − ξr ∥2 = 4 sin2 (π/p)

r=0

∥ξr ∥2 .

r=0

Set Zi = ξr for i ∈ Qr , r = 0, . . . , p − 1. Then

G0 (Z) =

p−1 X

P

i∈V Zi = (D + 1)

Pp−1

r=0 ξr = 0 and

p−1 p−1 D+1 X 1X X ∥Zi ∥2 = ∥ξr ∥2 . 2 r=0 i∈Q 2 r=0 r

Moreover, Vr = Qr ∪ {br }, with Zi = ξr for i ∈ Qr and Zbr = ξr+1 , so Z̄Vr = ((D + 1)ξr + (0)

ξr+1 )/(D + 2). Substitution into the definition of ∆r (0)

∆r (Z) =

yields

 1 D+1 (D + 1)∥ξr − Z̄Vr ∥2 + ∥ξr+1 − Z̄Vr ∥2 = ∥ξr+1 − ξr ∥2 . 2 2(D + 2)

(0) 2 r=0 ∆r (Z) = (D + 2)/(4 sin (π/p)) and (71) follows. b It remains to transfer the bound to G. Define G(W ) := G(W R1/2 ) for W

Hence G0 (Z)/

Pp−1

∈ S. The   Hessian bounds in Proposition 7 give α−1 I ⪯ ∇2 fi∗ (R1/2 ·) (Wi ) ⪯ α−1 I. Let PS and br (W ) := G(W b Pr be the Euclidean projectors onto S and Ur , respectively, and define ∆ )− b ). For G0 (V ) = 1 ∥V ∥2 , the minimizer over V + Ur is V − Pr V ; hence minU ∈W +Ur G(U 2 (0)

∆r (V ) = 21 ∥V ∥2 − 12 ∥V − Pr V ∥2 = 12 ∥Pr V ∥2 . The quadratic block error bound therefore Pp−1 (0) −1 2 gives ∥V ∥2 for V ∈ S. Since Ur ⊆ S, Pr PS = Pr . The smoothness r=0 ∥Pr V ∥ ≥ (κP ) and strong convexity bounds above then yield p−1 X

p−1 X
α α b b b br (W ) ≥ α ∥Pr ∇G(W )⊤ ∥2 ≥ ∥PS ∇G(W )⊤ ∥2 ≥ G(W ) − G⋆ . ∆ (0) (0) 2 2κ ακ r=0 r=0 P

P

(0)

Therefore κP ≤ (α/α)κP , and (71) proves κP = O(m2 /D).

⊓ ⊔

B Proofs for Section 5 For the proof notation, fix a block P r. For b ∈ RJr ×d with rows indexed by (i, h) ∈ ∂br , use the boundary contribution ci (b) = h∈A∂ Bi,h bi,h from Appendix A.2, and write cr (b) := b

i

(ci (b))i∈Vr . For U, ϑ ∈ RNr ×d , the exact and surrogate block slices are Gr (U ) :=

X i∈Vr

fi∗ (Ui ),

e r (U ; ϑ) := G

X

fei∗ (Ui ; ϑi ).

i∈Vr

Only nodes in Vr appear in these slices; the remaining terms are constant under a block-r update.

48

Kuangyu Ding, Gesualdo Scutari

B.1 Proof of Lemma 5 Proof of (52a)–(52c). Fix a block r. For b ∈ RJr ×d with rows indexed by (i, h) ∈ ∂br , set P b ∈ RNr ×d differ only in coordinate i. Define ηr (b) := i∈Vr ci (b). Suppose ϑ, ϑ b

er,j (b, ϑ) + cj (b), u0j := Z

er,j (b, ϑ) b + cj (b). u1j := Z

Applying the same optimality condition for each active edge variable as in the proof of Lemma 7 b with f ∗ replaced by fe∗ (·; ϑj ) and fe∗ (·; ϑ bj ), reto the two minimizers Yer (b, ϑ) and Yer (b, ϑ), j j j spectively, gives common values x0 , x1 ∈ Rd such that

−1 0 bj ) −1 (x1 ), (x ), u1j = ∇u fej∗ (·; ϑ u0j = ∇u fej∗ (·; ϑj ) X X u0j = u1j = ηr (b). j∈Vr

j ∈ Vr ,

j∈Vr

er,S in (48), By the definition of L er,{j} (ηr (b); ϑ), u0j = L

b er,{j} (ηr (b); ϑ). u1j = L

Using (50) at the fixed input ηr (b) gives, er,i (b, ϑ) b −Z er,i (b, ϑ)∥ = L b −L bi − ϑi ∥. er,{i} (ηr (b); ϑ) er,{i} (ηr (b); ϑ) ≤ κ ∥Z ec,r ∥ϑ For v ̸= i, ec,r b er,v (b, ϑ) b −Z er,v (b, ϑ)∥ = L b −L er,{v} (ηr (b); ϑ) er,{v} (ηr (b); ϑ) ≤ κ ∥Z ∥ϑi − ϑi ∥. Nr By Lemma 8, for some sign εe,i ∈ {±1}, e r,e (b, ϑ) b −Y e r,e (b, ϑ) = εe,i Y

X

(u1v − u0v ).

v∈V e (i)

The choice i ∈ / V e (i) matches the edge term in (50): the center perturbation is in coordinate i, while the aggregate is over the opposite component V e (i). By (48), X

b e e (u1v − u0v ) = L r,V e (i) (ηr (b); ϑ) − Lr,V e (i) (ηr (b); ϑ).

v∈V e (i)

Therefore |V e (i)| b e r,e (b, ϑ) b −Y e r,e (b, ϑ)∥ ≤ κ ∥Y ec,r ∥ϑi − ϑi ∥. Nr This proves (52a)–(52c). Proof of (51a)–(51b). Fix a center tuple ϑ = (ϑi )i∈Vr , and suppose b, b′ differ only in boundary coordinate (i, h). With ϑ fixed, (48) is the surrogate counterpart of the aggregate map used in er,S (·; ϑ) gives Lemma 3. Repeating the proof of Lemma 3 with Lr,S replaced by L |V e (i)| ′ e r,e (b′ , ϑ) − Y e r,e (b, ϑ)∥ ≤ κ ∥Y e∂,r ∥bi,h − bi,h ∥ Nr and

1 er,v (b′ , ϑ) − Z er,v (b, ϑ)∥ ≤ κ ∥Z e∂,r ∥b′ − bi,h ∥, Nr i,h This proves (51a)–(51b).

v ̸= i. ⊓ ⊔

Remark on κ ec,r . The constant κ ec,r in (50) measures the center sensitivity of the frozen aggregate maps and can reflect the associated surrogate approximation quality. When fej∗ ∈ C 2

Graph Decomposition in Decentralized Optimization via Message Passing

49

in (u, θ) for j ∈ Vr , fix i ∈ Vr , η ∈ Rd , and a center tuple ϑ ∈ RNr ×d . To identify the local derivative entering Lipϑi in (50), vary only the i-th center, denoted by θ. By (48), along this one-coordinate variation, for any nonempty S ⊆ Vr , er,S (η; ϑ) L

ϑi =θ

=

X

uj (θ),

j∈S

where uj (θ), j ∈ Vr , are determined by ∇u fej∗ (uj (θ); ϑj ) = x(θ)

∇u fei∗ (ui (θ); θ) = x(θ),

(j ̸= i),

X

uj (θ) = η.

j∈Vr

Applying the implicit function theorem at θ = ϑi , write  −1 Hj := ∇2uu fej∗ (uj (ϑi ); ϑj )

(j ̸= i),

−1  X e∗ Hj . , Ci := ∇⊤ Hi := ∇2uu fei∗ (ui (ϑi ); ϑi ) θ ∇u fi (ui (ϑi ); θ) θ=ϑ , HΣ := i

j∈Vr

Differentiating the defining equations gives ∇θ uj (ϑi )⊤ = Hj ∇θ x(ϑi )⊤ Differentiating

P

∇θ ui (ϑi )⊤ = Hi ∇θ x(ϑi )⊤ − Hi Ci .

(j ̸= i),

j∈Vr uj (θ) = η then yields −1 ∇θ x(ϑi )⊤ = HΣ Hi Ci .

0 = HΣ ∇θ x(ϑi )⊤ − Hi Ci ,

Therefore, for every component V e (i) not containing i, 



∇θ 

 ⊤

X

uv  (ϑi )

=

v∈V e (i)

 X

−1 Hv  HΣ Hi Ci ,

v∈V e (i)

−1 ∇θ ui (ϑi )⊤ = Hi (HΣ Hi − I)Ci ,

−1 ∇θ uv (ϑi )⊤ = Hv HΣ Hi Ci

(v ̸= i).

Thus κ ec,r is certified by any upper bound on 

( sup max η,ϑ i∈Vr

Nr

max

 X



e∈Er |V e (i)|

−1 Hv  HΣ Hi Ci ,

v∈V e (i)

) −1 Hi (HΣ Hi − I)Ci ,

−1 H i Ci max Nr Hv HΣ v̸=i

.

For the quadratic surrogates in Examples 2–3, let Qi (Zi ) denote the quadratic metric, so Qi ≡ Mi in Example 2 and Qi = Hi in Example 3. The local derivative above is Ci (ui (ϑi ), ϑi ), where

Ci (Ui , Zi )h = ∇2 fi∗ (Zi ) − Qi (Zi ) h + ∇Zi Qi (Zi )[h] (Ui − Zi ). In Example 2, ∥Ci (Ui , Zi )∥ ≤ µ−1 ec,r < ∞. f + ∥Mi ∥ and the uniform curvature bounds imply κ i

B.2 Proof of Lemma 6 Fix a block r and an iteration ν ≥ maxs∈[p] diam(Ts ). For i, v ∈ Vr , set di (v) := 0 if i = v, and di (v) := mine∈A◦v δe,i otherwise. Use the node-aligned boundary vector bνr,v from the ν−di (v)

ν := (Z proof of Lemma 10, and set Zr,v i ν ] = Zν . [Zr,v v v

)i∈Vr for the center coordinates. In particular,

50

Kuangyu Ding, Gesualdo Scutari

Mismatch decomposition. For v ∈ Vr , define the node mismatch mv := (Ẑrν+1 − Z̄rν+1 )v . ν ) depends on the incident edge e, whereas m fixes the node v. To estimate The pair (bνr,e , Zr,e v ν ). Since mv , insert the node-aligned pair (bνr,v , Zr,v

(Ẑrν+1 )v =

X

e r,e (bν , Z ν ) Bv,e Y r,e r,e

e∈A◦ v

er,v (bν , Z ν ), adding and subtracting and (Z̄rν+1 )v = Z r Vr X

er,v (bν , Z ν ) e r,e (bν , Z ν ) = Z Bv,e Y r,v r,v r,v r,v

e∈A◦ v

gives the exact decomposition mv = p v + qv , where X

pv :=

h i e r,e (bν , Z ν ) − Y e r,e (bν , Z ν ) , Bv,e Y r,e r,e r,v r,v

(75)

e∈A◦ v

er,v (bν , Z ν ) − Z er,v (bν , Z ν ). qv := Z r,v r,v r Vr

(76)

e r,e (bν , Z ν ) in each summand of (75). This gives Estimate of pv . Insert Y r,v r,e pv = p∂v + pcv , where X

p∂v :=

h i e r,e (bν , Z ν ) − Y e r,e (bν , Z ν ) , Bv,e Y r,e r,e r,v r,e

e∈A◦ v

X

pcv :=

h i e r,e (bν , Z ν ) − Y e r,e (bν , Z ν ) . Bv,e Y r,v r,e r,v r,v

e∈A◦ v

The term p∂v changes only the boundary vector. For e ∈ A◦v and (i, h) ∈ ∂br , the delay definition and (63) give δe,i ∈ {δr,i (v), δr,i (v) + 1}. Hence the same argument in (66) gives X

∥p∂v ∥2 ≤ Jbr κ e2∂,r

v∈Vr

ν−1 X

∥Yhℓ+1 − Yhℓ ∥2 .

X

(77)

e r (i,h)∈∂ br ℓ=ν−D

For the center part, write ∆Ziℓ := Ziℓ+1 − Ziℓ . For each i ∈ Vr , root the tree at i, and let Chr,i (v) := {e ∈ A◦v : δe,i = di (v) + 1}, which are among the child edges of v in this rooted tree. For v ̸= i, let pi (v) be the active edge from v to its parent, and set nr,i (i) := Nr ,

nr,i (v) := |V pi (v) (i)|,

v ̸= i.

ν Since δe,i = 0 for every e ∈ A◦i , Chr,i (i) = ∅. For each e ∈ A◦v , telescope differences from Zr,v ν by changing center coordinates one at a time. In the coordinate-i step, let ϑ− and to Zr,e e,i

ϑ+ e,i denote the consecutive center tuples, and define pcv,i :=

X

h i e r,e (bν , ϑ+ ) − Y e r,e (bν , ϑ− ) . Bv,e Y r,v r,v e,i e,i

e∈A◦ v c ◦ Then pcv = i∈Vr pv,i . Since δe,i ∈ {di (v), di (v) + 1} for every e ∈ Av , the i-coordinate difference is zero unless e ∈ Chr,i (v). If e ∈ Chr,i (v), then

P

ν−δe,i

− ν ν (ϑ+ e,i − ϑe,i )i = [Zr,e ]i − [Zr,v ]i = Zi

ν−di (v)

− Zi

ν−di (v)−1

= −∆Zi

.

Graph Decomposition in Decentralized Optimization via Message Passing

51

e r , and the sensitivity bound (52a) If Chr,i (v) = ∅, then pcv,i = 0. Otherwise di (v) + 1 ≤ D together with the counting argument for v ̸= i in (64) gives P ∥pcv,i ∥2 ≤ κ e2c,r

e∈Chr,i (v) |V e (i)|

2 ν−di (v)−1 2

∥∆Zi

Nr2

∥

(nr,i (v) − 1)2 ν−d (v)−1 2 ∥∆Zi i ∥ . Nr2

≤κ e2c,r By Cauchy-Schwarz,

X

∥pcv ∥2 ≤ Nr κ e2c,r

i∈Vr , Chr,i (v)̸=∅

(nr,i (v) − 1)2 ν−d (v)−1 2 ∥∆Zi i ∥ . Nr2

Summing over v and rearranging terms gives X

X

∥pcv ∥2 ≤ Nr κ e2c,r

v∈Vr

X

i∈Vr v∈Vr : Chr,i (v)̸=∅ Dr X X e

= Nr κ e2c,r

(nr,i (v) − 1)2 ν−d (v)−1 2 ∥∆Zi i ∥ Nr2

 X 

i∈Vr t=1 er D X X

≤ Nr κ e2c,r

v∈Vr : Chr,i (v)̸=∅, di (v)+1=t ν−1 X

e2c,r ∥∆Ziν−t ∥2 = Nr κ

i∈Vr t=1

 (nr,i (v) − 1)2  ∥∆Z ν−t ∥2 i Nr2 ∥Ziℓ+1 − Ziℓ ∥2 ,

X

(78)

e r i∈Vr ℓ=ν−D

Here di (v) = max{distTr (i, v) − 1, 0}, so each inner sum is over vertices at depth t and is at most one by (64). Combining (77) and (78) yields X

ν−1 X

∥pv ∥2 ≤ 2Jbr κ e2∂,r

v∈Vr

ν−1 X

∥Yhℓ+1 − Yhℓ ∥2 + 2Nr κ e2c,r

X

X

∥Ziℓ+1 − Ziℓ ∥2 .

e r i∈Vr ℓ=ν−D

e r (i,h)∈∂ br ℓ=ν−D

(79) Estimate of qv . Split qv = qv∂ + qvc , where er,v (bν , Z ν ) − Z er,v (bν , Z ν ), qv∂ := Z r,v r,v r r,v

er,v (bν , Z ν ) − Z er,v (bν , Z ν ). qvc := Z r r,v r Vr

ν fixed, Lemma 10 gives the same q -estimate with κ With Zr,v e∂,r in place of κ∂,r : v

X

ν−1 X

∥qv∂ ∥2 ≤ Jbr κ e2∂,r

v∈Vr

X

∥Yhℓ+1 − Yhℓ ∥2 .

(80)

e r (i,h)∈∂ br ℓ=ν−D

ν to Z ν one center For the center part, keep the boundary vector fixed at bνr and change ZV r,v r c er,v during the i-coordinate replacement. coordinate at a time. Let qv,i be the change in Z P c c c Since dv (v) = 0, we have qv,v = 0. Thus qvc = i∈Vr \{v} qv,i , and (52c) gives ∥qv,i ∥ ≤ κ e c,r ν−d (v) ∥Zi i − Ziν ∥ for i ̸= v. Hence, using Cauchy–Schwarz and (Nr − 1)/Nr2 ≤ 1/Nr , Nr

∥qvc ∥2 ≤

κ e2c,r X Nr i∈V

ν−di (v)

∥Zi

− Ziν ∥2 .

(81)

r

For every i, telescoping gives ν−di (v)

∥Zi

di (v)

− Ziν ∥2 ≤ di (v)

X m=1

∥Ziν−m+1 − Ziν−m ∥2 ,

er. 0 ≤ di (v) ≤ D

52

Kuangyu Ding, Gesualdo Scutari

Therefore 1 X X ν−d (v) er ∥Zi i − Ziν ∥2 ≤ D Nr v∈V i∈V r

where we used

r

P

ν−1 X

X

∥Ziℓ+1 − Ziℓ ∥2 ,

(82)

e r i∈Vr ℓ=ν−D

v∈Vr di (v) ≤ Nr Dr . Combining (81) and (82) yields

e

X

er κ e2c,r ∥qvc ∥2 ≤ D

ν−1 X

X

∥Ziℓ+1 − Ziℓ ∥2 .

e r i∈Vr ℓ=ν−D

v∈Vr

Together with (80), X

ν−1 X

∥qv ∥2 ≤ 2Jbr κ e2∂,r

v∈Vr

X

ν−1 X

er κ ∥Yhℓ+1 − Yhℓ ∥2 + 2D e2c,r

X

∥Ziℓ+1 − Ziℓ ∥2 .

e r i∈Vr ℓ=ν−D

e r (i,h)∈∂ br ℓ=ν−D

(83) Since

∥Ẑrν+1 − Z̄rν+1 ∥2 =

X

∥mv ∥2 ≤ 2

v∈Vr

X

∥pv ∥2 + 2

X

∥qv ∥2 ,

v∈Vr

v∈Vr

X

∥Yhℓ+1 − Yhℓ ∥2

combining (79) and (83) gives ν−1 X

∥Ẑrν+1 − Z̄rν+1 ∥2 ≤ 8Jbr κ e2∂,r

e r (i,h)∈∂ br ℓ=ν−D

e r )e + 4(Nr + D κ2c,r

ν−1 X

X

∥Ziℓ+1 − Ziℓ ∥2 .

(84)

e r i∈Vr ℓ=ν−D

Reduction to block increments. It remains to replace the coordinate increments by block and boundary increments. Since Z ℓ = BY ℓ , Zrℓ = BV,Er YEℓr , and Ai = A◦i ⊔ A∂i , for i ∈ Vr , X X Ziℓ+1 − Ziℓ = Bi,h (Yhℓ+1 − Yhℓ ) = (Zrℓ+1 − Zrℓ )i + Bi,h (Yhℓ+1 − Yhℓ ). h∈Ai

h∈A∂ i

Cauchy’s inequality, Jr,i := |A∂i | ≤ Jr , and ∂br = i∈Vr ({i} × A∂i ) give X X ∥Ziℓ+1 − Ziℓ ∥2 ≤ 2∥Zrℓ+1 − Zrℓ ∥2 + 2Jr ∥Yhℓ+1 − Yhℓ ∥2 . F

i∈Vr

br (i,h)∈∂

e r , . . . , ν − 1 and substituting into (84) gives Summing over ℓ = ν − D   e r )e ∥Ẑrν+1 − Z̄rν+1 ∥2 ≤ 8e κ2∂,r Jbr + 8Jr (Nr + D κ2c,r

ν−1 X

X

∥Yhℓ+1 − Yhℓ ∥2

e r (i,h)∈∂ br ℓ=ν−D

e r )e + 8(Nr + D κ2c,r

ν−1 X

∥Zrℓ+1 − Zrℓ ∥2 .

(85)

er ℓ=ν−D

By the proof of Lemma 4, X ∥Yhℓ+1 − Yhℓ ∥2 ≤ γr,s ∥Zsℓ+1 − Zsℓ ∥2 ≤ Γr ∥Zsℓ+1 − Zsℓ ∥2 ,

s ∈ Mr .

br (i,h)∈∂ h∈Es

Since ∂br = yields

F

s∈Mr {(i, h) ∈ ∂r : h ∈ Es }, summing this estimate over s and ℓ = ν− Dr , . . . , ν−1

b

ν−1 X

X

e r (i,h)∈∂ br ℓ=ν−D

e

∥Yhℓ+1 − Yhℓ ∥2 ≤ Γr

ν−1 X

X

∥Zsℓ+1 − Zsℓ ∥2 .

e r s∈Mr ℓ=ν−D

fr,∂ and M fr,c , proves (53). Substitution into (85), together with the definitions of M

⊓ ⊔

Graph Decomposition in Decentralized Optimization via Message Passing

53

B.3 Proof of Theorem 2 As in the proof of Theorem 1, we first rewrite Algorithm 2 as a delayed block update and then combine a one-step surrogate recursion with the delayed mismatch estimate. Similar to the proof of Proposition 5, applying the same message expansion to (39) gives the following delayed block representation; we omit the proof. Lemma 11 Under the assumptions of Theorem 2, for all ν ≥ maxr∈[p] diam(Tr ), Algorithm 2 is equivalent to the block update: for any e ∈ Er and r ∈ [p],  ν+1 ∈ argmin Ŷe Ye

e r BV ,E YE + cr (bν ); Z ν , min G r,e r,e r r r

YEr \{e}

(86)

 ν+1 = Yeν + τrν (Ŷeν+1 − Yeν ). Ye Lemma 12 Under Assumption 5, if 0 ≤ τrν ≤ 1/ωP for every r ∈ [p], then G(Z ν+1 ) ≤ G(Z ν ) −

p X

τrν δer (Y ν ) +

p X r=1

r=1

τrν

e∗ L r ∥Ẑrν+1 − Z̄rν+1 ∥2 . 2

(87)

Proof Since τrν ≤ 1/ωP , applying Jensen’s inequality to each fi∗ and summing over the nodes yields p h i X G(Z ν+1 ) − G(Z ν ) ≤ τrν G(Z ν − Zrν + Ẑrν+1 ) − G(Z ν ) . r=1

For fixed r, all outside coordinates are unchanged. Majorization and touching give e ν − Z ν + Ẑ ν+1 ; Z ν ) − G(Z e ν ; Z ν ). G(Z ν − Zrν + Ẑrν+1 ) − G(Z ν ) ≤ G(Z r r e Z ν ) over Z ν + Ur and Ẑrν+1 − Z̄rν+1 ∈ Ur , first-order Since Z ν − Zrν + Z̄rν+1 minimizes G(·; optimality gives D E e ν − Z ν + Z̄ ν+1 ; Z ν )⊤ , Ẑ ν+1 − Z̄ ν+1 = 0. ∇U G(Z r

r

r

r

e ∗ -smoothness on this slice then yields The L r e∗ e ν − Z ν + Ẑ ν+1 ; Z ν ) ≤ G(Z e ν − Z ν + Z̄ ν+1 ; Z ν ) + Lr ∥Ẑ ν+1 − Z̄ ν+1 ∥2 . G(Z r r r r r r 2 Combining these bounds with the definition of δer (Y ν ) proves (87).

⊔ ⊓

Lemma 13 Under Assumptions 5 and 6, assume that 0 < τrν ≤ 1/ωP for every r ∈ [p], and let τ ν := minr∈[p] τrν . Then G(Z ν+1 ) − G⋆ ≤

 1−

+

τν 2e κP

p X r=1

Proof Split



p

X µ e∗r G(Z ν ) − G⋆ − ∥Zrν+1 − Zrν ∥2 ν 8τ r r=1

e∗ + µ 2L e∗r r τrν ∥Ẑrν+1 − Z̄rν+1 ∥2 .

(88)

4

Pp

νe ν r=1 τr δr (Y ) in (87) into two halves. The surrogate block error bound gives p

1 X νe τν τ δr (Y ν ) ≥ G(Z ν ) − G⋆ . 2 r=1 r 2e κP For the second half, touching and strong convexity of the nondelayed surrogate slice give ∗

µ e δer (Y ν ) ≥ r ∥Z̄rν+1 − Zrν ∥2 . 2

54

Kuangyu Ding, Gesualdo Scutari

Using ∥Z̄rν+1 − Zrν ∥2 ≥

1 ν+1 ∥Ẑ − Zrν ∥2 − ∥Ẑrν+1 − Z̄rν+1 ∥2 2 r

and Zrν+1 − Zrν = τrν (Ẑrν+1 − Zrν ), the second half of the progress satisfies 1 νe µ e∗ µ e∗ τ δr (Y ν ) ≥ rν ∥Zrν+1 − Zrν ∥2 − τrν r ∥Ẑrν+1 − Z̄rν+1 ∥2 . 2 r 8τr 4 Substituting these bounds into Lemma 12 gives (88).

⊓ ⊔

Proof of Theorem 2. Substituting (53) into (88) and using (54) gives for all ν maxr∈[p] diam(Tr )

≥

G(Z ν+1 ) − G⋆ ≤

 1−

e + τA

τ 2e κP



ν−1 X

p

e∗ X
µ G(Z ν ) − G⋆ − ∥Z ν+1 − Zrν ∥2 8τ r=1 r p X

∥Zrℓ+1 − Zrℓ ∥2 .

e r=1 ℓ=ν−D

Invoking the standard delay-window inequality under (55) from this starting index and then using the same argument as in the proof of Theorem 1 gives (56). ⊔ ⊓

References 1. Albert Berahas, Raghu Bollapragada, Nitish Shirish Keskar, and Ermin Wei. Balancing Communication and Computation in Distributed Optimization. IEEE Trans. Autom. Control, to appear, 2019. 2. S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3(1):1–122, 2011. 3. Fan R. K. Chung. Spectral Graph Theory, volume 92 of CBMS Regional Conference Series in Mathematics. American Mathematical Society, Providence, RI, 1997. 4. P. Di Lorenzo and G. Scutari. NEXT: In-network nonconvex optimization. IEEE Trans. Signal Inf. Process. Netw., 2(2):120–136, June 2016. 5. Hamid Reza Feyzmahdavian and Mikael Johansson. Asynchronous iterations in optimization: New sequence results and sharper algorithmic guarantees. Journal of Machine Learning Research, 24(158):1–75, 2023. 6. Hadrien Hendrikx, Francis Bach, and Laurent Massoulie. An optimal algorithm for decentralized finite-sum optimization. SIAM Journal on Optimization, 31(4):2753–2783, 2021. 7. D. Jakovetic, J. M. F. Moura, and J. Xavier. Linear convergence rate of a class of distributed augmented lagrangian algorithms. IEEE Trans. Autom. Control, 60(4):922–936, April 2015. 8. Dusan Jakovetic. A Unification and Generalization of Exact Distributed First-Order Methods. IEEE Trans. Signal Inf. Process. Netw., 5(1):31–46, 2019. 9. Cassio G Lopes and Ali H Sayed. Diffusion Least-Mean Squares Over Adaptive Networks: Formulation and Performance Analysis. IEEE Trans. Signal Process., 56(7):3122–3136, 2008. 10. A. Nedić and A. Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Trans. Autom. Control, 54(1):48–61, January 2009. 11. Angelia Nedić, Alex Olshevsky, and Michael G. Rabbat. Network topology and communication-computation tradeoffs in decentralized optimization. Proc. IEEE, 106(5):953–976, 2018. 12. Angelia Nedic, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27(4):2597–2633, 2017. 13. A. Olshevsky and J. Tsitsiklis. Convergence speed in distributed consensus and averaging. SIAM REVIEW, 53(4):747–772, 2011.

Graph Decomposition in Decentralized Optimization via Message Passing

55

14. Guannan Qu and Na Li. Harnessing Smoothness to Accelerate Distributed Optimization. IEEE Control Netw. Syst., 5(3):1245–1260, 2018. 15. Ali H. Sayed. Adaptation, learning, and optimization over networks. Foundations and Trends in Machine Learning, 7(4-5):311–801, 2014. 16. Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In Doina Precup and Yee Whye Teh, editors, Proc. of the 34th International Conference on Machine Learning, volume 70 of Proc. of Machine Learning Research, pages 3027–3036, International Convention Centre, Sydney, Australia, 06–11 Aug 2017. PMLR. 17. Gesualdo Scutari and Ying Sun. Distributed nonconvex constrained optimization over time-varying digraphs. Mathematical Programming, 176(1–2):497–544, 2019. 18. Wei Shi, Qing Ling, Gang Wu, and Wotao Yin. On the linear convergence of the ADMM in decentralized consensus optimization. IEEE Transactions on Signal Processing, 62(7):1750–1761, 2014. 19. Wei Shi, Qing Ling, Gang Wu, and Wotao Yin. EXTRA: An exact first-order algorithm for decentralized consensus optimization. SIAM Journal on Optimization, 25(2):944–966, 2015. 20. Ying Sun, Gesualdo Scutari, and Amir Daneshmand. Distributed optimization based on gradient tracking revisited: Enhancing convergence rate via surrogation. SIAM Journal on Optimization, 32(2):354–385, 2022. 21. R. Xin, S. Pu, A. Nedic, and U. Khan. A general framework for decentralized optimization with first-order methods. Proc. IEEE, 108(11):1869–1889, 2020. 22. J. Xu, S. Zhu, Y. C. Soh, and L. Xie. Augmented distributed gradient methods for multiagent optimization under uncoordinated constant stepsizes. In Proc. of the 54th IEEE Conference on Decision and Control (CDC 2015), pages 2055–2060, Osaka, Japan, Dec. 2015. 23. Kun Yuan, Qing Ling, and WOTAO Yin. On the Convergence of Decentralized Gradient Descent. SIAM J. Optim., 26(3):1835–1854, January 2016. 24. Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3):1835–1854, 2016.

Related documents

• From Mixing to Tearing: Graph Decomposition in Decentralized Optimization via Message Passing#1188420
• Fair Division of Graphs: Beyond Traceability#799152
• Fair Division of Graphs: Beyond Traceability#797729
• Polynomial Lower Bounds for Distributed Graph Sketching with Tiny Error: Connectivity and Spanning Tree Construction#973425
• Equalizing Closeness Centralities via Edge Additions#1198809