On the Linear Convergence of the ADMM in Decentralized Consensus Optimization

I Introduction

Recent advances in signal processing and control of networked multi-agent systems have led to much research interests in decentralized optimization . Decentralized optimization problems arising in networked multi-agent systems include coordination of aircraft or vehicle networks , data processing of wireless sensor networks , spectrum sensing of cognitive radio networks , state estimation and operation optimization of smart grids , etc. In these scenarios, the data is collected and/or stored in a distributed manner; a fusion center is either disallowed or not economical. Consequently, any computing tasks must be accomplished in a decentralized and collaborative manner by the agents. This approach can be powerful and efficient, as the computing tasks are distributed over all the agents and information exchange occurs only between the agents with direct communication links. There is no risk of central computation overload or network congestion.

In this paper, we focus on decentralized consensus optimization, an important class of decentralized optimization in which a network of $L$ agents cooperatively solve

There exist several methods for decentralized consensus optimization, including distributed subgradient descent algorithms , dual averaging methods , and the alternating direction method of multipliers (ADMM) . Among these algorithms, the ADMM demonstrates fast convergence in many applications, e.g., . However, how fast it converges and what factors affect the rate are both unknown. This paper addresses these issues.

Firstly, we establish the linear convergence rate of the ADMM that is applied to decentralized consensus optimization with strongly convex local objective functions. This theoretical result gives a performance guarantee for the ADMM and validates the observation in prior literature.

Secondly, we study how the network topology, the properties of local objective functions, and the algorithm parameter affect the convergence rate. The analysis provide guidelines for networking strategies, objective-function splitting strategies, and algorithm parameter settings to achieve faster convergence.

I-B Related Work

Besides the ADMM, existing decentralized approaches for solving (1) include belief propagation , incremental optimization , subgradient descent , dual averaging , etc. Belief propagation and incremental optimization require one to predefine a tree or loop structure in the network, whereas the advantage of the ADMM, subgradient descent, and dual averaging is that they do not rely on any predefined structures. Subgradient descent and dual averaging work well for asynchronous networks but suffer from slow convergence. Indeed, for subgradient descent algorithms and establish the convergence rate of $O(1/k)$, where $k$ is the number of iterations, to a neighborhood of the optimal solution when the local subgradients are bounded and the stepsize is fixed. Further assuming that the local objective functions are strongly convex, choosing a dynamic stepsize leads to a rate of $O(\log(k)/k)$ . Dual averaging methods using dynamic stepsizes also have sublinear rates, e.g., $O(\log(k)/\sqrt{k})$ as proved in and .

The decentralized ADMM approaches use synchronous steps by all the agents but have much faster empirical convergence, as demonstrated in many applications . However, existing convergence rate analysis of the ADMM is restricted to the classic, centralized computation. The centralized ADMM has a sublinear convergence rate $O(1/k)$ for general convex optimization problems . In an ADMM with restricted stepsizes is proposed and proved to be linearly convergent for certain types of non-strongly convex objective functions. A recent paper shows a linear convergence rate $O(1/a^{k})$ for some $a>1$ under a strongly convex assumption, and our paper extends the analysis tools therein to the decentralized regime.

I-C Paper Organization and Notation

This paper is organized as follows. Section II reformulates the decentralized consensus optimization problem and develops an algorithm based on the ADMM. Section III analyzes the linear convergence rate of the ADMM and shows how to accelerate the convergence through tuning the algorithm parameter. Section IV provides extensive numerical experiments to validate the theoretical analysis in Section III. Section V concludes the paper.

II The ADMM for Decentralized Consensus Optimization

In this section, we first reformulate the decentralized consensus optimization problem (1) such that it can be solved by the ADMM (see Section II-A). Then we develop the decentralized ADMM approach and provide a simplified decentralized algorithm (see Section II-B).

Generally speaking, the ADMM applies to the convex optimization problem in the form of

