Multi-consensus Decentralized Accelerated Gradient Descent

Introduction

In this paper, we consider the decentralized optimization problem, where the objective function is composed of $m$ local functions $f_{i}(x)$ that are located on $m$ different agents. The agents form a connected and undirected network and each of them only accesses its local function and communicates with its neighbors. All of the agents target to cooperatively solve the convex optimization problem

where $f(x)$ is $L$-smooth and $\mu$-strongly convex, $r(x)$ is convex but may be non-differentiable. Many machine learning models have the form (1) such as logistic regression and elastic net regression. Decentralized optimization has been widely studied and applied in many applications such as large-scale machine learning (Tsianos et al., 2012; Kairouz et al., 2021), automatic control (Bullo et al., 2009; Lopes and Sayed, 2008), wireless communication (Ribeiro, 2010), and sensor networks (Rabbat and Nowak, 2004; Khan et al., 2009).

Many decentralized optimization algorithms have been proposed. One class of them is primal-only methods, including decentralized gradient methods (Nedic and Ozdaglar, 2009; Yuan et al., 2016), decentralized accelerated gradient method (Jakovetić et al., 2014; Qu and Li, 2019) and EXTRA (Shi et al., 2015b; Li et al., 2019; Mokhtari and Ribeiro, 2016). They only access the gradients of $f_{i}(x)$ and are usually computationally efficient. Another class of algorithms are the dual-based decentralized algorithms, such as the dual subgradient ascent (Terelius et al., 2011), dual gradient ascent and its accelerated version (Scaman et al., 2017; Uribe et al., 2020), the primal-dual method (Lan et al., 2020; Scaman et al., 2018; Hong et al., 2017), and ADMM (Erseghe et al., 2011; Shi et al., 2014). However, dual-based algorithms commonly need more computation cost when the gradient of the dual function is not explicitly available.

This paper addresses the theoretical issues discussed above and designs two novel decentralized algorithms ProxMudag and Mudag. We summarize our contributions as follows:

Our algorithms have the optimal computation complexity $\mathcal{O}\left(\sqrt{\kappa_{g}}\log({1}/{\epsilon})\right)$ and the near optimal communication complexity \mathcal{O}\big{(}\sqrt{{\kappa_{g}}/{(1-\lambda_{2}(W))}}\log\big{(}{M\kappa_{g}}/{L}\big{)}\log({1}/{\epsilon})\big{)}, where $M$ and $L$ are the smoothness parameters of $f_{i}(x)$ and $f(x)$ respectively. To the best of our knowledge, this is the first (near) optimal decentralized algorithm that depends on the global condition number which provides an affirmative answer to the open problem whether there exists an algorithm that can achieve a communication complexity of $\mathcal{O}\left(\sqrt{{\kappa_{g}}/{(1-\lambda_{2}(W))}}\log({1}/{\epsilon})\right)$ or even close to it (Scaman et al., 2017).

Our algorithms do not require each individual function to be convex. Hence, they can be used in a wider range of applications than existing optimal decentralized algorithms. For example, the sub-problem of fast PCA by the shift-invert method is non-convex.

The proposed ProxMudag can achieve optimal computation and (near) optimal communication complexity when $r(x)$ is convex but non-differentiable. To the best of our knowledge, it obtains the best-known communication complexity for the decentralized strongly-convex optimization problems with the composite objective function.

Related Work

We first review the penalty-based algorithms. Nedic and Ozdaglar (2009) proposed the well-known decentralized gradient descent method, where each agent performs a consensus step and a gradient descent step with a fixed step-size related to the penalty parameter. Yuan et al. (2016) proved the convergence rate of decentralized gradient descent and showed how the penalty parameter affects the computation complexity. To avoid the diminishing step-size commonly required in penalty-based algorithms, Jakovetić et al. (2014) combined multi-consensus and Nesterov’s acceleration to achieve the optimal computation complexity for minimizing non-strongly convex functions. Berahas et al. (2018) proposed to use multi-consensus to achieve the balance between computation and communication complexity. Recently, Li et al. (2020b) proposed APM-C, which employed multi-consensus and increased the penalty parameter properly for each iteration. Combining Nesterov’s acceleration, APM-C can achieve a linear convergence rate and a low communication complexity. Li et al. (2020a) applied multi-consensus to network Newton method to achieve computation and communication efficiency.

Dual-based methods are another important research line. These methods introduce a Lagrangian function and work in the dual space. There are different ways to solve the reformulated problem such as gradient descent method (Terelius et al., 2011), accelerated gradient method (Scaman et al., 2017; Uribe et al., 2020), primal-dual method (Lan et al., 2020; Scaman et al., 2018) and ADMM (Shi et al., 2014; Erseghe et al., 2011). However, such methods are typically computationally inefficient. For example, using the accelerated gradient method to solve the dual counterpart of the decentralized optimization problem can achieve optimal communication complexity Scaman et al. (2017); Uribe et al. (2020), but its computation complexity will have an additional dependency on the eigenvalue gap of gossip matrix (Uribe et al., 2020).

