PaperlayerView exact revision on arXiv

Source-linked AI summary

Communication-efficient ADMM over Hierarchical Networks

Binh Nguyen, Shuangqing Wei, Truong X. Nghiem

arXiv:2609.09361v2math.OCcs.SYeess.SY

TL;DR

Hierarchical tree networks pose coordination and communication challenges, and existing ADMM approaches can incur communication overhead. hADMM rearranges the augmented Lagrangian to use local tree-structured exchanges; experiments report improved communication efficiency, with reduced TotalVals relative to fADMM.

  • Problem

    Hierarchical networks have parent–child relationships and asymmetric information flows that complicate coordination, scalability, and communication efficiency.

    Source: §I · p. 1

  • Method

    hADMM rearranges the augmented Lagrangian so nodes exchange information locally through a top-down primal pass and a bottom-up dual pass.

    Source: B. Hierarchical ADMM (hADMM) algorithm · p. 5

  • Results

    D = 3 to D = 5, hADMM’s TotalVals reduction versus fADMM becomes increasingly pronounced; the paper also reports superior communication efficiency to nADMM.

    Source: §I · p. 2, A. Disjoint problems over randomized… · p. 8

  • Takeaways & Limitations

    The paper concludes that hADMM solves general tree-structured problems in a fully distributed manner with substantially reduced communication costs.

    Source: §VI · p. 10

    The considered setting is a fixed bidirectional tree; extending hADMM beyond it, including to time-varying links, is future work.

    Source: §VI · p. 10

Abstract

from arXiv · show

This paper develops a novel distributed optimization algorithm based on the Alternating Direction Method of Multipliers (ADMM) to solve hierarchical optimization problems over tree-structured networks, termed hierarchical ADMM (hADMM), with a particular focus on enhancing communication efficiency across the network. By rearranging the augmented Lagrangian to establish a query-response communication mechanism between nodes that explicitly exploits the hierarchical tree structure, the proposed algorithm significantly reduces communication costs compared to existing ADMM-based methods for hierarchical optimization. Furthermore, hADMM guarantees asymptotic convergence under convexity assumptions. We also present a convergence rate analysis based on linear matrix inequalities to characterize the maximum theoretically achievable convergence rates across different network topologies, showing that the proposed hADMM attains linear convergence under mild conditions. Three numerical experiments demonstrate that hADMM is compatible with arbitrary tree network structures and outperforms existing approaches in terms of communication efficiency.

I. INTRODUCTION

Hierarchical networks create coordination and communication challenges that standard ADMM-based approaches do not fully avoid. The paper introduces hADMM, which exploits tree structure for distributed optimization and establishes convergence guarantees under convexity assumptions.

I. INTRODUCTION

  • Hierarchical parent–child relationships and asymmetric information flows complicate coordination, scalability, and communication efficiency.The introduction identifies these challenges as motivating structure-aware distributed optimization.Source: §I · p. 1
  • Nested ADMM recursively solves each tree layer, while flattened ADMM relays messages through the root; both incur communication overhead.The nested method uses multiple loops, with subtree query-response rounds inside outer iterations.Source: §I · p. 1, C. Nested ADMM (nADMM) algorithm · p. 3
  • hADMM exploits arbitrary tree structures and reduces network communication costs relative to nested and flattened ADMM.Nodes exchange queries top-down and primal responses bottom-up, communicating only with parents and children.Source: §I · p. 2
  • hADMM is guaranteed to converge under general convexity assumptions, including when cost functions are nonsmooth.Source: §I · p. 2

A. Hierarchical optimization over tree networks

II. PROBLEM FORMULATION AND RELATED LITERATURE

  • The general model assigns each node a decision vector and convex cost, with constraints relating each child’s variables to its parent’s.The parent–child constraints are expressed using matrices and a vector.Source: A. Hierarchical optimization over tree… · p. 3

B. Disjoint problems over tree networks

  • In the disjoint problem, each parent’s decision vector concatenates its children’s vectors in index order.The coupling constraints specialize to concatenation, with matrices selecting each child’s variables.Source: B. Disjoint problems over tree networks · p. 3

C. Nested ADMM (nADMM) algorithm

  • Nested ADMM treats each subtree as one node for its parent’s optimization and runs a separate ADMM loop at each tree level.Inner query-response rounds solve subtree minimizations before returning responses to the root.Source: C. Nested ADMM (nADMM) algorithm · p. 3

