Asynchronous Distributed Optimization using a Randomized Alternating Direction Method of Multipliers

I Introduction

Consider a network represented by a set $V$ of agents seeking to solve the following optimization problem on a Euclidean space $\mathsf{X}$:

where $f_{v}$ is a convex real function known by agent $v$ only. Function $f_{v}$ can be interpreted as the price payed by an agent $v$ when the global network state is equal to $x$.

This problem arises for instance in cloud learning applications where massive data sets are distributed in a network and processed by distinct virtual machines . We investigate distributed optimization algorithms: agents iteratively update a local estimate using their private objective $f_{v}$ and, simultaneously, exchange information with their neighbors in order to eventually reach a consensus on the global solution. Standard algorithms are generally synchronous: all agents are supposed to complete their local computations synchronously at each tick of an external clock, and then synchronously merge their local results. However, in many situations, one faces variable sizes of the local data sets along with heterogeneous computational abilities of the virtual machines. Synchronism then becomes a burden, as the global convergence rate is expected to depend on the local computation times of the slowest agents. It is crucial to introduce asynchronous methods which allow the estimates to be updated in a non-coordinated fashion, rather than all together or in some frozen order.

The literature contains at least three classes of distributed optimization methods for solving (1). The first one is based on the simultaneous use of a local first-order optimization algorithm (subgradient algorithm , Nesterov-like method ) and a gossip process which drives the network to a consensus. A second class of methods is formed by distributed Newton-Raphson methods . This paper focuses on a third class of methods derived from proximal splitting methods . Perhaps the most emblematic proximal splitting method is the so-called Alternating Direction Method of Multipliers (ADMM) recently popularized to multiagent systems by the monograph . Schizas et al. demonstrated the remarkable potential of ADMM to handle distributed optimization problems and introduce a useful framework to encompass graph-constrained communications . We also refer to for recent contributions. However, all of these works share a common perspective: Algorithms are synchronous. They require a significant amount of coordination or scheduling between agents. In , agents operate in parallel, whereas proposes a sequential version of ADMM where agents operate one after the other in a predetermined order.

Contributions. This paper introduces a novel class of distributed algorithms to solve (1). The algorithms are asynchronous in the sense that some components of the network are allowed to wake up at random and perform local updates, while the rest of the network stands still. No coordinator or global clock is needed. The frequency of activation of the various network components is likely to vary. The algorithms rely on the introduction of randomized Gauss-Seidel iterations of a Douglas-Rachford monotone operator. We prove that the latter iterations provides a new powerful method for finding the zeros of a sum of two monotone operators. Application of our method to problem (1) yields a randomized ADMM-like algorithm, which is proved to converge to the sought minimizers.

The paper is organized as follows. The distributed optimization problem is rigorously stated in Section II. The synchronous ADMM algorithm that solves this problem is then described in Section III. Section IV forms the core of the paper. After quickly recalling the monotone operator formalism, the random Gauss-Seidel form of the proximal algorithm is described and its convergence is shown there. These results will eventually lead to an asynchronous version of the well-known Douglas-Rachford splitting algorithm. In Section V, the results of Section IV are applied towards developing an asynchronous version of the ADMM algorithm. An implementation example is finally provided in Section VI along with some simulations in Section VII.

We denote by $\Pi_{A}x$ the restriction of $x$ to $A$ i.e., $\Pi_{A}:\mathsf{X}^{V}\to\mathsf{X}^{A}$ is the linear operator defined for any $x\in\mathsf{X}^{V}$ as $\Pi_{A}x:(v\in A)\mapsto x(v)$. We denote by $1_{A}\in\mathsf{X}^{A}$ the constant function equal to one and by $\text{sp}(1_{A})$ the linear span of $1_{A}$ i.e., the set of constant functions on $A$. Notation $|A|$ represents the cardinal of a set $A$.

For a closed proper convex function $h:\mathsf{X}\to(-\infty,+\infty]$ we define $\text{prox}_{h,\rho}(x)=\arg\min_{y}h(y)+\frac{\rho}{2}\|y-x\|^{2}$.