The gradient-tracking method is a popular way to reduce the computational cost (Qu and Li, 2017; Xu et al., 2015; Qu and Li, 2019; Di Lorenzo and Scutari, 2016, 2015; Sun et al., 2022; Nedic et al., 2017; Zhu and Martínez, 2010). There are two different techniques for gradient-tracking. One of them is keeping a variable to estimate the average gradient and uses this estimation in the gradient descent step (Sun et al., 2022; Di Lorenzo and Scutari, 2016; Qu and Li, 2017). Another one is introducing two different weight matrices to track the difference of gradients (Shi et al., 2015b; Li et al., 2019). Recently, (Nedic et al., 2017; Li and Lin, 2020; Jakovetić, 2018; Xu et al., 2021) studied the connection between these two strategies and showed that they can be transformed to each other. Due to the tracking of history information, gradient-tracking based algorithms can achieve linear convergence rates for strongly convex objective functions (Qu and Li, 2017; Shi et al., 2015b; Nedic et al., 2017; Sun et al., 2022). However, the previously obtained convergence rates and communication complexities are much worse than the results in this paper.

For the case $r(x)$ is convex but non-differentiable, many gradient tracking based algorithms have been extended to decentralized composite optimization problems with a non-differentiable regularization term such as PG-EXTRA (Shi et al., 2015a) and NIDS (Li et al., 2019). However, due to the non-differentiable term, these algorithms can only achieve sub-linear convergence rates. Recently, Sun et al. (2022) proposed a gradient tracking based method called SONATA, and established a linear convergence rate with the assumption that $f(x)$ is strongly convex. In addition, Alghunaim et al. (2019) proposed a primal-dual algorithm which can achieve a linear convergence rate when each $f_{i}(x)$ is convex. Recently, Alghunaim et al. (2020); Xu et al. (2021) proposed a unified framework to analyze a large group of algorithms. They showed the algorithms including EXTRA (PG-EXTRA) (Shi et al., 2015b), NIDS (Li et al., 2019) and Harnessing (Qu and Li, 2017) can also achieve linear convergence rates with a non-differentiable regularization term. Despite intensive studies in the literature, the convergence rates of these previous algorithms do not match the optimal convergence rate. Moreover, the communication complexities achieved by algorithms analyzed in the framework of Xu et al. (2021) and Alghunaim et al. (2020) are sub-optimal. The conference version of our paper proposed DAPG which achieves the optimal computation complexity and near optimal communication complexity (Ye et al., 2020). However DAPG takes three multi-consensus steps while ProxMudag in this paper only takes two multi-consensus steps. Thus, ProxMudag can achieve better communication-efficiency than DAPG. We compare our ProxMudag with existing state-of-the-art decentralized algorithms for the composite optimization in Table 2.

Preliminaries

where $\mathbf{x}^{(i)}$ means the $i$-th row of matrix $\mathbf{x}$. Moreover, we use $\left\|\cdot\right\|$ to denote the Frobenius norm of vector or matrix and use $\left\langle x,y\right\rangle$ to denote the inner product of vectors $x$ and $y$.

Accordingly, we introduce the proximal operator and aggregated proximal operator with respect to $r(\cdot)$ and $R(\cdot)$ as

Using above notations, we define the (aggregated) generalized gradients as

Then we introduce the following definitions that will be used in the whole paper:

Based on the smoothness and strong convexity, we can define global and local condition numbers of the objective function as

For the topology of the network, we let $W$ be the weight matrix associated with the network, indicating how agents are connected to each other. We assume that the weight matrix $W$ has the following properties:

$W$ is symmetric with $W_{i,j}\neq 0$ if and if only agents $i$ and $j$ are connected or $i=j$;

${\mathbf{0}}\preceq W\preceq I$, $W{\mathbf{1}}={\mathbf{1}}$, ${\rm null}(I-W)={\rm span}(\mathbf{1})$;

Let $\mathbf{x}^{K}$ be the output of Algorithm 2 with $\eta_{w}=1/(1+\sqrt{1-\lambda_{2}^{2}(W)})$ and we denote $\bar{x}=\frac{1}{m}\mathbf{1}^{\top}\mathbf{x}^{0}$. Then it holds that

where $\lambda_{2}(W)$ is the second largest eigenvalue of $W$.

Multi-Consensus Decentralized Accelerated Gradient Descent

In this section, we propose two novel decentralized algorithms achieving the optimal computation complexity and near optimal communication complexity. These two algorithms are suitable for the case of $r(x)=0$ and the case of $r(x)$ is general convex respectively.

Our algorithms are based on the multi-consensus, gradient-tracking and Nesterov’s acceleration technique. We first introduce ProxMudag (Algorithm 3) for solving the problem with $r(x)\neq 0$. It has the following algorithmic procedure:

where $\eta$ is the step size and $K$ is the step number in multi-consensus. We can observe that Eqs. (10) and (11) belong to the algorithmic framework of accelerated proximal gradient descent since $\mathbf{s}_{t}$ can approximate the average gradient. In Eq. (12), we introduce $\mathbf{s}_{t}$ to track the gradient by using history information and the gradient difference. Thus, $\mathbf{s}_{t}$ can well approximate the average gradient $\mathbf{1}\bar{g}_{t}$ (defined in Eq. (3)). Furthermore, the variable $\mathbf{y}_{t}$ can also approximate $\mathbf{1}\bar{y}_{t}$ well by the “FastMix” operator. Since both $\bar{y}_{t}$ and $\bar{g}_{t}$ well approximate the averages, then we can obtain that $\bar{g}_{t}\approx\nabla f(\bar{y}_{t})$. Thus, the convergence properties of our algorithm are similar to the centralized accelerated proximal gradient descent, which is the main idea behind our approach to the decentralized optimization. In other words, we combine multi-consensus with gradient-tracking to approximate the centralized accelerated proximal gradient descent. As we will show, this seemingly simple idea leads to establishing a near optimal algorithm for the decentralized optimization. Note that Algorithm 3 only takes two multi-consensus steps at each iteration. In contrast, the algorithm in conference version (Ye et al., 2020, Algorithm 1) of this paper requires three multi-consensus steps at each round. Though reducing one multi-consensus step will not improve the order of communication complexity, it requires much less communication cost and benefits in real applications.

