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

I Introduction

We consider the following optimization problem with a separable objective function and linear constraints:

Our focus on this formulation is motivated by distributed multi-agent optimization problems, which attracted much recent attention in the optimization, control and signal processing communities. Such problems involve resource allocation, information processing, and learning among a set $\{1,\ldots,N\}$ of distributed agents connected through a network $G=(V,E)$, where $E$ denotes the set of $M$ undirected edges between the agents. In such applications, each agent has access to a privately known local objective (or cost) function, which represents the negative utility or the loss agent $i$ incurs at the decision variable $x$. The goal is to collectively solve a global optimization problemThe usefulness of formulation (2) can be illustrated by, among other things, machine learning problems described as follows: $\displaystyle\min_{x}\sum_{i=1}^{N-1}l\left([W_{i}x-b_{i}]\right)+\pi\left|\left|x\right|\right|_{1},$ where $W_{i}$ corresponds to the input sample data (and functions thereof), $b_{i}$ represents the measured outputs, $W_{i}x-b_{i}$ indicates the prediction error and $l$ is the loss function on the prediction error. Scalar $\pi$ is nonnegative and it indicates the penalty parameter on complexity of the model. The widely used Least Absolute Deviation (LAD) formulation, the Least-Absolute Shrinkage and Selection Operator (Lasso) formulation and $l_{1}$ regularized formulations can all be represented by the above formulation by varying loss function $l$ and penalty parameter $\pi$ (see for more details). The above formulation is a special case of the distributed multi-agent optimization problem (2), where $f_{i}(x)=l\left(W_{i}x-b_{i}\right)$ for $i=1,\ldots,N-1$ and $f_{N}=\pi_{2}\left|\left|x\right|\right|_{1}.$ In applications where the data pairs \big{(}W_{i},b_{i}\big{)} are collected and maintained by different sensors over a network, the functions $f_{i}$ are local to each agent and the need for a distributed algorithm arises naturally.

where $x$ is the vector $[x_{1},x_{2},\ldots,x_{N}]^{\prime}$. We will refer to this formulation as the edge-based reformulation of the multi-agent optimization problem. Note that this formulation is a special case of problem (1) with $D=A$, $H=0$ and $X_{i}=X$ for all $i$. Since these problems often lack a centralized processing unit, it is imperative that iterative solutions of problem (2) involve decentralized computations, meaning that each node (processor) performs calculations independently and on the basis of local information available to it and then communicates this information to its neighbors according to the underlying network structure.

Though there have been many important advances in the design of decentralized optimization algorithms for multi-agent optimization problems, several challenges still remain. First, many of these algorithms are based on first-order subgradient methods, which have slow convergence rates (given by $O(1/\sqrt{k})$ where $k$ is the iteration number), making them impractical in many large scale applications. Second, with the exception of a few recent contributions, existing algorithms are synchronous, meaning that computations are simultaneously performed according to some global clock, but this often goes against the highly decentralized nature of the problem, which precludes such global information being available to all nodes.

In this paper, we focus on the more general formulation (1) and propose an asynchronous decentralized algorithm based on the classical Alternating Direction Method of Multipliers (ADMM) (see , for comprehensive tutorials). We adopt the following asynchronous implementation for our algorithm: at each iteration $k$, a random subset $\Psi^{k}$ of the constraints are selected, which in turn selects the components of $x$ that appear in these constraints. We refer to the selected constraints as active constraints and selected components as the active components (or agents). We design an ADMM-type primal-dual algorithm which at each iteration updates the primal variables using partial information about the problem data, in particular using cost functions corresponding to active components and active constraints, and updates the dual variables corresponding to active constraints. In the context of the edge-based reformulated multi-agent optimization problem (3), this corresponds to a fully decentralized and asynchronous implementation in which a subset of the edges are randomly activated (for example according to local clocks associated with those edges) and the agents incident to those edges perform computations on the basis of their local objective functions followed by communication of updated values with neighbors.

Under the assumption that each constraint has a positive probability of being selected and the constraints have a decoupled structure (which is satisfied by reformulations of the distributed multi-agent optimization problem), our first result shows that the (primal) asynchronous iterates generated by this algorithm converge almost surely to an optimal solution. Our proof relies on relating the asynchronous iterates to full-information iterates that would be generated by the algorithm that use full information about the cost functions and constraints at each iteration. In particular, we introduce a weighted norm where the weights are given by the inverse of the probabilities with which the constraints are activated and constructs a Lyapunov function for the asynchronous iterates using this weighted norm. Our second result establishes a performance guarantee of $O(1/k)$ for this algorithm under a compactness assumption on the constraint sets $X$ and $Z$, which to our knowledge is faster than the guarantees available in the literature for this problem. More specifically, we show that the expected value of the difference of the objective function value and the optimal value as well as the expected feasibility violation converges to 0 at rate $O(1/k)$.

