PaperlayerView exact revision on arXiv

Source-linked AI summary

A Decentralized Second-Order Method with Exact Linear Convergence Rate for Consensus Optimization

Aryan Mokhtari, Wei Shi, Qing Ling, Alejandro Ribeiro

arXiv:1602.00596v1math.OCcs.DC

TL;DR

Neighbor-only consensus optimization makes multiplier-based methods difficult to implement because their augmented-Lagrangian updates are nonseparable. ESOM uses a quadratic approximation and truncated Hessian-inverse expansion to obtain decentralized updates; its iterates converge linearly, with iteration and communication costs varying by truncation order.

  • Problem

    Multiplier-based consensus optimization uses a nonseparable augmented-Lagrangian update that prevents decentralized implementation.

    Source: §II · p. 4, A. Convergence of Proximal Method of… · p. 9

  • Method

    ESOM uses a separable quadratic approximation of the augmented Lagrangian and a truncated Taylor expansion to approximate its Hessian inverse.

    Source: §I · p. 2, §III · p. 5, §VI · p. 15

  • Results

    ESOM-K converges linearly for every K; larger K improves iteration convergence, while ESOM-0 is most efficient in communication cost.

    Source: §I · p. 2, §VI · p. 16

  • Takeaways & Limitations

    The truncation order offers a trade-off between faster convergence by iteration count and lower communication cost with ESOM-0.

    Source: §I · p. 2, §VI · p. 16

Abstract

from arXiv · show

This paper considers decentralized consensus optimization problems where different summands of a global objective function are available at nodes of a network that can communicate with neighbors only. The proximal method of multipliers is considered as a powerful tool that relies on proximal primal descent and dual ascent updates on a suitably defined augmented Lagrangian. The structure of the augmented Lagrangian makes this problem non-decomposable, which precludes distributed implementations. This problem is regularly addressed by the use of the alternating direction method of multipliers. The exact second order method (ESOM) is introduced here as an alternative that relies on: (i) The use of a separable quadratic approximation of the augmented Lagrangian. (ii) A truncated Taylor's series to estimate the solution of the first order condition imposed on the minimization of the quadratic approximation of the augmented Lagrangian. The sequences of primal and dual variables generated by ESOM are shown to converge linearly to their optimal arguments when the aggregate cost function is strongly convex and its gradients are Lipschitz continuous. Numerical results demonstrate advantages of ESOM relative to decentralized alternatives in solving least squares and logistic regression problems.

I. INTRODUCTION

ESOM addresses the difficulty of implementing multiplier-based consensus optimization with neighbor-only communication by using a separable approximation and a truncated Hessian-inverse expansion. The paper establishes linear convergence and reports trade-offs across iteration and communication costs.

I. INTRODUCTION

  • DGD and Network Newton converge only to a neighborhood with constant step sizes, or sublinearly to the exact optimum with diminishing step sizes.The paper also notes that decentralized ADMM variants are known to converge linearly under strong convexity and Lipschitz-continuous gradients.Source: §I · pp. 1–2

II. PROXIMAL METHOD OF MULTIPLIERS

  • PMM uses primal minimization and dual ascent on an augmented Lagrangian, but its quadratic augmentation prevents distributed computation of primal gradients.The paper uses PMM as the basis for its decentralized approximation.Source: §I · p. 2, §II · pp. 3–4

I. INTRODUCTION

  • ESOM replaces the nonseparable proximal augmented-Lagrangian minimization with a separable quadratic approximation and a truncated Taylor expansion of the Hessian inverse.The truncation yields ESOM-K methods whose performance penalty relative to centralized PMM vanishes with increasing iterations.Source: §I · p. 2, §II · p. 4
  • The experiments report faster convergence than EXTRA, Network Newton, and DADMM, while larger K improves iteration counts and ESOM-0 is most efficient in communication exchanges.The comparisons cover decentralized least-squares and logistic-regression problems.Source: §I · p. 2

II. PROXIMAL METHOD OF MULTIPLIERS

  • The PMM primal update is computationally costly and nonseparable because its augmentation term couples nodes, preventing neighbor-only implementation.The proximal term keeps iterates close to the previous iterate and improves computational stability without affecting convergence guarantees.Source: §II · p. 4

