Pauline Tan

Acceleration of saddle-point methods in smooth cases

published or not. The documents may come

Acceleration of saddle-point methods in smooth cases

Introduction 1.Context

The Alternating Direction Methods of Multipliers (ADMM) is a widely-used method aimed at minimizing constrained problems of form min (x,z)∈X×Z Ax+Bz=c g(x) + h(z).

(

The objective function is separable in (x, z) with g : X → R ∪ {+∞} and h : Z → R ∪ {+∞} two closed convex functions. The constraint involves two linear operators A : X → Y and B : Z → Y and a constant c ∈ Y . In this work, X, Z, and Y are finitedimensional real Hilbert spaces. The ADMM was initially introduced in the mid-70's by Gabay-Mercier [START_REF] Gabay | A dual algorithm for the solution of nonlinear variational problems via finite element approximation[END_REF] and by Glowinski-Marrocco [START_REF] Glowinski | Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité d'une classe de problèmes de dirichlet non linéaires[END_REF]. It considers the augmented Lagrangian associated to problem [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF] L τ (x, z; y) := g(x) + h(z)

+ Ax + Bz -c, y + 1 2 τ Ax + Bz -c 2 (2)
for τ > 0 which leads to solve the saddle-point problem min

(x,z)∈X×Z sup y∈Y L τ (x, z; y) (3)
instead of the initial problem. One particular instance of these so-called augmented Lagrangian methods uses Uzawa's method to solve [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF]. Namely, the method of multipliers tackles this problem by alternating an exact minimization on the primal variable (x, z) and a gradient ascent step on the dual variable y. In such a method, the minimization step couples the primal variables. To decouple them, one may consider splitting this step into two partial minimizations, one over x and another over z. These two minimization can be done simultaneously, from the same initial points, or, in the case of the ADMM, one after the other, with an update in between. This leads to the following algorithm

             x n+1 = arg min x∈X L τ (x, z n ; y n ) z n+1 = arg min z∈Z L τ (x n+1 , z; y n ) y n+1 = y n + 1 τ (Ax n+1 -z n+1 ). (4)
This method can be proved to be linked to another famous algorithm, which is known as the Primal-Dual Hybrid Gradient (PDHG) method [START_REF] Zhu | An efficient primal-dual hybrid gradient algorithm for total variation image restoration[END_REF]. The PDHG method tackles saddle-point problems by alternating gradient descent steps and gradient ascent steps. Such problems arise while considering a primal-dual formulation of a convex minimization problem, in a splitting strategy for instance. A noteworthy feature of the PDHG method is that it can be accelerated thanks to an overrelaxation step à la Nesterov [START_REF] Nesterov | A method of solving a convex programming problem with convergence rate o(1/k 2 )[END_REF] on one of the variables [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][START_REF] Esser | A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science[END_REF][START_REF] Chambolle | On the ergodic convergence rates of a firstorder primal-dual algorithm[END_REF], which leads to the overrelaxed PDHG (oPDHG).

The ADMM has been intensively studied in the past years. One may see for instance a comprehensive review in [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF]. The key point is the convergence of the algorithm and its convergence rate. Under assumptions on the matrix ranks and / or the regularity of the objective functions g and h, linear rates can be achieved [START_REF] Hong | On the linear convergence of the alternating direction method of multipliers[END_REF]. Eventually, some accelerated variants of the ADMM have been proposed [START_REF] Deng | On the global and linear convergence of the generalized alternating direction method of multipliers[END_REF][START_REF] Davis | Faster convergence rates of relaxed peacemanrachford and admm under regularity assumptions[END_REF].

As a recent developpement, we should mention [START_REF] He | On the convergence of primal-dual hybrid gradient algorithm[END_REF], which also studied the convergence of the PDHG method and derived optimal step size choice, when only one function assumed to be strongly convex.

Contribution of this paper

In this paper, we provide a new analysis of the ADMM based on the equivalence between the ADMM and the oPDHG method. More specifically, we use the analysis to derive convergence rate for the ADMM in a case we refer to be smooth. We indeed made restrictive assumptions on the initial problem [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF], which implies that we consider the following particular instance of (1): min

(x,z)∈X×Y Ax=z g(x) + h(z). (5)
which may be rewritten as the unconstrained composite problem min x∈X g(x) + h(Ax) [START_REF] Davis | Faster convergence rates of relaxed peacemanrachford and admm under regularity assumptions[END_REF] with regularity assumptions on g, which is supposed to be strongly convex, and h, which has a Lipschitz gradient. We first establish new linear ergodic convergence rates of the oPDHG by generalizing the proofs of [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF][START_REF] Chambolle | On the ergodic convergence rates of a firstorder primal-dual algorithm[END_REF]. This leads to a linear rate for the ADMM under these assumptions. Then, we introduce a slight variant of the ADMM which leads to a better rate, by relaxing the choice of the parameters in the convergence proof of the oPDHG method.

The reason why we only consider the case B = -Id and c = 0 is that, otherwise, as the map y → h * (B * y) will be supposed to be strongly convex, this implies that ∇f is Lipschitz continuous and that B is invertible. Such conditions are artificial when B is not -Id. However, the interested reader will easily extend our result to this case. Moreover, problems of standard form [START_REF] Davis | Faster convergence rates of relaxed peacemanrachford and admm under regularity assumptions[END_REF] often arise in many contexts, and thus can justify a special study by themselves.

Structure of the paper

This paper is organized as follows. In Section 2, we recall the equivalence between the ADMM and the oPDHG method. We also define what we call the smooth case, which is the case we will consider throughout this paper. In Section 3, we establish two linear convergence results for the oPDHG, and we provide the best parameter choice in the case where the overrelaxation parameter is fixed to be 1 or left unconstrained. In Section 4, we exploit the equivalence between the ADMM and the oPDHG to derive from the results of Section 3 new linear convergence rate for the ADMM. We also propose a slight variant of the ADMM, which leads in the best case to the same convergence rate as the oPDHG method. In Section 5, we compare our results with some found in the literature for the classical ADMM or variants, in the case where the assumptions made on the problem yield a linear convergence rate. Those assumptions do not necessary include the smooth case studied here. Eventually, in Section 6, we applied our accelerated ADMM on two problems, and compared its convergent with the unaccelerated ADMM, the oPDHG and an adaptation of Beck and Teboulle's FISTA [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF] for the strongly convex case [START_REF] Nesterov | Introductory lectures on convex optimization[END_REF][START_REF] Chambolle | An introduction to continuous optimization for imaging[END_REF].

2 Equivalence between the ADMM and the oPDHG

Initial primal problem

Let X and Y be two finite-dimensional real Hilbert spaces. The inner product is denoted by •, • and • stands for the induced norm. We recall that we consider the minimization problem min

x∈X f (x) := g(x) + h(Ax) (7)
where g : X → R ∪ {+∞} and h : Y → R ∪ {+∞} are proper, convex, and lower semi-continuous (l.s.c.) functions. The map A : X → Y is a continuous linear operator. Its adjoint is denoted by A * and it is supposed to be bounded, of norm

L A L A := A = sup x∈X, x ≤1 Ax . (8)

Equivalence with oPDHG

Let us briefly recall how the ADMM is connected to the oPDHG algorithm, by rewritting the ADMM iterations (4) applied on Problem [START_REF] Deng | On the global and linear convergence of the generalized alternating direction method of multipliers[END_REF]. Ignoring the constant terms in the minimization steps, we obtain

                   x n+1 = arg min x∈X g(x) + Ax, y n + 1 2 τ Ax -z n 2 z n+1 = arg min z∈Y h(z) -z, y n + 1 2 τ Ax n+1 -z 2 y n+1 = y n + 1 τ (Ax n+1 -z n+1 ). (9)
Defining ξ n+1 := Ax n+1 and introducing the map

g A (ξ) := inf x∈X,Ax=ξ g(x) (10)
we can make a change of variable in the x-update and rewrite the updates of x n+1 and y n+1 thanks to proximity operators. This yields

         ξ n+1 = prox τ g A ξ n -τ ȳn y n+1 = prox h * /τ (y n + ξ n+1 /τ ) ȳn+1 = y n+1 + (y n+1 -y n ) (11)
and the z-update is given by z n+1 = ξ n+1 -τ (y n+1 -y n ). This primal-dual algorithm has been studied in [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF]. It can be interpreted as an PDHG algorithm with an additional overrelaxation step (of parameter 1) on the dual variable. It solves the saddle-point problem min

ξ∈Y sup y∈Y g A (ξ) + ξ, y -h * (y) (12)
which is of general form

min ξ∈Z sup y∈Y L(ξ; y) := G(ξ) + Kξ, y -H * (y) (13)
with Z = Y , K = Id, G = g A and H = h. Note that ( 13) is the primal-dual formulation of the minimization problem

min ξ∈Z G(ξ) + H(Kξ) . ( 14
)

Smooth case

From now on, we consider the smooth case. In the initial primal problem [START_REF] Deng | On the global and linear convergence of the generalized alternating direction method of multipliers[END_REF], the functions g and h * are both supposed to be strongly convex, with respective parameter γ > 0 and δ > 0. We recall that a function f : X → R ∪ {+∞} is strongly convex of parameter α > 0 (f is also said to be α-convex) if for any x 1 , x 2 ∈ X and p ∈ ∂f (x 1 )

f (x 2 ) ≥ f (x 1 ) + p, x 2 -x 1 + α 2 x 2 -x 1 2 (15)
where ∂f (x 1 ) denotes the subdifferential of f at point x 1 . One can easily check that if f is α-convex, then its convex conjugate f * is differentiable, with a Lipschitz continuous gradient, of constant 1/α. Let us study the regularity of Problem [START_REF] Nesterov | A method of solving a convex programming problem with convergence rate o(1/k 2 )[END_REF]. The assumptions made above imply obviously that H * is δ-convex. Moreover, it is easy to show that G * is differentiable and that ∇G * is Lipschitz continuous with constant L 2 A /γ, which follows from

g * A (y + t) = g * A * (y + t) = g * (A * y) + ∇g * (A * y), A * t + o( A * t ) ( 16
) since g is γ-convex. Hence, G is γ/L 2 A -convex. Let γ = γ/L 2 A and δ = δ. We define κ f := L 2
A /(δγ) the condition number of f as the ratio between L 2 A /δ the Lipschitz constant of the smooth part h(K•) and γ the strong convexity parameter of the non-smooth part g. In the case where f is both smooth with ∇f lipschitz continuous and strongly convex, this definition recovers the one usually used in such cases and the condition number is always larger than 1. In the general case, it can be less than 1. When κ f is large, the function is said ill-conditioned.

Forward-backward splitting

If h is differentiable, it is possible to consider a forward-backward splitting (FBS) strategy to solve problem [START_REF] Deng | On the global and linear convergence of the generalized alternating direction method of multipliers[END_REF]. The FBS applied on the sum f = g + h(A•) gives updates of form

x n+1 = prox τ g x n -τ A * ∇h(Ax n ) . (17)
Hence, choosing to use the FBS instead of the ADMM or the oPDHG method suggests that ∇h is supposed to be easier to compute than prox h . A variant of the FBS is FISTA [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF], which adds an extra overrelaxation step. It can be adapted to solve for strongly convex problems following [START_REF] Nesterov | Introductory lectures on convex optimization[END_REF], see [START_REF] Chambolle | An introduction to continuous optimization for imaging[END_REF]Appendix B] for details. In other terms, the updates (17) are replaced by

x n+1 = prox τ g xn -τ A * ∇h(Ax n ) xn+1 = x n+1 + θ n+1 (x n+1 -x n ) ( 18
)
where the variable overrelaxation parameter θ n is chosen in the strongly convex case by letting

t n+1 = 1 -q t 2 n + (1 -q t n 2 ) 2 + 4 t n 2 2 ( 19
)
for q = τ γ/(1 + τ γ) for τ ∈ (0, δ/L 2 A ]. We will refer to this algorithm as 'strongly convex FISTA' in this paper. Then,

θ n = 1 + τ γ(1 -t n+1 ) t n -1 t n+1 . ( 20
)
In the non-strongly convex case (γ = δ = 0), the quantity q is null, and the resulting updates of t n and θ n are those in the original paper of Beck and Teboulle. When g is assumed to be strongly convex and h(A• ) has a L 2 A /δ-Lipschitz gradient, the convergence rate for the objective error of this algorithm has been proved to be linear. In the case where t (and thus, θ) is chosen to be constant

t n = t = 1 √ q and θ n = θ = (1 - √ q) 2 1 + τ γ 1 -τ γ (21)
then the linear rate is of parameter 1 -√ q [5, Remark B.2]. This rate is minimal when τ is maximal and equals

ω = 1 - δγ/L 2 A 1 + δγ/L 2 A = 1 - 1 κ f + 1 . (22)
Note that if g is γ-convex then this so is f . Hence, the optimality condition on x * coupled with the strong convexity inequality recalled in (15) yields

