Antonin Chambolle
email: antonin.chambolle@cmap.polytechnique.fr

Thomas Pock
email: pock@icg.tugraz.at

On the ergodic convergence rates of a first-order primal-dual algorithm

Keywords: MSC Classification: 49M29 65K10 65Y20 90C25 Saddle-point problems, first order algorithms, primal-dual algorithms, convergence rates, ergodic convergence

We revisit the proofs of convergence for a first order primal-dual algorithm for convex optimization which we have studied a few years ago. In particular, we prove rates of convergence for a more general version, with simpler proofs and more complete results. The new results can deal with explicit terms and nonlinear proximity operators in spaces with quite general norms.

Introduction

In this work we revisit a first-order primal-dual algorithm which was introduced in [START_REF] Pock | An algorithm for minimizing the Mumford-Shah functional[END_REF][START_REF] Esser | A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science[END_REF] and its accelerated variants which were studied in [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF]. We derive new estimates for the rate of convergence. In particular, exploiting a proximal-point interpretation due to [START_REF] He | Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective[END_REF], we are able to give a very elementary proof of an ergodic O(1/N ) rate of convergence (where N is the number of iterations), which also generalizes to non-linear norms [START_REF] Hohage | A generalization of the Chambolle-Pock algorithm to Banach spaces with applications to inverse problems[END_REF], to overrelaxed [START_REF] He | Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective[END_REF][START_REF] Condat | A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms[END_REF] and inertial [START_REF] Lorenz | An inertial forward-backward algorithm for monotone inclusions[END_REF] variants. In the second part, we give new, more precise estimates of the convergence rate for the accelerated variants of the algorithm. We conclude the paper by showing the practical performance of the algorithm on a number of randomly generated standard optimization problems.

The new proofs we propose easily incorporate additional smooth terms such as considered in [START_REF] Condat | A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms[END_REF][START_REF] Àng | A splitting algorithm for dual monotone inclusions involving cocoercive operators[END_REF] (where convergence is already been proved, without rates), and [START_REF] Bot | On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems[END_REF] (where the proofs of [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF] are extended to the framework of [START_REF] Àng | A splitting algorithm for dual monotone inclusions involving cocoercive operators[END_REF] which considers general monotone operators-in this setting one must also mention the recent work [START_REF] Davis | A three-operator splitting scheme and its optimization applications[END_REF] for a Douglas-Rachford approach to the same problem, with a slightly different algorithm also presenting very good convergence properties). Also, a very recent work of Drori, Sabach and Teboulle, establishes similar results on a closely related primal-dual ("PAPC") algorithm [START_REF] Drori | A simple algorithm for a class of nonsmooth convex-concave saddle-point problems[END_REF], which also handles explicit terms, but cannot jointly handle (without further splitting) nonsmooth functions in both the primal and dual variables.

We must observe that in addition, our proofs carry on to the nonlinear (or Banach space) setting. They can indeed take into account without effort non-linear proximity operators, based on Bregman distance functions (except in the accelerated variables of the accelerated schemes), in the spirit of the "Mirror-descent" methods introduced by Nemirovski and Yudin [START_REF] Arkadi | Problem complexity and method efficiency in optimization[END_REF]. These were extensively studied by many authors, see in particular [START_REF] Teboulle | Entropic proximal mappings with applications to nonlinear programming[END_REF][START_REF] Chen | Convergence analysis of a proximal-like minimization algorithm using Bregman functions[END_REF][START_REF] Beck | Mirror descent and nonlinear projected subgradient methods for convex optimization[END_REF], and [START_REF] Arkadi | Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems[END_REF] in a primal-dual framework. See also [START_REF] Patrick | A forward-backward view of some primal-dual optimization methods in image recovery[END_REF][START_REF] Pesquet | A class of randomized primal-dual algorithms for distributed optimization[END_REF] for recent advances on such primal-dual algorithms, including stochastic versions. On the other hand, in the standard Euclidean setting, the algorithm we study can be shown to be a particular linearized variant of the ADMM algorithm for which a convergence theory, with more precise results, is found in [START_REF] Shefi | Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex minimization[END_REF]. We should add that the relationship between the type of algorithms which we study here and the ADMM was already stressed in [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF] and that, in particular, one can derive from the analysis in [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF] and in this paper convergence rates for the ADMM which are different from the ones currently found in the literature, see for instance [START_REF] He | On the O(1/n) convergence rate of the Douglas-Rachford alternating direction method[END_REF].

We are addressing the following problem

min x∈X max y∈Y L(x, y) = Kx, y + f (x) + g(x) -h * (y) , (1)
which is the convex-concave saddle-point form of the "primal" minimization problem

min x∈X f (x) + g(x) + h(Kx) . (2)
Here, X and Y are, in the most general setting, real reflexive Banach spaces endowed with corresponding norms • x and • y . Note however that in this setting it is quite restrictive to assume that K is bounded, so that the reader could assume that they are finite-dimensional.

The only point where it matters is the fact that the estimates we compute never involve the dimension of the current spaces, except possibly through quantities such as K . For notational simplicity, we will drop the subscript for the norms whenever there is no ambiguity. The dual spaces (spaces of all continuous linear functionals) are denoted by X * , and Y * . For x * ∈ X * and x ∈ X , the bilinear form x * , x gives the value of the function x * at x. Similar, for y * ∈ Y * and y ∈ Y, y * , y gives the value of the function y * at y. The norms of the dual spaces are defined as x * * = sup

x ≤1

x * , x , y * * = sup y ≤1 y * , y .

By definition, we also have that

x * , x ≤ x • x * * , y * , y ≤ y • y * * .
We further assume that the following assumptions are fulfilled:

(i) K : X → Y * is a bounded linear operator, with corresponding adjoint operator K * : Y → X * defined by Kx, y = K * y, x ∀(x, y) ∈ X × Y.

Throughout the whole paper we will keep the notation "L" for the norm of this operator, defined by

L := K = sup x ≤1, y ≤1
Kx, y = sup

x ≤1 Kx * = K * = sup y ≤1 K * y * .
Hence, we also have that Kx, y ≤ Kx * y ≤ L x y , K * y, x ≤ K * y * x ≤ L x y .

For example, let • x = • p and • y = • q , with p, q ≥ 1, i.e. the usual p norms, then

K = sup x p ≤1
Kx q = sup y q ≤1 K * y p = sup

x p ≤1 y q ≤1
Kx, y , with p , q such that 1/p + 1/p = 1, and 1/q + 1/q = 1.

(ii) f is a proper, lower semicontinuous (l.s.c.), convex function, with ∇f Lipschitz continuous on

X , i.e. ∇f (x) -∇f (x ) * ≤ L f x -x , ∀x, x ∈ X ;
(iii) g, h are proper, l.s.c., convex functions with simple structure, in the sense that their proximal maps min

x g(x) + 1 τ D x (x, x) , min y h * (y) + 1 σ D y (y, ȳ) ,
can be computed for any τ, σ > 0.

Here D x and D y are Bregman proximity/distance functions based on 1-strongly convex (w.r.t. the respective norms) functions ψ x and ψ y , defined by

D x (x, x) = ψ x (x) -ψ x (x) -∇ψ x (x), x -x , D y (y, ȳ) = ψ y (y) -ψ y (ȳ) -∇ψ y (ȳ), y -ȳ .
Following [START_REF] Eckstein | Nonlinear proximal point algorithms using bregman functions, with applications to convex programming[END_REF], we assume that ψ x , ψ y are continuously differentiable on open sets S x , S y , continuous on S x , S y , and that given any converging sequences (x n ) and (y n ),

x n → x ⇒ lim n→∞ D x (x, x n ) = 0, y n → y ⇒ lim n→∞ D y (y, y n ) = 0. (3)
We may of course assume that S x and S y are the respective domains of ψ x , ψ y . We need, in addition to [START_REF] Eckstein | Nonlinear proximal point algorithms using bregman functions, with applications to convex programming[END_REF], to assume the strong convexity of our functions to ensure the convergence of the algorithms studied in this paper. This restricts the possible class of Bregman functions, notice however that classical examples such as the entropy ψ x (x) = d i=1 x i log x i is well-known to be 1-strongly convex with respect to the 1-norm [START_REF] Beck | Mirror descent and nonlinear projected subgradient methods for convex optimization[END_REF][START_REF] Teboulle | Entropic proximal mappings with applications to nonlinear programming[END_REF] when restricted to the unit simplex, it is also strongly convex with respect to the 2-norm on bounded sets of (R + ) d . Eventually, we must assume here that dom g ⊆ dom ψ x = S x and dom h * ⊆ dom ψ y = S y .

Clearly, the Lipschitz continuity of f implies that

f (x ) ≤ f (x) + ∇f (x), x -x + L f 2 x -x 2 , ∀x, x ∈ X . (4)
Furthermore, the 1-strongy convexity of ψ x and ψ y easily implies that for any x, x and y, ȳ, it holds

D x (x, x) ≥ 1 2 x -x 2 , D y (y, ȳ) ≥ 1 2 y -ȳ 2 .
The most common choice for ψ x and ψ y is the usual squared Euclidean norm 1 2 • 2 2 (or Hilbertian in infinite dimension), which yields

D(x, x) = 1 2 x -x 2 2 .
We will refer to this classical case as the "Euclidean case" . In this case, it is standard that given a convex, l.s.c. function φ, if û is the minimizer of

φ(u) + 1 2 u -ū 2 2
(which we call the "Euclidean proximity map" of φ at ū), then by strong convexity one has for all u φ(u)

+ 1 2 u -ū 2 2 ≥ φ(û) + 1 2 û -ū 2 2 + 1 2 u -û 2 2 .
It turns out that this property is true also for non-Euclidean proximity operators, that is

û = arg min u φ(u) + D(u, ū) =⇒ ∀u, φ(u) + D(u, ū) ≥ φ(û) + D(û, ū) + D(u, û). ( 5
)
This is easily deduced from the optimality conditions for û, see [START_REF] Chen | Convergence analysis of a proximal-like minimization algorithm using Bregman functions[END_REF][START_REF] Tseng | On accelerated proximal gradient methods for convex-concave optimization[END_REF]. Before closing this section, we point out that most of our results still hold, if the function h is a convex l.s.c. function of the form [START_REF] Àng | A splitting algorithm for dual monotone inclusions involving cocoercive operators[END_REF][START_REF] Bot | On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems[END_REF][START_REF] Lorenz | An inertial forward-backward algorithm for monotone inclusions[END_REF] h(y) = min y1+y2=y h 1 (y 1 ) + h 2 (y 2 ), [START_REF] Chen | Convergence analysis of a proximal-like minimization algorithm using Bregman functions[END_REF] so that h * (y) = h * 1 (y) + h * 2 (y), h * 1 having simple structure while ∇h * 2 can be evaluated and is Lipschitz continuous with parameter L h * 2 . For the ease of presentation we will not consider this situation but we will mention when our results can be extended to this case.