In the case of $r(x)=0$, we propose Mudag (Algorithm 1) that only needs one multi-consensus step for each iteration. The Mudag has the following algorithmic procedure:

To understand Mudag from perspective of gradient tracking, we can reformulate the above procedure in a form similar to Eqs. (10) to (12) as follows (The reformulation is proved in Lemma 23)

Note that Eq. (16) is an explicit gradient tracking step similar to Eq. (12). Comparing Eqs. (14)-(16) with Eqs. (10)-(12), we can observe that these two algorithms share a similar procedure since they share the same intuition. However, the iteration of ProxMudag cannot be improved to one multi-consensus step like Mudag. If we directly replace Eq. (13) by

it is easy to check that the algorithm cannot converge to the optimum.

Because Mudag only has one multi-consensus step for each iteration while ProxMudag takes two multi-consensus steps, in practice, Mudag commonly requires much less communication cost than ProxMudag when Mudag is applicable. Thus, the Mudag is a better choice than ProxMudag in the case of $r(x)=0$.

2 Main Results

In this work, we focus on the synchronized setting in which the computation complexity depends on the number of gradient calls and the communication complexity depends on the rounds of local communication. We give the detailed upper complexity bounds for our algorithms in the following theorems.

Let $f(x)$ be $L$-smooth and $\mu$-strongly convex. Assume each $f_{i}(x)$ is $M$-smooth. We set $\eta={1}/{L}$ and $\alpha=\sqrt{\mu\eta}$ in Algorithm 1. Letting $K$ in Algorithm 1 satisfy that

then the sequence $\{\bar{x}_{t}\}$ satisfies that

where $x^{*}$ is the global minimum of $f(x)$. To achieve $\mathbf{x}_{T}$ such that $\left\|\mathbf{x}_{T}-\mathbf{1}x^{*}\right\|^{2}=\mathcal{O}(m\epsilon/\mu)$ and $f(\bar{x}_{T})-f(x^{*})\leq\epsilon$, the computation and communication complexities of Algorithm 1 are at most

Let $f(x)$ be $L$-smooth and $\mu$-strongly convex. Assume each $f_{i}(x)$ is $M$-smooth. We set $\eta={1}/{(2L)}$ and $\alpha=\sqrt{\mu\eta}$ in Algorithm 3. Letting $K$ in Algorithm 3 satisfy that

then sequence $\{\bar{x}_{t}\}$ generated by Algorithm 3 satisfies that

where $x^{*}$ is the global minimum of $h(x)$. To achieve $\mathbf{x}_{T}$ such that $\left\|\mathbf{x}_{T}-\mathbf{1}x^{*}\right\|^{2}=\mathcal{O}(m\epsilon/\mu)$ and $h(\bar{x}_{T})-h(x^{*})\leq\epsilon$, the computation and communication complexities of Algorithm 1 are at most

Theorem 2 shows that Mudag achieves the same order of computation complexity as that of the centralized Nesterov’s accelerated gradient descent. At the same time, the communication complexity nearly matches the known lower bound of decentralized optimization problem up to a factor of $\log\left({M\kappa_{g}}/{L}\right)$. We conjecture that it may be possible to remove the $\log(\kappa_{g})$ factor, because the term only comes from the inequality $\left\|\bar{y}_{t}-x^{*}\right\|\leq\sqrt{2V_{t}/{\mu}}$, where $V_{t}$ is defined in Eq. (17) in the proof, which may be loose.

Theorem 2 and 3 only assume that $f(x)$ is $\mu$-strongly convex and $L$-smooth, and $f_{i}(x)$ is $M$-smooth (note that unlike many previous works, our dependency on $M$ is logarithmic only). Thus, our algorithms can be used when $f_{i}(x)$ is possibly non-convex. This kind of problem has been widely studied in recent years (Allen-Zhu, 2018; Garber et al., 2016) and one important example is the fast PCA by shift-invert method (Garber et al., 2016). In contrast, the previous works (Scaman et al., 2017; Li et al., 2020b, 2019; Qu and Li, 2019; Kovalev et al., 2020; Li and Lin, 2021) require the (strong) convexity of $f_{i}(x)$ to obtain the linear convergence rate.

Observe that the step 3 of Algorithm 1 resorts to multi-consensus and gradient tracking to encourage $\mathbf{x}(i,:)$ on different agents to be close to each other. Similarly, for the centralized distributed optimization problem, the consensus step is also needed, which is often implemented by two rounds of communications between agents and the central server. In this view, the centralized optimization methods and the decentralized one only differ in the way to achieve consensus. We can also regard the decentralized optimization methods as an approximation to the decentralized one.

Convergence Analysis

In this section, we give a detailed characterization on how our decentralized algorithms approximate accelerated (proximal) gradient descent. Since Mudag and ProxMudag have similar ideas for convergence analysis, we only present how to obtain the convergence rate of ProxMudag in this section and leave the analysis of Mudag in Appendix C. Note that the analysis of ProxMudag may be more sophisticated than the one of Mudag because of the additional step of proximal operation.

We first introduce the Lyapunov function as follows

In the rest of this section, we will show how the Lyapunov function $V_{t}$ converges and how multi-consensus and gradient-tracking help us to approximate centralized accelerated proximal gradient descent.

