PaperlayerView exact revision on arXiv

Source-linked AI summary

DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers

Aryan Mokhtari, Wei Shi, Qing Ling, Alejandro Ribeiro

arXiv:1508.02073v1math.OC

TL;DR

Decentralized consensus optimization requires network nodes to minimize a shared objective using local costs and neighbor exchanges, but DADMM's exact optimization at each iteration can be costly. DQM substitutes a quadratic approximation, retaining convergence behavior close to DADMM while reducing runtime in the reported logistic-regression experiment.

  • Problem

    DADMM converges linearly for decentralized consensus optimization, but solving a convex optimization problem at every iteration can make its computational cost and overall convergence time large.

    Source: §I · p. 1

  • Method

    DQM replaces DADMM's exact per-iteration minimization with a quadratic approximation of the primal objective around the current iterate.

    Source: §I · p. 1, §III · p. 3

  • Results

    At relative error ∥xk − x∗∥/∥x0 − x∗∥ = 10^-10, DQM required 0.4 seconds, compared with 3.6 seconds for DADMM and 1.3 seconds for DLM; DQM and DADMM convergence paths were almost identical in the reported experiment.

    Source: A. Comparison of DLM, DQM, and DADMM · p. 7

  • Takeaways & Limitations

    In the reported logistic-regression problem, DQM combined computationally cheaper iterations with convergence paths similar to DADMM.

    Source: A. Comparison of DLM, DQM, and DADMM · p. 7, §VI · p. 8

Abstract

from arXiv · show

This paper considers decentralized consensus optimization problems where nodes of a network have access to different summands of a global objective function. Nodes cooperate to minimize the global objective by exchanging information with neighbors only. A decentralized version of the alternating directions method of multipliers (DADMM) is a common method for solving this category of problems. DADMM exhibits linear convergence rate to the optimal objective but its implementation requires solving a convex optimization problem at each iteration. This can be computationally costly and may result in large overall convergence times. The decentralized quadratically approximated ADMM algorithm (DQM), which minimizes a quadratic approximation of the objective function that DADMM minimizes at each iteration, is proposed here. The consequent reduction in computational time is shown to have minimal effect on convergence properties. Convergence still proceeds at a linear rate with a guaranteed constant that is asymptotically equivalent to the DADMM linear convergence rate constant. Numerical results demonstrate advantages of DQM relative to DADMM and other alternatives in a logistic regression problem.

I. INTRODUCTION

Decentralized consensus optimization lets network nodes minimize a shared objective using local costs and neighbor exchanges. DQM seeks DADMM-like convergence with less expensive iterations by replacing exact minimization with a quadratic approximation.

I. INTRODUCTION

  • The analysis assumes twice-differentiable, strongly convex local costs, and the paper situates these problems in areas including decentralized control, wireless communication, sensor networks, and large-scale machine learning.The paper expands results preliminarily reported in.Source: §I · p. 1
  • Dual methods such as DADMM generally require solving a convex optimization problem per iteration, making iterations costlier but reducing the number needed to converge.Primal methods instead compute local gradients and Hessians at each iteration.Source: §I · p. 1
  • DLM replaces ADMM's convex minimization with a first-order linear approximation, yielding gradient-like per-iteration cost and convergence properties closer to DADMM than DGD.DQM builds on this approximation strategy with a second-order model.Source: §I · p. 1
  • DQM minimizes a quadratic approximation of the per-iteration problem solved exactly by DADMM, with convergence properties better than DLM and asymptotically identical to DADMM.The paper evaluates these claims analytically and practically.Source: §I · p. 1

II. DISTRIBUTED ALTERNATING DIRECTIONS METHOD OF MULTIPLIERS

DADMM applies ADMM to a consensus formulation in which each node's local variable is tied to its neighbors through edge variables. DLM avoids DADMM's costly exact primal update by using a regularized first-order approximation.

