PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Linearized Alternating Direction Method of Multipliers for Composite Convex Consensus Optimization

Necdet Serhat Aybat, Zi Wang, Tianyi Lin, Shiqian Ma

arXiv:1512.08122v4math.OC

TL;DR

Computing the prox map for each private composite function is difficult. The paper studies distributed proximal-gradient ADMM methods and reports convergence with local communication and limited network information.

  • Problem

    Computing the prox map for Φ_i = ξ_i + f_i is not easy.

  • Method

    The paper studies distributed proximal gradient ADMM and its stochastic counterpart for distributed minimization of composite convex functions over connected networks.

  • Results

    The methods compute an ϵ-optimal ϵ-feasible solution in O(ϵ^-1) iterations, requiring one or two neighbor communication rounds per iteration and thus O(ϵ^-1) communications.

  • Takeaways & Limitations

    DPGA, DPGA-W, SDPGA, and SDPGA-W are fully distributed node-based algorithms using only local communication, without requiring agents to know global network quantities.

  • Takeaways & Limitations

    The methods assume agents know who their neighbors are.

Abstract

from arXiv · show

Given an undirected graph $\mathcal{G}=(\mathcal{N},\mathcal{E})$ of agents $\mathcal{N}=\{1,\ldots,N\}$ connected with edges in $\mathcal{E}$, we study how to compute an optimal decision on which there is consensus among agents and that minimizes the sum of agent-specific private convex composite functions $\{Φ_i\}_{i\in\mathcal{N}}$ while respecting privacy requirements, where $Φ_i\triangleq ξ_i + f_i$ belongs to agent-$i$. Assuming only agents connected by an edge can communicate, we propose a distributed proximal gradient method DPGA for consensus optimization over both unweighted and weighted static (undirected) communication networks. In one iteration, each agent-$i$ computes the prox map of $ξ_i$ and gradient of $f_i$, and this is followed by local communication with neighboring agents. We also study its stochastic gradient variant, SDPGA, which can only access to noisy estimates of $\nabla f_i$ at each agent-$i$. This computational model abstracts a number of applications in distributed sensing, machine learning and statistical inference. We show ergodic convergence in both sub-optimality error and consensus violation for DPGA and SDPGA with rates $\mathcal{O}(1/t)$ and $\mathcal{O}(1/\sqrt{t})$, respectively.

I. INTRODUCTION

The paper studies fully distributed consensus optimization for privately known composite convex objectives over connected undirected networks. It proposes proximal-gradient ADMM algorithms that use local computation and communication, with ergodic convergence guarantees for deterministic and stochastic gradients.

  • Problem: The composite objective separates each agent's function as Φ_i = ξ_i + f_i, where ξ_i may be nonsmooth and f_i is smooth with Lipschitz-continuous gradient.The methods require efficient computation of proxξ_i and gradients of f_i.
  • Problem: The problem minimizes a sum of privately known composite convex functions while enforcing consensus using only neighbor-to-neighbor communication.The decentralized formulation avoids collecting private functions or data at a central node.
  • Methods: The paper proposes PG-ADMM and its stochastic variant SPG-ADMM, implemented as DPGA, DPGA-W, SDPGA, and SDPGA-W for unweighted and weighted static networks.The stochastic methods extend the framework to noisy gradient information, while the node-based algorithms operate through local neighbor communication.
  • Methods: The proposed algorithms are fully distributed: agents need only neighbor identities rather than global network parameters such as the Laplacian's second-smallest eigenvalue.They use node-based storage and communication, reducing burden relative to edge-based approaches.
  • Results: The algorithms use a single loop and can compute an ϵ-feasible, ϵ-optimal solution within O(1/ϵ) communication rounds under weaker assumptions than several compared methods.The paper highlights simpler implementation and guarantees without assuming bounded gradients.

II. PROXIMAL GRADIENT ADMM AND ITS CONNECTIONS

The paper formulates composite convex optimization with linear constraints and develops proximal-gradient ADMM methods using easy proximal maps and gradient information, including stochastic gradients.

  • Problem and method: PG-ADMM solves linearly constrained composite convex optimization by combining proximal updates for ξ_i with gradient steps for f_i.The formulation uses constraints A_i x_i + B_i y = b_i and assumes ξ_i and g have easy proximal maps.
  • Problem and method: The augmented Lagrangian separates a smooth component φ_γ from the nonsmooth functions, enabling proximal-gradient updates.The smooth component is explicitly identified within the augmented Lagrangian.
  • Stochastic extension: The stochastic variant replaces ∇f_i with noisy stochastic first-order-oracle observations and uses stochastic-gradient step sizes.The paper defines SFOs for each ∇f_i and analyzes their effect on convergence.
  • Connections: PG-ADMM and SPG-ADMM extend G-ADMM and SG-ADMM by allowing general nonsmooth convex ξ_i terms.In the single-agent, ξ_i = 0 case, the methods reduce to the earlier gradient-based ADMM variants.
  • Assumptions and analysis: The analysis assumes a nonempty optimal primal-dual solution set and uses saddle-point optimality conditions for the constrained problem.The optimality conditions characterize a primal-dual point satisfying the stationarity, feasibility, and dual relations.