f (x n ) -f (x * ) ≥ γ 2 x n -x * 2 (23)
that is, a linear convergence for the objective error implies a linear convergence of at least same rate for the convergence of the primal iterate x n .

3 Convergence of oPDHG in the smooth case

In this section, we establish the general convergence proof of the following algorithm

         y n+1 = prox σH * (y n + σ K ξn ) ξ n+1 = prox τ G ξ n -τ K * y n+1 ξn+1 = ξ n+1 + θ (ξ n+1 -ξ n ). (24)
which aims at solving problem [START_REF] Nesterov | A method of solving a convex programming problem with convergence rate o(1/k 2 )[END_REF], in the general case where

K : Z → Y is bounded of norm L K , G : Z → R ∪ {+∞} is γ-convex and H * : Y → R ∪ {+∞} is δ-convex.
The step sizes τ, σ > 0 and the relaxation parameter 0 < θ ≤ 1 are to be specified. When θ = 0, this algorithm is known as the PDHG method [START_REF] Zhu | An efficient primal-dual hybrid gradient algorithm for total variation image restoration[END_REF]. It consists in a proximal gradient ascent step for the dual variable, followed by a proximal gradient descent step for the primal variable. The overrelaxation step has been added in [START_REF] Pock | An algorithm for minimizing the mumford-shah functional[END_REF] for minimizing the Mumford-Shah functional, and studied in a wider framework in [START_REF] Esser | A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science[END_REF] and more recently in [START_REF] Chambolle | On the ergodic convergence rates of a firstorder primal-dual algorithm[END_REF]. The case θ = 1 and τ σ = 1 corresponds to the equivalence with the ADMM, as recalled in the previous section. When θ = 1 and τ σ = 1, the iterations are equivalent to the ADMM with an additional proximal term [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF], which leads to a preconditioned version of the ADMM [START_REF] Esser | A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science[END_REF]. Now we can formulate our main result.

Theorem 1 Assume problem (13) has a solution, which is a saddle-point of L, denoted by (ξ * , y * ). Choose τ > 0, σ > 0 and 0 < θ ≤ 1 such that

max 1 τ γ + 1 , 1 σ δ + 1 ≤ θ ≤ 1 L 2 K τ σ . ( 25
)
Then, for any ω such that

max 1 τ γ + 1 , θ + 1 σ δ + 2 ≤ ω ≤ θ (26)
we have the following majoration for any N ∈ N and any (ξ, y) ∈ Z × Y :

1 2τ ξ N -ξ 2 + (1 -ωL 2 K τ σ) 1 2σ y N -y 2 + N n=1 ω n ω n-1 L(ξ n ; y) -L(ξ; y n ) ≤ ω N 2τ ξ 0 -ξ 2 + ω N 2σ y 0 -y 2 (27)
where (ξ n , y n ) n are generated by Algorithm (24). Hence, if we define

T N := N n=1 1 ω n-1 = 1 -ω N ω N -1 (1 -ω) (28)
and let

Ξ N := 1 T N N n=1 1 ω n-1 ξ n and Y N := 1 T N N n=1 1 ω n-1 y n . ( 29
)
Then we have the following bound for any (ξ, y) ∈ Z × Y :

1 -ω ω(1 -ω N ) 1 2τ ξ -ξ N 2 + 1 -ω ω(1 -ω N ) (1 -ωL 2 K τ σ) 1 2σ y -y N 2 + L(Ξ N ; y) -L(ξ; Y N ) ≤ 1 T N 1 2τ ξ -ξ 0 2 + 1 T N 1 2σ y -y 0 2 . ( 30
)
This theorem provides a linear ergodic convergence rate, namely for the sequences (Ξ N ) and (Y N ). This rate can be compared with [START_REF] Nesterov | Introductory lectures on convex optimization[END_REF], and will proved to be better with optimal parameters. Also note that no assumption is made about the rank of the linear operator K. Equation (30) can be applied to ξ = ξ * and y = y * , which yields a nonergodic linear convergence rate for the variable convergence (see subsection 3.1.3).

A similar result may be found in [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF], but the rate we provide here is better, since no restrictive assumptions are made on the parameters values, unless necessary.

Proof of convergence

We proceed analogously to the proof in [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF], but we do not specify any parameter unless needed. This proof is also inspired by the one found in [START_REF] Chambolle | On the ergodic convergence rates of a firstorder primal-dual algorithm[END_REF], which does not allow θ = 1. For now, we only assume that 0 < θ ≤ 1.

Preliminaries

Let us consider the general updates (ŷ, ξ) by setting for any ( ξ, ξ)

∈ Z 2 and (ȳ, ỹ) ∈ Y 2    ŷ := prox σH * (ȳ + σK ξ) ξ := prox τ G ( ξ -τ K * ỹ). ( 31
)
In other terms, ŷ and ξ are the output of an iteration, and are respectively computed from initial points (ȳ, ξ) and (ỹ, ξ). These points are related by first-order optimality conditions. For instance, the point ξ is defined as the solution of a minimization problem

ξ = arg min ξ∈Z 1 2τ ξ -τ K * ỹ -ξ 2 + G(ξ) (32)
so, by optimality, we obtain

- 1 τ ( ξ -ξ) -K * ỹ ∈ ∂G( ξ). ( 33
)
Similarly, the definition of ŷ yields

- 1 σ (ŷ -ȳ) + K ξ ∈ ∂F * (ŷ). ( 34
)
Using the definition of strong convexity recalled in [START_REF] Nishihara | A general analysis of the convergence of admm[END_REF], we get (after expanding the scalar products)

G(ξ) + 1 2τ ξ -ξ 2 ≥ G( ξ) + K( ξ -ξ), ỹ + 1 2τ ξ -ξ 2 + 1 2τ ξ -ξ 2 + γ 2 ξ -ξ 2 (35) H * (y)+ 1 2σ y -ȳ 2 ≥ H * (ŷ)-K ξ, ŷ -y + 1 2σ ŷ -ȳ 2 + 1 2σ y -ŷ 2 + δ 2 y -ŷ 2 . (36)
Now, summing (35) and (36), we have after rearrangement

L( ξ; y) -L(ξ; ŷ) ≤ 1 2τ ξ -ξ 2 - 1 + τ γ 2τ ξ -ξ 2 - 1 2τ ξ -ξ 2 + 1 2σ y -ȳ 2 - 1 + σ δ 2σ y -ŷ 2 - 1 2σ ȳ -ŷ 2 + K( ξ -ξ), ŷ -ỹ -K( ξ -ξ), ŷ -y .
(37)

First inequality

Let us now prove the following lemma:

Lemma 1 Let (ξ n , y n ) n be generated by Algorithm (24). Then, for any n ∈ N, τ, σ > 0 and 0 < ω ≤ θ, we have

L(ξ n ; y) -L(ξ; y n ) ≤ 1 2τ ξ -ξ n 2 + 1 2σ y -y n 2 - 1 ω 1 2τ ξ -ξ n+1 2 + 1 2σ y -y n+1 2 + ω 1 2τ ξ n-1 -ξ n 2 - 1 2τ ξ n -ξ n+1 2 + ω K(ξ n-1 -ξ n ), y -y n -K(ξ n -ξ n+1 ), y -y n+1 . ( 38
)
Proof We specify the six variables in (37), by choosing on one hand

ξ = ξ n+1 , ξ = ξ n , and ξ = ξ n + θ (ξ n -ξ n-1 ) (39)
for 1 ≥ θ > 0 not specified yet, and ŷ = y n+1 , ȳ = y n , and ỹ = y n+1 (40) on the other hand, which leads to the iterations in (24). After a simplification, we get

L(ξ n+1 ; y) -L(ξ; y n+1 ) ≤ 1 2τ ξ -ξ n 2 + 1 2σ y -y n 2 - 1 + τ γ 2τ ξ -ξ n+1 2 - 1 + σ δ 2σ y -y n+1 2 - 1 2τ ξ n -ξ n+1 2 - 1 2σ y n -y n+1 2 + θ K(ξ n-1 -ξ n ), y -y n+1 -K(ξ n -ξ n+1 ), y -y n+1 . (41)
Now, we define τ γ = µ > 0 and σ δ = µ > 0. For any n ∈ N, we set

∆ n = 1 2τ ξ -ξ n 2 + 1 2σ y -y n 2 . (42)
Hence, we can rewrite (41) with ∆ n , which yields

L(ξ n+1 ; y) -L(ξ; y n+1 ) ≤ ∆ n -(1 + µ) ∆ n+1 - 1 2τ ξ n -ξ n+1 2 - 1 2σ y n -y n+1 2 + θ K(ξ n-1 -ξ n ), y -y n+1 -K(ξ n -ξ n+1 ), y -y n+1 + µ -µ 2σ y -y n+1 2 . ( 43
)
Let us bound the scalar products in (43). For any 0 < ω ≤ θ, we have the decomposition

θ K(ξ n-1 -ξ n ), y -y n+1 = ω K(ξ n-1 -ξ n ), y -y n + ω K(ξ n-1 -ξ n ), y n -y n+1 + (θ -ω) K(ξ n-1 -ξ n ), y -y n+1 . (44)
Let us have a closer look at the last two terms. Let α > 0. Since ω ≥ 0, we have

ω K(ξ n-1 -ξ n ), y n -y n+1 ≤ ω L K ξ n-1 -ξ n • y n -y n+1 ≤ ω L K α 2 ξ n-1 -ξ n 2 + 1 2α y n -y n+1 2 . (45) Similarly, since θ -ω ≥ 0, (θ -ω) K(ξ n-1 -ξ n ), y -y n+1 ≤ (θ -ω) L K α 2 ξ n-1 -ξ n 2 + 1 2α y -y n+1 2 . ( 46
)
After simplification, the majoration (43) becomes, thanks to inequalities (45) and (46),

L(ξ n+1 ; y) -L(ξ; y n+1 ) ≤ ∆ n -(1 + µ) ∆ n+1 + θ L K α 2 ξ n-1 -ξ n 2 - 1 2τ ξ n -ξ n+1 2 + ω L K 2α - 1 2σ y n -y n+1 2 + ω K(ξ n-1 -ξ n ), y -y n -K(ξ n -ξ n+1 ), y -y n+1 + (θ -ω) L K 2α + µ -µ 2σ y -y n+1 2 . ( 47
)
Choose α = ωL K σ. Hence, we have ωL K /α = 1/σ, so that the y n -y n+1 2 term cancels. This leads to:

L(ξ n+1 ; y) -L(ξ; y n+1 ) ≤ ∆ n -(1 + µ) ∆ n+1 + ω θL 2 K τ σ 2τ ξ n-1 -ξ n 2 - 1 2τ ξ n -ξ n+1 2 + ω K(ξ n-1 -ξ n ), y -y n -K(ξ n -ξ n+1 ), y -y n+1 + θ -ω ω + µ -µ 1 2σ y -y n+1 2 .
(48)

Since 1 + µ = 1/ω + 1 + µ -1/ω, we have -(1 + µ) ∆ n+1 = - 1 ω ∆ n+1 + 1 ω -µ -1 1 2τ ξ -ξ n+1 2 + 1 2σ y -y n+1 2 (49)
so the right-hand side of (48) becomes

∆ n - 1 ω ∆ n+1 + ω θL 2 K τ σ 2τ ξ n -ξ n-1 2 - 1 2τ ξ n -ξ n+1 2 + ω K(ξ n-1 -ξ n ), y -y n -K(ξ n -ξ n+1 ), y -y n+1 + 1 ω -µ -1 1 2τ ξ -ξ n+1 2 + θ -ω ω + 1 ω -µ -1 1 2σ y -y n+1 2 .
(50)

It is now time to set conditions on ω, θ, τ and σ. First, choose θ, τ and σ so that θL 2 K τ σ ≤ 1. Then, choose θ so that both 1/ω -µ -1 and (θ -ω)/ω + 1/ω -µ -1 are nonpositive, which implies that

1 µ + 1 ≤ ω ≤ θ and θ + 1 µ + 2 ≤ ω ≤ θ. (51)
Then we can bound (50) by

∆ n - 1 ω ∆ n+1 + ω 1 2τ ξ n-1 -ξ n 2 - 1 2τ ξ n -ξ n+1 2 + ω K(ξ n-1 -ξ n ), y -y n -K(ξ n -ξ n+1 ), y -y n+1 . (52)
Eventually, back to (48) we get the wanted inequality

L(ξ n+1 ; y) -L(ξ; y n+1 ) ≤ ∆ n - 1 ω ∆ n+1 + ω 1 2τ ξ n-1 -ξ n 2 - 1 2τ ξ n -ξ n+1 2 + ω K(ξ n-1 -ξ n ), y -y n -K(ξ n -ξ n+1 ), y -y n+1 .
(53)

Linear convergence of the iterates

Multiplying (53) by 1/ω n and summing between n = 0 and n = N -1 (choose ξ -1 = ξ 0 ) cancels most of the terms:

N n=1 1 ω n-1 L(ξ n ; y) -L(ξ; y n ) ≤ ∆ 0 - 1 ω N ∆ N - 1 2τ ω N -1 ξ N -1 -ξ N 2 - 1 ω N -1 K(ξ N -1 -ξ N ), y -y N . (54)
Once again, we bound the scalar product: let β > 0,

- 1 ω N -1 K(ξ N -1 -ξ N ), y -y N ≤ L K ω N -1 β 2 ξ N -1 -ξ N 2 + 1 2β y -y N 2 (55)
and inequality (54) becomes

N n=1 1 ω n-1 L(ξ n ; y) -L(ξ; y n ) ≤ ∆ 0 - 1 ω N ∆ N + L K β 2ω N -1 - 1 2τ ω N -1 ξ N -1 -ξ N 2 + L K ω N -1 1 2β y N -y 2 . ( 56
)
Now choose β = 1/(L K τ ), which cancels the ξ N -1 -ξ N 2 term, and we get

N n=1 1 ω n-1 L(ξ n ; y) -L(ξ; y n ) ≤ ∆ 0 - 1 ω N ∆ N + L 2 K τ σ ω N -1 1 2σ y -y N 2 . ( 57
)
Replacing ∆ 0 and ∆ n by their respective definition, we obtain

N n=1 1 ω n-1 L(ξ n ; y) -L(ξ; y n ) ≤ 1 2τ ξ -ξ 0 2 + 1 2σ y -y 0 2 - 1 ω N 1 2τ ξ -ξ N 2 - 1 ω N (1 -ωL 2 K τ σ) 1 2σ y -y N 2 . ( 58
) Since ωL 2 K τ σ ≤ θL 2 K τ σ ≤ 1 and L(ξ n ; y) -L(ξ; y n ) ≥ 0 for any n ∈ N, we have 0 ≤ 1 2τ ξ -ξ N 2 + (1 -ωL 2 K τ σ) 1 2σ y -y N 2 + N n=1 ω N ω n-1 L(ξ n ; y) -L(ξ; y n ) ≤ ω N 2τ ξ -ξ 0 2 + ω N 2σ y -y 0 2 . ( 59
)
The latter inequality proves the linear convergence of the iterates:

Corollary 1 Assume problem (13) has a solution, which is a saddle-point of L, denoted by (ξ * , y * ). Let (ξ n , y n ) n be generated by Algorithm (24). Suppose there exist τ , σ, θ and ω satisfying both conditions (25) and (26). Then, for any N ∈ N, we have

ξ * -ξ N 2 ≤ ω N ξ * -ξ 0 2 + τ σ y * -y 0 2 . ( 60
)
Moreover, if ωL 2 K τ σ = 1, then we also have

y * -y N 2 ≤ ω N 1 -ωL 2 K τ σ σ τ ξ * -ξ 0 2 + y * -y 0 2 . ( 61
)
Remark: The convergence rate in Corollary 1 can be improved if we use the fact that, by definition,

L(ξ n+1 ; y * ) -L(ξ * ; y n+1 ) = G(ξ n+1 ) -G(ξ * ) + H * (y n+1 ) -H * (y * ) + Kξ n+1 , y * -Kξ * , y n+1 . ( 62
)
The strong convexity of G et H * and the optimality of ξ * and y * yield the following inequalities:

G(ξ n+1 ) -G(ξ * ) ≥ -K * y * , ξ n+1 -ξ * + γ 2 ξ n+1 -ξ * 2 (63) H * (y n+1 ) -H * (y * ) ≥ Kξ * , y n+1 -y * + δ 2 y n+1 -y * 2 . ( 64
)
This implies that

γ 2 ξ n+1 -ξ * 2 + δ 2 y n+1 -y * 2 ≤ L(ξ n+1 ; y * ) -L(ξ * ; y n+1 ) (65)
since the sum of the scalar products cancels. Hence, if we choose not to control the primal-dual gap, choosing (ξ, y) = (ξ * , y * ), in (41) becomes

0 ≤ 1 2τ ξ * -ξ n 2 + 1 2σ y * -y n 2 - 1 + 2τ γ 2τ ξ * -ξ n+1 2 - 1 + 2σ δ 2σ y * -y n+1 2 - 1 2τ ξ n -ξ n+1 2 - 1 2σ y n -y n+1 2 + θ K(ξ n-1 -ξ n ), y * -y n+1 -K(ξ n -ξ n+1 ), y * -y n+1 (66)
which means that all the computations from (41) to (59) hold, with µ and µ replaced by μ = 2µ and μ = 2µ and without L-terms, as well as the constraints on the parameters. In others terms, the same computations prove that Corollary 2 Assume problem (13) has a solution, which is a saddle-point of L, denoted by (ξ * , y * ). Let (ξ n , y n ) n be generated by Algorithm (24). Suppose there exist τ , σ, θ and ω satisfying both conditions

max 1 2τ γ + 1 , 1 2σ δ + 1 ≤ θ ≤ 1 L 2 K τ σ . ( 67
)
Then, for any ω such that

max 1 2τ γ + 1 , θ + 1 2σ δ + 2 ≤ ω ≤ θ. (68)
Then, for any N ∈ N, we have

ξ * -ξ N 2 ≤ ωN ξ * -ξ 0 2 + τ σ y * -y 0 2 . ( 69
)
Moreover, if ωL 2 K τ σ = 1, then we also have

y * -y N 2 ≤ ωN 1 -ωL 2 K τ σ σ τ ξ * -ξ 0 2 + y * -y 0 2 . ( 70
)
For given τ , σ and θ, the lower bounds 1/(2τ γ + 1) and (θ + 1)/(2σ δ + 2) for ω are smaller than those for ω. Thus, the new rate ω can be expected to be better than the global one ω (which is called global since it also holds for the objectif error, as shown in the next paragraph). This will be checked in Subsection 3.2.

End of the proof

We can now complete the proof of Theorem 1. Dividing (59) by ω N = 0 and by T N = 0, we get

1 -ω ω(1 -ω N ) 1 2τ ξ -ξ N 2 + 1 -ω ω(1 -ω N ) (1 -ωL 2 K τ σ) 1 2σ y -y N 2 + 1 T N N n=1 1 ω n-1 L(ξ n ; y) -L(ξ; y n ) ≤ 1 T N 1 2τ ξ -ξ 0 2 + 1 T N 1 2σ y -y 0 2 . (71)
But, by convexity,

L(Ξ N ; y) -L(ξ; Y N ) ≤ 1 T N N n=1 1 ω n-1 L(ξ n ; y) -L(ξ; y n ) (72)
Therefore, (71) becomes

1 -ω ω(1 -ω N ) 1 2τ ξ -ξ N 2 + 1 -ω ω(1 -ω N ) (1 -ωL 2 K τ σ) 1 2σ y -y N 2 + L(Ξ N ; y) -L(ξ; Y N ) ≤ 1 T N 1 2τ ξ -ξ 0 2 + 1 T N 1 2σ y -y 0 2 (73)
which completes the proof of Theorem 1.

Remark Equation (73) provides a way to establish the (ergodic) linear convergence of the objective function whe applied to (ξ, y) = (ξ * N , y * N ) where the supremum of the primal-dual gap is attained. The main argument relies on the Lipschitz continuity of the gradients of H and G * , which ensures that this point is close to (ξ * , y * ). A more detailed example of such computations is provided in Section 4 in the case of the ADMM.

Choice of parameters

Theorem 1 holds provided one can properly choose the steps τ and σ and the relaxation parameter θ. We study some particular choices for those parameters and the convergence rate they yield. Since a smaller ω leads to a faster convergence, we tune the algorithm parameters to minimize the lower bound of ω. Here is how we proceed:

1. Fix τ > 0.

2. Find conditions on σ so that inequalities (25) hold.

3. Minimize (θ + 1)/(σ δ + 2) with respect to (w.r.t.) θ satisfying (25) and w.r.t σ given by the previous step.

4. Compare this minimum to 1/(τ γ + 1) and deduce the lower bound ω * (τ ) for ω.

5. Minimize ω * (τ ) and derive the optimal rate ω * .

Since the resulting parameters are compatible with conditions (67) and ( 68), the lefthand member in (69) yields a better theoretical rate for the convergence of the variables. Besides, the same computations (with γ and δ doubled) may be used to choose the parameters so that the rate ω (Corollary 2) is minimal.

Case θ = 1

We first fix θ = 1. As shown in [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF], this choice is equivalent to the ADMM with an additional proximal term.

Fix τ > 0. Replacing θ = 1 in (25), we obtain that the steps τ and σ are constrained as following

1 ≤ 1 L 2 K τ σ (74)
which implies that σ ≤ 1/(L 2 K τ ). Then, (26) in Theorem 1 states that the convergence rate ω satisfies

max 1 τ γ + 1 , 1 σ δ/2 + 1 ≤ ω ≤ 1 ( 75
)
Let us minimize 1/(σ δ/2 + 1) w.r.t. σ satisfying (74). Since the map σ → 1/(σ δ/2 + 1) is nondecreasing, its minimum is reached when σ is maximal, which leads to min σ subject to (74)

1 σ δ/2 + 1 = 1 δ/(2L 2 K τ ) + 1 . (76)
Now, compare it to 1/(τ γ + 1). It is clear that the quantity 1/( δ/(2L 2 K τ ) + 1) is greater than 1/(τ γ + 1) as soon as τ 2 ≥ δ/(2γL 2 K ). Hence, the lower bound ω * (τ ) is given by

ω * (τ ) = max 1 τ γ + 1 , 1 δ/(2L 2 K τ ) + 1 =        1 τ γ + 1 if 0 < τ < δ/(2γL 2 K ) 1 δ/(2L 2 K τ ) + 1 if τ ≥ δ/(2γL 2 K ) (77)
which is minimal for τ * = δ/(2γL 2 K ) and leads to the optimal rate

ω * = ω * (τ * ) = 1 (γ δ)/(2L 2 K ) + 1 = 1 1/(2κ F ) + 1 . ( 78
)
This rate is reached for

τ = τ * = δ 2γL 2 K and σ = 1 L 2 K τ * = 2γ δL 2 K . ( 79
)
One can check that the same choice for τ and σ yield the minimal value for the solution error rate ω, which is

ω * = 1 2 (γ δ)/(2L 2 K ) + 1 = 1 2/κ F + 1 . ( 80
)
In other terms, in the case where θ = 1, the best choice for the global rate ω and for the solution error rate ω coincide.

3.2.2

The best convergence rate (θ < 1)

In this section, we want to derive the best convergence rate given the constraints in (1).

Theorem 2

The best convergence rate in Theorem 1 is obtained when choosing

τ = δ 2 L 2 K 1 + 1 + 4 L 2 K γ δ and σ = γ 2 L 2 K 1 + 1 + 4 L 2 K γ δ (81) and, if κ F = L 2 K /(γ δ), θ = 1 + (4 L 2 K )/(γ δ) -1 1 + (4 L 2 K )/(γ δ) + 1 = √ 1 + 4 κ F -1 √ 1 + 4 κ F + 1 < 1 (82)
which satisfy τ γ = σ δ. The resulting rate is ω * = θ.

Proof Fix τ > 0 and find out which conditions σ must satisfy to ensure the existence of θ satisfying (25). There exists θ satisfying (25) if

1 τ γ + 1 ≤ 1 L 2 K τ σ and 1 σ δ + 1 ≤ 1 L 2 K τ σ . ( 83
)
which also reads

σ ≤ 1 L 2 K τ + γ L 2 K and (L 2 K τ -δ) σ ≤ 1. ( 84
)
Let us determine conditions on σ so that these inequalities hold. If L 2 K τ -δ ≤ 0, i.e. τ ≤ δ/L 2 K , the second inequality is always true. Hence, let us study the case L 2 K τδ > 0, i.e. τ > δ/L 2 K . It implies that σ must satisfy both majorations

σ ≤ 1 L 2 K τ + γ L 2 K and σ ≤ 1 L 2 K τ - δ . (85)
Let us compare these two bounds. Since

1 L 2 K τ + γ L 2 K - 1 L 2 K τ - δ = γL 2 K τ 2 -γ δτ - δ L 2 K τ (L 2 K τ -δ) (86) with L 2 K τ (L 2 K τ -δ) positive, 1/(L 2 K τ ) + γ/L 2 K is greater than 1/(L 2 K τ -δ) iff γL 2 K τ 2 - γ δτ -δ ≥ 0, i.e. iff τ ≥ τ * , given by τ * = δ 2 L 2 K 1 + 1 + 4 L 2 K γ δ > δ L 2 K . (87)
Therefore, for any δ/L 2 K < τ ≤ τ * , (85

) becomes σ ≤ 1/(L 2 K τ ) + γ/L 2 K . If τ > τ * , (85) reads σ ≤ 1/(L 2 K τ -δ).
As a conclusion, we have the following upper bounds for σ:

σ ≤        1 L 2 K τ + γ L 2 K if 0 < τ ≤ τ * 1 L 2 K τ - δ if τ * < τ. (88)
Now, fix σ satisfying (88) and let us minimize (θ + 1)/(σ δ + 2) subject to (25). The map θ → (θ + 1)/(σ δ + 2) is minimal when θ is minimal. Hence, let us determine the lower bound of θ, which is given by

max 1 τ γ + 1 , 1 σ δ + 1 . (89) First, remark that, if τ > δ/L 2 K , then δ L 2 K τ - δ ≤ τ γ ⇐⇒ γL 2 K τ 2 -γ δτ -δ ≥ 0 ⇐⇒ τ ≥ τ * . (90)
Suppose that τ > τ * , which implies that τ > δ/L 2 K . Since σ is bounded from above by 1/(L 2 K τ -δ), we deduce that σ δ ≤ τ γ, which yields

max 1 τ γ + 1 , 1 σ δ + 1 = 1 σ δ + 1 if 0 < σ ≤ 1 L 2 K τ - δ . (91)
Now, let us consider the case τ ≤ τ * . Since

1 L 2 K τ + γ L 2 K ≥ τ γ δ ⇐⇒ γL 2 K τ 2 -γ δτ -δ ≤ 0 ⇐⇒ τ ≤ τ * (92)
we deduce that

max 1 τ γ + 1 , 1 σ δ + 1 =        1 σ δ + 1 if 0 < σ ≤ τ γ δ 1 τ γ + 1 if τ γ δ < σ ≤ 1 L 2 K τ + γ L 2 K . (93)
Let us minimize (θ + 1)/(σ δ + 2) w.r.t. to σ, when θ is equal to its lower bound θ * (σ), given by (91) and (93). This leads to minimize the following quantity w.r.t. σ:

θ * (σ) + 1 σ δ + 2 =        1 σ δ + 1 if τ > τ * or τ ≤ τ * and 0 < σ ≤ τ γ δ 1 τ γ + 1 τ γ + 2 σ δ + 2 if τ ≤ τ * and τ γ δ < σ ≤ 1 L 2 K τ + γ L 2 K . (94)
In both cases, the minimum is reached when σ is maximal, equal to its upper bound given by (88). Hence, min σ subject to (88) θ subject to (25)

θ + 2 σ + 1 =          1 - δ L 2 K τ if τ > τ * min 1 τ γ + 1 , 1 τ γ + 1 τ γ + 2 δ/(L 2 K τ ) + δγ/L 2 K + 2 if τ ≤ τ * .
(95) Compare it to 1/(τ γ + 1), and deduce the lower bound ω * (τ ):

ω * (τ ) = max      1 τ γ + 1 , min σ subject to (88) θ subject to (25) θ + 2 σ + 1      . ( 96
)
Thanks to (90), it follows that

ω * (τ ) =        1 - δ L 2 K τ if τ > τ * 1 τ γ + 1 if τ ≤ τ * . (97)
In the second case, σ δ is supposed to be greater than τ γ, so (θ * + 1)/(σ δ + 2) is always smaller than 1/(τ γ + 1). Therefore, the best rate is bounded from below by 1/(τ γ + 1). Eventually, we get the following best rate:

ω * (τ ) =        1 - δ L 2 K τ if τ > τ * 1 τ γ + 1 if τ ≤ τ * (98)
which is minimal for τ = τ * . This eventually leads to the best rate

ω * = 1 - δ L 2 K τ * = 1 τ * γ + 1 = 1 + (4 L 2 K )/(γ δ) -1 1 + (4 L 2 K )/(γ δ) + 1 = √ 1 + 4κ F -1 √ 1 + 4κ F + 1 ( 99
)
obtained when τ = τ * and σ = τ * γ/ δ. This choice leads to the following value for the solution error rate ω:

ω = 1 2τ * γ + 1 = 1 + (4 L 2 K )/(γ δ) -1 1 + (4 L 2 K )/(γ δ) + 3 = √ 1 + 4κ F -1 √ 1 + 4κ F + 3 . ( 100
)
Once again, the same computations prove that the best solution error rate ω is reached when

τ = δ L 2 K 1 + 1 + L 2 K γ δ and σ = γ L 2 K 1 + 1 + L 2 K γ δ ( 101
)
and leads to

ω * = θ = 1 + L 2 K /(γ δ) -1 1 + L 2 K /(γ δ) + 1 = √ 1 + κ F -1 √ 1 + κ F + 1 < ω * . ( 102
)

Overrelaxation on the dual variable

Thanks to the symetry of Problem ( 13), similar results still hold if the relaxation is done on the dual variable y instead of the primal variable ξ, namely if the updates are replaced by

         ξ n+1 = prox τ G (ξ n -τ K * ȳn ) y n+1 = prox σH * (y n + σKξ n+1 ) ȳn+1 = y n+1 + θ (y n+1 -y n ). ( 103
)
As seen in [START_REF] He | On the convergence of primal-dual hybrid gradient algorithm[END_REF], such an overrelaxation will be useful for the analysis of the ADMM. It is equivalent to inverting the role of the dual and the primal variables. Indeed, Problem ( 13) can be rewritten

min y∈Y sup ξ∈X H * (y) -K * y, ξ -G(ξ) (104)
which shares the same regularity assumptions as Problem [START_REF] Nesterov | A method of solving a convex programming problem with convergence rate o(1/k 2 )[END_REF]. Hence, applying Theorem 1 yields the following result:

Theorem 3 Assume problem (13) has a solution, which is a saddle-point of L, denoted by (ξ * , y * ). Choose τ > 0, σ > 0 and 0 < θ ≤ 1 such that

max 1 τ γ + 1 , 1 σ δ + 1 ≤ θ ≤ 1 L 2 K τ σ . ( 105
)
Then, for any ω such that

max θ + 1 τ γ + 2 , 1 σ δ + 1 ≤ ω ≤ θ (106)
we have the following majoration for any N ∈ N and any (ξ, y) ∈ Ξ × Y :

(1 -ωL 2 K τ σ) 1 2τ ξ N -ξ 2 + 1 2σ y N -y 2 + N n=1 ω n ω n-1 L(ξ n ; y) -L(ξ; y n ) ≤ ω N 2τ ξ 0 -ξ 2 + ω N 2σ y 0 -y 2 . ( 107
)
Now, define

T N := N n=1 1 ω n-1 = 1 -ω N ω N -1 (1 -ω) ( 108
)
and let

Ξ N := 1 T N N n=1 1 ω n-1 ξ n and Y N := 1 T N N n=1 1 ω n-1 y n . ( 109
)
Then we have the following bound for any (ξ, y) ∈ Ξ × Y :

1 -ω ω(1 -ω N ) (1 -ωL 2 K τ σ) 1 2τ ξ -ξ N 2 + 1 -ω ω(1 -ω N ) 1 2σ y -y N 2 + L(Ξ N ; y) -L(ξ; Y N ) ≤ 1 T N 1 2τ ξ -ξ 0 2 + 1 T N 1 2σ y -y 0 2 . ( 110
)
Note that the conditions on the parameters now slightly differ from the previous case. A variant can be found in [START_REF] Chambolle | An introduction to continuous optimization for imaging[END_REF]Appendix C2].

As in the previous case where the overrelaxation is done over the primal variable, we can prove the following result for the linear convergence of the solution errors:

Corollary 3 Assume problem (13) has a solution, which is a saddle-point of L, denoted by (ξ * , y * ). Let (ξ n , y n ) n be generated by Algorithm (24). Suppose there exist τ , σ, θ and ω satisfying both conditions

max 1 2τ γ + 1 , 1 2σ δ + 1 ≤ θ ≤ 1 L 2 K τ σ . ( 111
)
Then, for any ω such that

max θ + 1 2τ γ + 1 , 1 2σ δ + 2 ≤ ω ≤ θ. ( 112
)
Then, for any N ∈ N, we have

y * -y N 2 ≤ ωN y * -y 0 2 + τ σ ξ * -ξ 0 2 . ( 113
)
Moreover, if ωL 2 K τ σ = 1, then we also have

ξ * -ξ N 2 ≤ ωN 1 -ωL 2 K τ σ σ τ y * -y 0 2 + ξ * -ξ 0 2 . ( 114
)
Similar computations as in the previous section show that the best rate ω * is achieved when choosing the following parameters:

τ = δ 2 L 2 K 1 + 1 + 4 L 2 K γ δ and σ = γ 2 L 2 K 1 + 1 + 4 L 2 K γ δ (115)
and, with κ

F = L 2 K /(γ δ), θ = 1 + (4 L 2 K )/(γ δ) -1 1 + (4 L 2 K )/(γ δ) + 1 = √ 1 + 4 κ F -1 √ 1 + 4 κ F + 1 < 1 (116)
which leads to ω * = θ.

4 Application : convergence rate for the ADMM in the smooth case

As the ADMM is nothing but a particular instance of the oPDHG method with additional constraints on the parameter choice, its convergence rate is expected to be worse than that of the latter. In subsection 4.1, it will indeed be derived from the computations of the previous section and shown to be greater than that of the oPDHG method. However, as we will show it in the subsection 4.2, it is possible to recover the same convergence rate as in the oPDHG method by introducing a slight modification in the ADMM iterations.

Unaccelerated ADMM

As recalled in Section 2.2, the ADMM iterations [START_REF] Gabay | A dual algorithm for the solution of nonlinear variational problems via finite element approximation[END_REF], which aim at solving the primal problem min

x∈X f (x) := g(x) + h(Ax) (117)
are equivalent to the oPDHG iterations [START_REF] He | On the convergence of primal-dual hybrid gradient algorithm[END_REF] applied to the primal-dual problem

min ξ∈Y sup y∈Y L(ξ; y) := g A (ξ) + ξ, y -h * (y) . (118)
Hence, to study the convergence of the ADMM, one can either apply Theorem 1 or Theorem 3, depending on the overrelaxation choice, with G = g A and H = h, and the identity operator K = Id, of norm L K = 1. We recall that Kx n = ξ n and that g A (Kx) = g(x) for any x ∈ X. The functions G and H are proved to be respectively γ = γ/L 2 Aconvex and δ = δ-convex. In the case considered here, the relaxation is done on the dual variable, of parameter θ = 1. The stepsize for the primal (resp. dual) proximal ascent is τ > 0 (resp. σ = 1/τ ).

Ergodic linear convergence

Apply Theorem 3. Parameters θ and σ being constrained as stated above, Theorem 3 ensures that, provided one can find τ > 0 such that

max 1 τ γ/L 2 A + 1 , 1 δ/τ + 1 ≤ 1 (119)
for any ω such that

max 2 τ γ/L 2 A + 2 , 1 δ/τ + 1 ≤ ω ≤ 1 (120)
we have the following bound for any (x, y) ∈ X × Y :

(1 -ω) 2 ω(1 -ω N ) 1 2τ Ax -Ax N 2 + 1 -ω ω(1 -ω N ) 1 2/τ y -y N 2 + L(AX N ; y) -L(Ax; Y N ) ≤ 1 T N 1 2τ Ax -Ax 0 2 + 1 T N 1 2/τ y -y 0 2 . (121)
We recall that L(Ax; y) = g(x) + Ax, y -h * (y) and f (x) = sup y∈Y L(Ax; y). First note that, if we apply this inequality to (x, y) = (x * , y * ), then its left-hand side is nonnegative. Hence, the linear convergence of the dual iterates comes naturally. However, though the strong convexity ensures the convergence of the primal iterates x N , their convergence speed is not clear. We can solely estimate the convergence of Ax N , which is linear. Thanks to

z N +1 -z * = Ax N +1 -Ax * + τ (y * -y N +1 ) + τ (y N -y * ) (122)
we can nevertheless deduce the linear convergence of the primal iterates z N . This also implies the linear convergence for the feasibility error Ax N -z N . If we now apply (121) to x = x * , using

f (x * ) = L(Ax * ; y * ) = sup y∈Y L(Ax * ; y) ≥ L(Ax * ; Y N ) (123)
we get for any y ∈ Y

(1 -ω) 2 ω(1 -ω N ) 1 2τ Ax * -Ax N 2 + 1 -ω ω(1 -ω N ) 1 2/τ y -y N 2 + L(AX N ; y) -f (x * ) ≤ 1 T N 1 2τ Ax * -Ax 0 2 + 1 T N 1 2/τ y -y 0 2 . ( 124
) Let define y * N ∈ Y as y * N = arg max y∈Y L(AX N ; y) (125)
so that L(AX N ; y * N ) = f (X N ). The left-hand side in (124) is then nonnegative for y = y * N and yields

