Accelerated Dual Averaging Methods for Decentralized Constrained Optimization

We consider the finite-sum optimization problem (1), in which $\mathcal{X}$ is a convex and compact set, and $f_{i}$ satisfies the following assumptions for all $i=1,\dots,n$:

A direct consequence of Assumption 1(iii) is

The above assumptions are standard in the study of decentralized algorithms for convex optimization problems. Throughout the paper, we denote by $x^{*}$ an optimal solution of Problem (1).

We consider solving Problem (1) in a decentralized fashion, that is, a pair of agents can exchange information only if they are connected in the communication network. To describe the network topology, an undirected graph $\mathcal{G}=\{\mathcal{V},\mathcal{E}\}$ is used, where $\mathcal{V}=\{1,\cdots,n\}$ denotes the set of $n$ agents and $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ represents the set of bidirectional channels, i.e., $(i,j)\in\mathcal{E}$ indicates that nodes $i$ and $j$ can send information to each other. Agent $j$ is said to be a neighbor of $i$ if there exists a link between them, and the set of $i$’s neighbors is denoted by $\mathcal{N}_{i}=\{j\in\mathcal{V}|(j,i)\in\mathcal{E}\}$. For every pair $(i,j)\in\mathcal{E}$, a positive weight $p_{ij}>0$ is assigned to $i$ and $j$ to weigh the information received from each other. Otherwise $p_{ij}=0$ is considered. For the convergence of the algorithm, we make the following assumption for $P:=[p_{ij}]\in[0,1]^{n\times n}$.

Assumption 2 implies that $\sigma_{2}(P)<1$ [28]. Given a connected network, the constant edge weights and the Metropolis-Hastings algorithm [36] can be used to construct a weight matrix $P$ fulfilling Assumption 2.

Our algorithms are based on the dual averaging methods [31]. Before introducing them, we state the following definition.

Let $d$ be a strongly convex and differentiable function with modulus $1$ on $\mathcal{X}$ such that

To meet the condition in (5) for any $x^{(0)}\in\mathcal{X}$, one can choose

where $\tilde{d}$ is any strongly convex function with modulus $1$, e.g., $\tilde{d}(x)=\lVert x\rVert^{2}/2$. The convex conjugate of $d$ is defined as

As a corollary of Danskin’s Theorem, we have the following result [35].

Dual averaging. The dual averaging method can be applied to solving Problem (1) in a centralized manner. Starting with $x^{(0)}$, it generates a sequence of variables $\{x^{(t)}\}_{t\geq 0}$ iteratively according to

where

and $\{a_{t}\}_{t\geq 0}$ is a sequence of positive parameters that determines the rate of convergence. Let $\tilde{x}^{(t)}=t^{-1}\sum_{\tau=0}^{t-1}{x}_{i}^{(\tau)}$. It is proved in [31] that $f(\tilde{x}^{(t)})-f(x^{*})\leq\mathcal{O}({1}/{\sqrt{t}})$ when $a_{t}=\Theta(1/\sqrt{t})$, that is, with order exactly $1/\sqrt{t}$. When the objective function is convex and smooth, a constant $a_{t}=a$ can be used to achieve an ergodic $\mathcal{O}({1}/{t})$ rate of convergence in terms of objective error [37].

Accelerated dual averaging. To speed up the rate of convergence, an accelerated dual averaging algorithm is developed in [35]. In particular, the variables are updated according to

where $a_{t}:=a(t+1)$ for some $a>0$, $A_{t}=\sum_{\tau=1}^{t}a_{\tau}$ and

Note that $t\geq 2$ is considered for the above iteration, and the variables are initialized with $u^{(1)}=w^{(0)}=x^{(0)}$, $v^{(1)}=w^{(1)}$. For convex and smooth objective functions, it is proved that $f(v^{(t)})-f(x^{*})\leq\mathcal{O}(1/t^{2})$ [35].

To solve Problem (1) in a decentralized manner, we propose a novel DDA algorithm. In particular, we employ the following dynamic average consensus protocol to estimate $z^{(t)}$ in (8):

