Hadrien Hendrikx
email: hadrien.hendrikx@inria.fr

Francis Bach
email: francis.bach@inria.fr

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

Dual-Free Stochastic Decentralized Optimization with Variance Reduction

We consider the problem of training machine learning models on distributed data in a decentralized way. For finite-sum problems, fast single-machine algorithms for large datasets rely on stochastic updates combined with variance reduction. Yet, existing decentralized stochastic algorithms either do not obtain the full speedup allowed by stochastic updates, or require oracles that are more expensive than regular gradients. In this work, we introduce a Decentralized stochastic algorithm with Variance Reduction called DVR. DVR only requires computing stochastic gradients of the local functions, and is computationally as fast as a standard stochastic variance-reduced algorithms run on a 1/n fraction of the dataset, where n is the number of nodes. To derive DVR, we use Bregman coordinate descent on a well-chosen dual problem, and obtain a dual-free algorithm using a specific Bregman divergence. We give an accelerated version of DVR based on the Catalyst framework, and illustrate its effectiveness with simulations on real data.

Introduction

We consider the regularized empirical risk minimization problem distributed on a network of n nodes. Each node has a local dataset of size m, and the problem thus writes:

min x∈R d F (x) n i=1 f i (x), with f i (x) σ i 2 x 2 + m j=1 f ij (x), (1)
where f ij typically corresponds to the loss function for training example j of machine i, and σ i is the local regularization parameter for node i. We assume that each function f ij is convex and L ij -smooth (see, e.g., [START_REF] Nesterov | Introductory Lectures on Convex Optimization: A Basic Course[END_REF]), and that each function f i is M i -smooth. Following [START_REF] Xiao | DSCOVR: Randomized primal-dual block coordinate algorithms for asynchronous distributed optimization[END_REF], we denote κ i = (1 + m i=1 L ij )/σ i the stochastic condition number of f i , and κ s = max i κ i . Similarly, the batch condition number is κ b = max i M i /σ i . It always holds that κ b ≤ κ s ≤ mκ b , but generally κ s mκ b , which explains the success of stochastic methods. Indeed, κ s ≈ mκ b when all Hessians are orthogonal to one another which is rarely the case in practice, especially for a large dataset.

Regarding the distributed aspect, we follow the standard gossip framework [START_REF] Boyd | Randomized gossip algorithms[END_REF][START_REF] Nedic | Distributed subgradient methods for multi-agent optimization[END_REF][START_REF] Duchi | Dual averaging for distributed optimization: Convergence analysis and network scaling[END_REF][START_REF] Scaman | Optimal algorithms for smooth and strongly convex distributed optimization in networks[END_REF] and assume that nodes are linked by a communication network which we represent as an undirected graph G. We denote N (i) the set of neighbors of node i and 1 ∈ R d the vector with all coordinates equal to 1. Communication is abstracted by multiplication by a positive semi-definite matrix W ∈ R n×n , which is such that W k = 0 if k / ∈ N ( ), and Ker(W ) = Span [START_REF] Heinz | A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications[END_REF]. The matrix W is called the gossip matrix, and we denote its spectral gap by γ = λ + min (W )/λ max (W ), the ratio between the smallest 34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada.

non-zero and the highest eigenvalue of W , which is a key quantity in decentralized optimization.

We finally assume that nodes can compute a local stochastic gradient ∇f ij in time 1, and that communication (i.e., multiplication by W ) takes time τ .

Single-machine stochastic methods. Problem (1) is generally solved using first-order methods. When m is large, computing ∇F becomes very expensive, and batch methods require O(κ b log(ε -1 )) iterations, which takes time O(mκ b log(ε -1 )), to minimize F up to precision ε. In this case, updates using the stochastic gradients ∇f ij , where (i, j) is selected randomly, can be much more effective [START_REF] Bottou | Large-scale machine learning with stochastic gradient descent[END_REF].

Yet, these updates are noisy and plain stochastic gradient descent (SGD) does not converge to the exact solution unless the step-size goes to zero, which slows down the algorithm. One way to fix this problem is to use variance-reduced methods such as SAG [START_REF] Schmidt | Minimizing finite sums with the stochastic average gradient[END_REF], SDCA [START_REF] Shalev | Stochastic dual coordinate ascent methods for regularized loss minimization[END_REF], SVRG [START_REF] Johnson | Accelerating stochastic gradient descent using predictive variance reduction[END_REF] or SAGA [START_REF] Defazio | SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives[END_REF]. These methods require O((nm + κ s ) log(ε -1 )) stochastic gradient evaluations, which can be much smaller than O(mκ b log(ε -1 )).

Decentralized methods. Decentralized adaptations of gradient descent in the smooth and strongly convex setting include EXTRA [START_REF] Shi | Extra: An exact first-order algorithm for decentralized consensus optimization[END_REF], DIGing [START_REF] Nedic | Achieving geometric convergence for distributed optimization over time-varying graphs[END_REF] or NIDS [START_REF] Li | A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates[END_REF]. These algorithms have sparked a lot of interest, and the latest convergence results [START_REF] Jakovetić | A unification and generalization of exact distributed first-order methods[END_REF][START_REF] Xu | Distributed algorithms for composite optimization: Unified and tight convergence analysis[END_REF][START_REF] Li | Revisiting EXTRA for smooth distributed optimization[END_REF] show that EXTRA and NIDS require time O((κ b + γ -1 )(m + τ )) log(ε -1 )) to reach precision ε. A generic acceleration of EXTRA using Catalyst [START_REF] Li | Revisiting EXTRA for smooth distributed optimization[END_REF] obtains the (batch) optimal O( √ κ b (1 + τ / √ γ) log(ε -1 )) rate up to log factors.

Another line of work on decentralized algorithms is based on the penalty method [START_REF] Li | A sharp convergence rate analysis for distributed accelerated gradient methods[END_REF][START_REF] Dvinskikh | Decentralized and parallelized primal and dual accelerated methods for stochastic convex programming problems[END_REF]. This consists in performing traditional optimization algorithms to problems augmented with a Laplacian penalty, and in particular enables the use of accelerated methods. Yet, these algorithms are sensitive to the value of the penalty parameter (when it is fixed), since it directly influences the solution they converge to. Another natural way to construct decentralized optimization algorithms is through dual approaches [START_REF] Scaman | Optimal algorithms for smooth and strongly convex distributed optimization in networks[END_REF][START_REF] César | A dual approach for optimal algorithms in distributed optimization over networks[END_REF]. Although the dual approach leads to algorithms that are optimal both in terms of number of communications and computations [START_REF] Scaman | Optimal convergence rates for convex distributed optimization in networks[END_REF][START_REF] Hendrikx | An optimal algorithm for decentralized finite sum optimization[END_REF], they generally assume access to the proximal operator or the gradient of the Fenchel conjugate of the local functions, which is not very practical in general since it requires solving a subproblem at each step.

Decentralized stochastic optimization. Although both stochastic and decentralized methods have a rich litterature, there exist few decentralized stochastic methods with linear convergence rate.

