Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization

Introduction

In this paper we are concerned with the design and analysis of new efficient algorithms for solving optimization problems in a decentralized storage and computation regime. In this regime, a network of agents/devices/workers, such as mobile devices, hospitals, wireless sensors, or smart home appliances, collaborates to solve a single optimization problem whose description is stored across the nodes of the network. Each node can perform computations using its local state and data, and is only allowed to communicate with its neighbors.

Problems of this form have been traditionally studied in the signal processing community (Xu et al., 2020), but are attracting increasing interest from the machine learning and optimization community as well (Scaman et al., 2017). Indeed, the training of supervised machine learning models via empirical risk minimization from training data stored across a network is most naturally cast as a decentralized optimization problem. Finally, while current federated learning (Konečný et al., 2016; McMahan et al., 2017) systems rely on a star network topology, with a trusted server performing aggregation and coordination placed at the center of the network, advances in decentralized optimization could be useful in new generation federated learning formulations that would rely on fully decentralized computation (Li et al., 2019). In summary, decentralized optimization is of direct relevance to machine learning, present and future.

Formally, given an undirected connected network $\mathcal{G}=(\mathcal{V},\mathcal{E})$ with nodes/vertices $\mathcal{V}=\{1,\ldots,n\}$ and edges $\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$, we consider optimization problems of the form

2 Computation and communication

Several decentralized gradient-type algorithms have been proposed to solve (1) in the smooth and strongly convex regime. Two key efficiency measures used to compare such methods are: i) the number of gradient evaluations (where one gradient evaluation refers to computing $\nabla f_{i}(x_{i})$ for all $i\in\mathcal{V}$ for some input vectors $x_{i}$), and ii) the number of communication rounds, where one round allows each node to send $\mathcal{O}(1)$ vectors of size $d$ to their neighbors. If computation is costly, the first comparison metric is more important, and if communication is costly, the second is more important.

Note that problem (1) poses certain intrinsic difficulties each method designed for it needs to address. Clearly, more information can be communicated in each communication round if the network $\mathcal{G}$ is “more highly” connected. By $\chi$ we denote the condition number associated with (the connectivity of) the graph $\mathcal{G}$; a formal definition is given later. Likewise, more computation will be needed if the functions $f_{i}$ are “more complicated”. We will entirely focus on problems where all functions $f_{i}$ are $L$-smooth and $\mu$-strongly convex, which naturally leads to the quantity $\kappa\coloneqq L/\mu$ as a condition number associated with computation.

Much of decentralized optimization research is focused on designing decentralized algorithms with computation and communication guarantees which have as good as possible dependence on the intrinsic properties of the problem, i.e., on the condition numbers $\kappa$ and $\chi$.

Related Work and Contributions

In this section we first briefly review some of the key results on decentralized optimization, and subsequently provide a brief summary of our key contributions.

Existing gradient-type decentralized methods for solving problem (1) can be informally classified into three classes: non-accelerated algorithms, accelerated algorithm and optimal algorithms.

Loosely speaking, a method is non-accelerated if it has at least a linear dependence on the condition numbers $\kappa$ and $\chi$, i.e., $\mathcal{O}(\kappa)$ and $\mathcal{O}(\chi)$. Please refer to (Xu et al., 2020, Table 1) for a summary of many such methods, see also (Alghunaim et al., 2019; Li and Lin, 2020). Xu et al., 2020 provide a tight unified analysis of many of these nonaccelerated algorithms, and relies on similar tools as those used in this paper, such as operator splitting and Chebyshev acceleration.

Accelerated methods have an improved (sublinear) dependence on the condition numbers, typically $\mathcal{O}(\sqrt{\kappa})$ and $\mathcal{O}(\sqrt{\chi})$. Accelerated algorithms include accelerated DNGD of Qu and Li, 2020 and accelerated EXTRA of Li and Lin, 2020; the latter using the Catalyst (Lin et al., 2017) framework to accelerate EXTRA (Shi et al., 2015). Additional accelerated methods include, the Accelerated Penalty Method of Li et al., 2018; Dvinskikh et al., 2019, SSDA and MSDA of Scaman et al., 2017 and Accelerated Dual Ascent of Uribe et al., 2020.