Our paper is related to a large recent literature on distributed optimization methods for solving the multi-agent optimization problem. Most closely related is a recent stream which proposed distributed synchronous ADMM algorithms for solving problem (2) (or specialized versions of it) (see , , , , ). These papers have demonstrated the excellent computational performance of ADMM algorithms in the context of several signal processing applications. A closely related work in this stream is our recent paper , where we considered problem (2) under the general assumption that the $f_{i}$ are convex. In , we presented an ADMM based algorithm which operates by updating the decision variable $x$ in $N$ steps in a synchronous manner using a deterministic cyclic order and showed that it converges at the rate $O(1/k)$. This algorithm however requires a synchronous implementation and a globally known order on the set of agents. The algorithm presented here selects a subset of the components of the decision variable $x$ randomly and updates the variables $(x,z)$ in two steps by first updating the selected components of $x$ and then updating the $z$ variable.

Another strand of this literature uses first-order (sub)gradient methods for solving problem (2). Much of this work builds on the seminal works and , which proposed gradient methods that can parallelize computations across multiple processors. The more recent paper introduced a first-order primal subgradient method for solving problem (2) over deterministically varying networks. This method involves each agent maintaining and updating an estimate of the optimal solution by linearly combining a subgradient step along its local cost function with averaging of estimates obtained from his neighbors (also known as a single consensus step).This work is clearly also related to the extensive literature on consensus and cooperative control, where the goal is to design local deterministic or random update rules to achieve global coordination (for deterministic update rules, see , , , , , , , , ; for random update rules, see , , , ). Several follow-up papers considered variants of this method for problems with local and global constraints , randomly varying networks , , and random gradient errors , . A different distributed algorithm that relies on Nesterov’s dual averaging algorithm for static networks has been proposed and analyzed in . Such gradient methods typically have a convergence rate of $O(1/\sqrt{k})$. The more recent contribution focuses on a special case of (2) under smoothness assumptions on the cost functions and availability of global information about some problem parameters, and provided gradient algorithms (with multiple consensus steps) which converge at the faster rate of $O(1/k^{2})$.

With the exception of and , all algorithms provided in the literature are synchronous and assume that computations at all nodes are performed simultaneously according to a global clock. provides an asynchronous subgradient method that uses gossip-type activation and communication between pairs of nodes and shows (under a compactness assumption on the iterates) that the iterates generated by this method converge almost surely to an optimal solution. The recent independent paper provides an asynchronous randomized ADMM algorithm for solving problem (2) and establishes convergence of the iterates to an optimal solution by studying the convergence of randomized Gauss-Seidel iterations on non-expansive operators. Our paper instead proposes an asynchronous ADMM algorithm for the more general problem (1) and uses a Lyapunov function argument for establishing $O(1/k)$ rate of convergence.

Our algorithm and analysis also build on and combines ideas from several important contributions in the study of ADMM algorithms. Earlier work in this area focuses on the case $C=2$, where $C$ refers to the number of sequential primal updates at each iteration, and studies convergence in the context of finding zeros of the sum of two maximal monotone operators (more specifically, the Douglas-Rachford operator), see , , . The recent contribution considered solving problem (1) (with $C=2$) with ADMM and showed that the objective function values of the iterates converge at the rate $O(1/k)$. Other recent works analyzed the rate of convergence of ADMM and other related algorithms under smoothness conditions on the objective function (see , , ). Another paper considered the case $C\geq 2$ and showed that the resulting ADMM algorithm, converges under the more restrictive assumption that each $f_{i}$ is strongly convex. The recent paper focused on the general case $C\geq 2$ and established a global linear convergence rate using an error bound condition that estimates the distance from the dual optimal solution set in terms of norm of a proximal residual.

The paper is organized as follows: we start in Section II by highlighting the main ideas of the standard ADMM algorithm. In Section III, we focus on the more general formulation (1), present the asynchronous ADMM algorithm and apply this algorithm to solve problem (2) in a distributed way. Section IV contains our convergence and rate of convergence analysis. Section V concludes with closing remarks.

II Preliminaries: Standard ADMM Algorithm

The standard ADMM algorithm solves a separable convex optimization problem where the decision vector decomposes into two variables and the objective function is the sum of convex functions over these variables that are coupled through a linear constraint:Interested readers can find more details in and .

We consider the augmented Lagrangian function of problem (4) obtained by adding a quadratic penalty for feasibility violation to the Lagrangian function:

We assume that the minimizers in steps (6) and (7) exist, however they need not be unique. Note that the stepsize used in updating the dual variable is the same as the penalty parameter $\beta$.

The ADMM algorithm takes advantage of the separable structure of problem (4) and decouples the minimization of functions $F_{s}$ and $G_{s}$ since the sequential minimization over $x$ and $z$ involves (quadratic perturbations) these functions separately. This is particularly useful in applications where the minimization over these component functions admit simple solutions and can be implemented in a parallel or decentralized manner.

The analysis of the ADMM algorithm adopts the following standard assumption on problem (4).

(Existence of a Saddle Point) The Lagrangian function of problem (4) given by

has a saddle point, i.e., there exists a solution-multiplier pair $(x^{*},z^{*},p^{*})$ with

Note that the existence of a saddle point is equivalent to the existence of a primal dual optimal solution pair. It is well-known that under the given assumptions, the objective function value of the primal sequence $\{x^{k},z^{k}\}$ generated by (6)-(7) converges to the optimal value of problem (4) and the dual sequence $\{p^{k}\}$ generated by (8) converges to a dual optimal solution (see Section 3.2 of ).

III Asynchronous ADMM Algorithm

