Pascal Bianchi

Olivier Fercoq

Using Big Steps in Coordinate Descent Primal-Dual Algorithms

The V ũ-Condat algorithm is a standard method for finding a saddle point of a Lagrangian involving a differentiable function. Recent works have tried to adapt the idea of random coordinate descent to this algorithm, with the aim to efficiently solve some regularized or distributed optimization problems. A drawback of these approaches is that the admissible step sizes can be small, leading to slow convergence. In this paper, we introduce a coordinate descent primal-dual algorithm which is provably convergent for a wider range of step size values than previous methods. In particular, the condition on the step-sizes depends on the coordinate-wise Lipschitz constant of the differentiable function's gradient. We discuss the application of our method to distributed optimization and large scale support vector machine problems.

I. INTRODUCTION

In applications such as machine learning or multiagent systems, one is often faced with the issue of solving large scale optimization problems containing both differentiable and non-differentiable terms. In this context, random coordinate descent (CD) algorithms are amongst the most popular approaches. They consist in updating only a subset of the components of the estimate at each iteration, the other coordinates being maintained to their past value. Not only it is often computationally easier to evaluate a single coordinate of the gradient vector rather than the whole vector, but the conditions under which the CD version of the algorithm is provably convergent are generally weaker than in the case of their deterministic counterpart. For instance, in the CD version of the gradient descent [START_REF] Nesterov | Efficiency of coordinate descent methods on hugescale optimization problems[END_REF] (or its proximal variant [START_REF] Richtárik | Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function[END_REF]), the step size used in the algorithm when updating a given coordinate i can be chosen to be inversely proportional to the coordinate-wise Lipschitz constant of the differentiable function along its ith coordinate, rather than the global Lipschitz constant (as would be the case in a standard gradient descent). Hence, the introduction of coordinate descent allows to use longer step sizes which results in a more attractive performance.

There is a rich literature on CD version of primal methods. Richtárik and Takáč [START_REF] Richtárik | Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function[END_REF] apply CD to the minimization of a sum of two convex functions f + g. The algorithm of [START_REF] Richtárik | Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function[END_REF] is analyzed under the additional assumption that function g is separable in the sense that for each x ∈ X , g(x) = n i=1 g i (x (i) ) for some functions g i : X i →] -∞, +∞], where x (i) stands for the ith coordinate of x.

Comparatively, less work has been done regarding the application of CD to primal dual methods i.e., when one seeks LTCI, CNRS, Télécom ParisTech, Université Paris-Saclay, 75013, Paris,

France. E-mails: forename.name@telecom-paristech.fr.

This work has been supported by the Orange/Telecom ParisTech think tank Phi-TAB and the ANR project ODISSEE to find a saddle point of the Lagrangian. In the case where the optimization problem contains a separable and a strongly convex function, Zhang and Xiao [START_REF] Zhang | Stochastic primal-dual coordinate method for regularized empirical risk minimization[END_REF] introduce a stochastic CD primal-dual algorithm and analyze its convergence rate. In 2013, Iutzeler et al. [START_REF] Iutzeler | Asynchronous distributed optimization using a randomized alternating direction method of multipliers[END_REF] proved that random coordinate descent can be successfully applied to fixed point iterations of firmly non-expansive (FNE) operators. It is known that the ADMM can be written as a fixed point algorithm of a FNE operator, which led the authors of [START_REF] Iutzeler | Asynchronous distributed optimization using a randomized alternating direction method of multipliers[END_REF] to propose a coordinate descent version of ADMM with application to distributed optimization. The key idea behind the convergence proof of [START_REF] Iutzeler | Asynchronous distributed optimization using a randomized alternating direction method of multipliers[END_REF] is to establish the so-called stochastic Fejér monotonicity of the sequence of iterates as noted by [START_REF] Patrick | Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping[END_REF]. In a more general setting than [START_REF] Iutzeler | Asynchronous distributed optimization using a randomized alternating direction method of multipliers[END_REF], Combettes et al. in [START_REF] Patrick | Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping[END_REF] and Bianchi et al. [START_REF] Bianchi | A stochastic coordinate descent primal-dual algorithm and applications to largescale composite optimization[END_REF] extend the proof to the so-called α-averaged operators, which include FNE operators as a special case. This generalization allows to apply the coordinate descent principle to a broader class of primal-dual algorithms which is no longer restricted to the ADMM or the Douglas Rachford algorithm. For instance, Forward-Backward splitting is considered in [START_REF] Patrick | Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping[END_REF] and a particular case of the Vũ-Condat algorithm is considered in [START_REF] Bianchi | A stochastic coordinate descent primal-dual algorithm and applications to largescale composite optimization[END_REF].