Although DSA [START_REF] Mokhtari | DSA: Decentralized double stochastic averaging gradient algorithm[END_REF], or GT-SAGA [START_REF] Xin | Decentralized stochastic optimization and machine learning: A unified variance-reduction framework for robust performance and fast convergence[END_REF] propose such algorithms, they respectively take time O((mκ s + κ 4 s γ -1 (1 + τ ) log(ε -1 )) and O((m + κ 2 s γ -2 )(1 + τ ) log(ε -1 )) to reach precision ε. Therefore, they have significantly worse rates than decentralized batch methods when m = 1, and than single-machine stochastic methods when n = 1. Other methods have better rates of convergence [START_REF] Shen | Towards more efficient stochastic decentralized learning: Faster convergence and sparse communication[END_REF][START_REF] Hendrikx | An accelerated decentralized stochastic proximal algorithm for finite sums[END_REF] but they require evaluation of proximal operators, which may be expensive.

Our contributions. This work develops a dual approach similar to that of [START_REF] Hendrikx | An accelerated decentralized stochastic proximal algorithm for finite sums[END_REF], which leads to a decentralized stochastic algorithm with rate O(m + κ s + τ κ b / √ γ), where the √ γ factor comes from Chebyshev acceleration, such as used in [START_REF] Scaman | Optimal algorithms for smooth and strongly convex distributed optimization in networks[END_REF]. Yet, our algorithm, called DVR, can be formulated in the primal only, thus avoiding the need for computing expensive dual gradients or proximal operators. Besides, DVR is derived by applying Bregman coordinate descent to the dual of a specific augmented problem. Thus, its convergence follows from the convergence of block coordinate descent with Bregman gradients, which we prove as a side contribution. When executed on a single-machine, DVR is similar to dual-free SDCA [START_REF] Shalev-Shwartz | SDCA without duality, regularization, and individual convexity[END_REF], and obtains similar rates. We believe that the same methodology could be applied to tackle non-convex problems, but we leave these extensions for future work.

We present in Section 2 the derivations leading to DVR, namely the dual approach and the dual-free trick. Then, Section 3 presents the actual algorithm along with a convergence theorem based on block Bregman coordinate descent (presented in Appendix A). Section 4 shows how to accelerate DVR, both in terms of network dependence (Chebyshev acceleration) and global iteration complexity (Catalyst acceleration [START_REF] Lin | Catalyst acceleration for first-order convex optimization: from theory to practice[END_REF]). Finally, experiments on real-world data are presented in Section 5, that demonstrate the effectiveness of DVR.

Algorithm Design

This section presents the key steps leading to DVR. We start by introducing a relevant dual formulation from [START_REF] Hendrikx | An accelerated decentralized stochastic proximal algorithm for finite sums[END_REF], then introduce the dual-free trick based on [START_REF] Lan | An optimal randomized incremental gradient method[END_REF], and finally show how this leads to DVR, an actual implementable decentralized stochastic algorithm, as a special case of the previous derivations.

Dual formulation

The standard dual formulation of Problem ( 1) is obtained by associating a parameter vector to each node, and imposing that two neighboring nodes have the same parameters [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF][START_REF] Jakovetić | Linear convergence rate of a class of distributed augmented Lagrangian algorithms[END_REF][START_REF] Scaman | Optimal algorithms for smooth and strongly convex distributed optimization in networks[END_REF]. This leads to the following constrained problem, in which we write θ (i) ∈ R d the local vector of node i:

min θ∈R nd n i=1 f i (θ (i) ) such that ∀k, ∈ N (k), θ (k) = θ ( ) . (2)
Following the approach of [START_REF] Hendrikx | An accelerated decentralized stochastic proximal algorithm for finite sums[END_REF][START_REF] Hendrikx | An optimal algorithm for decentralized finite sum optimization[END_REF], we further split the f i (θ

(i) ) term into σ i θ (i) 2 /2 + n j=1 f ij (θ (ij)
), with the constraint that θ (i) = θ (ij) for all j. This is equivalent to the previous approach performed on an augmented graph [START_REF] Hendrikx | An accelerated decentralized stochastic proximal algorithm for finite sums[END_REF][START_REF] Hendrikx | An optimal algorithm for decentralized finite sum optimization[END_REF] in which each node is split into a star network with the regularization in the center and a local summand at each tip of the star. Thus, the equivalent augmented constrained problem that we consider writes:

min θ∈R n(m+1)d n i=1   σ i 2 θ (i) 2 + m j=1 f ij (θ (ij) )   s.t. ∀k, ∈ N (k), θ (k) = θ ( ) and ∀i, j, θ (i) = θ (ij) .
(3) We now use Lagrangian duality, and introduce two kinds of multipliers. The variable x corresponds to multipliers associated with the constraints given by edges of the communication graph (i.e.,

θ (k) = θ ( ) if k ∈ N ( ))
, that we will call communication edges. Similarly, y corresponds to the constraints associated with the edges that are specific to the augmented graph (i.e., θ (i) = θ (ij) ∀i, j) that we call computation or virtual edges, since they are not present in the original graph and were constructed for the augmented problem. Therefore, there are E communication edges (number of edges in the initial graph), and nm virtual edges. The dual formulation of Problem (3) thus writes:

min x∈R Ed , y∈R nmd 1 2 q A (x, y) + n i=1 m j=1 f * ij ((A(x, y)) (ij) ), with q A (x, y) (x, y) A ΣA(x, y), (4)
and where (x, y) ∈ R (E+nm)d is the concatenation of vectors x ∈ R Ed , which is associated with the communication edges, and y ∈ R nmd , which is the vector associated with computation edges. We denote

Σ = Diag(σ -1 1 , • • • , σ -1 n , 0, • • • , 0) ⊗ I d ∈ R n(m+1)d×n(m+1)d and A is such that for all z ∈ R d , A(e k, ⊗ z) = µ k (u k -u ) ⊗ P k z for edge (k, ), where P k = I d if (k, ) is a communication edge, P ij is the projector on Ker(f ij ) ⊥ (∩ x∈R d Ker(∇ 2 f ij (x))) ⊥ if (i, j
) is a virtual edge, z 1 ⊗ z 2 is the Kronecker product of vectors z 1 and z 2 , and e k, ∈ R E+nm and u k ∈ R n(m+1) are the unit vectors associated with edge (k, ) and node k respectively. Note that the upper left nd × nd block of AA (corresponding to the communication edges) is equal to W ⊗ I d where W is a gossip matrix (see, e.g., [START_REF] Scaman | Optimal algorithms for smooth and strongly convex distributed optimization in networks[END_REF]) that depends on the µ k . In particular, W is equal to the Laplacian of the communication graph if µ 2 k = 1/2 for all (k, ). For computation edges, the projectors P ij account for the fact that the parameters θ (i) and θ (ij) only need to be equal on the subspaces on which f ij is not constant, and we choose µ ij such that µ 2 ij = αL ij for some α > 0. Although this introduces heavier notations, explicitly writing A as an n(1 + m)d × (E + nm)d matrix instead of an n(1 + m) × (E + nm) matrix allows to introduce the projectors P ij , which then yields a better communication complexity than choosing P ij = I d . See [START_REF] Hendrikx | An accelerated decentralized stochastic proximal algorithm for finite sums[END_REF][START_REF] Hendrikx | An optimal algorithm for decentralized finite sum optimization[END_REF] for more details on this dual formulation, and in particular on the construction on the augmented graph. Now that we have obtained a suitable dual problem, we would like to solve it without computing gradients or proximal operators of f * ij , which can be very expensive.

Dual-free trick

Dual methods are based on variants of Problem (4), and apply different algorithms to it. In particular, [START_REF] Scaman | Optimal algorithms for smooth and strongly convex distributed optimization in networks[END_REF][START_REF] César | A dual approach for optimal algorithms in distributed optimization over networks[END_REF] use accelerated gradient descent [START_REF] Nesterov | Introductory Lectures on Convex Optimization: A Basic Course[END_REF], and [START_REF] Hendrikx | Accelerated decentralized optimization with local updates for smooth and strongly convex objectives[END_REF][START_REF] Hendrikx | An accelerated decentralized stochastic proximal algorithm for finite sums[END_REF] use accelerated (proximal) coordinate descent [START_REF] Lin | An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization[END_REF]. Let p comm denote the probability of performing a communication step and p ij be the probability that node i samples a gradient of f ij , which are such that for all i, m j=1 p ij = 1 -p comm . Applying a coordinate update with step-size η/p comm to Problem (4) in the direction x (associated with communication edges) writes:

x t+1 = x t -ηp -1 comm ∇ x q A (x t , y t ), (5)
where we denote ∇ x the gradient in coordinates that correspond to x (communication edges), and ∇ y,ij the gradient for coordinate (ij) (computation edge). Similarly, the standard coordinate update of a local computation edge (i, j) can be written as:

y (ij) t+1 = arg min y∈R d ∇ y,ij q A (x t , y t ) + µ ij ∇f * ij (µ ij y (ij) t ) y + p ij 2η y -y (ij) t 2 , (6)
where the minimization problem actually has a closed form solution. Yet, as mentioned before, solving Equation ( 6) requires computing the derivative of f * ij . In order to avoid this, a trick introduced by [START_REF] Lan | An optimal randomized incremental gradient method[END_REF] and later used in [START_REF] Wang | Exploiting strong convexity from data with primal-dual first-order algorithms[END_REF] is to replace the Euclidean distance term by a well-chosen Bregman divergence. More specifically, the Bregman divergence of a convex function φ is defined as:

D φ (x, y) = φ(x) -φ(y) -∇φ(y) (x -y). (7)
Bregman gradient algorithms typically enjoy the same kind of guarantees as standard gradient algorithms, but with slightly different notions of relative smoothness and strong convexity [START_REF] Heinz | A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications[END_REF][START_REF] Lu | Relatively smooth convex optimization by first-order methods, and applications[END_REF]. Note that the Bregman divergence of the squared Euclidean norm is the squared Euclidean distance, and the standard gradient descent algorithm is recovered in that case. We now replace the Euclidean distance by the Bregman divergence induced by function φ :

y → (L ij /µ 2 ij )f * ij (µ ij y (ij)
), which is normalized to be 1-strongly convex since f * ij is L -1 ij -strongly convex. We introduce the constant α > 0 such that µ 2 ij = αL ij for all computation edges (i, j). Using the definition of the Bregman divergence with respect to φ, we write:

y (ij) t+1 = arg min y∈R d ∇ y,ij q A (x t , y t ) + µ ij ∇f * ij (µ ij y (ij) t ) y + p ij η D φ y, y (ij) t = arg min y∈R αη p ij ∇ y,ij q A (x t , y t ) -1 - αη p ij µ ij ∇f * ij (µ ij y (ij) t ) y + f * ij (µ ij y) = 1 µ ij ∇f ij 1 - αη p ij ∇f * ij (µ ij y (ij) t ) - αη µ ij p ij ∇ y,ij q A (x t , y t ) .
In particular, if we know ∇f * ij (µ ij y

(ij) t
) then it is possible to compute y

(ij) t+1 . Besides, ∇f * ij (µ ij y (ij) t+1 ) = (1 -αη)∇f * ij (µ ij y (ij) t ) - αη µ ij ∇ y,ij q A (x t , y t ), (8)
so we can also compute ∇f * ij (µ ij y

(ij)
t+1 ), and we can use it for the next step. Therefore, instead of computing a dual gradient at each step, we can simply choose y

(i) 0 = µ -1 ij ∇f ij (z (ij) 0 ) for any z (ij)
0 , and iterate from this. Therefore, the Bregman coordinate update applied to Problem (4) in the block of direction (i, j) with y

(ij) 0 = µ -1 ij ∇f i (z (ij) 0 ) yields: z (ij) t+1 = 1 - αη p ij z (ij) t - αη p ij µ ij ∇ y,ij q A (x t , y t ), y (ij) t+1 = µ -1 ij ∇f i (z (ij) t+1 ). (9)
The iterations of ( 9) are called a dual-free algorithm because they are a transformation of the iterations from (6) that do not require computing ∇f * ij anymore. This is obtained by replacing the Euclidean distance in (6) by the Bregman divergence of a function proportional to f * ij . Note that although we use the same dual-free trick the tools are different since [START_REF] Lan | An optimal randomized incremental gradient method[END_REF] applies a randomized primal-dual algorithm with fixed Bregman divergences choice to a specific primal-dual formulation. Instead, we apply a generic randomized Bregman coordinate descent algorithm to a specific dual formulation.

Distributed implementation

Iterations from (9) do not involve functions f * ij anymore, which was our first goal. Yet, they consist in updating dual variables associated with edges of the augmented graph, and have no clear distributed meaning yet. In this section, we rewrite the updates of (9) in order to have an easy to implement distributed algorithm. The key steps are (i) multiplication of the updates by A, (ii) expliciting the gossip matrix and (iii) remarking that θ (i) t = (ΣA(x t , y t )) (i) converges to the primal solution for all i. For a vector z ∈ R (n+nm)d , we denote [z] comm ∈ R nd its restriction to the communication nodes, and [M ] comm ∈ R nd×nd similarly refers to the restriction on communication edges of a matrix M ∈ R (n+nm)d×(n+nm)d . By abuse of notations, we call A comm ∈ R nd×Ed the restriction of A to communication nodes and edges. We denote P comm the projector on communication edges, and P comp the projector on y. We multiply the x (communication) update in (9) by A on the left (which is standard [START_REF] Scaman | Optimal algorithms for smooth and strongly convex distributed optimization in networks[END_REF][START_REF] Hendrikx | An accelerated decentralized stochastic proximal algorithm for finite sums[END_REF]) and obtain:

A comm x t+1 = A comm x t -ηp -1 comm [AP comm A ] comm [ΣA(x t , y t )] comm . (10)
xt+1 = xt -ηp -1 comm (W ⊗ I d )Σ comm [A(x t , y t )] comm . To show that [A(x t , y t )
] comm is locally accessible to each node, we write:

[A(x t , y t )] (i) comm = (A comm x t ) (i) - n k=1 m j=1 (A(e kj ⊗ y (kj) t )) (i) = (x t ) (i) - m j=1 µ ij y (ij) t .
We note this rescaled local vector θ t = Σ comm ([A(x t , y t )] comm ), and obtain for variables xt the gossip update of [START_REF] Hendrikx | An accelerated decentralized stochastic proximal algorithm for finite sums[END_REF]. Note that we directly write y

(ij) t instead of P ij y (ij) t
even though there has been a multiplication by the matrix A. This is allowed because Equation ( 13) implies that (i) y

(ij) t ∈ Ker(f ij ) ⊥ for all t, and (ii) the value of (I d -P ij )z (ij) t does not matter since z (ij) t
is only used to compute ∇f ij . We now consider computation edges, and remark that:

∇ y,ij q A (x t , y t ) = -µ ij (Σ comm ) ii ([A(x t , y t )] comm ) (i) = -µ ij θ t . (11)
Plugging Equation ( 11) into the updates of ( 9), we obtain the following updates:

xt+1 = xt - η p comm (W ⊗ I d )θ t , (12)
for communication edges, and for the local update of the j-th component of node i:

z (ij) t+1 = 1 - αη p ij z (ij) t + αη p ij θ (i) t , θ (i) t+1 = 1 σ i x(i) t+1 - m j=1 ∇f ij (z (ij) t+1 ) . (13)
Finally, Algorithm 1 is obtained by expressing everything in terms of θ t and removing variable xt .

To simplify notations, we further consider θ as a matrix in R n×d (instead of a vector in R nd ), and so the communication update of Equation ( 12) is a standard gossip update with matrix W , which we recall is such that W ⊗ I d = [AP comm A ] comm . We now discuss the local updates of Equation ( 13) more in details, which are closely related to dual-free SDCA updates [START_REF] Shalev-Shwartz | SDCA without duality, regularization, and individual convexity[END_REF].

Convergence Rate

The goal of this section is to set parameters η and α in order to get the best convergence guarantees. We introduce

κ comm = γλ max (A comm Σ comm A comm )/λ + min (A comm D -1 M A comm )
, where λ + min and λ max respectively refer to the smallest non-zero and the highest eigenvalue of the corresponding matrices. We denote D M the diagonal matrix such that

(D M ) ii = σ i + λ max ( m j=1 L ij P ij ), where ∇ 2 f ij (x)
L ij P ij for all x ∈ R d . Note that we use notation κ comm since it corresponds to a condition number. In particular, κ comm ≤ κ s when σ i = σ j for all i, j, and κ comm more finely captures the interplay between regularity of local functions (through D M and Σ comm ) and the topology of the network (through A) otherwise.

Theorem 1. We choose

p comm = 1 + γ m+κs κcomm -1 , p ij ∝ (1 -p comm )(1 + L ij /σ i )
and α and η as in Algorithm 1. Then, there exists C 0 > 0 that only depends on θ 0 (initial conditions) such that for all t > 0, the error and the expected time T ε required to reach precision ε are such that:

n i=1 1 2 E θ (i) t -θ 2 ≤ C 0 1 - αη 2 t
, and so

T ε = O m + κ s + τ κ comm γ log ε -1 . Algorithm 1 DVR(z 0 ) 1: α = 2λ + min (A comm D -1 M A comm ), η = min pcomm λmax(A comm ΣcommAcomm) , pij α(1+σ -1 i Lij ) // Init. 2: θ (i) 0 = -( m j=1 ∇f ij (z (ij) 0 ))/σ i . // z 0 is arbitrary but not θ 0 . 3: for t = 0 to K -1 do //
θ t+1 = θ t -η pcomm ΣW θ t // Communication using W 7:
else 8:

for i = 1 to n do 9:

Sample j ∈ {1, • • • , m} with probability p ij .

10:

z (ij ) t+1 = z (ij ) t
for j = j // Only one virtual node is updated

11: z (ij) t+1 = 1 -αη pij z (ij) t + αη pij θ (i) t // Virtual node update 12: θ (i) t+1 = θ (i) t -1 σi ∇f ij (z (ij) t+1 ) -∇f ij (z (ij) t ) // Local update using f ij 13: return θ K
Proof sketch. We have seen in Section 2 that DVR is obtained by applying Bregman coordinate descent on a well-chosen dual problem. Therefore, one of our key results consists in proving convergence rates for Bregman coordinate descent in the relatively smooth setting. Although a similar algorithm is analyzed in [START_REF] Hanzely | Fastest rates for stochastic mirror descent methods[END_REF], we give sharper results in the case of arbitrary sampling of blocks, and tightly adapt to the separability structure. This is crucial to our analysis since the probabilities to sample a local gradient and to communicate can be vastly different. In order to ease the reading of the paper, we present these results for a general setting in Appendix A, which is self-contained and which we believe to be of independent interest (beyond its application to decentralized optimization).

Then, Appendix B focuses on the application to decentralized optimization. In particular, we recall the Equivalence between DVR and Bregman coordinate descent applied to the dual problem of Equation ( 4), and show that its structure is suited to the application of coordinate descent. Indeed, no two virtual edges adjacent to the same node are updated at the same time with our sampling. Then, we evaluate the relative smoothness and strong convexity constants of the augmented problem, which is rather challenging due to the complex structure of the dual problem. This allows to derive adequate values for parameters α and η. Finally, we choose p comm in order to minimize the execution time of DVR.

We would like to highlight the fact that the convergence theory of DVR decomposes nicely into several building blocks, and thus simple rates are obtained. This is not so usual for decentralized algorithms, for instance many follow-up papers were needed to obtain a tight convergence theory for EXTRA [START_REF] Shi | Extra: An exact first-order algorithm for decentralized consensus optimization[END_REF][START_REF] Jakovetić | A unification and generalization of exact distributed first-order methods[END_REF][START_REF] Xu | Distributed algorithms for composite optimization: Unified and tight convergence analysis[END_REF][START_REF] Li | Revisiting EXTRA for smooth distributed optimization[END_REF]. We now discuss the convergence rate of DVR more in details.

Computation complexity. The computation complexity of DVR is the same computation complexity as locally running a stochastic algorithm with variance reduction at each node. This is not surprising since, as we argue later, DVR can be understood as a decentralized version of an algorithm that is closely related to dual-free SDCA [START_REF] Shalev-Shwartz | SDCA without duality, regularization, and individual convexity[END_REF]. Therefore, this improves the computation complexity of EXTRA from O(m(κ b +γ -1 )) individual gradients to O(m+κ s ), which is the expected improvement for stochastic variance-reduced algorithm. In comparison, GT-SAGA [START_REF] Xin | Decentralized stochastic optimization and machine learning: A unified variance-reduction framework for robust performance and fast convergence[END_REF], a recent decentralized stochastic algorithm, has a computation complexity of order O(m + κ 2 s /γ 2 ), which is significantly worse than that of DVR, and generally worse than that of EXTRA as well.

Communication complexity. The communication complexity of DVR (i.e., the number of communications, so the communication time is retrieved by multiplying by τ ) is of order O(κ comm /γ), and can be improved to O(κ comm / √ γ) using Chebyshev acceleration (see Section 4). Yet, this is in general worse than the O(κ b + γ -1 ) communication complexity of EXTRA or NIDS, which can be interpreted as a partly accelerated communication complexity since the optimal dependence is O( κ b /γ) [START_REF] Scaman | Optimal convergence rates for convex distributed optimization in networks[END_REF], and

2 κ b /γ = κ b + γ -1 in the worst case (κ b = γ -1
). Yet, stochastic updates are mainly intended to deal with cases in which the computation time dominates, and we show in the experimental section that DVR outperforms EXTRA and NIDS for a wide range of communication times τ (the computation complexity dominates roughly as long as τ < √ γ(m + κ s )/κ comm ). Finally, the communication complexity of DVR is significantly lower than that of DSA and GT-SAGA, the primal decentralized stochastic alternatives presented in Section 1.

Homogeneous parameter choice. In the homogeneous case (σ i = σ j for all i, j), choosing the optimal p comp and p comm described above leads to ηλ max (W ) = σp comm . Therefore, the communication update becomes θ t+1 = (I -W/λ max (W )) θ t , which is a gossip update with a standard step-size (independent of the optimization parameters). Similarly, αη(m + κ s ) = p comp , and so the step-size for the computation updates is independent of the network.

Links with SDCA. The single-machine version of Algorithm 1 (n = 1, p comm = 0) is closely related to dual-free SDCA [START_REF] Shalev-Shwartz | SDCA without duality, regularization, and individual convexity[END_REF]. The difference is in the stochastic gradient used: DVR uses ∇f ij (z

(ij) t
), where z

(ij) t is a convex combination of θ (i) k for k < t, whereas dual-free SDCA uses g (ij) t , which is a convex combination of ∇f ij (θ (i) k ) for k < t.
Both algorithms obtain the same rates. Local synchrony. Instead of using the synchronous communications of Algorithm 1, it is possible to update edges one at a time, as in [START_REF] Hendrikx | An accelerated decentralized stochastic proximal algorithm for finite sums[END_REF]. This can be very efficient in heterogeneous settings (both in terms of computation and communication times) and similar convergence results can be obtained using the same framework, and we leave the details for future work.

Acceleration

We show in this section how to modify DVR to improve the convergence rate of Theorem 1.

Network acceleration. Algorithm 1 depends on γ -1 , also called the mixing time of the graph, which can be as high as O(n 2 ) for a chain of length n [START_REF] Mohar | Some applications of laplace eigenvalues of graphs[END_REF]. However, it is possible to improve this dependency to γ -1/2 by using Chebyshev acceleration, as in [START_REF] Scaman | Optimal algorithms for smooth and strongly convex distributed optimization in networks[END_REF]. To do so, the first step is to choose a polynomial P of degree k and communicate with P (W ) instead of W . In terms of implementation, this comes down to performing k communication rounds instead of one, but this makes the algorithm depend on the spectral gap of P (W ). Then, the important fact is that there is a polynomial P γ of degree γ -1/2 such that the spectral gap of P γ (W ) is of order 1. Each communication step with P γ (W ) only takes time τ deg(P γ ) = τ γ -1/2 , and so the communication term in Theorem 1 can be replaced by τ κ comm γ -1/2 , thus leading to network acceleration. The polynomial P γ can for example be chosen as a Chebyshev polynomial, and we refer the interested reader to [START_REF] Scaman | Optimal algorithms for smooth and strongly convex distributed optimization in networks[END_REF] for more details. Finally, other polynomials yield even faster convergence when the graph topology is known [START_REF] Berthier | Accelerated gossip in networks of given dimension using jacobi polynomial iterations[END_REF].

Catalyst acceleration. Catalyst [START_REF] Lin | A universal catalyst for first-order optimization[END_REF] is a generic framework that achieves acceleration by solving a sequence of subproblems. Because of space limitations, we only present the accelerated convergence rate without specifying the algorithm in the main text. Yet, only mild modifications to Algorithm 1 are required to obtain these rates, and the detailed derivations and proofs are presented in Appendix C. Theorem 2. DVR can be accelerated using catalyst, so that the time T ε required to reach precision ε is equal (up to log factors) to

T ε = Õ m + √ mκ s + τ κ comm γ × m κ comm κ s log ε -1
Proof sketch. We follow the approach of [START_REF] Li | Revisiting EXTRA for smooth distributed optimization[END_REF] to derive the algorithm, and apply Catalyst acceleration to the primal problem on the mean parameter θt (which is never explicitly computed). Indeed, this conceptual algorithm can actually be implemented in a fully decentralized manner.

Then, we proceed to the actual proof, which requires a tight control over both primal and dual warm-start errors. Indeed, Theorem 4 (Appendix B) controls dual variables but Catalyst acceleration is applied to the primal variables.

This rate recovers the computation complexity of optimal finite sum algorithms such as ADFS [START_REF] Hendrikx | An accelerated decentralized stochastic proximal algorithm for finite sums[END_REF][START_REF] Hendrikx | An optimal algorithm for decentralized finite sum optimization[END_REF].

Although the communication time is slightly increased (by a factor mκ comm /κ s ), ADFS uses a stronger oracle than DVR (proximal operator instead of gradient), which is why we develop DVR in the first place. Although both ADFS and DVR are derived using the same dual formulation, both the approach and the resulting algorithms are rather different: ADFS uses accelerated coordinate descent, and thus has strong convergence guarantees at the cost of requiring dual oracles. DVR uses coordinate descent with the Bregman divergence of φ ij ∝ f * ij in order to work with primal oracles, but thus loses direct acceleration, which is recovered through the Catalyst framework. Note that the parameters of accelerated DVR can also be set such that

T ε = Õ √ κ comm m + τ / √ γ log ε -1 ,
which recovers the convergence rate of optimal batch algorithms, but loses the finite-sum speedup.

Experiments

We investigate in this section the practical performances of DVR. We solve a regularized logistic regression problem on the RCV1 dataset [START_REF] David D Lewis | Rcv1: A new benchmark collection for text categorization research[END_REF] (d = 47236) with n = 81 (leading to m = 2430) and two different graph topologies: an Erdős-Rényi random graph (see, e.g., [START_REF] Bollobás | Random graphs. Number 73 in Cambridge studies in advanced mathematics[END_REF]) and a grid. We choose µ 2 k = 1/2 for all communication edges, so the gossip matrix W is the Laplacian of the graph. Figure 1 compares the performance of DVR with that of state-of-the-art primal algorithms such as EXTRA [START_REF] Shi | Extra: An exact first-order algorithm for decentralized consensus optimization[END_REF], NIDS [START_REF] Li | A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates[END_REF], GT-SAGA [START_REF] Xin | Decentralized stochastic optimization and machine learning: A unified variance-reduction framework for robust performance and fast convergence[END_REF], and Catalyst accelerated versions of EXTRA [START_REF] Li | Revisiting EXTRA for smooth distributed optimization[END_REF] and DVR. Suboptimality refers to F (θ

(0) t ) -F (θ )
, where node 0 is chosen arbitrarily and F (θ ) is approximated by the minimal error over all iterations. Each subplot of Figure 1(a) shows the same run with different x axes. The left plot measures the complexity in terms of individual gradients (∇f ij ) computed by each node whereas the center plot measures it in terms of communications (multiplications by W ). All other plots are taken with respect to (simulated) time (i.e., computing ∇f ij takes time 1 and multiplying by W takes time τ ) with τ = 250 in order to report results that are independent of the computing cluster hardware and status. All parameters are chosen according to theory, except for the smoothness of the f i , which requires finding the smallest eigenvalue of a d × d matrix. For this, we start with L b = σ i + m j=1 L ij (which is a known upper bound), and decrease it while convergence is ensured, leading to κ b = 0.01κ s . The parameters for accelerated EXTRA are chosen as in [START_REF] Li | Revisiting EXTRA for smooth distributed optimization[END_REF] since tuning the number of inner iterations does not significantly improve the results (at the cost of a high tuning effort). For accelerated DVR, we set the number of inner iterations to N/p comp (one pass over the local dataset). We use Chebyshev acceleration for (accelerated) DVR but not for (accelerated) EXTRA since it is actually slower, as predicted by the theory.

As expected from their theoretical iteration complexities, NIDS and EXTRA perform very similarly [START_REF] Li | Revisiting EXTRA for smooth distributed optimization[END_REF], and GT-SAGA is the slowest method. Therefore, we only plot NIDS and GT-SAGA in Figure 1(a). We then see that though it requires more communications, DVR has a much lower computation complexity than EXTRA, which illustrates the benefits of stochastic methods. We see that DVR is faster overall if we choose τ = 250, and both methods perform similarly for τ ≈ 1000, at which point communicating takes roughly as much time as computing a full local gradient. We then see that accelerated EXTRA has quite a lot of overhead and, despite our tuning efforts, is slower than EXTRA when the regularization is rather high. On the other hand, accelerated DVR consistently outperforms DVR by a relatively large margin. The communication complexity is in particular greatly improved, allowing accelerated DVR to be the fastest method regardless of the setting.

Finally, Figure 2 presents the comparison between DVR and MSDA [START_REF] Scaman | Optimal algorithms for smooth and strongly convex distributed optimization in networks[END_REF], an optimal decentralized batch algorithm, in terms of communication complexity. To implement MSDA, we compute the dual gradients by solving each local subproblem (∇f * (x) = arg max y x y -f (y)) up to precision 10 -11 using accelerated gradient descent. Solving the subproblems with lower precision caused MSDA to plateau and not converge to the true optimum. In Figure 2(c), Acc. DVR comm (the brown line) refers to Accelerated DVR with Catalyst parameter chosen to favor communication complexity (as explained after Theorem 2). MSDA is the fastest algorithm as expected, but accelerated DVR is not too far behind, especially given the fact that it relies on generic Catalyst acceleration, which adds some complexity overhead. Therefore, the comparison with MSDA corroborates the fact that accelerated DVR is competitive with optimal methods in terms of communication while enjoying a drastically lower computational cost. Further experimental results are given in Appendix D, and the code is available in supplementary material and at https://github.com/HadrienHx/DVR_NeurIPS.

Conclusion

This paper introduces DVR, a Decentralized stochastic algorithm with Variance Reduction obtained using Bregman block coordinate descent on a well-chosen dual formulation. Thanks to this approach, DVR inherits from the fast rates and simple theory of dual approaches without the computational burden of relying on dual oracles. Therefore, DVR has a drastically lower computational cost than standard primal decentralized algorithms, although sometimes at the cost of a slight increase in communication complexity. The framework used to derive DVR is rather general and could in particular be extended to analyze asynchronous algorithms. Finally, although deriving a direct acceleration of DVR is a challenging open problem, Catalyst and Chebyshev accelerations allow to significantly reduce DVR's communication overhead both in theory and in practice.

This appendix contains the details of the derivations and proofs from the main text. More specifically, Appendix A is a self-contained appendix that specifies the Bregman coordinate descent algorithm and proves its convergence rate. Appendix B focuses on the application of Bregman coordinate descent to the dual problem (relative smoothness and strong convexity constants, sparsity structure), and how to retrieve guarantees on the primal parameters. Appendix C is devoted to presenting the Catalyst acceleration of DVR and proving its convergence speed, and Appendix D details the experimental setting, along with more experiments.

A Block Coordinate descent

We focus in this section on the general problem minimizing f + g using coordinate Bregman gradient, where g is separable, i.e., g(x)

= d i=1 g i (x (i) )
. This is a self-contained section, and notations may differ from the rest of the paper. In particular, function f is for now arbitrary and not related to F or f i from Problem (1), and the dimension d is arbitrary as well.

We first precise the blocks sampling rule. More specifically, we define a block b ⊂ {1, . . . , d} as a collection of coordinates, and B is the set of all blocks that can be chosen for the updates. Then, the algorithm updates each block b ∈ B with probability p(b), so that the probability of updating a given coordinate is given by p i = i∈b p(b). Similarly to individual coordinates, we write x (b) the restriction of x to coordinates in b. The Bregman coordinate gradient update for a block of coordinates b writes:

x t+1 = arg min x∈R d V b t (x) i∈b η t p i ∇ i f (x t ) x + g i (x (i) ) + D φ (x, x t ) , (14)
where ∇ i f denotes the gradient of f in direction i. Note that this update is more general than the one used to derive DVR, for which g = 0. In order to derive strong guarantees for this block coordinate descent algorithm, we need to ensure that there is some separability in functions f and φ, and that the block structure is suited to this separability. All the assumptions about the separability structure of f , g and φ are contained in the following assumption. Assumption 1 (Separability). The function g is separable and the function φ is block-separable for b, meaning that for all b ∈ B, there exist two convex functions φ b and φ ⊥ b such that for all x, φ(

x) = φ b (x (b) ) + φ ⊥ b (x -x (b) ). ( 15
)
Besides, for all b ∈ B, either of the following two hold:

1. φ and f are separable for b, i.e., φ b (x (b) ) = i∈b φ i (x (i) ), and

i∈b [f (x t + δ i e i ) -f (x t )] = f x t + i∈b δ i e i -f (x t ).
2. p i = p j for all i, j ∈ b.

If φ is not block-separable, the support of the Bregman update in direction b may not restricted to b. This causes some of the derivations below to fail, which is why we prevent it by assuming that Equation ( 15) holds.

Then, the first option ensures that within a block, the updates do not affect each other. The function f is not separable, but some directions can be updated independently from others. To have these independent updates, we also need to assume further separability of φ within the blocks. The second option states that if only block-separability of φ is assumed then within each block for which φ and f are not separable, coordinates must be picked with the same probability.

Assumption 1 is a bit technical but we actually require all statements in order to derive DVR. In particular, the first option is verified when updating within the same block virtual edges that are adjacent to different nodes in the dual problem. The second option is verified when picking all communication edges at once within the same block. Now that we have made assumptions on the structure of f , g and φ, we will make assumptions on their regularity. We start by a directional relative smoothness assumption between f and φ, i.e., we assume that for all i, there exists L i rel such that for all δ > 0 and e i the unit vector of direction i,

D f (x + δe i , x) ≤ L i rel D φ (x + δe i , x). (16)
Similarly, for σ rel > 0, f is said to be σ rel -strongly convex relatively to φ if for all x, y:

D f (x, y) ≥ σ rel D φ (x, y). ( 17
)
We finally assume that f and φ are convex (but not necessarily smooth). We can now state the central theorem of this section:

Theorem 3. Let f and φ be such that f is L i rel -smooth in direction i and σ rel -strongly convex relatively to φ. Denote p min = min i p i , and

L t = D φ (x, x t ) + η t p min (F (x t ) -F (x)) .
Then, if the blocks B respect Assumption 1 (separability) and η t L i rel < p i for all i, the Bregman coordinate descent algorithm guarantees for all x:

E [L t+1 ] ≤ (1 -η t σ rel )L t .
The same result holds with

L t = D φ (x, x t ) + 1 L max rel (F (x t ) -F (x)), where L max rel = max i L i rel .
To prove this theorem, we start by proving the monotonicity of such iterations.

Lemma 1 (Monotonicity). We note δ i = e i (x t+1 -x t )e i . If x t+1 = arg min x V b t (x) then:

1. If φ and f are separable for b then for all i ∈ b, if

η t L i rel ≤ p i then F (x t ) ≥ F (x t + δ i ).

If p

i = p j for all i, j ∈ b and η t L b rel ≤ p b then F (x t ) ≥ F (x t+1 ).
Proof. We start by the first point. If φ is separable for b then this means that each coordinate is updated independently. By definition of x

(i) t+1 , we have V b t (x (b) t+1 ) ≤ V b t (x t
). This writes, splitting over each i and using the fact that D φi (x t , x t ) = 0:

g i (x (i) t ) -g i (x (i) t+1 ) ≥ ∇ i f (x t ) (x (i) t+1 -x (i) t ) + p i η D φi (x (i) t+1 , x (i) t ) = ∇ i f (x t ) (x t + δ i -x t ) + p i η D φi (x (i) t+1 , x (i) t ) = f (x t + δ i ) -f (x t ) -D f (x (i) t+1 , x (i) t ) + p i η D φi (x (i) t+1 , x (i) t ) ≥ f (x t + δ i ) -f (x t ) + p i η -L i rel D φi (x (i) t+1 , x (i) t ) ≥ f (x t + δ i ) -f (x t ).
The result follows from summing over all i ∈ b, and using Assumption 1. For the second point, it is not possible to split the update per coordinate since φ is not separable. Yet, we can still write (using separability of g):

i∈b η t p i g(x (i) t ) -g(x (i) t+1 ) -∇ i f (x t ) (x (i) t+1 -x (i) t ) ≥ D φ (x t+1 , x t ). ( 18
)
Since g is separable and p i = p b for all i ∈ b, Equation ( 18) writes:

g(x t ) -g(x t+1 ) ≥ ∇f (x t ) (x t+1 -x t ) + p b η D φ (x t+1 , x t ). ( 19
)
Note that this crucially relies on x t+1 -x t having support on b, which is enforced by the blockseparability of φ. Then, the proof is similar to that of the first point, using that η t L b rel ≤ p b .

Using this monotonicity result allows us to prove Theorem 3.

Proof of Theorem 3. First note that by convexity of all g i ,

∇ 2 V b t (x) = i∈b η t p i ∇ 2 g i (x (i) ) + ∇ 2 φ(x) ∇ 2 φ(x).
Therefore, we have D V b t (x, y) ≥ D φ (x, y) for all x, y ∈ R d . Applying this with y = x t+1 yields:

V b t (x) -V b t (x t+1 ) -∇V b t (x t+1 ) (x -x t+1 ) ≥ D φ (x, x t+1 ). (20)
Then, ∇V b t (x t+1 ) = 0 by definition of x t+1 , so Equation ( 20) writes:

D φ (x, x t+1 ) + i∈b η t p i g i (x (i) t+1 ) -g(x (i) ) ≤ i∈b η t p i ∇ i f (x t ) (x -x t+1 ) + D φ (x, x t ) -D φ (x t+1 , x t ).
We first consider that the first option of Assumption 1 holds, i.e., that f and φ are separable in b. We note δ i = e i (x t+1 -x t )e i , so that:

-∇ i f (x t ) (x t+1 -x t ) = ∇f (x t ) (x t + δ i -x t ) = f (x t ) -f (x t + δ i ) + D f (x t + δ i , x t ) ≤ f (x t ) -f (x t + δ i ) + L i rel D φi (x (i) t+1 , x (i) t ). Therefore, if η t L i rel ≤ p i for all i ∈ b, - i∈b η t p i ∇ i f (x t ) (x t+1 -x t ) -D φ (x t+1 , x t ) ≤ i∈b η t p i [f (x t ) -f (x t + δ i )] + i∈b η t L i rel p i -1 D φi (x (i) t+1 , x (i) t )
≤ i∈b η t p i [f (x t ) -f (x t + δ i )]
The g i (x

(i) t+1 ) -g i (x (i)
) term can be replaced by g(x t + δ i ) -g(x t ) + g i (x

(i) t ) -g i (x (i)
) since g j (x t+1 ) = g j (x t ) for j = i. Therefore, we obtain:

D φ (x, x t+1 ) + i∈b η t p i [F (x t + δ i ) -F (x t )] + i∈b η t p i g i (x (i) t ) -g i (x (i) ) ≤ i∈b η t p i ∇ i f (x t ) (x -x t ) + D φ (x, x t ). (21)
The separability of F in b and its monotonicity lead to, using the fact that x t+1 = x t + i∈b δ i :

i∈b η t p i [F (x t + δ i ) -F (x t )] ≥ η t p min i∈b [F (x t + δ i ) -F (x t )] = η t p min [F (x t+1 ) -F (x t )] .
Therefore, if the first option of Assumption 1 holds, we obtain:

D φ (x, x t+1 ) + η t p min [F (x t+1 ) -F (x t )] + i∈b η t p i g i (x (i) t ) -g i (x (i) ) ≤ i∈b η t p i ∇ i f (x t ) (x -x t ) + D φ (x, x t ). (22)
If the second option holds, i.e., p i = p for all i ∈ b, then

i∈b η t p i ∇ i f (x t ) (x t+1 -x t ) = η t p ∇f (x t ) (x t+1 -x t ),
and Equation ( 22) can be obtained through similar derivations (at the block-level). Using the separability of g, we obtain that

E i∈b 1 p i g i (x (i) t ) -g i (x (i) ) = g(x t ) -g(x).
Then, since

E i∈b 1 pi ∇ i f (x t ) = i p -1 i b:i∈b p(b)∇ i f (x t ) = ∇f (x t )
, and the relative strong convexity assumption yields:

E i∈b 1 p i ∇ i f (x t ) (x -x t ) = ∇f (x t ) (x -x t ) ≤ f (x) -f (x t ) -σ rel D φ (x, x t ).
Therefore, taking the expectation of Equation ( 21) yields:

E D φ (x, x t+1 ) + η t p min (F (x t+1 ) -F (x t )) ≤ η t (F (x) -F (x t )) + (1 -η t σ rel )D φ (x, x t ).
We obtain after some rewriting:

E D φ (x, x t+1 ) + η t p min (F (x t+1 ) -F (x)) ≤ (1 -p min ) η t p min (F (x t ) -F (x)) + (1 -η t σ rel )D φ (x, x t ).
Finally, σ rel ≤ L i rel so η t σ rel ≤ η t L i rel ≤ p i for all i, and in particular 1 -p min ≤ 1 -η t σ rel , which yields the desired result.

The result on L t is be obtained by bounding η/p min by L max rel = max i L i rel and remarking that

1 -η t L max rel ≤ 1 -η t σ rel since L max rel ≥ σ rel .

B Convergence results for DVR

We now give a series of small results, that justify our approach. We start by showing the applicability of Theorem 3 to Problem (4), and the associated constants. Finally, we show how to obtain rates for the primal iterates θ t .

B.1 Application to the dual of the augmented problem

In this section, we note f * sum = n i=1 m j=1 f * ij , so that Problem 4 writes:

min x,y q A (x, y) + f * sum (y) (23)
Lemma 2. The iterations of Algorithm 1 are equivalent to the iteration of Equations ( 14) applied to Problem (4) with g = 0 and φ(x, y) = φ comm (x) +

n i=1 m j=1 φ ij (y (ij) ), with φ comm (x) = 1 2 x 2 A † A
for coordinates associated with communication edges, and φ ij (y

(ij) ) = Lij µ 2 ij f * ij (µ ij y ij )
for coordinates associated with computation edges.

Proof. This result follows from the dual-free and implementation-friendly derivations presented in the previous section.

Lemma 3. Let α = 2λ min (A comm D -1 M A comm )
, and φ as in Lemma 2, then:

1. q A + f * sum is (α/2)-strongly convex relatively to φ. 2. q A + f * sum is (L comm rel
)-smooth relatively to φ in the direction of communication edges, with

L comm rel = λ max (A comm Σ comm A comm ). 3. q A + f * sum is (L ij rel )
-smooth relatively to φ in the direction of virtual edge (i, j), with

L ij rel = α 1 + L ij σ i .
Proof. First note that ∇ 2 f * sum is a block-diagonal matrix, and its ij-th block is equal to

(∇ 2 f * sum (y)) ij = A (u ij u ij ⊗ ∇ 2 f * ij (µ ij y (ij) ))A 1 L ij A (u ij u ij ⊗ P ij )A, (24)
Therefore,

q A   x t + (i,j)∈b δ ij   -q A (x t ) = 1 2   (i,j)∈b δ ij   A ΣA (ij)∈b δ ij +   (ij)∈b Aδ ij   ΣAx t = (i,j)∈b q A (δ ij ) + δ ij A ΣAx t = (i,j)∈b (q A (x t + δ ij ) -q A (x t )) .
Finally, f * sum is separable, and so q A + f * sum respects option 2.

We can now prove the main theorem on the convergence rate of DVR.

Theorem 4. We choose

p comm = 1 + γ m+κs κcomm -1 and p ij ∝ (1 -p comm )(1 + L ij /σ i ).
Then, for all θ 0 ∈ R n×d and all t > 0, the error is such that:

η t p min D φ (λ , λ t ) + D(λ t ) -D(λ ) ≤ 1 - αη t 2 t η t p min D φ (λ , λ 0 ) + D(λ 0 ) -D(λ ) , (26)
with p min = min(p comm , min ij p ij ), λ t = (x t , y t ) and D = -(q A + f * sum ). Therefore, the expected time T ε required to reach precision ε is equal to:

T ε = O m + κ s + τ κ comm γ log ε -1 .
Proof. Using Lemmas 4 and 3, we apply Theorem 3 (convergence of Bregman coordinate gradient descent), and obtain that the convergence rate is η t α/2, with η t ≤ min ij p ij /L i rel and η t ≤ p comm /L comm rel . Therefore, for communication edges, we have that

η t ≤ p comm L comm rel = p comm λ max (A comm Σ -1 comm A comm )
.

For computation edges, we know that

p ij = p comm (1 + L ij /σ i )/( m j=1 (1 + L ij /σ i ))
, and so

η t ≤ p ij L ij rel = p comp α m j=1 (1 + σ -1 i L ij ) ≤ p comp α(m + κ s ) , with κ s ≥ σ -1 i m j=1
L ij for all i. In the end, we would like these two bounds to be equal, so we choose p comp and p comm such that

p comp = p comm (m + κ s ) λ + min (A comm D -1 M A comm ) λ max (A comm Σ -1 comm A comm )
.

Yet, we also know that p comm = 1 -p comp , so

p comp = 1 + 1 m + κ s λ max (A comm Σ -1 comm A comm ) λ + min (A comm D -1 M A comm ) -1
.

Equivalently, this corresponds to taking

p comm = 1 + γ m + κ s κ comm -1
.

With this choice, one can verify that η t verifies both η t α ≤ 2p comm and η t α ≤ 2 min ij p ij , so the rate is:

1 - η t α 2 = 1 - p comp 2(m + κ s )
.

The expected execution time to reach precision ε, denoted T ε , is equal to T ε = ρ -1 (p comp + τ p comm )K ε with K ε such that C(1 -η t α/2) Kε < ε for some constant C, and so:

T ε = O 2(m + κ s ) + τ κ comm γ .

B.2 Primal guarantees

The goal of this section is to recover primal guarantees from dual guarantees. Although the initial setting is inspired from [START_REF] Lin | An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization[END_REF], the proof is different, and in particular does not require smoothness of the f * ij or an extra proximal step. We define for β ≥ 0 the Lagrangian function:

L(λ, θ) = n i=1 m j=1 f ij (θ (ij) ) + σ i 2 θ (i) 2 + β 2 θ (i) -ω (i) 2 -λ A θ. (27)
The dual problem D(λ) is defined as

D(λ) = min θ L(λ, θ).
Given an approximate dual solution λ k , we can get an approximate primal solution θ k = arg min θ L(λ k , θ), which is obtained as:

θ (ij) t = arg min v f ij (v) -µ ij λ (ij) t v ∈ ∂f * ij (µ ij λ (ij) t ), (28)
θ (i) t = 1 σ i + β (Aλ t ) (i) + βω (i) . (29)
Note that θ

(ij) t corresponds to the z (ij) t
from Algorithm 1. We chose to use a different notation in the main text to emphasize on the fact that these are the parameters for the virtual nodes, but z (ij) t actually converge to the solution as well. Similarly, λ t corresponds to (x t , y t ) the concatenation of the parameters for communication and virtual edges from Section 2. The last difference is that the Lagrangian defined in Equation ( 27) actually corresponds to a Lagrangian associated to a perturbed version of Problem [START_REF] Heinz | A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications[END_REF]

in which fi (θ) = f i (θ) + β 2 θ -ω (i) 2
. The solution to the initial problem can be retrieved by taking β = 0, but this more general formulation enables us to derive results that also holds for the inner problems solved by the Catalyst accelerated version of DVR.

(i) t -θ 2 ≤ C 0 (1 -ρ) t . ( 30
)
Proof. Using the fact that θ

(i) t = 1 σi+β ((Aλ t ) (i) + ω (i)
t ) (and similarly for θ ), where Σ β is the block diagonal matrix such that (Σ β ) ii = (σ i + β) -1 I d , we obtain:

n i=1 θ (i) t -θ 2 = n i=1 1 (σ i + β) 2 (Aλ t ) (i) -(Aλ ) (i) 2 ≤ 1 (σ min + β) 2 Aλ t -Aλ 2 .
Using the min((

σ max + β) -1 , L -1 ij )-strong convexity of θ → 1 2 x Σ β x + i,j f * ij (x (ij)
), we obtain:

n i=1 θ (i) t -θ 2 ≤ 2 (β + σ max + L max ) (σ min + β) 2 (D(λ ) -D(λ t )) . (31)
Then, we add p min η -1 t D φ (λ , λ t ) ≥ 0 and apply Theorem 4, which yields

n i=1 θ (i) t -θ 2 ≤ 2(β + σ max + L max ) (σ min + β) 2 (1 -ρ) t p min η t D φ (λ , λ 0 ) + (D(λ ) -D(λ 0 )) .
Then, Theorem 1 is a direct consequence of Theorem 4 and Lemma 5.

C Catalyst acceleration

We show in this Section how to apply Catalyst acceleration to DVR, and prove the convergence speed in this case.

C.1 Derivation and rates

In the main text, we derived DVR to solve regularized finite sum problems. Although not so different, the subproblem obtained with Catalyst is not in the form of Problem [START_REF] Heinz | A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications[END_REF], and some adjustments need to be made. More specifically, we would like to solve problems of the form:

min θ    F t (θ) n i=1   σ i 2 θ 2 + β 2 θ -ω (i) t 2 + m j=1 f ij (θ)      . ( 32
)
An easy way to adapt the algorithm is to consider the extra (β/2) θ-ω

(i) t
2 as just another component of the sum. Yet, the point of this extra term is to make the problem easier to solve by adding strong convexity. This would not be the case if this term were is treated as just another term in the sum. Therefore, we want to include it with the quadratic term. We define:

h(x) = σ i 2 θ 2 + β 2 θ -ω (i) t 2 , then h * (x) = 1 2(β+σ) x + βω (i) t 2 -β 2 ω (i) t 2 .
Therefore, Problem (4) becomes:

min λ∈R (E+mn)d 1 2 λ A Σ β Aλ + βω t Σ β Aλ + n i=1 m j=1 f * ij ((Aλ) ij ), (33)
with (Σ β ) ii = (σ i + β) -1 for i ∈ {1, . . . , n}. The linear term does not affect the Hessians, and thus the convergence rate is the same as before, with σ replaced by σ + β. In terms of algorithms, we just need to modify the gradient term, and obtain Algorithm 2. The only term that changes is ∇q A (x, y), to which an extra βΣ β ω t term is added. Therefore, the updates to θ t and z t remain unchanged, and only the initial expression of θ t requires some adjustments since we now have that (as written in Equation 29):

θ (i) t,k = 1 σ i + β (Aλ t,k ) (i) + βω (i) .
If we only consider 1 inner loop then the only thing that changes is the initial condition. If we consider several outer loops, then the we must choose the new parameter as θ t+1 0 = θ t T + Σ β (ω t+1 -ω t ) in order to maintain the invariant, but a remarkable fact is that the inner iterations remain the same, with the only exception that Σ is replaced by Σ β . Note that it is possible to warm-start the z t+1,0 as well, but this requires updating θ t,0 accordingly with ∇f ij (z (ij) t,0 ), which requires a full pass over the local dataset. We therefore choose not to do it. However, it is not obvious that Algorithm 2 corresponds to a genuine Catalyst acceleration yet. Indeed, Catalyst acceleration requires having a feasible ε t -approximations for the primal problem, i.e., points θ t ∈ R d such that F t (θ t ) -min θ F (θ) ≤ ε t . In our case, we only have dual guarantees and approximate feasibility. We know that the parameters converge to consensus, but they do not reach it at any time. This is a problem because it is then not possible to adequately define F t+1 based on the local approximations of the solutions of F t . Yet, following the approach of [START_REF] Li | Revisiting EXTRA for smooth distributed optimization[END_REF], we note that

n i=1 θ -ω (i) t 2 = n θ -ωt 2 + n i=1 ω (i) t 2 -n ωt 2 ,
where ωt =

1: α = 2λ + min (A comm D -1 M A comm ), η = min pcomm λmax(A comm Σ β,comm Acomm) , pij α(1+σ -1 i Lij ) 2: q = σmin σmin+β // Initialization 3: ω (i) 0 = -1 σi+β m j=1 ∇f ij (z (ij) 0 ), θ (i) 0 = 1 + β σi+β ω (i) 0 .
// z 0 is arbitrary but not θ 0 .

4: for t = 0 to T -1 do // T outer loops 5:

for k = 0 to K -1 do // Inner loop runs for K iterations

θ (i) t,k+1 = θ (i) t,k -1 σi+β ∇f ij (z (ij) t,k+1 ) -∇f ij (z (ij) t,k ) // Local update using f ij 15: ω t+1 = θ t,K + 1- √ q 1+ √ q (θ t,K -θ t-1,K ) 16: θ t+1,0 = θ t,K + β β+σi (ω t+1 -ω t ) 17:
z t+1,0 = z t,K 18: return θ T knowing only its own parameter), it is conceptually applied to a mean parameter θt (that is never explicitly computed). In the following, we thus analyze the performances of the following algorithm:

θt+1 ≈ arg min θ F (θ) + nβ 2 θ -ωt 2 ωt = θt+1 + 1 - √ q 1 + √ q ( θt+1 -θt ), (34)
where we recall that q = σ min /(σ min + β). Recall that the inner problem is approximated using DVR and the means do not need to be computed explicitly. Let κ β s = max i 1 + ( m j=1 L ij )/(β + σ i ), and κ β comm be obtained similarly to κ comm but replacing Σ by Σ β . We consider in this section that σ i = σ for all i ∈ {1, . . . , n} in order to simplify exposition, but the results hold more generally. Note that α and η have slightly different expressions than in the main text since β is now involved in their definitions. We define the sequence ε t which is such that:

ε t = 2 9 (F (θ 0 ) -F (θ )) (1 -ρ out ) t with ρ out < √ q, and q = σ σ + β . (35)
We then prove the following theorem:

Theorem 5. Consider Algorithm 2 with p comm = 1+γ

m+κ β s κ β comm -1 , p ij ∝ (1-p comm )(1+L ij /(σ i + β)). If K = Õ (1/(η t α)) then for all t ≤ T , F t ( θt ) -F t (θ t ) ≤ ε t and F ( θt ) -F (θ ) ≤ 8 ( √ q -ρ out ) 2 (1 -ρ out ) t+1 (F ( θ0 ) -F (θ )). (36)
Note that the error is on the mean parameter, and we also want θ (i)