Then we show that $\bar{x}_{t}$, $\bar{y}_{t}$, $\bar{g}_{t}$ (defined in Eq. (3) and generated by Algorithm 3) and $\bar{v}_{t}$ (defined in Eq. (18)) can be fit into the framework of the centralized accelerated proximal gradient descent.

Let $\bar{x}_{t}$, $\bar{y}_{t}$, $\bar{g}_{t}$ and $\bar{G}_{t}$ (defined in Eqs. (3) and (6)) be generated by Algorithm 3. By setting $\bar{s}_{t}=\frac{1}{m}\mathbf{1}^{\top}\mathbf{s}_{t}$ with $\mathbf{s}_{t}$ defined in Eq. (12), it satisfies:

We first the last equality by induction. For $t=0$, we use the fact that $\mathbf{s}_{0}=\nabla F(\mathbf{y}_{0})$. Then, it holds that $\bar{s}_{0}=\bar{g}_{0}$. We assume that $\bar{s}_{t}=\bar{g}_{t}$ at time $t$. By the update equation (12) and Proposition 1, we have

Thus, we obtain the result at time $t+1$.

Lemma 8 shows that the averaged version of Eqs. (10)-(12) is almost the same as accelerated proximal gradient descent (Nesterov, 2018). Thus, if $\bar{s}_{t}$ is an accurate estimation of $\nabla f(\bar{y}_{t})$, then Algorithm 3 has convergence properties similar to accelerated proximal gradient descent. Next, we are going to show $\mathbf{y}_{t}(i,:)\approx\bar{y}_{t}$ and $\mathbf{s}_{t}(i,:)\approx\bar{s}_{t}$ by the following lemma.

Let $\mathbf{z}_{t}=[\left\|\mathbf{x}_{t}-\mathbf{1}\bar{x}_{t}\right\|,\left\|\mathbf{y}_{t}-\mathbf{1}\bar{y}_{t}\right\|,\eta\left\|\mathbf{s}_{t}-\mathbf{1}\bar{s}_{t}\right\|]^{\top}$ with $\mathbf{x}_{t}$, $\mathbf{y}_{t}$ and $\mathbf{s}_{t}$ generated by Algorithm 3, then it holds that

where $\rho$ and $\mathbf{A}$ are defined as

If the spectral radius of $\mathbf{A}$ is less than $1$ and $V_{t}$ converges to zero, then $\left\|\mathbf{z}_{t}\right\|$ will converge to zero. Note that $\left\|\mathbf{x}_{t}-\mathbf{1}\bar{x}_{t}\right\|$, $\left\|\mathbf{y}_{t}-\mathbf{1}\bar{y}_{t}\right\|$ and $\eta\left\|\mathbf{s}_{t}-\mathbf{1}\bar{s}_{t}\right\|$ are no larger than $\left\|\mathbf{z}_{t}\right\|$. Hence, Algorithm 3 can well approximate centralized accelerated proximal gradient descent in such conditions.

Next, we prove above two conditions that lead to the convergence of $\left\|\mathbf{z}_{t}\right\|$. First, the following lemma shows the spectral radius of $\mathbf{A}$ is less than $\frac{1}{2}$ if $\rho$ is small enough.

Matrix ${\mathbf{A}}$ defined in Eq. (23) satisfies that

with $\lambda_{i}(\mathbf{A})$ being the $i$-th largest eigenvalue of $\mathbf{A}$. Letting $\eta=1/(2L)$ and $\rho\leq{L^{3}}/{(1280M^{3})}$, then it holds that

and the eigenvector $\mathbf{v}$ associated with $\lambda_{1}(\mathbf{A})$ is positive and its entries satisfy

where $\mathbf{v}(i)$ is $i$-th entry of $\mathbf{v}$.

Now, we are going to show $V_{t}$ converges linearly but with some perturbation terms related to $\mathbf{z}_{t}$.

Letting $\mathbf{x}_{t},\mathbf{y}_{t},\mathbf{s}_{t}$ be generated by Algorithm 3, it holds that

The above lemma shows that the Algorithm 3 has a convergence property similar to the accelerated proximal gradient descent but with some perturbation terms. Next, using above lemmas and choosing proper $\rho$ by a proper $K$, we will obtain the convergence rate of Algorithm 3.

Finally, we provide the proof of our main result Theorem 3.

Proof It is easy to check that $\rho$ satisfies the conditions required in Lemma 10. Let the eigenvector $\mathbf{v}$ defined in Lemma 10 and set $\mathbf{v}(3)=1$. Combining with the fact that the first two entries of $\mathbf{z}_{0}$ are zero, we can obtain that,

where the first equality is because $\mathbf{v}$ is the eigenvector associated with $\lambda_{1}(\mathbf{A})$ and the last inequality is because of $\lambda_{1}(\mathbf{A})\leq\frac{1}{2}$ obtained in Lemma 10.

Next, we will prove our result by induction. For $t=0$, we have $\left\|\mathbf{y}_{0}-\mathbf{1}\bar{y}_{0}\right\|=0$ and

Next, we assume that for $i=1,\dots,t$, it holds that

Combining with Eq. (26), we can obtain that

Thus, using the definition of $\mathbf{z}$ and $\mathbf{A}$, we can obtain that

where the second inequality is because of the induction assumption and the last inequality is due to \rho\leq{L^{6}}/\big{(}5.5\cdot 10^{8}\cdot\kappa_{g}^{3/2}M^{6}\big{)}. Furthermore, it holds that

Experiments

