Distributed Alternating Direction Method of Multipliers

We consider a network of agents that are cooperatively solving a global unconstrained optimization problem, where the objective function is the sum of privately known local objective functions of the agents. Recent literature on distributed optimization methods for solving this problem focused on subgradient based methods, which typically converge at the rate O (1/√k), where k is the number of iterations. In this paper, k we introduce a new distributed optimization algorithm based on Alternating Direction Method of Multipliers (ADMM), which is a classical method for sequentially decomposing optimization problems with coupled constraints. We show that this algorithm converges at the rate O (1/k).


I. INTRODUCTION
Some of the problems in machine learning and statistical inference, LASSO (least-absolute shrinkage and selection operator) for instance, can be characterized by a network of agents, where each of the agents is associated with a local cost function and the system objective is to minimize the sum of all local costs. The local cost functions are often determined by a large private data set, which makes passing information regarding the local cost function very difficult. These problems motivated research interest in developing distributed method for solving optimization problems [4], [7], [12], [13], [15], [18], [19].
There are two general types of distributed algorithms. The first type is (sub)gradient based, where at each step a (sub)gradient related step is taken, followed by averaging with neighbors. The computation at each step can be very inexpensive and lead to distributed implementations [4], [9], [8], [11], [13], [14]. The best known rate of convergence for subgradient based distributed methods is O( 1 √ k ). The second type of distributed algorithm is for solving constrained problems and it relies on dual methods. In these methods, at each step for a fixed dual variable, the primal variables are solved to minimize some Lagrangian related function, then the dual variables are updated accordingly [3], [6], [7], [17]. This type of methods is preferred when each agent can solve the local optimization problem efficiently. One of the well known method of this kind is the Alternating Direction Method of Multipliers (ADMM), which decomposes the original problem into two sub-problems, sequentially solves them and updates the dual variables associated with a coupling constraint at each iteration. The best known rate of convergence for the classic ADMM algorithm is O( 1 k ).
This work was supported by National Science Foundation under Career grant DMI-0545910 and AFOSR MURI FA9550-09-1-0538.
† Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology The drawback of the standard ADMM method is that it partitions the problem into only two subproblems and thus cannot be implemented in a distributed way for a larger network. In recent works [5], [16] and [10], distributed ADMM algorithms tailored for specific machine learning problems and parameter estimation in wireless sensor networks have been proposed without convergence rate analysis. In this work, we propose a distributed ADMM algorithm for an unconstrained general optimization problem over an Nagent network. We first transform the problem into one with constraints and then distribute the problem to N agents. Each agent implements the algorithm using local cost functions and information obtained via communication with neighbors. We also establish that the proposed algorithm has O( 1 k ) rate of convergence.
In the distributed ADMM algorithm, the updates of the agents are done in a sequential order. 1 In this sense, our proposed method is closely related to incremental distributed algorithms studied in the literature [2], [15], where each agent takes turn to update the system wide decision variable and passes the updated variable to the network. The difference here is that each agent maintains and updates its local estimate. The analysis in this paper is related to [3] and [6]. In both of the works, convergence analysis are done to the standard ADMM algorithm. One of our contributions is to extend the analysis to the distributed ADMM algorithm with N agents.
The rest of the paper is organized as follows. Section II defines the problem formulation and equivalent transformation. In Section III, we review the standard ADMM algorithm and develop the distributed ADMM method. In Section IV, we present the convergence analysis of the distributed ADMM algorithm. Section V contains our concluding remarks.

Basic Notation and Notions:
A vector is viewed as a column vector, unless clearly stated otherwise. For a matrix A, we write A ij to denote the matrix entry in the i th row and j th column, and [A] i to denote the i th column of the matrix A, and [A] j to denote the j th row of the matrix A. For a vector x, x i denotes the i th component of the vector. We use x and A to denote the transpose of a vector x and a matrix A respectively. For a real-valued function f : X → R, where X is a subset of R n , the gradient vector of f at x in X are denoted by ∇f (x). We use standard Euclidean norm unless otherwise noted, i.e., for a vector x in R n , ||x|| = n i=1 x 2 i 1 2 .