t to be close to θt for all i. This is ensured by Lemma 5. Before we start the proof of Theorem 5, we show that Theorem 2 is a corollary of Theorem 5.

Proof of Theorem 2. Using the same argument as in Theorem 1, we obtain that each inner loop takes time

T inner = O m + L s + σ β + σ + τ L comm + β γ(β + σ)
in expectation, so the total number of inner iterations is of order:

T ε = Õ   1/ρ out k=0 T inner   = Õ 1 + β σ m + L s + σ β + σ + τ L comm + β γ(β + σ) log 1 ε . (37)
Therefore, we see that if we choose β + σ = L comm then, taking into account the fact that κ s ≤ mκ comm , the algorithm takes time:

T ε = Õ √ κ comm m + τ c γ .
Therefore, using Chebyshev acceleration allows to recover the rate of optimal batch algorithms (up to log factors). On the other hand, if we choose β = L s /m -σ then if β ≥ 0 (i.e., κ s ≥ m), the time to convergence is equal to:

T ε = Õ κ s m m + τ mκ comm + κ s γκ s .
This can be rewritten as:

T ε = Õ √ mκ s + τ √ κ comm γ mκ comm κ s .
Therefore, we obtain the optimal √ mκ s computation complexity in this case, with a slightly suboptimal communication complexity due to the mκ comm /κ s term. When this term is equal to 1 then √ mκ s = m √ κ b and so nothing is gained from using a stochastic algorithm. Otherwise, this allows to trade-off communications for computations.