where $y_{1}$ and $y_{2}$ are optimization variables, $g_{1}$ and $g_{2}$ are convex functions, and $C_{1}y_{1}+C_{2}y_{2}=b$ is a linear constraint of $y_{1}$ and $y_{2}$. The ADMM solves a sequence of subproblems involving $g_{1}$ and $g_{2}$ one at a time and iterates to converge as long as a saddle point exists.

To solve (1) with the ADMM in a decentralized manner, we reformulate it as

II-B Algorithm Development

Now we apply the ADMM to solve (4). The augmented Lagrangian of (4) is

where $\nabla f(x^{k+1})$ is the gradient of $f(x)$ at point $x=x^{k+1}$ if $f$ is differentiable, or is a subgradient if $f$ is non-differentiable.

Next we show that if the initial values of $z$ and $\lambda$ are properly chosen the ADMM updates in (5) can be simplified (see also the derivation in ). Multiplying the two sides of the $\lambda$-update by $A^{T}$ and adding it to the $x$-update, we have $\nabla f(x^{k+1})+A^{T}\lambda^{k+1}+cA^{T}B(z^{k}-z^{k+1})=0$. Further, multiplying the two sides of the $\lambda$-update by $B^{T}$ and adding it to the $z$-update we have $B^{T}\lambda^{k+1}=0$. Therefore (5) can be equivalently expressed as

To summarize, with initialization $\beta^{0}=-\gamma^{0}$ and $z^{0}=\frac{1}{2}M_{+}^{T}x^{0}$, (6) reduces to

In Section III we will analyze the convergence rate of the ADMM updates (7). The analysis requires an extra initialization condition that $\beta^{0}$ lies in the column space of $M_{-}^{T}$ (e.g., $\beta^{0}=0$) such that $\beta^{k+1}$ also lies in the column space of $M_{-}^{T}$; the reason will be given in Section III.

Indeed, (7) also leads to a simple decentralized algorithm that involves only an $x$-update and a new multiplier update. To see this, substituting $\frac{1}{2}M_{+}^{T}x^{k}-z^{k}=0$ into the first two equations of (7) we have

where $\mathcal{N}_{i}$ denotes the set of neighbors of agent $i$. The algorithm is fully decentralized since the updates of $x_{i}$ and $\alpha_{i}$ only rely on local and neighboring information. The decentralized consensus optimization algorithm based on the ADMM is outlined in Table I.

III Convergence Rate Analysis

This section first establishes the linear convergence rate of the ADMM in decentralized consensus optimization with strongly convex local objective functions (see Section III-A); the detailed proof of the main theoretical result is placed in Appendix. We then discuss how to tune the parameter and accelerate the convergence (see Section III-B).

Throughout this paper, we make the following assumption that the local objective functions are strongly convex and have Lipschitz continuous gradients; note that the latter implies differentiability.

Although the convergence of Algorithm 1 to the optimal solution of (4) can be shown based on the convergence property of the ADMM (see e.g., ), establishing its linear convergence is nontrivial. In the linear convergence of the centralized ADMM is proved given that either $g(z)$ is strongly convex or $B$ is full row-rank in (4). However, the decentralized consensus optimization problem does not satisfy these conditions. The function $g(z)=0$ is not strongly convex, and the matrix $B=[-I_{2EN};-I_{2EN}]$ is row-rank deficient.

Next we will analyze the convergence rate of the ADMM iteration (7). The analysis requires an extra initialization condition that $\beta^{0}$ lies in the column space of $M_{-}^{T}$ such that $\beta^{k+1}$ also lies in the column space of $M_{-}^{T}$, which is necessary in the analysis. Note that there is a unique optimal multiplier $\beta^{*}$ lying in the column space of $M_{-}^{T}$. To see so, consider the KKT conditions of (4)

Our main theoretical result considers the convergence of a vector that concatenating the primal variable $z$ and the dual variable $\beta$, which is common in the convergence rate analysis of the ADMM . Let us introduce