D. Flattened ADMM (fADMM) algorithm

The section contrasts flattened and nested ADMM baselines with hADMM, which uses the tree structure for local communication and computation. Its augmented-Lagrangian reformulation supports parent–child updates in a forward and backward pass.

D. Flattened ADMM (fADMM) algorithm

  • fADMM flattens the hierarchical objective into a star-topology ADMM formulation, while data still travel along the tree through relaying nodes.It is presented as a direct baseline that ignores the hierarchy in the optimization formulation.Source: D. Flattened ADMM (fADMM) algorithm · p. 3

E. Communication and computation of nADMM and fADMM

  • nADMM uses recursive inner solves, while fADMM relies on multi-hop relays; both incur communication costs, with nADMM’s total costs higher in the stated comparison.In the example, fADMM uses 9 local solves and 26 transmissions per iteration; nADMM requires at least 6 + 4T2,1 + 6T2,3 transmissions.Source: E. Communication and computation of… · p. 4

III. HIERARCHICAL ADMM (HADMM) ALGORITHM

  • hADMM follows the network tree for computation and communication, with savings compared to nADMM and fADMM.The paper proposes it for hierarchical optimization over tree-structured networks.Source: §III · p. 4

A. Augmented Lagrangian function

  • The augmented Lagrangian is rearranged by tree layer, with parent–child constraints combined into aggregate constraints.The aggregate constraint links a parent’s variable with the variables of its children.Source: A. Augmented Lagrangian function · p. 4

B. Hierarchical ADMM (hADMM) algorithm

  • hADMM updates primal variables top-down and dual variables bottom-up, keeping each node’s updates and communications local to its parent and children.Each iteration uses one top-down primal pass and one bottom-up dual pass, without nested lower-level ADMM solves.Source: B. Hierarchical ADMM (hADMM) algorithm · pp. 4–5

C. Stopping criterion

The section describes a distributed query-response mechanism and summarizes the assumptions used to analyze hADMM’s convergence. It reports a linear convergence-rate result.

IV. CONVERGENCE ANALYSIS OF HADMM

  • Theorem 3 reports a linear convergence rate for hADMM.Table II is identified as summarizing scenarios and convergence results, but the supplied passage does not provide its entries.Source: C. Stopping criterion · p. 6, Table II · p. 6

C. Stopping criterion

  • A child updates its variable upon receiving a query and returns it, allowing nodes at the same level to solve without waiting for one another.Parents store edge constraint parameters and dual variables, send queries forward, and receive child variables in the backward pass.Source: C. Stopping criterion · p. 6

IV. CONVERGENCE ANALYSIS OF HADMM

  • The convergence analysis considers scenarios including convex objectives with full-column-rank constraint matrices and differentiable strongly convex objectives.The paper states that its scenarios are based on assumptions commonly used in the literature.Source: §IV · p. 6

A. Convergence of hADMM

The paper establishes convergence guarantees for hADMM under stated convexity scenarios. It also gives a linear-rate result under a stricter scenario and an SDP feasibility condition.

A. Convergence of hADMM

  • Under Scenario 1, the sequence produced by Algorithm 1 is bounded, primal residuals r_k^d tend to 0 for all d in ND−1, and every cluster point belongs to O⋆.If O⋆ is a singleton, the whole sequence converges to its unique point.Source: A. Convergence of hADMM · p. 6
  • Under Scenario 2, the primal sequence converges to the unique minimizer.The stated convergence result is for the differentiable strongly convex scenario.Source: A. Convergence of hADMM · p. 6

B. Convergence rate of hADMM

  • Under the stricter Scenario 3, hADMM has a linear convergence rate when the theorem’s semidefinite program is feasible.Scenario 3 assumes strong convexity and Lipschitz-continuous gradients for f2 through fD.Source: B. Convergence rate of hADMM · p. 6

2. Then, ˆV k satisfies

This section gives an SDP-feasibility condition relevant to linear-rate design and evaluates hADMM on randomized disjoint problems and a hierarchical power-sharing case.