However, in the approach of [START_REF] Iutzeler | Asynchronous distributed optimization using a randomized alternating direction method of multipliers[END_REF], [START_REF] Patrick | Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping[END_REF], [START_REF] Bianchi | A stochastic coordinate descent primal-dual algorithm and applications to largescale composite optimization[END_REF] the convergence conditions are identical to the ones of the brute method, the one without coordinate descent. These conditions involve the global Lipschitz constant of the gradient the differentiable term instead than its coordinate-wise Lipschitz constants. In practice, it means that the application of coordinate descent to primal-dual algorithm as suggested by [START_REF] Patrick | Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping[END_REF] and [START_REF] Bianchi | A stochastic coordinate descent primal-dual algorithm and applications to largescale composite optimization[END_REF] is restricted to the use of potentially small step sizes. One of the major benefits of coordinate descent is lost.

In this paper, we provide a CD primal-dual algorithm with a broader range of admissible step sizes. Our numerical experiments show that remarkable performance gains can be obtained when using larger step sizes. We review applications to asynchronous distributed optimization and machine learning.

The paper is organized as follows. In Section II, we formulate the problem. In Section III we review some applications to distributed optimization and to support vector machines (SVM). The main algorithm is introduced in SectionIV. The algorithm is instantiated in the case of distributed optimization in Section V. Numerical experiments are provided in Section VI in the case of SVM.

II. OPTIMIZATION FRAMEWORK

We consider the optimization problem

inf x∈X f (x) + g(x) + h(M x) (1)
where X is a Euclidean space, M : X → Y is a linear operator onto a second Euclidean space Y; functions f : X → R, g : X → (-∞, +∞] and h : Y →] -∞, +∞] are assumed proper, closed and convex; the function f is moreover assumed differentiable. We assume that X and Y are product spaces of the form

X = X 1 × • • • × X n and Y = Y 1 ו • •×Y p
for some integers n, p. For any x ∈ X , we use the notation x = (x (1) , . . . , x (n) ) to represent the (block of) coordinates of x (similarly for y = (y (1) , . . . , y (p) ) in Y).

Under the standard qualification condition 0 ∈ ri(M domgdomh) (where dom and ri stand for domain and relative interior, respectively), a point x ∈ X is a minimizer of (1) if and only if there exists y ∈ Y such that (x, y) is a saddle point of the Lagrangian function

L(x, y) = f (x) + g(x) + y, M x -h (y)
where . , . is the inner product and h : y → sup z∈Y y, z -h(z) is the Fenchel-Legendre transform of h.

Vũ [START_REF] Bang | A splitting algorithm for dual monotone inclusions involving cocoercive operators[END_REF] and Condat [START_REF] Condat | A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms[END_REF] separately proposed a primal-dual algorithm allowing to handle f explicitly, and requiring one evaluation of the gradient of f at each iteration. The algorithm can be also be casted into a more general formalism [START_REF] Davis | A three-operator splitting scheme and its optimization applications[END_REF], [START_REF] Latafat | Asymmetric forward-backwardadjoint splitting for solving monotone inclusions involving three operators[END_REF].

III. APPLICATIONS A. Distributed Optimization

Consider a set of n > 1 computing agents that cooperate to solve the minimization problem