II Distributed Optimization on a Graph

Consider a network of agents represented by a non-oriented graph $G=(V,E)$ where $V$ is a finite set of vertices (i.e., the agents) and $E$ is a set of edges. Each agent $v\in V$ has a private cost function $f_{v}:\mathsf{X}\to(-\infty,+\infty]$ where $\mathsf{X}$ is a Euclidean space. We make the following assumption on functions $f_{v}$.

i) For all $v\in V$, $f_{v}$ is a proper closed convex function. ii) The infimum in (1) is finite and is attained at some point $x^{*}\in\mathsf{X}$.

In order to solve the optimization problem (1) on the graph $G$, we first provide an equivalent formulation of (1) that will be revealed useful. For some integer $L\geq 1$, consider a finite collection $A_{1},A_{2},\cdots,A_{L}$ of subsets of $V$ which we shall refer to as components. We assume the following condition.

We introduce some notations. We set for any $x\in\mathsf{X}^{V}$,

For any $z=(z_{1},\cdots,z_{L})\in\mathsf{Z}\triangleq\mathsf{X}^{A_{1}}\times\cdots\times\mathsf{X}^{A_{L}}$, we define the closed proper convex function

Under Assumption 2, $x$ is a minimizer of (2) if and only if $x=\bar{x}1_{V}$ where $\bar{x}\in\mathsf{X}$ is a minimizer of (1).

As noted in , solving Problem (2) is equivalent to the search of the zeros of two monotone operators. One of possible approaches for that sake is to use ADMM. Although the choice of the sets $A_{1},\cdots,A_{L}$ does not change the minimizers of the initial problem, it has an impact on the particular form of ADMM used to find these minimizers, as we shall see below.

In order to be more explicit, we provide in this section two important examples of possible choices for the components $A_{1},\cdots,A_{L}$.

Let $L=1$ and $A_{1}=V$. Problem (2) writes

In this case, the formulation is identical to [11, Chapter 7].

where $\boldsymbol{1}_{2}$ stands for the vector $(1,1)^{T}$.

III Synchronous ADMM

We now apply the standard ADMM to Problem (2). Perhaps the most direct way to describe ADMM is to reformulate the unconstrained problem (2) into the following constrained problem: Minimize $f(x)+g(z)$ subject to $z=Mx$. For any $x\in\mathsf{X}^{V}$, $\lambda,z\in\mathsf{Z}$, the augmented Lagrangian is given by

where $\rho>0$ is a constant. ADMM consists of the iterations

From [11, Chap. 3.2], the following result is immediate.

Under Assumption 1, the sequence $(x^{k})$ defined in (4a) converges to a minimizer of (2).

III-B Decentralized Implementation

Now consider the first update equation (4a). Getting rid of all quantities in $\mathcal{L}_{\rho}$ which do not depend on the $v$th component of $x$, we obtain for any $v\in V$

After some algebra, the above equation further simplifies to

where we introduced the following constants:

For each agent $v$, compute $Z^{k+1}(v)$ and $B^{k+1}(v)$ using (6) and (9) respectively.

It is worth noting that in the case of Example 1, the synchronous ADMM described above coincides with the algorithm of .

IV A Randomized Proximal Algorithm

An operator $\mathsf{T}$ on a Euclidean space $\mathsf{Y}$ is a set valued mapping $\mathsf{T}:{\mathsf{Y}}\to 2^{\mathsf{Y}}$. An operator can be equivalently identified with a subset of $\mathsf{Y}\times\mathsf{Y}$, and we write $(x,y)\in\mathsf{T}$ when $y\in\mathsf{T}(x)$. Given two operators $\mathsf{T}_{1}$ and $\mathsf{T}_{2}$ on $\mathsf{Y}$ and two real numbers $\alpha_{1}$ and $\alpha_{2}$, the operator $\alpha_{1}\mathsf{T}_{1}+\alpha_{2}\mathsf{T}_{2}$ is defined as $\alpha_{1}\mathsf{T}_{1}+\alpha_{2}\mathsf{T}_{2}=\{(x,\alpha_{1}y_{1}+\alpha_{2}y_{2})\,:\,(x,y_{1})\in\mathsf{T}_{1},\,(x,y_{2})\in\mathsf{T}_{2}\}$. The identity operator is $\mathsf{I}=\{(x,x):x\in\mathsf{Y}\}$ and the inverse of the operator $\mathsf{T}$ is $\mathsf{T}^{-1}=\{(x,y):(y,x)\in\mathsf{T}\}$. The operator $\mathsf{T}$ is said monotone if