The general iteration

Iteration: (x, ŷ) = PD τ,σ (x, ȳ, x, ỹ)    x = arg min x f (x) + ∇f (x), x -x + g(x) + Kx, ỹ + 1 τ D x (x, x) ŷ = arg min y h * (y) -K x, y + 1 σ D y (y, ȳ) . (7)
The main iterate of the class of primal-dual algorithms we consider in this paper is defined in [START_REF] Chen | Optimal primal-dual methods for a class of saddle point problems[END_REF]. It takes the points (x, ȳ) as well as the intermediate points (x, ỹ) as input and outputs the new points (x, ŷ). It satisfies the following descent rule: Lemma 1. If (7) holds, then for any x ∈ X and y ∈ Y one has

L(x, y) -L(x, ŷ) ≤ 1 τ D x (x, x) - 1 τ D x (x, x) - 1 τ D x (x, x) + L f 2 x -x 2 + 1 σ D y (y, ȳ) - 1 σ D y (y, ŷ) - 1 σ D y (ŷ, ȳ)+ + K(x -x), ỹ -ŷ -K(x -x), y -ŷ . ( 8
)
Proof. From the first line in the above iteration [START_REF] Chen | Optimal primal-dual methods for a class of saddle point problems[END_REF] and property [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF], it follows:

∇f (x), x + g(x) + Kx, ỹ + 1 τ D x (x, x) ≥ ∇f (x), x + g(x) + K x, ỹ + 1 τ D x (x, x) + 1 τ D x (x, x) .
Moreover, from the convexity of f and (4) it follows

f (x) ≥ f (x) + ∇f (x), x -x ≥ f (x) + ∇f (x), x -x - L f 2 x -x 2 .
Combining this with the previous inequality, we arrive at

f (x) + g(x) + 1 τ D x (x, x) + L f 2 x -x 2 ≥ f (x) + g(x) + K(x -x), ỹ + 1 τ D x (x, x) + 1 τ D x (x, x) . (9)
In the same way:

h * (y) + 1 σ D y (y, ȳ) ≥ h * (ŷ) -K x, ŷ -y + 1 σ D y (ŷ, ȳ) + 1 σ D y (y, ŷ) . (10)
Summing ( 9), [START_REF] Davis | A three-operator splitting scheme and its optimization applications[END_REF] and rearranging the terms appropriately, we obtain (8).

Non-linear primal-dual algorithm

In this section we address the convergence rate of the non-linear primal-dual algorithm shown in Algorithm 1: The elegant interpretation in [START_REF] He | Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective[END_REF] shows that by writing the algorithm in this form • Initialization: Choose (x 0 , y 0 ) ∈ X × Y, τ, σ > 0

• Iterations: For each n ≥ 0 let (x n+1 , y n+1 ) = PD τ,σ (x n , y n , 2x n+1 -x n , y n ) (11)
(which "shifts" the updates with respect to [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF]), in the Euclidean case, that is

• x = • y = • 2 ,
and

D x (x, x ) = 1 2 x -x 2 2 , D y (y, y ) = 1 2 y -y 2 2
, then it is an instance of the proximal point algorithm [START_REF] Rockafellar | Monotone operators and the proximal point algorithm[END_REF], up to the explicit term ∇f (x n ), since

K * + ∂g -K + ∂h * (z n+1 ) + M τ,σ (z n+1 -z n ) -∇f (x n ) 0 ,
where the variable z ∈ X × Y represents the pair (x, y), and the matrix M τ,σ is given by

M τ,σ = 1 τ I -K * -K 1 σ I , (12)
which is positive-definite as soon as τ σL 2 < 1. A proof of convergence is easily deduced. Moreover, since in our particular setting we never really use the machinery of monotone operators, and rely only on the fact that we are studying a specific saddle-point problem, the results are a bit improved: in particular we deal easily with the explicit term f and non-linear proximity operators.

Theorem 1. Let (x n , y n ), n = 0, . . . , N -1 be a sequence generated by the non-linear primaldual algorithm [START_REF] Drori | A simple algorithm for a class of nonsmooth convex-concave saddle-point problems[END_REF]. Let the step size parameters τ, σ > 0 be chosen such that for all x, x ∈ dom g and y, y ∈ dom h * it holds that

1 τ -L f D x (x, x ) + 1 σ D y (y, y ) -K(x -x ), y -y ≥ 0 . (13)
Then, for any (x, y) ∈ X × Y it holds that

L(X N , y) -L(x, Y N ) ≤ 1 N 1 τ D x (x, x 0 ) + 1 σ D y (y, y 0 ) -K(x -x 0 ), y -y 0 , ( 14
)
where

X N = 1 N N n=1
x n , and

Y N = 1 N N n=1 y n .
Proof. According to the iterative scheme [START_REF] Drori | A simple algorithm for a class of nonsmooth convex-concave saddle-point problems[END_REF], the estimate (8) becomes

L(x n+1 , y) -L(x, y n+1 ) ≤ 1 τ D x (x, x n ) + 1 σ D y (y, y n ) -K(x -x n ), y -y n - 1 τ D x (x, x n+1 ) + 1 σ D y (y, y n+1 ) -K(x -x n+1 ), y -y n+1 - 1 τ D x (x n+1 , x n ) + 1 σ D y (y n+1 , y n ) -K(x n+1 -x n ), y n+1 -y n - L f 2 x n+1 -x n 2 . ( 15
)
Thanks to [START_REF] Eckstein | Nonlinear proximal point algorithms using bregman functions, with applications to convex programming[END_REF], the terms in the brackets are non-negative. Now we sum the last estimate from n = 0, . . . , N -1 and find

N n=1 L(x n , y) -L(x, y n ) ≤ 1 τ D x (x, x 0 ) + 1 σ D y (y, y 0 ) -K(x -x 0 ), y -y 0 ,
where we have removed negative terms on the right hand side. Equation ( 14) follows from the convexity of (ξ, η) → L(ξ, y) -L(x, η).

Remark 1. Observe that since D x (•, x ) and D y (•, y ) are 1-convex, ( 13) is ensured as soon as

1 τ -L f 1 σ ≥ L 2 . ( 16
)
Remark 2. The rate (14) can also be written solely in terms of the distance functions D x and D y . In fact, for any α > 0,

| K(x -x 0 ), y -y 0 | ≤ L x -x 0 y -y 0 ≤ αL 2 x -x 0 2 + L 2α y -y 0 2 ≤ αLD x (x, x 0 ) + L α D y (y, y 0 ).
In case L f = 0, τ σL 2 = 1 and choosing α = 1/(τ L), the rate (14) becomes

L(X N , y) -L(x, Y N ) ≤ 2 N 1 τ D x (x, x 0 ) + 1 σ D y (y, y 0 ) . (17)
In the Euclidean setting, that is

• x = • y = • 2 = •, • 1 2 , and D(x, x ) = 1 2 x -x 2 2 , D(y, y ) = 1 2 y -y 2 2
, the estimate (15) reduces to

L(x n+1 , y) -L(x, y n+1 ) ≤ 1 2 z -z n 2 Mτ,σ - 1 2 z -z n+1 2 Mτ,σ - 1 2 z n+1 -z n 2 Mτ,σ + L f 2 x n+1 -x n 2 2 ,
with M τ,σ defined in [START_REF] Duchi | Efficient projections onto the 1 -ball for learning in high dimensions[END_REF]. This can also be rewritten as

L(x n+1 , y) -L(x, y n+1 ) ≤ z n+1 -z n , z -z n+1 Mτ,σ + L f 2 x n+1 -x n 2 2 ( 18
)
while the final estimate [START_REF] Eckstein | On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators[END_REF] becomes

L(X N , y) -L(x, Y N ) ≤ 1 2N z -z 0 2 Mτ,σ . (19)
Observe that this rate is different from the rate obtained in [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF], which does only depend on the diagonal part of M τ,σ (each rate can be bounded by twice the other).

Remark 3. If we assume in addition that the inequality τ σL 2 < 1 is strict (which follows from [START_REF] He | Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective[END_REF] if L f > 0, and has to be assumed else), then we can deduce as in [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF] convergence results for the algorithm, whenever a saddle-point z * = (x * , y * ) exists. The first thing to observe is that this inequality yields that

1 τ D x (x, x ) + 1 σ D y (y, y ) -K(x -x ), y -y ≥ α( x -x 2 + y -y 2 ) ( 20
)
for some α > 0. As a consequence, it follows from (15) that the sequence z n = (x n , y n ) is globally bounded (indeed, L(X N , y * ) -L(x * , Y N ) ≥ 0). Obviously, this also yields a bound for Z N = (X N , Y N ). We may thus assume that a subsequence (Z N k ) k weakly converges in X × Y to some Z = (X, Y ), and from ( 14) and the lower-semicontinuity of f, g, h * it follows that the limit Z is a saddle-point.

In finite dimension, we can also show the convergence of the whole sequences z n and Z N to the same saddle-point. The proof follows the proof in [START_REF] Pock | An algorithm for minimizing the Mumford-Shah functional[END_REF][START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF], in the linear case. Let us assume that z is a limit point for a subsequence (z n k ) k , then since [START_REF] Esser | A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science[END_REF] guaranties the summability of z n+1 -z n 2 , we have that also z n k ±1 → z. It follows that z is a fixed point of the algorithm and thus a saddle-point (which we now denote z * = (x * , y * )).

Let m ≥ 0 be the limit of the nonincreasing sequence

1 τ D x (x * , x n ) + 1 σ D y (y * , y n ) -K(x * -x n ), y * -y n ,
we wish to show that m = 0. Since

z n k → z * we deduce lim k→∞ 1 τ D x (x * , x n k ) + 1 σ D y (y * , y n k ) = m.
Using assumption (3), we deduce m = 0. The convergence of the global sequence follows from [START_REF] Arkadi | Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems[END_REF]. In Hilbert spaces of infinite dimension, the same proof shows weak convergence of the sequence for Euclidean proximity operators, invoking Opial's theorem [START_REF] Law | Weak convergence of the sequence of successive approximations for nonexpansive mappings[END_REF].

Remark 4. In the Euclidean setting and when g = 0, a better algorithm (in fact, optimal, see [START_REF] Arkadi | Problem complexity and method efficiency in optimization[END_REF][START_REF] Nesterov | Smooth minimization of non-smooth functions[END_REF]) is proposed in [START_REF] Chen | Optimal primal-dual methods for a class of saddle point problems[END_REF], which yields a rate of order O(L f /N 2 + L/N ).

Remark 5. In case h has the composite form ( 6), then the theorem still holds with the condition ( 16) replaced with

1 τ -L f 1 σ -L h * 2 ≥ L 2 . ( 21
)

Overrelaxed and inertial variants

In this section, we consider overrelaxed and inertial versions of the primal-dual algorithm. We will only consider the Euclidean setting, that is

