Guillaume Carlier
email: carlier@ceremade.dauphine.fr

Paul Pegon
email: pegon@ceremade.dauphine.fr

Luca Tamanini
email: luca.tamanini@unibocconi.it

Convergence rate of general entropic optimal transport costs

Keywords: optimal transport, entropic regularization, Schrödinger problem, convex analysis, entropy dimension. 2020 Mathematics Subject Classification. Primary: 49Q22 ; Secondary: 49N15, 94A17, 49K40

We investigate the convergence rate of the optimal entropic cost v ε to the optimal transport cost as the noise parameter ε ↓ 0. We show that for a large class of cost functions c on R d ×R d (for which optimal plans are not necessarily unique or induced by a transport map) and compactly supported and

Upper bounds are obtained by a block approximation strategy and an integral variant of Alexandrov's theorem. Under an infinitesimal twist condition on c, i.e. invertibility of ∇ 2 xy c(x, y), we get the lower bound by establishing a quadratic detachment of the duality gap in d dimensions thanks to Minty's trick.

Introduction

We consider two probability measures µ ± compactly supported in X ± ⊆ R d and a cost function c : X -× X + → R. The Entropic Optimal Transport problem (also called entropy-regularized optimal transport problem, EOT for short) reads as:

v ε := inf ˆX-×X + c(x, y) dγ(x, y) + εEnt(γ | µ -⊗ µ + ) (1.1)
where the infimum is taken among all couplings γ between µ -and µ + , i.e. probability measures having µ -and µ + as marginals. The classical optimal transport (OT) problem corresponds to ε = 0. The penalization term Ent is the Boltzmann-Shannon relative entropy (also called Kullback-Leibler divergence) and ε > 0 can be interpreted as a temperature parameter. Heuristically, this consists in moving µ -onto µ + in the cheapest and (at the same time) most "diffuse" way, since the (unique) minimizer γ ε of (1.1) is forced to be absolutely continuous with respect to µ -⊗ µ + because of the entropy term and so its mass has to be "spread out", in contrast with solutions to the unperturbed transport problem.

In the last decade, this class of problems has witnessed a rapidly increasing interest and is now an extremely active research topic, because it has found numerous ap-plications and proved to be an efficient way to approximate OT problems, especially from a computational viewpoint. Indeed, when it comes to solving EOT by alternating Kullback-Leibler projections on the two marginal constraints, by the algebraic properties of the entropy such iterative projections correspond to the celebrated Sinkhorn's algorithm [START_REF] Sinkhorn | A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices[END_REF], applied in this framework in the pioneering works [START_REF] Cuturi | Sinkhorn Distances: Lightspeed Computation of Optimal Transport[END_REF][START_REF] Benamou | Iterative Bregman Projections for Regularized Transportation Problems[END_REF]. The simplicity and the good convergence guarantees (see [START_REF] Franklin | On the Scaling of Multidimensional Matrices[END_REF][START_REF] Marino | An Optimal Transport Approach for the Schrödinger Bridge Problem and Convergence of Sinkhorn Algorithm[END_REF]) of this method compared to the algorithms used for the Monge-Kantorovich problem, then determined the success of EOT for applications in machine learning, statistics, image processing, language processing and other areas (see the monograph [START_REF] Peyré | Computational Optimal Transport: With Applications to Data Science[END_REF] and references therein).

As it appears clearly from (1.1), EOT is a perturbed transport problem and, as such, it is natural to investigate its behaviour as the parameter ε vanishes. In this direction, several aspects deserve to be studied, such as the convergence of optimal values, potentials and optimal plans, possibly with quantitative rates. Leveraging on a large deviations interpretation and on the notion of (c, ε)-cyclical monotonicity, the two last questions have been addressed very recently in [START_REF] Bernton | Entropic Optimal Transport: Geometry and Large Deviations[END_REF][START_REF] Nutz | Entropic Optimal Transport: Convergence of Potentials[END_REF].

