Kevin Scaman
email: kevin.scaman@huawei.com

Francis Bach
email: francis.bach@inria.fr

Sébastien Bubeck
email: sebubeck@microsoft.com

Yin Tat Lee

Laurent Massoulié
email: laurent.massoulie@inria.fr

Optimal Convergence Rates for Convex Distributed Optimization in Networks

Keywords: distributed optimization, convex optimization, first-order methods n n

come   L'archive ouverte pluridisciplinaire

Introduction

Distributed optimization finds many applications in machine learning, for example when the data set is large and training is achieved using a cluster of computing units. As a result, many algorithms were recently introduced to minimize the average f =1 often, these algorithms alternate between local and incremental improvement steps (such as gradient steps) with communication steps between nodes in the network, and come with a variety of convergence rates (see, for example, [START_REF] Shi | On the linear convergence of the ADMM in decentralized consensus optimization[END_REF][START_REF] Shi | EXTRA: An exact first-order algorithm for decentralized consensus optimization[END_REF][START_REF] Jakovetić | Linear convergence rate of a class of distributed augmented lagrangian algorithms[END_REF][START_REF] Nedic | Achieving geometric convergence for distributed optimization over time-varying graphs[END_REF].

The main contribution of this paper is to provide optimal convergence rates and their corresponding optimal algorithms for distributed convex problems under a large panel of regularity assumptions and communication schemes. More specifically, we consider two communication schemes and four regularity assumptions. Communication is either achieved through a master/slave approach that we refer to as centralized, or in a decentralized scheme in which communication is performed using the gossip algorithm [START_REF] Boyd | Randomized gossip algorithms[END_REF]. Moreover, the four regularity assumptions that we investigate in this paper are: Lipschitz continuity, strong convexity, smoothness, and both strong convexity and smoothness. These settings are summarized in Table 1 along with their corresponding upper and lower complexity bounds. These bounds depend on the time τ necessary to communicate a vector between two neighbors in the communication graph, the diameter of the communication graph ∆, its mixing time ∆ (see Section 4), the dimension of the optimization problem d and distance to optimum R, and the Lipschitz, strong convexity, smoothness constants, and condition number of the objective function (L g , α g , β g and κ g , respectively, for the global objective function, and L , α , β and κ for an aggregation of the local individual functions of each computing unit, see Section 2).

Under decentralized communication, we provide in Section 4 matching upper and lower bounds of complexity. 1 Moreover, we propose the first optimal algorithm for non-smooth decentralized optimization, called multi-step primal-dual (MSPD). Under centralized communication, we show in Section 3 that, for smooth objectives, a naïve distribution of accelerated gradient descent is optimal, while for non-smooth objectives, distributing the simple smoothing approach introduced by Duchi et al. (2012b) yields fast convergence rates with respect to communication. This algorithm, called distributed randomized smoothing (DRS), achieves a convergence rate matching the lower bound up to a d 1/4 multiplicative factor, where d is the dimensionality of the problem.

The analysis of non-smooth optimization differs from the smooth setting in two major aspects: (1) the naïve master/slave distributed algorithm is in this case not optimal, and (2) the convergence rates differ between communication and local computations. More specifically, errors due to limits in communication resources enjoy fast convergence rates, as we establish by formulating the optimization problem as a composite saddle-point problem with a smooth term for communication and non-smooth term for the optimization of the local functions (see Section 4 and Equation 11 for more details).

Related Work

Many algorithms were proposed to solve the decentralized optimization of an average of functions, from early decentralized algorithms [START_REF] Nedic | Distributed subgradient methods for multi-agent optimization[END_REF][START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF]Duchi et al., 2012a;[START_REF] Wei | Distributed alternating direction method of multipliers[END_REF][START_REF] Jakovetić | Fast distributed gradient methods[END_REF][START_REF] Shi | On the linear convergence of the ADMM in decentralized consensus optimization[END_REF][START_REF] Shi | EXTRA: An exact first-order algorithm for decentralized consensus optimization[END_REF] Table 1: Upper and lower bounds on the minimax optimal time needed to reach an ε > 0 precision for four regularization assumptions and two communication settings, along with corresponding optimal algorithms (AGD stands for the naïve distribution of accelerated gradient descent, see Section 3 for more details). [START_REF] Mokhtari | DSA: Decentralized double stochastic averaging gradient algorithm[END_REF] to more recent improvements [START_REF] Qu | Accelerated distributed nesterov gradient descent for smooth and strongly convex functions[END_REF][START_REF] Jiang | Collaborative deep learning in fixed topology networks[END_REF][START_REF] He | Cola: Decentralized linear learning[END_REF][START_REF] Shi Pu | A push-pull gradient method for distributed optimization in networks[END_REF][START_REF] César | A dual approach for optimal algorithms in distributed optimization over networks[END_REF][START_REF] Koloskova | Decentralized stochastic optimization and gossip algorithms with compressed communication[END_REF][START_REF] Xin | Distributed nesterov gradient methods over arbitrary graphs[END_REF][START_REF] Jakovetić | A unification and generalization of exact distributed first-order methods[END_REF]. Another line of work considers more restrictive assumptions on the optimization problems to obtain fast convergence rates [START_REF] Lee | Communication-efficient sparse regression[END_REF][START_REF] Hou | Efficient distributed estimation of inverse covariance matrices[END_REF][START_REF] Tian | Communication-efficient Distributed Sparse Linear Discriminant Analysis[END_REF]. A sheer amount of work was devoted to improving the convergence rate of these algorithms [START_REF] Shi | On the linear convergence of the ADMM in decentralized consensus optimization[END_REF][START_REF] Jakovetić | Linear convergence rate of a class of distributed augmented lagrangian algorithms[END_REF]. In the case of non-smooth optimization, fast communication schemes were developed by [START_REF] Lan | Communication-efficient algorithms for decentralized and stochastic optimization[END_REF]; [START_REF] Jaggi | Communication-efficient distributed dual coordinate ascent[END_REF], although precise optimal convergence rates were not obtained. Our decentralized algorithm is closely related to the recent primal-dual algorithm of [START_REF] Lan | Communication-efficient algorithms for decentralized and stochastic optimization[END_REF] which enjoys fast communication rates in a decentralized and stochastic setting. Unfortunately, their algorithm lacks gossip acceleration to reach optimality with respect to communication time. Finally, optimal convergence rates for distributed algorithms were investigated by [START_REF] Scaman | Optimal algorithms for smooth and strongly convex distributed optimization in networks[END_REF] for smooth and strongly convex objective functions, [START_REF] Shamir | Fundamental limits of online and distributed algorithms for statistical learning and estimation[END_REF]; [START_REF] Arjevani | Communication complexity of distributed convex learning and optimization[END_REF] for totally connected networks, and more recently by Dvinskikh and Gasnikov (2019) who derive optimal algorithms (up to logarithmic multiplicative factors) for decentralized optimization, yet without the corresponding complexity lower bounds. Our analysis proves that these algorithms are indeed, up to logarithmic multiplicative factors, optimal in a minimax sense. A preliminary version of this work with only the analysis for the Lipschitz-continuous case (first line in Table 1) is available as a conference paper [START_REF] Scaman | Optimal algorithms for non-smooth distributed optimization in networks[END_REF].

Distributed Optimization Setting

In this section, we provide a detailed presentation of the distributed optimization setting considered in this work. The definitions are analogous to that of [START_REF] Scaman | Optimal algorithms for smooth and strongly convex distributed optimization in networks[END_REF].

Optimization Problem

Let G = (V, E) be a connected simple (i.e., undirected) graph of n computing units and diameter ∆, each having access to a convex function f i over a convex set K ⊂ R d . We consider minimizing the average of the local functions

min θ∈K f (θ) = 1 n n i=1 f i (θ) , (1)
in a distributed setting. More specifically, we assume that each computing unit can compute a subgradient ∇f i (θ) of its own function in one unit of time, and communicate values (i.e., vectors in R d ) to its neighbors in G. A direct communication along the edge (i, j) ∈ E requires a time τ ≥ 0. These actions may be performed asynchronously and in parallel, and each machine i possesses a local version of the parameter, which we refer to as θ i ∈ K.

Regularity Assumptions

Optimal convergence rates depend on the precise set of assumptions applied to the objective function. In our case, we will consider four different regularity assumptions:

1. Convexity: a function f is convex if, for all θ, θ ∈ K and a ∈ [0, 1],

f (aθ + (1 -a)θ ) ≤ af (θ) + (1 -a)f (θ ) . 2. Strong convexity: a function f is α-strongly convex if f (θ) -α 2 θ 2 2 is convex. 3. Lipschitz continuity: a function f is L-Lipschitz continuous if, for all θ, θ ∈ K, |f (θ) -f (θ )| ≤ L θ -θ 2 . 4. Smoothness: a function f is β-smooth if its gradient ∇f is β-Lipschitz continuous.
Moreover, when a function is both α-strongly convex and β-smooth, we denote by κ = β/α its condition number. In our analysis, we will denote by L g , α g , β g and κ g the characteristics of the (global) function f , while, for i ∈ 1, n , we will refer to L i , α i , β i and κ i for characteristics of each (local) function f i . Finally, for the sake of clarity, we will aggregate these local characteristics into the following values:

L = 1 n n i=1 L 2 i , α = min i α i , β = max i β i , and κ = β /α .
Global regularity is always weaker than local regularity, as we always have L g ≤ L , α g ≥ α , β g ≤ β and κ g ≤ κ . Moreover, we may have L g = 0 and L arbitrarily large, for example with two linear functions f 1 (x) = -f 2 (x) = ax and a → +∞. We will see in the following sections that the local regularity assumption is easier to analyze and leads to matching upper and lower bounds. For the global regularity assumption, we only provide algorithms with a d 1/4 competitive ratio, where d is the dimension of the problem. Finding an optimal distributed algorithm for global regularity is, to our understanding, a much more challenging task and is left for future work.

Finally, we assume that the feasible region K is convex and bounded, and denote by R the radius of a ball containing K, i.e.,

∀θ ∈ K, θ -θ 0 2 ≤ R ,
where θ 0 ∈ K is the initial value of the algorithm, that we set to θ 0 = 0 without loss of generality.

Black-box Optimization Procedure

The lower bounds provided hereafter depend on the notion of black-box optimization procedures for the problem in Equation 1. The definition is analogous to that of [START_REF] Scaman | Optimal algorithms for smooth and strongly convex distributed optimization in networks[END_REF], except that gradients of the Fenchel conjugate of local functions are considered too expensive to compute. This allows us to focus on primal methods which are generally easier to apply (less assumptions required on the objective function) and faster to compute (the Fenchel conjugate is, except for very specific functions, hard to approximate). A black-box optimization procedure is a distributed algorithm verifying the following constraints:

1. Local memory: each node i can store past values in a (finite) internal memory M i,t ⊂ R d at time t ≥ 0. These values can be accessed and used at time t by the algorithm run by node i, and are updated either by local computation or by communication (defined below), that is, for all i ∈ 1, n ,

M i,t ⊂ M comp i,t ∪ M comm i,t .
2. Local computation: each node i can, at time t, compute a subgradient of its local function ∇f i (θ) for a value θ ∈ M i,t-1 in the node's internal memory before the computation.

M comp i,t = Span ({θ, ∇f i (θ) : θ ∈ M i,t-1 }) .
3. Local communication: each node i can, at time t, share a value to all or part of its neighbors, that is, for all i ∈ 1, n ,

M comm i,t = Span (j,i)∈E M j,t-τ .
4. Output value: each node i must, at time t, specify one vector in its memory as local output of the algorithm, that is, for all i ∈ 1, n ,

θ i,t ∈ M i,t .
Hence, a black-box procedure will return n output values-one for each computing unit-and our analysis will focus on ensuring that all local output values are converging to the optimal parameter of Equation 1. For simplicity, we assume that all nodes start with the simple internal memory M i,0 = {0}. Note that communications and local computations may be performed in parallel and asynchronously.

Centralized Optimization under Global Regularity

The most standard approach for distributing a first-order optimization method consists in computing a gradient (or subgradient when the objective function is non-smooth) of the average function

∇ f (θ) = 1 n n i=1 ∇f i (θ) ,
where ∇f i (θ) is a gradient (or any subgradient of f i at θ), by sending the current parameter θ t to all nodes, performing the computation of all local subgradients in parallel and averaging them on a master node. Since each iteration requires communicating twice to the whole network (once for θ t and once for sending the local subgradients to the master node, which both take a time ∆τ where ∆ is the diameter of the network) and one gradient computation (on each node and performed in parallel), the time to reach a precision ε with such a distributed optimization algorithm is upper-bounded by

O g(ε)(1 + ∆τ ) , (2)
where g(ε) is the number of iterations required for the single-machine optimization algorithm to achieve a precision ε. Note that, as the single-machine optimization algorithm is directly used for f , this convergence rate depends on the global characteristics of objective function.

For smooth objective functions, we will see in Section 3.2 that distributing in such a way Nesterov's accelerated gradient descent leads to an optimal convergence rate. For non-smooth objective functions, however, the simple scheme is not optimal: the number of subgradient computations in Equation 2 (i.e., the term not proportional to τ ) cannot be improved, since it is already optimal for objective functions defined on only one machine-see for example Theorem 3.13 p. 280 from [START_REF] Bubeck | Convex optimization: Algorithms and complexity[END_REF]. However, quite surprisingly, the error due to communication time may benefit from fast convergence rates in O(RL g /ε). This result is already known under the local regularity assumption (i.e., replacing L g with L or even max i L i ) in the case of decentralized optimization [START_REF] Lan | Communication-efficient algorithms for decentralized and stochastic optimization[END_REF] or distributed optimization on a totally connected network [START_REF] Arjevani | Communication complexity of distributed convex learning and optimization[END_REF]. To our knowledge, the case of global regularity has not been investigated by prior work.

We first describe algorithms in Section 3.1, and then study their optimality according in Section 3.2.

Fast Communication Rates for Non-Smooth Objective Functions

We now show that the simple smoothing approach introduced by Duchi et al. (2012b) can lead to fast rates for error due to communication time. Let γ > 0 and f : R d → R be a real function. We denote as smoothed version of f the following function:

f γ (θ) = E [f (θ + γX)] , (3)
where X ∼ N(0, I) is a standard Gaussian random variable. The following lemma shows that f γ is both smooth and a good approximation of f .

Lemma 1 (Lemma E.3 of Duchi et al., 2012b) If γ > 0, then f γ is ( Lg γ )-smooth and, for all θ ∈ R d , f (θ) ≤ f γ (θ) ≤ f (θ) + γL g √ d .
Hence, smoothing the objective function allows the use of accelerated optimization algorithms and provides faster convergence rates. Of course, the price to pay is that each computation of the smoothed gradient ∇ f γ (θ) = 1 n n i=1 ∇f γ i (θ) now requires, at each iteration m, to sample a sufficient amount of subgradients ∇f i (θ + γX m,k ) to approximate Equation 3, where X m,k are K i.i.d. Gaussian random variables. At first glance, this algorithm requires all computing units to synchronize on the choice of X m,k , which would require to send to all nodes each X m,k and thus incur a communication cost proportional to the number of samples. Fortunately, computing units only need to share one random seed s ∈ R and then use a random number generator initialized with the provided seed to generate the same random variables X m,k without the need to communicate any vector. While the theoretical results assume that the randomness is shared, in practice this is done approximately by sharing random seeds and using pseudo-random generators. The overall algorithm, denoted distributed randomized smoothing (DRS), uses the randomized smoothing optimization algorithm of Duchi et al. (2012b) adapted to a distributed setting, and is summarized in Alg. 1. The computation of a spanning tree T in step 1 allows efficient communication to the whole network in time at most ∆τ . Most of the algorithm (i.e., steps 2, 4, 6, 7, 9, 10 and 11) are performed on the root of the spanning subtree T, while the rest of the computing units are responsible for computing the smoothed gradient (step 8). The seed s of step 2 is used to ensure that every X m,k , although random, is the same on every node. Finally, step 10 is a simple orthogonal projection of the gradient step on the convex set K.

Convex Case

We now show that the DRS algorithm converges to the optimal parameter under global Lipschitz regularity.

Theorem 2 Under global Lipschitz-continuity, Alg. 1 achieves an approximation error

E f (θ T ) -f (θ * ) of at most ε > 0 in a time T ε upper-bounded by O RL g ε 2 + RL g ε (1 + ∆τ )d 1/4 . ( 4
)
Algorithm 1 distributed randomized smoothing (convex case)

Input: approximation error ε > 0, communication graph G, α 0 = 1, α t+1 = 2/(1 + 1 + 4/α 2 t ) T = 20RLgd 1/4 ε , K = 5RLgd -1/4 ε , γ t = Rd -1/4 α t , η t = Rαt 2Lg(d 1/4 + t+1 K )
.

Output: optimizer θ T 1: Compute a spanning tree T on G.

2: Send a random seed s to every node in T.

3: Initialize the random number generator of each node using s.

4: x 0 = 0, z 0 = 0, G 0 = 0 5: for t = 0 to T -1 do 6: y t = (1 -α t )x t + α t z t 7:
Send y t to every node in T.

8:

Each node i computes g i = 1 K K k=1 ∇f i (y t + γ t X t,k ), where X t,k ∼ N(0, I) 9: G t+1 = G t + 1 nαt i g i 10: z t+1 = argmin x∈K x + η t+1 G t+1 2 2
11:

x t+1 = (1 -α t )x t + α t z t+1 12: end for 13: return θ T = x T More specifically, Alg. 1 completes its T iterations by time

T ε ≤ 100 RL g d 1/4 ε RL g d -1/4 ε + 40 RL g d 1/4 ε ∆τ . (5)
Comparing Equation 4to Equation 2, we can see that our algorithm benefits from faster convergence rates than the naïve distribution of gradient descent (leading to g(ε) = (RL g /ε) 2 in Equation 2, which is optimal for single machine optimization of convex non-smooth problems) when the dimension is not too large, and more specifically

d ≤ RL g ε 4 .
In practice, this condition is easily met, as ε ≤ 10 -2 already leads to the condition d ≤ 10 8 (assuming that the product RL g is close to 1). Moreover, for problems of moderate dimension, the term d 1/4 remains a small multiplicative factor (e.g. for d = 1000, d 1/4 ≈ 6). Finally, note that DRS achieves a linear speedup when communication through the whole network requires a constant time, i.e., ∆τ = O(1).

Remark 3 Several other smoothing methods exist in the literature, notably the Moreau envelope [START_REF] Moreau | Proximité et dualité dans un espace Hilbertien[END_REF] enjoying a dimension-free approximation guarantee. However, the Moreau envelope of an average of functions is difficult to compute (requires a different oracle than computing a subgradient), and unfortunately leads to convergence rates with respect to local Lipschitz characteristics instead of L g . Moreover, the above analysis can be extended to any rotation invariant probability measure (e.g. uniform on a ball) for the smoothing noise. Such an analysis shows that the convergence rate obtained by using Gaussian random

Algorithm 2 distributed randomized smoothing (strongly-convex case)

Input: approximation error ε > 0, communication graph G, c d,ε = d 1/4 log 8( f (θ 0 )-f (θ * )) ε , T = 2 √ 2Lgc d,ε √ αgε , K = 70Lgc -1 d,ε √ αgε , γ = ε 2Lg √ d , n 0 = -1, n 1 = Lg αgγ log 4( f (θ 0 )-f (θ * )) ε , ∀t > 1, n t = 2 t Lg αgγ log(8) , η 1 = γ Lg , ∀t > 1, η t = γ 2 2t Lg , µ t = 1- √ αgηt 1+ √ αgηt . Output: optimizer θ T 1:
Compute a spanning tree T on G.

2: Send a random seed s to every node in T.

3: Initialize the random number generator of each node using s.

4: for t = 1 to T do 5:

x t 0 = x t 1 = x t-1 n t-1 +1
6:

for m = 1 to n t do 7:

y t m = (1 + µ t )x t m -µ t x t m-1 8:
Send y t m to every node in T.

9:

Each node i computes

g i = 1 K K k=1 ∇f i (y t m + γX k )
, where X k ∼ N(0, I) 10:

x t m+1 = y t m -ηt n i g i 11:
end for 12: end for 13: return θ T = x T noise is unimprovable by modifying the noise distribution. This is in accordance with recent theoretical results of [START_REF] Bubeck | Complexity of highly parallel non-smooth convex optimization[END_REF] that imply that the d 1/4 multiplicative factor in Equation 4 is unimprovable in the regime T ≤ √ d where T is the number of iterations of the algorithm.

Remark 4 Due to its random nature, Alg. 1 is not per se a black-box procedure, and Theorems 8 and 9 of Section 3.2 do not apply to it. Lower bounds for random algorithms are more challenging and left for future work.

Remark 5 Only the convexity of the global function f is necessary for Alg. 1 to converge. For example, the local functions f i may be non convex differentiable functions whose average is convex.

Strongly Convex Case

The same smoothing strategy is also applicable for strongly convex objectives, and yields similar improvements in the convergence rate. Unfortunately, the analysis of randomized smoothing for strongly convex objectives is yet missing in the literature, and we thus need to use another convergence result. Alg. 2 applies Nesterov's accelerated gradient descent to the smoothed objective function f γ , leading to fast communication rates for strongly convex objectives. More specifically, we use the recent algorithm M-ASG by Serhat Aybat et al. ( 2019) that provides tight convergence rates for accelerated gradient descent under additive noise on the gradient.

Theorem 6 Under global Lipschitz-continuity and strong convexity and for ε

< f (θ 0 ) - f (θ * ), Alg. 2 achieves an approximation error E f (θ T ) -f (θ * ) of at most ε in a time T ε upper-bounded by O L 2 g α g ε + L 2 g α g ε (1 + ∆τ )d 1/4 log 1 ε .
More specifically, Alg. 2 completes its T iterations by time

T ε ≤ 2 √ 2L g c d,ε √ α g ε 70L g c -1 d,ε √ α g ε + 4 √ 2L g c d,ε √ α g ε ∆τ , (6)
where

c d,ε = d 1/4 log 8( f (θ 0 )-f (θ * )) ε
. The proof is available in Appendix A.

While Alg. 2 relies on the two-level nested iterations of M-ASG, we believe that more simple algorithms may also lead to similar convergence rates, e.g. directly using Nesterov's gradient descent and its recent stochastic analysis by [START_REF] Vaswani | Fast and faster convergence of SGD for over-parameterized models and an accelerated perceptron[END_REF]. Note that Theorem 6, as well as all lower bounds for the strongly convex case, is an addition compared to our preliminary work [START_REF] Scaman | Optimal algorithms for non-smooth distributed optimization in networks[END_REF].

Remark 7 The Lipschitz and convex setting of Section 3.1.1 can also be solved by Alg. 2 by adding a quadratic regularization α 2 θ 2 2 with a sufficiently small α, although this would incur a multiplicative logarithmic factor compared to the convergence rate of Alg. 1.

Optimal Convergence Rates

The following results provide oracle complexity lower bounds for centralized algorithms, and are proved in Appendix B. These lower bounds extend the communication complexity lower bounds for totally connected communication networks of [START_REF] Arjevani | Communication complexity of distributed convex learning and optimization[END_REF]. Note that, in all following results, we consider that the dimension d is larger than both the number of communication and computation steps. This assumption is relatively standard in non-smooth optimization (Nesterov, 2004, Theorem 3.2.1) and valid for either small times or large dimensional problems. When the number of iterations is larger than the dimension d, linearly convergent algorithms exist even for convex non-smooth problems [START_REF] Bubeck | Convex optimization: Algorithms and complexity[END_REF].

Non-Smooth Objective Functions

Theorem 8 Let G be a network of computing units of size n > 0, and L g , R > 0. There exists n convex functions f i : R d → R such that f is L g -Lipschitz and, for any t < d-2 2 min{1, ∆τ } and any black-box procedure one has, for all i ∈ 1, n ,

f (θ i,t ) -min θ∈B 2 (R) f (θ) ≥ RL g 36 1 (1 + t 2∆τ ) 2 + 1 1 + t . (7)
Assuming that the dimension d is large compared to the characteristic values of the problem (i.e., d > 2 + 2 max{t, t/∆τ }), Theorem 8 implies that, under global Lipschitz continuity, the time to reach a precision ε > 0 with any black-box procedure is lower bounded by

Ω RL g ε 2 + RL g ε ∆τ ,
where the notation g(ε) = Ω(f (ε)) stands for ∃C > 0 s.t. ∀ε > 0, g(ε) ≥ Cf (ε). This lower bound proves that the convergence rate of DRS in Equation 4 is optimal with respect to computation time and within a d 1/4 multiplicative factor of the optimal convergence rate with respect to communication.

Theorem 9 Let G be a network of computing units of size n > 0, and L g , α g > 0. There exists a convex set Θ ⊂ R d and n convex functions f i : Θ → R such that f is L g -Lipschitz and α g -strongly convex and, for any t < d-2 2 min{1, ∆τ } and any black-box procedure one has, for all i ∈ 1, n ,

f (θ i,t ) -min θ∈Θ f (θ) ≥ L 2 g 108α g 1 (1 + t 2∆τ ) 2 + 1 1 + t . ( 8
)
Assuming that the dimension d is large compared to the characteristic values of the problem (i.e., d > 2 + 2 max{t, t/∆τ }), Theorem 9 implies that, under global strong convexity and Lipschitz continuity, the time to reach a precision ε > 0 with any black-box procedure is lower bounded by

Ω L 2 g α g ε + L 2 g α g ε ∆τ .
This lower bound proves that the convergence rate of the strongly convex version of DRS in Equation 6 is, up to logarithmic factors, optimal with respect to computation time and within a d 1/4 multiplicative factor of the optimal convergence rate with respect to communication.

The proof of Theorem 8 and Theorem 9 relies on the use of two objective functions: first, the standard worst case function used for single machine convex optimization (see, e.g., [START_REF] Bubeck | Convex optimization: Algorithms and complexity[END_REF] is used to obtain a lower bound on the local computation time of individual machines. Then, a second function first introduced by Arjevani and Shamir ( 2015) is split on the two most distant machines to obtain worst case communication times. By aggregating these two functions, a third one is obtained with the desired lower bound on the convergence rate. The complete proof is available in Appendix B.1. Finally, note that, due to its random nature, Alg. 1 is not per se a black-box procedure, and Theorems 8 and 9 do not apply to it. Lower bounds for random algorithms are more challenging and left for future work.

Remark 10 The lower bounds also hold for the average of local parameters 1 n n i=1 θ i , and more generally any parameter that can be computed using any vector of the local memories at time t: in Theorem 8, θ i,t may be replaced by any θ t such that

θ t ∈ Span i∈V M i,t .

Smooth Objective Functions

The following theorems provide lower bounds for smooth centralized optimization. The first is a novel result of this work, while the second was first derived by Scaman et al. (2017, Theorem 1) and is included in this section for the sake of completeness.

Theorem 11 Let G be a network of computing units of size n > 0, and β g > 0. There exists n convex functions f i : R d → R such that f is β g -smooth and, for any t ≤ 1 + d-3

2 (1 + ∆τ ) and any black-box procedure one has, for all i ∈ 1, n ,

f (θ i,t ) -min θ∈R d f (θ) ≥ 3β g θ i,0 -θ * 2 32 t-1 1+∆τ + 1 2 , ( 9
)
where θ * is a minimizer of f .

Assuming that the dimension d is large compared to the characteristic values of the problem (i.e., d > 3+2(t-1)/(1+∆τ )), Theorem 11 implies that, under global smoothness, the time to reach a precision ε > 0 with any black-box procedure is lower bounded by

Ω β g θ i,0 -θ * 2 ε 1 + ∆τ .
In order to simplify the proofs of the following theorem, and following the approach of Bubeck (2015), we will consider the limiting situation d → +∞. More specifically, we now assume that we are working in 2 = {θ = (θ k ) k∈N :

k θ 2 k < +∞} rather than R d . Theorem 12 Let G be a network of computing units of size n > 0, and β g ≥ α g > 0. There exists n convex functions f i : 2 → R such that f is α g strongly convex and β g smooth, and for any t ≥ 0 and any black-box procedure one has, for all i ∈ 1, n ,

f (θ i,t ) -f (θ * ) ≥ α g 2 1 - 4 √ κ g 1+ t 1+∆τ θ i,0 -θ * 2 , ( 10
)
where κ g = β g /α g .

Assuming that the dimension d is large compared to the characteristic values of the problem (i.e., d max{t, t/∆τ }), Theorem 12 implies that, under global strong convexity and smoothness, the time to reach a precision ε > 0 with any black-box procedure is lower bounded by

Ω √ κ g ln 1 ε 1 + ∆τ .
These two lower bounds prove that the naïve distribution of Nesterov's gradient descent is optimal for both smooth and smooth and strongly convex objective functions. Their proofs rely on splitting the functions used by Nesterov to prove oracle complexities for smooth optimization [START_REF] Nesterov | Introductory Lectures on Convex Optimization : a Basic Course[END_REF][START_REF] Bubeck | Convex optimization: Algorithms and complexity[END_REF] on two nodes at distance ∆. One can show that most dimensions of the parameters θ i,t will remain zero, and local gradient computations may only increase the number of non-zero dimensions by one. Finally, at least ∆ communication rounds are necessary in-between every gradient computation, in order to share information between the two nodes. The complete proofs are available in Appendix B.2.

Decentralized Optimization under Local Regularity

In many practical scenarios, the network may be unknown or changing through time, and a local communication scheme is preferable to the master/slave approach of Alg. 1. Decentralized algorithms tackle this problem by replacing targeted communication by local averaging of the values of neighboring nodes [START_REF] Boyd | Randomized gossip algorithms[END_REF]. More specifically, we now consider that, during a communication step, each machine i broadcasts a vector x i ∈ R d to its neighbors, then performs a weighted average of the values received from its neighbors: node i sends x i to his neighbors and receives j W ji x j .

In order to ensure the efficiency of this communication scheme, we impose standard assumptions on the matrix W ∈ R n×n , called the gossip matrix [START_REF] Boyd | Randomized gossip algorithms[END_REF][START_REF] Scaman | Optimal algorithms for smooth and strongly convex distributed optimization in networks[END_REF]:

1. W is symmetric and positive semi-definite.

2. The kernel of W is the set of constant vectors: Ker(W ) = Span(1), where 1 = (1, ..., 1) .

3. W is defined on the edges of the network:

W ij = 0 only if i = j or (i, j) ∈ E.
This procedure, known as gossip algorithm [START_REF] Boyd | Randomized gossip algorithms[END_REF], is a standard method for averaging values across a network when its connectivity may vary through time. This approach was shown to be robust against machine failures, non-uniform latencies and asynchronous or time-varying graphs, and a large body of literature extended this algorithm to distributed optimization [START_REF] Nedic | Distributed subgradient methods for multi-agent optimization[END_REF]Duchi et al., 2012a;[START_REF] Wei | Distributed alternating direction method of multipliers[END_REF][START_REF] Shi | EXTRA: An exact first-order algorithm for decentralized consensus optimization[END_REF][START_REF] Jakovetić | Linear convergence rate of a class of distributed augmented lagrangian algorithms[END_REF][START_REF] Nedic | Achieving geometric convergence for distributed optimization over time-varying graphs[END_REF][START_REF] Mokhtari | DSA: Decentralized double stochastic averaging gradient algorithm[END_REF]. Note that these assumptions are implied by symmetry, stochasticity and positive eigengap on I -W . The convergence analysis of decentralized algorithms usually relies on the spectrum of the gossip matrix W used for communicating values in the network, and more specifically on the ratio between the second smallest and the largest eigenvalue of W , denoted γ(W ) = λ n-1 (W )/λ 1 (W ) and sometimes called normalized eigengap. More precisely, our lower bounds on the optimal convergence rate are obtained by replacing the diameter of the network with the quantity ∆ = 1/ γ(W ), that we refer to as the mixing time due to its relation to the mixing time of random walks when W is the Laplacian matrix of the communication network.

To ease the presentation of this section, and contrary to Section 3, we first present the lower bounds for decentralized optimization in Section 4.1, before describing the corresponding optimal algorithms in Section 4.2.

Remark 13 When communication is asymmetric, or the assumptions on the gossip matrix do not hold, traditional gossip methods fail and more advanced communication methods are required. We refer the reader to [START_REF] Nedic | Distributed optimization over time-varying directed graphs[END_REF]; [START_REF] Xi | Dextra: A fast algorithm for optimization over directed graphs[END_REF]; Nedic and Olshevsky (2016); Nedic et al. (2016) for asymmetric decentralized optimization algorithms.

Optimal Convergence Rates

The following results provide oracle complexity lower bounds for decentralized algorithms, and are proved in Appendix C. Similarly to Section 3.2, we consider that the dimension d is larger than both the number of communication and computation steps. This assumption is relatively standard in non-smooth optimization (Nesterov, 2004, Theorem 3.2.1) and valid for either small times or large dimensional problems. When the number of iterations is larger than the dimension d, linearly convergent algorithms exist even for convex nonsmooth problems [START_REF] Bubeck | Convex optimization: Algorithms and complexity[END_REF].

Non-Smooth Objective Functions

Theorem 14 Let L , R > 0 and ∆ ≥ 1. There exists a matrix W of mixing time ∆, and n convex and L i -Lipschitz functions f i , where n is the size of W , such that for all t < d-2 2 min(1, ∆τ ) and all i ∈ 1, n ,

f (θ i,t ) -min θ∈B 2 (R) f (θ) ≥ RL 108 1 1 + 2t ∆τ 2 + 1 1 + t , where L = 1 n i L 2 i .
Assuming that the dimension d is large compared to the characteristic values of the problem (i.e., d > 2 + 2 max{t, t/ ∆τ }), Theorem 14 implies that, under local Lipschitz continuity and for a gossip matrix W with mixing time ∆, the time to reach a precision ε > 0 with any decentralized black-box procedure is lower-bounded by

Ω RL ε 2 + RL ε ∆τ .
Theorem 15 Let L , α > 0 and ∆ ≥ 1. There exists a matrix W of size n and mixing time ∆, a convex set Θ ⊂ R d and n α i -strongly convex and L i -Lipschitz functions f i : Θ → R, such that for all t < d-2 2 min(1, ∆τ ) and all i ∈ 1, n ,

f (θ i,t ) -min θ∈Θ f (θ) ≥ L 2 648α 1 1 + 2t ∆τ 2 + 1 1 + t ,
where α = min i α i and L = 1

n i L 2 i .
Assuming that the dimension d is large compared to the characteristic values of the problem (i.e., d > 2+2 max{t, t/ ∆τ }), Theorem 15 implies that, under local strong convexity and Lipschitz continuity, and for a gossip matrix W with mixing time ∆, the time to reach a precision ε > 0 with any decentralized black-box procedure is lower-bounded by

Ω L 2 α ε + L 2 α ε ∆τ .
The proof of Theorem 14 relies on linear graphs (whose diameter is proportional to ∆ when the Laplacian matrix is used as gossip matrix) and Theorem 8. More specifically, a technical aspect of the proof consists in splitting the functions used in Theorem 8 on multiple nodes to obtain a dependency in L instead of L g . The complete derivation is available in Appendix C.1.

Smooth Objective Functions

The following theorems provide lower bounds for smooth centralized optimization. The first is a novel result of this work, while the second was first derived by Scaman et al. (2017, Theorem 2) and is included in this section for the sake of completeness.

Theorem 16 Let β > 0 and ∆ ≥ 1. There exists a matrix W of mixing time ∆, and n convex and β i -smooth functions f i , where n is the size of W , such that for all t ≤ 1 + d-3

2 (1 + ∆τ ) and all i ∈ 1, n ,

f (θ i,t ) -min θ∈R d f (θ) ≥ 3β θ i,0 -θ * 2 64 3(t-1) 3+ ∆τ + 1 2 ,
where θ * is a minimizer of f and β = max i β i .

Assuming that the dimension d is large compared to the characteristic values of the problem (i.e., d > 3 + 2(t -1)/(1 + ∆τ )), Theorem 16 implies that, under local smoothness, and for a gossip matrix W with mixing time ∆, the time to reach a precision ε > 0 with any decentralized black-box procedure is lower-bounded by

Ω β θ i,0 -θ * 2 ε 1 + ∆τ .
Theorem 17 Let α, β > 0 and ∆ ≥ 1. There exists a gossip matrix W of mixing time ∆, and α-strongly convex and β-smooth functions f i : 2 → R such that, for any t ≥ 0 and any black-box procedure using W one has, for all i ∈ 1, n ,

f (θ i,t ) -f (θ * ) ≥ α 2 1 - 16 √ κ 1+ 3t 3+ ∆τ θ i,0 -θ * 2 ,
where κ = β/α is the local condition number.

Assuming that the dimension d is large compared to the characteristic values of the problem (i.e., d max{t, t/ ∆τ }), Theorem 17 implies that, under local strong convexity and smoothness, and for a gossip matrix W with mixing time ∆, the time to reach a precision ε > 0 with any decentralized black-box procedure is lower-bounded by

Ω √ κ l ln 1 ε 1 + ∆τ .
The proofs of Theorem 16 and Theorem 17 rely on the same technique as that of Theorem 14 and Theorem 15. The complete proof is available in Appendix C.2.

We will see in the next section that this lower bound is met for a novel decentralized algorithm called multi-step primal-dual (MSPD) and based on the dual formulation of the optimization problem. Note that these results provide optimal convergence rates with respect to κ l and ∆, but do not imply that ∆ is the right quantity to consider on general graphs. The quantity ∆ may indeed be very large compared to ∆, for example for star networks, for which ∆ = 2 and ∆ = √ n. However, on many simple networks, the diameter ∆ and the eigengap of the Laplacian matrix are tightly connected, and ∆ ≈ ∆. For example, for linear graphs, ∆ = n -1 and ∆ ≈ 2n/π, for totally connected networks, ∆ = 1 and ∆ = 1, and for regular networks, ∆ ≥ ∆ 2 √ 2 ln 2 n [START_REF] Alon | λ 1 , isoperimetric inequalities for graphs, and superconcentrators[END_REF]. Finally, note that the case of totally connected networks corresponds to a previous complexity lower bound on communications proven by [START_REF] Arjevani | Communication complexity of distributed convex learning and optimization[END_REF], and is equivalent to our result for centralized algorithms with ∆ = 1.

Optimal Decentralized Algorithms

In this section, we present optimal algorithms for the decentralized setting.

Non-Smooth Objective Functions

We now provide an optimal decentralized optimization algorithm under (A2). This algorithm is closely related to the primal-dual algorithm proposed by [START_REF] Lan | Communication-efficient algorithms for decentralized and stochastic optimization[END_REF], which we modify by the use of accelerated gossip using Chebyshev polynomials as done by [START_REF] Scaman | Optimal algorithms for smooth and strongly convex distributed optimization in networks[END_REF].

First, following [START_REF] Jakovetić | Linear convergence rate of a class of distributed augmented lagrangian algorithms[END_REF], we formulate our optimization problem in Equation 1 as the saddle-point problem in Equation 11 below, by considering the equivalent problem of minimizing 1 n n i=1 f i (θ i ) over Θ = (θ 1 , . . . , θ n ) ∈ K n with the constraint that θ 1 = • • • = θ n , or equivalently ΘA = 0, where A is a square root of the symmetric matrix W . Through Lagrangian duality, we therefore get the equivalent problem:

min Θ∈K n max Λ∈R d×n 1 n n i=1 f i (θ i ) -tr Λ ΘA . ( 11
)
We solve it by applying the algorithm of [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF], which is both simple and well tailored to our problem-we could alternatively apply composite Mirror-Prox [START_REF] He | Mirror prox algorithm for multi-term composite minimization and semi-separable problems[END_REF]: (a) it is an accelerated method for saddle-point problems, (b) it allows for composite problems with a sum of non-smooth and smooth terms, (c) it provides a primaldual gap that can easily be extended to the case of approximate proximal operators. At each iteration t, with initialization Λ 0 = 0 and Θ 0 = Θ -1 = (θ 0 , . . . , θ 0 ):

(a) Λ t+1 = Λ t -σ(2Θ t -Θ t-1 )A (b) Θ t+1 = argmin Θ∈K n 1 n n i=1 f i (θ i ) -tr Θ Λ t+1 A + 1 2η tr(Θ -Θ t ) (Θ -Θ t ) ,
where the gain parameters η, σ are required to satisfy σηλ 1 (W ) ≤ 1. We implement the algorithm with the variables Θ t and Y t = Λ t A = (y t 1 , . . . , y t n ) ∈ R d×n , for which all updates Algorithm 3 multi-step primal-dual algorithm Input: approximation error ε > 0, gossip matrix

W ∈ R n×n , T = 2RL ∆ ε , M = 2RL ε ∆ , η = nR L ∆ , σ = 1 ηλ 1 (W ) . Output: optimizer θT 1: Θ 0 = 0, Θ -1 = 0, Y 0 = 0 2: for t = 0 to T -1 do 3: Y t+1 = Y t -σ(2Θ t -Θ t-1 )W 4: Θ0 = Θ t 5:
for m = 0 to M -1 do 6:

θm+1 i = m m+2 θm i -2 m+2 [ η n ∇f i ( θm i ) -ηy t+1 i -θ t i ], ∀i ∈ 1, n 7:
end for 8:

Θ t+1 = ΘM 9: end for 10: return θT = 1 T 1 n T t=1 n i=1 θ t i can be made locally: since AA = W , they now become (a ) Y t+1 = Y t -σ(2Θ t -Θ t-1 )W (b ) θ t+1 i = argmin θ i ∈K 1 n f i (θ i ) -θ i y t+1 i + 1 2η θ i -θ t i 2 , ∀i ∈ 1, n . (12)
The step (b ) still requires a proximal step for each function f i . We approximate it by the outcome of the subgradient method run for M steps, with a step-size proportional to 2/(m + 2) as suggested by [START_REF] Lacoste-Julien | A simpler approach to obtaining an O(1/t) convergence rate for the projected stochastic subgradient method[END_REF]. That is, initialized with θ0 i = θ t i , it performs the iterations

θm+1 i = m m + 2 θm i - 2 m + 2 η n ∇f i ( θm i ) -ηy t+1 i -θ t i , m = 0, . . . , M -1. ( 13
)
We thus replace the step (b ) by running M steps of the subgradient method to obtain θM i .

Theorem 18 Under local Lipschitz continuity, the approximation error with the iterative algorithm of Equation 12and 13 after T iterations and using M subgradient steps per iteration is bounded by

f ( θT ) -min θ∈K f (θ) ≤ RL ∆ T + 1 M ∆ .
Theorem 18 implies that the proposed algorithm achieves an error of at most ε in a time no larger than

O RL ε 2 + RL ε ∆τ , (14)
which is optimal due to Theorem 14. This algorithm, called multi-step primal-dual (MSPD), is described in Alg. 3.

Remark 19 It is clear from the algorithm's description that it completes its T iterations by time

T ε ≤ 2RL ∆ ε 2RL ε ∆ + 2RL ∆ ε τ . (15)
To obtain the average of local parameters θT = 1 nT T t=1 n i=1 θ i , one can then rely on accelerated gossip [START_REF] Auzinger | Iterative Solution of Large Linear Systems[END_REF][START_REF] Arioli | Chebyshev acceleration of iterative refinement[END_REF] to average over the network the individual nodes' time averages. This leads to a time O( ln ( RL ε ) ∆τ ) to ensure that each node reaches a precision ε on the objective function (see [START_REF] Boyd | Randomized gossip algorithms[END_REF], for more details on the linear convergence of gossip), which is negligible compared to Equation 14.

Remark 20 A stochastic version of the algorithm is also possible by considering stochastic oracles on each f i and using stochastic subgradient descent instead of the subgradient method.

Remark 21 In the more general context where node compute times ρ i are not necessarily all equal to 1, we may still apply Alg. 3, where now the number of subgradient iterations performed by node i is M/ρ i rather than M . The proof of Theorem 18 also applies, and now yields the modified upper bound on time to reach precision ε:

O RL c ε 2 + RL ε ∆τ , (16)
where

L 2 c = 1 n n i=1 ρ i L 2 i .

Other Regularity Assumptions

While this primal-dual approach could in theory be applied to all remaining three settings (strongly convex, smooth, and both strongly convex and smooth), the convergence rates of the Chambolle-Pock algorithm are weaker in such settings, and lead to convergence rates with respect to the distance to the optimum in squared norm θ t -θ * 2 (see [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF], Theorems 2 and 3). These issues could be avoided using the stronger results of composite Mirror-Prox [START_REF] He | Mirror prox algorithm for multi-term composite minimization and semi-separable problems[END_REF], but would require substantial modifications to the algorithm. Fortunately, these cases were recently investigated by [START_REF] Dvinskikh | Decentralized and Parallelized Primal and Dual Accelerated Methods for Stochastic Convex Programming Problems[END_REF], who designed optimal algorithms up to logarithmic factors for each decentralized communication setting (R-Sliding for strongly convex objectives and PSTM for smooth objectives). We thus refer to their work for the remaining cases.

Conclusion

In this paper, we provide optimal convergence rates for convex distributed optimization for two communication schemes (centralized and decentralized) and under four regularity assumptions on the objective function: Lipschitz continuity, strong convexity, smoothness, and both strong convexity and smoothness. Under decentralized communication, we provide optimal convergence rates that depend on the local regularity characteristics and mixing time of the gossip matrix. Moreover, we also provide the first optimal decentralized algorithm, called multi-step primal-dual (MSPD).

Under centralized communication, we first show that the naïve distribution of accelerated gradient descent is optimal for smooth functions. Then, we provide lower complexity bounds for non-smooth functions that depends on the (global) characteristics of the objective function, as well as a distributed version of the smoothing approach of Duchi et al. (2012b) and show that this algorithm is within a d 1/4 multiplicative factor of the optimal convergence rate.

In both settings, the optimal convergence rate for non-smooth distributed optimization exhibits two different speeds: a slow rate in Θ(1/ √ t) with respect to local computations and a fast rate in Θ(1/t) due to communication. Intuitively, communication is the limiting factor in the initial phase of optimization. However, its impact decreases with time and, for the final phase of optimization, local computation time is the main limiting factor.

The analysis presented in this paper allows several natural extensions, including timevarying communication networks, asynchronous algorithms, in the line of Hendrikx et al. (2019b), stochastic settings (see, e.g., Hendrikx et al., 2019a;[START_REF] Stich | Local SGD converges fast and communicates little[END_REF], and an analysis of unequal node compute speeds going beyond Remark 21. Moreover, despite the efficiency of DRS, finding an optimal algorithm under the global regularity assumption remains an open problem and would make a notable addition to this work.

where Appendix B. Proof of the Centralized Lower Bounds (Theorems 8, 9, 11 and 12)

c d,ε = d 1/4 log 8( f (θ 0 )-f (θ * )) ε . Since f γ is an L g γ √ d-
The proofs of lower bounds all rely on the fact that, for well-chosen local functions, most of the coordinates of the vectors in the memory of any node will remain equal to 0.

Definition 22 Let G = (V, E) be a graph of n nodes, I 0 , I 1 ⊂ V and x nz = max{k ∈ N : x k = 0} the largest non-zero coordinate of x. Local functions (f i ) i∈ 1,n are called (I 0 , I 1 )-zero preserving if, for all x ∈ R d and i ∈ 1, n ,

∇f i (x) nz ≤          x nz + 1{ x nz ≡ 0 mod 2} if i ∈ I 0 , x nz + 1{ x nz ≡ 1 mod 2} if i ∈ I 1 ,
x nz otherwise.

In other words, local gradients can only increase even dimensions for nodes in I 0 and odd dimensions for nodes in I 1 . With such objective functions, information needs to travel from I 0 to I 1 at each iteration in order to increase the number of non-zero coordinates.

Lemma 23 Let G = (V, E) be a graph of n nodes, I 0 , I 1 ⊂ V and k i,t = max{k ∈ N : ∃θ ∈ M i,t s.t. θ k = 0} be the last non-zero coordinate of a vector in the memory of node i at time t. If the local functions are (I 0 , I 1 )-zero preserving, then

∀i ∈ V, k i,t ≤ t -1 1 + d(I 0 , I 1 )τ + 1 , (17)
where d(I 0 , I 1 ) is the shortest-path distance between I 0 and I 1 in G.

Proof Since the local functions are zero preserving, we have, under any black-box procedure and for any local computation step,

k i,t+1 ≤          k i,t + 1{k i,t ≡ 0 mod 2} if i ∈ I 0 , k i,t + 1{k i,t ≡ 1 mod 2} if i ∈ I 1 , k i,t otherwise.
Thus, in order to reach the third coordinate, algorithms must first perform one local computation in I 0 , then d(I 0 , I 1 ) communication steps in order for a node in I 1 to have a non-zero second coordinate, and finally, one local computation in I 1 . Accordingly, one must perform at least k local computation steps and (k -1)d(I 0 , I 1 ) communication steps to achieve k i,t ≥ k for at least one node i ∈ V, and thus, for any k ∈ N * ,

∀t < 1 + (k -1)(1 + d(I 0 , I 1 )τ ), k i,t ≤ k -1 ,
which leads to the desired result.

B.1. Non-Smooth Lower Bounds

Let i 0 ∈ V and i 1 ∈ V be two nodes at distance ∆. Following [START_REF] Nesterov | Introductory Lectures on Convex Optimization : a Basic Course[END_REF], the function used by [START_REF] Bubeck | Convex optimization: Algorithms and complexity[END_REF] to prove the oracle complexity for non-smooth convex functions is

g 1 (θ) = δ max i∈ 1,t θ i + α 2 θ 2 2 .
By considering this function on a single node (e.g. i 0 ), at least O RL ε 2 subgradients will be necessary to obtain a precision ε. Moreover, we also split the difficult function used by [START_REF] Arjevani | Communication complexity of distributed convex learning and optimization[END_REF] g

2 (θ) = γ t i=1 |θ i+1 -θ i | -βθ 1 + α 2 θ 2 2 ,
on the two extremal nodes i 0 and i 1 in order to ensure that communication is necessary between the most distant nodes of the network. The final function that we consider is, for all j ∈ 1, n ,

f j (θ) =          α 2 θ 2 2 + n γ k i=1 |θ 2i+1 -θ 2i | -βθ 1 if j = i 0 , α 2 θ 2 2 + n γ k i=1 |θ 2i -θ 2i-1 | + δ max i∈ 2k+2,2k+1+l θ i if j = i 1 , α 2 θ 2 2 otherwise, (18)
where γ, δ, β, α > 0 and k, l ≥ 0 are parameters of the function satisfying 2k + l < d. The objective function is thus

f (θ) = γ 2k i=1 |θ i+1 -θ i | -βθ 1 + δ max i∈ 2k+2,2k+1+l θ i + α 2 θ 2 2 .
First, note that reordering the coordinates of θ between θ 2 and θ 2k+1 in a decreasing order can only decrease the value function f (θ). Hence, the optimal value θ * verifies this constraint and f (θ

* ) = -γθ * 2k+1 -(β -γ)θ * 1 + δ max i∈ 2k+2,2k+1+l θ * i + α 2 θ * 2 2 .
Moreover, at the optimum, all the coordinates between θ 2 and θ 2k+1 are equal, all the coordinates between θ 2k+2 and θ 2k+1+l are also equal, and all the coordinates after θ 2k+1+l are zero. Hence

f (θ * ) = -γθ * 2k+1 -(β -γ)θ * 1 + δθ * 2k+2 + α 2 θ * 1 2 + 2kθ * 2k+1 2 + lθ * 2k+2 2 ,
and optimizing over θ

* 1 ≥ θ * 2k+1 ≥ 0 ≥ θ * 2k+2 leads to, when β ≥ γ(1 + 1 2k ), f (θ * ) = -1 2α (β -γ) 2 + γ 2 2k + δ 2 l .
Now note that the objective function is the sum of two functions, one function on (θ 1 , ..., θ 2k+1 ) that is (i 0 , i 1 )-zero preserving, and another function on (θ 2k+2 , ..., θ 2k+1+l ) that is (i 1 , i 1 )zero preserving. As a result, Lemma 23 implies that, if l > t -1 + 1, we have θ t,2k+1+l = 0 and thus max i∈ 2k+2,2k+1+l θ t,i ≥ 0 .

Moreover, if 2k + 1 > t-1 1+∆τ + 1, then θ t,2k+1 = 0, and thus

f (θ t ) ≥ min θ∈R d -(β -γ)θ 1 + α 2 θ 2 2 ≥ -(β-γ) 2 2α
.

Hence, we have,

f (θ t ) -f (θ * ) ≥ 1 2α γ 2 2k + δ 2 l .
Optimizing f over a ball of radius R ≥ θ * 2 thus leads to the previous approximation error bound, and we choose

R 2 = θ * 2 2 = 1 α 2 (β -γ) 2 + γ 2 2k + δ 2 l .
Finally, the Lipschitz constant of the objective function f on a ball of radius R is

L g = β + 2 √ 2k + 1γ + δ + αR,
and setting the parameters of f to

β = γ(1 + 1 √ 2k ), δ = Lg 9 , γ = Lg 9 √ k , l = t + 1, and k = t 2∆τ + 1 leads to l > t -1 + 1 and 2k + 1 > t-1 1+∆τ + 1, and f (θ t ) -f (θ * ) ≥ RL g 36 1 (1 + t 2∆τ ) 2 + 1 1 + t ,
while f is L g -Lipschitz and θ * 2 ≤ R. Moreover, f is α-strongly convex and rewriting the radius R is terms of α g = α and L g gives

R = L g 3α g 1 k 2 + 1 l , and thus f (θ t ) -f (θ * ) ≥ L 2 g 108α 1 (1 + t 2∆τ ) 2 + 1 1 + t .

B.2. Smooth Lower Bounds

Both proofs of smooth lower bounds rely on splitting the function used by Nesterov to prove oracle complexities for smooth optimization [START_REF] Nesterov | Introductory Lectures on Convex Optimization : a Basic Course[END_REF][START_REF] Bubeck | Convex optimization: Algorithms and complexity[END_REF].

B.2.1. Convex and Smooth Case

Let β > 0, G = (V, E) a graph and i 0 ∈ V and i 1 ∈ V two nodes at distance ∆. Let, for all j ∈ V, f j : R d → R be the functions defined as:

f j (θ) =          nβ 8 k i=1 (θ 2i+1 -θ 2i ) 2 + θ 2 1 -2θ 1 if j = i 0 nβ 8 k i=1 (θ 2i -θ 2i-1 ) 2 + θ 2 2k+1 if j = i 1 0 otherwise , (19)
where k ∈ N is a parameter of the function. The objective function is thus 2k+1) is a tridiagonal matrix with 2 on the diagonal and -1 on the upper and lower diagonals. A simple calculation shows that 0 M 4I, and thus f is β-smooth. The optimum of f is obtained for θ * i = 1 -i 2k+2 , and

f (θ) = β 8 2k i=1 (θ i+1 -θ i ) 2 + θ 2 1 + θ 2 2k+1 -2θ 1 . First, note that ∇ f (θ) = β 8 (M θ -2e 1 ) where M = M 0 0 0 and M ∈ R (2k+1)×(
f (θ * ) = - β 8 1 - 1 2k + 2 .
Moreover, since the local functions are (i 0 , i 1 )-zero preserving, Lemma 23 implies that, for all i > k t = t-1 1+∆τ + 1, one has θ t,i = 0, and thus

f (θ t ) ≥ - β 8 1 - 1 k t + 1 . Choosing k = k t directly implies f (θ t ) -f (θ * ) ≥ β 16(k t + 1) ≥ β 16 t-1 1+∆τ + 2 . Finally, noting that θ 0 -θ * 2 = θ * 2 ≤ 2(k+1)
3 leads to the desired result.

B.2.2. Strongly Convex and Smooth Case

Let β ≥ α > 0, G = (V, E) a graph and i 0 ∈ V and i 1 ∈ V two nodes at distance ∆. Let, for all j ∈ V, f j : 2 → R be the functions defined as:

f j (θ) =          α 2 θ 2 2 + n β-α 8 (θ M 1 θ -2θ 1 ) if j = i 0 , α 2 θ 2 2 + n β-α 8 θ M 2 θ if j = i 1 , α 2 θ 2 2 otherwise, (20)
where M 2 : 2 → 2 is the infinite block diagonal matrix with 1 -1 -1 1 on the diagonal,

and

M 1 = 1 0 0 M 2 . First, note that, since 0 M 1 + M 2 4I, f = 1 n n i=1 f i is
α-strongly convex and β-smooth. Since the local functions are (i 0 , i 1 )-zero preserving, Lemma 23 implies that, for all i > k t = t-1 1+∆τ + 1, one has θ t,i = 0, and thus

θ t -θ * 2 2 ≥ +∞ i=kt+1 θ * i 2 . ( 21
)
Since f is α-strongly convex, we also have

f (θ t ) -f (θ * ) ≥ α 2 θ t -θ * 2 2 . (22)
Finally, the solution of the global problem min

θ f (θ) is θ * i = √ β- √ α √ β+ √ α i
. Combining this result with Equations 17, 21 and 22 leads to the desired inequality.

Proof Let γ = 1/ ∆ 2 be the (desired) eigengap of the gossip matrix. First of all, when γ ≥ 1/3, we consider the totally connected network of 3 nodes, reweight only the edge (v 1 , v 3 ) by a ∈ [0, 1], and let W a be its Laplacian matrix. If a = 1, then the network is totally connected and γ(W a ) = 1. If, on the contrary, a = 0, then the network is a linear graph and γ(W a ) = 1/3. Thus, by continuity of the eigenvalues of a matrix, there exists a value a ∈ [0, 1] such that γ(W a ) = γ and Equation 23 is trivially verified. Otherwise, let x n = 1-cos( π n ) 1+cos( π n ) be a decreasing sequence of positive numbers. Since x 3 = 1/3 and lim n x n = 0, there exists n ≥ 3 such that x n ≥ γ > x n+1 . Let G be the linear graph of size n ordered from node v 1 to v n , and weighted with w i,i+1 = 1 -a1{i = 1}. If we take W a as the Laplacian of the weighted graph G, a simple calculation gives that, if a = 0, γ(W a ) = x n and, if a = 1, the network is disconnected and γ(W a ) = 0. Thus, there exists a value a ∈ [0, 1] such that γ(W a ) = γ. By definition of n, one has

γ > x n+1 ≥ 2 (n + 1) 2 . ( 24
)
We now consider I 0 = 1, m and I 1 = n -m + 1, n where m = n+1 3 . When γ < 1/3, G is linear and the distance d(I 0 , I 1 ) between the two sets I 0 and I 1 is thus bounded by

d(I 0 , I 1 ) = n -2m + 1 ≥ n + 1 3 ,
and using Equation 24 leads to the desired inequality. For γ ≥ 1/3, G is a triangle and Equation 23 also trivially holds. Finally, since, for all γ ∈ (0, 1], n ≥ 3, we have m = n+1 3 ≥ n 4 .

Since all centralized lower bounds depend on splitting the objective function f (θ) = f 1 (θ)+f 2 (θ) 2 on two nodes at distance ∆, Lemma 24 allows to replace ∆ by √ 2 3 ∆. Finally, all lower bounds are obtained by splitting the functions f 1 and f 2 on all I 0 and I 1 nodes, respectively, in order to decrease local regularity characteristics.

C.1. Non-Smooth Lower Bounds

We now consider the local functions of Equation 18 split on I 0 and I 1 of Lemma 24:

f j (θ) =          α 2 θ 2 2 + n m γ k i=1 |θ 2i -θ 2i-1 | + δ max i∈ 2k+2,2k+1+l θ i if j ∈ I 0 , α 2 θ 2 2 + n m γ k i=1 |θ 2i+1 -θ 2i | -βθ 1 if j ∈ I 1 , α 2 θ 2 2 otherwise.
The average function f remains unchanged and the time to communicate a vector between a node of I 0 and a node of I 1 is at least d(I 0 , I 1 )τ . Thus, the same result as Theorem 8 holds with ∆ = d(I 0 , I 1 ). Moreover, α = α = α g and, since m ≥ n/4, the local Lipschitz constant L is bounded by

L ≤ 2n m L g ≤ 3L g .
Replacing L g , α g and ∆ by, respectively, L /3, α and √ 2 3 ∆ in Equation 7and Equation 8 leads to the desired result.

C.2. Smooth Lower Bounds

For the smooth and convex setting, we consider the local functions of Equation 19 split on I 0 and I 1 of Lemma 24:

f j (θ) =          nβ 8m k i=1 (θ 2i+1 -θ 2i ) 2 + θ 2 1 -2θ 1 if j ∈ I 0 , nβ 8m k i=1 (θ 2i -θ 2i-1 ) 2 + θ 2 2k+1 if j ∈ I 1 , 0 otherwise.
The average function f remains unchanged and the time to communicate a vector between a node of I 0 and a node of I 1 is at least d(I 0 , I 1 )τ . Thus, the same result as Theorem 11 holds with ∆ = d(I 0 , I 1 ). Moreover, since m ≥ n/4, the local smoothness β is bounded by

β = max i β i = n 2m β g ≤ 2β g .
Replacing β g and ∆ by, respectively, β /2 and √ 2 3 ∆ in Equation 9 leads to the desired result. For the smooth and strongly convex setting, we consider the local functions of Equation 20 split on I 0 and I 1 of Lemma 24:

f j (θ) =          α 2 θ 2 2 + n m β-α 8 (θ M 1 θ -2θ 1 ) if j ∈ I 0 , α 2 θ 2 2 + n m β-α 8 θ M 2 θ if j ∈ I 1 , α 2 θ 2 2 otherwise.
The average function f remains unchanged and the time to communicate a vector between a node of I 0 and a node of I 1 is at least d(I 0 , I 1 )τ . Thus, the same result as Theorem 12 holds with ∆ = d(I 0 , I 1 ). Moreover, α = α = α g and, since m ≥ n/4, the local condition number κ is bounded by

κ = max i β i min i α i = α + n 2m (β -α) α ≤ 2κ g -1 .
Replacing κ g and ∆ by, respectively, κ /2 and √ 2 3 ∆ in Equation 10 leads to the desired result.

Appendix D. Proof of the Convergence Rate of MSPD (Theorem 18)

Theorem 1 (b) in [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF] implies that, provided τ σλ 1 (W ) < 1, the algorithm with exact proximal step leads to a restricted primal-dual gap sup

Λ F ≤c 1 n n i=1 f i (θ i ) -tr Λ ΘA -inf Θ ∈K n 1 n n i=1 f i (θ i ) -tr Λ Θ A of ε = 1 2t nR 2 η + c 2 σ .
This implies that our candidate Θ is such that

1 n n i=1 f i (θ i ) + c ΘA F ≤ inf Θ ∈K n 1 n n i=1 f i (θ i ) + c Θ A F + ε .
Let θ be the average of all θ i . We have:

1 n n i=1 f i (θ) ≤ 1 n n i=1 f i (θ i ) + 1 n n i=1 L i θ i -θ ≤ 1 n n i=1 f i (θ i ) + 1 √ n 1 n n i=1 L 2 i • Θ(I -11 /n) F ≤ 1 n n i=1 f i (θ i ) + 1 √ n 1 n n i=1 L 2 i λ n-1 (W ) • ΘA F .
Thus, if we take c = 1 W ) , we obtain

√ n 1 n n i=1 L 2 i λ n-1 (
1 n n i=1 f i (θ) ≤ 1 n n i=1 f i (θ * ) + ε,
and we thus obtain an ε-minimizer of the original problem. We have

ε ≤ 1 2T nR 2 η + 1 λ n-1 (W ) 1 n 2 n i=1 L 2 i σ
with the constraint σηλ 1 (W ) < 1. This leads to, with the choice η = nR λ n-1 (W )/λ 1 (W ) n i=1 L 2 i /n and taking σ to the limit σηλ 1 (W ) = 1, to a convergence rate of

ε = 1 T R 1 n n i=1 L 2 i λ 1 (W ) λ n-1 (W ) .
Since we cannot use the exact proximal operator of f i , we instead approximate it. If we approximate (with the proper notion of gap (Chambolle and Pock, 2011, Eq. (11))) each argmin θ i ∈K f i (θ i ) + n 2η θ i -z 2 up to δ i , then the overall added gap is 1 n n i=1 δ i . If we do M steps of subgradient descent then the associated gap is δ i = L 2 i η nM (standard result for strongly convex subgradient [START_REF] Lacoste-Julien | A simpler approach to obtaining an O(1/t) convergence rate for the projected stochastic subgradient method[END_REF]). Therefore the added gap is

1 M R 1 n n i=1 L 2 i λ n-1 (W ) λ 1 (W ) .
Therefore after T communication steps, i.e., communication time T τ plus M T subgradient evaluations, i.e., time M T , we get an error of

∆ T + 1 M ∆ RL ,
where ∆ = 1/ γ(W ) = λ 1 (W )/λ n-1 (W ). Thus to reach ε, it takes

2RL ∆ ε 2RL ε ∆ + 2RL ∆ ε τ ,
which leads to the desired result.

  approximation of f (see Lemma 1), setting γ = ε 2Lg √ d leads to a precision ε on f after n ε iterations. Finally, each iteration takes a time n ε (K + 2∆τ ), and setting K =

  ;

	Setting			Lower bound		Upper bound	Algorithm
	Lipschitz continuity + convexity
	Centr.	Ω		LgR ε	2	+	LgR ε ∆τ	O	LgR ε	2	+	LgR ε ∆τ d 1/4	DRS (Alg. 1)
	Decentr. Ω		L R ε	2	+ L R ε ∆τ		matching lower bound	MSPD (Alg. 3)
	Lipschitz continuity + strong convexity
	Centr.	Ω	L 2 g αgε +		L 2 g αgε ∆τ	O	L 2 g αgε +	L 2 g αgε ∆τ d 1/4 log 1 ε	DRS (Alg. 2)
	Decentr.	Ω	L 2 α ε +		L 2 α ε ∆τ		matching lower bound 1	R-Sliding 1
	Smoothness + convexity
	Centr.	Ω R	βg ε (1 + ∆τ )		matching lower bound	AGD
	Decentr.	Ω R β ε (1 + ∆τ )		matching lower bound 1	PSTM 1
	Smoothness + strong convexity
	Centr.	Ω	√ κ g ln 1 ε (1 + ∆τ )		matching lower bound	AGD
	Decentr. Ω	√ κ ln 1 ε (1 + ∆τ )		matching lower bound 1	PSTM 1

The lower bounds for decentralized communication for strongly convex, smooth, and both strongly convex and smooth settings, are met up to logarithmic factors using the PSTM and R-Sliding algorithms of[START_REF] Dvinskikh | Decentralized and Parallelized Primal and Dual Accelerated Methods for Stochastic Convex Programming Problems[END_REF].

Acknowledgments

We acknowledge support from the European Research Council (grant SEQUOIA 724063).

Appendix A. Proof of the Convergence Rate of DRS (Theorems 2 and 6) In this appendix, we provide detailed proofs of Theorems 2 and 6, that is, for the convex and strongly-convex cases.

A.1. Convex Case

Corollary 2.4 of Duchi et al. (2012b) gives, with the appropriate choice of gradient step η t and smoothing γ t ,

Thus, to reach a precision ε > 0, we may set T =

, leading to the desired bound on the time T ε = T (2∆τ + K) to reach ε.

A.2. Strongly Convex Case

Using Corollary 3.9 of Serhat [START_REF] Serhat Aybat | A Universally Optimal Multistage Accelerated Stochastic Gradient Method[END_REF] to optimize f γ , the number of iterations n ε to reach a precision ε/2 is bounded by

Appendix C. Proof of Decentralized Lower Bounds (Theorems 14, 15, 16 and 17)

Lower bounds for decentralized optimization are proved using the centralized setting on linear graphs and splitting the worst-case objective functions on multiple nodes. This allows to have both local characteristics approximately equal to global characteristics (i.e., L ≈ L g , α ≈ α g , β ≈ β g and κ ≈ κ g ) and the mixing time approximately equal to the diameter of the graph.

Lemma 24 Let ∆ ≥ 1. There exists a graph G = (V, E) of size n and a gossip matrix W ∈ R n×n on this graph such that its mixing time is ∆. Moreover, there exists two subsets of nodes I 0 , I 1 ⊂ V of size |I 0 | = |I 1 | ≥ n/4 and such that

where d(I 0 , I 1 ) is the shortest-path distance in G between the two sets.