Scaman et al., 2017 provide lower bounds for the gradient computation and communication complexities of finding an $\varepsilon$-accurate solution; see Section 3.2 below. There have been several attempts to match these lower bounds, which include algorithms summarized in Table 1. Note, that gradient computation complexity is left as N/A for SSDA and MSDA. This is because they rely on the computation of the gradient of the Fenchel conjugate of $f_{i}$, called dual gradients in the sequel, which can be intractable. Indeed, computing a dual gradient can be as hard as minimizing $f_{i}$. Finally, we remark that Scaman et al., 2018 provide lower bounds in the nonsmooth regime as well, and an algorithm matching this lower bound is called MSPD. MSPD is primal dual Chambolle and Pock, 2011, similarly to the algorithms developed in this paper.

2 Summary of contributions

The starting point of this paper is the realization that, to the best of our knowledge, in the class of algorithms not relying on the computation of the dual gradients, there is no algorithm optimal in communication complexity, and as a result, no algorithm optimal in both gradient computation and communication complexity. To remedy this situation, we do the following:

We propose a new accelerated decentralized algorithm not relying on dual gradients: Accelerated Proximal Alternating Predictor-Corrector (APAPC) method (Algorithm 1). We show that in order to obtain $x$ for which $\|x-x^{*}\|^{2}\leq\varepsilon$, where $x^{*}$ is the solution of (1), this method only needs

gradient computations and communication rounds (Theorem 2). When combined with Chebyshev acceleration, similarly to the trick used in (Scaman et al., 2017, Section 4.2), we show that our method, which we then call Optimal Proximal Alternating Predictor-Corrector (OPAPC) method (Algorithm 2), leads to an optimal decentralized method both in terms of gradient computation and communication complexity (Corollary 1). In particular, OPAPC finds an $\varepsilon$-solution in at most

communication rounds. Algorithm 2 reaches the lower bounds (Theorem 1), and hence it is indeed optimal.

We also propose another accelerated algorithm (Algorithm 3) not relying on dual gradients, one that is optimal in communication complexity (this algorithm is presented in the appendix only). Compared to the above development, this algorithm has the added advantage that it requires the computation of a single gradient per communication step. This can have practical benefits when communication is expensive.

Background

$\mathbf{W}$ is symmetric and positive semi definite,

$\mathbf{W}_{i,j}\neq 0$ if and only if $i=j$ or $(i,j)\in\mathcal{E}$,

$\lambda_{\max}(\mathbf{W})=\lambda_{\max}(\hat{\mathbf{W}})$ and $\lambda_{\min}^{+}(\mathbf{W})=\lambda_{\min}^{+}(\hat{\mathbf{W}})$, where $\lambda_{\max}$ (resp. $\lambda_{\min}^{+}$) denotes the largest (resp. the smallest positive) eigenvalue.

In the rest of the paper, our goal is to solve the equivalent problem (3) with $\mathbf{W}$ being a gossip matrix via an optimization algorithm which uses only evaluations of $\nabla F$ and multiplications by $\mathbf{W}$.

2 Lower bounds

Linearly converging decentralized algorithms using a gossip matrix $\mathbf{W}$ often have a linear rate depending on the condition number of the $f_{i}$, $\kappa\coloneqq\frac{L}{\mu}$ and the condition number (or spectral gap) of $\mathbf{W}$, $\chi(\mathbf{W})\coloneqq\frac{\lambda_{\max}(\mathbf{W})}{\lambda_{\min}^{+}(\mathbf{W})}$. Indeed, the spectral gap of the Laplacian matrix is known to be a measure of the connectivity of the graph.

In this paper, we define the class of (first order) decentralized algorithms as the subset of black box optimization procedure (Scaman et al., 2017, Section 3.1) not using dual gradients, i.e. a decentralized algorithm is not allowed to compute $\nabla f_{i}^{*}$ (a formal definition is given in the Supplementary material). Complexity lower bounds for solving Problem (1) by a black-box optimization procedure are given by Scaman et al., 2017. These lower bounds relate the number of gradient computations (resp. number of communication rounds) to achieve $\varepsilon$ accuracy to the condition numbers $\kappa$ and $\chi(\mathbf{W})$. Since a decentralized algorithm is a black-box optimization procedure, these lower bounds apply to decentralized algorithms. Therefore, we obtain our first result as a direct application of (Scaman et al., 2017, Corollary 2).