0 ≤ f (X N ) -f (x * ) ≤ 1 T N 1 2τ Ax * -Ax 0 2 + 1 T N 1 2/τ y * N -y 0 2 . ( 126
)
Hence, if the quantity y * N -y 0 is proved to be bounded, then the ergodic linear convergence of the ADMM in terms of objective error follows. One can check that y * N = ∇h(AX N ) and y * = ∇h(Ax * ) which implies, thanks to the Lipschitz continuity of ∇h, that y * N -y 0 ≤ y * -y * N + y * -y 0 ≤ Ax * -AX N /δ + y * -y 0 . However, Equation (124) applied to y = y * and N = n implies that

Ax * -Ax n 2 ≤ ω(1 -ω n ) (1 -ω) 2 2τ T n 1 2τ Ax * -Ax 0 2 + 1 2/τ y -y 0 2 . (127)
Thus, using the definition of X N and the convexity of the quadratic norm, we get

Ax * -AX N 2 = Ax * -A 1 T N N n=1 1 ω n-1 x n 2 (128) ≤ 1 T N N n=1 1 ω n-1 Ax * -Ax n 2 (129) Ax * -AX N 2 ≤ 2τ N T N ω 1 -ω 1 2τ Ax * -Ax 0 2 + 1 2/τ y -y 0 2 (130)
thanks to the definition of T n (28). Since (N/T N ) N goes to zero, we get the desired result.

Convergence rate

Let us estimate the best convergence rate which can be achieved by the ADMM. Condition (119) is always true. Hence, for any τ > 0, the convergence rate satisfies

max 1 (τ γ)/(2L 2 A ) + 1 , 1 δ/τ + 1 ≤ ω ≤ 1. (131)
The lower bound is equal to 1/((τ γ)/(2L 2 A ) + 1) when τ ≤ (2δL 2 A )/γ and is equal to 1/(δ/τ + 1) otherwise. This leads to the best rate

ω * = 1 (γδ)/(2L 2 A ) + 1 = 1 1/(2κ f ) + 1 reached when τ = 2δL 2 A γ . (132)

Convergence rate

Let us derive the best convergence rate for Algorithm (134). We may use Theorem 3, which ensures that steps τ and τ are constrained by the relations

max 1 τ γ/L 2 A + 1 , 1 δ/τ + 1 ≤ τ τ ≤ 1 (137)
and that the convergence rate is constrained by

max τ /τ + 1 τ γ/L 2 A + 2 , 1 δ/τ + 1 ≤ ω ≤ τ τ . (138)
Hence, it is sufficient to find (τ, τ ) satisfying both (137) and ( 138) which minimize the left-hand member in the latter.

One can also first use the remark made after Corollary 3. If no constraint on θ is made, then the best rate is achieved when

τ = δ 2   1 + 1 + 4 L 2 A γδ   and σ = 1 τ = γ 2 L 2 A   1 + 1 + 4 L 2 A γδ   (139)
and

θ = 1 + 4L 2 A /(γδ) -1 1 + 4L 2 A /(γδ) + 1 . (140)
Let us check that such a choice satisfy θ = τ /τ . First, we have

τ = 2L 2 A /γ 1 + 1 + 4L 2 A /(γδ) = (δ/2)( 1 + 4L 2 A /(γδ) + 1)( 1 + 4L 2 A /(γδ) -1) 1 + 1 + 4L 2 A /(γδ) (141)
which implies that

τ τ = 1 + 4L 2 A /(γδ) -1 1 + 4L 2 A /(γδ) + 1 . ( 142
)
Hence, these parameters can be chosen for the accelerated ADMM, and yields to the best rate. Thus, they are called optimal parameters for the accelerated ADMM. With this parameter choice, we have ω * = θ. Note that the resulting rate is the same as the best one expected when applying the oPDHG on Problem (6). However, unlike in the oPDHG algorithm, this choice implies a loss of control on both x-iterates and z-iterates. Moreover, this choice leads to the following rate ω:

ω = 1 2δ/(τ ) * + 1 = 1 + (4L 2 A )/(γδ) -1 1 + (4L 2 A )/(γδ) + 3 = 1 + κ f -1 1 + κ f + 3 (143)
To minimize the latter rate, we use the previous computations with γ and δ doubled, which leads to the parameter choice

τ = δ 2   1 + L 2 A γδ -1   and τ = δ 2   1 + L 2 A γδ + 1   (144)
and the resulting rate:

ω * = 1 + L 2 A /(γδ) -1 1 + L 2 A /(γδ) + 1 = 1 + κ f -1 1 + κ f + 1 . ( 145
)
Figure 1: theoretical rate comparison. In red/thick the unaccelerated ADMM, in magenta/thick dotted the accelerated ADMM, in blue/dotted the oPDHG and in green strongly convex FISTA with constant step.

Theoretical rate comparison

Figure 1 compares the theoretical rates of the unaccelerated ADMM, the accelerated ADMM, the oPDHG method and strongly convex FISTA with constant step, by plotting for each algorithm the best rate with respect to the condition number κ f . The rate achieved by strongly convex FISTA is the best one, but remains comparable with the accelerated ADMM and the oPDHG method. As expected, the unaccelerated ADMM yield larger rate values.

Relations of other methods

In this section, we make a quick review on other linear convergence results for variant of the ADMM found in the literature. Generally, their differ from our result on the hypotheses made on the problem (both on the regularity of the objective function and on the operators).

Overrelaxed ADMM

In [START_REF] Nishihara | A general analysis of the convergence of admm[END_REF], the authors propose to add an overrelaxation step in the spirit of Nesterov's acceleration. They showed linear convergence rate when h is assumed to be strongly convex and with Lipschitz-continuous gradient, while B is invertible and A is full column rank.

Generalized ADMM

In [START_REF] Deng | On the global and linear convergence of the generalized alternating direction method of multipliers[END_REF], the authors studied the ADMM in a wider framework, by allowing in each partial minimization to add an extra proximal term, which leads to a generalized ADMM. Linear convergence rates are proved for four scenarios in which at least one of the functions g or h is strongly convex and has a Lipschitz gradient, which is not assumed here. The case we treated is considered, but with extra assumptions (in particular, h is supposed to be strongly convex). They provided an explicit convergence rate for only one scenario [7, Corollary 3.6].

Relaxed ADMM

It can be shown that the ADMM iterations are also equivalent to applying the Douglas-Rachford splitting (DRS) to the dual of [START_REF] Davis | Faster convergence rates of relaxed peacemanrachford and admm under regularity assumptions[END_REF]. A relaxed version of the DRS, called Peaceman-Rachford splitting (PRS), can be obtained by introducing a relaxed parameter in the DRS iterations. Applying the PRS on the dual of ( 6) hence leads to a so-called relaxed ADMM [START_REF] Davis | Faster convergence rates of relaxed peacemanrachford and admm under regularity assumptions[END_REF]. In [START_REF] Davis | Faster convergence rates of relaxed peacemanrachford and admm under regularity assumptions[END_REF]Theorem 6.3], the authors proved the linear convergence rate of the relaxed ADMM in various cases (including the one we studied here), which depend on the assumptions made on the operators A and B (which is not supposed to be the negative identity) and / or on the regularity of the functions g and h.

However, the study is theoretical and does not provide explicit optimal rates.

K-block ADMM

In [START_REF] Hong | On the linear convergence of the alternating direction method of multipliers[END_REF], the authors proved a linear convergence rate in the case where one can make assumptions on g and h which are supposed to be decomposable into a strictly convex term and a polyhedral one. This includes for instance the strongly convex case, but do not recover the smooth case studied in this paper. Furthermore, hypothesis on the rank of operators A and B (not necessary the negative identity) are made. Moreover, their proof still holds when the objective function is a sum of K separable convex functions (with an according number of variables).

6 Applications 6.1 A toy example

Problem

Let N be a integer. We consider the following constrained problem:

min x=(xi) i=0,••• ,N -1 ∈R N x0=1 f (x) := M -m 2 K N x 2 2 + m 2 x 2 2 (146)
where the linear operator

K N : R N → R N -1 is defined by (K N x) i = (x i+1 -x i )/2 for any i = 0, • • • , N -2, of norm K N ≤ 1. The condition number of this problem is M/m. Hence, if m is negligible compared to M , then the problem is ill-conditioned. Let h(z) := (M -m) z 2 2 /2 for any z ∈ R N -1 and g(x) := m x 2 2 /2 + χ {1} (x 0 ) for any x = (x i ) i=0,••• ,N -1 ∈ R N . The function g is m-convex and the convex conjugate h * : y → (M -m) -1 y 2 2 /2 is (M -m) -1 -convex.

Solution

The minimizer of problem (146) may be explicitly computed, by introducting the subvector x given by:

∀ i = 0, • • • , N -2, xi = x i+1 . (147)
such that x = (1, x). The constrained problem (146) can thus be rewritten in the unconstrained form

min x=(xi) i=0,••• ,N -2 ∈R N -1 M -m 2 K N -1 x 2 2 + (x 0 -1) 2 4 + m 2 ( x 2 2 + 1) (148)
A = m I N -1 + (M -m) K * N -1 K N -1 + M -m 4 e 0,0 (149)

ADMM

We apply the accelerated ADMM, which yields

                   x n+1 = arg min x=(xi)i∈R N x0=1 m 2 x 2 2 + K N x, y n + 1 2 τ K N x -z n 2 2 z n+1 = arg min z∈R N -1 M -m 2 z 2 2 -z, y n + 1 2 τ K N x n+1 -z 2 2 y n+1 = y n + 1 τ (K N x n+1 -z n+1 ).
The z-update is computed thanks to the Euler equation:

z n+1 = y n + K N x n+1 /τ M -m + 1/τ . (150)
The x-update is computed thanks to the subvectors we introduced above and is equivalent to minimizing

m 2 x 2 2 + x, K * N -1 ŷn + 1 2 τ K N -1 x -ẑn 2 2 + x0 -1 2 -(z n ) 0 2 . (151)
The Euler equation ensures that xn+1 = A -1 n b n with

A n = m I N -1 + 1 τ K * N -1 K N -1 + 1 4 τ e 0,0 (152)
b n = -K * N -1 ŷn + 1 τ K * N -1 ẑn + - (y n ) 0 2 + 1 2τ (z n ) 0 + 1 4τ e 0 . (153)
We eventually have x n+1 = (1, xn+1 ).

Parameters

We tested two sets of parameters:

1. optimal parameter for the unaccelerated ADMM:

τ = τ = 2 m(M -m) (154)
(we assume that L = 1).

2. optimal paramaters for the accelerated ADMM:

τ = 1 2(M -m) 1 + 4(M -m) m + 1 (155) τ = τ - 1 M -m = 1 2(M -m) 1 + 4(M -m) m -1 . (156)
The convergence rates achieved in each case are respectively 1/( 1/(M/m -1)/2 + 1) and ( 4M/m -3 -1)/( 4M/m -3 + 1).

Comparison with oPDHG and strongly convex FISTA

To solve problem (148), we can use the oPDHG iterations, by considering its primal-dual formulation min

x=(xi) i=0,••• ,N -1 ∈R N x0=1 sup z ∈R N -1 m 2 x 2 2 + Kx, z - 1 2(M -m) z 2 2 . (157)
Hence, we are considering the following algorithm:

         z n+1 = prox σh * (z n + σ K N xn ) x n+1 = prox τ g x n -τ K * N z n+1 xn+1 = x n+1 + θ (x n+1 -x n ) (158)
for which the best theoretical convergence rate is achieved when choosing

τ = 1 2(M -m) 1 + 1 + 4(M -m) m (159) σ = m 2 1 + 1 + 4(M -m) m (160) θ = 1 + 4(M -m) m -1 1 + 4(M -m) m + 1 < 1. (161)
The z -iterates are explicitly given by

z n+1 = M -m M -m + σ (z n + σK N xn ) (162) xn+1 = xn /τ -K * N -1 ẑ n+1 1/τ + m and x n+1 = (1, xn+1 ). ( 163
)
Note that, unlike in the ADMM iterations, there is no operator to invert. We can also use the strongly convex FISTA algorithm, which solves problem (146) by an accelerated FBS which can be written (165)

Results

To compare the convergence of each set of parameters, we used two tools:

1. the solution error x n -x * 2 2 ;

2. the objective error f (x n ) -f (x * ).

Figure 3 displays the evolution of both measures, as well as the theoretical convergence decays expected in each case (ω and ω). We chose m = 0.1 and M = 10, so that κ f = 100. We first observe that, as expected, the accelerated ADMM has a better convergence than the unaccelerated ADMM. The empirical rates are better than the theoretical ones, which can be explained by the over-smoothness of the quadratic problem, compared to the assumptions required by the smooth case.

We also observe oscillations for both the oPDHG and strongly convex FISTA. Rippling for FISTA has been already observed for quadratic problems of this kind [START_REF] Brendan | Adaptive restart for accelerated gradient schemes[END_REF]. This phenomena occurs when the overrelaxation parameter θ is chosen too large compared to the eigenvalues of m I N + (M -m)K * N K N . Similar cause may explain the oscillations in the oPDHG, namely using overrelaxation steps can introduce oscillations when the according parameter are unproperly chosen. Hence, we do not expect to observe such oscillations for ADMM-like schemes.