A. Convergence Rate of PG-ADMM and SPG-ADMM

The convergence analysis establishes ergodic bounds for deterministic and stochastic proximal-gradient ADMM under step-size and boundedness conditions, with stronger conclusions in the deterministic case.

  • Stochastic convergence: The stochastic analysis models gradient errors through an SFO and permits either finite domain diameter or finite initial-distance control.These conditions govern the quantities used in the convergence bounds.
  • Stochastic convergence: For stochastic gradients, the bounds require conditions such as σ > 0, finite D or D∗(x0), and specified iteration-dependent step sizes.The theorem uses c_i = (L_i + γ_i ∥A_i∥^2 + 1)^-1 in one stated setting.
  • Deterministic convergence: For exact gradients, constant step sizes c_i ∈ (0, (L_i + γ_i∥A_i∥^2]^-1) yield a probability-one convergence bound for all t ≥ 1.The exact-gradient case is obtained by setting σ = 0 in the stochastic-oracle analysis and sharpening the resulting bounds.
  • Convergence of iterates: Both iterate sequences converge to a primal-dual optimal point when the vertically concatenated matrix B has full column rank.The full-column-rank condition is used to establish boundedness of the y-iterates and identify primal-dual limit points.

B. Connections to the existing work

The paper relates PG-ADMM to primal-dual algorithms and shows that this connection extends to noisy-gradient settings where earlier primal-dual methods cannot operate.

  • Convergence connection: For deterministic gradients, PG-ADMM has ergodic suboptimality and infeasibility convergence under c ≥ 1/(L + γ∥A∥^2).The result applies for any γ > 0 under the stated stepsize condition.
  • Connections to primal-dual algorithms: PG-ADMM generates the same iterate sequence as a primal-dual algorithm under the stated problem structure and Bregman choices.The equivalence holds for the formulation with constraint Ax−y=0 and B=−I_n.
  • Scope of equivalence: The equivalence with primal-dual algorithms does not extend to general B in min Φ(x)+g(y) subject to Ax+By=b.The stated equivalence specifically relies on B=−I_n.
  • Scope beyond prior methods: PG-ADMM is more general than the cited primal-dual algorithms because it also accommodates noisy gradients.The cited primal-dual methods do not handle noisy gradients.

III. PROXIMAL GRADIENT METHODS FOR DISTRIBUTED OPTIMIZATION

This section formulates decentralized consensus optimization on connected undirected networks and derives distributed deterministic and stochastic algorithms from PG-ADMM, with topology-dependent convergence bounds.

  • Network model: The framework applies to unweighted and weighted static undirected communication networks.The network is modeled as connected, with oriented edges, neighboring nodes, a Laplacian, and an incidence matrix.
  • Distributed formulations: The decentralized formulations yield two distributed algorithms based on PG-ADMM, with customized convergence bounds that capture network-topology effects.The constructions cover the two formulations introduced for consensus optimization.
  • Stochastic variants: Stochastic-gradient variants are obtained by applying SPG-ADMM to the two decentralized formulations.Their error bounds are derived from the deterministic results using Theorem 3.
  • Proof scope: The stochastic error-bound proofs are omitted for space and presented as consequences of the deterministic bounds.The text explicitly states that the proofs are skipped.
  • Consensus geometry: Connectedness gives ψ_{N−1} > ψ_N = 0 and rank(M ⊗ I_n)=n(N−1), supporting the consensus-space analysis.The incidence and Laplacian matrices satisfy Ω=M^⊤M.

A. DPGA Algorithm

DPGA implements the consensus formulation through local proximal-gradient updates and neighbor communication, with node-specific stepsizes constrained by local smoothness, penalties, and degree.

  • Consensus reformulation: DPGA is obtained by applying PG-ADMM to an edge-variable consensus reformulation with constraints x_i−y_ij=0 and x_j−y_ij=0.The reformulation sets g(y)=0 and associates dual variables with the edge constraints.
  • Stepsize selection: The node-specific stepsizes satisfy 0 < c_i ≤ 1/(L_i + γ_i∥A_i∥^2), which becomes c_i ≤ 1/(L_i + γ_i d_i) for the consensus formulation.Strict inequality is required for convergence of the iterate sequence to a unique limit point.
  • Algorithm derivation: The DPGA updates are a simplified form of the PG-ADMM steps after eliminating the edge-variable recursions.The resulting steps can be computed for all iterations and are summarized in Figure 1.
  • Algorithm scope: DPGA and its stochastic counterpart are designed for distributed optimization over the two decentralized consensus formulations.The algorithmic structure is presented as a node-based implementation of the PG-ADMM framework.
  • Distributed implementation: Each node computes a proximal step, broadcasts its updated iterate, and updates local variables using communication with neighboring nodes.The implementation stores three n-dimensional variables per node and repeats these operations each iteration.