As concerns the convergence of the optimal values (also called entropic costs) denoted by v ε , let us mention earlier contributions. In the pioneering works [Mik04; MT08; Léo12] (which tackled the question from the Schrödinger problem's viewpoint) and [START_REF] Carlier | Convergence of Entropic Schemes for Optimal Transport and Gradient Flows[END_REF], the Γ-convergence of the EOT problem towards the unregularized OT problem was proved in the quadratic case, i.e. for c(x, y) = |x -y| 2 . As a consequence, the optimal value of the quadratic EOT problem converges to the optimal value of the quadratic OT problem, namely the squared Wasserstein distance.

Since then, this convergence result was generalized in two directions: at the level of the accuracy and at the level of the cost function. As for the former, in [Ada+11; [START_REF] Erbar | From Large Deviations to Wasserstein Gradient Flows in Multiple Dimensions[END_REF][START_REF]On the Difference between Entropic Cost and the Optimal Transport Cost[END_REF] the first-order asymptotic expansion for the cost is established, both in a pointwise and Γ-convergence sense. A further improvement has been obtained independently in [START_REF] Conforti | A Formula for the Time Derivative of the Entropic Cost and Applications[END_REF][START_REF] Chizat | Faster Wasserstein Distance Estimation with the Sinkhorn Divergence[END_REF], where also the second-order term in the expansion is determined (under a regularity assumption on the Wasserstein geodesic connecting the two marginals). A second-order expansion in the same spirit has been obtained for semi-discrete OT in [START_REF] Altschuler | Asymptotics for Semidiscrete Entropic Optimal Transport[END_REF]. As regards the second direction (more general costs), the Γ-convergence result actually holds true for a very large class of continuous cost functions, but the first-order expansion is much more difficult to extend. In [START_REF]On the Difference between Entropic Cost and the Optimal Transport Cost[END_REF], this is achieved for costs satisfying strong regularity assumptions (roughly speaking, a uniform ellipticity condition on the Hessian of the Kantorovich potential of the associated OT problem).

The aim of this paper is to continue in the second direction, namely to weaken even further the assumptions on the cost function c. First of all, it is folklore that v ε is a C ∞ function of ε > 0 (and even analytic as we shall see in Theorem 2.1). However, the differentiability of v ε at ε = 0 + is equivalent to the existence of a finite entropy solution for v 0 , which is generally false, apart from the discrete case. Instead, one expects v ε -v 0 to be of the order of ε log(1/ε). We shall prove that it is indeed the case and that the remainder is O(ε) under quite general assumptions, one of which, inspired by [MTW05; MPW12], is the infinitesimal twist condition which requires the cross-derivative ∇ 2 xy c(x, y) to be invertible for every (x, y). It is worth stressing that for costs satisfying this condition, the solutions to the associated OT problem need not be concentrated on a graph and may even fail to be unique, see [MPW12, Example 3.1].

Our main findings may be summarized as:

Theorem 1.1. Let Ω ± ⊆ R d be open convex sets and µ ± be absolutely continuous probability measures compactly supported on Ω ± and with L ∞ densities. Assume that the cost c is C 2 on Ω -× Ω + and infinitesimally twisted. Then

v ε = v 0 + d 2 ε log(1/ε) + O(ε),
v ε being the value of (1.1).

Hence v ε approximates the transport cost v 0 with accuracy d 2 ε log(1/ε) and the next term in the expansion is at most of order ε ; it cannot be better in general, as shown in the cases handled in [START_REF]On the Difference between Entropic Cost and the Optimal Transport Cost[END_REF]. As an application, if we debias the problem, namely if we consider the Sinkhorn divergence (see [START_REF] Ramdas | On Wasserstein Two-Sample Testing and Related Families of Nonparametric Tests[END_REF])

OT ε (µ -, µ + ) := v ε (µ -, µ + ) - 1 2 v ε (µ -, µ -) + v ε (µ + , µ + )
instead of the entropic cost v ε , it immediately follows from our main theorem that the term in ε log(1/ε) disappears and therefore

OT ε (µ -, µ + ) = v 0 (µ -, µ + ) + O(ε).
For the proof of Theorem 1.1 we will show separately that for ε 1,

v ε ≤ v 0 + d 2 ε log(1/ε) + M ε and v ε ≥ v 0 + d 2 ε log(1/ε) -mε, (1.2)
for some constants m, M . For the upper bound, the proof relies on the block approximation introduced in [Car+17] and on an integral variant of Alexandrov's theorem tailored to our purpose (see Lemma 3.6). Let us emphasize that this upper bound only requires C 1,1 regularity and no twist condition. We also treat more general situations where the cost function is only Lipschitz, in which case the constant d/2 has to be replaced by the upper entropy dimension (without the 1/2 factor) of the marginals (see Proposition 3.1), and this is shown to be sharp in Example 3.3.

For the lower bound, from the dual formulation of (1.1) it follows:

v ε ≥ v 0 -ε log ˆRd ×R d e -E(x,y) ε dµ -(x) dµ + (y),
where E(x, y) := c(x, y) -φ(x) -ψ(y) is the duality gap and (φ, ψ) are Kantorovich potentials for the OT problem. By using the so-called Minty's trick as presented in [START_REF] Mccann | Rectifiability of Optimal Transportation Plans[END_REF] (here the infinitesimal twist condition on c is required), we are able to prove that E detaches quadratically from the set {E = 0} and this allows us to estimate the previous integral in the desired way. We also explain in the quadratic case how to derive a quantitative stability result for optimal plans from the same trick.

Related literature

The discrete case with finitely supported marginals falls within the class of finitedimensional linear programming problems. In this framework, the choice of the entropy as regularizing function has a long tradition and a detailed investigation of convergence rates for regularized primal/dual formulations and expansion of the cost was already addressed in the early work [START_REF] Cominetti | Asymptotic Analysis of the Exponential Penalty Trajectory in Linear Programming[END_REF].

In the continuous setting, entropic regularization is a more recent technique [Car+17] and has been initially employed in the quadratic case c(x, y) = |x -y| 2 , where EOT appears as a perturbation of the (squared) Wasserstein distance. For this choice of cost function, EOT is intimately linked (and actually equivalent in the Euclidean setting) to a much older problem, known as Schrödinger problem (SP for short, see the survey [START_REF] Léonard | A Survey of the Schrödinger Problem and Some of Its Connections with Optimal Transport[END_REF]). The latter can be better described as a control problem for Brownian particles, hence a dynamical problem, unlike EOT which is static in nature. This dynamical aspect turns out to be very useful to overcome regularity problems affecting Wasserstein geodesics, as already shown in [START_REF] Gigli | Second order differentiation formula on RCD * (K, N ) spaces[END_REF][START_REF] Gentil | An Entropic Interpolation Proof of the HWI Inequality[END_REF]. The fact that, for c(x, y) = |x-y| 2 , EOT and SP coincide (see [START_REF] Gigli | Benamou-Brenier and duality formulas for the entropic cost on RCD * (K, N ) spaces[END_REF]) explains why the quadratic EOT problem has attracted a lot of attention coming from different research areas: not only the ones mentioned before, where EOT has proved to be a valuable tool, but also (stochastic) control, statistical mechanics and many others.

In the very last years, several generalizations of both EOT and SP have appeared. As concerns the latter, extensions to mean-field and interacting particle systems [Bac+20; CCT21], and to an abstract framework [START_REF] Monsaingeon | The Dynamical Schrödinger Problem in Abstract Metric Spaces[END_REF] are worth mentioning. As regards EOT, regularizing functions other than the entropy (and their impact on algorithms) have been considered for instance in [DG20; LM22]. Moreover, adding entropy penalizations in the spirit of EOT has also been used in the study of multi-marginal OT [Car22; BCN19; MG20], incompressible fluids [Arn+20; BM20] and unbalanced OT [START_REF] Baradat | Regularized Unbalanced Optimal Transport as Entropy Minimization with Respect to Branching Brownian Motion[END_REF], where the entropy term gives rise to a branching unbalanced OT problem.

For an account of latest developments let us finally mention a series of recent works [GNB21; EN21; NW22], where stability with respect to marginals of plans and potentials for EOT is addressed.

Structure of the paper

In Section 2, we recall some main features of the OT and EOT problems and prove the analyticity of v ε (Theorem 2.1). The upper and lower bounds on v ε are established respectively in Section 3 (Proposition 3.1 and Proposition 3.4) and Section 4 (Proposition 4.4).

Regularity of the EOT cost

Let us first collect all notations, definitions and relevant results concerning the optimal transport problem and its entropy-regularized counterpart. As already anticipated in the introduction, given a parameter ε > 0, two measures µ ± ∈ P(R d ) with compact support X ± := S µ ± and a continuous cost function c ∈ C (X -× X + ), the EOT problem is given by

v ε := inf γ∈Π(µ -, µ + ) ˆX-×X + c(x, y) dγ(x, y) + εEnt(γ | µ -⊗ µ + ) , (EOT ε )
where Π(µ -, µ + ) denotes the set of couplings between µ -and µ + and Ent(• | µ -⊗µ + ) the Boltzmann-Shannon relative entropy (or Kullback-Leibler divergence) w.r.t. the product measure µ -⊗ µ + , defined for general probability measures p, q as

Ent(p | q) =      ˆRd ρ log(ρ) dq if p = ρq, +∞ otherwise.
The fact that q is a probability measure ensures that Ent(p | q) ≥ 0. The value of (EOT ε ), denoted by v ε , is called entropic cost.

The dual problem of (EOT ε ) in the sense of convex analysis reads as

sup φ∈C (X -) ψ∈C (X + ) ˆX- φ dµ -+ ˆX+ ψ dµ + -ε ˆX-×X + e φ(x)+ψ(y)-c(x,y) ε dµ -(x) dµ + (y) + ε ,
which is invariant by (φ, ψ) → (φ + λ, ψ -λ) where λ ∈ R. Another way to write the dual problem, which is also invariant by φ → φ + λ and ψ → ψ + λ, reads as

sup φ∈C (X -) ψ∈C (X + ) ˆX- φ dµ -+ ˆX+ ψ dµ + -ε log ˆX-×X + e φ(x)+ψ(y)-c(x,y) ε dµ -(x) dµ + (y) ,
(D ε ) see [START_REF] Léonard | Minimization of Energy Functionals Applied to Some Inverse Problems[END_REF] or [START_REF] Nutz | Introduction to Entropic Optimal Transport[END_REF] for a more recent presentation. From (EOT ε ) and (D ε ) we recover, as ε → 0, the (unregularized) optimal transport problem associated with c and its dual, that we recall for the reader's sake:

v 0 := inf γ∈Π(µ -, µ + ) ˆX-×X + c(x, y) dγ(x, y) (OT) and sup φ∈C (X -) ψ∈C (X + ) ˆX- φ dµ -+ ˆX+ ψ dµ + : φ ⊕ ψ ≤ c , (D)
respectively, where φ ⊕ ψ(x, y) := φ(x) + ψ(y). The set of optimal couplings between µ -and µ + will be denoted by Opt(µ -, µ + ). The value of (OT), denoted by v 0 , is called transport cost. As for (D), it is well known that optimizers, called Kantorovich potentials, exist whenever X ± are compact and they can be chosen c-conjugate (see [San15, Chapter 1]):

φ = inf y∈X + c(•, y) -ψ(y), ψ = inf x∈X - c(x, •) -φ(x).
The link between EOT and OT is very strong, as already discussed in the introduction. For later use, recall that a consequence of the Γ-convergence of (EOT ε ) towards (OT) is that lim

ε↓0 v ε = v 0 .
(2.1)

A proof tailored to our setting can be found in [Car+17, Section 2.3] (although formulated for the quadratic cost, it actually works for any continuous cost as long as µ ± have compact supports).

The fact that (EOT ε ) admits a unique solution γ ε , called optimal entropic plan, is a consequence of the direct method in the calculus of variations and strict convexity of the entropy. The structure of γ ε is then very rigid: indeed, there exist two real-valued Borel functions φ ε , ψ ε such that

γ ε = exp φ ε ⊕ ψ ε -c ε µ -⊗ µ + , (2.2)
which implies in particular that

v ε = ˆX- φ ε dµ -+ ˆX+ ψ ε dµ + (2.3)
and these functions, which have continuous representatives, are a.s. uniquely determined up to additive constants, in the sense that if (2.2) holds for (φ, ψ) and (φ , ψ ), then φ = φ + λ µ --a.e. and ψ = ψ -λ µ + -a.e. for some λ ∈ R. Moreover, γ ε is the unique coupling γ ∈ Π(µ -, µ + ) whose density w.r.t. µ -⊗ µ + can be written as in (2.2). A self-contained proof of all these facts in the case of compactly supported measures µ ± can be found in [GT21, Proposition 2.1]. The reader is refered to the analysis of [START_REF] Marino | An Optimal Transport Approach for the Schrödinger Bridge Problem and Convergence of Sinkhorn Algorithm[END_REF], to the notes of Nutz [START_REF] Nutz | Introduction to Entropic Optimal Transport[END_REF] for a more general framework, and to [BL92; BLN94; Csi75; FG97; RT98] for earlier references. The functions φ ε , ψ ε in (2.2) are called Schrödinger potentials, the terminology being motivated by the fact that they solve the dual problem (D ε ). Furthermore, φ ε , ψ ε are the (unique) solutions to the so-called Schrödinger system

       φ(x) = -ε log ˆX+ e ψ(y)-c(x,y) ε dµ + (y) for µ --a.e. x, ψ(y) = -ε log ˆX- e φ(x)-c(x,y) ε dµ -(x) for µ + -a.e. y,
(2.4) named after E. Schrödinger who introduced it in the seminal papers [Sch31; Sch32] (see also [START_REF] Chetrite | Schrödinger's 1931 Paper "On the Reversal of the Laws of Nature[END_REF] for a recent English translation of the former). Note that (2.4) is a softmin version of the classical c-conjugacy relation for Kantorovich potentials. From (2.4) and the continuity of c, we easily deduce that φ, ψ share a common modulus of continuity with c (see [START_REF] Marino | An Optimal Transport Approach for the Schrödinger Bridge Problem and Convergence of Sinkhorn Algorithm[END_REF] for details). From an OT viewpoint, (2.4) simply means that e (φ⊕ψ-c)/ε µ -⊗ µ + ∈ Π(µ -, µ + ).

We are now ready to state and prove the first main result. Recall that v ε denotes the value of (EOT ε ) and v 0 the one of (OT); the dependence on µ + , µ -∈ P(R d ) is omitted, as they will always be fixed.

Theorem 2.1. Let µ ± ∈ P(R d ) have compact support X ± ⊆ R d and c ∈ C (X -× X + ).
Then the function ε → v ε is continuous, non-decreasing and concave on [0, +∞) ; it is analytic on (0, +∞).

Proof. The convergence of v ε to v 0 as ε ↓ 0 is precisely (2.1). The fact that v is nondecreasing follows from the non-negativity of the entropy; concavity is also obvious since v ε is an infimum of affine functions of ε.

Analyticity of v on (0, +∞) can be deduced from the analytic version of the implicit function theorem, adapting the arguments of [START_REF] Carlier | A Differential Approach to the Multi-Marginal Schrödinger System[END_REF] as follows. Let ε > 0 and, recalling that Schrödinger potentials are unique up to the trivial transformation (φ, ψ) → (φλ, ψ + λ) with λ ∈ R, impose the following normalization condition ˆXφ dµ -= 0.

(2.5) Denote then by (φ ε , ψ ε ) the unique functions satisfying (2.4) and (2.5) and note that by (2.3) and (2.5) the entropic cost writes as

v ε = ˆX+ ψ ε dµ + . (2.6)
As already noticed, φ ε and ψ ε are continuous in X -and X + respectively, whence the validity of both equations in (2.4) in a pointwise sense. This means that, if we define

F (ε, φ, ψ)(x) := e φ(x) ε ˆX+ e -c(x,y)+ψ(y) ε dµ + (y), x ∈ X - G(ε, φ, ψ)(y) := e ψ(y) ε ˆX- e -c(x,y)+φ(x) ε dµ -(x), y ∈ X +
the Schrödinger system (2.4) is equivalent to

F (ε, φ ε , ψ ε )(x) = 1 (∀x ∈ X -), and
G(ε, φ ε , ψ ε )(y) = 1 (∀y ∈ X + ).
Finally, define the spaces

A := {(φ, ψ) ∈ C (X -) × C (X + ) : (2.5) holds}
and

B := (f, g) ∈ C (X -) × C (X + ) : ˆX- f dµ -= ˆX+ g dµ + ,
which are Banach spaces when equipped with the uniform norm, and the map S :

(0, +∞) × C (X -) × C (X + ) → C (X -) × C (X + ) S(ε, φ, ψ) := (F (ε, φ, ψ), G(ε, φ, ψ)).
Let us observe that S is analytic, takes values in B and the pair of normalized Schrödinger potentials (φ ε , ψ ε ) is implicitly defined by

(φ ε , ψ ε ) ∈ A and S(ε, φ ε , ψ ε ) = (1, 1).
We claim that for every ε > 0 and (φ, ψ) ∈ A, the derivative of S w.r.t. (φ, ψ) at (ε, ψ, φ) is an isomorphism between A and B, analyticity of ε → (φ ε , ψ ε ) will then follow from the implicit function theorem in the analytic case. To ease notations assume ε = 1 and let (φ, ψ) ∈ A be fixed. Defining

S = S(1, •, •) = (F (1, •, •), G(1, •, •)), S := (log(F ), log(G)),
and

L := S (φ, ψ) = (L 1 , L 2 ), L := S (φ, ψ) = ( L1 , L2 ), for (h, k) ∈ C (X -) × C (X + ) we then have L1 (h, k)(x) = h(x) + ˆX+ e -c(x,y)+ψ(y) k(y) dµ + (y) ˆX+ e -c(x,y)+ψ(y) dµ + (y) , L 1 (h, k) = F (φ, ψ) L1 (h, k),
and

L2 (h, k)(y) = k(y) + ˆX- e -c(x,y)+φ(x) h(x) dµ -(x) ˆX- e -c(x,y)+φ(x) dµ -(x) , L 2 (h, k) = G(φ, ψ) L2 (h, k).
We can write in a more synthetic way L as

L1 (h, k)(x) = h(x) + ˆX+ k(y) dQ x (y), L2 (h, k)(y) = k(y) + ˆX- h(x) dQ y (x), (2.7)
where Q x and Q y are the disintegration measures of the probability measure dQ(x, y) := e φ(x)+ψ(y)-c(x,y) dµ -(x) dµ + (y) ˆX-×X + e φ(x )+ψ(y )-c(x ,y ) dµ -(x ) dµ + (y )

with respect to its first marginal α and second marginal β, that is:

Q = α ⊗ Q x = Q y ⊗ β (2.8) (in other words given (X, Y ) with law Q, Q x is the conditional law of Y given X = x and Q y is the conditional law of X given Y = y). Assume now that (h, k) ∈ C (X -) × C (X + ) belongs to ker(L) = ker( L), i.e. h(x) + ˆX+ k(y) dQ x (y) = 0, ∀x ∈ X -= S α (2.9) and k(y) + ˆX- h(x) dQ y (x) = 0, ∀y ∈ X + = S β (2.10)
where X -= S α and X + = S β follow from the equivalence of Q with µ -⊗ µ + (in the sense that they have the same negligible sets). Multiplying (2.9) by h(x) and integrating w.r.t. α, multiplying (2.10) by k(y) and integrating w.r.t. β, and summing the two, by (2.8) we get ˆX-×X + (h(x) + k(y)) 2 dQ(x, y) = 0 from which we deduce that h(x) + k(y) = 0 for µ -⊗ µ + -a.e. (x, y), that is h and k are two constants that sum to 0. We thus have ker( L) = ker(L) = {(λ, -λ) : λ ∈ R} and in particular ker(L) ∩ A = {0}, so that L is injective on A. Since c is uniformly continuous on X -× X + , all functions in the image of L are equi-continuous and equi-bounded, and it follows from Ascoli's Theorem that L is a compact perturbation of the identity map on C (X -) × C (X + ). This enables us to invoke the Fredholm alternative theorem to deduce from the fact that ker

( L) is a line that L(C (X -) × C (X + )) = L(A) is a hyperplane of C (X -) × C (X + ). Since L(A) is isomorphic to L(A)
, and L(A) is included in the hyperplane B (because the original non-linear map S takes values in B), we have

L(A) = B.
Hence L is an isomorphism between A and B and, as anticipated, the implicit function theorem for analytic maps (see chapter 4 of [START_REF] Buffoni | Analytic Theory of Global Bifurcation: An Introduction[END_REF]) therefore implies that (φ ε , ψ ε ) depends analytically on ε > 0. In particular (0, +∞) ε → ψ ε ∈ C (X -) is analytic too, whence the analyticity of v on (0, +∞) thanks to (2.6).

Remark 2.2. The entropic cost ε → v ε being analytic on (0, +∞), it can be extended in an analytic fashion to some complex values of ε. Note that the proof above shows that the entropic cost is also an analytic function of the transport cost c. Remark 2.3. Even if Theorem 2.1 is stated in the Euclidean setting, it is worth stressing that it is in fact true in a much more general framework. Indeed, it is not difficult to see that the previous proof works verbatim over compact metric spaces and an even higher level of generality is possible. More precisely, not even a topological structure is needed. It is indeed sufficient that c ∈ L ∞ (µ -⊗ µ + ) with µ -, µ + probability measures on arbitrary measurable spaces, as it is the case in [START_REF] Carlier | A Differential Approach to the Multi-Marginal Schrödinger System[END_REF]. However, with no topological structure the proof of the analyticity of ε → v ε would be more involved.

Knowing that all order derivatives of ε → v ε exist on (0, +∞), it is natural to look for an explicit expression for them. The case of the first derivative is particularly easy to handle, as shown below.

Corollary 2.4. Under the same assumptions of Theorem 2.1, it holds

v ε = Ent(γ ε | µ -⊗ µ + ), ∀ε > 0.
(2.11)

Besides, if there exists γ 0 ∈ Opt(µ -⊗ µ + ) with Ent(γ 0 | µ -⊗ µ + ) < +∞, then ε → v ε belongs to C 1 ([0, +∞))
with right derivative at ε = 0 given by

v ε | ε=0 = inf γ∈Opt(µ -,µ + ) Ent(γ | µ -⊗ µ + ), (2.12)
in other words:

v ε -v 0 = ε inf γ∈Opt(µ -,µ + ) Ent(γ | µ -⊗ µ + ) + o(ε). (2.13)
Moreover, in that case, γ ε converges narrowly to the unique coupling γ * of minimal entropy in Opt(µ -, µ + ), namely

γ * = arg min γ∈Opt(µ -,µ + ) Ent(γ | µ -⊗ µ + ).
Proof. Knowing that ε → v ε is analytic (C1 would be enough), (2.11) is a consequence of the envelope theorem and of the uniqueness of the minimizer of (EOT ε ).

As concerns the second part of the statement, define

C ε (γ) := ˆX-×X + c dγ + εEnt(γ | µ -⊗ µ + ) and observe that v ε -v 0 = C ε (γ ε ) -C 0 (γ) ≤ C ε (γ) -C 0 (γ) = εEnt(γ | µ -⊗ µ + ) for any γ ∈ Opt(µ -, µ + ), hence lim sup ε↓0 v ε -v 0 ε ≤ inf γ∈Opt(µ -,µ + ) Ent(γ | µ -⊗ µ + ), (2.14)
the right-hand side being finite thanks to the existence of γ 0 as in the statement. For the liminf inequality, recall that (EOT ε ) Γ-converges to (OT) as ε → 0, so that up to subsequences γ ε converges narrowly to γ * ∈ Opt(µ -, µ + ). Combining this information with

v ε -v 0 ≥ C ε (γ ε ) -C 0 (γ ε ) = εEnt(γ ε | µ -⊗ µ + )
v ε -v 0 ε ≥ Ent(γ * | µ -⊗ µ + ) ≥ inf γ∈Opt(µ -,µ + ) Ent(γ | µ -⊗ µ + ),
and this inequality 1 together with (2.14) implies the right differentiability of v ε at ε = 0 as well as (2.12). Note that the argument above also proves the existence of a γ * ∈ Opt(µ -, µ + ) of minimal entropy towards which γ ε converges narrowly (up to subsequences) as well as the lower semicontinuity of v ε at ε = 0. The uniqueness of such γ * comes from the convexity of Opt(µ -, µ + ) and the strict convexity of the entropy, hence the convergence of the whole sequence. The upper semicontinuity of v ε at ε = 0 is instead a consequence of concavity, so that in conclusion v ε is continuous up to ε = 0, namely

v ε ∈ C 1 ([0, +∞)).
Let us stress that while (2.11) is an immediate consequence of Theorem 2.1, the proof of (2.12) (inspired by [CT21; MTV20]) requires the existence of an optimal coupling with finite entropy w.r.t. µ -⊗ µ + and the reader may wonder whether this condition is reasonable or not. If µ -and µ + are finitely-supported measures, the condition is trivially satisfied; hence identities (2.12) and (2.13) may be of some interest in this case (in this direction, recall the pioneering work [START_REF] Cominetti | Asymptotic Analysis of the Exponential Penalty Trajectory in Linear Programming[END_REF]).

However, as soon as µ -and µ + have densities, the aforementioned condition is not satisfied in general. In particular, it cannot hold whenever optimal plans are concentrated on d-rectifiable sets. To obtain a non-trivial asymptotic expansion of the entropic cost around ε = 0 in more general situations, a more accurate study of v ε -v 0 is thus required, and this will be carried out in Sections 3 and 4.

Upper bound

Our goal in this section is to establish upper bounds on v ε -v 0 up to order O(ε) as ε → 0. We start with a general upper bound holding for C 0,1 (i.e. Lipschitz) costs, then we prove a finer upper bound for C 1,1 costs. The leading order terms, which are proportional to ε log(1/ε), will be shown to be sharp in this section and in Section 4.

Upper bound for C 0,1 costs

The upper bound we are going to establish will depend on the dimension of µ -and µ + . The natural notion of dimension which arises in our context is the entropy dimension, also called information dimension or Rényi dimension, since it was originally introduced by Rényi in [START_REF] Rényi | On the Dimension and Entropy of Probability Distributions[END_REF]. The definition that we use corresponds to the one given in [START_REF] Young | Dimension, Entropy and Lyapunov Exponents[END_REF]: if µ is a probability measure over R d , we set for every δ > 0,

H δ (µ) = inf    n∈N µ(A n ) log(1/µ(A n )) : ∀n, diam(A n ) ≤ δ, and R d = n∈N A n    ,
where the infimum is taken over countable coverings (A n ) n∈N of R d by Borel subsets, and we define the lower and upper entropy dimension of µ respectively by: dim E (µ) := lim inf

δ→0 + H δ (µ) log(1/δ) , dim E (µ) := lim sup δ→0 + H δ (µ) log(1/δ)
.

When µ has compact support, notice that its upper entropy dimension is always smaller than the upper box dimension of the support of µ, that is:

dim E (µ) ≤ dim B (S µ ) := lim sup δ→0 + log(N δ (S µ )) log(1/δ) ,
where for every A ⊆ R d , N δ (A) denotes the box-counting number of A at scale δ, i.e. the minimal number of sets of diameter δ > 0 which cover A.

Indeed if (A 1 , . . . , A N δ (Sµ)
) is such a covering, by concavity of t → t log(1/t), we have

1≤n≤N δ (Sµ) µ(A n ) log(1/µ(A n )) ≤ log N δ (S µ ). (3.1)
The reader interested in the different notions of dimension of sets and measures may consult [START_REF] Falconer | Techniques in Fractal Geometry[END_REF].

Proposition 3.1. If µ ± ∈ P(R d ) and c ∈ C 0,1 (S µ -× S µ + ), then for every ε > 0,

v ε ≤ v 0 + ε(H ε (µ -) ∧ H ε (µ + )) + [c] C 0,1 (S µ -×S µ + ) ε. (3.2)
In particular, setting d ± = dim E (µ ± ),

v ε ≤ v 0 + (d + ∧ d -)ε log(1/ε) + o(ε log(1/ε)) as ε → 0, (3.3)
and if µ ± are concentrated on compact submanifolds of dimension d ± ,

v ε ≤ v 0 + (d + ∧ d -)ε log(1/ε) + O(ε). (3.4)
The proof is based on a generalization of the block approximation defined in [Car+17, Definition 2.9].

Proof. Let γ 0 ∈ Opt(µ -, µ + ). First of all, let us extend the cost to a function c ∈

C 0,1 (R d × R d ) with same Lipschitz constant L := [c] C 0,1 (R d ×R d ) = [c] C 0,1 (S µ -×S µ + ) . We consider a covering R d = n∈N A n of Borel sets such that diam(A n ) ≤ δ for every n ∈ N.
We set for every n ∈ N,

µ ± n :=      µ ± A n µ ± (A n ) if µ ± (A n ) > 0, 0 otherwise,
then for every pair i, j ∈ N,

(γ 0 ) i,j := γ 0 (A i × A j )µ - i ⊗ µ + j ,
and finally,

γ δ := i,j∈N (γ 0 ) i,j .
By definition, γ δ µ -⊗ µ + and we may check that its marginals are µ ± , for instance:

(π 1 ) # γ δ = i,j∈N (π 1 ) # (γ 0 (A i × A j )µ - i ⊗ µ + j ) = i,j∈N γ 0 (A i × A j )µ - i = i∈N µ -(A i )µ - i = µ -.
Besides, for µ -⊗ µ + -almost every (x, y)

∈ A i × A j , dγ δ dµ -⊗ µ + (x, y) = γ 0 (A i × A j ) µ -(A i )µ + (A j ) if µ -(A i )µ + (A j ) > 0,
and it is 0 otherwise. Let us compute its entropy, summing only over indices i, j such that µ -(A i ) > 0 and µ + (A j ) > 0.

Ent(γ δ | µ -⊗ µ + ) = i,j∈N ˆAi ×A j log γ 0 (A i × A j ) µ -(A i )µ + (A j ) dγ δ = i,j∈N γ 0 (A i × A j ) log γ 0 (A i × A j ) µ -(A i )µ + (A j ) = i,j∈N γ 0 (A i × A j ) log γ 0 (A i × A j ) µ -(A i ) + j∈N µ + (A j ) log(1/µ + (A j )) ≤ j∈N µ + (A j ) log(1/µ + (A j )),
the last inequality coming from the inequality γ 0 (A i × A j ) ≤ µ -(A i ). Taking arbitrary coverings (A n ) n∈N of diameter smaller than δ, we get by definition of H δ ,

Ent(γ δ | µ -⊗ µ + ) ≤ H δ (µ + ).
Notice that W ∞ (γ δ , γ 0 ) ≤ δ, where W p denotes the p-Wasserstein distance2 between compactly supported probability measures for p ∈ [1, ∞]. As a consequence, taking γ δ as competitor in (EOT ε ), since W 1 ≤ W ∞ we obtain

v ε ≤ ˆRd ×R d c dγ δ + εH δ (µ + ) = v 0 + ˆRd ×R d c d(γ δ -γ 0 ) + εH δ (µ + ) ≤ v 0 + LW 1 (γ δ , γ 0 ) + εH δ (µ + ) ≤ v 0 + Lδ + εH δ (µ + ).
(3.5)

Taking δ = ε and interchanging the roles of µ -and µ + yields (3.2), and (3.3) follows from the definition of the upper entropy dimension. Finally, if µ ± are concentrated on compact d ± -dimensional manifolds M ± , knowing that their box counting number N ε (M ± ) is bounded from above by C/ε d ± for some constant C > 0 and every ε ∈ (0, 1), applying (3.1) to µ ± yields H ε (µ ± ) ≤ d ± log(1/ε) + log C, thus

v ε ≤ v 0 + (d -∧ d + )ε log(1/ε) + (L + log C)ε
and (3.4) is proved.

Remark 3.2. If the cost c is only assumed to be uniformly continuous on S µ -× S µ + , with modulus of continuity ω c : δ → sup x-x ≤δ |c(x) -c(x )|, a straightforward adaptation of the above proof shows that

v ε ≤ v 0 + (d + ∧ d -+ o(1))ε log(1/ω -1 c (ε)), and if µ ± are concentrated on d ± -dimensional submanifolds, v ε ≤ v 0 + (d + ∧ d -)ε log(1/ω -1 c (ε)) + O(ε), where ω -1
c is the generalized inverse defined by ω -1 c (t) := inf{s ≥ 0 : ω c (s) ≥ t}.

The following easy example shows that the leading order term is in general sharp in the class of C 0,1 cost functions.

Example 3.3. Consider µ -= µ + = L [0, 1] and c(x, y) := |x -y| for x, y ∈ [0, 1]. Then

v ε ≥ v 0 + ε log(1/ε).
Indeed, the unique optimizer to (OT) is γ 0 = (Id, Id) # µ -with cost v 0 = 0, and the pair (φ 0 , ψ 0 ) = (0, 0) is a solution to the dual problem (D). We use (φ 0 , ψ 0 ) as a competitor in (D ε ) to get

v ε ≥ -ε log ˆ[0,1] 2 e -|y-x| ε dx dy .
We have

ˆ[0,1] 2 e -|y-x| ε dx dy = 2 ˆ1 0 ˆy 0 e -t ε dt dy = 2 ˆ1 0 ε(1 -e -y ε ) dy = 2ε(1 -ε(1 -e -1 ε )) ≤ 2ε,
thus for every ε > 0,

v ε ≥ -ε log 2ε = v 0 + ε log(1/ε) + O(ε),
and together with (3.4), since

d ± = 1, we get v ε -v 0 = ε log(1/ε) + O(ε).

Upper bound for C 1,1 costs and L ∞ marginals

Building upon the same block approximation used to establish Proposition 3.1, we provide a finer upper bound when the cost is of class C 1,1 and µ ± have L ∞ densities.

Proposition 3.4. Let c ∈ C 1,1 loc (Ω -× Ω + )
where Ω ± ⊆ R d are open convex sets and µ ± ∈ L ∞ (Ω ± ) be two probability measures compactly supported in Ω ± . Then there exists a constant M ≥ 0 such that for every ε ∈ (0, 1),

v ε ≤ v 0 + d 2 ε log(1/ε) + M ε. (3.6)
Remark 3.5. Notice that Proposition 3.1 would only show that v ε ≤ v 0 + dε log(1/ε) + O(ε). The term dε log(1/ε) term is generally sharp as shown in Example 3.3, when c is only Lipschitz, but Proposition 3.4 shows that d may actually be replaced by d/2 when c is C 1,1 . This is in turn sharp in the class of C 1,1 costs, as already exhibited in the quadratic case in [START_REF] Adams | From a Large-Deviations Principle to the Wasserstein Gradient Flow: A New Micro-Macro Passage[END_REF] or in the setting of [START_REF]On the Difference between Entropic Cost and the Optimal Transport Cost[END_REF], but it is also a consequence of our lower bound stated in Proposition 4.4 in the case of infinitesimally twisted cost functions.

To prove Proposition 3.4, we will need a quadratic bound on the average error between a λ-convex function f and its first-order Taylor expansion. We recall that a function

f : Ω → R defined on a convex set Ω ⊆ R d is λ-convex, for λ ∈ R, if x → f (x) -λ |x| 2 2 is convex, and f is λ-concave if -f is (-λ)-convex. If Ω is open and f is λ-convex,
then it is differentiable almost everywhere on Ω by Rademacher's Theorem, and its distributional Hessian D 2 f is a S d (R)-valued Radon measure over Ω, which may be written (see [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF]§1.3

]) as D 2 f = σ f |D 2 f | where |D 2 f | is
|f (y)-(f (x)+∇f (x)•(y-x))| dx ≤ Cr 2 H d-1 (∂Ω)([f ] C 0,1 (Ω) +|λ| diam(Ω)). (3.7)
The proof is based on that of Alexandrov's Theorem, asserting the existence of a second-order Taylor expansion at almost every point, which is given in [EG15, §6.4].

Proof.

Step 1. Let g be a function which is convex on B r (x) and assume that x is a differentiability point of g and a Lebesgue point of both g and ∇g. Let us show that

sup y∈B r/2 (x) |g(y) -(g(x) + ∇g(x) • (y -x))| ≤ Cr 2 |D 2 g|(B r (x)) L d (B r (x))) (3.8) for a constant C = C(d).
For ε ∈ (0, r), we set r ε = r -ε and we define g ε := g η ε on B rε (x), where η ε is a standard mollifier supported on B ε . Since g ε ∈ C 2 (B rε (x)), by the classical Taylor integral formula, for every h ∈ B rε ,

