PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-Agent Distributed Optimization via Inexact Consensus ADMM

Tsung-Hui Chang, Mingyi Hong, Xiangfeng Wang

arXiv:1402.6065v2eess.SYmath.OC

TL;DR

Distributed consensus ADMM can converge faster than consensus subgradient methods but may be expensive for large or structurally complicated problems. The paper develops IC-ADMM and IDC-ADMM, which use one proximal-gradient update per iteration, and reports faster convergence with significantly reduced computational complexity under stated assumptions.

  • Problem

    Distributed ADMM methods can be computationally demanding because agents repeatedly solve subproblems to global optimality, especially for complicated or large-scale problems.

  • Method

    The paper proposes IC-ADMM and IDC-ADMM, allowing agents to perform a single proximal-gradient update at each iteration instead of exactly solving the ADMM subproblems.

  • Results

    The proposed methods converge faster than consensus subgradient in numerical examples and significantly reduce computational complexity, with an order-of-magnitude reduction reported for certain problems.

  • Takeaways & Limitations

    Inexact consensus ADMM trades additional ADMM iterations for a significant reduction in per-iteration computational complexity.

Abstract

from arXiv · show

Multi-agent distributed consensus optimization problems arise in many signal processing applications. Recently, the alternating direction method of multipliers (ADMM) has been used for solving this family of problems. ADMM based distributed optimization method is shown to have faster convergence rate compared with classic methods based on consensus subgradient, but can be computationally expensive, especially for problems with complicated structures or large dimensions. In this paper, we propose low-complexity algorithms that can reduce the overall computational cost of consensus ADMM by an order of magnitude for certain large-scale problems. Central to the proposed algorithms is the use of an inexact step for each ADMM update, which enables the agents to perform cheap computation at each iteration. Our convergence analyses show that the proposed methods converge well under some convexity assumptions. Numerical results show that the proposed algorithms offer considerably lower computational complexity than the standard ADMM based distributed optimization methods.

I. INTRODUCTION

Distributed agents seek optimal solutions using only local information and neighbor messages, but standard ADMM methods can be computationally demanding. The paper proposes inexact consensus ADMM variants that use cheap proximal-gradient updates while retaining convergence guarantees under stated conditions.

  • Distributed consensus optimization requires agents to obtain a shared optimum using local information and messages exchanged with neighbors.
  • Consensus subgradient methods are simple and broadly applicable, but their convergence is usually slow.
  • C-ADMM and DC-ADMM provide parallel distributed solutions for (P1) and (P2), but repeatedly solving agent subproblems to global optimality can be computationally demanding.
  • IC-ADMM and IDC-ADMM replace exact ADMM subproblem solutions with a single proximal-gradient step at each iteration.The proximal-gradient step is usually simple when the nonsmooth functions have structured forms.
  • The proposed inexact approach approximates the smooth functions in C-ADMM, unlike known inexact ADMM methods that approximate only the quadratic penalty.
  • Under stated convexity and graph conditions, the methods have global or linear convergence results, and numerical examples report faster convergence than consensus subgradient with an order-of-magnitude lower computational cost.For (P2), DC-ADMM is described as globally solving the problem for any connected graph and convex φi’s; IC-ADMM is reported to converge linearly under similar conditions as prior work.

II. APPLICATIONS AND NETWORK MODEL

The paper formulates distributed regression and related consensus problems over connected multi-agent networks, covering LASSO and logistic regression as special cases. Its assumptions require convexity, attainment of optima, and smooth strongly convex local components, while composite objectives may still lack strong convexity.

  • Applications: The applications include row- and column-partitioned distributed regression, encompassing LASSO and logistic regression.Local agents hold partitioned data or variables and cooperate through consensus constraints.
  • Applications: In row-partitioned regression, each agent contributes a local cost Ψi(y; Ai, bi) based on local data Ai and response bi.
  • Applications: In column-partitioned regression, agents hold local variables xi and data matrices Ei while sharing the response signal b.
  • Network model: The network is modeled by a connected undirected graph whose Laplacian is L = D − W, with neighboring agents communicating along edges.
  • Assumptions: The assumptions impose proper closed convex regularizers, bounded subgradients, attained minima, and strong duality for (P2).
  • Assumptions: Although fi(Aix) is strongly convex with Lipschitz gradients, φi(x) need not be strongly convex when Ai is fat and rank deficient.

III. DISTRIBUTED CONSENSUS ADMM