inf u∈R d n i=1 (f i (u) + g i (u)) (2)
where d ≥ 1 is an integer and where f i , g i are two private cost functions available at Agent i. Typically, f i represents a differentiable data fitting term corresponding to the data locally accessible at node i, while g i represents a regularization term. Here, the purpose is to design a distributed iterative algorithm where at a each iteration, each active agent updates a local estimate in the parameter space X based on the sole knowledge of this agent's private cost functions and on an information it received from its neighbors through some communication network. Eventually, the local estimates will converge to a common value (or consensus) which is a minimizer (assumed to exist) of the aggregate cost function of Problem [START_REF] Richtárik | Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function[END_REF]. In practice, it is assumed that the agents are able to exchange information over a certain communication graph G = (V, E) where V = {1, . . . , n} represents the set of agents and where E is a set of undirected edges such that {i, j} ∈ E if and only if the agents i and j are likely to communicate. As noted by [START_REF] Bianchi | A stochastic coordinate descent primal-dual algorithm and applications to largescale composite optimization[END_REF], the problem ( 2) is an instance of the general problem (1) by setting X = (R d ) ⊗N and for every n) and to +∞ otherwise. We briefly recall the specific choice h and M leading to a distributed algorithm (see [START_REF] Bianchi | A stochastic coordinate descent primal-dual algorithm and applications to largescale composite optimization[END_REF] for more details).