II. FORMULATION
We consider a network, represented by an undirected connected simple graph with N nodes and M edges, G = {V, E}, where the set V denotes the set of nodes and the set E denotes the set of undirected edges. The nodes can be considered as agents in many applications, we will use the two terms interchangeably. We assume that nodes are ordered from 1 to N and use e ij to denote the edge between nodes i and j with i < j.
Each node is associated with a cost function f i : R → R, which is not necessarily differentiable. The nodes in the network are collectively solving the following unconstrained optimization problem We assume that each f i is locally known by agent i only. 2 We next consider a reformulation of problem (1) which will be used in the development of our distributed algorithm. In particular, we will introduce a separate decision variable x i for each of the nodes and impose the constraint x i = x j for all pairs (i, j) with e ij in set E, which guarantees that the node decision variables are equal, i.e., x i =x for all nodes i for somex. We write the transformed problem compactly by introducing the edge-node incidence matrix, which represents the network topology. The edge-node incidence matrix of network G, denoted by A, has dimension M × N . Each row of matrix A corresponds to an edge in the graph and each column represent an agent. The row corresponding to the edge e ij , which we denote by [A] eij , has 1 in the i th column, −1 in the j th column and 0 in the other columns, i.e., 3 For instance, the edge-node incidence matrix for the network in Figure 1 is given by The analysis in this paper can be extended to the case when the f i are multi-dimensional functions. To highlight the main ideas, we restrict attention to the case where the f i are one-dimensional here. 3 We adopt the convention that the smaller column has entry 1 and the larger one has −1. The analysis holds for other consistent way of writing the edge-node incidence matrix, for example, with −1 at i th column and 1 at j th column. With the edge-node incidence matrix, we can now rewrite problem (1) as The constraint Ax = 0 is a compact way of writing x i = x j for nodes i and j which are connected by an edge. For the rest of the paper, we will focus on solving problem (2). We denote the optimal value of problem (2) by F * . For notational convenience, we define the function F : We denote by L : R N × R M → R the Lagrangian function given by where λ in R M is the Lagrange multiplier vector associated with the constraint Ax = 0. We impose the following standard assumptions on the optimization problem.
Assumption 1: (Convexity) Each of the cost function f i : R → R is closed, proper and strictly convex.
for all x in R N and λ in R M . Assumption 1 implies that F (x) [cf. Eq. (3)] and therefore L(x, λ * ) is strictly convex in x. This assumption will be used in our convergence analysis. Assumption 2 implies that problem (2) has an optimal solution, which we denote by x * .
III. ALGORITHM In this section, we develop our distributed optimization algorithm, which is a primal dual algorithm motivated by the alternating direction method of multipliers (ADMM) (see [3] for a recent survey on ADMM). The standard ADMM algorithm involves decomposing the decision vector into subvectors, updating each subvector sequentially (using the most recent value for the rest of the subvectors) by minimizing an augmented Lagrangian function, and finally updating the Lagrange multiplier corresponding to the constraint that couples the subvectors using a dual subgradient method. The ADMM algorithm has typically been used for solving problems in which the decision variable is decomposed into two subvectors, which are coupled with a linear constraint. Hence, it can be viewed as solving a 2-agent special case of problem (2). Here we extend the formulation to N subvectors (each corresponding to an agent) and develop an ADMM that can be implemented in a distributed manner over the connected network in which the agents are situated. We first present the standard ADMM formulation and algorithm and then present our distributed ADMM algorithm.

A. Preliminaries: Standard ADMM Algorithm
The standard ADMM algorithm solves the following prob- We consider the augmented Lagrangian function given by where µ is the Lagrange multiplier corresponding to the constraint F y + Dz = c and ρ is a positive scalar. The ADMM algorithm updates the primal variables y and z and the Lagrange multiplier µ as follows: Starting from some initial vector (y 0 , x 0 , µ 0 ) 5 , at iteration k ≥ 0, the variables are updated as Note that stepsize used in updating the Lagrange multiplier vector is the same as the augmented Lagrangian function parameter ρ.
The ADMM algorithm has an equivalent representation, which we will use to develop our distributed ADMM algorithm. The equivalent representation is based on the following transformation. The last two terms in the augmented Lagrangian function [cf. Eq. (7)] satisfy µ (F y + Dz − c) + 4 This subsection follows closely the development in [3] 5 We use superscripts to denote the iteration number where we used the identity 2a b + ||b|| 2 = ||a + b|| 2 − ||a|| 2 replacing a = µ and b = F y+Dz−c. Therefore, by ignoring terms which are independent of the minimization variables, updates (8) and (9) can be expressed as We will now use updates (11), (12) and (10) to develop the distributed ADMM algorithm.