Let $\chi\geq 1$. There exist a gossip matrix $\mathbf{W}$ with condition number $\chi$, and a family of smooth strongly convex functions $(f_{i})_{i\in\mathcal{V}}$ with condition number $\kappa>0$ such that the following holds: for any $\varepsilon>0$, any decentralized algorithm requires at least $\Omega\left(\sqrt{\kappa\chi}\log(1/\varepsilon)\right)$ communication rounds, and at least $\Omega\left(\sqrt{\kappa}\log(1/\varepsilon)\right)$ gradient computations to output $x=(x_{1},\ldots,x_{n})$ such that $\|x-x^{*}\|^{2}<\varepsilon$, where $x^{*}=\argmin F.$

Although the lower bounds of Theorem 1 are obvious consequences of (Scaman et al., 2017, Corollary 2), their tightness is not. Indeed, the lower bounds of Theorem 1 are tight on the class of black-box optimization procedures since they are achieved by MSDA Scaman et al., 2017. However, MSDA uses dual gradients and whether these lower bounds are tight on the class of decentralized algorithms is not known. In this paper, we propose decentralized algorithms achieving these lower bounds, showing in particular that they are tight.

3 Operator splitting

Recall that in this paper, any optimization algorithm solving Problem (3) by using evaluations of $\nabla F$ and multiplications by the gossip matrix $\mathbf{W}$ only is a decentralized algorithm. Such algorithms can be obtained in several ways, e.g., by applying operator splitting methods to primal dual reformulations of Problem (3), see Condat et al., 2019. This is the approach we chose in this work.

We now provide some minimal background knowledge on the Forward Backward algorithm involving monotone operators. We restrict ourselves to single valued, continuous monotone operators. For the general case of set valued monotone operators, the reader is referred to Bauschke and Combettes, 2011.

If $\nu<0$, $A$ is weakly monotone, if $\nu>0$, $A$ is strongly monotone and if $\nu=0$ then $A$ is monotone. In this paper, a monotone operator is defined as a monotone continuous map. For every monotone operator and every $\gamma>0$, the map $I+\gamma A:{\mathsf{E}}\to{\mathsf{E}}$ is one-to-one and its inverse $J_{\gamma A}=(I+\gamma A)^{-1}:{\mathsf{E}}\to{\mathsf{E}}$, called resolvent, is well defined. Let $F$ be a smooth convex function, i.e., $F$ is differentiable and its gradient is Lipschitz continuous. Then $\nabla F$ is a monotone operator, and the resolvent $J_{\gamma\nabla F}$ is the proximity operator of $\gamma F$. However, there exist monotone operators which are not gradients of convex functions. For instance, a skew symmetric operator $S$ on ${\mathsf{E}}$ defines the linear map $x\mapsto Sx$ which is not a gradient. This map is a monotone operator since $\left\langle Sx,x\right\rangle_{{\mathsf{E}}}=0$. The set of zeros of $A$, defined as $Z(A)\coloneqq\{x\in{\mathsf{E}},A(x)=0\}$, is often of interest in optimization. For instance, $Z(\nabla F)=\argmin F$.

In order to find an element in $Z(A+B)$, where $B$ is another monotone operator, the Forward Backward algorithm iterates

Note that if $A=\nabla F$ and $B=\nabla G$, where $G$ is another differentiable convex function, the Forward Backward algorithm boils down to the proximal gradient algorithm. In this particular case, Nesterov acceleration can be applied to (4) and leads to faster convergence rates compared to the proximal gradient algorithm (Nesterov, 1983; Beck and Teboulle, 2009).

For every positive definite operator $\mathbf{P}$ on ${\mathsf{E}}$, the algorithm

called the Generalized Forward Backward method, can be seen as an instance of (4) because $Z(\mathbf{P}^{-1}A+\mathbf{P}^{-1}B)=Z(A+B)$ and $\mathbf{P}^{-1}A$, $\mathbf{P}^{-1}B$ are monotone operators under the inner product induced by $\mathbf{P}$ on ${\mathsf{E}}$. For example, the gradient of $F$ under this inner product is $\mathbf{P}^{-1}\nabla F$. A primal dual optimization algorithm is an algorithm solving a primal dual formulation of a minimization problem, see below. Many primal dual algorithms can be seen as instances of (5), with general monotone operators $A,B$, for a well chosen parameter $\mathbf{P}$, see (Condat et al., 2019).