The proof of Theorem 5 is obtained in several steps, that we emphasize below:

1. Equivalent decentralized implementation of Catalyst. 2. Bounding the primal suboptimality as F t ( θt ) -min θ F t (θ) ≤ (1 -(ηα)/2) k D t 0 , with k the number of inner iterations and D t 0 a dual error. This quantifies how precisely the inner problem is solved. 3. Evaluating the initial dual suboptimality D t 0 , which depends on θ t-1 (and its associated dual parameter λ t-1 ). This quantifies how good θt-1 already is as a solution to F t .

In the end, this allows us to use the catalyst general results with primal criterion, and with simple warm-start scheme (warm-start on the last iterate of the last outer iteration). The first point is presented at the beginnning of this section and the second one is adressed by Lemma 5. The following section deals the last point.

C.2 Proof of Theorem 5

We now show a bound on the initial error of an inner loop when warm-starting on the last iterate of the previous inner loop. Indeed, the convergence results for DVR depend on the initial dual error and so results from [START_REF] Lin | Catalyst acceleration for first-order convex optimization: from theory to practice[END_REF] cannot be used directly. Yet, it can be adapted, as we show in this section. We note D t (λ) the dual function at outer step t (which should not be mistaken with the Bregman divergence D φ ), and λ t its minimizer. Similarly, we note θ t = arg min θ F t (θ), whereas θ is the global minimizer of F . The following theorem ensures convergence of θt to the true optimum, given that the subproblems are solved precisely enough. Theorem 6. [23, Proposition 5]. If F k ( θk ) -F k (θ k ) ≤ ε k for all k ≤ t then F ( θt ) -F (θ ) ≤ 8 ( √ q -ρ out ) 2 (1 -ρ out ) t+1 (F ( θ0 ) -F (θ )).