III. ESOM: EXACT SECOND-ORDER METHOD

ESOM approximates the PMM primal update with a quadratic model, then replaces the generally nonlocal Hessian inverse with a truncated, neighbor-sparse approximation. This produces updates designed for decentralized implementation.

III. ESOM: EXACT SECOND-ORDER METHOD

  • ESOM substitutes a second-order Taylor approximation of the augmented Lagrangian into the PMM primal update, yielding a positive-definite quadratic minimization.The resulting update uses the inverse of the quadratic model's Hessian.Source: §III · p. 4
  • Although the Hessian is block neighbor sparse, its inverse is not, so the exact inverse-based update cannot be implemented using only neighbor exchanges.The Hessian's sparsity follows from the block-diagonal local objective Hessians and the neighbor-sparse network matrix.Source: §III · pp. 4–5
  • ESOM-K replaces the Hessian inverse with a K-hop block neighbor-sparse approximation formed by truncating its Taylor series after K + 1 terms.The approximation uses local operations rather than global communication to compute the series.Source: §III · p. 5
  • ESOM retains PMM's dual update while its primal update differs by approximating both the augmented Lagrangian and its Hessian inverse.The inverse approximation is the step that makes the update suitable for decentralized implementation.Source: §III · p. 5

A. Decentralized implementation of ESOM

The implementation eliminates the non-neighbor-sparse square-root matrix from ESOM's updates by transforming the dual variables and computing descent directions through neighbor exchanges. The truncation order controls the number of communication rounds used to form those directions.

A. Decentralized implementation of ESOM

  • Defining q_t = (I − Z)^(1/2)v_t rewrites ESOM's primal-dual updates without the non-neighbor-sparse square-root matrix, enabling neighbor-only computation.The rewritten updates generate the same primal iterates as the original updates.Source: A. Decentralized implementation of ESOM · pp. 5–6
  • Each node computes its initial descent direction locally, then exchanges directions with neighbors for K rounds to form its ESOM-K direction.Nodes subsequently exchange updated primal variables with neighbors for the dual update.Source: A. Decentralized implementation of ESOM · p. 6
  • ESOM and Network Newton use approximate decentralized Newton directions for different objectives: the augmented Lagrangian and a penalized objective, respectively.The penalized objective's optimum differs from the consensus optimum by a distance of order O(1/α).Source: A. Decentralized implementation of ESOM · p. 7
  • A first-order approximation of PMM recovers EXTRA for specific choices of α and ϵ, whereas ESOM uses second-order information.The paper expects faster convergence for ESOM relative to EXTRA and studies that comparison in its experiments.Source: A. Decentralized implementation of ESOM · pp. 7–8

IV. CONVERGENCE ANALYSIS

The section studies linear convergence of PMM and ESOM under twice-differentiable local objectives with bounded Hessian eigenvalues. The global objective is strongly convex and has Lipschitz-continuous gradients under these assumptions.

IV. CONVERGENCE ANALYSIS

  • PMM and ESOM are analyzed for linear convergence of their generated iterates to the optimum.PMM’s convergence rate serves as a benchmark for ESOM.Source: §IV · p. 8
  • Each local objective is twice differentiable, with Hessian eigenvalues bounded between positive constants m and M.The bounds apply for all local decision variables.Source: §IV · p. 8
  • The lower Hessian bound gives strong convexity, while the upper bound yields M-Lipschitz-continuous gradients for the global objective.The global Hessian is block diagonal, so the local eigenvalue bounds also hold globally.Source: §IV · p. 8

A. Convergence of Proximal Method of Multipliers (PMM)

PMM’s primal-dual Lyapunov function converges linearly under Assumption 1, with rate factor 1/(1+δ). Its convergence depends on network connectivity and objective conditioning, but PMM is infeasible to implement decentrally because each iteration requires infinite communication rounds.