x ∈ X , f (x) = n i=1 f i (x (i) ), g(x) = n i=1 g i (x (i) ) and finally h(M x) is chosen as an indicator function equal to zero if x (1) = • • • = x (
The idea is to ensure consensus separately over all the edges of the graph. This way, the constraints are localized at the edge level, but are equivalent to global consensus as soon as G is connected. Mathematically, for any e = {i, j} ∈ E, let M e be the linear operator from X to R d × R d such that M e x = (x (i) , x (j) ) for any x ∈ X (here we assume some implicit ordering of the nodes). Define M as the linear operator generated by stacking vertically the (M e ) e∈E , that is M : X → Y where Y = (R d × R d ) |E| . For every y ∈ Y, decompose y as (y e ) e∈E where each y e ∈ R d × R d is a pair of vectors of R d . Denote by h(y) the function equal to zero if every pair y e has its two components equal, and to zero otherwise. As made clear in [START_REF] Bianchi | A stochastic coordinate descent primal-dual algorithm and applications to largescale composite optimization[END_REF], the quantity h(M x) is equal to zero if x has all its components equal and to +∞ otherwise, as soon as G is connected. Hence, the problem (2) can be casted into the form [START_REF] Nesterov | Efficiency of coordinate descent methods on hugescale optimization problems[END_REF].

By applying the Vũ-Condat algorithm on that problem, [START_REF] Bianchi | A stochastic coordinate descent primal-dual algorithm and applications to largescale composite optimization[END_REF] obtains a distributed proximal gradient algorithm, which they call DADMM+. Applying on the top of that the idea of coordinate descent, they may choose to update at each iteration only the subset of coordinates which are physically handled by a sole agent, chosen at random. This approach has the advantage of making the algorithm asynchronous: at each time n, an agent picked at random wakes up, updates its own variables and sends the result of its computation to its neighbors in the graph.

The drawback of the algorithm lies in its convergence conditions. The conditions on the step size are related to the global Lipschitz constant of the gradient of f (x) = n i=1 f i (x (i) ) and the minimum node-degree in the graph. First, these constants are by definition unknown (recall that each function f i is only known by Agent i). Second, the step size are limited by the Agent having the worst local Lipschitz constant, and by the smallest node degree. In this paper, we prove that these convergence conditions are too conservative, and establish that each Agent might select its local step size as a function of its own local Lipschitz constant and its own degree.

B. Support Vector Machines

We consider a set of n observations gathered into a data matrix A ∈ R m×n and labels b ∈ R n and we intend to solve the following Support Vector Machine (SVM) problem:

min w∈R m ,w0∈R n i=1 C i max 0, 1 -b i ((A w) i + w 0 ) + λ 2 w 2 2
where C 1 , . . . , C n are positive weights typically allowing to cope with potentially unbalanced classes. As is common practice for this problem, we solve instead the Dual Support Vector Machine problem:

max x∈R n - 1 2λ AD(b)x 2 2 + e T x - n i=1 I [0,Ci] (x i ) -I b ⊥ (x)
where D(b) is the diagonal matrix containing the labels, e is the vector whose components are all equal to one, I S is the indicator function of a set S (equal to zero on that set, to +∞ outside) and b ⊥ is the orthogonal space to the linear span of the vector b. Some authors proposed to fix the bias w 0 to 0 in order to make the problem easier to solve [START_REF] Shalev | Stochastic dual coordinate ascent methods for regularized loss minimization[END_REF]. Here, we intend to solve the initial problem with a non-zero bias. Setting

f (x) = 1 2 AD(b)x 2 2 -e T x, g(x) = n i=1 I [0,Ci] (x i ), h(y) = I b ⊥ (y)
and M = I, the problem falls again into the formulation [START_REF] Nesterov | Efficiency of coordinate descent methods on hugescale optimization problems[END_REF].

Other application examples are provided in [START_REF] Fercoq | A coordinate descent primal-dual algorithm with large step size and possibly non separable functions[END_REF].

IV. MAIN ALGORITHM

A. Notation

We note M = (M j,i : i ∈ {1, . . . , n}, j ∈ {1, . . . , p}) where M j,i : X i → Y j are the block components of M . For each j ∈ {1, . . . , p}, we introduce the set

I(j) := i ∈ {1, . . . , n} : M j,i = 0 .
Otherwise stated, the jth component of vector M x only depends on x through the coordinates x (i) such that i ∈ I(j). We denote by m j := card(I(j))

the number of such coordinates. Without loss of generality, we assume that m j = 0 for all j. For all i ∈ {1, . . . , n}, we define

J(i) := j ∈ {1, . . . , p} : M j,i = 0 .
Note that for every pair (i, j), the statements i ∈ I(j) and

j ∈ J(i) are equivalent. Recall that Y = Y 1 × • • • × Y p .
For every j ∈ {1, . . . , p}, we use the notation Y j := Y I(j) j

. An arbitrary element u in Y j will be represented by u = (u(i) : i ∈ I(j)). We define Y := Y 1 × • • • × Y p . An arbitrary element y in Y will be represented as y = (y (1) , . . . , y (p) ). This notation is recalled in Table I

Space Element

X = X 1 × • • • × Xn x = (x (i) : i ∈ {1, . . . , n}) Y = Y 1 × • • • × Yp y = (y (j) : j ∈ {1, . . . , p}) Y j = Y I(j) j u = (u(i) : i ∈ I(j)) Y = Y 1 × • • • × Y p y = (y (j) : j ∈ {1, . . . , p}) where y (j) = (y (j) (i) : i ∈ I(j)) ∀j If is an integer, γ = (γ 1 , . . . ,

γ ) is a collection of positive real numbers and A

= A 1 × • • • × A is a product of Euclidean spaces, we introduce the weighted norm . γ on A given by u 2 γ = i=1 γ i u (i) 2
Ai for every u = (u (1) , . . . , u ( ) ) where . Ai stand for the norm on A i . If F : A →] -∞, +∞] denotes a convex proper lower-semicontinuous function, we introduce the proximity operator prox γ,F : A → A defined for any u ∈ A by prox γ,F (u) := arg min w∈A

F (w) + 1 2 w -u 2 γ -1
where we use the notation γ -1 = (γ -1 1 , . . . , γ -1 ). We denote by prox

(i) γ,F : A → A i the ith coordinate mapping of prox γ,F that is, prox γ,F (u) = (prox (1)
γ,F (u), . . . , prox ( ) γ,F (u)) for any u ∈ A. The notation D A (γ) (or simply D(γ) when no ambiguity occurs) stands for the diagonal operator on A → A given by D A (γ)(u) = (γ 1 u (1) , . . . , γ u ( ) ) for every u = (u (1) , . . . , u ( ) ).

