On the O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers

Ermin Wei; Asuman Ozdaglar

Source-linked AI summary

On the O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers

Ermin Wei, Asuman Ozdaglar

arXiv:1307.8254v1Jul 31, 2013math.OC

TL;DR

The paper addresses distributed convex optimization with private local objectives, linear coupling constraints, and prior methods limited by slower subgradient rates or synchronous coordination. It develops a fully asynchronous decentralized ADMM method for the general formulation and proves almost-sure convergence to an optimum, with objective error and feasibility violation at O(1/k).

Problem
Distributed optimization methods for this general formulation were limited by O(1/sqrt(k)) subgradient rates or synchronous implementations requiring a global clock.
Method
The paper develops a fully asynchronous decentralized ADMM algorithm that randomly activates constraint subsets and updates the associated primal and dual variables using local information.
Results
The algorithm converges almost surely to an optimal solution, while objective-function values and feasibility violation converge at O(1/k).
Takeaways & Limitations
The method provides an asynchronous ADMM-based distributed solution for convex optimization with separable objectives and linear constraints.

Abstract

from arXiv · show

We consider a network of agents that are cooperatively solving a global optimization problem, where the objective function is the sum of privately known local objective functions of the agents and the decision variables are coupled via linear constraints. Recent literature focused on special cases of this formulation and studied their distributed solution through either subgradient based methods with O(1/sqrt(k)) rate of convergence (where k is the iteration number) or Alternating Direction Method of Multipliers (ADMM) based methods, which require a synchronous implementation and a globally known order on the agents. In this paper, we present a novel asynchronous ADMM based distributed method for the general formulation and show that it converges at the rate O(1/k).

I. INTRODUCTION

The paper formulates distributed multi-agent optimization with separable local objectives and linear coupling constraints, then proposes an asynchronous decentralized ADMM method for this general setting. Under positive constraint-selection probabilities and compact constraint sets, the method converges almost surely to an optimal solution, with objective error and feasibility violation decreasing at O(1/k).

Motivation: Distributed agents collectively solve a global optimization problem using privately known local objective functions and coupled decision variables.The formulation supports decentralized computation and neighbor communication when no centralized processing unit is available.
Problem formulation: The distributed problem is reformulated by giving each agent a local copy x_i and enforcing x_i = x_j across network edges.Connectedness ensures all local copies agree; the edge-node incidence matrix provides a compact representation.
Challenges: Existing approaches rely either on first-order subgradient methods with O(1/sqrt(k)) rates or synchronous algorithms driven by a global clock.These requirements create challenges for large-scale and highly decentralized settings.
Proposed method: The paper proposes an asynchronous decentralized ADMM algorithm for the general formulation, activating random subsets of constraints and updating corresponding primal and dual variables.Active components use local cost functions and active constraints, while the method’s analysis uses a weighted norm and a Lyapunov function.
Convergence: Almost surely, the asynchronous primal iterates converge to an optimal solution when every constraint has positive selection probability and the constraints have decoupled structure.The proof relates asynchronous iterates to full-information iterates through probability-weighted analysis.
Rate guarantee: O(1/k) bounds hold for expected objective-value difference and expected feasibility violation under compactness of the constraint sets X and Z.The conclusion states the same O(1/k) rate for objective values and feasibility violation.

II. PRELIMINARIES: STANDARD ADMM ALGORITHM

Standard ADMM solves separable convex problems with linearly coupled variables by sequentially updating primal variables and then the dual variable. Under a saddle-point assumption, its objective values converge to the optimum, while the primal and dual sequences converge to optimal solutions.

ADMM targets separable convex optimization problems whose decision variables are coupled through a linear constraint.The formulation uses convex functions over closed convex sets and a positive penalty parameter.
The augmented Lagrangian adds a quadratic feasibility penalty to the ordinary Lagrangian.The penalty parameter is β, and p is the multiplier for Dsx + Hsz = c.
Each iteration sequentially minimizes over x and z in a Gauss-Seidel manner, then updates the dual variable by gradient ascent.The primal updates use the current multiplier and the augmented Lagrangian.
The separable structure decouples minimization over component functions, which can support parallel or decentralized implementations when those minimizations are simple.The decoupling arises from sequential minimization with quadratic perturbations.
Under existence of a saddle point, the primal objective values converge to the optimal value and the dual sequence converges to a dual optimal solution.The saddle point is equivalent to a primal-dual optimal solution pair.