Therefore, our goal is to prove that F t ( θt+1 ) -F t (θ t ) ≤ ε t for all t. The smoothness of F t ensures that this is achieved if

n i=1 θ (i) t+1 -θ t 2 ≤ n L ε t . (39)
This lemma has the following corollary: Corollary 1 (Warm-started virtual error decrease). For all (i, j), We use Lemma 8 for the first term.

E   i,j (θ t+1 ) (ij) -θ t 2   ≤ (1 -ρ) K 6 C ω + n L + K ρ sum C comp 1 -ρ ε t-1 , (58)
Lemma 12 (Condition on K). If Equations (40), ( 41) and (42) hold at time t, and K is such that:

(1 -ρ) K ≤ min C 1 (1 -ρ out ) 12(C ω + n/L) , C 1 (1 -ρ out )(1 -ρ) Kρ sum C comp , C 2 C L , n(σ min + β) 2 2LC L (β + σ max + L max )
, then they also hold at time t + 1.

Proof. Using Corollary 1, we obtain that if K is set such that

(1 -ρ) K 6 C ω + n L + K ρ sum C comp 1 -ρ ≤ C 1 (1 -ρ out ),
then the recursion condition is respected for the virtual parameters. This yields the first and second conditions on K. Now, we write C L = pmin ηt C φ + C D , then using Lemmas 10 and 7 (where C φ and C D are defined), we obtain using Theorem 4 that D t (λ t ) -D t (λ t+1 ) ≤ C L (1 -ρ) K ε t-1 , since λ t+1 is obtained by performing K iterations of DVR to minimize F t starting from λ t . This yields the third condition on K. Finally, the last condition on K is obtained by leveraging Lemma 5.

