PaperlayerView exact revision on arXiv

Source-linked AI summary

Convergence Rate of Distributed ADMM over Networks

Ali Makhdoumi, Asuman Ozdaglar

arXiv:1601.00194v1math.OC

TL;DR

The paper asks how to solve sums of locally known convex objectives when data and communication are distributed across a network. It develops a node-based distributed ADMM algorithm and analyzes its convergence. The method achieves O(1/T) rates for convex objectives and linear convergence under strong convexity and Lipschitz gradients, with rates also depending on network structure.

  • Problem

    Distributed data and local objective functions must be jointly optimized when each function is available only to one communicating agent.

  • Method

    A node-based reformulation enables a distributed ADMM algorithm for solving the networked sum-of-objectives problem.

  • Results

    O(1/T) convergence holds for convex objectives, while strongly convex objectives with Lipschitz continuous gradients converge linearly.

  • Takeaways & Limitations

    Convergence guarantees reflect both objective regularity and network structure, including algebraic connectivity and node degrees.

Abstract

from arXiv · show

We propose a distributed algorithm based on Alternating Direction Method of Multipliers (ADMM) to minimize the sum of locally known convex functions using communication over a network. This optimization problem emerges in many applications in distributed machine learning and statistical estimation. We show that when functions are convex, both the objective function values and the feasibility violation converge with rate $O(\frac{1}{T})$, where $T$ is the number of iterations. We then show that if the functions are strongly convex and have Lipschitz continuous gradients, the sequence generated by our algorithm converges linearly to the optimal solution. In particular, an $ε$-optimal solution can be computed with $O(\sqrt{κ_f} \log (1/ε))$ iterations, where $κ_f$ is the condition number of the problem. Our analysis also highlights the effect of network structure on the convergence rate through maximum and minimum degree of nodes as well as the algebraic connectivity of the network.

I. INTRODUCTION

The paper addresses distributed optimization when data and convex objectives are spread across machines connected by communication constraints. It introduces a distributed ADMM method and analyzes convergence under convex and strongly convex smooth objectives, including network effects.

  • Motivation: Distributed data and local information require decentralized optimization across multiple processors.The setting arises because data may be collected by decentralized agents or cannot fit on one machine.
  • Motivation: The target problem minimizes a sum of convex local objective functions known only to individual agents communicating over a network.Empirical risk minimization is given as a prominent example of this formulation.
  • Contributions: The proposed node-based distributed ADMM reformulation reduces stored and communicated variables relative to edge-based ADMM.The reformulation uses dual variables whose dimension is determined by the number of network nodes.
  • Contributions: O(1/T) convergence is established for convex objectives, while strongly convex objectives with Lipschitz gradients yield linear convergence.The convex result concerns the objective at the ergodic average, and the analysis provides a unified treatment of both regimes.
  • Contributions: The convergence analysis identifies dependence on network structure and communication weights, including degree and algebraic-connectivity effects.For Laplacian-governed communication weights, the paper gives a network-dependent iteration complexity.

C. Outline

The paper formulates consensus-constrained optimization over a connected network and develops a node-based distributed ADMM algorithm. The reformulation reduces stored and communicated variables while preserving the ADMM sequence and distributed implementation.

  • Problem formulation: The agents minimize a sum of locally known functions while enforcing equality of their local variables over a connected graph.The consensus constraint is represented as Ax = 0 using a communication matrix and A = P ⊗ I_d.
  • Problem formulation: Assumption 1 requires the communication matrix to have null(P) = span{1}, which guarantees consensus under Ax = 0.A connected graph with suitable Laplacian-type weights provides an example satisfying this assumption.
  • Distributed ADMM: The algorithm expands node constraints into neighbor-wise constraints and applies ADMM to update primal, auxiliary, and dual variables.The reformulation assigns multipliers λij to equality constraints and uses a quadratic penalty for feasibility violations.
  • Distributed ADMM: Symmetry reduces the dual variables from neighbor-specific λij to node-based pi and the auxiliary variables from zij to node estimates yi.Each yi is formed from neighboring primal variables, enabling lower-dimensional node-based updates.
  • Distributed ADMM: The node-based implementation preserves the sequence generated by the ADMM algorithm and requires each node to maintain three variables while communicating only with neighbors.The stated overall requirements are storage 3|V| and communication |E| per iteration.