where $z_{i}^{(t)}$ is a local estimate of $z^{(t)}$ generated by agent $i$, $s_{i}^{(t)}$ is a proxy of $\frac{1}{n}\sum_{i=1}^{n}\nabla f_{i}(x_{i}^{(t)})$ which aims to reduce the consensus error among variables $\{z_{i}^{(t)}:i=1,\cdots,n\}_{t\geq 0}$. Using it, each agent $i$ performs a local computation step to update its estimate of $x^{(t)}$:

The overall algorithm is summarized in Algorithm 1.

Before proceeding, we make the following remarks on Algorithm 1.

i) Subproblem solvability. Similar to centralized dual averaging methods, we assume the subproblem in (12) can be solved easily. For general problems, we can choose $d(x)=\lVert x-x^{(0)}\rVert^{2}/2$ such that the subproblem (12) reduces to computing the projection of variables onto $\mathcal{X}$. If $\mathcal{X}$ is simple enough, e.g., the simplex or $l_{1}$-norm ball, a closed-form solution exists.

ii) Comparison with existing DDA algorithms. In existing DDA algorithms [26, 29, 28], each agent estimates $z^{(t)}$ in the following way

For this scheme, it is proved that the consensus error among variables $\{z_{i}^{(t)}:i=1,\cdots,n\}_{t\geq 0}$ admits a constant upper bound [26], which necessitates the use of a monotonically decreasing sequence $\{a_{t}\}_{t\geq 0}$ for convergence. However, decreasing $a_{t}$ slows down the convergence significantly; the rate of convergence in [26, 29] is reported to be $\mathcal{O}(1/\sqrt{t})$. To speed up the convergence, we develop the consensus protocol in (11), which is inspired by the high-order consensus scheme in [6]. Thanks to it, we are able to prove that the deviation among variables $\{z_{i}^{(t)}:i=1,\cdots,n\}_{t\geq 0}$ asymptotically vanishes as time evolves. Therefore, the parameter in (12) can be set constant, i.e, $a_{t}=a>0$, which is key to obtaining the improved rates.

iii) Comparison with DGD algorithms. In existing DGD, a so-called gradient-tracking process similar to (11) is usually observed:

where $a$ represents the step size. The proposed scheme (11) differs from (14) in step (11a). With such a deliberate design and another local dual averaging step in (12), Algorithm 1 solves constrained problems with convergence rate guarantee. To compare DDA with existing algorithms applicable to solving Problem (1), we recall the PG-EXTRA algorithm [21]:

where $a$ represents the step size and $\tilde{p}_{ij}^{(t)}$ denotes the $(i,j)$-th entry of $\tilde{P}={(P+I)}/{2}$. Notably, PG-EXTRA seeks consensus among variables $\{{x}_{i}^{(t)}:i=1,\cdots,n\}$ at time $t+1$ that are obtained via a projection operator at time $t$. In contrast, DDA manages to agree on $\{{z}_{i}^{(t)}:i=1,\cdots,n\}$, which essentially decouples the consensus-seeking procedure from projection. After using the smoothness assumption in (3) to bound $\lVert\nabla f_{i}(x^{(t)}_{i})-\nabla f_{i}(x^{(t-1)}_{i})\rVert$ in (11b), the iteration in (11) can be kept almost linear, which greatly facilitates the rate analysis; see the proof of Lemma 5 for more details.

Next, we present the convergence result of Algorithm 1. Inspired by [26], we first establish the convergence property of an auxiliary sequence $\{{y}^{(t)}\}_{t\geq 0}$, which is instrumental in proving the convergence of $\{x_{i}^{(t)}:i=1,\cdots,n\}_{t\geq 0}$. In particular, the update of ${y}^{(t)}$ obeys

where the initial vector ${y}^{(0)}=x^{(0)}$ and $\overline{z}^{(t)}=\frac{1}{n}\sum_{i=1}^{n}z_{i}^{(t)}$. To proceed, we introduce the following $2\times 2$ matrix:

where $\beta=\sigma_{2}(P)$, and let $\rho({\bf M})$ be the spectral radius of ${\bf M}$.

To obtain a more explicit version of (18), we identify the eigenvalues of ${\bf M}$ as $\lambda_{1}=(\xi_{1}+\xi_{2})/2$ and $\lambda_{2}=(\xi_{1}-\xi_{2})/2$, where

Thus, we have $\lvert\lambda_{1}\rvert>\lvert\lambda_{2}\rvert$ and $\rho({\bf M})=\lambda_{1}>0$. By routine calculation, we can verify that $\rho({\bf M})$ and $\nu(a):=\frac{8}{9(1-(\rho({\bf M}))^{2})}$ monotonically increase with $a$. Due to

we have that as long as $a$ satisfies

then $a$ also satisfies (18). Based on (24), we have

whose size is comparable to the DGD algorithms [38, 8, 39] in the literature.

Next, we consider an unconstrained version of Problem (1), i.e., $\mathcal{X}=\mathbb{R}^{m}$, where the rate of convergence is stated for $f(\tilde{x}_{i}^{(t)})-f(x^{*})$.

To further speed up the convergence, we develop a decentralized variant of the accelerated dual averaging method in (9) and (10). Different from Algorithm 1, we consider building consensus among variables $\{v_{i}^{(t)},i=1,\cdots,n\}$ and propose the following iteration rule:

where

and

The overall algorithm is summarized in Algorithm 2. It is worth to mention that agents in Algorithm 2 consume the same communication resources as Algorithm 1 to achieve acceleration.

For Algorithm 2 and Theorem 2, the following remarks are in order.

i) Comparison with existing accelerated algorithms. Accelerated methods for decentralized constrained optimization are rarely reported in the literature. Recently, the authors in [22] developed the APM algorithm, where the iteration rule reads

where $\beta_{0}={L}/{\sqrt{1-\lambda_{2}(P)}}$ and $\theta_{k}$ is a decreasing parameter satisfying $\theta_{k}={\theta_{k-1}}/{(1+\theta_{k-1})}$ with $\theta_{0}=1$. Letting $\hat{s}_{i}^{(t)}=\theta_{k}s_{i}^{(t)}$, we can equivalently rewrite (33b) and (33c) as

from which we can see that new gradients are assigned with decreasing weights, whereas increasing weights are used for ADDA in (28). The reason for such different choices of parameters may be two-fold. First, parameter choices in (centralized) primal gradient descent and dual averaging methods are intrinsically different. Second, APM gradually increases the penalty parameter $1/\theta_{t}$ in order to enforce consensus, which essentially dilutes the weight for gradients, as shown above. We will show in simulation that decreasing weights over time slows down convergence. There are also a few other accelerated decentralized methods such as [9, 14], however they do not apply to constrained problems.

ii) Discussion about optimality. For ADDA, the rate of convergence is proved to be

In light of the lower bound in [14], it is not optimal in terms of the dependence on $\beta$. In particular, the dominant term of the error in $\mathcal{O}(1/(t(1-\beta)^{2}))$ becomes larger as $\beta$ grows, i.e., the network becomes more sparsely connected. This is mainly because we consider a one-consensus-one-gradient update in the algorithm. However, extending the algorithm in [14] to handle constraints may require further investigation. In the simulation section, we demonstrate the superiority of ADDA over existing decentralized constrained optimization algorithms.

In this setting, we use sparco7 [40, 17] to define the LASSO problem, and consider a cycle graph and a complete graph of $n=50$ nodes. The corresponding weight matrix $P$ is determined by following the Metropolis-Hastings rule [36]. Each local measurement matrix $M_{i}\in\mathbb{R}^{12\times 2560}$, and the local corrupted measurement $c_{i}\in\mathbb{R}^{12}$. The constraint parameter is set as $R=1.1\cdot\lVert x_{{g}}\rVert_{1}$, where $x_{{g}}$ with $\lVert x_{g}\rVert_{0}=20$ denotes the unknown variable to be recovered via solving LASSO. In this case, the simulation experiments were performed using MATLAB R2020b.