Extending the standard ADMM, we present in this section an asynchronous distributed ADMM algorithm. We present the problem formulation and assumptions in Section III-A. In Section III-B, we discuss the asynchronous implementation considered in the rest of this paper that involves updating a subset of components of the decision vector at each time using partial information about problem data and without need for a global coordinator. Section III-C contains the details of the asynchronous ADMM algorithm. In Section III-D, we apply the asynchronous ADMM algorithm to solve the distributed multi-agent optimization problem (2).

We consider the optimization problem given in (1), which is restated here for convenience:

Similar to the standard ADMM formulation, we adopt the following assumption.

(Existence of a Saddle Point) The Lagrangian function of problem (1),

has a saddle point, i.e., there exists a solution-multiplier pair $(x^{*},z^{*},p^{*})$ with

Moreover, we assume that the matrices have special structure that enables solving problem (1) in an asynchronous manner:

(Decoupled Constraints) Matrix $H$ is diagonal and invertible. Each row of matrix $D$ has exactly one nonzero element and matrix $D$ has no columns of all zeros.We assume without loss of generality that each $x_{i}$ is involved at least in one of the constraints, otherwise, we could remove it from the problem and optimize it separately. Similarly, the diagonal elements of matrix $H$ are assumed to be non-zero, otherwise, that component of variable $z$ can be dropped from the optimization problem.

The diagonal structure of matrix $H$ implies that each component of vector $z$ appears in exactly one linear constraint. The conditions that each row of matrix $D$ has only one nonzero element and matrix $D$ has no column of zeros guarantee the columns of matrix $D$ are linearly independent and hence matrix $D^{\prime}D$ is positive definite. The condition on matrix $D$ implies that each row of the constraint $Dx+Hz=0$ involves exactly one $x_{i}$. We will see in Section III-D that this assumption is satisfied by the distributed multi-agent optimization problem that motivates this work.

III-B Asynchronous Algorithm Implementation

In the large scale multi-agent applications descried above, it is essential that the iterative solution of the problem involves computations performed by agents in a decentralized manner (with access to local information) with as little coordination as possible. This necessitates an asynchronous implementation in which some of the agents become active (randomly) in time and update the relevant components of the decision variable using partial and local information about problem data while keeping the rest of the components of the decision variable unchanged. This removes the need for a centralized coordinator or global clock, which is an unrealistic requirement in such decentralized environments.

To describe the asynchronous algorithm implementation we consider in this paper more formally, we first introduce some notation. We call a partition of the set $\{1,\ldots,W\}$ a proper partition if it has the property that if $z_{i}$ and $z_{j}$ are coupled in the constraint set $Z$, i.e., value of $z_{i}$ affects the constraint on $z_{j}$ for any $z$ in set $Z$, then $i$ and $j$ belong to the same partition, i.e., $\{i,j\}\subset\psi$ for some $\psi$ in the partition. We let $\Pi$ be a proper partition of the set $\{1,\ldots,W\}$ , which forms a partition of the set of $W$ rows of the linear constraint $Dx+Hz=0$. For each $\psi$ in $\Pi$, we define $\Phi(\psi)$ to be the set of indices $i$, where $x_{i}$ appears in the linear constraints in set $\psi$. Note that $\Phi(\psi)$ is an element of the power set $2^{\{1,\ldots,N\}}$.

At each iteration of the asynchronous algorithm, two random variables $\Phi^{k}$ and $\Psi^{k}$ are realized. While the pair $(\Phi^{k},\Psi^{k})$ is correlated for each iteration $k$, these variables are assumed to be independent and identically distributed across iterations. At each iteration $k$, first the random variable $\Psi^{k}$ is realized. The realized value, denoted by $\psi^{k}$, is an element of the proper partition $\Pi$ and selects a subset of the linear constraints $Dx+Hz=0$. The random variable $\Phi^{k}$ then takes the realized value $\phi^{k}=\Phi(\psi^{k})$. We can view this process as activating a subset of the coupling constraints and the components that are involved in these constraints. If $l\in\psi^{k}$, we say constraint $l$ as well as its associated dual variable $p_{l}$ is active at iteration $k$. Moreover, if $i\in\Phi(\psi^{k})$, we say that component $i$ or agent $i$ is active at iteration $k$. We use the notation $\bar{\phi}^{k}$ to denote the complement of set $\phi^{k}$ in set $\{1,\ldots,N\}$ and similarly $\bar{\psi}^{k}$ to denote the complement of set $\psi^{k}$ in set $\{1,\ldots,W\}$.

We impose the following condition on the asynchronous algorithm.

(Infinitely Often Update) For all $k$ and all $\psi$ in the proper partition $\Pi$,

This assumption ensures that each element of the partition $\Pi$ is active infinitely often with probability 1. Since matrix $D$ has no columns of all zeros, each of the $x_{i}$ is involved in some constraints, and hence $\cup_{\psi\in\Pi}\Phi(\psi)=\{1,\ldots,N\}$. The preceding assumption therefore implies that each agent $i$ belongs to at least one set $\Phi(\psi)$ and therefore is active infinitely often with probability $1$. From definition of the partition $\Pi$, we have $\cup_{\psi\in\Pi}\psi=\{1,\ldots,W\}$. Thus, each constraint $l$ is active infinitely often with probability $1$.

III-C Asynchronous ADMM Algorithm