Consensus ADMM updates agents in parallel and is guaranteed to converge under stated convexity assumptions, but its local subproblem can be difficult and expensive to solve accurately for large regression problems.

  • C-ADMM: C-ADMM applies ADMM to a consensus reformulation, with agents updating local variables and dual variables using information from direct neighbors.
  • Convergence: Under Assumptions 1 and 2, C-ADMM is guaranteed to converge for any penalty parameter c > 0.
  • Convergence: C-ADMM can converge linearly when the local composite functions are purely smooth and strongly convex with respect to their variables.
  • Computational challenge: For logistic regression, the C-ADMM subproblem has no simple solution because of the complicated logistic-regression cost.
  • Computational challenge: High-accuracy solution of the local subproblem becomes computationally expensive as the problem dimension or training-data count grows.
  • Computational challenge: Using a low-accuracy subproblem solution can reduce complexity but may destroy C-ADMM’s convergence behavior.

B. Proposed Inexact C-ADMM

The proposed IC-ADMM replaces difficult exact local solves with proximal-gradient updates that linearize the smooth cost while retaining a proximal treatment of the nonsmooth term. Under the stated assumptions, it achieves consensus and optimality, with linear convergence under stronger conditions.

  • Proposed method: IC-ADMM reduces C-ADMM complexity by replacing the direct subproblem solve with a proximal first-order approximation of the smooth cost.
  • Proposed method: The resulting update is a proximal-gradient step with penalty parameter βi and can admit closed-form solutions for common nonsmooth functions.
  • Proposed method: For gi(y) = ∥y∥1, the proximal update has the closed-form soft-thresholding solution.
  • Novelty: Unlike prior inexact ADMM methods that approximate only the quadratic penalty, the proposed approach also linearizes the cost function.
  • Convergence: Under Assumptions 1, 2(a), and 3, IC-ADMM’s local iterates converge to a common point y⋆.
  • Convergence: With sufficiently large βi, IC-ADMM achieves consensus and optimality and converges linearly when φi is purely smooth and strongly convex.
  • Convergence: The linear-convergence condition requires global knowledge of λmin(D + W), and its satisfaction depends on network topology.

IV. DISTRIBUTED DUAL CONSENSUS ADMM

The paper develops DC-ADMM by applying consensus ADMM to an equivalent dual formulation of (P2), while recovering primal solutions through saddle-point updates. The method is parallel, avoids per-iteration min-max solves, and converges under broader graph conditions than bipartite-only requirements.

  • DC-ADMM formulation: DC-ADMM applies C-ADMM to the dual problem and uses a min-max/saddle-point formulation to derive distributed updates.
  • DC-ADMM formulation: The inner minimizer is uniquely determined, enabling the min-max subproblem to be handled through sequential primal and dual-variable operations.
  • Convergence: Although DC-ADMM operates on the equivalent dual problem, it directly yields a primal optimal solution of (P2).
  • Convergence: The dual local copies converge to a common dual optimum, and any limit point of the primal iterates is asymptotically optimal for (P2).
  • Convergence: Primal feasibility depends on agents reaching consensus on the dual variable ν.
  • Algorithm properties: Algorithm 3 is fully parallel, avoids solving a min-max subproblem at every iteration, and converges without requiring a bipartite graph.

B. Proposed Inexact DC-ADMM

IDC-ADMM replaces the expensive DC-ADMM subproblem update with an inexact, proximal-gradient-based update. Under stated convexity and matrix-rank assumptions, the resulting iterates converge to an optimal consensus solution.

  • Method: IDC-ADMM uses an inexact update because solving the original subproblem can be expensive.The method is introduced as an inexact version of DC-ADMM to reduce update cost.
  • Method: The proposed update approximates both fi(Aixi) and the quadratic term when the matrix Ei complicates the solution.The approximation leads to a proximal-gradient update with penalty parameter βi > 0.
  • Method: When Ei has orthogonal columns, approximating the quadratic term may not be necessary.The paper gives ET i Ei = αIK as an example condition.
  • Convergence: Under Assumptions 1, 2(b), and 3, Algorithm 4 generates primal iterates that converge to an optimal solution of (P2).The theorem also imposes matrix conditions including full column rank for Ai and full row rank for Ei.
  • Convergence: The agents’ dual variables converge to a common point ν⋆ of problem (5).This establishes consensus in the dual variables under the theorem’s assumptions.
  • Convergence: IDC-ADMM requires Ei to have full row rank in addition to a smooth and strongly convex objective function for linear convergence.The paper identifies the rank requirement as an additional condition for the convergence guarantee.

V. NUMERICAL RESULTS

Numerical experiments compare standard C-ADMM with inexact IC-ADMM on distributed regression and image-classification settings. IC-ADMM generally needs more ADMM iterations, but substantially reduces computation time and can converge linearly under the tested conditions.

  • Comparison: C-ADMM with pgr < 10−4 reaches acc < 10−4 but fails to reach the cserr target 10−5.Its consensus error is reported as cserr = 3.425 × 10−4 and remains relatively high across iterations.
  • Comparison: The consensus subgradient method converges much slower than IC-ADMM in the plotted comparisons.The comparison uses a diminishing step size 10/k.
  • Scalability: 8.75 times smaller computation time is reported for IC-ADMM than C-ADMM when the network size is increased to N = 50.The comparison again uses C-ADMM with pgr < 10−5.
  • Convergence: Both C-ADMM and IC-ADMM converge linearly under the tested setting with λ = 0, N = 10, K = 25, and M = 1,000.The convergence curves are shown for the corresponding regression problem instance.