Finally, the adjoint of a linear operator B is denoted B . The spectral radius of a square matrix A is denoted by ρ(A).

B. Algorithm

Consider Problem [START_REF] Nesterov | Efficiency of coordinate descent methods on hugescale optimization problems[END_REF]. Let σ = (σ 1 , . . . , σ p ) and τ = (τ 1 , . . . , τ n ) be two tuples of positive real numbers. Consider an independent and identically distributed sequence (i k : k ∈ N * ) with uniform distribution on {1, . . . , n}. The proposed primal-dual CD algorithm consists in updating four sequences

x k ∈ X , w k ∈ X , z k ∈ Y and y k ∈ Y. It is provided in Algorithm 1 below. Algorithm 1 Coordinate-descent primal-dual algorithm Initialization: Choose x 0 ∈ X , y 0 ∈ Y.
For all i ∈ {1, . . . , n}, set w

(i) 0 = j∈J(i) M j,i y (j) 0 (i).
For all j ∈ {1, . . . , p}, set z

(j) 0 = 1 mj i∈I(j) y (j) 0 (i).
Iteration k: Define:

y k+1 = prox σ,h z k + D(σ)M x k x k+1 = prox τ,g x k -D(τ ) ∇f (x k ) + 2M y k+1 -w k .
For i = i k+1 and for each j ∈ J(i k+1 ), update:

x (i) k+1 = x (i) k+1 y (j) k+1 (i) = y (j) k+1 w (i) k+1 = w (i) k + j∈J(i) M j,i (y (j) k+1 (i) -y (j) k (i)) z (j) k+1 = z (j) k + 1 m j (y (j) k+1 (i) -y (j) k (i)) . Otherwise, set x (i) k+1 = x (i) k , w (i) k+1 = w (i) k , z (j) k+1 = z (j)
k and y (j)

k+1 (i) = y (j) k (i).
Remark. In Algorithm 1, it is worth noting that quantities (x k+1 , y k+1 ) do not need to be explicitly calculated. At iteration k, only the coordinates

x (i k+1 ) k+1
and y (j) k+1 , ∀j ∈ J(i k+1 ) are needed to perform the update. When g is separable, it can be easily checked that other coordinates do not need to be computed. From a computational point of view, it is often the case that the evaluation of the above coordinates is less demanding than the computation of the whole vectors x k+1 , y k+1 . Practical examples are provided in Section VI.

For every i ∈ {1, . . . , n}, we denote by U i : X i → X the linear operator such that all coordinates of U i (u) are zero except the ith coordinate which coincides with u: U i (u) = (0, • • • , 0, u, 0, • • • , 0). Our convergence result holds under the following assumptions. b) The function f is differentiable on X . c) For every i ∈ {1, . . . , n}, there exists β i ≥ 0 such that for any x ∈ X , any u ∈ X i ,

f (x + U i u) ≤ f (x) + ∇f (x), U i u + β i 2 u 2 Xi .
d) The random sequence (i k ) k∈N * is independent with uniform distribution on {1, . . . , n}. e) For every i ∈ {1, . . . , n}, τ i < 1

β i + ρ j∈J(i) m j σ j M j,i M j,i
.

We denote by S the set of saddle points of the Lagrangian function L. Otherwise stated, a couple (x * , y * ) ∈ X × Y lies in S if and only if it satisfies the following inclusions

0 ∈ ∇f (x * ) + ∂g(x * ) + M y * (3) 0 ∈ -M x * + ∂h (y * ) . (4)
We shall also refer to elements of S as primal-dual solutions.

Theorem 4.2: Let Assumption 4.1 hold true and suppose that S = ∅. Let (x k , y k ) be a sequence generated by Algorithm 1. Almost surely, there exists (x * , y * ) ∈ S s.t.