III. PRELIMINARY RESULTS

This section develops preliminary representations for analyzing Algorithm 1. It rewrites the primal evolution as a perturbed linear update whose consensus and optimization effects support the convergence analysis.

  • Objective representation: The analysis defines the subdifferential of the separable objective F and specializes notation to scalar local variables without restricting the general method.The analysis is stated to generalize from x ∈ R to x ∈ R^d.
  • Perturbed linear update: Lemma 2 expresses the primal update as a perturbed linear recurrence involving a subgradient h(x(t + 1)).This representation is used as a compact form of Algorithm 1’s evolution.
  • Perturbed linear update: The linear term drives the iterates toward consensus, while the perturbation term ensures the limiting consensus point minimizes F.This separates the roles of network consensus and objective minimization in the convergence argument.

IV. SUB-LINEAR RATE OF CONVERGENCE

The analysis establishes an O(1/T) sub-linear convergence rate for the ergodic average, covering both objective optimality and feasibility violation. The guarantee depends on network and communication-matrix spectral quantities.

  • The proof introduces Q = (A′D−1A)1/2 and auxiliary sequences to analyze the distributed updates.Q is defined through the singular value decomposition of A′D−1A.
  • Theorem 2 bounds the convergence guarantee using the subgradient bound U and the spectral quantities ˜λm and λM.˜λm is the smallest non-zero eigenvalue of A′D−1A, while λM is the largest eigenvalue of M − A′D−1A.
  • O(1/T) convergence holds for the objective function at the ergodic average and for feasibility violation.The ergodic average is formed by recursive time-averaging of each agent’s estimates.
  • Better performance guarantees require maximizing ˜λm and minimizing λM.For Laplacian communication matrices, these quantities can be expressed through network structure and algebraic connectivity.

V. LINEAR RATE OF CONVERGENCE

Under strong convexity and Lipschitz-gradient assumptions, the algorithm’s iterates converge linearly to the unique optimal solution. The optimized rate exhibits square-root dependence on the problem condition number and remains linear for every positive penalty parameter.

  • The condition number is κf = L/ν, using the maximum Lipschitz-gradient parameter L and minimum strong-convexity constant ν.These constants aggregate the corresponding local-function parameters.
  • Strong convexity and Lipschitz continuous gradients make the optimal solution unique and yield linear convergence of the iterates.The proof shows contraction of the G-norm distance between q(t) and q∗ at each iteration.
  • Linear convergence holds for every penalty parameter c > 0.Theorem 3 states this under Assumptions 1, 2, and 3, with β ∈ (0, 1).
  • An ε-neighborhood of the optimum is reached within O(√κf log(1/ε)) iterations for an appropriate penalty parameter.The optimized estimate improves on the linear condition-number dependence reported for edge-based ADMM.

VI. NETWORK EFFECTS

The convergence guarantees depend explicitly on network connectivity and node degrees. With Laplacian communication, larger algebraic connectivity and minimum degree, together with smaller maximum degree, produce faster rates.

  • Laplacian communication matrices expose network effects through algebraic connectivity and node degrees.The paper derives explicit bounds for both sub-linear and linear convergence regimes.
  • Larger algebraic connectivity a(G) yields faster convergence guarantees.The proposition links highly connected graphs with larger algebraic connectivity to faster rates.
  • Larger dmin and smaller dmax improve the convergence rate.Both sub-linear and linear guaranteed rates depend on dmax, dmin, and a(G).
  • For d-regular graphs, ˜λm = a(G)^2/(d+1) and λM = d(d+1).The paper notes that good expanders can have a(G) = O(d), and compares regular graphs with d = 10, 20, 30 numerically.
  • The numerical examples use Laplacian communication for a distributed estimation objective with locally known scalar measurements ai.The experiments compare performance across several regular graphs.

APPENDIX