B. Performance of DC-ADMM and IDC-ADMM

The experiments compare DC-ADMM with its inexact counterpart IDC-ADMM on distributed regression problems. IDC-ADMM uses cheaper updates, requiring more ADMM iterations but substantially less computation time.

  • Experimental setup: DC-ADMM and IDC-ADMM were evaluated on distributed CPD LR problems with constrained variables and generated regression data.The setup uses Ψ_i(x_i; E_i, b), g_i(x_i)=λ∥x_i∥_1, and bounded coordinate constraints.
  • Convergence and computation: 329 versus 10,814 ADMM iterations were required to achieve acc < 10^-4 for DC-ADMM and IDC-ADMM, respectively.The DC-ADMM comparison uses pgr < 10^-5.
  • Convergence and computation: 22.28 times higher computation time was required by DC-ADMM than IDC-ADMM in the reported comparison.The ratio is computed as 42.78/1.92.
  • Convergence and computation: DC-ADMM converged faster by ADMM iterations, but IDC-ADMM was faster when convergence was measured by computation time.Reducing FISTA solution accuracy to pgr < 10^-4 prevented DC-ADMM from reaching acc < 10^-4.
  • Conclusion: The conclusion reports that both proposed inexact methods converge faster than consensus subgradient while requiring more ADMM iterations than their exact counterparts.The paper characterizes the resulting computational-complexity reduction as significant.

APPENDIX A

The appendix develops optimality relations for the distributed formulation and uses graph, convexity, and matrix properties in the convergence analysis.

  • Optimality conditions: The appendix characterizes optimal primal and dual solutions through KKT conditions for the distributed problem.These conditions are combined with update relations and graph-structured matrices.
  • Proof ingredients: Strong convexity of f_i and convexity of g_i provide lower bounds used in the convergence proof.The analysis also invokes Assumption 3 and positive penalty parameters ρ_i.
  • Proof ingredients: The proof rewrites terms using stacked variables, block-diagonal matrices, the network matrix W, and diagonal parameter matrices.These transformations organize the agent-wise relations into global matrix expressions.
  • Proof ingredients: Graph symmetry and normalized-Laplacian properties support the rearrangement and bounding of consensus-related terms.The appendix applies these properties to the fourth, fifth, and sixth terms of the proof inequality.

2. Thus, in (A.16),

The appendix establishes convergence of the IC-ADMM analysis and gives sufficient conditions for linear convergence under the stated assumptions.

  • Convergence: Under condition (A.21), the proof obtains convergence of the relevant sequence for any optimal primal-dual pair and boundedness of the dual-related sequences.The appendix labels these conclusions R1 and R2.
  • Convergence: Every limit point is shown to be an optimal primal and dual solution of the distributed problem.The argument uses vanishing successive differences and the optimality relations.
  • Convergence: The proof concludes that the agent variables converge to a common optimal value.The consensus relation is obtained after the Lyapunov-type sequences converge and one component tends to zero.
  • Linear convergence: Linear convergence is proved by showing a contraction condition with some δ > 0.The derivation uses the minimum nonzero singular value of Υ and matrix inequalities involving the Lipschitz constants.
  • Linear convergence: Sufficient conditions for the contraction include inequalities involving δ, the network mapping, and the matrix ˜A^T D_Lf ˜A.The proof verifies that these conditions hold under the stated rank and parameter assumptions.
  • Linear convergence: The appendix states that the three sufficient conditions hold for some δ > 0 under the adopted assumptions.This completes the linear-convergence proof.

APPENDIX B

The appendix analyzes convergence for the second distributed problem using primal-dual optimality conditions, matrix bounds, and rank assumptions.

  • Optimality conditions: The proof begins from optimal primal and dual solutions and their associated optimality conditions.These relations are used to derive inequalities for the algorithmic iterates.
  • Proof construction: The analysis combines agent-wise updates using block-diagonal matrices, the network matrix, and weighted quadratic terms.The resulting expressions support bounds on primal and dual errors.
  • Assumptions: Under the stated parameter condition, the proof uses bounds of the form σ_f,i^2 ≤ ρ_i < 2σ_f,i^2.This condition appears in the matrix inequality argument.
  • Convergence: The appendix states convergence for optimal primal and dual solutions of the second problem and identifies limit points as optimal solutions.The argument concludes convergence of the corresponding weighted error sequence and iterates.
  • Assumptions: The proof assumes φ_i(x_i)=f_i(A_i x_i), with A_i having full column rank and E_i having full row rank.These rank conditions are used to establish finite bounds and the final sufficient inequalities.
Loading 1402.6065v2…