A monotone operator is said maximal if it is not strictly contained in any monotone operator (as a subset of $\mathsf{Y}\times\mathsf{Y}$). Finally, $\mathsf{T}$ is said firmly non-expansive if

The typical example of a monotone operator is the subdifferential $\partial f$ of a convex function $f:\mathsf{Y}\to\mathds{R}$. Finding a minimum of $f$ amounts to finding a point in $\operatorname*{zer}(\partial f)$, where $\operatorname*{zer}(\mathsf{T})=\{x:0\in\mathsf{T}(x)\}$ is the set of zeroes of an operator $\mathsf{T}$. A common technique for finding a zero of a maximal monotone operator $\mathsf{T}$ is the so-called proximal point algorithm that we now describe. The resolvent of $\mathsf{T}$ is the operator $\mathsf{J}_{\rho\mathsf{T}}\triangleq(\mathsf{I}+\rho\mathsf{T})^{-1}$ for $\rho>0$. One key result (see e.g. ) says that $\mathsf{T}$ is maximal monotone if and only if $\mathsf{J}_{\rho\mathsf{T}}$ is firmly non expansive and its domain is $\mathsf{Y}$. Observe that a firmly non expansive operator is single valued and denote by $\operatorname*{fix}(\mathsf{J}_{\rho\mathsf{T}})$ the set of fixed points of $\mathsf{J}_{\rho\mathsf{T}}$. It is clear that $\operatorname*{fix}(\mathsf{J}_{\rho\mathsf{T}})=\operatorname*{zer}(\mathsf{T})$. The firm non expansiveness of $\mathsf{J}_{\rho\mathsf{T}}$ plays a central role in the proof of the following result:

If $\mathsf{T}$ is a maximal monotone operator and $\rho>0$, then the iterates $\zeta^{k+1}=\mathsf{J}_{\rho\mathsf{T}}(\zeta^{k})$ starting at any point of $\mathsf{Y}$ converge to a point of $\operatorname*{fix}(\mathsf{J}_{\rho\mathsf{T}})$ whenever this set is non-empty.

IV-B Random Gauss-Seidel iterations

We are interested here in the convergence of the random iterates $\zeta^{k+1}=\hat{\mathsf{S}}_{\xi^{k+1}}(\zeta^{k})$ towards a (generally random) point of $\operatorname*{fix}(\mathsf{S})$, provided this set is non empty:

Let $\mathsf{S}$ is a firmly non-expansive operator on $\mathsf{Y}$ with domain $\mathsf{Y}$. Let $(\xi^{k})_{k\in\mathds{N}}$ be a sequence of random variables satisfying Assumption 3. Assume that $\operatorname*{fix}(\mathsf{S})\neq\emptyset$. Then for any initial value $\zeta^{0}$, the sequence of iterates $\zeta^{k+1}=\hat{\mathsf{S}}_{\xi^{k+1}}(\zeta^{k})$ converges almost surely to a random variable supported by $\operatorname*{fix}(\mathsf{S})$.

Since $(\mathsf{I}-\mathsf{S})(\zeta^{\star})=0$, we have

where the inequality comes from the easily verifiable fact that $(\mathsf{I}-\mathsf{S})$ is firmly non-expansive when $\mathsf{S}$ is. This leads to the inequality