D Experiments

For the experiments, the following logistic regression problem is solved:

min θ∈R d n i=1   σ 2 θ 2 + m j=1 1 m log(1 + exp(-y ij X ij θ))   , (59)
where the pairs (X ij , y ij ) ∈ R d × {-1, 1} are taken from the RCV1 dataset, which we downloaded from https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary.html.

Figure 3 is the full version of Figure 1, in which we report the number of individual gradients and number of communications for each configuration. We see that accelerated EXTRA actually outperforms EXTRA when the regularization is small, as already mentioned in the main text. We also see that Accelerated EXTRA and Accelerated DVR have comparable communication complexity on the grid graph, when γ is smaller. Yet, the computation complexity of (accelerated) DVR is much smaller, so accelerated DVR is much faster overall as long as τ is not too big.

  Grid, σ = m • 10 -5 Erdős-Rényi, σ = m • 10 -7 Grid, σ = m • 10 -7

Figure 1 :

 1 Figure 1: Experimental results for the RCV1 dataset with different graphs of size n = 81, with m = 2430 samples per node, and with different regularization parameters.

5 0

 5 Erdős-Rényi, σ = m • 10 -Grid, σ = m • 10 -7

Figure 2 :

 2 Figure 2: Experimental results for the RCV1 dataset with different graphs of size n = 81, with m = 2430 samples per node, and with different regularization parameters.

Lemma 5 .

 5 Denote C 0 = (β+σmax+Lmax) 2(σmin+β) 2 pmin ηt D φ (λ , λ 0 ) + (D(λ ) -D(λ 0 )) , then n i=1 θ

  Note that [P comm A ΣA(x t , y t )] comm = [P comm A ] comm [ΣA(x t , y t )] comm because P comm and Σ are non-zero only for communication edges and nodes. Similarly, and as previously stated, one can verify thatA comm [P comm A ] comm = [AP comm A ] comm = W ⊗ I d ∈ R nd×ndwhere W is a gossip matrix. We finally introduce xt ∈ R nd which is a variable associated with nodes, and which is such that xt = A comm x t . With this rewriting, the communication update becomes:

  , solving F t is equivalent to solving a problem involving ωt only. Besides, the Catalyst iterations are linear, meaning that performing the extrapolation step on θt is equivalent to performing it on each θ

	Algorithm 2 Accelerated DVR(z 0 )
	1 n	n i=1 ω	(i)
			(i)
			t
	individually. Therefore, although Catalyst is implemented in a fully decentralized manner (each node

t . This means that although F t is only defined with the local variables ω (i) t

  Proof. Using Lemmas 5, 10 and 7, we write:C 0 (t) = (β + σ max + L max ) (σ min + β) 2 p min η t D φ (λ t , λ t 0 ) + D(λ t ) -D(λ t 0 ) ≤ C comp ε t-1

	with
	C comp =	(β + σ max + L max ) (σ min + β) 2	p min η t	C φ + C 2 + C ω + 4	βn L

Acknowledgement

This work was funded in part by the French government under management of Agence Nationalede la Recherche as part of the "Investissements d'avenir" program, reference ANR-19-P3IA-0001(PRAIRIE 3IA Institute). We also acknowledge support from the European Research Council (grantSEQUOIA 724063) and from the MSR-INRIA joint centre.

Broader impact statement

This work does not present any foreseeable societal consequence.

where u ij ∈ R n(1+m) denotes the unit vector corresponding to virtual node (i, j). We denote

Relative strong convexity. Then, [START_REF] Hendrikx | An optimal algorithm for decentralized finite sum optimization[END_REF]Lemma 6.5] leads to A ΣA σ F A † A. Note that the notations are slightly different, and the matrix Σ in this paper is the same as the matrix Σ † in [START_REF] Hendrikx | An optimal algorithm for decentralized finite sum optimization[END_REF]. Then, remark that

, and φ ij = α -1 f * ij , so that:

Finally, using that Equation [START_REF] Lin | An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization[END_REF] along with the fact that σ F ≤ α implies that q A + f * sum is σ Frelatively strongly convex with respect to φ.

Relative smoothness. We first prove the relative smoothness property for communicate edges. For any x ∈ R Ed , Equation ( 25) leads to:

(x, 0) [∇ 2 q A (x, y) + ∇ 2 f * sum (y)](x, 0) = (x, 0) A ΣA(x, 0) L comm rel (x, 0) ∇ 2 φ(x, y)(x, 0).

Similarly, for any θ ∈ R d , we consider ỹ = e ij ⊗ θ and write:

and α ≤ L i rel , which ends the proof of the directional relative smoothness result. Lemma 4. Assumption 1 holds with f = q A + f * sum , g = 0, and φ as in Lemma 2, and when the sampling is such that either:

• All communication edges are sampled at once, or

• Each node samples exactly one virtual edge.

Proof. First of all, g = 0 is separable, and φ is separable with respect to the communication and computation blocks by construction.

We note b comm the block of all communication edges, which is sampled with probability p comm . All communication edges are sampled at the same time, so p i = p comm for all i ∈ b comm and so φ respects option 2 for the communication block.

Let us now consider a computation block b. First of all, φ is separable for the virtual edges. Then, virtual blocks contain exactly one virtual edge per node, and so b = {(1, j 1 ), • • • , (n, j n )}. Let k = , then e k,j k A ΣAe ,j = µ k,j k µ ,j (e k -e k,j k ) Σ(e -e ,j ) = 0.

Yet, using Lemma 5, we know that, since θ (i) t+1 is obtained by applying K steps of DVR to F t starting from λ t 0 .

Unfortunately, we have no control over the dual error at this point. In the remainder of this section, we prove by recursion that Equation [START_REF] Wang | Exploiting strong convexity from data with primal-dual first-order algorithms[END_REF] holds for all t. More specifically, we start by assuming that:

where C 1 and C 2 are such that the conditions are verified for t = -1, with D -1 = D 0 , θ -1 = θ 0 , and λ -1 = λ 0 . Equation [START_REF] Xiao | DSCOVR: Randomized primal-dual block coordinate algorithms for asynchronous distributed optimization[END_REF] may not hold for t = -1, but making it hold at time t = 0 would only require a slightly longer first inner iteration, meaning at most an extra log factor. Therefore we assume without loss of generality that it is the case, since the final complexities are given up to logarithmic factors. The rest of this section is devoted to showing that if K is chosen as in Theorem 5 then Equations ( 40), ( 41) and ( 42) hold regardless of t. The first part focuses on assessing the initial error of outer iteration t + 1 when the conditions hold at the end of outer iteration t, and the second part on showing how these errors shrink during outer iteration t + 1.

C.2.1 Warm-start error

We know that DVR converges linearly, and so the error for each subproblem decreases exponentially fast. Yet, we need to know how big the error is when solving a new problem in order to make sure that the progress from solving previous subproblems is not lost. The point of this is to avoid an extra log(ε -1 ) factor in the rate, which would come from having to solve each subproblem from a O(1) precision to an ε precision using DVR. We show in this section that the initial error is actually much lower than O(1) and decreases with the outer iterations. We first start by bounding the variations of ω t across iterations, which we will need for the next proofs. Lemma 6 (Distance between subproblems). It holds that

Proof. The form of the updates yields that (see [START_REF] Lin | Catalyst acceleration for first-order convex optimization: from theory to practice[END_REF]Proposition 12] or [20, Proof of Lemma 10])

t-2 -θ }. Note that here, θ is the actual solution of the primal problem without the catalyst perturbation. Then, the error can be decomposed as:

Finally, the strong convexity of F leads to

where in the last inequality we use [23, Proposition 5], which holds because

and a similar bound can be used for θ

Then, we finish proof by plugging in the expression of ε t-1 .

We then use Lemma 6 to bound the initial dual error. We denote θ t k (and λ t k ) the parameters at inner iteration k of outer iteration t. Lemma 7 (Dual error warm-start). The warm-started dual error verifies:

Note that we simply warm-start the dual coordinates for an outer iteration using the last iterate from the previous one. Yet, this leads to

Proof. Equation [START_REF] Schmidt | Minimizing finite sums with the stochastic average gradient[END_REF] implies that D t (λ) can be written as:

with R comp (λ) that only depends on λ (ij) and not on ω

Equation ( 29) writes

t , and so:

Then, we know from the equivalent reformulation of Equation ( 34) that θ t = arg min F (θ) + β 2 θωt 2 , so using the 1-Lipschitzness of the proximal operator yields

, and so:

Plugging in Equation (46) yields:

Finally note that D t-1 (λ t ) ≤ D t-1 (λ t-1 ) since λ t-1 is the maximizer of D t-1 , and

since it is the output of DVR after inner iteration t. The final expression is obtained using 6 and the recursion assumptions given by Equations ( 40) and [START_REF] Xu | Distributed algorithms for composite optimization: Unified and tight convergence analysis[END_REF].

Finally, the warm-start error on the nodes parameters is given by the two following lemmas.

Lemma 8 (Virtual parameters warm-starts

Proof. We use the fact that

Then, as before, the 1-Lipchitzness of the prox operator yields θ t-1 -θ t ≤ 1 n ω t -ω t-1 .

Lemma 9 (Parameters warm-start). Denote

Proof. We use the fact that since

t-1 ) to write:

We finish this part on warm starts by proving the following lemma, that links the initial dual parameters error (computed with the Bregman divergence of φ), to the other parameters which we already know how to control. Lemma 10 (Dual parameters warm-start, as measured by the Bregman divergence).

with

Proof. We first decompose the Bregman divergence as:

Then, we bound the communication term as:

Using Lemmas 8 and 9, we obtain:

For the computation part, we use the duality property of the Bregman divergence, which yields

Therefore,

Substituting Equations ( 51) and (52) into Equation (50) finishes the proof.

C.2.2 Inner iteration error decrease

Now that we have bounded the error at the beginning of each outer iteration, we bound error at the end of each outer iteration by using the convergence results for DVR. We first prove the following Lemma, which controls the distance between the virtual parameters and the actual one: Lemma 11 (Virtual error decrease). For all (i, j),