For comparison, the PG-EXTRA method in [21] and the APM method in [27] are simulated. For their algorithmic parameters, the step size for PG-EXTRA is set as $10^{-4}$, and the parameters for APM are set as $L=250$ and $\beta_{0}={L}/{\sqrt{1-\lambda_{2}(P)}}$. For DDA and ADDA in this work, we use $a=5\cdot 10^{-4}$ and $a_{t}=(t+1)\cdot 10^{-4}$, respectively, and $\lVert x\rVert^{2}/2$ as the prox-function. The projection onto an $l_{1}$ ball is carried out via the algorithm in [41]. All the methods are initialized with $x_{i}^{(0)}=0,\forall i\in\mathcal{V}$.

The performance of four algorithms are displayed in Figs. 1 and 2. In Fig. 1, the performance is evaluated in terms of the objective error $f(\frac{1}{n}\sum_{i=1}^{n}x_{i}^{(t)})-f(x^{*})$, where $x^{*}$ is identified using CVX [42]. It demonstrates that the DDA method outperforms other methods when the graph is a cycle. As the graph becomes denser, i.e, complete graph, the convergence of all algorithms becomes faster. Among them, the ADDA method demonstrates the most significant improvement. This is in line with Theorem 2, where the network connectivity impacts the convergence error in $\mathcal{O}(1/t)$ as opposed to $\mathcal{O}(1/t^{2})$. In Fig. 2, we compare the trajectories of consensus error, i.e., $\sqrt{\sum_{i=1}^{n}\lVert x_{i}^{(t)}-n^{-1}\sum_{j=1}^{n}x_{j}^{(t)}\rVert^{2}}$, by all methods. When the graph is a cycle, the APM and PG-EXTRA have smaller consensus error than the developed methods, mainly because they build consensus directly among variables $\{x_{i}^{(t)}:i=1,\cdots,n\}_{t\geq 0}$. When the graph is complete, the consensus error by the proposed DDA method vanishes because of the conservation property established in Lemma 3 and the complete graph structure.

For the synthetic dataset, the parameters are set as $n=8$, $m=30000$, $p_{i}=2000,\forall i\in\mathcal{V}$, and the data is generated in the following way. First, each local measurement matrix $M_{i}$ is randomly generated where each entry follows the normal distribution $\mathcal{N}(0,1)$. Next, each entry of the sparse vector $x_{{g}}$ to be recovered via LASSO is randomly generated from the normal distribution $\mathcal{N}(0,1)$ with $\lVert x_{{g}}\rVert_{0}=1500$. Then the corrupted measurement $c_{i}$ is produced based on

where $b_{i}$ represents the Gaussian noise with zero mean and variance $0.01$. The constraint parameter is set as $R=1.1\cdot\lVert x_{g}\rVert_{1}$. For this setting, we employed the message passing interface (MPI) in Python 3.7.3 to simulate a network of $8$ nodes, where each node $i$ is connected to a subset of nodes $\{1+i\,\mathrm{mod}\,8,1+(i+3)\,\mathrm{mod}\,8,1+(i+6)\,\mathrm{mod}\,8\}$. For comparison, the proposed methods are compared to their centralized counterparts. The parameters for dual averaging and accelerated dual averaging are set as $a=1/(3\cdot 10^{5})$ and $a_{t}=a(t+1)$, respectively. Similarly, the function $\lVert x\rVert^{2}/2$ is used as a prox-function, and the algorithms are initialized with $x_{i}^{(0)}=0,\forall i\in\mathcal{V}$.

The performance of the developed algorithms and their centralized counterparts is illustrated in Fig. 3. In particular, the performance is evaluated in terms of objective function value versus computing time. It demonstrates that the proposed methods outperform the corresponding centralized algorithms in the sense that the decentralized algorithms consume less computing time to reach the same degree of accuracy than their centralized counterparts.