The appendix derives compact update representations and supporting inequalities used in the convergence proofs. These steps eliminate auxiliary-variable dependence and connect primal iterates to the rate analysis.

  • Consensus is enforced by Ax = 0, with A = P ⊗ I_d, so all node variables become equal under the communication-matrix assumption.The null-space condition on P ensures coordinate-wise equality across agents.
  • Algorithm 1’s primal update can be rewritten solely in terms of the sequence of primal iterates and aggregate subgradients.The derivation eliminates dependence on auxiliary variables yi(t) and pi(t).
  • Lemma 4 establishes a relation between the auxiliary sequence r(t) and the primal sequence x(t).This relation is used in the proof of the sub-linear convergence proposition.
  • The sub-linear proof combines telescoping inequalities, convexity, Jensen’s inequality, and saddle-point bounds.These steps bound objective performance and feasibility violation after summing over iterations.

E. Proof of Theorem 2

The proof bounds an optimal dual solution using subgradient and spectral properties, then applies that bound to analyze the network effect.

  • E. Proof of Theorem 2: A lemma establishes a bound on the norm of an optimal dual solution.The construction preserves the saddle-point conditions while selecting a bounded dual solution.
  • E. Proof of Theorem 2: The dual construction represents the relevant subgradient through the singular-value structure of Q.The proof uses the singular value decomposition of Q and chooses the dual vector within the appropriate column-space representation.
  • E. Proof of Theorem 2: The resulting primal-dual pair satisfies the saddle-point inequality and is therefore optimal.The argument identifies c˜r′Q with a subgradient at x∗ and uses this equality to establish optimality.
  • E. Proof of Theorem 2: The network-effect analysis applies Theorem 1 with zero initial condition after establishing the dual bound.The supplied proof text presents this as the next step after the lemma.

F. Proof of Lemma 3

The proof develops matrix and sequence lemmas for the distributed iterations, using positive semidefiniteness, subgradient inequalities, and column-space relations.

  • F. Proof of Lemma 3: The proof introduces φ_x(y) = f_i(y) − ⟨∇f_i(x), y⟩, whose gradient is Lipschitz with parameter L_fi and whose minimum occurs at y = x.These properties support the subsequent inequalities used for each i.
  • F. Proof of Lemma 3: Lemma 6 shows that M − A′D−1A and A′D−1A are positive semidefinite.The proof establishes symmetry and uses the Gerschgorin Circle Theorem for both matrices.
  • F. Proof of Lemma 3: For differentiable functions, Lemma 7 relates the sequences x(t), r(t), and q(t) under Assumptions 1 and 2.The proof then rearranges the iteration after subtracting (A′D−1A)x(t+1).
  • F. Proof of Lemma 3: The optimal gradient lies in the column span of Q because its components sum to zero and null(Q) = span{1}.This yields an r satisfying the required relation with Q, and projection provides r∗ in the column space of Q.

H. Proof of Theorem 4

The proof determines the largest admissible δ by optimizing the constraint from Theorem 1 over β ∈ (0, 1).

  • H. Proof of Theorem 4: The largest possible δ is obtained by maximizing the Theorem 1 constraint over β ∈ (0, 1).The resulting optimization problem defines the parameter used in the theorem’s bound.

I. Proof of Proposition 3

The proof bounds the convergence parameters using the network’s algebraic connectivity and degree quantities, then substitutes those bounds into the iteration estimate.

  • I. Proof of Proposition 3: Theorem 2’s bound depends on ˜λ_m, which is bounded using the graph’s algebraic connectivity a(G).Here a(G) is the smallest non-zero eigenvalue of the graph Laplacian.
  • I. Proof of Proposition 3: The degree-based bounds are substituted into Theorem 2, using d_min ≥ 1 to complete the network-dependent estimate.The proof explicitly combines the connectivity and degree bounds before concluding the proposition.
  • I. Proof of Proposition 3: For sufficiently large κ_f, equivalently sufficiently small δ∗, the proof derives an iteration requirement for ||x(t) − x∗||_2 ≤ ε.The resulting bound depends on ˜λ_m and λ_M before further substitution.
  • I. Proof of Proposition 3: The final convergence estimate follows by plugging the bound involving network parameters into equation (28).The proof concludes after this substitution.
Loading 1601.00194v1…