We evaluate the performance of our algorithms on (sparse) logistic regression with different settings, including the situation in which each $f_{i}(x)$ is strongly convex and the local function $f_{i}(x)$ may be non-convex.

In our experiments, we consider random networks where each pair of agents have a connection with a probability of $p$. We set $W=I-{\mathbf{L}}/{\lambda_{1}(\mathbf{L})}$, where $\mathbf{L}$ is the Laplacian matrix associated with a weighted graph, and $\lambda_{1}(\mathbf{L})$ is the largest eigenvalue of $\mathbf{L}$. We also set $m=100$, that is, there exist $100$ agents in this network. In our experiments, we run the algorithms on the settings of $p=0.1$ and $p=0.5$, which correspond to $1-\lambda_{2}(W)=0.05$ and $1-\lambda_{2}(W)=0.81$ respectively.

We set $\sigma_{1}=\dots=\sigma_{m}=10^{-3}$, then each $f_{i}(x)$ is strongly-convex.

We set $\sigma_{1}=\dots=\sigma_{m}=10^{-4}$, then each $f_{i}(x)$ is strongly-convex.

We set $\sigma_{1}=\dots=\sigma_{m-1}=-10^{-1}$ and $\sigma_{m}=10$, then functions $f_{i}(x)$ for $i<m$ are non-convex but $f(x)$ is still strongly-convex.

We set $\sigma_{1}=\dots=\sigma_{m-1}=-10^{-2}$ and $\sigma_{m}=1$, then functions $f_{i}(x)$ for $i<m$ are non-convex but $f(x)$ is still strongly-convex.

We compare our algorithm (Mudag) to centralized accelerated gradient descent (AGD) in (Nesterov, 2018), EXTRA in (Shi et al., 2015b), NIDS in (Li et al., 2019), Acc-DNGD in (Qu and Li, 2019) and APM-C in (Li et al., 2020b). In this paper, we do not compare our algorithm to the dual-based algorithms such as accelerated dual ascent algorithm (Uribe et al., 2020; Scaman et al., 2017) because these algorithms cannot be applied to the case where some functions $f_{i}(x)$ are non-convex. The step sizes of all algorithms are well-tuned to achieve their best performances. Furthermore, we set the momentum coefficient as {\big{(}\sqrt{L}-\sqrt{\mu}\big{)}}/{\big{(}\sqrt{L}+\sqrt{\mu}\,\big{)}} for Mudag, AGD and APM-C. We initialize $\mathbf{x}_{0}$ at $\mathbf{0}$ for all the compared methods.

In the setting in which each $f_{i}(x)$ is strongly convex, we report the experimental results in Figure 1. Compared with AGD, our algorithm has almost the same computation cost, which validates our theoretical analysis. Assuming that AGD communicates once per iteration, we can also see that the communication cost of Mudag is almost the same communication cost as that of AGD when $1-\lambda_{2}(W)=0.81$, and six times of that of AGD when $1-\lambda_{2}(W)=0.05$. This matches the theoretical results of communication complexity for our algorithm. Furthermore, our algorithm achieves both lower computation cost and lower communication cost than other decentralized algorithms on all settings. The advantages are more obvious for small $\sigma_{i}$, which also validates the comparison of the upper bounds with related works.

In the setting in which an individual function $f_{i}(x)$ could be non-convex, we report the experimental results in Figure 2. Note that the global objective function of experiments reported in Figure 1 and Figure 2 are the same but the model that corresponds to Figure 2 contains some non-convex $f_{i}(x)$. Comparing the curves in these two figures, we can observe that the computation cost of AGD and our algorithm are not affected by the non-convexity of $f_{i}(x)$ because their convergence rates only depend on $\sqrt{\kappa_{g}}$. On the other hand, the communication cost of our algorithm increases slightly compared to the setting where each $f_{i}(x)$ is convex. This is because the ratio $M/L$ of $f_{i}(x)$ increases when we set $\sigma_{i}=-10^{-1}$ or $\sigma_{i}=-10^{-2}$ for agent $i=1,\dots,m-1$. Our communication complexity theory shows $M/L$ will affect the communication cost by a $\log(M/L)$ factor. Compared with our algorithm, the performance of the other decentralized algorithms deteriorates greatly, which can be clearly observed by comparing the two figures in the top right corners of Figure 1 and Figure 2.

3 Experiments on Sparse Logistic Regression

We consider the sparse logistic regression model whose objective function is defined as

where $f_{i}(x)$ is defined in Eq. (31). We conduct experiments on the graph with $1-\lambda_{2}(W)=0.05$ and $f_{i}(x)$ and only consider the case when each $f_{i}(x)$ is convex, since experiments on logistic regression have already shown the advantage of our ideas for non-convex $f_{i}(x)$. We conduct experiments on the datasets ‘a9a’ and ‘w8a’, which can be downloaded from Libsvm datasets. For ‘w8a’, we set $n=497$ and $d=300$. For ‘a9a’, we set $n=325$ and $d=123$. We conduct the following two experimental settings:

We set $\gamma=10^{-4}$ and $\sigma_{1}=\dots=\sigma_{m}=10^{-3}$.

We set $\gamma=10^{-4}$ and $\sigma_{1}=\dots=\sigma_{m}=10^{-4}$.

Conclusion

In this paper, we proposed two novel decentralized algorithms, which achieve the optimal computation complexity and the near optimal communication complexity. To the best of our knowledge, this is the best communication complexity that primal-based decentralized algorithms can achieve especially for the decentralized composite optimization problems.