Denoising with TV-Huber

Problem

We now apply the accelerated ADMM to a denoising problem, which is less smooth and more realistic than the toy example. Let g ∈ R 3NxNy be a RGB-color (noisy) image. We

where the gradient linear operator ∇ : R 3NxNy → R 3NxNy × R 3NxNy is defined for any color image v by a pair of color images ∇v = (δ x v, δ y v) T . The finite differences are given at any index (i, j) ∈ [0, N x -1] × [0, N y -1] by

(δ x v) i,j = v i+1,j -v i,j if i < N x -1 0 otherwise (167)
and (δ y v) i,j = v i,j+1 -v i,j if j < N y -1 0 otherwise.

(168)

The TV-Huber regularization term is defined by

h(∇v) = Nx-1 i=0 Ny-1 j=0 h 0 (∇v) i,j (169)
with

h 0 (z) = |z| 2 /2 if |z| ≤ 1 |z| -1/2 if |z| > 1 and h 0 (z) = z if |z| ≤ 1 z/|z| if |z| > 1. ( 170
)
Hence, this term acts like a quadratic regularization when the image variations are small and like a TV regularization when they are larger (see Figure 4). The quantity µ > 0 is a weight parameter. The convex conjugate h * of the regularization function h can be proved to be

where χ [0,1] (t) = 0 if t ∈ [0, 1] and +∞ otherwise. This implies that h * is 1-convex.

Conclusion

In this work, we studied the convergence of the oPDHG scheme in the case where the composite problem has a strongly convex part and a differentiable with a Lipschitz continuous gradient part. Using the equivalence between this algorithm and the ADMM, we provided a new convergence analysis of the latter. This analysis allowed us to introduce an accelerated variant of the ADMM by changing the augmented Lagrangian parameter, which is proved to have same convergence rate as the oPDHG method. Hence, we showed that in the smooth case, the choice of the ADMM parameter(s) can be crucial in terms of convergence rate. Experimental results confirmed this theoretical analysis. In particular, it has been observed that the accelerated ADMM does not introduce oscillations in some cases, unlike the oPDHG algorithm and strongly convex FISTA, which are known to be in practice more efficient than the ADMM-like scheme, since they require no operator inversion.

Figure 2 :

 2 Figure 2: Minimizer of (146).

where e 0

 0 ,0 denote the matrix of size N -1 with null coefficients except the one at index (0, 0) equal to 1. The vector b is given by b := (M -m) e 0 /4, with e 0 the first vector of the canonical basis of R N -1 . Hence, the minimizer of the initial problem (146) is x * = (1, x * ). For N = 15, M = 1000, and m = 1, Figure 2 plots x * .

x

  n+1 = prox τ g xn -τ ∇h(x n ) xn+1 = x n+1 + θ n+1 (x n+1 -x n ). (164)where θ n is given by (21), with τ = 1/(M -m). The x-iterates are explicitly given byxn+1 = xn /τ -(M -m) (K * N K N xn ) 1/τ + m .

Figure 3 :

 3 Figure 3: Empirical convergence for the toy example.

Figure 4 :

 4 Figure 4: We added a white Gaussian noise to an ideal image (left) to get noisy image (middle). The noise is of standard variation 10 (the image values are between 0 and 255). The denoising is made by solving (166) (right). Source : Hepatica nobilis flowers, by Archenzo (detail).

  j | 2 + χ [0,1] (|y i,j |)

Figure 5 :

 5 Figure 5: Empirical convergence for TV-Huber denoising.

We call this parameter the optimal parameter for the ADMM. Using this parameter also yields the following theoretical rate for the dual variable and Ax n , given by Corollary 3:

This value can be easily proved to be the optimal one for ω.

Accelerated ADMM

We propose to relax the choice of step τ in the updates of z and of y in the ADMM. Replacing τ by τ ≤ τ in these two updates leads to the following algorithm:

(134)

Equivalent oPDHG

Following the same computations as in 2.2, we show that iterations in Algorithm (134) are equivalent to those of the following oPDHG algorithm

where the relaxation parameter θ = τ /τ is linked to the ascent steps τ and σ = 1/τ . Once again, Theorem 3 reads for any suitable ω, τ and τ :

which yields a linear convergence in terms of objective error (in an ergodic sense). However, the best convergence rate achieved by the algorithm is expected to be better than that of the unaccelerated ADMM. Indeed, introducing the relaxed step τ add a degree of freedom in the constraints over the value of ω. Hence, it is minimized over a larger set and its minimal value is thus smaller.

Similarly to the unaccelerated case, (136) ensures the linear convergence of the dual iterates. If 1 -ωτ /τ does not cancel, it also implies the linear convergence of the primal iterates (z N ). Otherwise, we lose the control on the convergence of (Ax N ), thus on that of (z N ).

ADMM

Let g := µ • -u 2 2 /2. We apply the accelerated ADMM to problem (166), which leads to the following iterations:

Each minimization is solved thanks to the Euler equation: the v-update reads

whereas the φ-update is given by

with

(174)

Parameters

Before choosing the parameters, we recall the regularity of the problem. Functions h * and g are respectively 1-convex and µ-convex. The gradient operator is bounded, of norm L ≤ 2 √ 2 (this bound being tight when N x or N y go to +∞). Thus, we set L = 2 √ 2. We tested two sets of parameters:

1. optimal parameter for the unaccelerated ADMM: τ = τ = 4/ √ µ;

2. optimal paramters for the accelerated ADMM:

These choices lead to the convergence rates 1/( µ/8 + 1) for the unaccelerated ADMM and ( 1 + 32/µ -1)/( 1 + 32/µ + 1) for the accelerated one.

oPDHG and strongly convex FISTA

The primal-dual formulation of problem (166) is given by min

Hence using the oPDHG algorithm to solve it leads to the following iterations:

which are computed thanks to the Euler equation:

(178) The best choice of parameters for this algorithm is (Theorem 2):

If we apply strongly convex FISTA to this problem, this leads to the following updates:

which leads to the explicit update

The variable relaxation parameter follows the update rule (21) with τ = 1/8.

Results

To measure the convergence of the algorithm, we used the same two tools as in the previous case: the solution error and the objective error. Figure 5(a) displays the evolution of the objective error, while Figure 5(b) shows the decay of the solution error, for the accelerated ADMM and the oPDHG method. In the latter, the theoretical linear rate ω is also plotted for comparison. We chose µ = 10. The solution error decreases as expected for all methods except strongly convex FISTA, for which we did not estimate a finer theoretical rate for the solution error. In practice, it seems that it converges with same rate as the oPDHG. Hence, in terms of solution error convergence, the accelerated ADMM provides the best empirical decay. For the objective error, the accelerated ADMM, the oPDHG method and strongly convex FISTA yield comparable decay rate. However, one should keep in mind that both the unaccelerated ADMM and the accelerated ADMM require an operator inversion, unlike the oPDHG method and strongly convex FISTA. Hence, even if comparable number of iterations are needed to achieve convergence, the ADMMs iterations are more time consuming than the other methods and should be used only when the inversion of the operator can be implemented efficiently.


Patrick Saint-Dizier
email: stdizier@irit.fr

Challenges of Argument Mining: Generating an Argument Synthesis based on the Qualia Structure

Given a controversial issue, argument mining from texts in natural language is extremely challenging: besides linguistic aspects, domain knowledge is often required together with appropriate forms of inferences to identify arguments. A major challenge is then to organize the arguments which have been mined to generate a synthesis that is relevant and usable. We show that the Generative Lexicon (GL) Qualia structure, enhanced in different manners and associated with inferences and language patterns, allows to capture the typical concepts found in arguments and to organize a relevant synthesis.

Introduction to Argument Mining

One of the main goals of argument mining is, given a controversial issue, to identify in a set of texts the arguments for or against that issue. These arguments act as supports or attacks of the issue. Arguments may also attack or support the arguments which support or attack that controversial issue in order to reinforce or cancel out their impact. Arguments are difficult to identify, in particular when they are not adjacent to the controversial issue, possibly not in the same text, because their linguistic, conceptual or referential links to that issue are rarely explicit.

For example, given the controversial issue: Vaccine against Ebola is necessary, the link with statements such as Ebola adjuvant is toxic, Ebola vaccine production is costly, or 7 people died during Ebola vaccine tests is not straightforward without domain knowledge, including finding the polarity of these statements. For example, a knowledge-based analysis of the third statement shows that it is irrelevant or neutral w.r.t. the issue (Saint-Dizier 2016).

Argument mining is an emerging research area which introduces new challenges in natural language processing and generation. Argument mining research applies to written texts, e.g. (Mochales Palau et ali.., 2009), (Kirschner et ali., 2015), for example for opinion analysis, e.g. [START_REF] Villalba | Some Facets of Argument Mining for Opinion Analysis[END_REF], mediation analysis [START_REF] Janier | Towards a Theory of Close Analysis for Dispute Mediation Discourse[END_REF] or transcribed argumentative dialog analysis, e.g. (Budzynska et ali., 2014), (Swanson et ali., 2015). The analysis of the NLP techniques relevant for argument mining from annotated structures is analyzed in e.g. [START_REF] Peldszus | From argument diagrams to argumentation mining in texts: a survey[END_REF]. Annotated corpora are now available, e.g. the AIFDB dialog corpora or [START_REF] Walker | A Corpus for Research on Deliberation and Debate[END_REF]. These corpora are very useful to understand how argumentation is realized in texts, e.g. to identify argumentative discourse units (ADUs), linguistic cues [START_REF] Nguyen | Extracting Argument and Domain Words for Identifying Argument Components in Texts[END_REF], and argumentation strategies, in a concrete way, possibly in association with abstract argumentation schemes, as shown in e.g. [START_REF] Feng | Classifying arguments by scheme[END_REF]. In natural language generation, argument generation started as early as (Zuckerman et ali. 2000). Finally, reasoning aspects related to argumentation analysis are developed in e.g. [START_REF] Fiedler | Argumentation within deductive reasoning[END_REF] and [START_REF] Winterstein | What but-sentences argue for: An argumentative analysis of 'but[END_REF] from a formal semantics perspective. Abstracting over arguments allows to construct summaries and to induce customer preferences or value systems.

In (Saint-Dizier 2016), a corpus analysis identifies the type of knowledge that is required to develop argument mining. It is briefly reported in this paper. Then, the Generative Lexicon (GL) is shown to be an appropriate model, sufficiently expressive, to characterize the types of knowledge, inferences and lexical data that are required to accurately identify arguments related to an issue. The present contribution focuses on the next stage: given a set of arguments for or against an issue that have been mined in various texts, how to generate a synthesis that is consistent, well-structured and usable?

2 Mining Arguments: the need of knowledge

To explore and characterize the forms of knowledge that are required to develop argument mining in texts, we constructed and annotated four corpora based on four independent controversial issues. The texts considered are extracts from various sources, e.g.: newspaper articles and blogs from associations.

Issues deal with (1) Ebola vaccination, (2) women's situation in India, (3) nuclear plants and (4) organic agriculture. The total corpus includes 51 texts, a total of 24500 words for 122 different arguments.

From our manual analysis, the following argument polarities are observed: attacks: 51 occurrences, supports: 32, argumentative concessions: 17, argumentative contrasts: 18 and undetermined: 4.

Our analysis shows that for 95 arguments (78%), some form of knowledge is involved to establish an argumentative relation with an issue. An important result is that the number of concepts involved is not very large: 121 concepts for 95 arguments over 4 domains. These concepts are mainly related to purposes, functions, parts, properties, creation and development of the concepts in the issues. These are relatively well defined and implemented in the Qualia structure of the Generative Lexicon, which is the framework adopted in our modeling.

The Generative Lexicon (GL) [START_REF] Pustejovsky | The Generative Lexicon[END_REF]) is an attempt to structure lexical semantics knowledge in conjunction with domain knowledge. In the GL, the Qualia structure of an entity is a kind of lexical and knowledge repository composed of four fields called roles: -the constitutive role describes the various parts of the entity and its physical properties, it may include subfields such as material, parts, shape, etc.

the formal role describes what distinguishes the entity from other objects, -the telic role describes the entity functions, uses, roles and purposes, -the agentive role describes the origin of the entity, how it was created or produced.

Let us consider the controversial issue (1): The vaccine against Ebola is necessary. The Qualia structure of the head term of (1), vaccine(X), is:

                 CONSTITUTIVE: ACTIVE PRINCIPLE, ADJUVANT , TELIC:    MAIN: PROTECT FROM(X,Y,D), AVOID(X,DISSEMINATION(D)), MEANS: INJECT(Z,X,Y)   , FORMAL: MEDICINE, ARTEFACT , AGENTIVE : DEVELOP(T,X), TEST(T,X), SELL(T,X)                 
The Qualia structure of Ebola is:

     FORMAL: VIRUS, DISEASE , TELIC: INFECT(E1,EBOLA,P) ⇒ GET SICK(E2,P) ⇒ ✸DIE(E3,P) ∧ E1≤E2 ≤E3     