We next describe the asynchronous ADMM algorithm for solving problem (1).

Initialization: choose some arbitrary $x^{0}$ in $X$, $z^{0}$ in $Z$ and $p^{0}=0$.

At iteration $k$, random variables $\Phi^{k}$ and $\Psi^{k}$ takes realizations $\phi^{k}$ and $\psi^{k}$. Function $f^{k}$ and matrices $D_{\phi^{k}}$, $H_{\psi^{k}}$ are generated accordingly.

with $x_{i}^{k+1}=x_{i}^{k}$, for $i$ in $\bar{\phi}^{k}$.

with $z_{i}^{k+1}=z_{i}^{k}$, for $i$ in $\bar{\psi}^{k}$.

We assume that the minimizers in updates (12) and (13) exist, but need not be unique.Note that the optimization in (12) and (13) are independent of components of $x$ not in $\phi^{k}$ and components of $z$ not in $\psi^{k}$ and thus the restriction of $x_{i}^{k+1}=x_{i}^{k}$, for $i$ not in $\phi^{k}$ and $z_{i}^{k+1}=z_{i}^{k}$, for $i$ not in $\psi^{k}$ still preserves optimality of $x^{k+1}$ and $z^{k+1}$ with respect to the optimization problems in update (12) and (13). The term $\frac{\beta}{2}\left|\left|D_{\phi^{k}}x+Hz^{k}\right|\right|^{2}$ in the objective function of the minimization problem in update (12) can be written as

where the last term is independent of the decision variable $x$ and thus can be dropped from the objective function. Therefore, the primal $x$ update can be written as

Similarly, the term $\frac{\beta}{2}\left|\left|H_{\psi^{k}}z+D_{\phi^{k}}x^{k+1}\right|\right|^{2}$ in update (13) can be expressed equivalently as

We can drop the term $\frac{\beta}{2}\left|\left|D_{\phi^{k}}x^{k+1}\right|\right|^{2}$, which is constant in $z$, and write update (13) as

The updates (15) and (16) make the dependence on the decision variables $x$ and $z$ more explicit and therefore will be used in the convergence analysis. We refer to (15) and (16) as the primal $x$ and $z$ update respectively, and (14) as the dual update.

III-D Special Case: Distributed Multi-agent Optimization

We apply the asynchronous ADMM algorithm to the edge-based reformulation of the multi-agent optimization problem (3).For simplifying the exposition, we assume $n=1$ and note that the results extend to $n>1$. Note that each constraint of this problem takes the form $x_{i}=x_{j}$ for agents $i$ and $j$ with $(i,j)\in E$. Therefore, this formulation does not satisfy Assumption 3.

We next introduce another reformulation of this problem, used also in Example 4.4 of Section 3.4 in , so that each each constraint only involves one component of the decision variable.Note that this reformulation can be applied to any problem with a separable objective function and linear constraints to turn it into a problem of form (1) that satisfies Assumption 3. More specifically, we let $N(e)$ denote the agents which are the endpoints of edge $e$ and introduce a variable $z=[z_{eq}]_{e=1,\ldots,M\atop q\in N(e)}$ of dimension 2$M$, one for each endpoint of each edge. Using this variable, we can write the constraint $x_{i}=x_{j}$ for each edge $e=(i,j)$ as

The variables $z_{ei}$ can be viewed as an estimate of the component $x_{j}$ which is known by node $i$. The transformed problem can be written compactly as

One natural implementation of the asynchronous algorithm is to associate with each edge an independent Poisson clock with identical rates across the edges. At iteration $k$, if the clock corresponding to edge $(i,j)$ ticks, then $\phi^{k}=\{i,j\}$ and $\psi^{k}$ picks the rows in the constraint associated with edge $(i,j)$, i.e., the constraints $x_{i}=z_{ei}$ and $-x_{j}=z_{ej}$.Note that this selection is a proper partition of the constraints since the set $Z$ couples only the variables $z_{ek}$ for the endpoints of an edge $e$.

The primal $z$ update involves a quadratic optimization problem with linear constraints which can be solved in closed form. In particular, using first order optimality conditions, we conclude

where $v^{k+1}$ is the Lagrange multiplier associated with the constraint $z_{ei}+z_{ej}=0$ and is given by

Combining these steps yields the following asynchronous algorithm for problem (3) which can be implemented in a decentralized manner by each node $i$ at each iteration $k$ having access to only his local objective function $f_{i}$, adjacency matrix entries $A_{ei}$, and his local variables $x_{i}^{k}$, $z_{ei}^{k}$, and $p_{ei}^{k}$ while exchanging information with one of his neighbors.The asynchronous ADMM algorithm can also be applied to a node-based reformulation of problem (2), where we impose the local copy of each node to be equal to the average of that of its neighbors. This leads to another asynchronous distributed algorithm with a different communication structure in which each node at each iteration broadcasts its local variables to all his neighbors, see for more details.

II. Asynchronous Edge Based ADMM algorithm:

Initialization: choose some arbitrary $x_{i}^{0}$ in $X$ and $z^{0}$ in $Z$, which are not necessarily all equal. Initialize $p_{ei}^{0}=0$ for all edges $e$ and end points $i$.

At time step $k$, the local clock associated with edge $e=(i,j)$ ticks,