1) Error Bounds for DPGA & Effect of Topology:

The DPGA analysis establishes convergence to an optimal consensus solution and derives ergodic error bounds whose constants reflect stepsizes, penalties, local function geometry, and network topology.

  • Effect of topology: The topology analysis studies how the communication network affects DPGA convergence rates.The bounds are specialized using the incidence and Laplacian structure of the consensus problem.
  • Ergodic error bounds: The averaged sequence x̄^t is analyzed through explicit bounds for every t ≥ 1 under c_i ≤ (L_i + γ_i d_i)^−1.The bounds use local subdifferential bounds κ_i and a matrix Q defined in the theorem.
  • Convergence guarantee: DPGA converges to an optimal solution when c_i < (L_i + γ_i d_i)^−1 for every node.The iterates generated by DPGA coincide with those of PG-ADMM on the consensus reformulation.
  • Proof ingredients: The proof uses consensus optimality conditions, dual solutions, convexity, and bounds on subgradients at an optimal solution.These ingredients are combined with the theorem inequalities to obtain the desired bounds.
  • Penalty specialization: For constant penalties, the theorem bounds can be further simplified, with the relevant penalty choice involving |E|.The supplied passage states that the expression involving |E| is optimal for constant penalty.

B. DPGA-W Algorithm for weighted communication networks

DPGA-W extends distributed proximal gradient optimization to weighted static communication networks through a weighted consensus formulation. Its updates preserve local computation while requiring two neighbor communications per iteration.

  • Network structure: The weighted communication matrix is sparse over neighbor links, and its nullspace enforces agreement among all agents.For vectors satisfying (W ⊗ In)x = 0, every agent variable equals a common consensus value.
  • Weighted consensus formulation: DPGA-W reformulates weighted consensus using local variables yij and constraints Wijxj − yij = 0, enabling a distributed primal-dual implementation.The formulation introduces node-local multipliers and constraint matrices derived from the communication weights.
  • Algorithm updates: Each DPGA-W iteration uses proximal-gradient and primal-dual updates, with local stepsizes satisfying ci ≤ 1/(Li + γi∥ωi∥2).The bound accounts for the local Lipschitz constant, penalty parameter, and weighted network column norm.
  • Algorithm updates: DPGA-W avoids computing prox(ξi + fi) directly, which may be impractical even when ξi and fi individually have simple proximal maps.The method instead separates the proximal operation from the smooth gradient component.
  • Communication cost: DPGA-W supports general weighted networks but requires each node to communicate twice with neighbors per iteration, versus once for the unweighted counterpart.Weights and penalty information are exchanged at initialization, while the per-iteration communication burden is higher.

1) Error Bounds for DPGA-W & Effect of Network Topology:

The DPGA-W iterates converge under stated feasibility, regularity, and stepsize conditions, with error bounds that incorporate network and problem parameters. The analysis also characterizes how topology enters these bounds.

  • Effect of network topology: Network topology affects the convergence-rate bound through weighted communication-matrix quantities such as ∥ωi∥ and the spectral structure of W.The analysis explicitly connects the rate bound to graph-dependent parameters.
  • Convergence guarantees: DPGA-W converges to an optimal solution when ci < (Li + γi∥ωi∥2)^−1, and its averaged iterates satisfy the corresponding error bounds.The result assumes a solution exists and the relevant relative-interior condition holds.
  • Convergence guarantees: The convergence proof requires stepsizes no larger than the inverse of the local smoothness and weighted penalty term, with equality allowed for the stated bound.The sufficient condition is ci ≤ (Li + γi∥ωi∥2)^−1 for the rate bound.
  • Error bounds: The DPGA-W error analysis derives suboptimality and consensus bounds by combining primal-dual inequalities with the graph matrix spectrum.The bounds use dual solutions, subdifferential bounds, and the nonzero eigenvalues of W.

C. Stochastic gradient variants of DPGA and DPGA-W