Proof. We cannot retrieve direct control over the θ

t+1 from control over the dual variables or the dual error, since this would require the f * ij functions to be smooth, which they may not be. Yet, we leverage the fact that θ

t+1 is obtained by a convex combination between θ (ij) t and θ (i) t to obtain convergence of to θ t . We note j t,k (i) the virtual node that is updated at time (t, k) for node i. We note E k the expectation relative to the value of j t,k (i). We start by remarking that:

, where in the last inequality we used the convexity of the squared norm. We use that p ij ρ ij ≥ ρ (equal for the smallest one), and write that:

Using Lemma 5, we know that

, with C 0 (t) a constant that depends on the initial conditions of outer iteration t. Therefore,

In the end,


domain: info.info-dm info shs

text:
Mathematics, the pandemic and complex systems

Bertrand Jouve

LISST -CNRS -Université Toulouse Jean Jaurès -France

---------Abstract:

We indirectly question the role of mathematics in the response to the COVID-19 pandemic. Firstly, we look at its importance in analysing the complexity of the systems currently facing us. Next, we look at the resulting relationship between mathematics and other disciplines, and why it is important that mathematics plays a part in scientific approaches to handle the major challenges presented by these systems.

---------I would like to thank the organisers Melanija Mitrović and Norbert Hounkonnou for giving me the opportunity to give this short talk.

I do not work in the field of epidemic modelling, so I will not provide precise information on models put in place in relation to COVID-19. However I have worked for a long time now on the use of graph theory to model real major networks -social networks, trading networks, real neural networks -and I have taken part in many interdisciplinary projects. Yet graph theory and the notion of a "network" are both very prevalent in scientific studies relating to COVID-19, and a multidisciplinary approach would appear increasingly important for effective handling of COVID-19. So I am going to indirectly question the role of mathematics in the response to the pandemic, firstly by briefly considering the complexity of the systems currently facing us, then the resulting relationship between mathematics and other disciplines, and why it is important that mathematics plays a role in scientific approaches to tackle the major issues created by these systems, such as social, environmental or health issues.

Mathematical models relating to the spread of an epidemic, management of statistical information on the number of infected people, vaccine research, preventive measures, economic measures... it quite quickly became apparent that we could not separate these different actions if we wanted to effectively combat the pandemic. This has resulted in what we call a "complex system", which is characterised by multi-scale dynamics, cascade effects leading to sudden quantitative and qualitative changes, and feedback loops which result in a non-linear system dynamic. These systems generally act in a manner which can be difficult to predict if we ignore the interactions between their different components. Whilst this complexity has become apparent to everyone during the current pandemic, researchers have been interested in the analysis of complex systems for decades, 1 and it is almost a cliché to say that complexity is everywhere: environmental changes, social communities, collective dynamics in biological systems, urban and transport systems, natural risks, brain function... Analysis of these complex systems was quite difficult until the mid-20th century, but our modern ability to produce a huge quantity of data on the real world's workings, combined with powerful calculations and increased storage capacity, has provided a fresh insight into understanding and processing this complexity, from both a practical and theoretical point of view. However, for many reasons this process often ignores qualitative approaches, which are common in human and social sciences, and even in experimental sciences. In my opinion, and to give just a few examples, the challenges which we must currently tackle relate to our inability to include local, traditional or indigenous knowledge in global sustainable development models, the difficulty of including clinical knowledge in bioengineering approaches, the weakness of non-economic criteria when evaluating comparative advantages on dynamic markets, or the difficulty of including knowledge on parties in environmental development models, and so on. For public or private decision makers, having access to large amounts of quantitative data can even lead to bypassing any discussion required to understand the dynamic of a complex phenomenon in progress. During a Big Data conference in Toulouse in 2015, Bernard Stiegler 2 stated: "[…] the problem is that Big Data has an unfortunate tendency to circumvent all deliberation processes, absolutely every one […]". What I mean to say here is that even though rapid action is needed to better understand the world's complexity, a complexity which we help to create, there will be no Big Data miracle or life-saving scientific discipline. Believing in one or the other would even be counter-productive, as it would limit the implementation of an effective approach to analysing complexity. A lot of hope is placed on "machine learning", a concept made possible by Big Data, which is found throughout our society, particularly to guide actions, whether political, economic or even medical, in a world that is moving ever faster and is increasingly interconnected. We need to be quick to keep up, and as explained by Etienne Klein citing Francis Bacon, we need to innovate, as the idea of life-saving innovation is a common one. However no one can work quicker than a computer, which can process up to hundreds of billions of operations per second, which is why we entrust decisions to algorithms and data. Mathematics is at the heart of the action, as it often structures simulation models which will be used en masse to assess the "efficacy" of an innovation, but also a political decision 3 . For example in France, when political figures grasped the scale of the pandemic, suddenly everyone learned about epidemic mathematical models and the famous R0. At this point, whether consciously or unconsciously, two incorrect views of mathematics could emerge. Firstly, because we could be led to believe that mathematics is able to deal easily with complexity, whereas the models we have today need thousands of examples to learn and are easily misled. My friend the economist Alan Kirman told me last year about Melanie Mitchell's thoughts on machine learning 4 "the machine doesn't understand what "the meaning" means, and that's the problem". Secondly, because we could be led to think that mathematics is nothing more than a more or less enhanced form of data processing. Alain Connes5 said in an interview with France Info on 8 May 2018: "What really surprises me is that Évariste Galois was able to understand concepts without doing the calculations. I think we are starting to confuse "understanding without doing" with "doing without understanding". However the essence of humans is understanding, and this is something completely out-of-reach of artificial intelligence [...] Currently, artificial intelligence lacks common sense and above all genius". It seems to me that we are witnessing a significant collective loss of trust in society, in ourselves.

To understand a crisis like the current COVID-19 pandemic, the approach using the methods and tools of complex systems is an integrated way to tackle questions, which we cannot avoid and which does not bypass disciplines. Rooted in disciplines but breaking free from disciplinary confinement, it is used to understand interactions between the different dimensions in play. Like any interdisciplinary approach, which is new for us 20th or 21st century researchers, it is a revolution in thinking and knowledge which is built over time, and the urgency of situations which we have and will have to face should not lead us to think that we can reduce time spent on scientific research to the bare minimum. Science is a universe of controversy where methods, results and models must be discussed at length to be robust. Mathematics is no exception, and we know that the mathematical models used now are backed by tens of years of research. What is the strength of mathematics in this context, and its position?

The power of mathematics largely stems from its generic nature, which is necessary to navigate the various concepts. Accustomed to reasoning with abstract objects, the mathematician has unique skills, providing a multidisciplinary group with the ability to understand interactions between logical reasoning and concepts. The mathematicians are also able to ignore any a priori approach, as they know that by changing hypotheses, a false result can become true. There are no taboos in mathematics; no one will prevent you from assuming that certain hypotheses are true and exploring what this means. But other sciences need to develop in silos, based on more or less implicit assumptions or observations, which cannot be broken; the efficiency is remarkable, but switching to other hypotheses is rarely considered. This is not about valuing mathematics above other sciences, which are more empirical or rooted in the world's realities, but pointing out the differences. For example, contradictions are forbidden in mathematical reasoning, whilst there are plenty in our society, and contradictory debate is the core methodology of human and social sciences. In a real world which wants to understand and control its evolution, where we are asked to predict increasingly far into the future, the universal nature of mathematics can obscure our vision. At this stage of reasoning, we could discuss the applicability of mathematics or knowing if the world is mathematical. From Galileo to Einstein and Kant, these questions have been discussed since ancient times, and I am not qualified to discuss such philosophical matters. However, it seems that we can admit that mathematics is neither an experimental science nor an observational science, and that the effectiveness of mathematics as a "tool to control complexity" or a "language of the world's imagination" 6 is not self-evident. As underlined by Jean-Michel Salanskis "all notions used to describe reality and its changes are included and affected by the chosen mathematical framework". A model is always built on hypotheses and with a choice of variables or distributions of possible variables which are not random, must be discussed, and are generally simplifications of reality. It is not enough to program formal models and supply them with "Big Data" to get a representation of the world in 10, 50 or 100 years. We really need to see a model as a piece of a puzzle that we put together as a group, each with different knowledge and skills. We can even quote George E.P. Box: "all models are wrong, but some are useful".

However I am convinced that mathematics must be involved, with other disciplines, in systems to study and understand complex phenomena which make up the world today, and in which it is already involved (development of social networks, growth of financial bubbles, etc.). To do so, it has an additional challenge to overcome: overcoming its language, which is technical but necessary. This is required for an interdisciplinary exchange to take place, particularly with less formalised sciences but which also have their own concepts, methods and tools. The mathematician probably needs to take a risk and aim to explain the representations that they have in mind in "simple" terms, share the fact that they make sense, in the mathematical world, and that they can also make sense in an interdisciplinary process to create innovations to understand and improve the world in which we live. With mutual listening and consideration, discourse is possible. All that said, we still need mathematics to be well received, and I worry when, during a meeting in 2017 on AI organised by Facebook Paris, Yann LeCun, Facebook's Chief AI Scientist, says the following when talking about the fact that we do not really know how deep learning algorithms work: "[...] it's not a major problem. It's very satisfying to have an explanation, and it reassures humans if an artificial intelligence system has an explanation. But ultimately what we want is good reliability". Was he simply being provocative? In a world witnessing AI developing at breakneck speeds, it is likely that it will be used widely to deal with major social, environmental or health challenges, like the current pandemic. Can we accept that the tools used are not understood by humans? Can we fight effectively against a pandemic if we simply know what is going to happen, but do not understand why? Do these few sentences, which completely go against the comments made previously by Alain Connes, completely deny mathematics' involvement in the implementation of these AI tools? Does this not deny the importance of mathematical theory?

To conclude, I would say that mathematics does not have a choice and must be included in the major socio-environmental and health challenges which we are facing. It must be included, because it contributes additional skills to other scientific fields, and in the field of AI which is itself involved, the responsibility of understanding why certain systems "work" relies on it. Over time, I am convinced that "doing without understanding" can only be a victim of its excessive ambition if it wants to interfere in all decision-making processes. Only systems which the human is able to understand and therefore control would survive long-term. Mathematics must also be involved because it otherwise risks being exploited by those who "use" it without understanding it, and potentially used to back up crucial decisions. It must be involved, without the illusion of offering absolute truth. As noted by Jacques Austruy7 in the 1960s, a period when the craze for structuralism encouraged combinatorial and topological formalisations of the world, "[...] whilst mathematics is a precise language, it is not as neutral a language as mathematicians sometimes believe".

The Santa Fe Institute was founded in 1984. https://www.santafe.edu

https://www.canal-u.tv/video/fmsh/les_donnees_en_shs_quelle_politique_bernard_stiegler.21150

see for example https://epidemap.com/

Mitchell, M. (2019). Artificial Intelligence Hits the Barrier of Meaning. Information, 10(2),

1982 Fields Medal, 2001 Crafoord Prize, 2004 CNRS Gold Medal.

Austruy, J. (1961). Methodes mathematiques et sciences de l'homme. Revue économique, 12(3), 414-439.