New Decentralized Algorithms

Before presenting our algorithm, we introduce an accelerated decentralized algorithm which we then use to motivate the development of our method.

Then $M,A$ and $B$ are monotone operators. Indeed, $A$ is the gradient of the convex function $(x,y)\mapsto F(x)$, $B$ satisfies

One idea to solve (6) is therefore to apply Algorithm (4) to the sum $A+B$. However, computing the resolvent $J_{B}$ in a decentralized way across the network $\mathcal{G}$ is notably challenging. Another idea is to apply (5) using the symmetric positive definite operator $P:{\mathsf{E}}\to{\mathsf{E}}$ defined by

Indeed, for every $(x,y)\in{\mathsf{E}}$, $(x^{\prime},y^{\prime})=J_{P^{-1}B}(x,y)$ implies $x^{\prime}=x-\eta y^{\prime}$ and $\frac{1}{\theta}(y^{\prime}-y)-\eta\mathbf{W}(y^{\prime}-y)=\mathbf{W}x^{\prime}=\mathbf{W}(x-\eta y^{\prime})$. Therefore, $y^{\prime}=y+\theta\mathbf{W}(x-\eta y)$, and the computation of $J_{P^{-1}B}$ only requires one multiplication by $\mathbf{W}$, i.e., one local communication round. The resulting algorithm is

The Proximal Alternating Predictor–Corrector (PAPC) algorithm, a.k.a. Loris–Verhoven (Loris and Verhoeven, 2011; Drori et al., 2015; Chen et al., 2013; Condat et al., 2019) is a primal dual algorithm that can tackle Problem (3). Up to a change of variable, Algorithm (9) can be shown to be equivalent to PAPC applied to (3). Moreover, it was already noticed that the PAPC can be represented as a Forward Backward algorithm (5) (Condat et al., 2019).

Invoking a complexity result on the PAPC from Salim et al., 2020, the complexity of Algorithm (9) is $\mathcal{O}\left((\kappa+\chi(\mathbf{W}))\log(1/\varepsilon)\right),$ both in communication and gradient computations. This complexity is equivalent to that of the best performing non accelerated algorithm proposed recently, such as Exact diffusion, NIDS and EXTRA (see Li and Lin, 2020; Xu et al., 2020). In spite of this, we are able to accelerate the convergence of Algorithm (9).

In particular, we propose a new algorithm that can be seen as an accelerated version of Algorithm (9). The proposed algorithm (APAPC) is defined in Algorithm 1) , and its complexity is given in Theorem 2. We prove that the complexity of APAPC is $\mathcal{O}((\sqrt{\kappa\chi(\mathbf{W})}+\chi(\mathbf{W}))\log(1/\varepsilon)),$ both in communication rounds and gradient computations. The proposed algorithm is accelerated because its dependence on the condition number $\kappa$ is $\mathcal{O}(\sqrt{\kappa})$ instead of $\mathcal{O}(\kappa)$.

Set the parameters $\eta,\theta,\alpha,\tau$ to $\eta=\frac{1}{4\tau L}$, $\theta=\frac{1}{\eta\lambda_{\max}(\mathbf{W})}$, $\alpha=\mu$, and $\tau=\min\left\{1,\frac{1}{2}\sqrt{\frac{\chi(\mathbf{W})}{\kappa}}\right\}.$ Then,

The proposed algorithm 1 provably accelerates Algorithm (9). The proof intuitively relies on viewing Algorithm 1 as an accelerated version of (5), although Nesterov’s acceleration does not apply to general monotone operators a priori.

2 A decentralized algorithm optimal both in communication and computation complexity

As mentioned before, while APAPC is accelerated, it is not optimal. We now derive a variant which is optimal both in gradient computations and communication rounds. Following Scaman et al., 2017, our main tool to derive the new decentralized optimal algorithm is the Chebyshev acceleration (Scaman et al., 2017; Arioli and Scott, 2014).

In particular, there exists a polynomial $P$ such that

multiplication by $P(\mathbf{W})$ requires $\left\lfloor\sqrt{\chi(\mathbf{W})}\right\rfloor$ multiplications by $\mathbf{W}$ (i.e., communication rounds) and is described by the subroutine AcceleratedGossip proposed in (Scaman et al., 2017, Algorithm 2) and recalled in Algorithm 2 for the ease of reading,