Agents $i$ and $j$ update their estimates $x_{i}^{k}$ and $x_{j}^{k}$ simultaneously as

for $q=i,j$. The updated value of $x_{i}^{k+1}$ and $x_{j}^{k+1}$ are exchanged over the edge $e$.

Agents $i$ and $j$ exchange their current dual variables $p_{ei}^{k}$ and $p_{ej}^{k}$ over the edge $e$. For $q=i,j$, agents $i$ and $j$ use the obtained values to compute the variable $v^{k+1}$ as Eq. (20), i.e.,

and update their estimates $z_{ei}^{k}$ and $z_{ej}^{k}$ according to Eq. (19), i.e.,

Agents $i$ and $j$ update the dual variables $p_{ei}^{k+1}$ and $p_{ej}^{k+1}$ as

All other agents keep the same variables as the previous time.

IV Convergence Analysis for Asynchronous ADMM Algorithm

In this section, we study the convergence behavior of the asynchronous ADMM algorithm under Assumptions 2-4. We show that the primal iterates $\{x^{k},z^{k}\}$ generated by (15) and (16) converge almost surely to an optimal solution of problem (1). Under the additional assumption that the constraint sets $X$ and $Z$ are compact, we further show that the corresponding objective function values converge to the optimal value in expectation at rate $O(1/k)$.

We first recall the relationship between the sets $\phi^{k}$ and $\psi^{k}$ for a particular iteration $k$, which plays an important role in the analysis. Since the set of active components at time $k$, $\phi^{k}$, represents all components of the decision variable that appear in the active constraints defined by the set $\psi^{k}$, we can write

We next consider a sequence $\{y^{k},v^{k},\mu^{k}\}$, which is formed of iterates defined by a “full information” version of the ADMM algorithm in which all constraints (and therefore all components) are active at each iteration. We will show that under the Decoupled Constraints Assumption (cf. Assumption 3), the iterates generated by the asynchronous algorithm $(x^{k},z^{k},p^{k})$ take the values of $(y^{k},v^{k},\mu^{k})$ over the sets of active components and constraints and remain at their previous values otherwise. This association enables us to perform the convergence analysis using the sequence $\{y^{k},v^{k},\mu^{k}\}$ and then translate the results into bounds on the objective function value improvement along the sequence $\{x^{k},z^{k},p^{k}\}$.

More specifically, at iteration $k$, we define $y^{k+1}$ by

Due to the fact that each row of matrix $D$ has only one nonzero element [cf. Assumption 3], the norm $\left|\left|Dy\right|\right|^{2}$ can be decomposed as $\sum_{i=1}^{N}\left|\left|D_{i}y_{i}\right|\right|^{2}$, where recall that $D_{i}$ is the matrix that picks up the columns corresponding to component $x_{i}$ and is equal to zero otherwise. Thus, the preceding optimization problem can be written as a separable optimization problem over the variables $y_{i}$:

Since $f^{k}(x)=\sum_{i\in\phi^{k}}f_{i}(x_{i})$, and $D_{\phi^{k}}=\sum_{i\in\phi^{k}}D_{i}$, the minimization problem that defines the iterate $x^{k+1}$ [cf. Eq. (15)] similarly decomposes over the variables $x_{i}$ for $i\in\Phi^{k}$. Hence, the iterates $x^{k+1}$ and $y^{k+1}$ are identical over the components in set $\phi^{k}$, i.e., $[x^{k+1}]_{\phi^{k}}=[y^{k+1}]_{\phi^{k}}$. Using the definition of matrix $D_{\phi^{k}}$, i.e., $D_{\phi^{k}}=\sum_{i\in\phi^{k}}D_{i}$, this implies the following relation:

The rest of the components of the iterate $x^{k+1}$ by definition remain at their previous value, i.e., $[x^{k+1}]_{\bar{\phi}^{k}}=[x^{k}]_{\bar{\phi}^{k}}$.

Similarly, we define vector $v^{k+1}$ in $Z$ by

Using the diagonal structure of matrix $H$ [cf. Assumption 3] and the fact that $\Pi$ is a proper partition of the constraint set [cf. Section III-B], this problem can also be decomposed in the following way:

where $H_{\psi}$ is a diagonal matrix that contains the $l^{th}$ diagonal element of the diagonal matrix $H$ for $l$ in set $\psi$ (and has zeros elsewhere) and set $Z_{\psi}$ is the projection of set $Z$ on component $[v]_{\psi}$. Since the diagonal matrix $H_{\psi^{k}}$ has nonzero elements only on the $l^{th}$ element of the diagonal with $l\in\psi^{k}$, the update of $[v]_{\psi}$ is independent of the other components, hence we can express the update on the components of $v^{k+1}$ in set $\psi^{k}$ as

By the primal $z$ update [cf. Eq. (16)], this shows that $[z^{k+1}]_{\psi^{k}}=[v^{k+1}]_{\psi^{k}}$. By definition, the rest of the components of $z^{k+1}$ remain at their previous values, i.e., $[z^{k+1}]_{\bar{\psi}^{k}}=[z^{k}]_{\bar{\psi}^{k}}$.

We relate this vector to the dual variable $p^{k+1}$ using the dual update [cf. Eq. (14)]. We also have