II. DISTRIBUTED ALTERNATING DIRECTIONS METHOD OF MULTIPLIERS

  • Connected-network constraints equate each node's local variable with its neighbors' edge variables, making feasibility equivalent to all local variables agreeing and preserving the original global optimum.The global objective is the sum of node-local costs.Source: §II · p. 2
  • DADMM alternates minimization over primal and auxiliary variables, then updates the Lagrange multiplier by dual ascent; its matrix structure supports distributed implementation.Its primal update requires solving an optimization problem, while the auxiliary-variable and multiplier updates are not computationally costly.Source: §II · p. 2
  • DLM replaces DADMM's exact primal minimization with a regularized linear approximation around the current iterate, producing a quadratic update solvable by inverting a positive-definite matrix.That update can also be implemented in a distributed manner.Source: §II · pp. 2–3
  • DLM converges linearly, but its convergence constant is smaller than DADMM's and can be much smaller depending on local-function conditioning, motivating a second-order approximation.This second-order approach is the paper's DQM method.Source: §II · p. 3

III. DQM: DECENTRALIZED QUADRATICALLY APPROXIMATED ADMM

DQM replaces DADMM's exact primal minimization with a quadratic model of the objective at the current iterate. Its reduced recursions support distributed updates, while its iterations cost less than DADMM's and its convergence improves on DLM's.

III. DQM: DECENTRALIZED QUADRATICALLY APPROXIMATED ADMM

  • DQM approximates the primal objective locally with its gradient and Hessian at the current iterate, then uses this second-order model in place of DADMM's exact primal minimization.Unlike DLM's first-order model, DQM uses the objective's second-order approximation for a more accurate approximation of f(x).Source: §III · p. 3
  • The DQM primal update solves a linear system involving the Hessian and ADMM constraint term, with invertibility supported by the assumed strong convexity of f.DQM retains DADMM's auxiliary-variable and multiplier updates.Source: §III · p. 3
  • Under Assumption 1, the multipliers are opposites and the auxiliary variables can be recovered from the primal variables, allowing a reduced recursion in φ.The recursion eliminates z and reduces the dual-state dimension from twice the number of edges to the number of nodes; φ0 = 0 is a valid initialization.Source: §III · pp. 3–4
  • DQM's reduced recursion can be implemented locally because its matrix inverse is block diagonal and its Laplacian products require only neighbor information exchanges.Each node's diagonal block uses its degree and local Hessian.Source: §III · p. 4
  • DQM converges strictly faster than DLM, while its per-iteration improvements become identical to DADMM's asymptotically, yielding DADMM-like iteration counts at lower computational cost.DQM iterations evaluate local Hessians and invert local matrices, so they cost more than DLM iterations but less than DADMM iterations except when its exact subproblem is easy.Source: §III · p. 4

IV. CONVERGENCE ANALYSIS

The analysis establishes linear convergence of DQM under network and objective-function assumptions, with the primal iterates converging R-linearly. It also shows that the quadratic-approximation error vanishes as consecutive iterates approach one another, eventually at quadratic order in their difference.

IV. CONVERGENCE ANALYSIS

  • The analysis assumes a non-bipartite network and twice-differentiable local objectives with Hessian eigenvalues bounded between positive constants and Lipschitz-continuous Hessians.The incidence-matrix condition in Assumption 2 implies the graph is non-bipartite.Source: §IV · p. 4
  • The DQM approximation error is bounded by linear and quadratic terms in the consecutive-iterate difference and eventually scales quadratically, so it vanishes faster than that difference.This follows as the iterate difference approaches zero.Source: §IV · p. 5
  • The DQM and DADMM updates differ in the primal optimality condition only by DQM’s gradient-approximation error; their auxiliary and dual updates are identical.DQM approximates the gradient at the next iterate using the current gradient and Hessian.Source: §IV · p. 5
  • DQM’s energy distance to the optimal auxiliary variables and multipliers converges linearly under the theorem’s parameter conditions.The theorem requires c > 4M^2/(mγ_u^2) and chooses η_k within (ζ_k/m, cγ_u^2/ζ_k).Source: §IV · pp. 5–6
  • The primal squared distance to the optimum converges R-linearly, although it need not decrease monotonically at every iteration.Its convergence is dominated by a linearly decreasing sequence.Source: §IV · p. 6

A. Convergence rates comparison