Therefore, one can replace $\mathbf{W}$ by $P(\mathbf{W})$ in Problem (3) to obtain an equivalent problem. Applying APAPC to the equivalent problem leads to a linearly converging decentralized algorithm. This new algorithm, called Optimal PAPC (OPAPC), is formalized as Algorithm 2.

Using the properties of $P(\mathbf{W})$ mentioned above, we obtain the following corollary of Theorem 2.

Set the parameters $T,c_{1},c_{2},c_{3},\eta,\theta,\alpha,\tau$ to

Moreover, for every $\varepsilon>0$, OPAPC finds $x^{k}$ for which $\|x^{k}-x^{*}\|^{2}\leq\varepsilon$ in at most $\mathcal{O}\left(\sqrt{\kappa}\log(1/\varepsilon)\right)$ gradient computations and at most $\mathcal{O}\left(\sqrt{\kappa\chi(\mathbf{W})}\log(1/\varepsilon)\right)$ communication rounds.

The Algorithm 2 achieves both the lower bounds of Theorem 1. In particular, the lower bounds of Theorem 1 are tight.

Numerical Experiments

In our experiments we used $10,000$ data samples randomly distributed to the nodes of network of size $n=100$, $m=100$ samples per each node. We used 2 networks: $10\times 10$ grid and Erdös-Rényi random graph of average degree 6. Same setup was tested by Scaman et al., 2017.

We use three LIBSVM The LIBSVM dataset collection is available at https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/ datasets: a6a, w6a, ijcnn1. The regularization parameter was chosen so that $\kappa\approx 10^{3}$. Additional experiments with synthetic data are given in the Supplementary material.

Figure 1 compares Algorithm 1 (Accelerated PAPC) and Algorithm 2 (Optimal PAPC) with three state-of-the-art accelerated benchmarks: Accelerated Penalty (Li et al., 2018; Dvinskikh et al., 2019), Accelerated Extra (Li and Lin, 2020) and MSDA Scaman et al., 2017, where we used the subroutine of Uribe et al., 2020 to compute the dual gradients. This subroutine uses primal gradients $\nabla f_{i}$, and the resulting algorithm can be shown to have an optimal communication complexity. We represent the squared distance to the solution as a function of the number of communication rounds and (primal) gradient computations.

The theory developed in this paper concerns the value of the linear rates of the proposed algorithms, i.e., the slope of the curves in Figure 1. In communication complexity, one can see that our Algorithms 1 and 2 have similar rate and perform better than the other benchmarks except MSDA. MSDA performs slightly better in communication complexity. However, MSDA uses dual gradients and has much higher iteration complexity. In gradient computation complexity, one can see that our main Algorithm 2 is, alongside Accelerated Penalty, the best performing method. Accelerated Penalty performs slightly better in gradient computation complexity. However, the theory of Accelerated Penalty does not predict linear convergence in the number of communication rounds and we see that this algorithm converges sublinearly. Overall, Optimal PAPC is the only universal method which performs well both in communication rounds and gradient computations.

2 Experiments with synthetic data

In this section, we present additional experiments. The experimental setup is the same as before, with only one difference: we use randomly generated dataset with the following choice of the number of features $d$: 40, 60, 80, 100. The results, which are shown in Figure 2, are similar to the previous results, and the same conclusions can be made.

References

Appendix

In this paper, we considered the resolution of (1) distributively across the nodes of the network $G$. Each node $i\in\mathcal{V}$ is associated with a computing agent that only have access to the local function $f_{i}$. The goal of the network of computing agent is to minimize the function (1) by performing local computations involving $f_{i}$ at each node $i$ and by communicating vectors along the edges, i.e., with neighbors $j\sim i$.

Finally, as in Scaman et al., 2017, we say that a decentralized algorithm uses the gossip matrix $\mathbf{W}$ if the local communication is achieved by multiplication of a vector by $\mathbf{W}$.

Appendix B Proof of Theorem 2 (APAPC)

If parameters $\eta$ and $\theta$ satisfy

Let $\alpha$ satisfy $0\leq\alpha\leq\mu$. Then the following inequality holds:

From line (7) of Algorithm 1 and optimality condition (6) it follows that

Since $f(x)-\frac{\alpha}{2}\|x\|^{2}$ is a convex and $(L-\alpha)$-smooth function, we can lower bound the last term and get

Rearranging and dividing by $2\eta$ concludes the proof. ∎

Let $\mathbf{P}$ be the matrix defined by (12):

From the definition of $\mathbf{P}$ it follows that

From line (7) of Algorithm 1 it follows that

From line (6) of Algorithm 1 it follows that

Finally, from lines 5 and 7 of Algorithm 1 it follows that

Let $\Psi^{k}$ be the following Lyapunov function:

Note, that stepsize $\eta$ defined by (18) and stepsize $\theta$ defined by (19) satisfy (13), hence inequality (14) holds. Using (14) and (16) we get

Since $\mathbf{W}\mathbf{W}^{\dagger}x^{*}=0$ and $\mathbf{W}\mathbf{W}^{\dagger}(y^{k+1}-y^{*})=y^{k+1}-y^{*}$, we get

Since $\nabla F(x^{*})+y^{*}=0$ (optimality condition (6)), we get

Using Young’s inequality $2\langle a,b\rangle\leq\|a\|^{2}+\|b\|^{2}$ we get

Now, we use lines 4 and 8 of Algorithm 1 and get

Since parameter $\eta$ defined by (18) satisfy $\eta\leq\frac{2-\tau}{4\tau L}$, we get

Using $\mu$-strong convexity and $L$-smoothness of $f(x)$ we get

Now, we define $\delta=\min\left\{1,\frac{1}{2\eta L}\right\}$. Since $\alpha$ defined by (20) satisfies conditions of Lemma 2, we can use (15) and get

Using parameter $\alpha$ defined by (20) we get

Using parameter $\theta$ defined by (19) and definition of $\delta$ we get

Plugging parameter $\eta$ defined by (18) we get

After rearranging and using definition of $\Psi^{k}$ (22) we get

Plugging parameter $\tau$ defined by (21) we get

Conditions of Lemma 4 are satisfied, hence the following inequality holds for all $k$:

It remains to lower bound $\Psi^{k}$ using (14) one more time:

implies $\|x^{k}-x^{*}\|^{2}\leq\varepsilon$. ∎

Appendix C Proof of Corollary 1 (OPAPC)

First, Theorem 2 still holds true by replacing $\lambda_{\max}(\mathbf{W})$ by an upper bound $\lambda_{1}$, $\lambda_{\min}^{+}(\mathbf{W})$ by a lower bound $\lambda_{2}>0$ and $\chi(\mathbf{W})$ by the upper bound $\chi=\nicefrac{{\lambda_{1}}}{{\lambda_{2}}}$. The proof is the same by replacing $\lambda_{\max}(\mathbf{W})$ by $\lambda_{1}$ and $\lambda_{\min}^{+}(\mathbf{W})$ by $\lambda_{2}$.

The proof of Corollary 1 is similar to the proof of Theorem 4 of Scaman et al., 2017.

Moreover, by replacing $c_{1}$ and $T$ by their values, $\chi\coloneqq\frac{\lambda_{1}}{\lambda_{2}}\leq 4$, see (Scaman et al., 2017, Equation 34).

Appendix D A Loopless Algorithm Optimal in Communication Complexity

We propose another accelerated Forward Backward algorithm to solve Problem (3). More precisely, we first provide a reformulation of Problem (3), different from the reformulation (6). Then, we design an accelerated Forward Backward algorithm associated with this reformulation. Remarkably, the matrix $\mathbf{W}$ is only involved in the operator $A$ of this new Forward Backward algorithm. This leads to an acceleration compared to APAPC, and to an optimal communication complexity.

Consider the map $M:{\mathsf{E}}\to{\mathsf{E}}$

Similary to Section 4.1, one can show that $M$ is a monotone operator. Moreover, $M(x^{*},y^{*},z^{*})=0$, i.e., $(x^{*},y^{*},z^{*})$ is a zero of $M$.

Consider the maps $A,B:{\mathsf{E}}\to{\mathsf{E}}$ defined by