• x = • y = • 2 = •, • 1 2 , and D(x, x ) = 1 2 x -x 2 2 , D(y, y ) = 1 2 y -y 2 2
, since our proofs heavily rely on the fact that • 2 2 = •, • .

Relaxed primal-dual algorithm

Algorithm 2: O(1/N ) Overrelaxed primal-dual algorithm

• Input: Operator norm L = K 2,2 , Lipschitz constant L f of ∇f , Bregman distance functions D(x, x ) = 1 2 x -x 2 2 , D(y, y ) = 1 2 y -y 2 2 .
• Initialization: Choose z 0 = (x 0 , y 0 ) ∈ X × Y, τ, σ > 0 and ρ n ∈ (0, 2)

• Iterations: For each n ≥ 0 let (ξ n+1 , η n+1 ) = PD τ,σ (x n , y n , 2ξ n+1 -x n , y n ) z n+1 = (1 -ρ n )z n + ρ n ζ n+1 (22)
where

z n = (x n , y n ) and ζ n = (ξ n , η n ).
First we consider the overrelaxed primal-dual Algorithm 2, whose convergence has been considered already in [START_REF] Eckstein | On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators[END_REF][START_REF] He | Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective[END_REF]. It is known that an overrelaxation parameter close to 2 can speed up the convergence but a theoretical justification was still missing.

Theorem 2. Assume • x = • y = • 2 = •, • 1 2 , D x (x, x ) = 1 2 x -x 2 2 , D y (y, y ) = 1 2 y -y 2 2 .
Let (ξ n , η n ), n = 0, . . . , N -1 be a sequence generated by the overrelaxed Euclidean primal-dual algorithm [START_REF] Nesterov | Introductory lectures on convex optimization[END_REF]. Let the step size parameters τ, σ > 0 and the overrelaxation parameter ρ n be a non-decreasing sequence in (0, ρ) with ρ < 2 such that for all x, x ∈ dom g and y, y ∈ dom h * it holds that

1 τ - L f 2 -ρ 1 σ > K 2 2 . ( 23
)
Then, for any z = (x, y) ∈ X × Y it holds that

L(X N , y) -L(x, Y N ) ≤ 1 2ρ 0 N z -z 0 2 Mτ,σ , (24)
where

X N = 1 N N n=1 ξ n , and Y N = 1 N N n=1 η n . Proof.
We start with the basic inequality [START_REF] Patrick | A forward-backward view of some primal-dual optimization methods in image recovery[END_REF]. According to [START_REF] Nesterov | Introductory lectures on convex optimization[END_REF], using z = z n and z = (2ξ n+1x n , y n ) and ẑ = ζ n+1 , we obtain

L(ξ n+1 , y) -L(x, η n+1 ) ≤ ζ n+1 -z n , z -ζ n+1 Mτ,σ + L f 2 ξ n+1 -x n 2 2 ,
where M τ,σ is defined in ( 12) and we have used the fact that 2 a, b

M = a 2 M + b 2 M -a -b 2 M
. Now, observe that from the second line in [START_REF] Nesterov | Introductory lectures on convex optimization[END_REF], the auxiliary point ζ n+1 can be written as

ζ n+1 = z n + 1 ρ n (z n+1 -z n ) .
Substituting back into the previous inequality, we have

L(ξ n+1 , y) -L(x, η n+1 ) ≤ z n + 1 ρ n (z n+1 -z n ) -z n , z -z n - 1 ρ n (z n+1 -z n ) Mτ,σ + L f 2 x n + 1 ρ n (x n+1 -x n ) -x n 2 2 = 1 ρ n z n+1 -z n , z -z n Mτ,σ - 1 ρ 2 n z n+1 -z n 2 Mτ,σ + L f 2ρ 2 n x n+1 -x n 2 2 = 1 2ρ n z -z n 2 Mτ,σ -z -z n+1 2 Mτ,σ - 2 -ρ n 2ρ 2 n z n+1 -z n 2 Mτ,σ + L f 2ρ 2 n x n+1 -x n 2 2 ≤ 1 2ρ n z -z n 2 Mτ,σ -z -z n+1 2 Mτ,σ - 2 -ρ n 2ρ 2 n z n+1 -z n 2 Mτ,σ,ρ n ,
where we have defined the metric

M τ,σ,ρn = 1 τ - L f 2-ρn I -K * -K 1 σ I ,
which is positive definite for all n as soon as ( 23) is fulfilled. In addition, since ρ n is a nondecreasing sequence in (0, ρ) with ρ < 2, summing the above inequality for n = 0, . . . , N -1 and omitting all nonpositive terms on the right hand side, it follows

N n=1 L(ξ n , y) -L(x, η n ) ≤ 1 2ρ 0 z -z 0 2 Mτ,σ .
The final estimate [START_REF] Law | Weak convergence of the sequence of successive approximations for nonexpansive mappings[END_REF] follows from defining appropriate averages and the convexity of the gap function.

Remark 6. The last result indeed shows that the convergence rate is improved by choosing ρ 0 as large as possible, i.e. close to 2. However, observe that in case the smooth explicit term ∇f is not zero, it might be less beneficial to use a overrerlaxation parameter larger than one since it requires a smaller primal step size τ .

Inertial primal-dual algorithm

Next, we consider an inertial version of the primal-dual algorithm, who has recently been considered in [START_REF] Lorenz | An inertial forward-backward algorithm for monotone inclusions[END_REF] as an extension of the inertial proximal point algorithm of Alvarez and Attouch [START_REF] Alvarez | An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping[END_REF]. It has already been observed in numerical experiments that inertial terms leads to a faster convergence of the algorithm. Here we give a theoretical evidence that indeed the presence of an inertial term leads to a smaller worst-case complexity. • Initialization: Choose (x -1 , y -1 ) = (x 0 , y 0 ) ∈ X × Y, τ, σ > 0 and α n ∈ [0, 1/3)

• Iterations: For each n ≥ 0 let a ζ n = z n + α n (z n -z n-1 ) (x n+1 , y n+1 ) = PD τ,σ (ξ n , η n , 2x n+1 -ξ n , η n ) (25)
a Here as before, z = (x, y) and similarly, ζ = (ξ, η).

Theorem 3. Assume • x = • y = • 2 = •, • 1 2 , D x (x, x ) = 1 2 x -x 2 2 , D y (y, y ) = 1 2 y -y 2 2 .
Let (x n , y n ), n = 0, . . . , N -1 be a sequence generated by the inertial Euclidean primal-dual algorithm [START_REF] Pesquet | A class of randomized primal-dual algorithms for distributed optimization[END_REF]. Let the step size parameters τ, σ > 0 and the inertial parameter α n be a non-decreasing sequence in [0, α] with α < 1/3 such that for all x, x ∈ dom g and y, y ∈ dom h * it holds that

1 τ - (1 + α) 2 1 -3α L f 1 σ > K 2 2 . ( 26
)
Then, for any z = (x, y) ∈ X × Y it holds that

L(X N , y) -L(x, Y N ) ≤ 1 -α 0 2N z -z 0 2 Mτ,σ , (27)
where

X N = 1 N N n=1
x n , and

Y N = 1 N N n=1 y n .
Proof. We again start with the basic inequality [START_REF] Patrick | A forward-backward view of some primal-dual optimization methods in image recovery[END_REF]. According to [START_REF] Pesquet | A class of randomized primal-dual algorithms for distributed optimization[END_REF], using z = ζ n and ẑ = z n+1 , we have

L(x n+1 , y) -L(x, y n+1 ) ≤ z n+1 -ζ n , z -z n+1 Mτ,σ + L f 2 x n+1 -ξ n 2 2 .
Plugging in the first line of ( 25) we arrive at

L(x n+1 , y)-L(x, y n+1 ) ≤ z n+1 -z n , z -z n+1 Mτ,σ -α n z n -z n-1 , z -z n+1 Mτ,σ + L f 2 x n+1 -x n -α n (x n -x n-1 ) 2 2 ≤ z n+1 -z n , z -z n+1 Mτ,σ -α n z n -z n-1 , z -z n + z n -z n+1 Mτ,σ + L f 2 (1 + α n ) x n+1 -x n 2 2 + (α n + α 2 n ) x n -x n-1 2 2 ≤ 1 2 z -z n 2 Mτ,σ -z -z n+1 2 Mτ,σ -z n+1 -z n 2 Mτ,σ - α n 2 z -z n-1 2 Mτ,σ -z -z n 2 Mτ,σ -z n -z n-1 2 Mτ,σ -α n z n -z n-1 , z n -z n+1 Mτ,σ + L f 2 (1 + α n ) x n+1 -x n 2 2 + (α n + α 2 n ) x n -x n-1 2 2 . Using the inequality | a, b M | ≤ 1 2 a 2 M + b 2 M we obtain the estimate L(x n+1 , y) -L(x, y n+1 ) ≤ 1 2 z -z n 2 Mτ,σ -z -z n+1 2 Mτ,σ + α n 2 z -z n 2 Mτ,σ -z -z n-1 2 Mτ,σ + α n -1 2 z n+1 -z n 2 Mτ,σ + α n z n -z n-1 2 Mτ,σ + L f 2 (1 + α n ) x n+1 -x n 2 2 + (α n + α 2 n ) x n -x n-1 2 2 .
Now, since α n ≥ 0 is non-decreasing and z -1 = z 0 , summing the above inequality for n = 0, . . . , N -1, we find:

N n=1 L(x n , y) -L(x, y n ) ≤ 1 -α 0 2 z -z 0 2 Mτ,σ - 1 2 z -z N 2 Mτ,σ + α N -1 2 z -z N -1 2 Mτ,σ + N -2 n=0 3α n+1 -1 2 z n+1 -z n 2 Mτ,σ,α n+1 + α N -1 -1 2 z N -z N -1 2 Mτ,σ + L f 2 (1 + α N -1 ) x N -x N -1 2 2 ,
where

M τ,σ,αn = 1 τ -(1+αn) 2 1-3αn L f I -K * -K 1 σ I ,
which is positive definite for all n as soon as ( 26) is fulfilled for all α n ≤ α < 1/3 since the function (1+αn) 2 1-3αn is monotonically increasing in α n . Our last estimate can be further simplified as

N n=1 L(x n , y) -L(x, y n ) ≤ 1 -α 0 2 z -z 0 2 Mτ,σ + α N -1 2 z -z N -1 2 Mτ,σ + α N -1 -1 2 z N -z N -1 2 Mτ,σ - 1 2 z -z N 2 Mτ,σ + L f 2 (1 + α N -1 ) x N -x N -1 2 2
It remains to show that the term in the last two lines of the above estimate is nonpositive. In fact:

α N -1 2 z -z N + z N -z N -1 2 Mτ,σ + α N -1 -1 2 z N -z N -1 2 Mτ,σ - 1 2 z -z N 2 Mτ,σ + L f 2 (1 + α N -1 ) x N -x N -1 2 2 ≤ α N -1 z -z N 2 Mτ,σ + z N -z N -1 2 Mτ,σ + α N -1 -1 2 z N -z N -1 2 Mτ,σ - 1 2 z -z N 2 Mτ,σ + L f 2 (1 + α N -1 ) x N -x N -1 2 2 = (α N -1 - 1 2 ) z -z N 2 Mτ,σ + 3α N -1 -1 2 z N -z N -1 2 Mτ,σ + L f 2 (1 + α N -1 ) x N -x N -1 2 2 = (α N -1 - 1 2 ) z -z N 2 Mτ,σ + 3α N -1 -1 2 z N -z N -1 2 P ≤ 0,
as α n ≤ α < 1/3 and as the matrix [START_REF] Pock | An algorithm for minimizing the Mumford-Shah functional[END_REF] is fulfilled. It remains to derive the ergodic rate by defining appropriate averages and exploiting the convexity of the gap function.

P = 1 τ -1+α N -1 1-3α N -1 L f I -K * -K 1 σ I is clearly positive definite if
Remark 7. This result again shows that it is beneficial to choose α 0 as large as possible, i.e. α 0 close to 1/3 in order to reduce the constant on the right hand side. Similar to the case of overrelaxation, larger values of α n leads to smaller primal step sizes τ and hence an inertial term might be less beneficial in presence of an explicit term ∇f . Remark 8. Letting γ = τ L f we find that the parameter α should satisfy

α < √ 16γ + 9 -3 2γ -1
in order for the left-hand side term in [START_REF] Pock | An algorithm for minimizing the Mumford-Shah functional[END_REF] to be positive (and then σ needs to be chosen accordingly). We point out that this condition is a bit more restrictive than the condition in [START_REF] Lorenz | An inertial forward-backward algorithm for monotone inclusions[END_REF]. This is due to the fact that our convergence proof is based on the Lipschitz continuity of ∇f rather than its co-coercivity, which leads to the loss of a factor 2 in the size of the primal step size τ relatively to the Lipschitz parameter L f .

Acceleration for strongly convex problems

Here in this section, we slightly improve the results in [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF] on accelerated algorithms. We address more precisely the natural generalization proposed in [START_REF] Condat | A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms[END_REF] (also [START_REF] Àng | A splitting algorithm for dual monotone inclusions involving cocoercive operators[END_REF]) and studied in [START_REF] Bot | On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems[END_REF] (where rates of convergence are proven). The main novelty with respect to [START_REF] Bot | On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems[END_REF] is a proof that in an ergodic sense, also the primal-dual gap is controlled and decreases at rate O(1/N 2 ) where N is the number of iterations. In addition to our assumptions (i)-(iii) we assume that (iv) f or g (or both) are strongly convex with respective parameters γ f , γ g and hence the primal objective is strongly convex with parameter γ = γ f + γ g > 0.

In fact, we observe that since

f (x) + g(x) = f (x) - γ f 2 x 2 + g(x) + γ f 2 x 2
we can "transfer" the strong convexity of f to g:

letting f = f -γ f • 2 /2, g = g + γ f • 2 /2,
and γ = γ f + γ g , we have now that g is γ-convex. In addition, ∇ f = ∇f -γ f I, so that

x = (I + τ ∂g) -1 (x -τ ∇ f (x)) ⇔ x = (I + τ ∂g) -1 (x -τ ∇f (x)) with τ = τ 1 + γ f τ , so that τ := τ 1 -γ f τ (28)
(observe that τ needs, as expected, to be less than 1/γ f > 1/L f ). In addition, we find that ∇ f is (L f -γ f )-Lipschitz. Hence in the following, to simplify we will just assume that g is strongly convex (that is, γ f = 0, γ = γ g ), replacing assumption (iv) with the simpler assumption:

(iv') g is strongly convex with parameter γ > 0.

We must eventually mention here that in case f = 0, the dual problem, which has the form min y g * (-K * y) + h * (y), is the sum of a smooth plus a nonsmooth objective which could be tackled directly by more standard optimal methods [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF][START_REF] Nesterov | Introductory lectures on convex optimization[END_REF][START_REF] Nesterov | Smooth minimization of non-smooth functions[END_REF] yielding similar convergence rates (provided one knows how to compute the Lipschitz gradient ∇g * , which is slightly different from the assumptions we use in this paper).

Convergence analysis

With this additional assumption, the descent rule (9) can be slightly improved: indeed, thanks to the strong convexity of g, we can control an additional quadratic term on the right-hand side. It follows that for any x ∈ X ,

f (x) + g(x) + 1 τ D x (x, x) + L f 2 x -x 2 ≥ f (x) + g(x) + K(x -x), ỹ + 1 τ D x (x, x) + 1 τ D x (x, x) + γ 2 x -x 2 . ( 29
)
It follows that ( 8) is also improved, with the additional term γ 2 x -x 2 on the left-hand side. One sees that one will be able to obtain a good convergence rate whenever the last two terms in [START_REF] Teboulle | Entropic proximal mappings with applications to nonlinear programming[END_REF] can be combined into one, which requires that

D x (x, x) = 1 2 x -x 2 2
, that is, we must consider linear proximity operators in the x variable. 1 To simplify the notation we will drop the subscript "2" in the norm for x, in the rest of this section. • Initialization: Choose x -1 = x 0 ∈ X , τ 0 , σ 0 , θ 0 > 0 which satisfy (34).

• Iterations: For each n ≥ 0 let (x n+1 , y n+1 ) = PD τn,σn (x n , y n , x n + θ n (x n -x n-1 ), y n+1 ) τ n+1 , σ n+1 , θ n+1 satisfy (32), ( 33), (34).

(

) 30
Now, we can specialize "à la" [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF]. That is, we choose in (8) ỹ = ŷ = y n+1 , x = x n+1 , x = x n + θ n (x n -x n-1 ), x = x n , ȳ = y n , and make τ, σ depend also on the iteration counter n. In particular, now, for any (x, y) ∈ X × Y,

K(x -x), ŷ -ỹ -K(x -x), y -ŷ = -K(x n+1 -x n ), y -y n+1 + θ n K(x n -x n-1 ), y -y n+1 = -K(x n+1 -x n ), y -y n+1 + θ n K(x n -x n-1 ), y -y n + θ n K(x n -x n-1 ), y n -y n+1 .
The last term is simply controlled by observing that

θ n K(x n -x n-1 ), y n -y n+1 ≥ -θ n L x n -x n-1 y n -y n+1 ≥ -θ n L µ x n -x n-1 2 2 + y n -y n+1 2µ 2
for any µ > 0, and choosing µ = θ n Lσ n we obtain

K(x -x), ŷ -ỹ -K(x -x), y -ŷ ≥ -K(x n+1 -x n ), y -y n+1 + θ n K(x n -x n-1 ), y -y n - y n+1 -y n 2σ n 2 -(θ 2 n L 2 σ n ) x n -x n-1 2 2 .
To sum up, it follows from (8), with the additional strong convexity term from [START_REF] Teboulle | Entropic proximal mappings with applications to nonlinear programming[END_REF], that for any 1 It must be observed here that the right assumption on g to obtain an accelerated scheme with an arbitrary Bregman distance Dx should be that g is "strongly convex with respect to ψx", in the sense that g -γψx is convex. The proof would then be similar. However, it is not clear whether this covers very interesting situations beyond the standard case.

(x, y), using also that D y (y n+1 , y n ) ≥ 1 2 y n+1 -y n 2 ,

x -

x n 2τ n 2 + D y (y, y n ) σ n -θ n K(x n -x n-1 ), y -y n + θ 2 n L 2 σ n 2 x n -x n-1 2 ≥ L(x n+1 , y) -L(x, y n+1 ) + 1 + γτ n 2τ n x -x n+1 2 + D y (y, y n+1 ) σ n -K(x n+1 -x n ), y -y n+1 + 1 -L f τ n 2τ n x n+1 -x n 2 . ( 31
)
Assume the sequences θ n , τ n , σ n satisfy for all n ≥ 0

1 + γτ n τ n ≥ 1 θ n+1 τ n+1 , ( 32
) 1 σ n = 1 θ n+1 σ n+1 , (33)
L 2 σ n ≤ 1 τ n -L f . (34)
Then ( 31) becomes (using

θ 2 n L 2 σ n = θ n L 2 σ n-1 , thanks to (33)) x -x n 2τ n 2 + D y (y, y n ) 2σ n + θ n L 2 σ n-1 x n -x n-1 2 2 -K(x n -x n-1 ), y -y n ≥ L(x n+1 , y) -L(x, y n+1 ) + 1 θ n+1 x -x n+1 2τ n+1 2 + D y (y, y n+1 ) 2σ n+1 + θ n+1 L 2 σ n x n+1 -x n 2 2 -K(x n+1 -x n ), y -y n+1 . (35)
Observe that from (33), N n=1 θ n = σ 0 /σ N . We now let

T N = N n=1 σ n-1 σ 0 , X N = 1 T N N n=1 σ n-1 σ 0 x n , Y N = 1 T N N n=1 σ n-1 σ 0 y n . (36)
Then, summing (35) (first multiplied on both sides by σ n /σ 0 ) from n = 0 to n = N -1 and assuming x -1 = x 0 , using also the convexity of (ξ, η) → L(ξ, y) -L(x, η) (for fixed x, y), we deduce

T N L(X N , y) -L(x, Y N ) + σ N σ 0 x -x N 2τ N 2 + D y (y, y N ) σ N + θ N L 2 σ N -1 x N -x N -1 2 2 -K(x N -x N -1 ), y -y N ≤ x -x 0 2τ 0 2 + D y (y, y 0 ) σ 0 .
Considering eventually that (using again (33))

K(x N -x N -1 ), y -y N ≤ D y (y, y N ) θ N σ N + L 2 σ N -1 2 x N -x N -1 2 ,
we deduce the following result.

Theorem 4. Assume D x (x, x ) = 1 2 x -x 2 x . Let (x n , y n ) be a sequence generated by Algorithm 4, and let (X N , Y N ) and (T N ) be the ergodic averages given by (36). Then, for all x and y, for all N ≥ 1, one has the estimate

T N L(X N , y) -L(x, Y N ) + σ N σ 0 x -x N 2τ N 2 ≤ x -x 0 2τ 0 2 + D y (y, y 0 ) σ 0 . ( 37
)
Remark 9. Notice that, taking (x, y) = (x * , y * ) a saddle-point in (37), we find that X N and x N are bounded (and converge to x * ). If we assume that h has full domain, so that h * (y)/|y| → ∞ as |y| → ∞, we deduce that also Y N is bounded (since otherwise -L(x * , Y N ) would go to infinity), and it follows that the (x, y) which realize the supremum in the expression L(X N , y) -L(x, Y N ) are also globally bounded. It follows the global estimate on the gap

sup x,y L(X N , y) -L(x, Y N ) ≤ C T N . ( 38
)

Parameter choices

It turns out that it is possible to choose sequences (τ n , σ n , θ n ) satisfying (32), ( 33), (34) in order to have 1/T N = O(1/N 2 ). A possible choice, similar to [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF], to ensure (32), ( 33), ( 34) is to keep the product σ n τ n constant and let

θ n+1 = 1 √ 1 + γτ n , τ n+1 = θ n+1 τ n , σ n+1 = σ n /θ n+1 . (39)
Then, letting

τ 0 = 1 2L f , σ 0 = L f L 2
(or τ 0 = σ 0 = 1/L if L f = 0), we find that by induction, since τ n+1 /τ n = σ n /σ n+1 < 1 for each n, (34) will be satisfied. We refer to [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF] for a proof that this choice ensures that σ n ∼ γn/(4L 2 ), so that T N ∼ γN 2 /(4L f ).

A simpler (still slightly suboptimal) choice is to take σ 0 > 0 arbitrary, and

τ n = 2 γn + 2(L f + L 2 σ 0 ) , σ n = σ 0 + γnσ 0 γ + 2(L f + L 2 σ 0 ) . (40)
Then, (32), (33), (34) hold, and

T N = N + N (N -1) 2 γ γ + 2(L f + L 2 σ 0 ) . ( 41
)
Observe that in this case,

θ n+1 = σ n σ n+1 = γ(n + 1) + 2(L f + L 2 σ 0 ) γ(n + 2) + 2(L f + L 2 σ 0 ) and θ n+1 τ n+1 = 2 γ(n + 2) + 2(L f + L 2 σ 0 ) = τ n 1 + γτ n ,
that is, the equality holds in (32).

The optimal rule should consist in choosing equalities in (32), ( 33) and (34). We find that σ 0 > 0 can be chosen arbitrarily,

τ 0 = 1 L f + L 2 σ 0 ,
and then:

1 + γτ n = τ n τ n+1 σ n+1 σ n = τ 2 n τ 2 n+1 1 -L f τ n+1 1 -L f τ n , τ 2 n+1 1 -L f τ n+1 = τ 2 n (1 + γτ n )(1 -L f τ n ) =: β 2 n+1
so that, assuming L f τ n < 1 (which is true for n = 0),

τ n+1 = β n+1 1 + L 2 f 4 β 2 n+1 - L f 2 β n+1 = β n+1 1 + L 2 f 4 β 2 n+1 + L f 2 β n+1 = τ n (1 + γτ n )(1 -L f τ n ) + L 2 f 4 τ 2 n + L f 2 τ n ≤ τ n ,
and

θ n+1 = (1 + γτ n )(1 -L f τ n ) + L 2 f 4 τ 2 n + L f 2 τ n 1 + γτ n ∈ 1 1 + γτ n , 1 √ 1 + γτ n .
Let us denote τ opt n , σ opt n and T opt N the τ n , σ n and T N obtained by this "optimal" rule (and the corresponding T N ) and let us keep the notation τ n , σ n , T N for the expressions in ( 40) and (41). These choices, in particular, satisfy the equality in (32), ( 33), but a strict inequality (for n ≥ 1) in (34). We assume that the starting point σ 0 = σ opt 0 is the same, then of course also τ 0 = τ opt 0 . Then one has: Lemma 2. For each n ≥ 0, σ opt n ≥ σ n , and

T opt n ≥ T n ∼ cn 2 .
Proof. We proceed by induction. We assume σ opt n ≥ σ n , which is true for n = 0. For practical reasons, let us set

X opt n = L 2 σ opt n , Y opt n = -1/τ opt n , X n = L 2 σ n
, and Y n = -1/τ n . Then from the equality in (32), we have for all n

X n+1 Y n+1 = X n Y n -γX n , X opt n+1 Y opt n+1 = X opt n Y opt n -γX opt n , (42)
We also assume Π n := X n Y n ≥ Π opt n := X opt n Y opt n , which is true at n = 0. It follows then that from (42) and X opt n ≥ X n that Π n+1 ≥ Π opt n+1 . Observe that being this product negative, it means in fact that |Π n+1 | ≤ |Π opt n+1 |. On the other hand, from (34), one has that

Σ n+1 := X n+1 + Y n+1 ≤ -L f = X opt n+1 + Y opt n+1 =: Σ opt n+1 ≤ 0 (and, again, |Σ n+1 | ≥ |Σ opt n+1 |).

One has then

X n+1 = Σ n+1 + Σ 2 n+1 -4Π n+1 2 = Σ 2 n+1 + 4|Π n+1 | -Σ 2 n+1 2 , which, by concavity of √ • and since Σ 2 n+1 ≥ (Σ opt n+1 ) 2 , |Π n+1 | ≤ |Π opt n+1 |
, is less than the similar expression for X opt n+1 . This shows the Lemma.

Acceleration for smooth and strongly convex problems

In this section, we finally make the additional assumption that (v) h * is strongly convex with parameter δ > 0.

Equivalently, h has (1/δ)-Lipschitz gradient, so that the primal objective is both smooth and strongly convex. Then, as expected, the rate can be improved, to linear convergence. In this section, we must assume that the Bregman distance functions satisfy D x (x, x ) = 1 2 x -x 2 2 and D y (y, y ) = 1 2 y -y 2 2 , that is, we are for both variables in the Euclidean/Hilbertian setting. For simplicity we will drop the subscript "2" in the rest of this section.

We show here how to modify the proof of the previous case to obtain a linear convergence rate on the gap. This slightly improves the results in [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF][START_REF] Bot | On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems[END_REF] which only give a rate on the iterates. In contrast to [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF], we do not show here convergence for a large range of relaxation parameters θ, but the proof presented can handle the explicit term ∇f and yields a similar convergence rate.

Convergence analysis

Algorithm 5: O(θ N ) Accelerated primal-dual algorithm

• Input: Operator norm L = K , Lipschitz constant L f of ∇f , parameters γ, δ of strong convexity of g and h * , D x (x, x ) = 1 2 x -x 2
x and D y (y, y ) = 1 2 y -y 2 y .

• Initialization: Choose x -1 = x 0 ∈ X , τ, σ, θ > 0 which satisfy ( 44) and (45).

• Iterations: For each n ≥ 0 let (x n+1 , y n+1 ) = PD τ,σ (x n , y n , x n + θ(x n -x n-1 ), y n+1 ) (43)

A first remark is that the inequality [START_REF] Àng | A splitting algorithm for dual monotone inclusions involving cocoercive operators[END_REF], in case h * is δ-convex, can be written

x -x n 2τ 2 + y -y n 2σ 2 -θ K(x n -x n-1 ), y -y n + θ 2 L 2 σ 2 x n -x n-1 2 ≥ L(x n+1 , y) -L(x, y n+1 ) + 1 + γτ 2τ x -x n+1 2 + 1 + δσ 2σ y -y n+1 2 -K(x n+1 -x n ), y -y n+1 + 1 -L f τ 2τ x n+1 -x n 2 .
It follows that if one can choose τ, σ, θ so that

1 + γτ = 1 + δσ = 1 θ (44) 1 -L f τ τ ≥ θL 2 σ (45)
then, multiplying the inequality by θ -n and summing from n = 0 to N -1, we get (assuming

x -1 = x 0 ) x -x 0 2τ 2 + y -y 0 2σ 2 ≥ N n=1 1 θ n-1 (L(x n , y) -L(x, y n )) + 1 θ N x -x N 2τ 2 + y -y N 2σ 2 -θ K(x N -x N -1 ), y -y N + 1 -L f τ 2τ θ N -1 x N -x N -1 2 .
Using (45) again, we deduce

N n=1 1 θ n-1 (L(x n , y) -L(x, y n )) + x -x N 2τ θ N 2 ≤ x -x 0 2τ 2 + y -y 0 2σ 2 .
Hence, letting now

T N = N n=1 θ -n+1 = 1 -θ N 1 -θ 1 θ N -1 and Z N = (X N , Y N ) = 1 T N N n=1 θ -n+1 z n (46)
we obtain the following result

Theorem 5. Assume D x (x, x ) = 1 2 x -x 2
x and D y (y, y ) = 1 2 y -y2 y . Let (x n , y n ) be a sequence generated by Algorithm 5, and let (X N , Y N ) and (T N ) be the ergodic averages defined in (46). Then, for all x and y, for all N ≥ 1, one has the estimate

L(X N , y) -L(x, Y N ) + θ(1 -θ) 1 -θ N x -x N 2τ 2 ≤ 1 T N x -x 0 2τ 2 + y -y 0 2σ 2 (47)
which yields a linear convergence rate.

Parameter choices

Solving the equations (44) for τ, σ, θ, we obtain, letting

2 µ = δ(γ + L f ) 2L 2 1 + 4 γL 2 δ(γ + L f ) 2 -1 ∈ (0, 1) : τ = µ γ(1 -µ) , σ = µ δ(1 -µ) , θ = 1 -µ. (48)
In case L f = 0, one has

µ = δγ 2L 2 1 + 4 L 2 δγ - 1
and the above formulas simplify to

τ = δ 1 + 1 + 4 L 2 γδ 2L 2 , σ = γ 1 + 1 + 4 L 2 γδ 2L 2 , θ = 1 - δγ 2L 2 1 + 4 L 2 δγ -1 . (49)
In this case, if δγ L 2 , then the linear rate of convergence is governed by the factor

θ ≤ 1 - √ δγ L + δγ 2L 2 ≈ 1 - √ δγ L :
we remark that this is of the same order as the rate found in [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF] (which was not a bound on the gap though). Note however that a more refined analysis in [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF] allowed to obtain better rates, for a larger choice of parameters θ. A similar analysis with L f = 0 would probably lead to close results through very tedious calculations. On the other hand, the new proof allows for slightly larger steps than in [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF].

Computational examples

In this section we demonstrate the practical performance of the proposed algorithms on a number of randomly generated instances of classical optimization problems.

Matrix games

Here, we consider the following min-max matrix game:

min x∈∆ l max y∈∆ k L(x, y) = Kx, y , (50)
where ∆ k and ∆ l denote the standard unit simplices in R k and R l and K ∈ R k×l . This class of min-max matrix games can be used for approximately finding the Nash equilibrium of two-person zero-sum matrix games such as two-person Texas Hold'em Poker. Following the computational experiments in [START_REF] Nesterov | Smooth minimization of non-smooth functions[END_REF], the entries of K are independently and uniformly distributed in the intervall [-1, 1]. We denote by L = K the operator norm of K. We can also easily compute the primal-dual gap of a feasible pair (x, y). For this we observe that arg min x∈∆ l L(x, y) = e j , where e j ∈ ∆ l is the j-th standard basis vector corresponding to the smallest entry of the vector K T y. Likewise, arg max y∈∆ k L(x, y) = e i , where i corresponds to the coordinate of the largest entry of Kx. Hence, the primal-dual gap is computed as

G(x, y) = P(x) = max i (Kx) i -D(y) = min j (K T y) j 7.1.

Linear and nonlinear primal-dual algorithms

We first consider different Bregman distance settings of the nonlinear primal-dual algorithm presented in Algorithm 1. The initial points (x 0 , y 0 ) are chosen to be the centers of the simplices, that is x 0 j = 1/l and y 0 i = 1/k for all i, j. There are two obvious choices for the Bregman distance functions:

1. Euclidean setting: In the Euclidean setting,

• x = • y = • 2 , D x (x, x ) = 1 2 x -x 2 , and D y (y, y ) = 1 2 y -y 2 . It follows that max x∈∆ l D x (x, x 0 ) = (1 -1 l )/2 and likewise max y∈∆ k D y (y, y 0 ) = (1 -1 k )/2.
The operator norm is computed as the largest singular value L 2 = s max (K). In the iterates of the algorithm, we need to solve subproblems of the following form:

x = arg min

x∈∆ l x, ξ + x -x 2τ 2 ⇔ x = proj ∆ l (x -τ ξ) ,
where we are using the n log n algorithm described in [START_REF] Duchi | Efficient projections onto the 1 -ball for learning in high dimensions[END_REF] to compute the orthogonal projections on the unit simplices. Taking the supremum on the right hand side of ( 17), the ergodic O(1/N ) rate for the primal-dual gap bounded by

G(X N , Y N ) ≤ 2 N 1 -1 l 2τ + 1 -1 k 2σ .
Since τ σL 2 2 = 1, the right hand side is minimized by setting

τ = 1 L 2 1 -1 l 1 -1 k , σ = 1 L 2 1 -1 k 1 -1 l .
Hence we get the following final estimate for the gap

G(X N , Y N ) ≤ 2 (1 -1 l )(1 -1 k ) N L 2 .

Entropy setting:

In the entropy setting we choose • x = • y = • 1 and the Bregman distance functions are given by D x (x, x ) = j x j (log x j -log x j ) -x j + x j and D y (y, y ) = i y i (log y i -log y i ) -y i + y i , which are 1-convex with respect to the 1-norm. Now, max x∈∆ l D x (x, x 0 ) = log l and max y∈∆ k D y (y, y 0 ) = log k. The operator norm is given by

L 1 = sup x 1=1 Kx ∞ = max i,j |K i,j |.
It is well known that in the entropy setting, the iterates of the algorithm are explicit:

x = arg min x∈∆ l x, ξ + 1 τ D x (x, x) ⇔ xj = xj exp(-τ ξ j ) l j=1 xj exp(-τ ξ j )
In turn, the ergodic O(1/N ) rate in [START_REF] He | On the O(1/n) convergence rate of the Douglas-Rachford alternating direction method[END_REF] specializes to

G(X N , Y N ) ≤ 2 N log l τ + log k σ .
Again, the right hand side is minimized by choosing

τ = 1 L 1 log l log k , σ = 1 L 1 log k log l
We obtain the final estimate as

G(X N , Y N ) ≤ 4 √ log l log k N L 1 .
Remark 10. Since the entries of K are uniformly distributed in [-1, 1], the solutions of the min-max matrix games always cluster around the simplex centers 1/k and 1/l. In this region, the entropy functions are strongly k-and l-convex, respectively, and hence for small variations around the center,

D x (x, x ) 1 2 ( √ l x -x 2 ) 2 , D y (y, y ) 1 2 ( √ k y -y 2 ) 2 .
With this information we can get a better (local) estimate of the operator norm:

L cent ≈ sup x 2≤1/ √ l Kx 2 / √ k = L 2 / √ kl
In practice, we observed that slightly larger values, e.g. 1.7 • L cent worked very well in our experiments. It would be of great interest to find a method which is able to exploit this variability, unfortunately we were not able to find a rigorous and efficient method.

First let us observe that our theoretical worst case bounds for the matrix games are exactly the same as the corresponding worst case bounds in [START_REF] Nesterov | Smooth minimization of non-smooth functions[END_REF]. In Table 1 we report the number of iterations of the O(1/N ) primal-dual algorithms using the Euclidean setting and the entropy setting to reach a primal-dual gap that is less than ε. One can see that the entropy-based algorithm is consistently faster compared to the Euclidean-based algorithm. Furthermore, one can see that the complexity for finding an ε accurate solution grows, as predicted in Theorem 1, with a factor of order 1/ε. Indeed, one can see that reducing ε by a factor of 10 roughly leads to 10 times more iterations. Comparing the results with the results reported in [START_REF] Nesterov | Smooth minimization of non-smooth functions[END_REF] the proposed algorithms are significantly faster. Also observe that counterintuively, less iterations are needed for larger problems. This might be due to the fact that the value of the gap of theses problems at the centers of the simplices goes to zero as the size goes to infinity, making this initialization more beneficial for larger problems. We also tested the performance of the nonergodic sequences, i.e. the rate of convergence of the primal-dual gap of the iterates (x n , y n ). Figure 1 depicts logarithmic convergence plots in the setting k = l = 1000, for both the Euclidean and the entropy setting. It shows that in the Euclidean setting, the nonergodic sequence converges even faster than the ergodic sequence. In the entropy setting however, we observed the contrary. The nonergodic sequence converges much slower than the ergodic sequence. We do not know the reason for this behavior. For both ergodic sequences, the gap decreases exactly at rate O(1/N ) as predicted by the analysis.

Overrelaxed and inertial primal-dual algorithms

In this section, we evaluate the performance of the overrelaxed and inertial version of the Euclidean primal-dual algorithm detailed in Algorithm 2 and Algorithm 3. We vary the relaxation parameter ρ and the inertial parameter α (which are kept constant during the iterations) and record the number of iterations that are necessary to reach a primal-dual gap which is less a tolerance of ε = 10 -4 . For both, the inertial and overrelaxed versions, we observe that the algorithms are still converging for the theoretical limits ρ = 2 and α = 1/3. In Table 2, we report the number of iterations using different values of the relaxation param-eter ρ. As predicted in Theorem 2, the number of iterations are approximately proportional to the factor 1/ρ. In Table 3, we report the number of iterations using different inertial parameters α. Again, as predicted in Theorem 3, the number of iterations roughly correspond to the factor 1 -1/α.

Simplex constrained least squares problem

In this section, we consider the following class of simplex-constrained least squares problems min

x∈∆ l P(x) = 1 2 Kx -b 2 , (51)
where ∆ l again denotes the standard unit simplex in R l and K ∈ R k×l , and b ∈ R k . Several standard optimization problems used in machine learning such as the support vector machine can be obtained as special cases from (51). Here, K and b are randomly generated with their entries 2. Entropy setting: In the entropy setting, we choose • x = • 1 and D x (x, x ) = j x j (log x jlog x j ) -x j + x j . The operator norm is now given by L 12 = K = sup x 1 ≤1 Kx 2 = max j K j 2 where K j denotes the j-th column of K, which is typically smaller than L 2 .

In analogy to the above calculations, we have

T N G(X N , Y N ) ≤ sup x D x (x, x 0 ) τ 0 + K(X N -x 0 ) 2 2σ 0 ≤ log l τ 0 + L 2 2 (1 -1 l ) 2σ 0 .
The optimal choice for τ 0 and σ 0 is now

τ 0 = 2 log l L 2 12 L 2 2 (1 -1 l ) , σ 0 = L 2 2 (1 -1 l ) 2L 2
12 log l , which yields the final estimate

G(X N , Y N ) ≤ L 12 L 2 (1-1 l ) log l 2 T N .
We also observed that in the entropy setting, we can choose larger step sizes: choosing L 12 = 0.35 • max j K j 2 gave experimentally good results. In Table 4, we report the number of iterations for Algorithm 4 in the Euclidean and the entropy setting. One can see that in the entropy setting, the algorithm converges significantly faster. Furthermore, one can see that the number of iterations which are necessary to reach a primal-dual gap less than ε nicely reflect the O(1/N 2 ) rate of Algorithm 4. Indeed, reducing ε by a factor of 10 roughly leads to √ 10 ≈ 3.16 more iterations. We also investigated the performance difference between the ergodic and the nonergodic sequences. Figure 2 shows a comparison between the ergodic and the nonergodic sequences for both the Euclidean and the entropy setup for the simplex constrained least squares problem (51) using k = 100, l = 1000. While the ergodic sequences both show a O(1/N 2 ) rate, the nonergodic sequences show a completely different behavior. In the entropy setting, the nonergodic sequence converges a little bit faster but is seems to be quite unstable. In the Euclidean setting, the nonergodic sequence converges extremely fast. We do not know the reason for this, but it will be interesting to find an alternative proof for the convergence rate that does not rely on the ergodic sequence.

Elastic net problem

Finally, we consider the elastic net problem which has been extensively used for feature selection and sparse coding. It is written as the following optimization problem:

min x P(x) = 1 2 Kx -b 2 + λ 1 x 1 + λ 2 2 x 2 , (53)
where K ∈ R k×l is a matrix where its columns are features and b ∈ R k is the measurement vector. For λ 2 = 0, the elastic net is equivalent to the well-known LASSO problem. It can be rewritten as the following saddle-point problem:

min x max y L(x, y) = Kx, y + λ 1 x 1 + λ 2 x 2 - 1 2 y 2 -b T y
Observe that the above problem is λ 2 -strongly convex in x and 1-strongly convex in y. Hence, we can make use of the linearly converging Algorithm 5. The dual problem is computed as

max y D(y) = - 1 2λ 2 (|K T y| -λ 1 ) + 2 - 1 2 y 2 -b T y,
where the expressions |K T y| and (t) + = max(0, t) are understood element-wise. In turn the primal-dual gap can be computed as

G(x, y) = 1 2 Kx -b 2 + λ 1 x 1 + λ 2 2 x 2 -- 1 2λ 2 (|K T y| -λ 1 ) + 2 - 1 2 y 2 -b T y . ( 54
)
In our experiments, we again choose the entries of K and b uniformly and independently in the interval [-1, 1] and we again denote by L 2 = K = s max (K) the largest singular value of K.

We compute the values for τ , σ and θ using the formulas provided in (49) and we choose x 0 = 0, y 0 = Kx 0 -b. According to (47), after N iterations, we have for all (x, y):

T N (L(X N , y) -L(x, Y N )) ≤ x -x 0 2 2τ + y -y 0 2 2σ .

Taking the supremum on the left hand with respect to (x, y) we find x = (|K T Y N | -λ 1 ) + • sgn(-K T Y N )/λ 2 and y = KX N -b. Substituting back we obtain the final estimate

T N G(X N , Y N ) ≤ (|K T Y N | -λ 1 ) + 2 2τ λ 2 2 + L 2 2 X N 2 2σ < ∞,
where T N ∼ O(θ -N ) is defined in (46) and τ, σ are chosen according to (49).

For the implementation of the algorithm we need to solve the proximal map with respect to the mixed 1 -2 norm appearing in the primal problem. The solution is given by: x = arg min

x λ 1 x 1 + λ 2 2 x 2 + 1 2τ x -x 2 ⇔ x = max(0, |x| -τ λ 1 ) • sgn(x) 1 + τ λ 2 ,
where the operations are understood element-wise.

In Table 5 we evaluate Algorithm 5 for different problem instances of (53). We set λ 1 = 1 and used different values of λ 2 in order to study the behavior of the algorithm for different degrees of convexity. The table reports the number of iterations that were needed to achieve a primal-dual gap less than the error tolerance ε. One can see that in general, a smaller value of λ 2 leads to a smaller strong convexity parameter of the primal problem and hence the problem appears more difficult to the algorithm. Thanks to the O(θ N ) linear convergence rate of the algorithm, reducing the required tolerance by a factor of 10 only leads to a small increase of the required iterations. Finally Figure 3 shows the performance difference between the ergodic sequence and the nonergodic sequence for the elastic net problem using k = 100, l = 1000, λ 1 = 1, and λ 2 = 10 -3 . One can see that while the performance of the ergodic sequence is again well predicted by the worst case rate O(θ N ), the performance of the nonergodic sequence is again superior.

Conclusion

In this work, we have presented refined ergodic convergence rates for a first-order primal-dual algorithm for composite convex-concave saddle-point problems. Some of the presented proofs are quite elementary and easily extend to non-linear Bregman distance functions and inertial or overrelaxed variants of the algorithm. Furthermore, we have given refined ergodic convergence rates in terms of the primal-dual gap function for accelerated variants of the algorithm. We have illustrated the theoretical results by applying the algorithms to a number of standard convex optimization problems including matrix games, simplex constrained least squares problems and the elastic net selector. The numerical results show a behaviour which corresponds nicely to the theoretical predictions. We have also observed that in the Euclidean setting, the nonergodic sequences very often converge much faster than the ergodic sequences. We will investigate this issue in more detail in our future research. Furthermore, it will be interesting to investigate strategies to dynamically adjust the step sizes (τ n , σ n and θ n ) to the local smoothness of the problem, which can vary a lot during the optimization (see Remark 10). like to thank his colleague S. Gaiffas for stimulating discussions, as well as J. Fadili for very helpful discussions on nonlinear proximity operators. This work also benefited from the support of the "Gaspard Monge Program in Optimization and Operations Research" (PGMO), supported by EDF and the Fondation Mathématique Jacques Hadamard (FMJH). The authors also need to thank the referees for their careful reading of the manuscript and their numerous helpful comments.

Algorithm 1 :

 1 O(1/N ) Non-linear primal-dual algorithm • Input: Operator norm L := K , Lipschitz constant L f of ∇f , and Bregman distance functions D x and D y .

Algorithm 3 :

 3 O(1/N ) Inertial primal-dual algorithm • Input: Operator norm L = K 2,2 , Lipschitz constant L f of ∇f , and Bregman distance functions D x (x, x ) = 1 2 x -x 2 2 and D y (y, y ) = 1 2 y -y 2 2 .

Algorithm 4 :

 4 O(1/N 2 ) Accelerated primal-dual algorithm • Input: Operator norm L = K , Lipschitz constant L f of ∇f , parameter γ of strong convexity of g, and Bregman distance function D y , D x (x, x ) = 1 2 x -x 2 x

Figure 1 :

 1 Figure 1: Comparison between the performance of the ergodic and the nonergodic sequences of Algorithm 1 applied to the matrix game problem (50).

Figure 2 :

 2 Figure 2: Comparison between the performance of the ergodic and the nonergodic sequences of Algorithm 4 applied to the simplex constrained least squares problem (51).

Figure 3 :

 3 Figure 3: Comparison between the performance of the ergodic and the nonergodic sequences of Algorithm 5 applied to the elastic net problem (53).

Table 1 :

 1 Computational results of Algorithm 1 applied to the matrix game problem (50).

		ε = 10 -3		ε = 10 -4
	k/l	Euclidean Entropy Euclidean Entropy
	100/100	942	730	9394	7292
	100/500	760	750	7671	7378
	100/1000	1138	960	11330	9862
	500/100	1085	648	10743	6474
	500/500	483	333	4782	3290
	500/1000	480	350	4796	3430
	1000/100	1537	640	15394	6284
	1000/500	547	297	5434	2905
	1000/1000	381	261	3797	2546

Table 2 :

 2 Computational results of Algorithm 2 applied to the matrix game problem (50).

	k/l	ρ = 1 ρ = 5/4 ρ = 3/2 ρ = 7/4 ρ = 2
	100/100	9394	7224	5784	4825	4075
	100/500	7671	5853	4748	3983	3337
	100/1000 11330	8861	7225	6063	5151
	500/100	10743	8389	6818	5721	4691
	500/500	4782	3651	2924	2402	2051
	500/1000	4796	3809	3156	2696	2346
	1000/100 15394	11982	9721	8126	6835
	1000/500	5434	4224	3426	2860	2437
	1000/1000 3797	2975	2433	2050	1881

Table 3 :

 3 Computational results of Algorithm 3 applied to matrix game problem (50).

	k/l	α = 0 α = 1/12 α = 1/6 α = 1/4 α = 1/3
	100/100	9394	8660	7939	7234	6545
	100/500	7671	7065	6467	5882	5328
	100/1000 11330	10420	9520	8632	7751
	500/100	10743	9882	9034	8203	7411
	500/500	4782	4401	4026	3655	3291
	500/1000	4796	4410	4029	3656	3299
	1000/100 15394	14147	12912	11692	10514
	1000/500	5434	4996	4563	4134	3721
	1000/1000 3797	3492	3191	2897	2613

Table 4 :

 4 Computational results of Algorithm 4 applied to the simplex constrained least squares problem (51).

		ε = 10 -3		ε = 10 -4
	k/l	Euclidean Entropy Euclidean Entropy
	100/100	423	128	1264	396
	100/500	645	179	1881	563
	100/1000	1008	191	2946	600
	500/100	1039	243	3187	726
	500/500	1399	329	4276	1026
	500/1000	1530	365	4570	1142
	1000/100	1752	367	5508	1115
	1000/500	2257	459	7079	1425
	1000/1000	2418	499	7507	1554

Table 5 :

 5 Computational results of Algorithm 5 applied to the elastic net problem (53). = 10 -2 λ 2 = 10 -3 λ 2 = 10 -2 λ 2 = 10 -3

		ε = 10 -3	ε = 10 -4
	k/l λ 2 100/100	445	1405	577	1823
	100/500	446	1339	624	1940
	100/1000	459	1319	703	2143
	500/100	1015	3209	1227	3879
	500/500	1189	3759	1486	4697
	500/1000	924	2869	1258	3950
	1000/100	1421	4494	1696	5363
	1000/500	1753	5542	2109	6667
	1000/1000	1707	5397	2123	6714
	7.3.1 Ergodic versus nonergodic sequence

using WolframAlpha to check our calculations.

Acknowledgments

This research is partially supported by the joint ANR/FWF Project Efficient Algorithms for Nonsmooth Optimization in Imaging (EANOI) FWF n. I1148 / ANR-12-IS01-0003. A.C. would

uniformly and independently distributed in the intervall [-1, 1]. We again denote by L = K the operator norm of K. The saddle-point formulation of (51) is given by min

Furthermore, the dual problem is given by

In turn, the primal-dual gap for a pair (x, y) can be easily computed by observing that arg min x∈∆ l L(x, y) = e j and also arg max y L(x, y) = Kx -b:

Accelerated primal-dual algorithms

Note that since the saddle-point problem is strongly convex in y, we can use the accelerated primal-dual algorithm presented in Algorithm 4 (by interchanging the role of the primal and the dual variables). Since L f = 0, we apply the simple parameter choice (39). We initialize the algorithms with the obvious choice (x 0 ) j = 1/l for all j and y 0 = Kx 0 -b. Recall that in the accelerated algorithm, we have fixed • y = • 2 and hence D y (y, y ) = 1 2 y -y 2 . Let us now consider two different setups of the algorithm:

1. Euclidean setting: In the Euclidean setting, we set

The operator norm L 2 = K is again given by s max (K). According to (37), we guaranteed that after N iterations for all (x, y) it holds that

Taking the supremum with respect to x on both sides, it follows

The right hand side is minimized by choosing τ 0 = 1/L 2 2 and σ 0 = 1 which gives the final estimate

where T N ∼ O(N 2 ) is defined in (36).


domain: scco info

text:
Nadine Glas
email: nadine.glas@telecom-paristech.fr

Catherine Pelachaud
email: catherine.pelachaud@telecom-paristech.fr

User Engagement and Preferences in Information-Giving Chat with Virtual Agents

We have performed a perceptive study that shows the existence of positive correlations between the user's preferences for an artwork (a physical object) and the user's engagement during the discussion of this object with a virtual agent. This finding encourages the development of agent dialogue strategies that personalise the topic of conversation in information-giving chat according to the user's preferences.

Introduction

Engagement is crucial in human-agent interaction as it is a prerequisite for the interaction to go on, and thus a prerequisite for the agent to deliver its messages and/or to complete the objective of the interaction [START_REF] Bickmore | Maintaining engagement in long-term interventions with relational agents[END_REF]. We consider engagement as "the value that a participant in an interaction attributes to the goal of being together with the other participant(s) and of continuing the interaction" [START_REF] Poggi | Mind, hands, face and body: a goal and belief view of multimodal communication[END_REF].

Previous research has demonstrated that a personalisation according to user preferences may contribute to, amongst others, an optimisation of user experience in game playing [START_REF] Yannakakis | Experience-driven procedural content generation[END_REF], an improvement in customer relationships [START_REF] Jiang | Mining preferences from superior and inferior examples[END_REF] and an enhancement of learning e ciency and experience [START_REF] Cha | Learning styles diagnosis based on user interface behaviors for the customization of learning interfaces in an intelligent tutoring system[END_REF]. In this study we explore if in non-task oriented human-agent interaction, an agent's personalisation according to the user's preferences can influence the user's engagement. Specifically, we will verify if the user's preference for a physical object (artwork) plays a role in the user's level of engagement during the discussion around this object with a virtual agent. The outcome of this perceptive study will be used to develop dialogue strategies for the virtual agent aiming at enhancing user engagement in human-agent interaction.

In the following two sections we define the type of interaction we look at and introduce the notion of preferences. In section 4 we present our methodology and in section 5 our results. In section 6 we conclude and discuss our findings.

Information-Giving Chat

The current research is conducted in the context of the French project 'Avatar 1:1' that aims at developing a human-sized virtual agent playing the role of a visitor in a museum. The agent's task is to engage human users in one-to-one face-to-face interaction about the museum and some of its artworks with the objective to give the visitors information about these subjects. The choice of the exact subject is secondary: what matters is that some amount of cultural information is transferred, as described also in [START_REF] Glas | Engagement driven topic selection for an information-giving agent[END_REF]. We refer to this type of interaction as an information-giving chat [START_REF] Glas | Engagement driven topic selection for an information-giving agent[END_REF] (as opposed to information-seeking chat [START_REF] Stede | Information-seeking chat: Dialogues driven by topicstructure[END_REF]). Like information-seeking chat [START_REF] Stede | Information-seeking chat: Dialogues driven by topicstructure[END_REF], information-giving chat has a more exploratory and less task-oriented nature but is more structured than general free conversation [START_REF] Glas | Engagement driven topic selection for an information-giving agent[END_REF].

Our aim is to explore if a personalisation of the topic of conversation based on the user's preferences of artworks (explained in Section 3) is likely to enhance the user's engagement, thereby augmenting the interaction time and thus the agent's opportunities to transfer cultural information.

Preferences

We interpret a preference according to the definition of Scherer [START_REF] Scherer | What are emotions? And how can they be measured?[END_REF] as "a relatively stable evaluative judgement in the sense of liking or disliking a stimulus". Preferences are everywhere in our daily lives [START_REF] Kießling | Foundations of preferences in database systems[END_REF] and the development of personalised content based on preferences increases in multiple domains of humancomputer interaction, such as e-commerce, news reading and computer games [START_REF] Yannakakis | Experience-driven procedural content generation[END_REF].

In the domain of non-task oriented human-virtual agent interaction, user personalisation is also increasing. Variables taken into account include the user's a↵ective state [START_REF] Prendinger | The empathic companion: A character-based interface that addresses users' a↵ective states[END_REF][7] [START_REF] Leite | Empathic Robots for Long-term Interaction[END_REF], emotions [START_REF] Paiva | Caring for agents and agents that care: Building empathic relations with synthetic agents[END_REF], appearance [START_REF] Paiva | Caring for agents and agents that care: Building empathic relations with synthetic agents[END_REF], expressions of appreciation [START_REF] Campano | Alignement par production d'Hétéro-Répétitions chez un ACA[END_REF] and politeness and formality [START_REF] De | Politeness and alignment in dialogues with a virtual guide[END_REF]. In the present work we will verify if we should augment this list with user preferences that are directly linked to the topic of conversation. Our goal is namely, to explore if a personalised topic of conversation according to the user's preferences regarding physical objects is likely to enhance the user's engagement. Some previously built virtual agent systems give their users the opportunity to directly select or reject the topics of interaction [3][12], thereby already adapting the interaction to some notion of user preference. However, these preferences only represent a choice of the user for certain information. The systems do not take into account the user preferences that may underlie the user's choice. In our work we will verify if the user's preferences towards the physical objects under discussion play a role in the user's interest for the discussion and his/her engagement. This will give us indications for the development and usefulness of dialogue strategies aiming at agent initiated topic selection.

Methodology

In order to find out if the user's preference for a museum object (artwork) plays a role in the user's level of engagement during the discussion of this artwork with a virtual agent we performed a perceptive study: We asked human participants one by one to visit a small improvised museum, talk with a virtual agent called Leonard, and fill in a questionnaire. Below we briefly discuss each of these steps. Fig. 2. The 'statue' between the agent and the user.

Museum

Since the project's avatar Leonard is not yet installed in the museum, we simulated a small museum in our laboratory; We exhibited 4 pictures of existing artworks in a first room and gave each participant as much time as he/she needed to observe the artworks, just as they would do in a regular museum (Fig. 1).

The artworks are shown in Appendix A and were chosen as to vary in style and type of a↵ect they might evoke: a photo of the exhibition of Balloon Dog by Je↵ Koons, and printed images of the paintings The Kiss by Gustav Klimt, Composition A by Piet Mondrian, and The Anatomy Lesson of Dr. Frederick Ruysch by Jan Van Neck. When the participant indicated that he/she finished looking at the artworks we explained that the visit would continue in the next room and that there he/she will talk with Leonard, a virtual character who also visits the museum. We placed another artwork between the screen of the virtual agent and the user that serves as a first conversation topic (Fig. 2): a picture of a statue named Soldier drawing his Bow, by Jacques Bousseau (Appendix A).

Virtual Agent and Interaction

A technical limit for interacting with Leonard is that at the moment we do not dispose of reliable speech recognition and natural language understanding modules. To resolve these issues we used a Wizard of Oz: we predefined keywords with which the participants needed to formulate their reaction (Fig. 3) and then transmitted the user's choice for that keyword to the agent. The keywords represent branches in the agent's predefined dialogue tree, meaning that the use of each keyword can lead to a particular predefined agent response. The dialogue tree is developed by using the hierarchical task network Disco for Games [START_REF] Rich | Using collaborative discourse theory to partially automate dialogue tree authoring[END_REF]. When the participant entered the room Leonard started the interaction. Leonard has the appearance of a cartoon-like version of a man of about 70 years old, is displayed on a 75-inch vertically placed screen, and speaks French. The user was recorded with two kinects and one camera (Fig. 2).

In the first couple of turns Leonard presented itself and asked for the name and region of the user. This small talk phase (in the sense of [START_REF] Bickmore | Small talk and conversational storytelling in embodied conversational interface agents[END_REF]) serves to let the user get used to the character and the way of interacting [START_REF] Bickmore | Small talk and conversational storytelling in embodied conversational interface agents[END_REF]).