III. ASYNCHRONOUS ADMM ALGORITHM

The paper extends standard ADMM to an asynchronous distributed algorithm. It updates subsets of decision components using partial problem information, without requiring a global coordinator.

The paper presents an asynchronous distributed ADMM algorithm as an extension of standard ADMM.
At each time, the method updates a subset of decision-vector components using partial information about the problem data.
The asynchronous implementation operates without a global coordinator.
The paper applies the asynchronous ADMM algorithm to a distributed multi-agent optimization problem.

A. Problem Formulation and Assumptions

The problem distributes local convex objectives and decision components across agents while coupling them through linear constraints. The formulation assumes a saddle point and a decoupled constraint structure suited to the distributed setting.

The global objective is the sum of privately distributed local functions fi, with each agent maintaining its decision component xi.
The constraints couple decision components according to the underlying connectivity among agents.
The formulation assumes that the Lagrangian has a saddle point with a solution-multiplier pair.
The constraint structure is assumed to support the distributed multi-agent optimization problem motivating the paper.
The matrix H is diagonal and invertible, while each row of D has exactly one nonzero element and D has no all-zero columns.These conditions imply that each component of z appears in exactly one constraint and each constraint involves exactly one xi.

B. Asynchronous Algorithm Implementation

The asynchronous implementation randomly activates constraint groups and their associated agents, updating only active primal and dual components with local information. An infinitely-often update condition ensures recurring activation of every partition element.

The implementation is motivated by large-scale decentralized problems that require iterative computation with little coordination.
Randomly activated agents update relevant decision components using partial and local problem information, while inactive components remain unchanged.
The method removes the need for a centralized coordinator or global clock.
At each iteration, a random partition element ψk selects a subset of coupling constraints, and φk identifies the associated decision components.
The activation variables are correlated within each iteration but independently and identically distributed across iterations.
Constraints and their dual variables are active when their indices lie in ψk, while component i or agent i is active when i lies in φk.
The algorithm updates active decision and dual variables using active agents’ local costs and active constraints.
The infinitely-often update assumption ensures every partition element, and consequently every agent and constraint, is active infinitely often with probability 1.

C. Asynchronous ADMM Algorithm

This section introduces the asynchronous ADMM algorithm for solving problem (1).

The paper next describes an asynchronous ADMM algorithm for problem (1).
The algorithm is presented as a method for solving problem (1).
The section transitions from the problem formulation to the asynchronous ADMM procedure.

I. Asynchronous ADMM algorithm:

The asynchronous ADMM iteration initializes primal and dual variables, updates selected primal components and dual variables, and uses equivalent update forms for convergence analysis.

The iteration initializes x0 in X, z0 in Z, and p0 = 0.
At iteration k, random variables Φk and Ψk select realizations φk and ψk for the asynchronous updates.
The primal variables x and z and the dual variable p are updated in separate steps.
The minimizers in updates (12) and (13) are assumed to exist but need not be unique.
Updates (15) and (16) expose dependence on x and z and are used in the convergence analysis, while (14) is the dual update.
Under the stated restriction, components of x and z outside the active sets retain optimality for updates (12) and (13).

D. Special Case: Distributed Multi-agent Optimization

The paper applies asynchronous ADMM to an edge-based reformulation of distributed multi-agent optimization, enabling decentralized updates triggered by edge clocks and local information exchange.

The formulation encodes consensus constraints xi = xj for agents connected through the network.
The edge-based reformulation represents each edge constraint using endpoint variables z_eq and constraints xi = zei, −xj = zej, and zei + zej = 0.
The reformulated problem has H = −I and a matrix D whose columns are nonzero because every node is incident to at least one edge.
With independent identical-rate Poisson clocks, an edge tick activates its two endpoint agents and the associated constraint rows.
The edge-based primal z update is a linearly constrained quadratic problem that can be solved in closed form.
The resulting algorithm is decentralized, using each node’s local objective, adjacency entries, local variables, and communication with a neighbor.
Each active edge causes its endpoint agents to exchange estimates and dual variables, update v and z, and then update their dual variables.
A node-based reformulation is also possible, but it uses a different communication structure in which nodes broadcast to all neighbors.