which shows that $\left|\!\left|\!\left|\zeta^{k}-\zeta^{\star}\right|\!\right|\!\right|^{2}$ is a nonnegative supermartingale with respect to the filtration $({\mathcal{F}}_{k})$. As such, it converges with probability one towards a random variable $X_{\zeta^{\star}}$ satisfying $0\leq X_{\zeta^{\star}}<\infty$ almost everywhere. Given a countable dense subset $H$ of $\operatorname*{fix}(\mathsf{S})$, there is a probability one set on which $\left|\!\left|\!\left|\zeta^{k}-{\boldsymbol{\zeta}}\right|\!\right|\!\right|\to X_{\boldsymbol{\zeta}}\in[0,\infty)$ for all ${\boldsymbol{\zeta}}\in H$. Let $\zeta^{\star}\in\operatorname*{fix}(\mathsf{S})$, let $\varepsilon>0$, and choose ${\boldsymbol{\zeta}}\in H$ such that $\left|\!\left|\!\left|\zeta^{\star}-\boldsymbol{\zeta}\right|\!\right|\!\right|\leq\varepsilon$. With probability one, we have

for $k$ large enough. Similarly, $\left|\!\left|\!\left|\zeta^{k}-\zeta^{\star}\right|\!\right|\!\right|\geq X_{\boldsymbol{\zeta}}-2\varepsilon$ for $k$ large enough. We therefore obtain:

There is a probability one set on which $\left|\!\left|\!\left|\zeta^{k}-\zeta^{\star}\right|\!\right|\!\right|$ converges for every $\zeta^{\star}\in\operatorname*{fix}(\mathsf{S})$.

Getting back to Inequality (11), taking the expectations on both sides of this inequality and iterating over $k$, we obtain

By Markov’s inequality and Borel Cantelli’s lemma, we therefore obtain:

$S(\zeta^{k})-\zeta^{k}\to 0$ almost surely.

We now consider an elementary event in the probability one set where C1 and C2 hold. On this event, since $\left|\!\left|\!\left|\zeta^{k}-\zeta^{\star}\right|\!\right|\!\right|$ converges for $\zeta^{\star}\in\operatorname*{fix}(\mathsf{S})$, the sequence $\zeta^{k}$ is bounded. Since $\mathsf{S}$ is firmly non expansive, it is continuous, and C2 shows that all the accumulation points of $\zeta^{k}$ are in $\operatorname*{fix}(\mathsf{S})$. It remains to show that these accumulation points reduce to one point. Assume that $\zeta_{1}^{\star}$ is an accumulation point. By C1, $\left|\!\left|\!\left|\zeta^{k}-\zeta^{\star}_{1}\right|\!\right|\!\right|$ converges. Therefore, $\lim\left|\!\left|\!\left|\zeta^{k}-\zeta^{\star}_{1}\right|\!\right|\!\right|=\liminf\left|\!\left|\!\left|\zeta^{k}-\zeta^{\star}_{1}\right|\!\right|\!\right|=0$, which shows that $\zeta^{\star}_{1}$ is unique. ∎

V Random ADMM

We now return to the optimization problem (2). It is a well known fact that the standard ADMM can be seen as special case of the so-called Douglas-Rachford algorithm . The Douglas-Rachford algorithm can itself be seen as a special case of a proximal point algorithm. By the results of the previous section, this suggests that random Gauss-Seidel iterations applied to the Douglas-Rachford operator produce a sequence which eventually converges to the sought solutions. It turns out that the latter random iterations can be written under the form of practical asynchronous ADMM-like algorithm.

Consider the following dual problem associated with (2)

where $f^{*},g^{*}$ are the Fenchel conjugates of $f$ and $g$ and $M^{*}$ is the adjoint of $M$. By Assumption 1 along with [16, Th.3.3.5], the minimum in (12) is attained and its opposite coincides with the minimum of (2). Note that $\lambda$ is a minimizer of (12) iff zero belongs to the subdifferential of the objective function in (12). By [16, Th.3.3.5] again, this reads $0\in-M\cdot\partial f^{*}(-M^{*}\lambda)+\partial g^{*}(\lambda)$. Otherwise stated, finding minimizers of the dual problem (12) boils down to searching zeros of the sum of two maximal monotone operators $\mathsf{T}+\mathsf{U}$ defined by $\mathsf{T}=-M\cdot\partial f^{*}\circ(-M^{*})$ and $\mathsf{U}=\partial g^{*}$. For a fixed $\rho>0$, the Douglas-Rachford / Lions-Mercier operator $\mathsf{R}$ is defined as