After the small talk phase Leonard started talking about the artwork in front of it (Fig. 2) as a way to open the conversation about the artworks. Then, the agent switched to discuss the other artworks of the improvised museum. For every artwork Leonard provided some information about the object, asked what the participant thinks of it, and optionally expressed its own opinion (as described in [START_REF] Campano | Workshop on Engagement in Human Computer Interaction[END_REF]). The order in which the 4 artworks from the first room were discussed was random and changed among the participants. After the discussion of all artworks Leonard closed the conversation. Depending on the user utterance lengths the entire interaction took between 6 and 10 minutes.

Questionnaire

Directly after the interaction the participants were presented a questionnaire.

To estimate the user's level of engagement during the di↵erent phases of the interaction we used the definition of Poggi et al. [START_REF] Poggi | Mind, hands, face and body: a goal and belief view of multimodal communication[END_REF] (see introduction), by asking Q1) to what extent the user wants to be together with Leonard and Q2) to what extent the user wants to continue the interaction during the di↵erent discussion phases. The di↵erent discussion phases for which these questions were asked were: the small talk phase (name and region), and each separate discussion around an artwork. All the questions needed to be answered on a 7 point scale ranging from not at all to extremely. We also asked Q3) to what extent the user was interested in the discussion during the di↵erent phases.