The stochastic variants replace exact gradients with stochastic first-order oracles while retaining the distributed proximal-gradient framework. Their convergence bounds follow by applying the general stochastic analysis to DPGA settings.

  • Convergence bounds: The SDPGA bounds are obtained by invoking the general theorem for the positive-noise case, and analogous bounds apply to SDPGA-W.The paper provides the SDPGA result directly and states that the weighted counterpart follows immediately.
  • Stochastic variants: SDPGA and SDPGA-W use stochastic first-order oracles instead of accessing exact gradients ∇fi at each node.The stochastic variants preserve the distributed structure while replacing the gradient information source.
  • Convergence bounds: The SDPGA average sequence satisfies stochastic error bounds under stepsizes such as ci = (Li + γi∥Ai∥2 + 1)^−1.The stated bounds use assumptions on the solution, relative-interior feasibility, and subdifferential magnitudes.

D. Adaptive step-size strategy

The paper develops locally checkable adaptive stepsizes for DPGA methods and compares them with distributed ADMM and PG-EXTRA. Adaptive stepsizes can exploit node-specific smoothness, while competing fixed-step or prox-based methods have communication, parameter, or computational constraints.

  • Adaptive step-size strategy: Local backtracking can produce longer convergent steps than fixed ci because each node checks its own descent condition.This strategy is useful when Lipschitz constants are unknown or would otherwise force very small steps.
  • Numerical comparison: DPGA was compared with PG-EXTRA, distributed ADMM, and a more efficient structure-exploiting ADMM variant on sparse-group LASSO with Huber loss.The experiment uses composite objectives with ℓ1 and group-norm regularization plus a Huber-loss smooth term.
  • Distributed ADMM comparison: ADMM is a special case of DPGA-W when all penalty parameters are equal and the full composite function is assigned to the nonsmooth component.This connects the proposed weighted proximal-gradient framework to the distributed ADMM formulation.
  • Distributed ADMM comparison: SADMM achieves an O(1/k) rate but communicates 4n scalars and stores 7n scalars per node per iteration.These costs are reported for the structure-exploiting ADMM variant.
  • PG-EXTRA comparison: PG-EXTRA has O(1/k) suboptimality and consensus-violation rates, but its common stepsize cannot exploit adaptive node-specific steps.Its implementation also depends on mixing matrices and may require globally determined parameters such as dmax and Lmax.

B. Implementation details and numerical results

The experiments compare distributed solvers on synthetic composite optimization problems, showing that DPGA and PG-EXTRA outperform ADMM variants in runtime and that adaptive steps substantially accelerate DPGA.

  • Implementation details: The test problems use star-tree or clique networks with 5 or 10 nodes and dimensions n ∈ {1000, 3000}.The composite regularizers and sensing matrices are generated under two cases with shared or node-specific partitions.
  • Implementation details: The experiments terminate at relative suboptimality below 10^-3 or after 1800 seconds, reporting the final iterate if the time limit is reached.Reported table statistics are means over five replications for each case.
  • Numerical results: DPGA and PG-EXTRA finish jobs much faster than ADMM and SADMM, while PG-EXTRA runs slower than DPGA.The comparison uses star trees and cliques with 5 or 10 nodes, across two problem cases and multiple problem sizes.
  • Numerical results: Adaptive step sizes speed up DPGA by a factor of at least 2 compared with constant step sizes.The reported runtime comparison excludes communication time.
  • Implementation details: DPGA uses one communication round per iteration, compared with two for PG-EXTRA and ADMM and four for SADMM.The authors expect DPGA’s advantage to increase when communication time is included.

C. Numerical Tests on the Effect of Network Topology and Noisy Gradients

Topology experiments show that denser networks converge faster, with network size affecting convergence more strongly than average edge density; noisy-gradient SDPGA is slower than DPGA but performs better empirically than its theoretical rate suggests.

  • Network topology: Adding edges improves convergence, with the improvement more noticeable for consensus violation than for suboptimality.The comparison examines circle, small-world, and complete-graph topologies.
  • Network topology: Smaller networks converge faster, while for fixed network size, higher edge density also accelerates convergence.The experiments vary average edges per node in small-world networks with 10 and 50 nodes.
  • Noisy gradients: SDPGA is slower than DPGA, but its empirical behavior is much better than the theoretical O(1/t) rate indicated in the experiments.The noisy-gradient comparison uses variances σ ∈ {0.01, 0.1, 1} on a 10-node random small-world network.
  • Concluding results: DPGA, DPGA-W, SDPGA, and SDPGA-W are fully distributed and require only neighbor knowledge rather than global topology parameters.The node-based algorithms also require less communication burden and memory storage than edge-based alternatives.
  • Concluding results: The proposed methods compute an ϵ-optimal, ϵ-feasible solution in O(ϵ^-1) iterations and O(ϵ^-1) total communications per node.Each iteration computes proxξ_i and ∇f_i and uses one or two neighbor communication rounds, without assuming bounded gradients.
Loading 1512.08122v4…