lim k→∞ x k = x * lim k→∞ y (j) k (i) = y (j) * (∀j ∈ {1, . . . , p}, ∀i ∈ I(j)) .
The proof of the following Theorem is found in [START_REF] Fercoq | A coordinate descent primal-dual algorithm with large step size and possibly non separable functions[END_REF]. It is worth noting that, under the stated assumption on the stepsize, the stochastic Fejér monotonicity of the sequence of iterates, which is the key idea in [START_REF] Iutzeler | Asynchronous distributed optimization using a randomized alternating direction method of multipliers[END_REF], [START_REF] Patrick | Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping[END_REF], [START_REF] Bianchi | A stochastic coordinate descent primal-dual algorithm and applications to largescale composite optimization[END_REF], does not hold (a counter-example is provided in [START_REF] Fercoq | A coordinate descent primal-dual algorithm with large step size and possibly non separable functions[END_REF]). Our proof is different and relies on the introduction of an adequate Lyapunov function.

Remark. A quite similar algorithm was proposed by [START_REF] Pesquet | A class of randomized primal-dual algorithms for distributed optimization[END_REF], unfortunately we have not been able to understand the convergence proof. Moreover, the algorithm of [START_REF] Pesquet | A class of randomized primal-dual algorithms for distributed optimization[END_REF] uses small step sizes which yields potentially slow convergence phenomena as discussed in [START_REF] Fercoq | A coordinate descent primal-dual algorithm with large step size and possibly non separable functions[END_REF].

C. Special Cases 1) The Case m 1 = • • • = m p = 1: We consider the special case m 1 = • • • = m p = 1.
Otherwise stated, the linear operator M has a single nonzero component M j,i per row j ∈ {1, . . . , p}.

For each j ∈ {1, . . . , p}, the vector y (j) k is reduced to a single value y (j) k (i) ∈ Y j where i is the unique index such that M j,i = 0. We simply denote this value by y (j) k . Algorithm 1 simplifies to Algorithm 2 below.

2) The Case h = 0: Instanciating Algorithm 1 in the special case h = 0, it boils down to the following CD forward-backward algorithm:

x (i) k+1 = prox (i) τ,g x k -D(τ )∇f (x k ) , if i = i k+1 , x (i) k , otherwise. (5)
Algorithm 2 Coordinate-descent primal-dual algorithm -Case

m 1 = • • • = m p = 1. Initialization: Choose x 0 ∈ X , y 0 ∈ Y.
Iteration k: Define:

y k+1 = prox σ,h y k + D(σ)M x k x k+1 = prox τ,g x k -D(τ ) ∇f (x k ) + M (2y k+1 -y k ) .
For i = i k+1 and for each j ∈ J(i k+1 ), update:

x (i) k+1 = x (i) k+1 y (j) k+1 = y (j) k+1 .
Otherwise, set x

(i) k+1 = x (i) k ,y (j) k+1 = y (j) k .
As a consequence, Algorithm 1 allows to recover the CD proximal gradient algorithm of [START_REF] Richtárik | Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function[END_REF] with the notable difference that we do not assume the separability of g. On the other hand, Assumption 4.1(e) becomes τ i < 1/β i whereas in the separable case, [START_REF] Richtárik | Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function[END_REF] assumes τ i = 1/β i .

V. APPLICATION TO DISTRIBUTED OPTIMIZATION

We apply our algorithm to the special instance described in Section III-A. Here our approach is identical to the one of [START_REF] Bianchi | A stochastic coordinate descent primal-dual algorithm and applications to largescale composite optimization[END_REF] (the difference with [START_REF] Bianchi | A stochastic coordinate descent primal-dual algorithm and applications to largescale composite optimization[END_REF] lies in the convergence condition). We will therefore skip the technical details behind the instanciation of the random coordinate descent and directly provide the algorithm, we refer the interested reader to [START_REF] Fercoq | A coordinate descent primal-dual algorithm with large step size and possibly non separable functions[END_REF].

The Distributed Asynchronous Primal Dual Algorithm (DAPD) method is described in Algorithm 3. The notation N i stands for the neighborhood of a node i in the graph and d i is the degree of node i.

Algorithm 3 DAPD.