IV. CONVERGENCE ANALYSIS FOR ASYNCHRONOUS ADMM ALGORITHM

The convergence analysis maps asynchronous iterates to full-information sequences over active components and constraints, then uses this correspondence to establish convergence and an O(1/k) expected objective-value rate.

The analysis studies asynchronous ADMM under the Decoupled Constraints Assumption.
Under Assumptions 2–4, the primal iterates {xk, zk} converge almost surely to an optimal solution of problem (1).
The corresponding objective function values converge in expectation to the optimal value at rate O(1/k).
Asynchronous iterates match auxiliary sequences on active components and constraints while remaining unchanged elsewhere.
This correspondence permits analysis through the sequence {yk, vk, µk} and translation into objective-value improvement bounds for {xk, zk, pk}.
The auxiliary x and z updates decompose across active components and constraint sets because of the structure imposed by Assumption 3.
Inactive components of x, z, and p retain their previous values during an iteration.
The residual at (yk+1, vk+1) specifies the update direction for the dual vector µk+1.

A. Preliminaries

The section develops preliminary bounds and limiting results for asynchronous ADMM iterates. These results connect weighted quantities to convergence and characterize when limit points are saddle points.

A. Preliminaries: The preliminary results are independent of the probability distributions of the random activation variables Φ_k and Ψ_k.Proofs for these results are omitted and referred to another source.
A. Preliminaries: The analysis bounds the objective gap, dual-solution distance, and distance to an optimal z∗ using weighted quantities.These bounds support both almost-sure convergence and convergence-rate analysis.
A. Preliminaries: Theorem 4.2 establishes iteration-wise relations for the asynchronous ADMM sequence and auxiliary sequences associated with a Lagrangian saddle point.The auxiliary sequences are defined in Eqs. (22)–(25).
A. Preliminaries: If the residual r_k converges to zero and {z_k, p_k} is bounded, then {x_k, y_k, z_k} has a limit point that is a Lagrangian saddle point.This is the sufficient condition supplied by Lemma 4.3.

B. Convergence and Rate of Convergence

The convergence analysis uses weighted norms, a weighted Lagrangian, and supermartingale arguments to establish almost-sure convergence and an O(1/k) rate for averaged iterates.

B. Convergence and Rate of Convergence: A weighted norm and weighted Lagrangian relate asynchronous iterates to auxiliary full-information quantities through activation probabilities.The weights are constructed from the distributions of the active constraints and components.
B. Convergence and Rate of Convergence: O(1/k) convergence holds in expectation for objective-function values and constraint violation using time-ergodic averages.The rate analysis is formulated for the averages of x_k and z_k through iteration T.
B. Convergence and Rate of Convergence: A nonnegative supermartingale argument yields almost-sure convergence of the relevant scalar sequence and drives the residual toward zero.The analysis uses martingale convergence and probability bounds to establish the limiting properties.
B. Convergence and Rate of Convergence: The asynchronous ADMM sequence {x_k, z_k, p_k} converges almost surely to a saddle point of the Lagrangian.The proof establishes the sufficient conditions of Lemma 4.5 with probability 1.
B. Convergence and Rate of Convergence: The rate analysis assumes compact feasible sets X and Z, while activation probabilities define the weighting matrix used in the proof.The compactness assumption ensures that the scalar Q(µ) is well defined.

V. CONCLUSIONS

The paper presents a fully asynchronous ADMM algorithm for convex distributed optimization with separable objectives and linear constraints. It establishes almost-sure optimal convergence and an O(1/k) rate for objective values and feasibility violation.

V. CONCLUSIONS: The algorithm addresses convex optimization with a separable objective and linear constraints in distributed multi-agent settings.Agents use privately known local objectives and communicate using local information and neighbors.
V. CONCLUSIONS: The algorithm converges almost surely to an optimal solution.This conclusion applies to the distributed setting described in the paper.
V. CONCLUSIONS: O(1/k) convergence applies to objective-function values and feasibility violation.The paper identifies communication noise, quantization, and time-varying topology as future network-effect questions.