g ε (x + h) = g ε (x) + ∇g ε (x) • h + ˆ1 0 (1 -t)D 2 g ε (x + th) • h ⊗ h dt,
and integrating w.r.t. h over B rε , we get the bound:

ˆBrε |g ε (x + h) -(g ε (x) + ∇g ε (x) • h)| dh ≤ r 2 ε ˆ1 0 (1 -t)|D 2 g ε |(B rεt (x)) dt ≤ r 2 ε ˆ1 0 (1 -t)|D 2 g|(B rεt+ε (x)) dt ≤ r 2 2 |D 2 g|(B r (x)).
The second inequality is a simple consequence of the identity

|µ|(O) = sup{ ´φ • dµ : φ ∈ C c (O, S d (R)), φ ≤ 1} when µ is a S d (R)-valued measure and O is open. Besides, since
x is assumed to be a differentiability point of g, and a Lebesgue point of g and ∇g, we may pass to the inferior limit on the left-hand side and use Fatou's lemma to get:

ˆBr |g(x + h) -(g(x) + ∇g(x) • h)| dh ≤ r 2 2 |D 2 g|(B r (x)).
(3.9)

We set T x u(y) = u(x) + ∇u(x) • (y -x) whenever a function u is differentiable at x. By convexity of g on B r (x), [EG15, Theorem 6.7 (ii)] yields