Our results provide an affirmative answer to the open problem whether there is a decentralized algorithm that can achieve the communication complexity \mathcal{O}\big{(}\sqrt{{\kappa_{g}}/{(1-\lambda_{2}(W))}}\log({1}/{\epsilon})\big{)} or even close to this lower bound for a strongly convex objective function. Furthermore, our algorithm does not require each individual functions $f_{i}(x)$ to be convex. Our experiments showed that the non-convexity of individual function $f_{i}(x)$ rarely degrades the performance of our algorithm. Our analysis also implies that integrating multi-consensus and gradient tracking can well approximate the decentralized optimization algorithm to the corresponding centralized counterpart. The implementation of the resulting algorithms are simple, effective and with (near) optimal complexities. This novel perspective may also provide useful insights for developing new decentralized optimization algorithms in other settings.

Acknowledgments

The authors would like to thank Lesi Chen and Yuxing Liu’s helpful discussion. Haishan Ye is supported by National Natural Science Foundation of China under Grant No. 12101491. Luo Luo is supported by National Natural Science Foundation of China (No. 62206058) and Shanghai Sailing Program (22YF1402900).

A Useful Lemmas

Proof The first inequality is because each $f_{i}(x)$ is $M$-smooth and

Then we can prove Eq. (35) using $L$-smoothness of $f(x)$ and the non-expansiveness of the proximal operator

where the last inequality is due to the $L$-smoothness of $f(x)$.

For $\bar{x}_{t}$, $\bar{y}_{t}$ and $\bar{v}_{t}$ defined in Eqs. (3) and (18), then we can obtain that

Proof First using the definition of $\bar{v}_{t}$, we have

Now, we are going to prove Eq. (38) with the case $r(x)$ is convex since $r(x)=0$ is a special case of $r(x)$ being convex. Then we have

Let $f(x)$ be $\mu$-strongly convex. For $\bar{y}_{t}$, and $V_{t}$ defined in Eqs. (3) and (17) and $x^{*}$ being the optimum, we have the following inequality,

Proof Since $f(x)$ is $\mu$-strongly convex, $h(x)$ in Eq. (1) is also $\mu$-strongly convex. Thus, we obtain

At the end of this section, we provide the proof of Proposition 1.

then the iteration of Algorithm 2 can be written as

The property $W\mathbf{1}=\mathbf{1}$ directly leads to $\bar{x}=\frac{1}{m}\mathbf{1}^{\top}\mathbf{x}^{K}$. It also indicates

where we use the equality (40). This implies for any $K\geq 2$, we have

Combining above result with Lemma 9 of Song et al. (2023), we have

B Proof of Lemmas in Section 5

We list several important lemmas that will be used in our proofs.

Letting ${\rm{\bf prox}}_{\eta m,R}^{(i)}(\mathbf{x})$ denote the $i$-th row of the matrix ${\rm{\bf prox}}_{\eta m,R}(\mathbf{x})$ (defined in Eqn. (4)), we have the following equation

which implies that $G_{t}^{(i)}$ equals to the $i$-th row of $G_{t}$ defined in Eq. (5).

Proof By the definition of the proximal operators, we have

Therefore, we have the following equation

Proof Using Lemma 17 and non-expansiveness of the proximal mapping, we have

Letting $\mathbf{s}_{t}^{(i)}$ be the $i$-th row of $\mathbf{s}_{t}$ and $G_{t}^{(i)},\;\bar{G}_{t}$ (defined in Eqs. (5), (6)) generated by Algorithm 3, we have

Proof Using the inequality that $(a+b)^{2}\leq 2a^{2}+2b^{2}$, we have

where the third inequality is from Eq. (34) and the $L$-smoothness of $f(x)$, the last inequality is due to $L\leq M$.

where the third and forth inequalities are due to the non-expansiveness of proximal mapping.

where the second inequality is due to the non-expansiveness of proximal operator, and the last inequality is from Eq. (34).

B.2 Proof of Lemma 9

where the third inequality is because of Lemma 18 and the non-expansiveness of proximal operator.

Using the definition of $\mathbf{y}_{t+1}$ in Algorithm 1 and the property of “FastMix” operation, we have

Now we are going to bound the value of $\left\|\mathbf{s}_{t+1}-\mathbf{1}\bar{s}_{t+1}\right\|$. We have

where the last inequality is because of $\rho\leq 1$. Then we only need to consider the term $\left\|\mathbf{1}\bar{y}_{t+1}-\mathbf{1}\bar{y}_{t}\right\|$. Using the iteration of average variables illustrated in Eq. (20), we have

where the last equality is because of $\eta={1}/{(2L)}$. Thus, we can obtain that

Combining above results, we can bound the value of $\eta\left\|\mathbf{s}_{t+1}-\mathbf{1}\bar{s}_{t+1}\right\|$ as follows

where the last inequality is because of $\eta={1}/{(2L)}$ and $1\leq{M}/{L}$.

Combining Eqs. (47), (48) and (49), we can obtain

B.3 Proof of Lemma 10

Proof It is easy to check that $\mathbf{A}$ is non-negative and irreducible. Furthermore, every diagonal entry of $\mathbf{A}$ is not zero. Thus, by Perron-Frobenius theorem and Corollary 8.4.7 of Horn and Johnson (2012), $\mathbf{A}$ has a real-valued positive number $\lambda_{1}(\mathbf{A})$ which is algebraically simple and associated with a strictly positive eigenvector $\mathbf{v}$. It also holds that $\lambda_{1}(\mathbf{A})$ is strictly larger than $|\lambda_{i}(\mathbf{A})|$ with $i=2,3$.