where the first equality follows from Eq. (23) and second is derived from Eq. (21). Moreover, since $H$ is diagonal, we have $[H_{\psi^{k}}z^{k+1}]_{\psi^{k}}=[Hv^{k+1}]_{\psi^{k}}$. Thus, we obtain $[p^{k+1}]_{\psi^{k}}=[\mu^{k+1}]_{\psi^{k}}$ and $[p^{k+1}]_{\bar{\psi}^{k}}=[p^{k}]_{\bar{\psi}^{k}}$.

A key term in our analysis will be the residual defined at a given primal vector $(y,v)$ by

The residual term is important since its value at the primal vector $(y^{k+1},v^{k+1})$ specifies the update direction for the dual vector $\mu^{k+1}$ [cf. Eq. (25)]. We will denote the residual at the primal vector $(y^{k+1},v^{k+1})$ by

We proceed to the convergence analysis of the asynchronous algorithm. We first present some preliminary results which will be used later to establish convergence properties of asynchronous algorithm. In particular, we provide bounds on the difference of the objective function value of the vector $y^{k}$ from the optimal value, the distance between $\mu^{k}$ and an optimal dual solution and distance between $v^{k}$ and an optimal solution $z^{*}$. We also provide a set of sufficient conditions for a limit point of the sequence $\{x^{k},z^{k},p^{k}\}$ to be a saddle point of the Lagrangian function. The results of this section are independent of the probability distributions of the random variables $\Phi^{k}$ and $\Psi^{k}$. Due to space constraints, the proofs of the results of in this section are omitted. We refer the reader to for the missing details.

The next lemma establishes primal feasibility (or zero residual property) of a saddle point of the Lagrangian function of problem (1).

Let $(x^{*},z^{*},p^{*})$ be a saddle point of the Lagrangian function defined as in Eq. (10) of problem (1). Then

The next theorem provides bounds on two key quantities, $F(y^{k+1})-\mu^{\prime}r^{k+1}$ and $\frac{1}{2\beta}\left|\left|\mu^{k+1}-p^{*}\right|\right|^{2}+\frac{\beta}{2}\left|\left|H(v^{k+1}-z^{*})\right|\right|^{2}$. These quantities will be related to the iterates generated by the asynchronous ADMM algorithm via a weighted norm and a weighted Lagrangian function in Section IV-B. The weighted version of the quantity $\frac{1}{2\beta}\left|\left|\mu^{k+1}-p^{*}\right|\right|^{2}+\frac{\beta}{2}\left|\left|H(v^{k+1}-z^{*})\right|\right|^{2}$ is used to show almost sure convergence of the algorithm and the quantity $F(y^{k+1})-\mu^{\prime}r^{k+1}$ is used in the convergence rate analysis.

Let $\{x^{k},z^{k},p^{k}\}$ be the sequence generated by the asynchronous ADMM algorithm (12)-(14). Let $\{y^{k},v^{k},\mu^{k}\}$ be the sequence defined in Eqs. (22)-(25) and $(x^{*},z^{*},p^{*})$ be a saddle point of the Lagrangian function of problem (1). The following hold at each iteration $k$:

The following lemma analyzes the limiting properties of the sequence $\{x^{k},z^{k},p^{k}\}$. The results will later be used in Lemma IV.5, which provides a set of sufficient conditions for a limit point of the sequence $\{x^{k},z^{k},p^{k}\}$ to be a saddle point.

Let $\{x^{k},z^{k},p^{k}\}$ be the sequence generated by the asynchronous ADMM algorithm (12)-(14). Let $\{y^{k},v^{k},\mu^{k}\}$ be the sequence defined in Eqs. (22), (24 and )(25). Consider a sample path of $\Psi^{k}$ and $\Phi^{k}$ along which the sequence $\left\{\left|\left|r^{k+1}\right|\right|^{2}+\left|\left|H(v^{k+1}-z^{k})\right|\right|^{2}\right\}$ converges to and the sequence $\{z^{k},p^{k}\}$ is bounded, where $r^{k}$ is the residual defined as in Eq. (27). Then, the sequence $\{x^{k},y^{k},z^{k}\}$ has a limit point, which is a saddle point of the Lagrangian function of problem (1).

IV-B Convergence and Rate of Convergence

The results of the previous section did not rely on the probability distributions of random variables $\Phi^{k}$ and $\Psi^{k}$. In this section, we will introduce a weighted norm and weighted Lagrangian function where the weights are defined in terms of the probability distributions of random variables $\Psi^{k}$ and $\Phi^{k}$ representing the active constraints and components. We will use the weighted norm to construct a nonnegative supermartingale along the sequence $\{x^{k},z^{k},p^{k}\}$ generated by the asynchronous ADMM algorithm and use it to establish the almost sure convergence of this sequence to a saddle point of the Lagrangian function of problem (1). By relating the iterates generated by the asynchronous ADMM algorithm to the variables $(y^{k},v^{k},\mu^{k})$ through taking expectations of the weighted Lagrangian function and using results from Theorem IV.2, we will show that under a compactness assumption on the constraint sets $X$ and $Z$, the asynchronous ADMM algorithm converges with rate $O(1/k)$ in expectation in terms of both objective function value and constraint violation.

We use the notation $\alpha_{i}$ to denote the probability that component $x_{i}$ is active at one iteration, i.e.,