3 sup B r/2 (x) |g -T x g| ≤ C Br(x)
|g -T x g|, (3.10) for a constant C = C(d), which together with (3.9) gives (3.8).

Step 2. Given a convex function g over Ω, let us show that:

ˆΩ sup B r/2 (x) |g -T x g| dx ≤ CH d-1 (∂Ω)r 2 [g] C 0,1 (Ω) , ( 3
≤ Cr 2 |D 2 g|(Ω).
(3.12) Again, we consider the regularization g ε = g η ε over Ω ε for small ε > 0. By convexity of g ε , we know that

|D 2 g ε | ≤ C∆g ε on Ω ε for some constant C = C(d). By Stokes' Theorem, ˆΩε ∆g ε = - ˆ∂Ωε ∇g ε • ν ≤ H d-1 (∂Ω ε )[g ε ] C 0,1 (Ωε) ≤ H d-1 (∂Ω)[g] C 0,1 (Ω) ,
where we have used the inequality H d-1 (∂Ω ε ) ≤ H d-1 (∂Ω), which holds because ∂Ω ε = p(∂Ω) where p is the projection onto the convex set Ω ε . Taking the limit ε → 0 yields, by weak convergence

D 2 g ε Ω ε D 2 g in C c (Ω, S d (R)) , |D 2 g|(Ω) ≤ lim inf ε→0 ˆΩε |D 2 g ε | ≤ lim inf ε→0 C ˆΩε ∆g ε ≤ CH d-1 (∂Ω)[g] C 0,1 (Ω) .
Then by monotone convergence, if we take the limit ε → 0 and report this in (3.12), we obtain:

ˆΩr sup B r/2 (x) |g -T x g| dx ≤ CH d-1 (∂Ω)r 2 [g] C 0,1 (Ω) ,
for some constant C = C(d). Now we need to take care of the integral over Ω

\ Ω r . But if g is Lipschitz on Ω with constant L = [g] C 0,1 (Ω) < ∞, then for almost every x ∈ Ω \ Ω r and every y ∈ B r/2 (x), we have |g(y) -(g(x) + ∇g(x) • (y -x))| ≤ 2L|y -x| ≤ Lr.
Finally, notice that since Ω is an open convex set, by the co-area formula (see [EG15, § 3.4]), for every r > 0,

L d (Ω \ Ω r ) = ˆr 0 H d-1 ({dist(•, R d \ Ω) = t}) dt = ˆr 0 H d-1 (∂Ω t ) dt ≤ rH d-1 (∂Ω),
and as a consequence, ˆΩ sup

B r/2 (x) |g -T x g| = ˆΩ\Ωr |g -T x g| + ˆΩr |g -T x g| ≤ (Lr)(rH d-1 (∂Ω)) + CH d-1 (∂Ω)r 2 [g] C 0,1 (Ω) = CH d-1 (∂Ω)[g] C 0,1 (Ω) r 2 ,
for some constant C = C(d) and (3.11) is proved.

Step 3. Let us conclude by establishing (3.7). Since f is λ-convex for some λ ≤ 0, we apply (3.11) to the convex function g :

x → f (x) -λ|x| 2 /2 to get ˆΩ sup B r/2 (x)∩Ω |f -T x f | ≤ ˆΩ sup B r/2 (x)∩Ω |g -T x g| dx + |λ| 2 ˆΩ sup y∈B r/2 (x)∩Ω ||y| 2 -(|x| 2 + 2x • (y -x))| dx ≤ Cr 2 H d-1 (∂Ω)[g] C 0,1 (Ω) + |λ| 8 r 2 L d (Ω) ≤ Cr 2 H d-1 (∂Ω)([f ] C 0,1 (Ω) + |λ| diam(Ω)) + |λ| 8 r 2 L d (Ω).
Knowing that L d (Ω) ≤ diam(Ω)H d-1 (∂Ω) since Ω is convex, we obtain (3.8) by replacing r by 2r, for some (different) constant C = C(d).

We are now ready to establish Proposition 3.4.

Proof of Proposition 3.4. The measures µ ± are supported in some open and bounded convex sets Ω ± 0 such that their closure X ± := cl(Ω ± 0 ) are included in Ω ± . Take γ 0 ∈ Opt(µ -, µ + ) and a pair of c-conjugate Kantorovich potentials (φ, ψ) ∈ C (X -) × C (X + ). Such potentials exist because c is continuous on the compact set X -× X + (see for example [San15, Proposition 1.11]). We set λ := sup

x =x ∈X -×X + |∇c(x )-∇c(x)| |x -x|
< ∞, so that c is λ-concave on X -× X + , which implies that φ, ψ are λ-concave on X -, X + respectively. As such, they are differentiable Lebesgue-a.e. on Ω - 0 , Ω + 0 , thus µ --a.e. and µ + -a.e. respectively, which in turn implies that

E := c -φ ⊕ ψ is differentiable γ 0 -a.e. on Ω - 0 × Ω + 0 because γ 0 ∈ Π(µ -, µ + ) and c ∈ C 1 (Ω - 0 × Ω + 0 )
. Moreover, by optimality of γ 0 and (φ, ψ) we have E ≥ 0 everywhere on X -× X + with equality on S γ 0 . As a consequence, for γ 0 -a.e. x 0 ∈ Ω - 0 × Ω + 0 , E(x 0 ) = 0, E is differentiable at x 0 and ∇E(x 0 ) = 0.

Take δ > 0 and consider the block approximation γ δ of γ 0 built in the proof of Proposition 3.1. Since by construction W ∞ (γ 0 , γ δ ) ≤ δ, there exists κ ∈ Π(γ 0 , γ δ ) such that x 0 -x ≤ δ for κ-a.e. (x 0 , x), and we know in particular that E is differentiable at x 0 , and T x 0 E(x) = 0 for κ-a.e. (x 0 , x). Thus we have: ˆΩ-

0 ×Ω + 0 (c -φ ⊕ ψ) dγ δ = ˆ(Ω - 0 ×Ω + 0 ) 2 (E(x) -T x 0 E(x)) dκ(x 0 , x) = ˆ(Ω - 0 ×Ω + 0 ) 2 (c(x) -T x 0 c(x)) dκ(x 0 , x) - ˆΩ- 0 ×Ω - 0 (φ(x) -T x 0 φ(x)) dκ -(x 0 , x) - ˆΩ+ 0 ×Ω + 0 (ψ(y) -T y 0 ψ(y)) dκ + (y 0 , y),
where

κ -= (π 1 , π 3 ) # κ, κ + = (π 2 , π 4 ) # κ and π i denotes the projection on the i-th component. Since c is λ-concave on Ω - 0 × Ω + 0 , c(x) -T x 0 c(x) ≤ λ 2 |x -x 0 | 2 ,
and since φ, ψ are λ-concave on Ω - 0 , Ω + 0 respectively, using Lemma 3.6 and recalling that

(π 1 ) # κ ± = µ ± , ˆΩ+ 0 ×Ω + 0 (c -φ ⊕ ψ) dγ δ ≤ λ 2 |x -x 0 | 2 + ˆΩ- 0 sup x∈B δ (x 0 )∩Ω - 0 |φ(x) -T x 0 φ(x)| dµ -(x 0 ) + ˆΩ+ 0 sup y∈B δ (y 0 )∩Ω + 0 |ψ(y) -T y 0 ψ(y)| dµ + (y 0 ) ≤ λδ 2 +Cδ 2 µ - L ∞ (Ω - 0 ) H d-1 (∂Ω - 0 )([φ] C 0,1 (Ω - 0 ) + λ diam(Ω - 0 )) +Cδ 2 µ + L ∞ (Ω + 0 ) H d-1 (∂Ω + 0 )([ψ] C 0,1 (Ω + 0 ) + λ diam(Ω + 0 )) ≤ C δ 2 ,
for some constant C > 0 which does not depend on δ. Now, we apply (3.1) to assert that H δ (µ + ) ≤ log(N δ (X + )) ≤ d log(1/δ) + log C for some constant C > 0 depending only on X + , and we use γ δ as a competitor in (EOT ε ) to obtain:

v ε ≤ ˆΩ-×Ω + c dγ δ + εH δ (µ + ) = v 0 + ˆΩ-×Ω + (c -φ ⊕ ψ) dγ δ + εH δ (µ + ) ≤ v 0 + C δ 2 + εH δ (µ + ) = v 0 + C δ 2 + dε log(1/δ) + ε log C.
Finally, taking δ = √ ε yields:

v ε ≤ v 0 + d 2 ε log(1/ε) + ε(C + log C).

Lower bound for infinitesimally twisted costs

In this section, we establish a lower bound that is analogous to the fine upper bound given in Section 3.2, for a class of C 2 costs satisfying an infinitesimal twist condition, which includes situations where optimal plans are not necessarily given by a map. Our proof is based on the so-called Minty's trick asserting that the graph of a monotone operator is a 1-Lipschitz graph in a rotated chart (see [START_REF] Minty | Monotone (Nonlinear) Operators in Hilbert Space[END_REF]). It has been used in particular by Alberti and Ambrosio [START_REF] Alberti | A geometrical approach to monotone functions in R n[END_REF] to study the fine properties of monotone functions on R d , and more recently in optimal transport by McCann, Pass and Warren [START_REF] Mccann | Rectifiability of Optimal Transportation Plans[END_REF] to show the rectifiability of optimal transport plans. We will exploit this trick a little bit further to show a quadratic detachment of the duality gap, leading to the lower bound that we seek. As a side remark, we deduce from the same trick a quantitative stability result in the quadratic case c(x, y) = |x -y| 2 .

Proof of the lower bound

We start with the definition of the infinitesimal twist condition, corresponding to condition (A2) in [START_REF] Ma | Regularity of Potential Functions of the Optimal Transportation Problem[END_REF], and the non-degeneracy condition in [START_REF] Mccann | Rectifiability of Optimal Transportation Plans[END_REF].

Definition 4.1. Given c ∈ C 2 (Ω -× Ω + ) where Ω ± ⊆ R d are open sets, we say that c is infinitesimally twisted if ∇ 2 xy c(x, y) := (∂ 2 x i y j c(x, y)) i,j ∈ M d (R) is invertible for every (x, y) ∈ Ω -× Ω + .
McCann, Pass and Warren have proved that for such a cost, the support of any optimal transport plan is locally Lipschitz (see [MPW12, Theorem 1.2]).

We closely follow the computations of [START_REF] Mccann | Rectifiability of Optimal Transportation Plans[END_REF] leading to the proof of their main theorem, but we consider points which do not necessarily belong to the support of an optimal plan. Lemma 4.2. Let c ∈ C 2 (Ω -× Ω + ) be an infinitesimally twisted cost, and (φ, ψ) ∈ C (X -) × C (X + ) be a pair of c-conjugate functions on compact convex sets X ± ⊆ Ω ± . We set E := c -φ ⊕ ψ on X -× X + , Σ := {E = 0}, and for every r > 0, κ(r) := sup Proof. Take x ∈ X -× X + , x = (x, y) and x = (x , y ) in B r (x) ∩ (X -× X + ). Knowing that (φ, ψ) is a pair of c-conjugate functions, and using Taylor's integral formula,

(x,x )∈X -×X + x -x ≤r ∇ 2 xy c(x ) -1 ∇ 2 xy c(x) -Id ∈ [0, ∞). If x ∈ X -× X + and x, x ∈ B r (x) ∩ (X -× X + ), then E(x ) + E(x) ≥ |∆u| 2 -|∆v| 2 -κ(r)(|∆u| 2 + |∆v| 2 ), ( 4
E(x ) = c(x , y ) -φ(x ) -ψ(y ) ≥ c(x , y ) -(c(x , y) -ψ(y)) -(c(x, y ) -φ(x)) = c(x , y ) -c(x , y) -c(x, y ) + c(x, y) -E(x) = -E(x) + (x -x) • ˆ1 0 ˆ1 0 ∇ 2 xy c(x + (1 -s)x , y + (1 -t)y ) ds dt (y -y).
With the notations introduced in the statement of the lemma, x = u(x) + v(x) and y = ∇ 2 xy c(x) -1 (u(x) -v(x)), and similarly for x , so that:

E(x ) + E(x) ≥ (∆u + ∆v) • ˆ1 0 ˆ1 0 ∇ 2 xy c(x + (1 -s)x , y + (1 -t)y )∇ 2 xy c(x) -1 ds dt (∆u -∆v) ≥ |∆u| 2 -|∆v| 2 -κ(r)|∆u + ∆v||∆u -∆v| ≥ |∆u| 2 -|∆v| 2 -κ(r)(|∆u| 2 + |∆v| 2 ),
the last inequality resulting from the fact that |a+b||a-b| ≤ |a| 2 +|b| 2 for every a, b ∈ R d , as can be seen by expanding and comparing the squares of the two sides.

Remark 4.3. The rectifiability theorem of McCann, Pass and Warren [MPW12, Theorem 1.2] is an immediate consequence of Lemma 4.2 (to no surprise, since we have essentially followed their computations). Indeed, for any optimal plan γ ∈ Π(µ -, µ + ) with µ ± supported on compact convex sets X ± ⊆ Ω ± , by taking x, x, x ∈ S γ ⊆ Σ , (4.1) yields

|∆u| ≤ 1 + κ(r) 1 -κ(r) |∆v|,
and since κ(r)

r→0 ---→ 0, v is a Lipschitz function of u, so that B r (x) ∩ S γ is included in a Lipschitz d-dimensional graph.
Notice however that (4.1) gives extra information: if we take for example x = x, and we fix v = v = v but we let the u component free, we get

E(x ) ≥ (1 -κ(r))|u -u| 2 .
Thus we have a quadratic growth of E away from x in the direction given by the u coordinate. This is what we shall use to get the lower bound.

Proposition 4.4. Let Ω ± be open convex subsets of R d , c ∈ C 2 (Ω -× Ω + ) be an in- finitesimally twisted cost, and µ ± ∈ P(Ω ± ) ∩ L ∞ (Ω ± ) with compact support in Ω ± . There exists a constant m ∈ [0, ∞) such that for every ε > 0, v ε ≥ v 0 + d 2 ε log(1/ε) -mε. (4.2)
Proof. The measures µ ± being concentrated on some compact convex subsets X ± ⊆ Ω ± , consider a pair (φ, ψ) ∈ C (X -) × C (X + ) of c-conjugate Kantorovich potentials. Taking (φ, ψ) as competitor in (D ε ), we get the lower bound:

v ε ≥ ˆX- φ dµ -+ ˆX+ ψ dµ + -ε log ˆX-×X + e -E ε dµ -⊗ µ + = v 0 -ε log ˆX-×X + e -E ε dµ -⊗ µ + ,
where E := c -φ ⊕ ψ on X -× X + as in Lemma 4.2. We are going to show that for some constant C > 0 and for every ε > 0, ˆX-×X + e -E/ε dµ -⊗ µ + ≤ Cε d/2 , which yields (4.2) with m = log(C). We follow the notation introduced in the statement of Lemma 4.2, and consider in particular the functions u, v defined for a fixed x ∈ X -× X + . We define the affine map Φ x : x → (u(x), v(x)) -(u(x), v(x)) whose Jacobian determinant is easily computed:

JΦ x = (-1/2) d det(∇ 2 xy c(x)). Thus Φ x is an affine isomorphism and |J(Φ x) -1 | ≤ C 1 := 2 d sup x∈X -×X + |det ∇ 2 xy c(x)| -1 < ∞ because c is infinitesimally twisted. We set E x := E • Φ -1 x over D x := Φ x(X -× X + ) and define the open neighborhood of x, P x := Φ -1 x (B r × B r ) ⊆ B Lr (x), where L := 2(1 ∧ sup x∈X -×X + (∇ 2 xy c(x)) -1
) and r > 0 is chosen such that κ(Lr) ≤ 1/2. By the change of variable formula we get:

ˆPx ∩X -×X + e -E/ε dµ -⊗ µ + = ˆ(Br×Br)∩D x e -E(Φ -1 x (u,v))/ε (µ -⊗ µ + )(Φ -1 x (u, v))|J(Φ x) -1 (u, v)| du dv ≤ C 1 µ - L ∞ (Ω -) µ + L ∞ (Ω + )
ˆπ2 ((Br×Br)∩D x) ˆ{u∈Br:(u,v)∈D x} e -E x(u,v)/ε du dv.

Now, for every

v ∈ π 2 ((B r × B r ) ∩ D x), consider u v a minimizer of E x(•, v) over {u ∈ Br : (u, v) ∈ D x}. By (4.1) of Lemma 4.2, for every u ∈ B r such that (u, v) ∈ D x, E x(u, v) ≥ 1 2 (E x(u v , v) + E x(u, v))) ≥ 1 2 (1 -κ(Lr))|u -u v | 2 ≥ 1 4 |u -u v | 2 .
As a consequence we obtain:

ˆπ2 ((Br×Br)∩D x) ˆ{u∈Br:(u,v)∈D x} e -E x(u,v)/ε du dv ≤ ˆπ2 (Br×Br)∩D x ˆBr e -|u-uv| 2 /2ε du dv ≤ ω d r d ε d/2 ˆRd e -|u| 2 /2 du ≤ C 2 r d ε d/2 ,
N i=1 P xi ∩X -×X + e -E/ε µ -⊗ µ + ≤ N C 1 C 2 µ - L ∞ (Ω -) µ + L ∞ (Ω + ) r d ε d/2 ≤ C 3 ε d/2 ,
for some constant C 3 > 0. Finally, since E is continuous and does not vanish on the compact set K = (X -×X + )\ N i=1 P xi , it is bounded from below on K by some constant C 4 > 0. Therefore, for every ε > 0,

ˆX-×X + e -E/ε dµ -⊗ µ + ≤ C 3 ε d/2 + e -C 4 /ε ≤ Cε d/2 ,
for some constant C > 0. This concludes the proof.

Quantitative stability of optimal plans for the quadratic cost

This final paragraph is devoted to the quadratic-cost case for which combining Minty's trick and the upper bound on the entropic cost, one can obtain a quantitative estimate between the optimal entropic plan and optimal transport plans. Given two probability measures µ ± ∈ P(R d ) with compact support, taking as cost function c(x, y) := 1 2 |x-y| 2 , the transport cost is merely the square 2-Wasserstein distance:

v 0 = 1 2 W 2 2 (µ -, µ + ) := 1 2 inf γ∈Π(µ -, µ + ) ˆRd ×R d |x -y| 2 dγ(x, y).
It is well known (see Brenier [START_REF] Brenier | Polar Factorization and Monotone Rearrangement of Vector-Valued Functions[END_REF], McCann [START_REF] Mccann | Existence and Uniqueness of Monotone Measure-Preserving Maps[END_REF]) that there exists a convex lsc function f on R d such that γ ∈ Π(µ -, µ + ) is optimal in the above quadratic OT problem if and only if

S γ ⊆ Γ f := {(x, y) ∈ R d × R d : f (x) + f * (y) = x • y} = {(x, y) ∈ R d × R d : y ∈ ∂f (x)}
where f * is the Legendre transform of f . Kantorovich potentials are then given by φ(x) := 1 2 |x| 2 -f (x), ψ(y) := 1 2 |y| 2 -f * (y), (∀x, y ∈ R d ).

If µ -is absolutely continuous with respect to the Lebesgue measure, f is differentiable µ --a.e. and there is a unique optimal plan γ := (Id, T ) # µ -where T := ∇f is Brenier's optimal transport map from µ -to µ + . For ε > 0, the entropic cost reads

v ε = inf γ∈Π(µ -, µ + ) 1 2 ˆRd ×R d |x -y| 2 dγ(x, y) + εEnt(γ | µ -⊗ µ + ) ,
and we denote as before by γ ε the optimal entropic plan. Our goal is to give an estimate on how γ ε fails to be concentrated on Γ f for small ε > 0 in a sense to be made precise. First we observe that by nonnegativity of the entropic term, we have

v ε -v 0 ≥ 1 2 ˆRd ×R d |x -y| 2 dγ ε (x, y) - 1 2 W 2 2 (µ -, µ + ).
Defining the duality gap as in the previous section by: E(x, y) := 1 2 |x -y| 2 -φ(x) -ψ(y) = f (x) + f * (y) -x • y (∀x, y ∈ R d ),

one has E ≥ 0 and E(x, y) = 0 if and only if (x, y) ∈ Γ f , i.e. y ∈ ∂f (x). Denoting by γ 0 an optimal transport plan, since E = 0 on S γ 0 and γ ε and γ share the same marginals, we have where γ x ε is the disintegration of γ ε with respect to its first marginal.

v ε -v 0 ≥ 1 2 ˆRd ×R d |x -y| 2 dγ ε (x, y) - 1 2 W 2 2 (µ -, µ + ) = ˆRd ×R d E(x,
Of course the requirement that the convex potential f is smooth is quite demanding and cannot be taken for granted in general. Yet, if f is an arbitrary lsc convex function, one can take advantage of Minty's trick to have a quadratic detachment lower bound on E as we did in Lemma 4.2. Proposition 4.6. If µ ± ∈ P(R d ) are compactly supported probability measures, and if we denote by γ ε the optimal entropic plan from µ -to µ + , the following stability bound holds:

ˆRd Now we observe that the resolvent (Id +∂f ) -1 is a single-valued 1-Lipschitz map and that E(x , y ) vanishes if and only if y + x ∈ x + ∂f (x ), hence if and only if x = (Id +∂f ) -1 (x + y ). As a consequence if we choose in the inequality above x = (Id +∂f ) -1 (x + y) and y = x + y -x , we have E(x , y ) = 0 and we get the quadratic detachment bound:

E(x,

  a positive Radon measure, and σ f : Ω → S d (R) is a Borel unit matrix field for the Frobenius norm. Lemma 3.6. Let f : Ω → R be a λ-convex function on a convex open set for some λ ≤ 0. There exists a constant C ≥ 0 depending only on d such that: ˆΩ sup y∈Br(x)∩Ω

. 1 )

 1 where we have set ∆u := u(x ) -u(x), ∆v := v(x ) -v(x), and u(x) 2 xy c(x)y), for every x = (x, y).

  y) dγ ε (x, y). (4.3)In the event where ∇f is M -Lipschitz, which, by Caffarelli's regularity theory[START_REF] Caffarelli | Boundary Regularity of Maps with Convex Potentials[END_REF][START_REF] Caffarelli | Boundary Regularity of Maps with Convex Potentials-II[END_REF] holds true if µ ± have Hölder densities bounded away from zero on their supports and the latter are smooth and uniformly convex, arguing as Berman in[START_REF] Berman | Convergence Rates for Discretized Monge-Ampère Equations and Quantitative Stability of Optimal Transport[END_REF] and as Li and Nochetto in[START_REF] Li | Quantitative Stability and Error Estimates for Optimal Transport Plans[END_REF], who build upon an earlier argument of Gigli[START_REF] Gigli | On Hölder Continuity-in-Time of the Optimal Transport Map towards Measures along a Curve[END_REF], one can use the inequalityE(x, y) = f * (y) -f * (∇f (x)) -x • (y -∇f (x)) ≥ 1 2M |y -∇f (x)| 2 (4.4) (using the fact that x ∈ ∂f * (∇f (x)) and f * -1 2M |•| 2 is convex as soon as ∇f is L-Lipschitz)to arrive at: Proposition 4.5. If Brenier's optimal transport map T = ∇f between the compactly supported probability measures µ -and µ + is M -Lipschitz, denoting by γ ε the optimal entropic plan between µ -and µ + , one has ˆRd ×R d |y -T (x)| 2 dγ ε (x, y) ≤ M (dε log(1/ε) + O(ε)). (4.5)In particular, if T ε denotes the barycentric projection of γ ε (i.e. T ε (x) is the conditional expectation of Y given X = x with (X, Y ) distributed according to γ ε ), there holdsT ε -T 2 L 2 (µ -) ≤ M (dε log(1/ε) + O(ε)). (4.6) Proof. Inequality (4.5) follows directly from (4.3), (4.4) and the upper bound v ε -v 0 ≤ dε log(1/ε) + O(ε) from Proposition 3.1 (note also that if µ ± have bounded densities, one can improve the factor d by d 2 thanks to Proposition 3.4). Finally (4.6) directly follows from (4.5) and Jensen's inequality: ˆRd ×R d |y -T (x)| 2 dγ ε (x, y) = ˆRd ˆRd |y -T (x)| 2 dγ x ε (y) dµ -(x) ≥ ˆRd ˆRd (y -T (x)) dγ x ε (y) 2 dµ -(x) = ˆRd |T ε (x) -T (x)| 2 dµ -(x),

  ×R d |x -(Id +∂f ) -1 (x + y)| 2 dγ ε (x, y) ≤ (dε log(1/ε) + O(ε)),where (Id +∂f ) -1 is the (single-valued) resolvent associated with f . Proof. Let us first observe that when c is the quadratic cost (4.1) takes the formE(x, y) ≥ -E(x , y ) -(x -x) • (y -y)(∀x, y, x , y ∈ R d ).

  y) ≥ |x -(Id +∂f ) -1 (x + y)| 2 , (∀x, y ∈ R d ).(4.7)Hence, from (4.7), (4.3) and Proposition 3.1, we obtain the desired inequality (and again one can improve the factor d by d 2 thanks to Proposition 3.4 if µ ± have bounded densities).

  .11) for some constant C = C(d). Without loss of generality, we may assume that Ω is bounded and [g] C 0,1 (Ω) < ∞, otherwise the right-hand side is trivial. Since g is convex, Lebesgue-almost every point x ∈ Ω is a differentiability point of g by Rademacher's Theorem, and a Lebesgue point of g and ∇g by Lebesgue's Theorem, thus integrating (3.8) over Ω

	ˆΩ	ˆBr(y)∩Ωr	1 ω d r d dx d|D 2 g|(y)

r := {x : dist(x, R d \ Ω) > r} and using Fubini-Tonelli's Theorem, ˆΩr sup

B r/2 (x)

|g -T x g| dx ≤ Cr 2

  for some constant C 2 > 0. The sets {P x} x∈Σ form an open covering of the compact set Σ ⊆ X -×X + , hence we may extract a finite covering P x1 , . . . , P xN , so that Σ ⊆ N i=1 P xi and: ˆ

By the way, this also shows that the differentiability of vε at ε = 0 is in fact equivalent to the existence of an optimal plan with finite entropy.

For measures on R d × R d , we consider the Wasserstein distance with respect to the norm that we introduced, namely (x, y) = max{|x|, |y|} for every (x, y) ∈ R d × R d .

Notice that the proof works as soon as g is defined on Br(x), not necessarily on the whole space R d .

Acknowledgments: G.C. acknowledges the support of the Lagrange Mathematics and Computing Research Center.


Abir Laraba

Jérôme François

Shihabur Isabelle Chrisment

Rahman Chowdhury

Raouf Boutaba

Detecting Multi-Step Attacks: A Modular Approach for Programmable Data Plane

HAL is