2. Then, ˆV k satisfies

  • Under Scenario 3 and Theorem 3's parameter choices, full row rank of the block lower-bidiagonal matrix is sufficient for SDP (17) to be feasible.The SDP maximizes a lower bound on the linear convergence-rate parameter γ⋆ with respect to network structure, constraints, and penalty parameter ρ.Source: §2 · p. 7

A. Disjoint problems over randomized tree networks

  • The disjoint-problem tests use three network configurations, each evaluated over 1,000 randomized tree topologies, with convex local costs that are not strongly convex.Penalty parameters were manually tuned per method and topology to achieve fastest convergence at εabs = 10^-4.Source: A. Disjoint problems over randomized… · p. 7
  • Across 1,000 randomized tree networks with (D = 3, N = 10), hADMM's optimality gap converges to zero as iterations increase, including for nonsmooth costs.This supports the convergence result established in Theorem 1.Source: A. Disjoint problems over randomized… · p. 7, Figure 2 · p. 8
  • fADMM has the fewest iterations, but its communication costs exceed hADMM's because lower-layer messages are relayed along paths to the root; nADMM has the highest iteration and communication costs.The TotalVals advantage of hADMM over fADMM becomes more pronounced as depth increases from D = 3 to D = 5.Source: A. Disjoint problems over randomized… · pp. 7–8, Figure 3 · p. 8
  • At comparable objective-gap levels, hADMM transmits fewer values than fADMM, with a larger advantage as network depth grows from D = 3 to D = 5.The comparison averages normalized optimality gaps over 1,000 randomized tree topologies.Source: A. Disjoint problems over randomized… · p. 8, Figure 4 · p. 8

B. Power sharing problem

  • The power-sharing example models a utility, aggregators, and clusters as root, parent nodes, and leaves, respectively.The utility coordinates consumption to track a desired load profile while minimizing costs and satisfying constraints at each hierarchy level.Source: B. Power sharing problem · pp. 8–9
  • In the power-sharing experiment, hADMM's optimality gap and primal residual converge, and its communication cost is significantly lower than nADMM's and fADMM's.The experiment uses nonsmooth, not strongly convex cost functions.Source: B. Power sharing problem · p. 9, Table V · p. 9

C. Convergence rate of hADMM for different topologies

Across two tree topologies with the same numbers of levels and nodes, hADMM’s observed contraction was faster for the topology with the higher theoretical rate parameter. The conclusion reports reduced communication costs and convergence guarantees under convexity assumptions, while identifying extensions beyond fixed bidirectional trees as future work.

C. Convergence rate of hADMM for different topologies

  • The experiment compares two topologies with the same numbers of levels and nodes; one balances levels 2 and 3, while the other has most nodes at the lowest level.The optimal consensus problem uses strongly convex costs, and the same initialization is used across the topologies.Source: Figure 6 · p. 9, C. Convergence rate of hADMM for… · p. 9
  • 33 iterations versus 104 were required for Topology 1 (γ⋆=0.097) and Topology 2 (γ⋆=0.023), respectively, with the higher-rate topology contracting more than three times as fast.The plotted dashed upper bounds validate the Lyapunov contraction rates (18).Source: C. Convergence rate of hADMM for… · p. 9, Figure 7 · p. 10

VI. CONCLUSION

  • The conclusion attributes hADMM’s reduced communication costs to reformulating the augmented Lagrangian to exploit tree structure, and establishes convergence guarantees under convexity assumptions.Future work will extend beyond fixed bidirectional trees to time-varying links, asynchronous updates, and unreliable communication with delays or packet losses.Source: §VI · p. 10

APPENDIX A THE GENERAL NADMM ALGORITHM

The appendix presents nADMM as a recursive application of ADMM to subtrees. It aggregates each subtree’s variables, objective, and constraints, then applies the same algorithm recursively at parent nodes.

APPENDIX A THE GENERAL NADMM ALGORITHM

  • Each subtree is represented by an aggregate variable vector, aggregate objective, and recursively split constraints linking parent and child nodes.For a leaf node, the aggregate variable is just that node’s variable, and its aggregate objective is its local cost.Source: Appendix A · p. 10
  • The reformulated subtree problem is solved using standard ADMM iterations, and the same procedure is applied recursively to parent subproblems.The appendix names this recursive procedure nested ADMM (nADMM).Source: Appendix A · p. 10
  • At a leaf, nADMM returns a minimizer of the local objective with its supplied parameter; non-leaf nodes repeat updates and call the procedure on their children.The algorithm invokes child calls in parallel.Source: Appendix A · p. 10