DQM’s convergence constant approaches DADMM’s asymptotic constant, while DLM has a smaller linear-convergence constant than DQM. The comparison also examines how the methods’ approximation errors vanish.

A. Convergence rates comparison

  • As DQM’s iterates converge, successive-iterate differences approach zero, so the bound ζk also converges to zero.ζk is bounded above by (L/2)∥xk+1 − xk∥.Source: A. Convergence rates comparison · p. 6
  • DQM’s linear-convergence constant approaches the constant for DADMM as time passes.The limit of DQM’s δk is identical to DADMM’s linear-convergence constant.Source: A. Convergence rates comparison · p. 6
  • The DLM gradient-approximation error vanishes at the rate of the successive-iterate difference, whereas the supplied comparison introduces DQM’s error without specifying its rate.The comparison identifies the DLM error’s rate as ∥xk+1 − xk∥.Source: A. Convergence rates comparison · p. 6
  • The DLM analysis states that a quantity eventually becomes proportional to the squared successive-iterate difference and connects this behavior to failure to match DADMM’s convergence behavior.The passage’s subject is truncated, so the proportionality claim is reported without assigning it to a specific error quantity.Source: A. Convergence rates comparison · p. 6
  • C generated by DLM converges linearly to 0, with a linear-convergence constant of 1/(1 + δ), smaller than DQM’s constant of 1/(1 + δk) in the cited comparison.Source: A. Convergence rates comparison · p. 6

V. NUMERICAL ANALYSIS

The numerical analysis evaluates DADMM, DQM, and DLM on decentralized logistic regression. Its supplied figure captions report similar iteration-wise convergence paths for DQM and DADMM, and lower computational cost for DQM in the runtime comparison.

V. NUMERICAL ANALYSIS

  • The experiment studies logistic regression, estimating a linear classifier from labeled training samples distributed across network nodes.The model estimates P(y = 1 | s) = 1/(1 + exp(−sT ˜x)).Source: §V · p. 6
  • DQM and DADMM have similar relative-error convergence paths and outperform DLM by orders of magnitude in the n = 10 network comparison.The figure plots relative error against iterations for a random network of size n = 10.Source: Figure 1 · p. 7
  • The runtime comparison reports lower computational cost for DQM than for DADMM and DLM.Fig. 2 plots relative error against runtime for the setting in Fig. 1.Source: Figure 2 · p. 7
  • The experiments use centrally precomputed ground-truth logistic classifiers as the reference optimum.The passage identifies these classifiers as the reference for all experiments in the section.Source: §V · p. 7

A. Comparison of DLM, DQM, and DADMM

In logistic-regression tests, DQM follows DADMM closely while requiring less computation, and it outperforms DLM in the reported settings. The comparison covers iteration counts and runtime, including a larger network.

A. Comparison of DLM, DQM, and DADMM

B. Effect of the regularization parameter c

The parameter c affects DQM convergence, and its best tested value depends on the problem setting. In the reported test, c = 0.8 performs best among four choices.

B. Effect of the regularization parameter c

C. Effect of network topology

The paper tests DQM on random graphs with different connectivity ratios and reports faster linear convergence as connectivity increases. The tested graphs use different optimal c values.

C. Effect of network topology

  • DQM's linear convergence accelerates as graph connectivity ratio increases.The tested ratios are 0.2, 0.3, 0.4, and 0.6.Source: C. Effect of network topology · p. 8, Figure 6 · p. 8
  • With other parameters held as in Fig. 1, DQM’s linear convergence accelerates as connectivity ratio increases across 0.2, 0.3, 0.4, and 0.6; optimal c choices vary across these graphs.Source: C. Effect of network topology · p. 8
  • The topology experiment generates random graphs with different numbers of edges by varying the probability that two nodes are connected.The study relates incidence-matrix singular-value bounds to network connectivity.Source: C. Effect of network topology · p. 8

VI. CONCLUSIONS

The conclusion presents DQM as a quadratic-approximation alternative to DADMM for decentralized optimization. It reports linear convergence under mild assumptions and similar large-iteration convergence paths with significantly lower computational complexity in logistic regression.