We write down the characteristic polynomial $p(\zeta)$ of ${\mathbf{A}}$, that is

It is easy to check that $\Delta>0$. Thus, two roots of $p_{0}(\zeta)$ are

Note that $p(\zeta)$ is monotonely increasing in the range $\left[\zeta^{*},\infty\right]$. Thus, $p(\zeta)$ does not have real roots in this range. This implies $\lambda_{1}(\mathbf{A})\leq\zeta^{*}$. By Eq. (50), we can obtain that if $\rho$ satisfies the condition that

then it holds that $\Delta\leq\frac{1}{4}$. If $\rho$ also satisfies the condition that

It is easy to check that if $\rho\leq{L^{3}}/{(1280M^{3})}$, inequalities (51) and (52) hold.

Now, we begin to prove that $\sqrt{\rho}<\lambda_{1}(\mathbf{A})$. We can conclude this result once it holds $p(\sqrt{\rho})<0$. This is because $p(\zeta)$ will have a root between $\sqrt{\rho}$ and $1/2$ and $\lambda_{1}(\mathbf{A})$ must be no less than this root. We have

where the first inequality is because of $M/L\geq 1$.

Since $\mathbf{v}$ is the eigenvector associated with $\lambda_{1}(\mathbf{A})$, we can obtain that $\mathbf{A}\mathbf{v}=\lambda_{1}(\mathbf{A})\mathbf{v}$ and have the following equations

By Eqs. (53) and (54), we can obtain that

Replacing above equation to Eq. (55), we can obtain that

where the second inequality is because of $\rho\leq 1/2$. Combining Eq. (53), we can obtain that

where the last inequality is because of $\lambda_{1}(\mathbf{A})\geq\sqrt{\rho}$.

B.4 Proof of Lemma 11

Before proving Lemma 11, we first give several important lemmas which are closely related to the convergence rate of Algorithm 3.

Letting $\mathbf{x}_{t},\mathbf{y}_{t},\mathbf{s}_{t}$ be generated by Algorithm 3, it holds that

Proof By $\mu$-strong convexity , $L$-smoothness of $f(x)$ and the property of proximal operator, we have

Similarly, multiplying $\alpha$ on both sides of Eq. (57) and setting $z=x^{*}$, we obtain that

Note that by Jensen’s inequality, we can get that

Then averaging Eq. (58) from $i=1$ to $m$ and using the convexity of $h(x)$, we have

where the first inequality is because of Cauchy’s inequality and the second inequality is because of $2ab\leq\eta a^{2}+b^{2}/\eta$.

Combining above two inequalities, we can obtain that

Combining Eqs. (60), (61) and (62), we can obtain that

where the last inequality is because of Jensen’s inequality.

Letting $\mathbf{x}_{t},\mathbf{y}_{t},\mathbf{s}_{t}$ be generated by Algorithm 3, it holds that

Furthermore, by Eq. (36), we have $\bar{v}_{t}=\bar{y}_{t}+\frac{1}{\alpha}(\bar{y}_{t}-\bar{x}_{t})$ which implies that

Combining above two lemmas, we can obtain the following result.

Proof [Proof of Lemma 11] Using the definition of $V_{t}$, we have

where the last inequality is because of $\eta={1}/{(2L)}$.

C Convergence Analysis of Algorithm 1

The proof of Algorithm 1 is almost the same to the one of Algorithm 3. But, without the proximal mapping which will cause extra consensus error terms, the detailed convergence analysis of Algorithm 1 is clean and easy to follow.

The update procedure of Algorithm 1 can be represented as

with $\mathbf{s}_{0}=\nabla F(\mathbf{y}_{0})$.

Proof The proof of this reformulation is equivalent to prove that given the reformulation of $\mathbf{x}_{t}$, $\mathbf{y}_{t}$ and $\mathbf{s}_{t}$ at iteration $t$, the reformulation of $\mathbf{x}_{t+1}$ holds at iteration $t+1$. Therefore our induction focuses on $\mathbf{x}_{t+1}$. First, when $t=0$, we can obtain that

where the first equation is because of the update of Algorithm 1. We obtain that the result holds at $t=0$.

We now show that $\bar{x}_{t}$, $\bar{y}_{t}$, $\bar{g}_{t}$ (defined in Eq. (3) and generated by Algorithm 1) and $\bar{v}_{t}$ (defined in Eq. (18)) can be fit into the framework of the centralized Nesterov’s accelerated gradient descent.

Let $\bar{x}_{t}$, $\bar{y}_{t}$, $\bar{g}_{t}$ (defined in Eq. (3)) be generated by Algorithm 1. Then they satisfy the following equalities:

Furthermore, we will prove $\bar{s}_{t}=\eta\bar{g}_{t}$ by induction. For $t=0$, we use the fact that $\mathbf{s}_{0}=\eta\nabla F(\mathbf{y}_{0})$. Then, it holds that $\bar{s}_{0}=\bar{g}_{0}$. We assume that $\bar{s}_{t}=\bar{g}_{t}$ at time $t$. By the update equation, we have

Thus, we obtain the result at time $t+1$. The first two equations can be proved using Eq. (68) and Proposition 1.

Let $\mathbf{z}_{t}=\left[\left\|\mathbf{y}_{t}-\mathbf{1}\bar{y}_{t}\right\|,\rho^{-1}\left\|\mathbf{x}_{t}-\mathbf{1}\bar{x}_{t}\right\|,M^{-1}\left\|\mathbf{s}_{t}-\mathbf{1}\bar{s}_{t}\right\|\right]^{\top}$ with $\mathbf{x}_{t}$ and $\mathbf{y}_{t}$ generated by Algorithm 1 and $\mathbf{s}_{t}$ defined in Eq. (66), then it holds that