A. Convergence of Proximal Method of Multipliers (PMM)

  • The Lyapunov function combines primal and dual errors, and the PMM iterates satisfy relations linking those variables.The vector u concatenates the dual and primal variables, and its G-weighted norm tracks both errors.Source: A. Convergence of Proximal Method of… · pp. 8–9
  • The PMM Lyapunov function converges linearly with factor 1/(1+δ), where δ is positive for feasible parameters.A larger δ gives a smaller convergence factor; maximizing it requires choosing β, ϵ, and α appropriately.Source: A. Convergence of Proximal Method of… · p. 9
  • A small first positive eigenvalue of I − Z or a large objective condition number M/m makes convergence slower.The eigenvalue reflects network connectivity: smaller values correspond to a less connected graph.Source: A. Convergence of Proximal Method of… · p. 9
  • PMM is infeasible for decentralized implementation because each iteration requires infinite communication rounds.Its convergence rate is used as a benchmark for ESOM, which is studied as a decentralized second-order approximation.Source: A. Convergence of Proximal Method of… · pp. 8–9

B. Convergence of ESOM

ESOM’s iterates converge linearly under the stated assumptions, with the primal squared error also converging linearly. The analysis relates this rate to the error from the second-order approximation and its Hessian-inverse approximation.

B. Convergence of ESOM

  • Increasing the Hessian-inverse approximation accuracy can make ESOM’s linear convergence factor arbitrarily close to PMM’s.The proof analyzes linear convergence of a Lyapunov function for the ESOM iterates.Source: B. Convergence of ESOM · pp. 10–11
  • ESOM’s quadratic approximation requires the local objective functions to be twice differentiable.This condition ensures the aggregate objective has a definable Hessian.Source: B. Convergence of ESOM · p. 10
  • ESOM’s primal optimality condition includes an error term reflecting its second-order approximation and approximate Hessian inverse.This error distinguishes the ESOM condition from the corresponding PMM condition.Source: B. Convergence of ESOM · p. 10
  • The second-order approximation error is bounded using Lipschitz continuity of the global Hessian and vanishes as the iterates approach the optimum.The bound relates the error to the step between successive iterates.Source: B. Convergence of ESOM · pp. 10–11
  • Under Assumptions 1–2, ESOM’s Lyapunov sequence and squared primal error converge to zero linearly.The result also implies convergence of the primal variables to the optimal argument.Source: B. Convergence of ESOM · pp. 11–12

C. Convergence rates comparison

PMM converges faster than ESOM at every step, but the gap between their linear convergence factors shrinks over time. A more accurate Hessian-inverse approximation brings ESOM’s factor closer to PMM’s.

C. Convergence rates comparison

  • PMM’s linear convergence is faster than ESOM’s at every step, while the gap between their factors shrinks over time.ESOM’s factor becomes closer to PMM’s as Γ_t decreases.Source: C. Convergence rates comparison · p. 12
  • As iterations progress, the step-dependent term in Γ_t approaches zero, while its truncation-dependent term remains constant.This helps explain why the convergence-factor gap narrows over time.Source: C. Convergence rates comparison · p. 12
  • Increasing the Hessian-inverse approximation order can bring ESOM’s convergence factor arbitrarily close to PMM’s.The approximation-error term can be made arbitrarily small through the choice of ρ and K.Source: C. Convergence rates comparison · p. 12

V. NUMERICAL EXPERIMENTS

The experiments compare decentralized methods on least-squares and logistic-regression problems, finding iteration and communication trade-offs for ESOM-K. The conclusion reports linear convergence for every K and relates larger K to faster iteration convergence.

A. Decentralized linear least squares

  • The least-squares experiment uses 20 nodes, dimension 5, five measurements per node, and a problem condition number of 10.The network is randomly generated with connectivity ratio r = 3/n.Source: A. Decentralized linear least squares · p. 12
  • In least squares, all ESOM-K variants outperform EXTRA among decentralized methods with exact linear convergence, while NN-K converges only to a neighborhood.Increasing K makes ESOM-K's convergence path approach PMM, whose path is generated centrally.Source: Figure 1 · p. 13, A. Decentralized linear least squares · p. 14
  • Each NN-K and ESOM-K iteration requires K + 1 local communication rounds, compared with one round for EXTRA.PMM is omitted from communication comparisons because each iteration requires infinitely many communication rounds.Source: Figure 2 · p. 13, A. Decentralized linear least squares · p. 14

B. Decentralized logistic regression