and the notation $\lambda_{l}$ to denote the probability that constraint $l$ is active at one iteration, i.e.,

We use the symbol $\mathcal{J}_{k}$ to denote the filtration up to and include iteration $k$, which contains information of random variables $\Phi^{t}$ and $\Psi^{t}$ for $t\leq k$. We have $\mathcal{J}_{k}\subset\mathcal{J}_{k+1}$ for all $k\geq 1$.

Let $\{x^{k},z^{k},p^{k}\}$ be the sequence generated by the asynchronous ADMM algorithm (12)-(14). Let $\{y^{k},v^{k},\mu^{k}\}$ be the sequence defined in Eqs. (22), (24), (25). Then the following hold for each iteration $k$:

By the definition of $\lambda_{l}$ in Eq. (32), for each $l$, the element $p^{k+1}_{l}$ can be either updated to $\mu^{k+1}_{l}$ with probability $\lambda_{l}$, or stay at previous value $p_{l}^{k}$ with probability $1-\lambda_{l}$. Hence, we have the following expected value

where the second equality follows from definition of $\left|\left|\cdot\right|\right|_{\bar{\Lambda}}$, and grouping the terms.

Similarly, $z^{k+1}_{l}$ is either equal to $v^{k+1}_{l}$ with probability $\lambda_{l}$ or $z^{k}_{l}$ with probability $1-\lambda_{l}$. Due to the diagonal structure of the $H$ matrix, the vector $H_{l}z$ has only one non-zero element equal to $[Hz]_{l}$ at $l^{th}$ position and zeros else where. Thus, we obtain

where we used the definition of $\left|\left|\cdot\right|\right|_{\bar{\Lambda}}$ once again. By summing the above two equations and using linearity of expectation operator, we obtain Eq. (34).

where we used the fact that $D=\sum_{i=1}^{N}D_{i}$. Using the definition $F(x)=\sum_{i=1}^{N}f_{i}(x)$ [cf. Eq. (9)], this shows Eq. (IV.4).

The next lemma builds on Lemma IV.3 and establishes a sufficient condition for the sequence $\{x^{k},z^{k},p^{k}\}$ to converge to a saddle point of the Lagrangian. Theorem IV.6 will then show that this sufficient condition holds with probability 1 and thus the algorithm converges almost surely.

Let $(x^{*},z^{*},p^{*})$ be any saddle point of the Lagrangian function of problem (1) and $\{x^{k},z^{k},p^{k}\}$ be the sequence generated by the asynchronous ADMM algorithm (12)-(14). Along any sample path of $\Phi^{k}$ and $\Psi^{k}$, if the scalar sequence $\frac{1}{2\beta}\left|\left|p^{k+1}-p^{*}\right|\right|^{2}_{\bar{\Lambda}}+\frac{\beta}{2}\left|\left|H(z^{k+1}-z^{*})\right|\right|^{2}_{\bar{\Lambda}}$ is convergent and the scalar sequence $\frac{\beta}{2}\left[\left|\left|r^{k+1}\right|\right|^{2}+\left|\left|H(v^{k+1}-z^{k})\right|\right|^{2}\right]$ converges to , then the sequence $\{x^{k},z^{k},p^{k}\}$ converges to a saddle point of the Lagrangian function of problem (1).

Since the scalar sequence $\frac{1}{2\beta}\left|\left|p^{k+1}-p^{*}\right|\right|^{2}_{\bar{\Lambda}}+\frac{\beta}{2}\left|\left|H(z^{k+1}-z^{*})\right|\right|^{2}_{\bar{\Lambda}}$ converges, matrix $\bar{\Lambda}$ is positive definite, and matrix $H$ is invertible [cf. Assumption 3], it follows that the sequences $\{p^{k}\}$ and $\{z^{k}\}$ are bounded. Lemma IV.3 then implies that the sequence $\{x^{k},z^{k},p^{k}\}$ has a limit point.

The next theorem establishes almost sure convergence of the asynchronous ADMM algorithm. Our analysis uses results related to supermartingales (interested readers are referred to and for a comprehensive treatment of the subject).

Let $\{x^{k},z^{k},p^{k}\}$ be the sequence generated by the asynchronous ADMM algorithm (12)-(14). The sequence $\{x^{k},z^{k},p^{k}\}$ converges almost surely to a saddle point of the Lagrangian function of problem (1).

We will show that the conditions of Lemma IV.5 are satisfied almost surely. We will first focus on the scalar sequence $\frac{1}{2\beta}\left|\left|p^{k+1}-\mu\right|\right|^{2}_{\bar{\Lambda}}+\frac{\beta}{2}\left|\left|H(z^{k+1}-v)\right|\right|^{2}_{\bar{\Lambda}}$ and show that it is a nonnegative supermartingale. By martingale convergence theorem, this shows that it converges almost surely. We next establish that the scalar sequence $\frac{\beta}{2}\left|\left|r^{k+1}-H(v^{k+1}-z^{k})\right|\right|^{2}$ converges to 0 almost surely by an argument similar to the one used to establish Borel-Cantelli lemma. These two results imply that the set of events where $\frac{1}{2\beta}\left|\left|p^{k+1}-p^{*}\right|\right|^{2}_{\bar{\Lambda}}+\frac{\beta}{2}\left|\left|H(z^{k+1}-z^{*})\right|\right|^{2}_{\bar{\Lambda}}$ is convergent and $\frac{\beta}{2}\left[\left|\left|r^{k+1}\right|\right|^{2}+\left|\left|H(v^{k+1}-z^{k})\right|\right|^{2}\right]$ converges to has probability $1$. Hence, by Lemma IV.5, we have the sequence $\{x^{k},z^{k},p^{k}\}$ converges to a saddle point of the Lagrangian function almost surely.