Then, $M=A+B$. Note that there is a term $\nu y$, where $\nu>0$ in $A(x,y,z)$ and a term $-\nu y$ in $B(x,y,z)$, which cancel out in the sum $A(x,y,z)+B(x,y,z)$. This additional term makes the operator $A(x,y,z)$ strongly monotone. Indeed, $A$ is the gradient of the strongly convex function (in ${\mathsf{E}}$) ${\mathsf{E}}\ni(x,y,z)\mapsto r(x)+h(y,z)$ defined by

In other words, operator $A(x,y,z)$ can be written as

and one can check that $A$ is strongly monotone. However, the operator $B(x,y,z)$ is not monotone in general. Indeed, $B$ is only weakly monotone since $B$ satisfies

One idea to solve (32)–(34) is to apply Algorithm (4) to the sum $A+B$, although $B$ is not monotone. Note that $B$ is linear and, although $B$ is not monotone, the resolvent of $B$ is still well defined while $1-\gamma\nu+\gamma^{2}\neq 0$. Indeed, $(x^{\prime},y^{\prime})=J_{\gamma B}(x,y)$ implies $x^{\prime}=x+\gamma y^{\prime}$, and $(1-\gamma\nu+\gamma^{2})y^{\prime}=y-\gamma x$.

In particular, we propose a new algorithm that can be seen as an accelerated version of the Forward Backward Algorithm (4) to find a zero of $A+B$. The proposed algorithm is defined in Algorithm 3 and its complexity is given in Theorem 3. We show that the complexity of Algorithm 3 is $\mathcal{O}(\sqrt{\kappa\chi(\mathbf{W})}\log(1/\varepsilon))$, both in communication rounds and gradient computations. The proposed algorithm is therefore optimal in communication complexity, see Section 3.2. Moreover, Algorithm 3 uses only one gradient computation by communication round.

Set the parameters $\eta,\theta,\lambda,\alpha,\beta,\gamma,\nu>0,\tau,\sigma\in(0,1)$ to

Then, the sequence $(x^{k})$ converges linearly to $x^{*}$. Moreover, for every $\varepsilon>0$, Algorithm 3 finds $x^{k}$ for which $\|x^{k}-x^{*}\|^{2}\leq\varepsilon$ in at most $\mathcal{O}\left(\sqrt{\kappa\chi(\mathbf{W})}\log(1/\varepsilon)\right)$ gradient computations (resp. communication rounds).

The Algorithm 3 achieves the communication lower bound of Theorem 1. The proof of Theorem 3 intuitively relies on viewing Algorithm 3 as an accelerated version of (4), although Nesterov’s acceleration does not apply to general monotone operators and even less to non monotone operators.

Appendix E Proof of Theorem 3 (Algorithm 3)

From line 9 of Algortihm 3 it follows that

From optimality condition (32) it follows that $\nabla r(x^{*})=y^{*}$ and hence

From (43) it follows that function $r(x)-\frac{\alpha}{2}\|x\|^{2}=F(x)-\frac{\mu+2\alpha}{4}\|x\|^{2}$ is convex and $L$-smooth, hence we can bound the last term:

Multiplying by $\frac{1}{2\eta}$ and rearranging gives

From optimality condition (32) it follows that $\nabla r(x^{*})=y^{*}$ and hence

Using lines 6 and 12 of Algorithm 3 we get

Using $\frac{\mu}{2}$-strong convexity and $L$-smoothness of $r(x)$ and $\eta$ defined by (46) we get

From optimality condition (33) it follows that $x^{*}=-\frac{2}{\mu}(y^{*}+z^{*})=-\nabla_{y}h(y^{*},z^{*})+\nu y^{*}$ and hence

Using lines 7 and 13 of Algorithm 3 we get

From optimality condition (34) it follows that $\mathbf{W}\nabla_{z}h(y^{*},z^{*})=0$ and hence

Using lines 8 and 14 of Algorithm 3 we get

Using $\gamma$ defined by (52) and the fact that $\beta\leq\frac{1}{\mu}$ which follows from (51) we get

Using the fact that $\beta\leq\frac{\nu}{3}$ which follows from (51) we get

Let $\Psi^{k}$ be the following Lyapunov function:

One can observe that conditions of lemma 6 and lemma 8 are satisfied. Hence we can combine (47) and (53) and get

and hence, using choice of $\alpha$, $\beta$ and $\nu$, we get

After rearranging and using definition of $\Psi^{k}$ (76) we get