VI. CONCLUSIONS

  • The conclusion reports that ESOM-K converges linearly to the optimum for every K; larger K brings its linear convergence factor closer to PMM's, while ESOM-0 is most communication-efficient.The numerical experiments are reported to verify the theoretical convergence and factor relationship.Source: §VI · pp. 15–16

APPENDIX A PROOF OF LEMMA 1

The proof derives relations between PMM iterates and the optimal primal-dual arguments, then uses strong convexity and Lipschitz gradients to establish a decrement bound. A positive constant satisfying the stated conditions yields the contraction claim.

APPENDIX A PROOF OF LEMMA 1

  • The PMM primal optimality condition is rewritten as a relation among the gradient difference, dual-variable difference, consensus term, and proximal step.Using the optimality condition and the dual update yields the identities used in the lemma's claims.Source: Appendix A · p. 16

APPENDIX B PROOF OF THEOREM 1

  • Strong convexity and Lipschitz continuity bound the gradient inner product, supporting a lower bound on the decrement in the combined primal-dual distance.The proof rewrites the inner products as differences of squared norms before deriving the decrement bound.Source: Appendix B · pp. 16–17
  • A positive δ satisfying the displayed matrix and eigenvalue conditions makes the decrement bound sufficient for the contraction claim.The proof selects δ under conditions involving β and the smallest nonzero eigenvalue of I − Z.Source: Appendix B · pp. 17–18

APPENDIX C PROOF OF LEMMA 2

The proof rewrites ESOM's primal update to compare it with the PMM optimality expression. The resulting relation differs by an error term arising from the approximate Hessian.

APPENDIX C PROOF OF LEMMA 2

  • Regrouping the ESOM primal update expresses it as a first-order condition with the approximate Hessian multiplying the primal step.The approximate Hessian is the inverse of the truncated Hessian-inverse approximation.Source: Appendix C · p. 18
  • After adding and subtracting the exact Hessian term, the update becomes the PMM expression plus an error term, which supports the lemma's comparison.The proof identifies the error through the difference between the approximate and exact Hessians applied to the primal step.Source: Appendix C · p. 18

APPENDIX D PROOF OF LEMMA 3

The proof bounds the error introduced by the truncated Hessian-inverse approximation. Under the stated Hessian and network-weight bounds, the truncation tail decreases geometrically and the inverse perturbation is bounded.

APPENDIX D PROOF OF LEMMA 3

  • The proof assumes bounded Hessian eigenvalues and a Lipschitz-continuous Hessian when bounding the approximation error.It also uses a lower bound on local mixing weights and strong convexity to bound the matrices involved.Source: Appendix D · pp. 18–20
  • The truncation tail satisfies ∥t^(K)∥ ≤ ρ^(K+1), as stated for t^(K); ρ is defined in (76), but the passages do not support the added eigenvalue explanation or interpretation of c.Source: Appendix D · p. 19
  • A lower bound on the approximate inverse's eigenvalues bounds the approximate Hessian, enabling an upper bound on the Hessian perturbation applied to the primal step.The resulting bound supports the proof's error claim.Source: Appendix D · pp. 19–20

APPENDIX E PROOF OF THEOREM 2

Appendix E derives sufficient inequalities for the linear-convergence claim in (41), ultimately requiring nonnegative coefficients and a choice of t satisfying (92).

APPENDIX E PROOF OF THEOREM 2

  • The proof reuses steps from Theorem 1 and writes the ESOM gradient difference as a combination of the v-variable difference, primal step, and error term.The decomposition is given in (84).Source: Appendix E · p. 20
  • The proof uses that decomposition to derive a lower bound on ∥u_t−u*∥² involving the gradient gap, primal step, primal error, and an error inner product.It first substitutes the gradient difference into an inequality and follows steps (54)–(59).Source: Appendix E · p. 20
  • A Young-type bound on the error inner product, together with upper bounds on the v-variable and e_t terms, yields a sufficient inequality for the convergence result.The proof then regroups terms to obtain inequality (91).Source: Appendix E · p. 21
  • When the coefficients of the primal-step, primal-error, and gradient-gap terms are nonnegative, a t satisfying (92) establishes claim (41).The proof identifies these coefficient conditions as necessary to satisfy inequality (91).Source: Appendix E · pp. 21–22

Related papers

Loading 1602.00596v1…