VI. CONCLUSIONS

  • DQM minimizes a quadratic approximation of the convex problem that DADMM solves exactly at each step, reducing DADMM's computational complexity.Source: §VI · p. 8
  • Under mild assumptions, DQM's generated sequence converges linearly, with its convergence constant approaching DADMM's asymptotically.Source: §VI · p. 8
  • In logistic regression, DQM and DADMM have similar convergence paths for large iteration indices, while DQM has significantly smaller computational complexity.Source: §VI · p. 8

APPENDIX A PROOF OF LEMMA 1

These appendices establish the DQM iterate relations, derive an equivalent update form, and bound Hessian and gradient errors used in later analysis.

APPENDIX A PROOF OF LEMMA 1

  • Lemma 1 establishes that the multipliers remain opposites and the primal iterates satisfy E_u x_k = 2z_k for all k ≥ 0.The proof also shows α_k remains in the column space of E_o, using the initial conditions in Assumption 1.Source: Appendix A · pp. 8–9

APPENDIX B PROOF OF PROPOSITION 1

  • The proof rewrites the DQM primal update using Laplacian matrices and φ_k = E_o^T α_k, recovering the first update in (14).It uses E_u x_k = 2z_k to replace the auxiliary-variable difference with a term involving L_u(x_{k+1} − x_k).Source: Appendix B · p. 9

APPENDIX C PROOF OF LEMMA 2

  • The proof of Lemma 2 uses block-diagonal Hessian structure and Hessian Lipschitz continuity to obtain the bound in (20).It removes a maximization over v and expresses the squared norm of the aggregate iterate difference as the sum of local squared norms.Source: Appendix C · pp. 9–10

APPENDIX D PROOFS OF PROPOSITIONS 2 AND 3

  • The proofs of Propositions 2 and 3 bound gradient differences using the fundamental theorem of calculus, Hessian Lipschitz continuity, and an upper Hessian eigenvalue bound.These bounds yield the claims in (22) and (35).Source: Appendix D · p. 10

APPENDIX E PROOF OF LEMMA 3

This appendix connects the DQM and DLM iterates to the optimization problem’s KKT conditions and establishes their shared relations to optimal variables.

APPENDIX E PROOF OF LEMMA 3

  • The proof treats DQM and DLM together by using a general error vector, substituting each algorithm’s error term to obtain its respective lemma.The multiplier update and incidence-matrix definitions are used to express the primal optimality condition in a common form.Source: Appendix E · pp. 10–11
  • Lemma 5 expresses the optimization problem’s KKT conditions and derives the corresponding relations among the optimal multiplier, primal variable, and auxiliary variable.The proof uses α* = −β* to decompose the consensus constraint into relations involving E_o and E_u.Source: Appendix E · pp. 10–11
  • The appendix establishes the shared lemma claims for DQM and DLM, including relations between their iterates and the optimal variables.The proof invokes the multiplier and primal-variable relations from Lemma 1 and the optimal relations from Lemma 5.Source: Appendix E · pp. 10–11

APPENDIX F PROOFS OF THEOREMS 1 AND 2

The appendix proves linear convergence claims for DQM and DLM by deriving sufficient conditions on the error and algorithm parameters. It then applies those conditions to the respective parameter choices in the theorems.

APPENDIX F PROOFS OF THEOREMS 1 AND 2

  • Lemma 6 gives a sufficient condition for linear convergence of the weighted distance ∥u_k − u*∥²_C under Assumptions 1–4 and positive δ_k.The proof shows that the theorem’s choice of δ_k satisfies this condition.Source: Appendix F · pp. 11–13
  • The proof bounds the DQM error term and iterate differences using singular-value bounds for E_u and E_o, then checks that δ_k makes the resulting inequality hold.The bounds use β_k and graph-matrix singular-value limits to relate iterate changes to the terms in the convergence condition.Source: Appendix F · pp. 12–13
  • Choosing δ_k as in (99) establishes linear convergence for DQM and DLM, with the linear constants in (31) and (37), respectively.The proof substitutes ζ_k for the DQM coefficient and ρ + M for the DLM coefficient.Source: Appendix F · pp. 11, 13

Related papers

Loading 1508.02073v1…