Then, via formula expansion, the formal representation of the controversial issue is:

✷ (protect from(X,Y, (infect(E1,ebola, Y) ⇒ get sick(E2,Y) ⇒ ✸ die(E3,Y))) ∧ avoid(X,dissemination(ebola)).
3 Generation of an argument synthesis related to a controversial issue 3.1 A Network of Qualias to Characterize the Generative Expansion of Arguments

Our observations show that arguments attack or support (1) specific concepts found in the Qualia of the head terms in the controversial issue (called root concepts) or (2) concepts derived from these root concepts, via their Qualia. For example, arguments can attack properties or purposes of the adjuvant or of the protocols used to test the vaccine. Then, a network of Qualias must be defined to develop the argument synthesis. This network is limited to three levels because derived concepts must remain functionally close to the root concepts.

A Qualia Q i describes major features of a concept such as vaccine(X), it can be formally defined as follows:

Q i : [ R X : T i,X j
], where:

-R X denotes the four roles: X ∈ {f ormal, constitutive, agentive, telic} and possibly subroles, -T i,X j is a term which is a formula, a predicate or a constant T j in the role X of Q i .

A network of Qualias is then defined as follows: -nodes are of two types: [terminal concept] (no associated Qualia) or [non terminal concept, associated Qualia], -the root is the semantic representation of the controversial issue and the related Qualias Q i , -Step 1: the first level of the network is composed of the nodes which correspond to the terms T i,X j in the roles of the Qualias Q i The result of this step is the set T of terminal nodes { T i,X j } and non termi-

nal nodes { T i,X j , Q ′ i ′ : [ R X : T ′ i ′ ,X j ′ ]}.
-Step 2: similarly, the terms T ′ i ′ ,X j ′ from the Q ′ i ′ of step 1 introduce new nodes into the network together with their own Qualia when they are non-terminal concepts. They form the set T ′ , derived from T.

-Step 3: the same operation is carried out on T ′ to produce T ′′ . -Final step: production of T ′′′ . The set of concepts involved is:

{T ∪ T ′ ∪ T ′′ ∪ T ′′′ }.
This network of Qualias forms the backbone of the argument mining system. This network develops the argumentative generative expansion of the controversial issue. This network is the organization principle, expressed in terms of relatedness, that guides the generation of a synthesis where the different facets of the Qualias it contains are the structuring principles.

Synthesis Generation Input Data

Arguments which have been mined are automatically tagged with the following attributes: -the argument identifier (an integer), -the identifier of what the argument attacks or supports (issue or another argument), -the text span involved that delimits the argument compound and its kernel, -the polarity of the argument w.r.t. the issue with one of the following values: support, attack, argumentative concession or contrast.

-the concepts involved, to identify the argument: list of the main concepts from the Qualias used in the mining process, -the strength of the argument, based on linguistic marks found in the argument, -the discourse structures in the compound, associated with the argument kernel, as processed by our discourse analysis platform TextCoop.

Argument 11 is tagged as follows: At this stage no metadata is considered such as date of argument or author status. This notation was defined independently of any ongoing task such as ConLL15.

Argument kernels are expressed in various ways: -evaluative expressions: Vaccine development is very costly, adjuvant is toxic, -comparatives: number of sick people much smaller than for Malaria.

facts related to properties of the main concept(s) of the issue: Vaccine is not yet available. There is no risk of dissemination.

facts related to the consequences, functions, purposes, uses or goals of the issue: vaccine prevents bio-terrorism, 3 vaccinated people died.

An indicative evaluation provides an accuracy of about 82% of the mining and tagging processes compared to our manual annotation.

A Multi-facet Argument Synthesis Generation

The network of Qualias together with the attributes 'relationWith', 'Polarity' and 'ConceptsInvolved' are the most crucial elements to generate a structured argument synthesis that corresponds to the domain conceptual organization. Each node of the Qualia network defines a cluster to which mined arguments are associated. Clusters are organized hierarchically by decreasing relatedness to the issue.

Redundant arguments characterized by lexical duplicates are eliminated.

The generation of a synthesis proceeds informally as follows:

(1) The concepts of the network of Qualias are organized hierarchically and by role. Level 0 of the synthesis contains the concepts T i,X j of the set T , since they are the most relevant. They are organized by role: constitutive, agentive and telic (which is the main role for argument mining). Each concept in a role is considered separately. In the telic role, the list starts by the 'Main' category and then the other types are considered, such as 'Means'.

(2) Each of these concepts defines a cluster that contains the mined arguments that have this concept in their 'conceptsInvolved' attribute, with the constraint that the argument concerns the issue (re-lationWith=issue), the other arguments are treated as presented in (6). For example, the concept sell(T,X) includes the mined argument with the value production costs its its attribute 'conceptsInvolved'.

(3) This process goes on with the lower levels of the network of Qualias: the concepts T ′ i ′ ,X j ′ associated with the Qualias Q i ′ are considered and then, the sets T ′′ and T ′′′ defined in 3.1. (4) When an argument involves several concepts, it is included into the concept cluster that is the highest in the network of concepts.

(5) For each concept, related arguments are structured by polarity: first supports and then attacks, for each of polarity, arguments are listed, with an indication of their number of occurrences found while mining to give an estimate of their recurrence. (6) To deal with the generation of a more comprehensive graph of attacks and supports, a further stage of the generation process consists in considering that each argument that has been mined can also be an issue which can be attacked or supported. This is specified in the attribute 'relationWith'. Therefore, the same process as for the controversial issue is applied, while keeping the same network of Qualias. Let us consider our example on vaccination, then: (a) the root concepts (Level 0) in the Qualia hierarchy are those of vaccine and ebola, e.g.: constitutive: active principle, adjuvant; agentive: develop, test, sell; telic: protect-from, dissemination, infect, get-sick, die, inject. (b) Level 1 concepts are those associated with the Qualias of the root concepts given in (a), e.g. those in the Qualias of: adjuvant (e.g. dilute), tests (e.g. efficiency measure, evaluation methods), develop (e.g. production costs, availability, ethics), etc. For example, a synthesis would be composed of the following clusters: Level 0: e.g.: Cluster 1: Adjuvant: attack: adjuvant is toxic (3 occurrences) ... Cluster 2: Dissemination: support: reduces dissemination (5).. Cluster 3: Get-sick: concessive support: limited number of cases and deaths compared to other diseases (2), ... Level 1:, e.g.: Cluster 4: Production costs: attack: high production and development costs (6) ... Cluster 5: Availability: concessive attack: vaccine not yet available (4), etc.

Finally, in order to make the synthesis based on Qualia network structure more clear, each of the concepts is associated with a simple and direct definition, directly generated via language patterns from the Qualia structure network, e.g.: -Side-effect and toxicity are related to the use of a medicine, -Contamination entails disease dissemination.

-Population isolation avoids disease dissemination.

-Production costs are related to the creation and development of any product, -Efficiency must be measured during the test phase. These definitions are defined for each cluster. The result is a hierarchically organized and well articulated set of clusters that account for the various arguments for or against an issue found in various texts, where each level is made clear to the reader. No evaluation of the relevance of this type of clustering technique has been carried out so far. This evaluation should involve the analysis of the adequacy of this clustering technique by real users, its granularity and its adequacy to the problem to investigate. It may also depend on the type of issue and arguments that have been mined. Deeper forms of argument synthesis could be desirable, but these involve complex conceptual planning issues. To the best of our knowledge, such a task has never been undertaken.


Patrick Saint-Dizier

Knowledge-Driven Argument Mining: what we learn from corpus analysis

Keywords: Argument mining, Natural language processing, Knowledge representation

Given a controversial issue, argument mining from texts in natural language is extremely challenging: besides linguistic aspects, domain knowledge is often required together with appropriate forms of inferences to identify arguments. Via the the analysis of various corpora, this contribution explores the types of knowledge that are required to develop an efficient argument mining system.

Aims and Challenges of Argument Mining

One of the main goals of argument mining is, given a controversial issue, to identify, in a set of texts, the arguments for or against that issue. Arguments are difficult to identify, in particular when they are not adjacent to the controversial issue, possibly not in the same text, because their linguistic, conceptual or referential links to that issue are rarely direct and explicit. Arguments are often evaluative natural language statements which become arguments because of the specific relations they have with another evaluative statement.

Except in specific contexts, most statements do not have any specific linguistic mark that would allow to directly identify as arguments. It is difficult to identify whether a statement is a support or an attack of a controversial issue, and what it precisely attacks or supports. Argument mining has to deal with two major problems: [START_REF] Budzynska | A model for processing illocutionary structures and argumentation in debates[END_REF] reference: the argument is thematically related to the issue, and [START_REF] Feng | Classifying arguments by scheme[END_REF] relatedness: what facets of the issue are involved, how and how much.

Argument mining is an emerging research area which introduces new challenges both in natural language processing (NLP) and in argumentation. It requires the combination of linguistic analysis and language processing with artificial intelligence technology. Argument mining research applies to written texts, e.g. (Mochales Palau et ali.., 2009), (Kirschner et ali., 2015), for example for opinion analysis, e.g. [START_REF] Villalba | Some Facets of Argument Mining for Opinion Analysis[END_REF], mediation analysis [START_REF] Janier | Towards a Theory of Close Analysis for Dispute Mediation Discourse[END_REF] or transcribed dialogue analysis, e.g. (Budzynska et ali., 2014), (Swanson et ali., 2015). The analysis of the NLP techniques relevant for argument mining from annotated structures is analyzed in e.g. [START_REF] Peldszus | From argument diagrams to argumentation mining in texts: a survey[END_REF]). Annotated corpora are now available, e.g. the AIFDB dialog corpora or [START_REF] Walker | A Corpus for Research on Deliberation and Debate[END_REF]. These corpora are very useful to understand how argumentation is realized in texts, e.g. to identify argumentative discourse units (ADUs), linguistic cues [START_REF] Nguyen | Extracting Argument and Domain Words for Identifying Argument Components in Texts[END_REF], and argumentation strategies, in a concrete way, possibly in association with abstract argumentation schemes, as shown in e.g. [START_REF] Feng | Classifying arguments by scheme[END_REF]. Finally, reasoning aspects related to argumentation analysis are developed in e.g. [START_REF] Fiedler | Argumentation within deductive reasoning[END_REF] and [START_REF] Winterstein | What but-sentences argue for: An argumentative analysis of 'but[END_REF] from a formal semantics perspective with a study of concessive and contrastive connectors. In opinion analysis, the benefits of argument mining are not only to identify the customers satisfaction level, but also to characterize why customers are happy or unhappy. Abstracting over arguments allows to construct summaries and to define customer preferences or value systems (e.g. low fares are preferred to localization or quality of welcome for some categories of hotel customers).

This paper focuses on the corpus construction and analysis and identifies and categorizes the needs in terms of knowledge to perform efficient argument mining.

Corpus Construction and Analysis

To explore and characterize the forms of knowledge that are required to develop argument mining in texts, we constructed and annotated four corpora based on four independent controversial issues. These corpora are relatively small, they are designed to explore the problem, and to elaborate the main features of a more extended empirical analysis and model, but not to design a comprehensive knowledge-driven argument mining system.

For this first experiment, we considered the four following issues, which involve very different types of arguments, forms of knowledge (concrete or relatively abstract) and language realizations. These issues are: (1) Ebola vaccination is necessary, (2) Women's conditions have improved in India, (3) The development of nuclear plants is necessary, and (4) Organic agriculture is the future.

For each of these issues, the corpus constructed and the different arguments found (eliminating duplicates or closely related arguments) are summarized in Table 1. The text fragments which are investigated are extracts from various sources where these issues are discussed, in particular: newspaper articles and blogs from associations. These are documents accessible to a large public, with no professional consideration. Language is French (glosses are given is paper) or English. For example: issue 1: The Lancet (UK journal), a French journal that develops results from the Howard Hughes Medical Institute, a web site: Ebola vaccines, therapies, and diagnostics Questions and Answers ; issue 2: http://saarthakindia.org/womens situation India.html, http://www.importantindia.com/20816/ women-in-india-role-and-status-of-women-inindia/; issue 3: Pour/Contre le nucleaire (les centrales) web site in French, etc. This corpus shows that the argument diversity per issue is not very large. A preliminary annotation task includes the annotation of all the arguments that have been found. In a second stage, arguments judged by the annotator to be similar or redundant are bound and count for a single utterance. A high overlap rate has been observed: while there are original arguments, authors tend to borrow quite a lot of material from each other, for example in (4) an average repetition rate of 3.8 has been observed. This overlap rate clearly depends on the annotator (personal analysis and knowledge of the issue domain) and is somewhat subjective. In spite of this subjectivity, this rate gives an interesting rough redundancy level. A more detailed analysis of those repetitions would be of much interest from a rhetorical and sociological perspective.