B. Distributed ADMM Algorithm
In the distributed ADMM algorithm, we associate a dual variable λ ij with the constraint x i = x j on edge e ij , and denote by λ the vector of dual variables, i.e., [λ ij ] ij,eij ∈E . Each agent i keeps a local decision estimate x i in R and a vector of dual variables λ ki with k < i. We say agent i owns the dual variable λ ki for k < i and agent i updates the dual variable.
To facilitate the development of our algorithm, we introduce the following notation. We partition the neighbors of a node i into two sets, which we call predecessors and successors of node i, denoted by P (i) and S(i). The set of the predecessors of i consists of neighbors whose index is smaller than i, i.e., P (i) = {j | e ji ∈ E, j < i}, and successors of i are the neighbors with index larger than i, i.e., S(i) = {j | e ij ∈ E, i < j}. Since the graph G is a simple graph, i.e., no edge of the type e ii , the set P (i)∪S(i) includes all neighbors of node i.
Following the development of ADMM described in the previous section, we use an augmented Lagrangian approach to solve problem (2) and use scalar β > 0 as the penalty parameter. We note that each row of the constraint Ax = 0 corresponds to x i −x j = 0 for some i < j with e ij in the set E and the distributed ADMM algorithm for solving problem (2) is given as follows: A Initialization: choose some arbitrary x 0 i in R for i = 1, . . . , N , which are not necessarily all equal. B For k ≥ 0, a Each agent i updates its estimate x k i in a sequential order with Fig. 2. Sample algorithm evolution.
b Each agent updates λ ji that he owns, for all j in P (i), Remarks: We assume that the nodes are ordered. In the above algorithm, at each iteration, the agents update in a sequential way, i.e., at iteration k agent i updates before agent j if i < j. In [20] we relax this assumption and the node update is determined randomly in a distributed manner.
We assume that as soon as the variables x k i and λ k ji are available to agent i, all of its neighbors can also access the data by local information exchange. The above algorithm is well defined, since the step B.a and B.b are implemented in a sequential way, the value of x k+1 j for j in P (i) and x k j for j in S(i) are available for agent i during its turn to update. The algorithm can be implemented in a distributed way, since the only communication (of scalar information x k j and λ k ji ) is with immediate neighbors at each step. This method is related to incremental methods, where each of the agents take turn to update the system wide decision variable and passes the updated variable to the network. The major difference here is that each agent has a local copy of the decision variable, which is not publicly accessible by all the other agents.
For illustration purposes, in Figure 2, we show a snapshot of the distributed ADMM algorithm applied to the network in Figure 1. In the figure, nodes 1 and 2 have completed the (k + 1) th updates, and node 3 (highlighted in yellow) is the next one to update. The predecessor of node 3, i.e.,