We first show that the scalar sequence $\frac{1}{2\beta}\left|\left|p^{k+1}-\mu\right|\right|^{2}_{\bar{\Lambda}}+\frac{\beta}{2}\left|\left|H(z^{k+1}-v)\right|\right|^{2}_{\bar{\Lambda}}$ is a nonnegative supermartingale. Since it is a summation of two norms, it immediately follows that it is nonnegative. To see it is a supermartingale, we let vectors $y^{k+1},v^{k+1},\mu^{k+1}$ and $r^{k+1}$ be those defined in Eqs. (22), (24), (25) and (27). Recall that the symbol $\mathcal{J}_{k}$ denotes the filtration up to and including iteration $k$. From Lemma IV.4, we have

Substituting $\mu=p^{*}$ and $v=z^{*}$ in the above expectation calculation and combining with the following inequality from Theorem IV.2,

Hence, the sequence $\frac{1}{2\beta}\left|\left|p^{k+1}-p^{*}\right|\right|^{2}_{\bar{\Lambda}}+\frac{\beta}{2}\left|\left|H(z^{k+1}-z^{*})\right|\right|^{2}_{\bar{\Lambda}}$ is a nonnegative supermartingale in $k$ and by martingale convergence theorem, it converges almost surely.

We next establish that the scalar sequence $\left\{\frac{\beta}{2}\left|\left|r^{k+1}\right|\right|^{2}+\frac{\beta}{2}\left|\left|H(v^{k+1}-z^{k})\right|\right|^{2}\right\}$ converges to 0 almost surely. Rearranging the terms in the previous inequality and taking iterated expectation with respect to the filtration $\mathcal{J}_{k}$, we obtain for all $T$

for any scalar $\epsilon>0$ for all iterations $t$. Therefore, we have

where the first inequality follows from union bound on probability, the second inequality follows from the preceding relation, and the last equality follows from Eq. (37). This proves that the sequence $\frac{\beta}{2}\left[\left|\left|r^{k+1}\right|\right|^{2}+\left|\left|H(v^{k+1}-z^{k})\right|\right|^{2}\right]$ converges to almost surely. ∎

The reason that such scalar $\bar{Q}<\infty$ exists is once again by Weierstrass theorem (maximization over a compact set).

The proof of the theorem relies on Lemma IV.4 and Theorem IV.2. We combine these results with law of iterated expectation, telescoping cancellation and convexity of the function $F$ to establish the bound

We will first prove Eq. (46). Recall Eq. (IV.4):

We rearrange Eq. (29) from Theorem IV.2, and obtain

Since $r^{k+1}=Dy^{k+1}+Hv^{k+1}$, we can apply this bound on the first term on the right-hand side of the preceding relation which implies

Combining the above inequality with Eq. (34) and using the linearity of expectation, we have

where the last inequality follows from relaxing the upper bound by dropping the non-positive term $-\frac{\beta}{2}\left|\left|r^{k+1}\right|\right|^{2}-\frac{\beta}{2}\left|\left|H(v^{k+1}-z^{k})\right|\right|^{2}$.

This relation holds for $k=1,\ldots,T$ and by the law of iterated expectation, the telescoping sum after term cancellation satisfies

By convexity of the functions $f_{i}$, we have

The same results hold after taking expectation on both sides. By linearity of matrix-vector multiplication, we have $\sum_{k=1}^{T}Dx^{k}=TD\bar{x}(T),\ \sum_{k=1}^{T}Hz^{k}=TH\bar{z}(T).$ Relation (47) therefore implies that

Using the definition of scalar $Q(\mu)$ [cf. Eq. (40)] and by dropping the non-positive norm terms from the above upper bound, we obtain

We now divide both sides of the preceding inequality by $T$ and obtain Eq. (46).

Since the point $(x^{*},z^{*},p^{*})$ is a saddle point of the Lagrangian function, using Lemma IV.1, we have

which shows the first desired inequality.

To prove Eq. (45), we let $\mu=p^{*}$ in Eq. (46) and obtain

This inequality together with Eq. (48) imply

The above inequality combined with Eq. (44) yields

Thus we have established the desired relation (45). ∎

V Conclusions

We developed a fully asynchronous ADMM based algorithm for a convex optimization problem with separable objective function and linear constraints. This problem is motivated by distributed multi-agent optimization problems where a (static) network of agents each with access to a privately known local objective function seek to optimize the sum of these functions using computations based on local information and communication with neighbors. We show that this algorithm converges almost surely to an optimal solution. Moreover, the rate of convergence of the objective function values and feasibility violation is given by $O(1/k)$. Future work includes investigating network effects (e.g., effects of communication noise, quantization) and time-varying network topology on the performance of the algorithm.

References