An argument and its context (the discourse structures that modify it) are tagged between XML <argument> tags with attributes. The argument kernel is tagged <main arg>. Attributes informally characterize the knowledge that is required. Tags encode typical features associated with arguments (text span, polarity, strength) and specific features proper to our investigation; these are:

-the text span involved, which ranges from a few words to a short paragraph. Arguments are numbered for referencing needs, -the discourse relations associated with the argument, these are annotated using the tags defined in our TextCoop platform (Saint-Dizier, 2012).

-the polarity of the argument w.r.t. the issue which has one of the following values: support, concession (argumentative concession is a weak support), contrast (a weak attack), and attack. The concession and contrast categories have been introduced to account for cases where the support or the attack are weak. These however need to be defined more precisely (formally and in annotation guidelines). Concessions and contrasts are both discourse structures and criteria to evaluate argument polarity.

-the conceptual relation with the issue: why it is an attack or a support, -the knowledge involved, when appropriate, to identify the argument: list of the main concepts used. These come preferably from a predefined domain ontology, or from the annotator intuitions, if none is available. This list may be quite informal, it nevertheless contributes to identify the nature of the knowledge involved to identify arguments, -the strength of the argument.

A tagged argument for issue (1) is the following: <argument nb= 11, polarity= concession , relationToIssue= limited proofs of efficiency and safety of vaccination, conceptsInvolved= efficiency measure, safety measures, test and evaluation methods, strength= moderate> <concession> Even if the vaccine seems 100% efficient and without any side effects on the tested population, < /concession> <main arg> it is necessary to wait for more conclusive data before making large vaccination campaigns < /main arg> <elaboration> The national authority of Guinea has approved the continuation of the tests on targeted populations.</elaboration> < /argument>.

From our manual analysis, the following argument polarities are observed: attacks: 53 occurrences, supports: 33, argumentative concessions: 21, argumentative contrasts: 19 and undetermined: 4. The corpus shows a tendency to argue against an issue: attacks and contrasts = 55%, supports and concessions = 41%. The need of knowledge to iden-tify the relation between an issue and an argument is summarized in Table 2 These figures show that for about 77% of the arguments, some form of knowledge is involved to establish an argumentative relation between a statement and a controversial issue. An important result is that the number of concepts involved is not very large: 124 concepts for 100 arguments over 4 domains. Even if the notion of concept remains vague, these results are nevertheless interesting to develop large argument mining systems. These considerations are exemplified below.

Analysis of the types of knowledge involved in argument identification

Our analysis below tends to suggest that the Generative Lexicon (Pustejovsky 1986) (GL), with some improvements, is an adequate representation framework to deal with knowledge based argument mining. The main other lexical semantics approaches such as FrameNet or VerbNet mainly concentrate on verb's predicate argument structure and adjuncts: they characterize the roles that these elements (NPs, PPs a,d S) play in the verb and proposition meaning. According to our observations, this are not central features for knowledge-based argument mining. The GL has a relatively simple argument structure feature, which could be enhanfced with FrameNet data, however, w.r.t. our analysis, the features of much interest are the purposes and goals of an object or action, its origin, and its uses. These are those which are evaluated in arguments. These, to the best of our knowledge, are specific features of the GL Qualia structure, in particular the telic and the agentive roles. A main limitation is that the GL has very little resources available.

The GL is an attempt to structure lexical semantics knowledge in conjunction with domain knowledge via a decompositional view of lexical meaning. The Qualia structure of an entity is composed of four fields called roles: -the constitutive role describes the various parts of the entity and its physical properties, it may include subfields such as material, parts and components, -the formal role describes what distinguishes the entity from other objects, i.e. the entity in its environment, in particular the entities which are more generic. It may also be structured into several subroles such as shape, dimensions, position, etc.

-the telic role describes the entity functions, uses, roles and purposes, -the agentive role describes the origin of the entity, how it was created or produced. Let us now develop the analysis of each corpus.

Main concepts in arguments related to issues (1) and (4)

For issues (1) and ( 4), arguments mainly attack or support salient features of the main concepts of the issue and closely related ones by means of various forms of evalu-ations. Samples of arguments found for issue (1) are: Supports: vaccine protection is very good; Ebola is a dangerous disease; high contamination risks; vaccine has limited side-effects, no medical alternative to vaccine, etc. Attacks: limited number of cases and deaths compared to other diseases; limited risks of contamination, ignorance of contamination forms; competent staff and P4 lab difficult to develop; vaccine toxicity and high side-effects, Concessions or Contrasts: some side-effects; high production and development costs;

vaccine not yet available; ethical and freedom problems.

For issue (1), the concept vaccine is the root of the system. The facets of this concept and the closely related ones used in arguments can be organized as follows:

(1) the parts of a vaccine: the adjuvant and the active principle; (2) its super types: a vaccine is a kind of medicine; and (3) the most central aspects of the concept vaccine w.r.t. argument mining, namely its purposes, goals and consequences, and how it is created, tested and sold. For example, the concepts of side-effect and toxicity are consequences of using a medicine; the concept of contamination is related to one of the purposes of a vaccine, namely to avoid disease dissemination; and production costs are related to the creation and development of any product, including medicines and vaccines, etc.

Without knowing that a vaccine protects humans from getting a disease, it is not possible, e.g. to say that prevents high contamination risks is a support for issue [START_REF] Budzynska | A model for processing illocutionary structures and argumentation in debates[END_REF]. Similarly, without the knowledge that the active principle of a vaccine is diluted into an adjuvant that is also injected, it is not possible to say that the adjuvant is toxic is an attack, this statement could be e.g. purely neutral or irrelevant to the issue.

The terms used in this short analysis: purpose, properties, creation and development, etc. are foundational aspects of the structure of a concept, relatively well defined in the GL. Using this knowledge allows to identify arguments that attack or support an issue and how. Positive or negative terms found in statements are not sufficient to determine arguments, as shown and illustrated in (Saint-Dizier 2016).

Main concepts in arguments related to issue (2)

The arguments related to issue (2) mainly involve comparisons with men's living conditions or refer to general principles of human welfare. Some arguments are justified by means of figures while others remain vague, possibly not up-to-date or relative to specific situations: women living and social conditions may indeed evolve over time, and may differ depending on locations. Samples of arguments found for issue (2) are: Supports: increased percentage of literacy among women; women are allowed to enter into new professional fields; at the upper primary level, the enrollment increased from 0.5 million girls to 22.7 million girls.

Attacks: practices of female infanticide, poor health conditions and lack of education still persisting; home is women's real domain; they are suffering the violence afflicted on them by their own family members; malnutrition is still endemic.

No concessions or contrasts have been observed: argument polarities are very clearcut, with a very positive or negative tonality, proper to highly controversial and overheated debates.

The concepts used in arguments related to issue (2) concentrate on facets of humans in the society. The identification of these concepts is crucial to characterize argumentative relations between issue (2) and their polarity. For example, improving literacy means higher education, better jobs and therefore more independence and social recognition, which are typical of living condition improvements.

The concepts used in arguments for issue (2) can be classified into two categories: -those related to the services provided by the society to individuals: education, safety, health, nutrition, human rights, etc.

-those related to the roles or functions humans can play in the society: job and economy development, family development, cultural and social involvement, etc. The first category is close to the formal role of the GL Qualia, while the latter is close to the telic role. These categories act as types which are characterized by more precise predicates in Qualia roles. For example the family category may include: have(X, family), develop(X, equality in family), educate(X, children), feed(X, family), choose(X, husband/wife).

Arguments pros or cons develop evaluations of these concepts for women. In addition, lexical inferences must be developed to establish a complete link between words found in arguments and the main concepts illustrated above. For example, malnutrition is provoked by a 'lack of food' and entails 'health problems'.

Main concepts in arguments related to issue (3)

In the case of issue (3) (nuclear plants are necessary), supports or attacks mainly involve comparisons between various sources of energy. Samples of arguments are: Supports: energy independence; creates high technology jobs; risks are over-estimated; wastes are well-managed and controlled by AIEA; preserves the other natural resources, Attacks: there are alternative solutions with less pollution; alternatives create more jobs than nuclear; there are risks of military uses : more dangerous than claimed; nuclear plants have high maintenance costs, etc. Concessions or Contrasts: nuclear plants use dangerous products, but we know how to manage them; difficult to manage nuclear plants, but we have competent persons, In terms of language realizations, arguments are essentially constructed on the basis of comparatives and facts related to consequences, purposes or uses of nuclear plants. Utterances are quite developed and refer to knowledge about energy, pollution, health, or various forms of dangers, etc.

In terms of knowledge, nuclear plants have relatively complex agentive (construction, maintenance) and telic (roles, purposes) roles which must be decomposed into facets. For this latter facet, subtypes can be defined which develop its main purposes and secondary purposes and consequences, such as the production of nuclear wastes. The same structures must be developed for other sources of energy (coal, sea, wind, etc.) so that comparisons can be evaluated. Most arguments lack precise comparative data, e.g. wastes are all said to be a nuisance, but the degree is not given. These arguments require knowledge to be evaluated against precise data, otherwise they rather play on the pathos. These are called underspecified arguments. Finally, some arguments are fallacious, for example, the 'energetic independence' advocated as a support for nuclear plants is not acceptable since uranium is bought abroad: the use of knowledge contributes to detect them.

Summary: from concepts to knowledge representation for argument mining

The introduction of knowledge in argument mining is a crucial feature which allows to improve the identification of: (1) the potential relatedness of an evaluative statement with a controversial issue, (2) which aspect(s) of the issue it deals with, characterized by a specific facet in a Qualia role, identified by one or more predicates, (3 ) the argument polarity: attack, support, concession, contrast, (4) neutral, irrelevant, underspecified (when knowledge is not comprehensive enough to decide on the polarity of an argument) and fallacious arguments. The fully annotated corpus (French and English) will be shortly made available.

In terms of language realizations, the following three main types of argument realizations are observed:

(1) use of evaluative expressions (52% of cases), in attribute-value form, where the attribute is proper to the concepts of the controversial issue or of closely derived concepts: Vaccine development is very expensive, adjuvant is toxic. Resources which are required are a set of Qualias representing the concepts, the lexical terms which are associated with each element of the Qualia and their quasi-synonyms, (2) use of comparatives applied to related concepts (e.g. electricty produced by nuclear energy compared to coal or wind, 21% of the cases): Qualia of related concepts are needed with lexical realizations, e.g. number of sick people much smaller than for Malaria, nuclear wastes are more dangerous than coal wastes.

(3) evaluation of uses, consequences or purposes of the main concept of the issue (27% of the cases) requires Qualia structures and associated lexical entries and, when relevant, lexical inference and presuppositions associated with those lexical entries. Examples are: vaccine prevents bio-terrorism, women are allowed to enter into new profesional fields.

Knowledge-based argument mining requires relatively complex sources of knowledge, however, an important result is that for a given issue, only a few conecpts (and their Qualias) are needed. We have breifly shown elements of GL Qualia structures seem to be an appropriate knowledge representation framework, with an adequate conceptual typing (e.g. various forms of telicity) which can be combined with lexical data and lexical inference. In addition, this approach allows to: -reason about arguments on the basis of a domain knowledge representation, -develop conceptually relevant forms of argument synthesis or clustering, based on Qualia roles.

An open issue remains the acquisition of the Qualia structure data. Given that relatively few Qualias are involved for a controversial issue, some features can be developed manually. An important investigation direction is the acquisition of additional features, probably based on bootstrapping techniques.

Conclusion

In this short paper, we present a preliminary analysis of the different forms of knowledge which are frequently required to relate arguments with a given controversial issue. Our short corpus analysis shows that the type of information proposed by the Qualia structure of the GL is a useful knowledge source: object parts, action or object properties, uses, functions, creation and development are often the main topics for arguments. Obviously, this analysis must be expanded in various directions before any development of a knowledge-driven argument mining system. A more detailed empirical analysis is necessary, with a larger corpus, several annotators, and annotation guidelines before conluding that e.g. the Qualia structure is the main resource that is needed.

Table 1 .

 1 Corpus typology

	Issue Corpus size	nb. of annotated	overlap rate: average
		(text extracts)	different arguments nb of similar arguments
	(1)	16 texts, 8300 words	50	4.7
	(2)	10 texts, 4800 words	27	4.5
	(3)	7 texts, 5800 words	31	3.3
	(4)	23 texts, 6200 words	22	3.8
	Total 56 texts, 25100 words	130	4.07

Table 2 .

 2 . Evidence for Knowledge

	Issue need of knowledge total number of concepts
		nb of cases (rate)	involved (estimate)
	(1)	44 (88%)	54
	(2)	21 (77%)	24
	(3)	18 (58%)	19
	(4)	17 (77%)	27
	Total	100 (77%)	124

COMMA

Workshop on the Linguistic Dimensions of Argumentation. Corresponding Author: IRIT-CNRS, 118 route de Narbonne, 31062 Toulouse Cedex France stdizier@irit.fr