The following Lemma is an immediate consequence of .

Under Assumption 1, $\mathsf{R}$ is maximal monotone, and $\operatorname*{zer}(\mathsf{R})\neq\emptyset$. Moreover, $\mathsf{J}_{\rho\mathsf{U}}(\zeta)\in\operatorname*{zer}(\mathsf{T}+\mathsf{U})$ for any $\zeta\in\operatorname*{zer}(\mathsf{R})$.

Lemma 3 implies that the search for a zero of $\mathsf{T}+\mathsf{U}$ boils down to the search of a zero of $\mathsf{R}$ up to a resolvent step $\mathsf{J}_{\rho\mathsf{U}}$. To that end, a standard approach is to use a proximal point algorithm of the form $\zeta^{k+1}=\mathsf{J}_{\mathsf{R}}(\zeta^{k})$. By , it can be shown that this approach is equivalent to the ADMM derived in Section II. Here, our aim is different. We shall consider random Gauss-Seidel iterations in order to derive an asynchronous version of the ADMM.

V-B Random Gauss-Seidel Iterations

Let Assumptions 1, 2 and 3 hold true. Consider the sequence $(\zeta^{k})_{k}$ defined by $\zeta^{k+1}=\hat{\mathsf{S}}_{\xi^{k+1}}(\zeta^{k})$. Then for any initial value $\zeta^{0}$, the sequence $\lambda^{k}\triangleq\mathsf{J}_{\rho\mathsf{U}}(\zeta^{k})$ converges almost surely to a minimizer of (12).

In order to complete the above result, we still must justify the fact that, as claimed, the above iterations can be seen as an asynchronous distributed algorithm.

V-C Distributed Algorithm

i)-ii) Existence: Let us define $\lambda=\mathsf{J}_{\rho\mathsf{U}}(\zeta)$ and $z=(\zeta-\lambda)/\rho$. Trivially, $\lambda+\rho z=\zeta$. As $\zeta\in\lambda+\rho\mathsf{U}(\lambda)$, we deduce that $(\lambda,z)\in\mathsf{U}$. Uniqueness: For a fixed $(\lambda,z)\in\mathsf{U}$ satisfying $\lambda+\rho z=\zeta$, one has $\zeta\in(I+\rho\mathsf{U})(\lambda)$ and thus $\lambda=\mathsf{J}_{\rho\mathsf{U}}(\zeta)$. As a consequence, $z=(\zeta-\lambda)/\rho$.

iv) Operator $\mathsf{S}=\mathsf{J}_{\mathsf{R}}$ can be written as

VI Implementation Example

When the edge $\{v,w\}$ is activated, the following two $\text{prox}(\cdot)$ operations are performed by the agents:

The two agents exchange then the values $x^{k+1}(v)$ and $x^{k+1}(w)$ and perform the following operations:

We remark that this communication scheme is reminiscent of the so-called Random Gossip algorithm introduced in in the context of distributed averaging.

VII Numerical Results

We consider a network with $V=\{1,\ldots,5\}$ and with $E=\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,3\}\}$. We evaluate the behavior of: i) the Synchronous ADMM ii) the Asynchronous ADMM and iii) the Distributed Gradient Descent with $1/\sqrt{k}$ stepsize using Random Gossip as a communication algorithm. Each agent maintains a different quadratic convex function and their goal is to reach consensus over the minimizer of problem (1).

In Figure 1, we plot the squared error versus the number of primal updates for the three considered algorithms. We observe that our algorithm clearly outperforms the Distributed Gradient Descent.

References