where $\rho$ and $\mathbf{A}$ are defined as

Proof By the update step of $\mathbf{y}_{t+1}$ in Algorithm 1, we have

By the update rule of $\mathbf{y}_{t+1}$, we have

where the last two inequalities use $1<1+\alpha$, $\eta={1}/{L}$ and $L\leq M$. Furthermore, we have

The first inequality is because of the $L$-smoothness of $f(x)$. The second inequality follows from the step size $\eta={1}/{L}$. The last inequality is due to the $\mu$-strong convexity. Thus, we can obtain that

By the definition of $\mathbf{z}_{t}$, we can obtain that

Next, we will prove the above two conditions which guarantee the convergence of $\left\|\mathbf{z}_{t}\right\|$. In the following lemma, we show the properties of $\mathbf{A}$ and prove that the spectrum radius of $\mathbf{A}$ is less than $\frac{1}{2}$ if $\rho$ is small enough.

Matrix ${\mathbf{A}}$ defined in Lemma 25 satisfies that

with $\lambda_{i}(\mathbf{A})$ being the $i$-th largest eigenvalue of $\mathbf{A}$. Let $\eta={1}/{L}$ and $\rho$ satisfy the condition that

and the eigenvector $\mathbf{v}$ associated with $\lambda_{1}(\mathbf{A})$ is positive and its entries satisfy

where $\mathbf{v}(i)$ is $i$-th entry of $\mathbf{v}$.

Proof It is easy to check that $\mathbf{A}$ is non-negative and irreducible. Furthermore, every diagonal entry of $\mathbf{A}$ is not zero. Thus, by Perron-Frobenius theorem and Corollary 8.4.7 of Horn and Johnson (2012), $\mathbf{A}$ has a real-valued positive number $\lambda_{1}(\mathbf{A})$ which is algebraically simple and associated with a strictly positive eigenvector $\mathbf{v}$. It also holds that $\lambda_{1}(\mathbf{A})$ is strictly larger than $|\lambda_{i}(\mathbf{A})|$ with $i=2,3$.

We write down the characteristic polynomial $p(\zeta)$ of ${\mathbf{A}}$,

Thus, two roots of $p_{0}(\zeta)$, $\zeta_{1}$ and $\zeta_{2}$ are

Note that $p(\zeta)$ is monotonely increasing in the range $\left[\zeta^{*},\infty\right]$. Thus, $p(\zeta)$ does not have real roots in this range. This implies $\lambda_{1}(\mathbf{A})\leq\zeta^{*}$. By Eq. (71), we can obtain that if $\rho$ satisfies

then it holds that $\Delta\leq\frac{1}{4}$. If $\rho$ also satisfies the condition that

Combining the above conditions of $\rho$, we only need that

Now, we show that $\sqrt{\rho}<\lambda_{1}(\mathbf{A})$. We can conclude this result once it holds $p(\sqrt{\rho})<0$. This is because $p(\zeta)$ will have a root between $\sqrt{\rho}$ and $1/2$ and $\lambda_{1}(\mathbf{A})$ must be no less than this root. We have

where the last inequality is because of $M\eta\geq 1$ (by Eq. (9)).

Since $\mathbf{v}$ is the eigenvector associated with $\lambda_{1}(\mathbf{A})$, we can obtain that $\mathbf{A}\mathbf{v}=\lambda_{1}(\mathbf{A})\mathbf{v}$ and have the following equations

Thus, combining with $\sqrt{\rho}\leq\lambda_{1}(\mathbf{A})\leq\frac{1}{2}$, we can obtain that

Letting $V_{t}$ be the Lyapunov function defined in Eq. (17) associated to Algorithm 1, then it satisfies the following property

Proof When $r(x)=0$, $h(x)$ equals to $f(x)$. Thus, we use $f(x)$ directly instead of $h(x)$. By the update procedure of Algorithm 1, we have

where the last equation is because $\eta={1}/{L}$. Furthermore, by the definition of $V_{t}$, we have

Furthermore, by Eq. (37), we can obtain that $\bar{v}_{t}=\bar{y}_{t}+\frac{1}{\alpha}(\bar{y}_{t}-\bar{x}_{t})$. Then we can obtain

where the last inequality is because $f(x)$ is $\mu$-strongly convex. Therefore, we can obtain that

where the second inequality is because of

Proof Let the eigenvector $\mathbf{v}$ be defined in Lemma 26 and set $\mathbf{v}(3)=1$. Combining with the fact that first two entries of $\mathbf{z}_{0}$ are zero, we can obtain that,

where the first equality is because $\mathbf{v}$ is the eigenvector associated with $\lambda_{1}(\mathbf{A})$ and the last inequality is because of Lemma 26.

Next, we will prove our result by induction. We have $\left\|\bar{s}_{0}-\eta\nabla f(\bar{y}_{0})\right\|=0$, because the initial values $\mathbf{x}_{0}(i,:)$ are equal to each other. Then by Eq. (72), we have

Next, we assume that for $i=1,\dots,t$, it holds that

Combining with Eq. (74), we can obtain that

Now we upper bound the value of $\left\|\bar{s}_{t}-\nabla f(\bar{y}_{t})\right\|$. First, by Lemma 25, we can obtain that

Combining the inductive hypothesis with Eq. (72), we have

Therefore, we can obtain that at the $(t+1)$-th iteration, it also holds that

References