We will show that $u^{k}=[z^{k};\beta^{k}]$ is Q-linearly convergent to its optimal $u^{*}=[z^{*};\beta^{*}]$ with respect to the $G$-norm. Further, the Q-linear convergence of $u^{k}=[z^{k};\beta^{k}]$ to $u^{*}=[z^{*};\beta^{*}]$ implies that $x^{k}$ is R-linearly convergent to its optimal $x^{*}$.

Consider the ADMM iteration (7) that solves (4). The primal variables $x$ and $z$ have their unique optimal values $x^{*}$ and $z^{*}$, respectively; the dual variable $\beta$ has its unique optimal value $\beta^{*}$ that lies in the column space of $M_{-}^{T}$. Recall the definition of $u$ and $G$ defined in (12). If the local objective functions satisfy Assumption 1 and the dual variable $\beta$ is initialized such that $\beta^{0}$ lies in the column space of $M_{-}^{T}$, then for any $\mu>1$, $u^{k}=[z^{k};\beta^{k}]$ is Q-linearly convergent to its optimal $u^{*}=[z^{*};\beta^{*}]$ with respect to the $G$-norm

Further, $x^{k}$ is R-linearly convergent to $x^{*}$ following from

In Theorem 1, (14) shows that $\|u^{k+1}-u^{*}\|_{G}^{2}$ is no greater than $\frac{1}{1+\delta}\|u^{k}-u^{*}\|_{G}^{2}$ and hence $u^{k}$ converges to $u^{*}$ Q-linearly at a rate

A larger $\delta$ guarantees faster convergence. On the other hand, $\frac{1}{1+\delta}$ is a theoretical upper bound of the convergence rate, probably not tight. The Q-linear convergence of $u^{k}$ to $u^{*}$ translates to the R-linear convergence of $x$ to $x^{*}$ as shown in (15).

III-B Accelerating the Convergence

Now we consider tuning the free parameter $\mu$ and the algorithm parameter $c$ to maximize $\delta$ and thus accelerate the convergence (i.e., through minimizing $\frac{1}{1+\delta}$ that is indeed an upper bound). From the analysis we will see more clearly how the convergence rate is influenced by the network topology and the local objective functions. For convenience, we define the condition number of $f$ as

If the algorithm parameter $c$ in (14) is chosen as

maximizes the value of $\delta$ in (14) and ensures that (15) holds.

Observing the two values inside the minimization operator in (14), we find that only the second term is relevant with $c$. It is easy to check that the value of $c$ in (16), no matter how $\mu$ is chosen, maximizes $\delta$ as

Inside the minimization operator in (19), the first and second terms are monotonically increasing and decreasing with regard to $\mu>1$, respectively. To maximize $\delta$, we choose a value of $\mu$ such that the two terms are equal. Simple calculations show that the value of $\mu$ in (17), which is larger than 1, satisfies this condition. The resulting maximum value of $\delta$ is the one in (18).

IV Numerical Experiments

In this section, we provide extensive numerical experiments and supplement to validate our theoretical analysis. We introduce experimental settings in Section IV-A and then study the influence of different factors on the convergence rate in Sections IV-B through IV-E.

We generate a network consisting of $L$ agents and possessing at most $\frac{L(L-1)}{2}$ edges. If the network is randomly generated, we define $p$, the connectivity ratio of the network, as its actual number of edges divided by $\frac{L(L-1)}{2}$. Such a random network is generated with $\frac{L(L-1)}{2}p$ edges that are uniformly randomly chosen, while ensuring the network connected.

We apply the ADMM to a decentralized consensus least squares problem

The solution to (20) is denoted by $x^{*}$ in which the part of agent $i$ is denoted by $x_{i}^{*}$. The algorithm is stopped once $\|x^{k}-x^{*}\|_{2}$ reaches $10^{-15}$ or the number of iterations $k$ reaches $4000$, whichever is earlier.