In order to estimate the preferences of the users we asked the participants Q4) to what extent they like the di↵erent artworks (according to Scherer's definition [START_REF] Scherer | What are emotions? And how can they be measured?[END_REF], see section 3) and Q5) to what extent they find them interesting.

Results

33 participants took part in the study (13 female, aged 19-58, all proficient in French). Analyses of the data show that the participants' degrees of liking an artwork is significantly, positively correlated to the users' engagement during the discussion of that artwork with Leonard (Kendall Tau tests). This is the case for both of the aspects of engagement we looked at: wanting to be together with Leonard (Q1, p <0.001, ⌧ = 0.50) and wanting to continue the interaction (Q2, p <0.001, ⌧ = 0.52). These results are obtained by taking, for all the participants, and all the 4 (in random order discussed) artworks from the first room, the participants' degree of liking the artwork (Q4), and comparing this with the scores that the participants attributed to their engagement during the corresponding discussion phases of all these artworks.

In the same way as above, a positive correlation is found between the extent to which the users found an artwork interesting (Q5) and their level of both engagement measurements during the discussion of this artwork (p <0.001, Q1: ⌧ = 0.45, Q2: ⌧ = 0.54). The users' liking and interest for an artwork are also positively correlated to the extent to which the participants found the discussion of the artwork interesting (Q3) (p <0.001, liking Q4: ⌧ = 0.56; interest Q5: ⌧ = 0.49).

For all of the above results, possible e↵ects of novelty [START_REF] Leite | Empathic Robots for Long-term Interaction[END_REF] are outbalanced by the random order in which the artworks were discussed. The discussion of the artwork that is located between the agent and the user (Fig. 2) and that is always discussed first, before the in random order discussed museum objects, does not lead to a significant di↵erent level of engagement or interest in the discussion than the other artworks (Kruskal-Wallis).

Conclusion & Discussion

The results of the perceptive study show that the user's liking (i.e. preference, see section 4.3) and interest of a museum artwork are significantly, positively correlated with the user's engagement and interest during the discussion of this artwork with a virtual agent. We can therefore confirm our hypothesis that the user's preferences of the physical object (artwork) under discussion play a role in the user's level of engagement in non-task oriented human-agent interaction. This conclusion is illustrated by comments from the participants: "This (answer)

shows that wanting to stay with Leonard depends on how much I find the topic interesting." "Talking about a work that I don't like is not pleasant and makes me less involved in the interaction".

From this finding we can derive that one of the agent's dialogue strategies that is likely to favour user engagement in information-giving chat is personalising the topic of conversation according to the user's preferences regarding the underlying objects. The other way around, the revealed positive correlations also indicate that by detecting a level of user engagement during the interaction we can obtain indications with respect to the user's preference towards the current topic of conversation and its underlying object. These two conclusions have lead us to develop an agent model that tries to enhance the user's engagement by personalising the topic of the interaction, as described in [START_REF] Glas | Engagement driven topic selection for an information-giving agent[END_REF].

We found no significantly di↵erent level of engagement or interest during the discussion of the object that was physically present during the interaction in comparison with the objects that were located in another room. This means that this study does not give us reasons to suspect that the physical presence of an object is required in order to engage the user.

In the future we plan to verify to what extent, and how exactly, a personalisation within the discussion phase of an artwork (object) may influence the user's engagement. The fact that the correlations we found have ⌧ -values around 0.50, confirms the expectation that there are more variables than just the topic of the interaction that influence the user's engagement. We would also like to consider what the consequences are of adapting the topic of conversation to the user preferences on the entire interaction and the overall engagement level of the user.

Fig. 1 .

 1 Fig. 1. The improvised museum.Fig.2. The 'statue' between the agent and the user.

Fig. 3 .

 3 Fig. 3. Leonard and the keywords that are needed to talk with it.

Fig. 4 .

 4 Fig. 4. The setting of the interaction.

Acknowledgements

We would like to thank all the participants of the study. This research is partially funded by the French national project Avatar 1:1, ANR MOCA, and the Labex SMART (ANR-11-LABX-65) which is supported by French state funds managed by the ANR, within the Investissements d'Avenir program under reference ANR-11-IDEX-0004-02.