IV. CONVERGENCE ANALYSIS
In this section, we present our analysis of the convergence properties of the distributed ADMM algorithm presented in the last section and show that it has a O( 1 k ) rate of convergence, where we count the updates (13) and (14) for all i as one iteration. The analysis here is inspired by the work in [6] and [3], both of which analyzed the standard ADMM algorithm applicable to the special case of a 2node network. We will first introduce some notation for representational convenience, and derive three lemmas, all of which will then be used to establish the convergence properties of the algorithm.
We denote by B, a matrix B in R M × R N given by B = min{0, A}, where the maximization is taken element-wise. For example, the B matrix for the network given in Figure  1 has the following form, From the definition of matrix B, it follows that each row of matrix B corresponds to one edge (i, j) with i < j and consists of exactly one entry of −1 at position j. We denote by [B] eij the row of B corresponding to the edge e ij . Our analysis of the convergence relies on a key relation derived from the optimality of x k i at each iteration. This is established in the following lemma.
Lemma 4.1: Let {x k , λ k } be the iterates generated by our distributed ADMM algorithm for problem (2), with vector and vector λ k = [λ k ij ] ij,eij ∈E . Then the following relation holds for all k, for any x in R N , where matrix A is the edge-node incidence matrix of the network and matrix B = min{0, A}. Proof: We denote by g i : R → R the function and from update (13), we have x k+1 i is the optimizer of g k i +f i . The optimality implies there exists some subgradient The above two relations yield We then substitute ∇g k i using the definition of function g [cf. Eq. (16)] into the above relation and obtain, (14), By using the definition of the matrix A, we can rewrite the preceding inequality as We then sum the above relation over i = 1, . . . , N , and obtain By using the definition of matrices A and B, we can rewrite the terms compactly in matrix representation as − The preceding three relations can be combined to establish the desired relation.
We next relate the terms on the left hand side of relation (15) to a combination of vector norms. This is important since we can bound each of the norm term as nonnegative, which will then be used to establish convergence properties by forming a telescoping series.
Lemma 4.2: Let {x k , λ k } be the iterates generated by our distributed ADMM algorithm for problem (2), with vector and vector λ k = [λ k ij ] ij,eij ∈E . Let matrix A be the edge-node incidence matrix of the network and matrix B satisfy B = min{0, A}. Then the following relation holds for all k, (17) Proof: The proof relies on rewriting the terms on the left hand side of (17), using algebraic manipulation and techniques similar to the appendix of [3]. Most of the manipulation are based on two observations: λ k+1 = λ k −βAx k+1 and ||a + b|| 2 = ||a|| 2 + ||b|| 2 + 2a b for arbitrary vectors a and b. Due to space constraints, we omit the proof here, interested readers can find the full proof in [20]. We now present a simple lemma based on saddle point properties of the Lagrangian function.  , λ), where x is in R N and λ is in R M , the following relation holds The above relation holds for all λ and thus Ax * = 0.
With the three preceding lemmas, we can now establish the main result of the paper, i.e., the O( 1 k ) rate of convergence of the distributed ADMM algorithm. Theorem 4.4: Let {x k , λ k } be the iterates generated by our distributed ADMM algorithm for problem (2), with vector x k = [x k 1 , x k 2 , . . . , x k N ] and vector λ k = [λ k ij ] ij,eij ∈E . Let matrix A be the edge-node incidence matrix of the network and matrix B satisfy B = min{0, A}. Let y k = 1 k k−1 s=0 x s be the ergodic average of x k up to time t, then the following relation holds for all t, Proof: The first inequality follows immediately from definition of the saddle point of the Lagrangian function [cf. relation (5)].
We now prove the second inequality in Eq. (19). By setting x = x * in relation (15) from Lemma 4.1, we obtain for all iteration s, Due to feasibility of the optimal solution x * , we have Ax * = 0, and the above relation is equivalent to By adding and subtracting the term (λ * ) Ax s+1 from the right hand side of the preceding relation, we have where we used the identity a = a for a scalar a. We now use Lemma 4.2 to equivalently express the preceding inequality as, which holds true for all s. We sum the preceding inequality over s = 0, 1, . . . , k − 1 and after telescoping cancelation, we obtain Due to the convexity of function F , we have k−1 s=0 F (x s ) ≥ kF (y k ), and thus using the definition for y k , we have kF (x * ) − kF (y k ) + (λ * ) Ay k By multiplying both sides by −k, we have established the desired relation.
The above relation combined with the definition of the Lagrangian function [cf. Eq. (4)] and Eq. (18) yield the desired relation. Due to strict convexity of the function F [cf. Assumption 1] and linearity of the term λ * Ax, we have the function L(x, λ * ) is strictly convex in x. Therefore we conclude that the function L(x, λ * ) has a unique minimizer, i.e., x * in Assumption 2. Hence Theorem 4.4 guarantees that the value of the Lagrangian function obtained by the ergodic average sequence y k , i.e., L(y k , λ * ), converges to L(x * , λ * ) = F * at the rate of O( 1 k ). In practice, one might implement the algorithm with one additional variable y k i to keep the ergodic average of x k i to achieve the O( 1 k ) rate of convergence. 6 V. CONCLUSIONS In this paper, we develop a distributed ADMM algorithm for an N -agent network, where each agent takes turn to update its local variable. We show that the proposed algorithm achieves a rate of O( 1 k ) rate of convergence, which is the best known rate for dual methods based distributed algorithms. In ongoing work, we are extending this analysis to the algorithm when agents update asynchronously (in some randomized order) and for constrained optimization problems [20].