In the numerical experiments, we choose to record the primal error $\|x^{k}-x^{*}\|_{2}$ instead of $\|u^{k}-u^{*}\|_{G}$ as the latter incurs significant extra computation when the number of agents $L$ is large. But note that $\|x^{k}-x^{*}\|_{2}$ is not necessarily monotonic in $k$. Let the transient convergence rate be $\rho_{k}=\frac{\|x^{k}-x^{*}\|_{2}}{\|x^{k-1}-x^{*}\|_{2}}$. As $\rho_{k}$ fluctuates, we report the running geometric-average rate of convergence $\bar{\rho}_{k}$ given by

which follows from (13) and (15). While $u^{0}$, $u^{*}$, $x^{0}$ $x^{*}$, and $m_{f}$ influence $\bar{\rho}_{k}$, observing

we see that their influence diminishes and the steady state $\bar{\rho}$ is upper bounded by $\sqrt{\frac{1}{1+\delta}}$ as $\rho$ is. Throughout the numerical experiments, we report $\bar{\rho}_{k}$ and $\bar{\rho}$.

IV-B Linear Convergence

As a comparison, we also demonstrate the convergence of the distributed gradient descent (DGD) method in Fig. 1 and Fig. 2. Using a diminishing stepsize $1/k^{1/3}$ , the DGD shows sublinear convergence that is slow even for a complete graph (i.e., $p=1$).

IV-C Algorithm Parameter

IV-D Condition Number of the Objective Function

IV-E Network Topology

IV-E2 Network Diameter

The network diameter $D$ is defined as the longest distance between any pair of agents in the network. In decentralized consensus optimization, $D$ is related to how many iterations the information from one agent will reach all the other agents.

To discuss the effect of the network diameter on the convergence rate, we randomly generated $4000$ connected networks with $L=200$ agents and connectivity ratios uniformly distributed on $[\frac{2}{L},1]$. We also generate the networks of the line, cycle, star, complete, and grid topologies. Most randomly generated networks possess small diameters. In this experiment, the numbers of those with $D=2$, $3\leq D\leq 4$ and $5\leq D\leq 198$ are $3141$, $717$ and $142$, respectively. From Fig. 9, we conclude that in general a larger diameter tends to cause a worse condition number of the network and thus slower convergence, though this relationship is interfered by network properties.

IV-E3 Geometric Average Degree

Define $d_{\min}$ and $d_{\max}$ as the largest and smallest degrees of the agents in the network, respectively. The geometric average degree $d_{s}=\sqrt{d_{\min}d_{\max}}$ reflects the agents’ number of neighbors in a geometric average sense. Its value reaches maximum at $L-1$ if the topology is complete; and reaches minimum $\sqrt{2}$ when the topology is a line.

Again, we randomly generated $4000$ connected networks with $L=200$ agents and connectivity ratios uniformly distributed on $[\frac{2}{L},1]$. We also generate the networks of the line, cycle, star, complete, and grid topologies. Out of the randomly generated networks, $417$ have $2\leq d_{s}\leq 20$, $1576$ have $21\leq d_{s}\leq 100$, and $1956$ have $101\leq d_{s}\leq 198$. From Fig. 10, we observe that a larger $d_{s}$ generally implies better connectedness and thus a smaller condition number of the network as well as faster convergence. This conclusion is similar to the one on the network diameter $D$ (see Fig. 9).

IV-E4 Imbalance of Bipartite Networks

Let $\mathcal{B}(\mathcal{L}_{A},\mathcal{L}_{B})$ denote the class of bipartite networks with $|\mathcal{L}_{A}|$ agents in one group and $|\mathcal{L}_{B}|$ agents in another group. Agents within either group cannot directly communicate with each other. For a bipartite network consisting of $L=|\mathcal{L}_{A}|+|\mathcal{L}_{B}|$ agents, its imbalance is defined as $L_{d}=|\mathcal{L}_{A}|-|\mathcal{L}_{B}|$, which can vary between and $L-2$.