APPENDIX B PROOF OF THEOREM 1

The proof develops relations between the iterates and the KKT conditions, then combines them to obtain the stated inequality. It uses convexity and the saddle-point property of the augmented Lagrangian in this argument.

APPENDIX B PROOF OF THEOREM 1

  • The proof is organized into two steps, beginning with a first-order condition for the forward-pass iterates.It invokes the generalized first-order condition and convexity to characterize the iterates as minimizers.Source: Appendix B · p. 11
  • The proof uses the saddle-point property of the augmented Lagrangian to relate its optimum value to the iterates.The cited passage states this property holds for any penalty parameter ρ.Source: Appendix B · p. 11
  • After rewriting terms in the inequality using the defined quantities, the proof sums the resulting relation across levels to obtain (32).The derivation combines the expressions in (39) and (40) with (31).Source: Appendix B · p. 11

2. Then, from (32),

The proof shows that the Lyapunov sequence is non-increasing and that its non-negative terms vanish. It then establishes that cluster points satisfy the KKT conditions, with convergence of the whole sequence when the KKT point is unique.

2. Then, from (32),

  • Because the Lyapunov sequence is non-increasing and non-negative, it converges and the non-negative terms in (41) vanish.Source: §2 · p. 11
  • The primal-dual sequence is bounded and therefore has at least one cluster point.The proof derives boundedness of the node variables using full-column-rank conditions.Source: §2 · p. 12
  • Every cluster point satisfies the KKT conditions, and if the KKT set is a singleton, the bounded sequence converges to its unique point.The proof obtains feasibility in the limit and uses closedness of the subdifferential graph to establish the KKT conditions.Source: §2 · p. 12

APPENDIX C PROOF OF THEOREM 2

The proof establishes the stated convergence under condition (44) and shows that the minimizer is unique in Scenarios 2 or 3 under Slater’s condition and strong convexity.

APPENDIX C PROOF OF THEOREM 2

  • Under (44), the stated x- and residual-related quantities tend to zero as k→∞.The proof derives (44) using strong convexity in Scenario 2.Source: Appendix C · p. 12
  • Slater’s condition and strong convexity of the objective functions imply a unique minimizer in Scenario 2 or Scenario 3.The proof identifies the block vector [x⋆_d] as that unique minimizer.Source: Appendix C · p. 12

APPENDIX D PROOF OF THEOREM 3

The proof derives the inequality used for Theorem 3 from blockwise bounds and establishes R-linear primal convergence, with strong convexity ensuring uniqueness.

APPENDIX D PROOF OF THEOREM 3

  • Lemmas 2 and 3 yield inequalities for a strongly convex function with modulus α > 0 and a differentiable convex function with Lipschitz constant L, for all z, z′ ∈ Dom(f).The resulting inequalities (48) and (49) apply for 2 ≤ d ≤ D and 1 ≤ d ≤ D, respectively.Source: Appendix D · p. 13
  • Weighted blockwise inequalities yield a matrix inequality that implies (18).The proof uses weights t and 1−t and details the blockwise identification of Ξ.Source: Appendix D · pp. 12–13
  • The resulting bound establishes R-linear primal convergence, and strong convexity ensures that the primal minimizer is unique.The proof combines the bound with inequalities (59)–(61).Source: Appendix D · p. 13

APPENDIX E PROOF OF PROPOSITION 1

The proof constructs Ξ from a four-block vector and establishes feasibility of (17) by showing that Ξ is positive definite.

APPENDIX E PROOF OF PROPOSITION 1

  • The proof forms Ξ using a four-block vector whose component blocks play the roles of specified algorithm variables.It defines coefficients a_d and w_d before deriving Ξ from the descent bound.Source: Appendix E · p. 14
  • Positive coefficients make Ξ positive semidefinite, while the zero-quadratic-form argument and full row rank of Λ establish positive definiteness.The zero-form argument first forces z_d, δ_d, and r_d to zero, then the remaining terms imply y_d=0.Source: Appendix E · p. 14
  • Positive definiteness of Ξ, together with the choice of γ, proves feasibility of (17).The proof obtains positive definiteness using full row rank of Λ.Source: Appendix E · p. 14
Loading 2609.09361v2…