Initialization: Each node i ∈ {1, . . . , n} chooses x (i) 0 and (λ (i,j) 0 Theorem 5.1: Assume that G is connected and that (2) has a minimizer. Assume that the sequence of active nodes (i k ) k∈N * is iid and uniformly distributed. Assume that for every i = 1, . . . , n, ∇f i is L i -Lipschitz continuous and

: j ∈ N i ) Iteration k: A node i = i k+1 wakes up uniformly at random λ (i,j) k+1 = λ (i,j) k -λ (j,i) k 2 + x (i) k -x (j) k 2ρ x (i) k+1 = prox τigi/di x (i) k - τ i d i ∇f i (x (i) k ) + τ i ∆ (i) k where ∆ (i) k = d -1 i j∈Ni (λ (j,i) k + ρ -1 (x (j) k -x (i) k )). Node i communicates x (i)
τ i -1 -ρ -1 > L i d i (6)
where d i is the degree of node i. Then, almost surely and for any initial value, there exists a minimizer x of (2) such that for every i = 1, . . . , n, the sequence x (i) k generated by the DAPD converges almost surely to a x . We now compare this result with [START_REF] Bianchi | A stochastic coordinate descent primal-dual algorithm and applications to largescale composite optimization[END_REF]. In [START_REF] Bianchi | A stochastic coordinate descent primal-dual algorithm and applications to largescale composite optimization[END_REF], the same step τ 1 = • • • = τ n = τ was used for all Agents and the convergence condition was τ -1 -ρ -1 > maxi Li 2 mini di . Apart from the factor 2, the condition (6) on the step size is generally milder and allows for larger step sizes. In addition, the conditions only involve parameters that are local.

VI. NUMERICAL EXPERIMENT

We used one processor of a computer with Intel Xeon CPUs at 2.80GHz. In the experiment 1 , we consider the SVM problem discussed in Section III-B. We consider the the RCV1 dataset where A is a sparse m × n matrix with m = 20,242, n = 47,236 and 0.157 % of nonzero entries and we take C i = 1 n for all i and λ = 1 4n . For this dataset, A 2 ≈ 40 max i Ae i 2 , which means that using small step sizes would lead to a roughly 40 times slower algorithm. This situation is not uncommon and is one of the reasons why coordinate descent methods are attractive. We compare our method with

• SCDA [START_REF] Shalev | Stochastic dual coordinate ascent methods for regularized loss minimization[END_REF]: note that SDCA simply forgets I b ⊥ (x) in order to be able to apply the classical coordinate descent method a thus will not converge to an optimal solution. • RCD [START_REF] Necoara | A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints[END_REF]: at each iteration, the algorithm selects two coordinates randomly and performs a coordinate descent step according to these two variables. Updating two variables at a times allows us to satisfy the linear constraint at each iteration. We can see on Figure 1 the decrease of the SVM duality gap for each algorithm. SDCA is very efficient in the beginning and converges quickly. However, as the method does not take into account the intercept, it does not converge to the optimal solution and stagnates after a few passes on the data. Algorithm 1 allows step sizes nearly as long as SDCA's and taking into account the coupling constraint represents only marginal additional work. Hence, the objective value decreases nearly as fast for SDCA in the beginning without sacrificing the intercept, leading to a smaller objective value in the end. The RCD method of [START_REF] Necoara | A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints[END_REF] does work but is not competitive in terms of speed of convergence. We also tried the C implementation of LIBSVM but it needed 175s to solve the (medium-size) RCV1 problem. Fig. 1. Comparison of dual algorithms for the resolution of linear SVM on the RCV1 dataset. We report the value of the duality gap after a postprocessing to recover feasible primal and dual variables. Primal variables are recovered as suggested in [START_REF] Shalev | Stochastic dual coordinate ascent methods for regularized loss minimization[END_REF] and the intercept is recovered by exact minimization of the primal objective given the other primal variables. When dual iterates are not feasible, we project them onto the dual feasible set before computing the dual objective. We stopped each algorithm after 100 passes through the data.

  Assumption 4.1: a) The functions f , g, h are closed proper and convex.

  k+1 and λ (i,j) k+1 to each neighbor j All nodes = i do not modify their iterates x