V Conclusions

We apply the ADMM to a reformulation of a general decentralized consensus optimization problem. We show that if the objective function is strongly convex, the decentralized ADMM converges at a globally linear rate, which can be given explicitly. It is revealed that several factors affect the convergence rate that include the topology-related properties of the network, the condition number of the objective function, and the algorithm parameter. Numerical experiments corroborate and supplement our theoretical findings. Our analysis sheds light on how to construct a network and tune the algorithm parameter for fast convergence.

Consider the ADMM updates (7) and the KKT conditions (11). Subtracting the three equations in (11) from the corresponding equations in (7) yields

To prove the Q-linear convergence of $\|u^{k+1}-u^{*}\|_{G}^{2}$ we use $m_{f}\|x^{k+1}-x^{*}\|_{2}^{2}$ as an intermediate. Based on Assumption 1, $f(x)$ is strongly convex with a constant $m_{f}$ such that

Using (23), we can split the right-hand side of (26) to two terms

Substituting (24) and (25) to (27) we can eliminate the term $x^{k+1}-x^{*}$ and obtain

Recall the definition of $u$ and $G$ defined in (12). It is obvious that the right-hand side of (28) can be written as a compact form $2(u^{k}-u^{k+1})^{T}G(u^{k+1}-u^{*})$. Using the equality $2(u^{k}-u^{k+1})^{T}G(u^{k+1}-u^{*})=\|u^{k}-u^{*}\|_{G}^{2}-\|u^{k+1}-u^{*}\|_{G}^{2}-\|u^{k}-u^{k+1}\|_{G}^{2}$, (28) is equivalent to

Having (30) at hand, to prove (13) we only need to show

The idea of proof is to show that $\delta c\|z^{k+1}-z^{*}\|_{2}^{2}$ and $\frac{\delta}{c}\|\beta^{k+1}-\beta^{*}\|_{2}^{2}$ are upper bounded by two non-overlapping parts of the left-hand side of (32), respectively.

The upper bound of $\|z^{k+1}-z^{*}\|_{2}^{2}$ follows from (25) that shows $\frac{1}{2}M_{+}^{T}(x^{k+1}-x^{*})=z^{k+1}-z^{*}$. Hence we have

where $\sigma_{\max}(M_{+})$ is the largest singular value of $M_{+}$. To find the upper bound of $\|\beta^{k+1}-\beta^{*}\|_{2}^{2}$, we use two inequalities $\sigma_{\max}^{2}(M_{+})\|z^{k+1}-z^{k}\|_{2}^{2}\geq\|M_{+}^{T}(z^{k}-z^{k+1})\|_{2}^{2}$ and $M_{f}^{2}\|x^{k+1}-x^{*}\|_{2}^{2}\geq\|\nabla f(x^{k+1})-\nabla f(x^{*})\|_{2}^{2}$; the latter holds since $f(x)$ has Lipschitz continuous gradients with a constant $M_{f}$. Therefore, given the positive algorithm parameter $c$ and any $\mu>1$ it holds

Recall that from (23) $cM_{+}(z^{k}-z^{k+1})$ is the summation of $\nabla f(x^{k+1})-\nabla f(x^{*})$ and $M_{-}(\beta^{k+1}-\beta^{*})$. Hence we can apply the basic inequality $\|a+b\|_{2}^{2}+(\mu-1)\|a\|_{2}^{2}\geq(1-\frac{1}{\mu})\|b\|_{2}^{2}$, which holds for any $\mu>0$, to (34) and obtain

Combining (33) and (36), we prove (32). From (33) we have

and consequently (32), which proves (13).

To prove the R-linear convergence of $x^{k}$ to $x^{*}$, we observe that (30) implies $m_{f}\|x^{k+1}-x^{*}\|_{2}^{2}\leq\|u^{k}-u^{*}\|_{G}^{2}$, which proves (15).

References