Tam Le

Jérôme Malick

Universal Generalization Guarantees for Wasserstein Distributionally Robust Models

Distributionally robust optimization has emerged as an attractive way to train robust machine learning models, capturing data uncertainty and distribution shifts. Recent statistical analyses have proved that robust models built from Wasserstein ambiguity sets have nice generalization guarantees, breaking the curse of dimensionality. However, these results are obtained in specific cases, at the cost of approximations, or under assumptions difficult to verify in practice. In contrast, we establish, in this article, exact generalization guarantees that cover all practical cases, including any transport cost function and any loss function, potentially non-convex and nonsmooth. For instance, our result applies to deep learning, without requiring restrictive assumptions. We achieve this result through a novel proof technique that combines nonsmooth analysis rationale with classical concentration results. Our approach is general enough to extend to the recent versions of Wasserstein/Sinkhorn distributionally robust problems that involve (double) regularizations.

Introduction 1.Wasserstein robustness: models and generalization

Machine learning models are challenged in practice by many obstacles, such as biases in data, adversarial attacks, or data shifts between training and deployment. Towards more resilient and reliable models, distributionally robust optimization has emerged as an attractive paradigm, where training no longer relies on minimizing the empirical risk, but rather on an optimization problem that takes into account potential perturbations in the data distribution; see e.g., the review articles [START_REF] Kuhn | Wasserstein distributionally robust optimization: Theory and applications in machine learning[END_REF][START_REF] Blanchet | Statistical analysis of wasserstein distributionally robust estimators[END_REF].

More specifically, the approach consists in minimizing the worst-risk among all distributions in a neighborhood of the empirical data distribution. A natural way [START_REF] Esfahani | Data-driven distributionally robust optimization using the wasserstein metric: performance guarantees and tractable reformulations[END_REF] to define such a neighborhood is to use the optimal transport distance, called the Wasserstein distance [START_REF] Peyré | Computational optimal transport: With applications to data science[END_REF]. Between two distributions Q and Q ′ on a sample space Ξ, the Wasserstein distance is defined as the minimal expected cost among all coupling probability π on Ξ × Ξ having Q and Q ′ as marginals:

W c (Q, Q ′ ) := inf π∈P(Ξ×Ξ) [π] 1 =Q,[π] 2 =Q ′ E (ξ,ζ)∼π [c(ξ, ζ)], (1)
where c : Ξ × Ξ → R is a transport cost over the sample space Ξ. For a class of loss functions F, the Wasserstein distributionally robust counterpart of the standard empirical risk minimization then writes min

f ∈F max Q∈P(Ξ),Wc( Pn,Q)≤ρ E ξ∼Q [f (ξ)], (2)
for a chosen radius ρ of the Wasserstein ball centered at the empirical data distribution, denoted P n . In the degenerate case ρ = 0, we have Q = P n and (2) boils down to empirical risk minimization. If ρ > 0, the training captures data uncertainty and provides more resilient learning models; see the discussions and illustrations [START_REF] Shafieezadeh-Abadeh | Distributionally robust logistic regression[END_REF][START_REF] Sinha | Certifying some distributional robustness with principled adversarial training[END_REF][START_REF] Zhao | Data-driven risk-averse stochastic optimization with wasserstein metric[END_REF][START_REF] Kwon | Principled learning method for wasserstein distributionally robust optimization with local perturbations[END_REF][START_REF] Li | Fast epigraphical projection-based incremental algorithms for wasserstein distributionally robust support vector machine[END_REF][START_REF] Taskesen | Sequential domain adaptation by synthesizing distributionally robust experts[END_REF][START_REF] Gao | Wasserstein distributionally robust optimization and variation regularization[END_REF][START_REF] Arrigo | Wasserstein distributionally robust chance-constrained optimization for energy and reserve dispatch: An exact and physically-bounded formulation[END_REF][START_REF] Belbasi | It's all in the mix: Wasserstein machine learning with mixed features[END_REF].

To support theoretically the modeling versatility and the practical success of these robust models, some statistical guarantees have been proposed in the literature. For a population distribution P , i.i.d. samples ξ 1 , . . . , ξ n drawn from P , and the associated empirical distribution P n := 1 n n i=1 δ ξ i , the best concentration results for the Wasserstein distance [START_REF] Fournier | On the rate of convergence in wasserstein distance of the empirical measure[END_REF] gives that if the radius ρ is large enough, then the Wasserstein ball around P n contains the true distribution P with high probability, which in turn gives directly [START_REF] Esfahani | Data-driven distributionally robust optimization using the wasserstein metric: performance guarantees and tractable reformulations[END_REF] a generalization bound of the form 3) to hold, estimated from 500 logistic regression instances and their ℓ 1 -robust counterparts (see at the end of Section 3). For large ρ, the bound always holds, whereas it does not for small ρ. Our aim is to quantify this phenomenon, which is not explained by existing results.

max Q∈P(Ξ),Wc( Pn,Q)≤ρ

E ξ∼Q [f (ξ)] ≥ E ξ∼P [f (ξ)]. ( 3
)
This exact bound is particularly attractive: the quantity that we compute from data and optimize by training provides a control on the idealistic population risk. However, the direct application of [START_REF] Fournier | On the rate of convergence in wasserstein distance of the empirical measure[END_REF] requires a number of training samples growing exponentially in the dimension.

Recent works have improved this direct approach by establishing, in various situations, generalization bounds that do not suffer from the curse of dimensionality, and rather feature radius ρ scaling as O(1/ √ n) [START_REF] Sinha | Certifying some distributional robustness with principled adversarial training[END_REF][START_REF] Blanchet | Confidence regions in Wasserstein distributionally robust estimation[END_REF][START_REF] An | Generalization bounds for (wasserstein) robust optimization[END_REF][START_REF] Gao | Finite-sample guarantees for wasserstein distributionally robust optimization: Breaking the curse of dimensionality[END_REF][START_REF] Azizian | Exact generalization guarantees for (regularized) wasserstein distributionally robust models[END_REF][START_REF] Blanchet | Statistical limit theorems in distributionally robust optimization[END_REF]]. Yet no existing result is general enough to cover all situations encountered in machine learning and to explain nice generalization properties usually observed in practice (as illustrated in Figure 1).

Contributions and outline

In this paper, we provide exact generalization guarantees of the form [START_REF] An | Generalization bounds for (wasserstein) robust optimization[END_REF], that are universal, in the sense that they apply to all machine learning situations, without restrictive assumptions. Indeed, our results apply to any kind of data lying in a metric space (e.g. classification and regression tasks with mixed features), as well as general classes of continuous loss functions (e.g. from standard regression tasks to deep learning models).

We prove these universal results by dealing directly with the nonsmoothness of the robust objective function (2) that we tackle with tools from variational analysis [START_REF] Clarke | Optimization and Nonsmooth Analysis[END_REF][START_REF] Rockafellar | Variational Analysis[END_REF][START_REF] Aliprantis | Infinite Dimensional Analysis[END_REF]. As a nice outcome of this approach, our results are able to cover deep learning models involving nonsmooth elementary blocks, such as the popular ReLU activation function, the max-pooling operator, or optimization layers [START_REF] Amos | Optnet: Differentiable optimization as a layer in neural networks[END_REF]. Moreover, our approach is systematic enough to extend to the recent versions of Wasserstein distributionally robust problems that involve (double) regularizations [START_REF]Regularization for wasserstein distributionally robust optimization[END_REF][START_REF] Wang | Sinkhorn distributionally robust optimization[END_REF].

The paper is structured as follows. First, Section 2 introduces and illustrates the setting of this work. Then Section 3 presents and discusses the main results (Theorems 3.1 and 3.2). Section 4 highlights our proof techniques, combining classical concentration lemma and advanced nonsmooth analysis aspects. Finally, Section 5 sheds some light on generalization constants and other quantities of interest appearing in the results and the proof. We differ, to the supplementary, the proofs of the succession of lemmas, as well as complementary results discussing technical assumptions of existing works.

Related work

Our work stands out from a recent line of research establishing generalization guarantees for Wasserstein distributionally robust models, breaking the curse of dimensionality. Notably, important results on the topic include [START_REF] Blanchet | Confidence regions in Wasserstein distributionally robust estimation[END_REF][START_REF] Blanchet | Statistical limit theorems in distributionally robust optimization[END_REF] about asymptotical results for smooth losses, and [START_REF] Chen | A robust learning approach for regression models based on distributionally robust optimization[END_REF][START_REF] Shafieezadeh-Abadeh | Regularization via mass transportation[END_REF] about non-asymptotically results for linear models and for smooth loss functions. For nonsmooth losses, the only work we are aware of is [START_REF] An | Generalization bounds for (wasserstein) robust optimization[END_REF] which derives results on piece-wise smooth losses (at the cost of abstract approximating constants). We underline that none of existing results covers deep learning models involving nonsmooth elementary blocks.

The closest work to our paper is [START_REF] Azizian | Exact generalization guarantees for (regularized) wasserstein distributionally robust models[END_REF] which establishes generalization results similar to ours, namely: exact bounds (3) in a regime where ρ > O(1/ √ n). In sharp contrast with our work though, these results rely on a restrictive context and some needless assumptions (the squared norm for c, a Gaussian reference distribution, additional growth conditions, and abstract compactness conditions 1 ). Throughout our developments, we will point out further technical differences with this work.

Notations

On probability spaces. Given a measurable space Ξ, we denote the space of probability measures on Ξ by P(Ξ). For all π ∈ P(Ξ × Ξ), i ∈ {1, 2}, we denote the i th marginal of π by [π] i . We denote the Dirac mass at ξ ∈ Ξ by δ ξ . Given a measurable function g : Ξ → R, we denote the expectation of g with respect to Q ∈ P(Ξ) by E ξ∼Q [g(ξ)] and we may also use the shorthand

E Q [f ]. 1
We show in Proposition F.3 in the supplementary that the compactness assumptions hide strong conditions on the maximizers.

On function spaces. In (X , dist) a metric space, the uniform norm of a function f is

∥f ∥ ∞ = sup x∈X |f (x)|. If F is a family of functions, we denote ∥F∥ ∞ = sup f ∈F ∥f ∥ ∞ . We say f is Lipschitz with constant L if for all x, y ∈ X , |f (x) -f (y)| ≤ L dist(x, y). For ϕ : R × X → R, we denote ∂ +
λ ϕ the right-sided derivative with respect to λ ∈ R, and ∂ λ ϕ its derivative, whenever well-defined.

Assumption and examples

In this section, we present the general framework illustrated by standard examples. Throughout the paper, we will make the following assumptions on the sample space Ξ, the transport cost of the Wasserstein distance, and the space F of loss functions from Ξ to R. Assumption 2.1.

• (Ξ, d) is a compact metric space. • c : Ξ × Ξ → R is jointly continuous with respect to d, non-negative and c(ξ, ζ) = 0 if and only if ξ = ζ. • (F, ∥ • ∥ ∞ ) is compact and every f ∈ F is continuous.
This setting encompasses a wide range of machine learning scenarios, as illustrated below.

Sample space and transport costs. The choice of the transport cost c depends on the nature of the data and of the potential data uncertainty. For instance, if the variables are continuous with Ξ ⊂ R m , we consider the distance

d = ∥ • -• ∥ p induced by ℓ p -norm (p ∈ [1, ∞]
) and the cost as a power (q

∈ [1, ∞)) of the distance c(ξ, ξ ′ ) = ∥ξ -ξ ′ ∥ q p .
If the variables are discrete with Ξ ⊂ {1, . . . , J} m , we consider the distance

d(ξ, ξ ′ ) = m i=1 1 {ξi̸ =ξ ′ i }
and the cost as a power of this distance. Finally, If we deal with mixed data, i.e. they contain both continuous and discrete variables, a sum of the previous costs can be considered.

In classification, for instance, with the samples composed of features x ∈ R m and a target y ∈ {-1, 1}, we may take, for a chosen κ > 0

c((x, y), (x ′ , y ′ )) = ∥x -x ′ ∥ q p + κ1 {y̸ =y ′ } (4)
which is obviously continuous with respect to

d((x, y), (x ′ , y ′ )) = ∥x -x ′ ∥ p + 1 {y̸ =y ′ } . (5)
This extends to mixed data with categorical, binary, and continuous variables; see e.g. [START_REF] Belbasi | It's all in the mix: Wasserstein machine learning with mixed features[END_REF].

Parametric models and loss functions. Our setting covers all standard machine learning models. Consider a parametric family F = {f (θ, •) : θ ∈ Θ}, where the parameter space Θ ⊂ R p compact and the loss function f : Θ × Ξ → R is jointly continuous. If Ξ is compact, such a family is compact regarding ∥ • ∥ ∞ . This situation covers regression models, k-means clustering, and neural networks. For example: least-squares regression

f (θ, (x, y)) = (⟨θ, x⟩ -y) 2 , Ξ ⊂ R m × R, logistic regression f (θ, (x, y)) = log 1 + e -y⟨θ,x⟩ , Ξ ⊂ R m × {-1, 1},
and support vector machines with hinge loss

f (θ, (x, y)) = max {0, 1 -y⟨θ, x⟩} , Ξ ⊂ R m × {-1, 1}
Note that this function is not differentiable, due to the max term. The k-means model also introduces a non-differentiable loss function:

f (θ, x) = min i∈{1,...,K} ∥θ i -x∥ 2 2 , Θ ⊂ R K×m , Ξ ⊂ R m .
Finally, most deep learning models fall in our setting. Indeed, they involve loss functions of the form

f (θ, (x, y)) = ℓ(h(θ, x), y),
where ℓ is a dissimilarity measure, and h is a parameterized prediction function, built as a composition of affine transformations (which are the parameters to train) with activation functions (see e.g. [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF][START_REF] Lecun | Deep learning[END_REF][START_REF] Redmon | You only look once: Unified, real-time object detection[END_REF]). Our setting is general enough to encompass all continuous activation functions, even non-differentiable ones (as ReLU = max(0, •)) as well as other nonsmooth elementary blocks (as max-pooling [START_REF] He | Deep residual learning for image recognition[END_REF], sorting procedures [START_REF] Sander | Fast, differentiable and sparse top-k: A convex analysis perspective[END_REF], and optimization layers [START_REF] Amos | Optnet: Differentiable optimization as a layer in neural networks[END_REF]). As already underlined in introduction, these examples involving non-differentiable terms are not covered by existing results.

3 Main results

Wasserstein robust models

Our main result establishes a generalization bound (3) for Wasserstein distributionally robust optimization (WDRO). Given a distribution Q ∈ P(Ξ) and a loss f ∈ F, the robust risk around Q with radius ρ > 0 is then defined as

R ρ,Q (f ) := max Q ′ ∈P(Ξ),Wc(Q,Q ′ )≤ρ E ξ∼Q ′ [f (ξ)]. (6)
In particular, taking Q = P n and Q = P in the above expression, we consider the empirical robust risk, R ρ (f ), and the true robust risk, R ρ (f ):

R ρ (f ) := R ρ, Pn (f ) and R ρ (f ) := R ρ,P (f ). ( 7
)
Our generalization result states as follows:

Theorem 3.1 (Generalization guarantee for Wasserstein robust models). Under Assumption 2.1, there exist α, β > 0 such that if

α √ n < ρ < ρ crit 2 - β √ n ,
then with probability at least 1δ,

∀f ∈ F, R ρ (f ) ≥ E ξ∼P [f (ξ)].
The quantity ρ crit is a critical radius, a relevant threshold that excludes degenerated problems and flat losses for which R ρ (f ) = max Ξ f . The exact generalization guarantee thus holds for a wide range of radius ρ, growing with the sample size between the two extreme cases 0 and ρ crit . As in Theorem 3.1 from [START_REF] Azizian | Exact generalization guarantees for (regularized) wasserstein distributionally robust models[END_REF], but adding the wide setting of Assumption 2.1, the sample rates are dimension-free. The constants α and β depend on the problem quantities, see Section 5 for a detailed discussion.

Regularized Wasserstein robust models

Part of the success of optimal transport in machine learning is the use of regularization, and specifically entropic regularization, opening the way to nice properties and efficient computational schemes [START_REF] Cuturi | Sinkhorn distances: Lightspeed computation of optimal transport[END_REF][START_REF] Peyré | Computational optimal transport: With applications to data science[END_REF]. Recall that the entropy-regularized Wasserstein distance writes, for a reference coupling π 0 ∈ P(Ξ×Ξ)

W τ c (P, Q) = inf π∈P(Ξ×Ξ) [π] 1 =P,[π 2 ]=Q {E π [c] + τ KL(π∥π 0 )} ( 8
)
where KL is the Kullback-Leibler divergence w.r.t. π 0 : KL(π∥π 0 ) = Ξ×Ξ log dπ dπ 0 dπ when π ≪ π 0 ∞ otherwise.

Regularization have been recently studied in the context of WDRO: [START_REF] Wang | Sinkhorn distributionally robust optimization[END_REF] introduces an entropic regularization in constraints for computational interests, [START_REF] Azizian | Exact generalization guarantees for (regularized) wasserstein distributionally robust models[END_REF] considers an entropic regularization in the objective for generalization, and [START_REF]Regularization for wasserstein distributionally robust optimization[END_REF] studies a general regularization in both constraints and objective. Following the most general case [START_REF]Regularization for wasserstein distributionally robust optimization[END_REF], we consider the robust risk with double regularization

R τ,ϵ ρ,Q (f ) := sup π∈P(Ξ×Ξ), [π] 1 =Q Eπ[c]+τ KL(π∥π 0 )≤ρ E [π] 2 [f ] -ϵ KL(π∥π 0 ) .
with two parameters ϵ > 0 and τ ≥ 0. Introducing the conditional moment of π 0 :

m c = max ξ∈Ξ E ζ∼π 0 (•|ξ) [c(ξ, ζ)], (9)
the generalization guarantee in this setting states as follows.

Theorem 3.2 (Generalization for double regularization). Under Assumption 2.1, there exist α τ,ϵ , β τ,ϵ > 0 such that if

max m c , α τ,ϵ √ n < ρ < ρ τ,ϵ crit 2 - β τ,ϵ √ n ,
then with probability at least 1δ, for all f ∈ F and all Q such that W τ c (P,

Q) ≤ ρ, R τ,ϵ ρ (f ) ≥ E ζ∼Q [f (ζ)] -ϵ KL(π P,Q ∥π 0 ),
where π P,Q is the optimal coupling in (8).

This result is similar to the one of Theorem 3.1, it is also similar to the only other generalization result existing for regularized WDRO [START_REF] Azizian | Exact generalization guarantees for (regularized) wasserstein distributionally robust models[END_REF]. Let us explicit below the main differences. We will discuss in Section 5, the generalization constants such as the critical radius ρ τ,ϵ crit . Unlike Wasserstein robust models (Theorem 3.1), regularization leads to an inexact generalization guarantee, where the regularized empirical robust risk bounds a proxy for the true risk E P [f ]. This is in line with the regularization in optimal transport that induces a bias in the Wasserstein metric, preventing W τ c (P, P ) from being null. Compared to [START_REF] Azizian | Exact generalization guarantees for (regularized) wasserstein distributionally robust models[END_REF], we underline that our result covers also the double regularization case. Moreover, it is valid for an arbitrary π 0 whereas the one of [START_REF] Azizian | Exact generalization guarantees for (regularized) wasserstein distributionally robust models[END_REF] relies on the specific form π 0 involving a Gaussian term. Our result is thus more flexible, allowing to choose conjointly c and π 0 . For example, a Laplace distribution can be chosen when c is the ℓ 1 -norm.

Before moving on to the proof of the generalization results, let us come back to Figure 1. To get this plot, we generated 500 instances of logistic regression problems with synthetic classification data (n = 100, d = 5), for which we solve an associated robust counterpart (with an ℓ 1 -cost c and a Laplace distribution π 0 (•|ξ))

min θ max Eπ[∥•∥ 1 ]≤ρ [π] 1 = Pn E (x,y)∼[π] 2 [log(1 + e y⟨θ,x⟩ )].
This setting is covered by Theorem 3.1 but not by existing results in previous works. Let us check the realizations of the bound (3). Using 10 5 samples, we estimate the true risk E P [f ] for computed optimal solutions f of the 500 instances. On the figure, we report the proportion of instances for which the bound holds and we observe that when ρ increases, the bound does hold true.

Proof strategy

This section presents our strategy to prove the generalization results of Section 3 (Theorems 3.1 and 3.2). The strength of our approach is to use flexible nonsmooth analysis arguments, able to cover the general situation of arbitrary (continuous) cost and objective functions. After an overview of the proof in Section 4.2, we explain the key mechanisms in Sections 4.3 and 4.4 and how they combine with a concentration theorem (Section 4.1) to show the results. In Sections 4.2, 4.3 and 4.4 we consider the standard WDRO setting of Theorem 3.1. The extension to the regularized setting of Theorem 3.2 is then explained in Section 4.5.

Furthermore, in order to focus on the rationale we do not include the proofs in the core of the paper and we refer precisely to corresponding results in the supplementary. We also underline the fundamental results of probability and (nonsmooth) analysis that are used all along. All the statements of this section implicitly assume that our Assumption 2.1 holds.

Uniform concentration inequality

In order to obtain high-probability bounds guarantees, uniform on F, we rely on a standard uniform concentration inequality on a compact metric space. We recall the essential result below, highlighting the two crucial properties on the random variable: (i) boundedness and (ii) global Lipschitzness. We refer to e.g. [START_REF] Boucheron | Concentration Inequalities: A Nonasymptotic Theory of Independence[END_REF] for general discussions, and to Theorem A.2 for one-sided alternatives.

Theorem 4.1 (Uniform concentration). Let (X , dist) be a compact metric space, and X : X × Ξ → R be a measurable function. Assume the following:

(i) There exist a, b ∈ R such that X(x, ξ) ∈ [a, b] for all (x, ξ) ∈ X × Ξ. (ii) X(•, ξ) is L-Lipschitz for all ξ ∈ Ξ.
Then with probability at least 1δ,

sup x∈X E ξ∼ Pn [X(x, ξ)] -E ξ∼P [X(x, ξ)] ≤ M √ n .
M is a problem-dependent constant having the expression2 M = 48 L I(X , dist) + (ba) 2 log(2/δ).

We will apply this concentration result to two families of functions (ψ and ϕ) appearing in our proof; to this end, we will establish the two points (i) and (ii) in Lemma 4.1 and Lemma 4.3 respectively.

Proof 's overview

Compared to the original formulation [START_REF]Regularization for wasserstein distributionally robust optimization[END_REF], the dual representation of WDRO significantly diminishes the problem's degrees of freedom, and is usually the starting point of most studies. Given any distribution Q ∈ P(Ξ), it holds that

R ρ,Q (f ) = inf λ≥0 {λρ + E ξ∼Q [ϕ(λ, f, ξ)]} , (10)
where the dual generator ϕ is a convex function with respect to λ, and Lipschitz continuous with respect to f . For Wasserstein robust models, ϕ has the expression (see e.g. [START_REF] Blanchet | Quantifying distributional model risk via optimal transport[END_REF])

ϕ(λ, f, ξ) = sup ζ∈Ξ {f (ζ) -λc(ξ, ζ)} .
Observe that ϕ is naturally convex in λ, but also nonsmooth. The originality of our approach is to build on this nonsmoothness by using a rationale of nonsmooth analysis. Note also that the convexity of ϕ will be a key property (see e.g. the argument of Figure 3). Let us then outline the main steps to establish Theorem 3.1:

1. We establish in Section 4.4 the existence of a dual lower bound λ low , which holds with high probability and uniformly on F, whenever ρ <

ρ crit 2 -β √ n : R ρ (f ) = inf λ∈[λ low ,∞) λρ + E Pn [ϕ(λ, f )] .
2. As explained in Section 4.3, this leads to

R ρ (f ) ≥ R ρ-α √ n (f ).
3. Finally, if furthermore α √ n < ρ, then we capture the true risk on the right:

R ρ (f ) ≥ E P [f ].

Concentration aspects by dual lower bound

We assume in this section that the empirical dual solution is lower bounded by a value λ low > 0 (with high probability), which means that the infimum in [START_REF] Blanchet | Confidence regions in Wasserstein distributionally robust estimation[END_REF], with Q = P n , may be taken over [λ low , 0) instead of R + . In this case, we can proceed as follows. For a distribution Q, we use the shorthand

E Q [ϕ] = E ξ∼Q [ϕ(λ, f, ξ)]. Then we can write for λ ≥ λ low , λρ + E Pn [ϕ] ≥ λ ρ - E P [ϕ] -E Pn [ϕ] λ + E P [ϕ] ≥ λ(ρ -α n ) + E P [ϕ], (11)
where α n is a formal lower bound on the quotient term (formally defined ( 14)). Taking the infimum over λ ≥ λ low , we obtain

R ρ (f ) ≥ R ρ-αn (f ) ≥ E ξ∼P [f (ξ)], (12)
whenever ρ > α n . This is the desired inequality of Theorem 3.1. Thus, in order to have [START_REF] Blanchet | Statistical limit theorems in distributionally robust optimization[END_REF] with high probability for all f ∈ F, we introduce the function ψ of the variable µ = λ -1 :

ψ(µ,f, ξ) := µϕ(µ -1 ,f, ξ) = sup ζ∈Ξ {µf (ζ)-c(ξ, ζ)} (13)
and we study the gap α n defined by

α n := sup E ξ∼P [ψ(µ, f, ξ)] -E ξ∼ Pn [ψ(µ, f, ξ)] : (µ, f ) ∈ (0, λ -1 low ] × F . (14)
In order to obtain a high probability bound of the form α n ≤ α √ n , boundedness (i) and Lipschitz continuity (ii) of (µ, f ) → ψ(µ, f, ξ) are required by the concentration theorem Theorem 4.1. In the expression [START_REF] Chen | A robust learning approach for regression models based on distributionally robust optimization[END_REF], we remark that the Lipschitz constant of ψ(µ, f, ξ) explodes as µ → ∞, hence we must bound µ = λ -1 above. Thus, if a lower bound λ low holds on λ, ψ satisfies the requirements of Theorem 4.1:

Lemma 4.1. Given λ low > 0, then for almost all ξ ∈ Ξ, (i) For all µ ∈ (0, λ -1 low ] and f ∈ F, ψ(µ, f, ξ) ∈ - ∥F∥ ∞ λ low , ∥F∥ ∞ λ low . (ii) (µ, f ) → ψ(µ, f, ξ) is Lipschitz continuous on (0, λ -1 low ] × F with constant ∥F∥ ∞ + λ -1 low . Proof. See Lemma C.1.2 in the supplementary.

Getting a dual lower bound.

In order to get a dual lower bound, we proceed in two steps:

1. We show the existence of a dual lower bound on the true robust risk. This involves the definition of an inherent maximal radius, which plays the role of a degeneracy threshold.

2. We show that the lower bound on the true robust risk transposes to the empirical robust risk, with high probability and uniformly on F. This is done by expressing a slope condition and applying the concentration inequality Theorem 4.1.

Dual bound on the true risk. In order to obtain a dual lower bound on the true robust risk, it is sufficient for the (right-sided) derivative of λ → λρ + E ξ∼P [ϕ(λ, f, ξ)] to be negative for all f ∈ F on an interval [0, 2λ low ]3 , with λ low > 0. This writes:

ρ ≤ E ξ∼P [-∂ + λ ϕ(λ, f, ξ)], (15)
which implies that ρ has to be small. To obtain the condition [START_REF] Cuturi | Sinkhorn distances: Lightspeed computation of optimal transport[END_REF] uniformly in f ∈ F, we introduce the maximal value of ρ allowed at a given λ ≥ 0 (illustrated in Figure 2):

ρ max (λ) = inf f ∈F E ξ∼P [-∂ + λ ϕ(λ, f, ξ)]. (16)
As illustrated by Figure 2, ρ max reaches its highest value at zero. This is the critical radius,

ρ crit = ρ max (0).
This particular quantity will be discussed in Section 5.2. As a central result of this work, we show that ρ max can be made arbitrarily close to ρ crit as λ → 0 + . Lemma 4.2. lim λ→0 + ρ max (λ) = ρ crit . In particular, there exists λ low > 0 such that for all λ ∈ [0, 2λ low ], for all f ∈ F,

E ξ∼P [∂ + λ ϕ(λ, f, ξ)] ≤ - ρ crit 2 . ( 17
)
Proof. See Lemma D.1 in the supplementary.

This means that the derivative condition ( 15) is satisfied whenever ρ ≤ ρ crit 2 . In order to transpose the inequality [START_REF] Durrett | Probability: Theory and Examples[END_REF] to the empirical problem, precisely to obtain

E ξ∼ Pn [∂ + λ ϕ(λ, f, ξ)] ≤ -ρ crit
2 with high probability, we would like to apply the concentration theorem (Theorem 4.1). Unfortunately, the derivative ∂ + λ ϕ(λ, •, ξ) is discontinuous and doesn't satisfy the Lipschitz condition (ii) from Theorem 4.1. Indeed, its expression is inherently given by the envelope formula (Theorem 2.8.2, [START_REF] Clarke | Optimization and Nonsmooth Analysis[END_REF]) involving an arg max: Dual bound on the empirical risk. We propose a simple way to overcome the limitation highlighted above by relying on the convexity of ϕ. Indeed, given a convex function g over R + , the infimum of g has to occur on an interval [λ low , +∞] if g has a negative slope between λ low and 2λ low (Figure 3):

∂ + λ ϕ(λ, f, ξ) = -min ζ∈Ξ {c(ζ, arg max Ξ {f -λc(ξ, •)}}.
g(2λ low ) -g(λ low ) λ low ≤ 0 =⇒ inf λ≥λ low g(λ) = inf λ≥0 g(λ).
We want this condition satisfied for the empirical Lagrangian function g(λ) = λρ + E Pn [ϕ(λ, f )] with high probability. For convenience, this can be expressed with the slope of E Pn [ϕ(•, f )]:

s(f ) := E Pn [ϕ(2λ low , f )] -E Pn [ϕ(λ low , f )] λ low ≤ -ρ.
(18) This is the condition we aim to obtain. To this end, we proceed by comparing the empirical slope to the true one,

s(f ) := E P [ϕ(2λ low , f )] -E P [ϕ(λ low , f )] λ low .
Indeed, we can show that any function (f, ξ) → ϕ(λ, f, ξ), with λ ∈ R + , satisfies the requirements for the concentration theorem (Theorem 4.1):

Lemma 4.3. For almost all ξ ∈ Ξ we have (i) For all λ ≥ 0 and f ∈ F, ϕ(λ, f, ξ) ∈ [-∥F∥ ∞ , ∥F∥ ∞ ]. (ii) For all λ ≥ 0, f → ϕ(λ, f, ξ) is Lipschitz continuous on F with constant 1. Proof. See Lemma C.1.1.
Consequently, we can apply the concentration theorem twice, on each function ϕ(2λ low , •, •) and ϕ(2λ low , •, •), to obtain that s(f ) approximates s(f ) with high probability, up to a term of the form β

√ n : ∀f ∈ F, s(f ) ≤ s(f ) + β √ n .
On the other hand, s(f

) ≤ E P [∂ + λ ϕ(2λ low , f )] by convexity of ϕ, hence s(f ) ≤ -ρ crit 2 by (17). This means s(f ) ≤ β √ n - ρ crit 2 ,
hence we have the desired condition [START_REF] Fournier | On the rate of convergence in wasserstein distance of the empirical measure[END_REF] when

ρ < ρ crit 2 - β √ n .

Extension to (double) regularization.

The strategy of Section 4.2 is flexible enough to be extended to the regularized setting of Section 3.2. Indeed, the regularized problem also has a dual representation, with a dual generator defined by

ϕ τ,ϵ (λ, f, ξ) = (ϵ + λτ ) log E ζ∼π 0 (•|ξ) e f (ζ)-λc(ξ,ζ) ϵ+λτ
, where ϵ > 0 and τ ≥ 0. Strong duality has been shown in [START_REF]Regularization for wasserstein distributionally robust optimization[END_REF]. We explain in Appendix B, Proposition B.2 how it applies to our general setting. This regularized dual generator leads to smooth counterparts of the key nonsmooth functions ψ, ρ max and ρ crit of the proof. In particular, we can show the regularized version of Lemma 4.2.

Lemma 4.4. lim λ→0 + ρ τ,ϵ max (λ) = ρ τ,ϵ crit . In particular, there exists λ τ,ϵ low > 0 such that for all λ ∈ [0, 2λ τ,ϵ low ], ∀f ∈ F,

E ξ∼P [∂ λ ϕ τ,ϵ (λ, f, ξ)] ≤ - ρ τ,ϵ crit 2 .
Then we obtain Theorem 3.2 by repeating the proof scheme ofSection 4.2. The core results that simultaneously lead to Theorems 3.1 and 3.2 are gathered in Appendix E.1. Due to the smoothness of ρ τ,ϵ max , an expression of λ τ,ϵ low can also be obtained; see Lemma D.2. The key difference brought by regularization is that the Lipschitz property of ψ τ,ϵ is lost when µ → 0. This is an inherent peculiarity of the regularized setting which may occur over the whole family F and the space Ξ; see the example of Proposition F.2. This prevents to use the concentration result without guaranteeing that we can set a lower bound on µ or equivalently an upper-bound on λ. This is the purpose of the next lemma which establishes the existence of such an upper-bound, for any distribution.

R ρ,Q (f ) = inf λ∈[0,λup] {λρ + E ξ∼Q [ϕ(λ, f, ξ)]} .
Proof. See Lemma D.3 in the supplementary.

On the generalization constants

In this section, we put our generalization results into perspective by further discussing the bounds α, β, the critical radius ρ crit appearing in Theorem 3.1, as well as their regularized counterparts of Theorem 3.2.

Sample complexity

We give the complete expressions of α, β, α τ,ϵ and β τ,ϵ in the detailed versions of Theorems 3.1 and 3.2 in Appendix E.2. Here we highlight their dependence from the problem's constants. First, in the setting of Theorem 3.1, α and β grow essentially with the size and the complexity of F. Indeed, we have

α = O I(F, ∥ • ∥ ∞ ) × ∥F∥ ∞ , β = O ∥F∥ ∞ + I(F, ∥ • ∥ ∞ ) . ( 19
)
The Dudley's entropy I(F, ∥ • ∥ ∞ ) quantifies the complexity of F. In the large class of Lipschitz functions, this quantity is exponential in the data dimension. In practice, most machine learning problems involve a Lipschitz parametric family of losses (Section 2) in which case I(F, ∥ • ∥ ∞ ) becomes proportional to √ p, where p is the parameter's dimension (see e.g.

Chapter 5.1 from [START_REF] Wainwright | High-Dimensional Statistics: A Non-Asymptotic Viewpoint[END_REF]).

The constants α and β also grow with 1/λ low and we have α = O (1/λ 2 low ) and β = O (1/λ low ). The constant λ low is implicitly defined and depends on the regularity at 0 of ρ max [START_REF] Donsker | Asymptotic evaluation of certain markov process expectations for large time, i[END_REF], hence it may depend on F, Ξ, c and P .

In the setting of Theorem 3.2, we have similar interpretations. In addition to the conditional moment m c (9), the constants α τ,ϵ and β τ,ϵ also involve the second order conditional moment:

m 2,c = max ξ∈Ξ E ζ∼π 0 (•|ξ) [c(ξ, ζ) 2 ].
They are parameters that may be chosen in practice and related to the reference coupling π 0 .

For instance, if

π 0 (•|ξ) is a truncated Gaussian π 0 (•|ξ) ∝ e -∥•-ξ∥ 2 2σ 2 1 Ξ and c(ξ, ζ) = 1 2 ∥ξ -ζ∥ 2 we have m c ∝ σ 2 and m 2,c ∝ σ 4 .
The coefficients α τ,ϵ and β τ,ϵ exhibit similar relations with λ τ,ϵ low , ∥F∥ ∞ , and I(F, ∥ • ∥ ∞ ) to their counterparts α and β [START_REF] Gao | Finite-sample guarantees for wasserstein distributionally robust optimization: Breaking the curse of dimensionality[END_REF]. Regarding the hyperparameters m c , ϵ, τ and ρ, they should be of comparable order according to the expression of α τ,ϵ (Theorem E.2). Compared to the standard setting, we have an estimate of the lower bound λ τ,ϵ low (Lemma D.2) showing dependence on the loss family: 1/λ τ,ϵ low = O e ∥F ∥∞ ϵ .

The critical radius

In the standard setting, the critical radius has the expression

ρ crit = E ξ∼P min c(ξ, ζ) : ζ ∈ arg max Ξ f .
Assuming ρ crit > 0 excludes losses that remain constant across all samples from the ground truth distribution P . This assumption reasonably aligns with practice and appeared in previous works [START_REF] An | Generalization bounds for (wasserstein) robust optimization[END_REF][START_REF] Azizian | Exact generalization guarantees for (regularized) wasserstein distributionally robust models[END_REF]. For instance, obtaining a predictor that precisely interpolates the ground truth distribution (leading to a loss equal to zero everywhere) is unrealistic. It also defines a threshold to exclude degenerated problems: if ρ > ρ crit , then there exists f ∈ F such that R ρ (f ) = max Ξ f and the problem becomes independent from ρ, see [START_REF] Azizian | Exact generalization guarantees for (regularized) wasserstein distributionally robust models[END_REF].

A similar interpretation can be made in the regularized case with smoothed counterparts. Indeed, we can verify that if ρ > ρ τ,ϵ crit , then there exists f ∈ F such that

R τ,ϵ ρ (f ) = sup π∈P(Ξ×Ξ),[π] 1 =P E [π] 2 [f ] -KL(π∥π 0 ) ,
and the problem becomes independent from ρ, see in particular Proposition F.1 in the supplementary.

Conclusion

In this work, we provide exact generalization guarantees of (regularized) Wasserstein robust models, covering all usual machine learning situations, without restrictive assumptions (on the Wasserstein metric or the class of functions). We achieve these universal results by directly addressing the intrinsic nonsmoothness of robust problems. Our results thus give users freedom when choosing the radius ρ: for all usual situations, it is not necessary to consider specific regimes for ρ in order to expect good generalization from robust models.

Further research can now focus on practical aspects: it would be of premier interest to design efficient practical procedures for selecting ρ, and more generally, scalable algorithms for solving distributionally robust optimization problems.

Supplementary Material

This supplementary gathers recalls, technical results, and examples, as well as, the detailed proof of the results of the main text. The core of our contributions are presented in Appendices D and E. The whole supplementary is organized as follows:

-In Appendix A, we recall some essential mathematical tools. They include a uniform concentration inequality (Theorem A.2), continuity notions in nonsmooth analysis, and the envelope formula to differentiate supremum functions (Theorem A.1).

-In Appendix B, we present strong duality results for WDRO and its regularized version. We explain in particular how the duality theorem from [START_REF]Regularization for wasserstein distributionally robust optimization[END_REF] can be easily adapted to our setting.

-Appendix C contains preliminary computations in view of applying the uniform concentration theorem.

-In Appendix D, we demonstrate the existence of a dual lower bound in the standard and regularized cases. In particular, the proofs involve the maximal radius introduced in Section 4.4.

-By using these preliminary results, in Appendix E, we prove our main generalization theorems (Theorem 3.1 and 3.2). Detailed versions with constants' expressions are proved, Theorem E.1 for the standard setting, and Theorem E.2 for the regularized setting.

-Appendix F contains minor results supporting several remarks found in the article. They include the interpretation of the critical radius in the regularized case, a counter-example justifying the upper-bound in the regularized case and the interpretation of the restrictive compactness assumptions used in [START_REF] Azizian | Exact generalization guarantees for (regularized) wasserstein distributionally robust models[END_REF].

Notations

Throughout the proofs will use the following notations:

In Wasserstein robust models:

• ϕ(λ, f, ξ) = sup ζ∈Ξ {f (ζ) -λc(ξ, ζ)} • ψ(µ, f, ξ) = µϕ(µ -1 , f, ξ)
In Wasserstein robust models with double regularization:

• ϕ τ,ϵ (λ, f, ξ) = (ϵ + λτ ) log E ζ∼π 0 (•|ξ) e f (ζ)-λc(ξ,ζ) ϵ+λτ • ψ τ,ϵ (µ, f, ξ) = µϕ τ,ϵ (µ -1 , f, ξ)
Given a measurable function h : Ξ → R and π ∈ P(Ξ) the Gibbs distribution π h is defined as dπ h ∝ e h dπ.

A Recalls and technical preliminaries

In this part, we use the notation G : X ⇒ Y to denote a function G defined on X and valued in the set of subsets of Y. Semicontinuity notions will be necessary to understand the proof of Lemma D.1. They are regularity notions recurrently arising when manipulating nonsmooth convex functions.

Definition A.1 (Lower and upper semicontinuity, 2.42 in [START_REF] Aliprantis | Infinite Dimensional Analysis[END_REF]). Let (X , dist) be a metric space and let f :

X → R. Then 1. f is called lower semicontinuous if for all x ∈ X , lim inf y→x f (y) ≥ f (x). 2. f is called upper semicontinuous if for all x ∈ X , lim sup y→x f (y) ≤ f (x).
In particular, if f is lower semicontinuous, then -f is upper semicontinuous.

Outer semicontinuity can be seen as the set-valued counterpart of upper semicontinuity: Definition A.2 (Outer semicontinuity). Let X and Y two metric spaces. Then a measurable and compact-valued map G :

X ⇒ Y is called outer semicontinuous at x ∈ X if for all open subset V ⊂ Y containing G(x), there exists a neighborhood U of x which is such that for all w ∈ U , G(w) ⊂ V .
Semicontinuity of maximum and arg max functions are central to the proof of Lemma D.1: Lemma A.1 (17.30 in [START_REF] Aliprantis | Infinite Dimensional Analysis[END_REF]). Let X and Ξ be two metric spaces and let G : X ⇒ Ξ be outer semicontinuous with nonempty compact values, h : Ξ × Ξ → R continuous. Then the function

x → max{h(x, v) : v ∈ G(x)} is upper semicontinuous. In particular, u → min{h(u, v) : v ∈ G(x)} is lower semicon- tinuous.
Lemma A.2 (17.31 in [START_REF] Aliprantis | Infinite Dimensional Analysis[END_REF]). If X is a metric space, (Ξ, d) is a compact metric space, and h : X × Ξ → R is continuous, then the function x → max z∈Ξ h(x, z) is continuous, and the set-valued map x → arg max z∈Ξ h(x, z) is outer semicontinuous.

We recall the definition of gradient for a nonsmooth convex function. This the subdifferential.

Definition A.3 (Subdifferential of convex function). Let ϕ : R m → R be a convex function. Then we call subdifferential of ϕ the set-valued map ∂ϕ : R m ⇒ R m such that for all x ∈ R m and y ∈ R m , ϕ(y) ≥ ϕ(x) + ⟨v, y -x⟩ for all v ∈ ∂ϕ(x).

In particular, we may apply the envelope formula to compute the subdifferential of a maximum function:

Theorem A.1 (Envelope formula, Corollary 1, Chapter 2.8 in [START_REF] Clarke | Optimization and Nonsmooth Analysis[END_REF]). Let (Ξ, d) be a compact metric space and g : R m × Ξ → R such that 1. For all x ∈ R m , g(x, •) is continuous.

For all

ζ ∈ Ξ, g(•, ζ) is convex with subdifferential ∂ x g(•, ζ).
Then G := sup ζ∈Ξ g(•, ζ) is convex on R m , and its subdifferential is given for all x ∈ R m by

∂G(x) := conv{v : v ∈ ∂ x g(x, ζ), ζ ∈ arg max Ξ g(x, •)}.
where conv denotes the convex hull of a set.

A.1 Uniform concentration inequality

We recall a concentration inequality that gives a high probability uniform bound for a family of bounded and Lipschitz functions. This is an extended version of Theorem 4.1 which details the one-sided inequalities (without the absolute value). We refer the reader to [START_REF] Boucheron | Concentration Inequalities: A Nonasymptotic Theory of Independence[END_REF] for a complete reference on concentration inequalities, and Lemma G.2 in [START_REF] Azizian | Exact generalization guarantees for (regularized) wasserstein distributionally robust models[END_REF] for the proof of such a result.

Theorem A.2 (Uniform concentration inequality, Lemma G.2 in [START_REF] Azizian | Exact generalization guarantees for (regularized) wasserstein distributionally robust models[END_REF]). Let (X , dist) be a (totally bounded) separable metric space, P a probability distribution on a probability space Ξ, and P n = 1 n n i=1 δ ξ i with ξ 1 , . . . , ξ n i.i.d.

∼ P . Consider a measurable mapping X : X × Ξ → R and assume that, (i) There is a constant L > 0 such that, for each ξ ∈ Ξ, x → X(x, ξ) is L-Lipschitz. Then, for any δ ∈ (0, 1), we respectively have 1. With probability at least 1δ,

sup x∈X E ξ∼ Pn [X(x, ξ)] -E ξ∼P [X(x, ξ)] ≤ 48LI(X , dist) √ n + (b -a) 2 log 1 δ n .

With probability at least

1 -δ, sup x∈X E ξ∼P [X(x, ξ)] -E ξ∼ Pn [X(x, ξ)] ≤ 48LI(X , dist) √ n + (b -a) 2 log 1 δ n .
The quantity I(X , dist) is defined as follows:

Definition A.4. Given a compact metric space (X , dist), Dudley's entropy integral, I(X , dist), is defined as

I(X , dist) := ∞ 0 log N (t, X , dist)dt
where N (t, X , dist) denotes the t-packing number of X , which is the maximal number of points in X that are at least at a distance t from each other.

We may recall some properties of Dudley's entropy for Cartesian products and segments from R. These are known results, see e.g. [START_REF] Wainwright | High-Dimensional Statistics: A Non-Asymptotic Viewpoint[END_REF] and Lemmas G.3 and G.4 from [START_REF] Azizian | Exact generalization guarantees for (regularized) wasserstein distributionally robust models[END_REF] for proofs.

Lemma A.3 (Dudley's integral estimates).

1. (on Cartesian products) Let (X 1 , dist 1 ) and (X 2 , dist 2 ) be two metric spaces. Consider the product space X := X 1 × X 2 equipped with the distance dist := dist 1 + dist 2 . Then we have the inequality

I(X , dist) ≤ I(X 1 , dist 1 ) + I(X 2 , dist 2 ).
2. (on R) Let c > 0. Then we have the inequality

I([0, c], | • |) ≤ 3c 2 .

B Strong duality

In this section, we recall duality results for WDRO [START_REF] Blanchet | Quantifying distributional model risk via optimal transport[END_REF] and its regularized version [START_REF]Regularization for wasserstein distributionally robust optimization[END_REF]. We recall the Wasserstein distance with cost c for (Q, Q ′ ) ∈ P(Ξ) × P(Ξ):

W c (Q, Q ′ ) = inf E (ξ,ζ)∼π [c(ξ, ζ)] : π ∈ P(Ξ × Ξ), [π] 1 = Q, [π] 2 = Q ′ .
Proposition B.1 (Strong duality, standard WDRO). Under Assumption 2.1, for any Q ∈ P(Ξ) and ρ > 0, max

Wc(Q,Q ′ )≤ρ E ξ∼Q ′ [f (ξ)] = inf λ≥0 {λρ + E ξ∼Q [ϕ(λ, f, ξ)]} .
Proof. This is an application of Theorem 1 from [START_REF] Blanchet | Quantifying distributional model risk via optimal transport[END_REF]. In particular, Assumptions 1 and 2 from [START_REF] Blanchet | Quantifying distributional model risk via optimal transport[END_REF] are satisfied through Assumption 2.1.

Proposition B.2 (Strong duality, regularized WDRO). Under Assumption 2.1, for any

Q ∈ P(Ξ) and ρ > 0, max π∈P(Ξ×Ξ) [π] 1 =Q Eπ[c]+τ KL(π∥π 0 )≤ρ E ξ∼[π] 2 [f (ζ)] -ϵ KL(π∥π 0 ) = inf λ≥0 {λρ + E ξ∼Q [ϕ τ,ϵ (λ, f, ξ)]} .
Proof. This is an application of Theorem 3.1 from [START_REF]Regularization for wasserstein distributionally robust optimization[END_REF], which is a corollary to Theorem 2.1 [START_REF]Regularization for wasserstein distributionally robust optimization[END_REF]. Note that the proofs of Theorems 2.1 and 3.1 from [START_REF]Regularization for wasserstein distributionally robust optimization[END_REF] can be easily extended to a general compact metric space (Ξ, d), without being rewritten entirely. Precisely, only two arguments in their proofs rely on the real-valued setting [START_REF] Rockafellar | Variational Analysis[END_REF] but can be directly extended to a general metric space as follows:

• In the proof of Theorem 2.1 from [START_REF]Regularization for wasserstein distributionally robust optimization[END_REF], one needs to justify

sup {E ξ∼P [φ(ξ, ζ(ξ))] : ζ : Ξ → Ξ measurable} ≥ E ξ∼P sup ζ∈Ξ φ(ξ, ζ) . (20)
To this end, the authors use the notion of normal integrand from [START_REF] Rockafellar | Variational Analysis[END_REF]. Actually, [START_REF] Gao | Wasserstein distributionally robust optimization and variation regularization[END_REF] holds true in a compact metric space: if φ is continuous, then by compactness of Ξ, the set-valued map ξ → arg max ζ∈Ξ φ(ξ, ζ) admits a measurable selection ζ * , by the measurable maximum theorem, see 18.19 in [START_REF] Aliprantis | Infinite Dimensional Analysis[END_REF]. Such a selection ζ * then satisfies φ(ξ, ζ * (ξ)) = sup ζ∈Ξ φ(ξ, ζ) for all ξ ∈ Ξ, hence the result.

• In the proof of Theorem 3.1 from [START_REF]Regularization for wasserstein distributionally robust optimization[END_REF], g φ = sup ζ∈Ξ φ(•, ζ) is actually continuous by Lemma A.2 and the approximation by the infimal convolutions (g φ k ) k∈N need not be done.

Note also that the convexity of Ξ is not required in this proof (although stated in Assumption 1 from [START_REF]Regularization for wasserstein distributionally robust optimization[END_REF]).

C Concentration constants

In this part, we compute several constants in view of applying Theorem A.2 for the main proofs of Appendix E.

C.1 Standard WDRO

The following lemma gathers Lemma 4.1 and Lemma 4.3. We compute bounds (i) and global Lipschitz constants (ii) for ϕ and ψ.

Lemma C.1 (Concentration conditions for WDRO). we have the following:

1. (i) For all λ ≥ 0, f ∈ F and ξ ∈ Ξ, ϕ(λ, f, ξ) ∈ [-∥F∥ ∞ , ∥F∥ ∞ ].
(ii) For all λ ≥ 0 and ξ ∈ Ξ, f → ϕ(λ, f, ξ) is Lipschitz continuous on F with constant 1.

(i) Given

λ low > 0, for all µ ∈ (0, λ -1 low ] and f ∈ F, ψ(µ, f, ξ) ∈ -∥F ∥∞ λ low , ∥F ∥∞ λ low . (ii) For all ξ ∈ Ξ, (µ, f ) → ψ(µ, f, ξ) is Lipschitz continuous on (0, λ -1 low ] with constant ∥F∥ ∞ + λ -1 low . Proof. 1. (i) Let (λ, f, ξ) ∈ R + × F × Ξ. Recall that ϕ(λ, f, ξ) := sup ζ∈Ξ {f (ζ) -λc(ξ, ζ)}.
Since c is nonnegative, we have ϕ(λ, f, ξ) ≤ ∥F∥ ∞ . On the other hand, since c(ξ, ξ) = 0, we also have

ϕ(λ, f, ξ) ≥ f (ξ) ≥ -∥F∥ ∞ . Finally, we have ϕ(λ, f, ξ) ∈ [-∥F∥ ∞ , ∥F∥ ∞ ]. (ii) Let λ ≥ 0, ξ ∈ Ξ and (f, f ′ ) ∈ F × F. For all ζ ∈ Ξ, we have f (ζ) -λc(ξ, ζ) -ϕ(λ, f ′ , ξ) ≤ f (ζ) -λc(ξ, ζ) -(f ′ (ζ) -λc(ξ, ζ)) ≤ f (ζ) -f ′ (ζ) ≤ ∥f -f ′ ∥ ∞ .
Taking the supremum over ζ ∈ Ξ on the left-hand side gives ϕ(λ, f, ξ)-ϕ(λ, f ′ , ξ) ≤ ∥f -f ′ ∥ ∞ .

Permuting the roles of f and

f ′ yields |ϕ(λ, f, ξ) -ϕ(λ, f ′ , ξ)| ≤ ∥f -f ′ ∥ ∞ . We proved that ϕ(λ, •, ξ) is 1-Lipschitz continuous.
2. (i) Now, let λ low > 0 and let (µ, f, ξ) ∈ (0, λ -1 low ] × F × Ξ be arbitrary. Then we have

µϕ(µ -1 , f, ξ) = sup ζ∈Ξ {µf (ζ) -c(ξ, ζ)} ≤ ∥F∥ ∞ λ low .
On the other hand, using c(ξ, ξ) = 0 we obtain

sup ζ∈Ξ {µf (ζ) -c(ξ, ζ)} ≥ µf (ξ) ≥ - ∥F∥ ∞ λ low ,
whence we have µϕ(µ -1 , f, ξ) ∈ -∥F ∥∞ λ low , ∥F ∥∞ λ low . (ii) Toward a proof of 2. (ii), let λ low > 0, and ξ ∈ Ξ and µ ∈ (0,

λ low ]. Remark that µϕ(µ -1 , f, ξ) = sup ζ∈Ξ {µf (ζ) -c(ξ, ζ)}. The function (µ, f ) → µϕ(µ -1 , f, ξ) write as a composition u • v where u(h) := sup ζ∈Ξ {h(ζ) -c(ξ, ζ)} for h ∈ C(Ξ, R), and v(µ, f ) := µf for µ ∈ (0, λ -1 low ]. u is 1-Lipschitz continuous with respect to ∥ • ∥ ∞ . As to v, we can write µf -µ ′ f ′ = µ(f -f ′ ) + f ′ (µ -µ ′ ), whence v is clearly (∥F∥ ∞ + λ -1 low )-Lipschitz continuous on (0, λ -1 low ] × F. By composition, u • v is Lipschitz continuous with constant ∥F∥ ∞ + λ -1 low .

C.2 Regularized WDRO

We will use the following lemma repeatedly:

Lemma C.2 (Lemma G.7 in [START_REF] Azizian | Exact generalization guarantees for (regularized) wasserstein distributionally robust models[END_REF]). Let g : Ξ → R be a measurable bounded function and Q ∈ P(Ξ). Then one has the inequality ζ) ]

log E ζ∼Q e g(ζ) ≤ E ζ∼Q [g(ζ)e g(ζ) ] E ζ∼Q [e g(
.

We prove the regularized version of Lemma C.1:

Lemma C.3 (Concentration conditions for regularized WDRO). Let ξ ∈ Ξ. Then 1. (i) For all λ ≥ 0 and f ∈ F, ϕ τ,ϵ (λ, f, ξ) ∈ [-∥F∥ ∞ -λm c , ∥F∥ ∞ ] .
(ii) For all λ ≥ 0, f → ϕ τ,ϵ (λ, f, ξ) is Lipschitz continuous with constant 1.

(i) Given

λ low > 0, for all µ ∈ [λ -1 up , λ -1 low ] and f ∈ F, ψ τ,ϵ (µ, f, ξ) ∈ -∥F ∥∞ λ low -m c , ∥F ∥∞ λ low . (ii) Given λ up > 0, (µ, f ) → ψ τ,ϵ (µ, f, ξ) is Lipschitz continuous on [λ -1 up , λ -1 low ] × F with constant ∥F∥ ∞ + λ -1 low + λupϵ ϵ+λupτ m c . Proof. 1. (i) Let (λ, f, ξ) ∈ R + × F × Ξ. For all ζ ∈ Ξ, e f (ζ)-λc(ξ,ζ) ϵ+λτ ≤ e ∥F ∥∞
ϵ+λτ . This gives

ϕ τ,ϵ (λ, f, ξ) ≤ (ϵ + λτ ) log E ζ∼π 0 (•|ξ) e ∥F ∥∞ ϵ+λτ = ∥F∥ ∞ . (21)
On the other hand, e

f (ζ)-λc(ξ,ζ) ϵ+λτ ≥ e -∥F ∥∞-λc(ξ,ζ) ϵ+λτ
, which gives

ϕ τ,ϵ (λ, f, ξ) ≥ (ϵ + λτ ) log e -∥F ∥∞ ϵ+λτ E ζ∼π 0 (•|ξ) e -λc(ξ,ζ) ϵ+λτ ≥ -∥F∥ ∞ + (ϵ + λτ ) log E ζ∼π 0 (•|ξ) e -λc(ξ,ζ) ϵ+λτ ≥ -∥F∥ ∞ -λm c , (22)
where for the last inequality we used Jensen's inequality on the convex function s → e -λs ϵ+λτ . Combining ( 21) and [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] gives

ϕ τ,ϵ (λ, f, ξ) ∈ [-∥F∥ ∞ -λm c , ∥F∥ ∞ ].
(ii) Let ξ ∈ Ξ and λ ≥ 0. To compute the Lipschitz constant of f → ϕ τ,ϵ (λ, f, ξ), we compute the derivative of h v : t → ϕ τ,ϵ (λ, f + tv, ξ) where t ∈ R and for an arbitrary direction v ∈ F. We have

h v (t) = (ϵ + λτ ) log E ζ∼π 0 (•|ξ) e f (ζ)+tv(ζ)-λc(ξ,ζ) ϵ+λτ
.

It is easy to verify

that h ′ v (t) = E ζ∼π f +tv-λc(ξ,•) ϵ+λτ 0 (•|ξ) [v(ζ)] , whence |h ′ v (t)| ≤ ∥v∥ ∞ .
This means that ϕ τ,ϵ (λ, •, ξ) has Lipschitz constant 1.

2. (i) Let λ low > 0 and (µ, f, ξ) ∈ (0, λ -1 low ] × F × Ξ. λ. We deduce from ( 21) and ( 22), with λ = µ -1 , that

µϕ τ,ϵ (µ -1 , f, ξ) ∈ - ∥F∥ ∞ λ low -m c , ∥F∥ ∞ λ low . (ii) Now, let ξ ∈ Ξ. Our goal is to compute a Lipschitz constant of (µ, f ) → µϕ τ,ϵ (µ -1 , f, ξ) on [λ -1 up , λ -1 low ] × F. We first compute a Lipschitz constant of h f : µ → µϕ τ,ϵ (µ -1 , f, ξ) = (µϵ + τ ) log E ζ∼π 0 (•|ξ) e µf (ζ)-c(ξ,ζ) µϵ+τ on [λ -1 up , λ -1 low ], for an arbitrary f ∈ F. The derivative of h f is h ′ f (µ) = 1 µϵ + τ E ζ∼π 0 (•|ξ) (ϵc(ξ, ζ) + τ f (ζ))e µf (ζ)-c(ξ,ζ) µϵ+τ E ζ∼π 0 (•|ξ) e µf (ζ)-c(ξ,ζ) µϵ+τ + ϵ log E ζ∼π 0 (•|ξ) e µf (ζ)-c(ξ,ζ) µϵ+τ
, which we write

h ′ f (µ) = E π µf -c(ξ,•) µϵ+τ 0 (•|ξ) ϵc(ξ, ζ) + τ f (ζ) µϵ + τ + ϵ log E ζ∼π 0 (•|ξ) e µf (ζ)-c(ξ,ζ) µϵ+τ . ( 23
)
We bound h ′ f (µ) above. By Lemma C.2 with Q = π 0 (•|ξ) and g = µf -c(ξ,•) µϵ+τ , we have that

ϵ log E ζ∼π 0 (•|ξ) e µf (ζ)-c(ξ,ζ) µϵ+τ ≤ E ζ∼π µf -c(ξ,•) µϵ+τ 0 (•|ξ) ϵµf (ζ) -ϵc(ξ, ζ) µϵ + τ which gives h ′ f (µ) ≤ E ζ∼π µf -c(ξ,•) µϵ+τ 0 [f (ζ)] ≤ ∥F∥ ∞ .
Now we bound h ′ f (µ) below. We start with the first term in [START_REF] Kuhn | Wasserstein distributionally robust optimization: Theory and applications in machine learning[END_REF]. Since c is nonnegative, we clearly have

E π µf -c(ξ,•) µϵ+τ 0 (•|ξ) ϵc(ξ, ζ) + τ f (ζ) µϵ + τ ≥ -τ ∥F∥ ∞ µϵ + τ (24)
As to the second term of ( 23), we have by Jensen's inequality,

ϵ log E ζ∼π 0 (•|ξ) e µf (ζ)-c(ξ,ζ) µϵ+τ ≥ - ϵµ∥F∥ ∞ µϵ + τ - ϵm c µϵ + τ (25)
Combining ( 24) and ( 25)

gives h ′ f (µ) ≥ -∥F∥ ∞ -λupϵmc ϵ+λupτ . Finally, h f has Lipschitz constant ∥F∥ ∞ + λupmc ϵ+λupτ Since ϕ τ,ϵ (µ -1 , •, ξ) has Lipschitz constant 1, then µ ≤ λ -1 low , the function µϕ τ,ϵ (µ -1 , •, ξ) has Lipschitz constant λ -1
low . Now, we can obtain a Lipschitz constant for

h : (µ, f ) → (µϵ + τ ) log E ζ∼π 0 (•|ξ) e µf (ζ)-c(ξ,ζ) µϵ+τ = ψ τ,ϵ (µ, f, ξ). Indeed, for (µ, µ ′ ) ∈ [λ -1 up , λ -1 low ] × [λ -1 up , λ -1 low ] and (f, f ′ ) ∈ F × F, we can write |h(µ, f ) -h(µ ′ , f ′ )| ≤ |h(µ, f ) -h(µ ′ , f )| + |h(µ ′ , f ) -h(µ ′ , f ′ )| ≤ ∥F∥ ∞ + λ up ϵ ϵ + λ up τ |µ -µ ′ | + λ -1 low ∥f -f ′ ∥ ∞ . hence h has Lipschitz constant ∥F∥ ∞ + λ -1 low + λupϵ ϵ+λupτ m c .

D Dual bounds and maximal radius

We establish the existence of a dual lower bound on the true robust risk, for the standard WDRO problem in D.1 and for regularized WDRO in D.2. The proofs involve the maximal radius introduced in Section 4.4. For the regularized case, an estimate of the dual lower bound is provided.

D.1 Standard WDRO: continuity at zero of the maximal radius

For λ ≥ 0, we consider the following quantities:

ρ crit = inf f ∈F E ξ∼P [-∂ + λ ϕ(0, f, ξ)] ρ max (λ) = inf f ∈F E ξ∼P [-∂ + λ ϕ(λ, f, ξ)]. Lemma D.1. lim λ→0 + ρ max (λ) = ρ crit .
Proof. For ξ ∈ Ξ, fλc(ξ, •) is continuous, hence we can apply the envelope formula (Theorem A.1) and the right-sided derivative of ϕ with respect to λ is

∂ + λ ϕ(λ, f, ξ) = -min {c(ξ, ζ) : ζ ∈ arg max Ξ {f -λc(ξ, •)}}.
For convenience, we use the shorthand c * (ξ, K) := min{c(ξ, z), z ∈ K} whenever K ⊂ Ξ is compact. By integration, we obtain

ρ max (λ) = E ξ∼P [c * (ξ, arg max Ξ {f -λc(ξ, •)})]. (26)
In particular,

ρ crit = inf f ∈F E ξ∼P [c * (ξ, arg max Ξ f )].
To prove the result, it is sufficient to show that lim inf k→∞ ρ max (λ k ) ≥ ρ crit for any positive sequence (λ k ) k∈N converging to 0. Indeed, the functions E ξ∼P [ϕ(•, f, ξ)] are convex hence their right-sided derivatives E ξ∼P [-∂ + λ ϕ(•, f, ξ)] are nonincreasing, and ρ max is nonincreasing since it is an infimum over nonincreasing functions. This means lim sup k→∞ ρ max (λ k ) ≤ ρ max (0) for any sequence λ k → 0. Now assume toward a contradiction that there exists ϵ > 0 and a sequence (λ k ) k∈N from R + , such that λ k → 0 as k → ∞, and ρ max (λ k ) ≤ ρ crit -ϵ for all k ∈ N. From the expression of ρ max [START_REF] Li | Fast epigraphical projection-based incremental algorithms for wasserstein distributionally robust support vector machine[END_REF] this means that for each k, there exists

f k such that E ξ∼P [c * (ξ, arg max Ξ f k -λ k c(ξ, •))] ≤ ρ crit -ϵ 2 . By compactness of F with respect to ∥ • ∥ ∞ , we may assume (f k ) k∈N to converge to some f * ∈ F. In particular, for ξ ∈ Ξ, f k , -λ k c(ξ, •) converges to f * as k → ∞.
Let ξ ∈ Ξ be arbitrary. (λ, f ) → arg max Ξ {fλc(ξ, •)} is outer semicontinuous with compact values (Lemma A.2) and c is jointly continuous, hence (λ, f ) → c * (ξ, arg max Ξ {fλc(ξ, •))} is lower semicontinuous, see Lemma A.1. We then have lim inf k→∞ c * (ξ, arg max Ξ {f kλ k c(ξ, •)}) ≥ c * (ξ, arg max Ξ f * ). By integration with respect to ξ ∼ P , we obtain

E ξ∼P [c * (ξ, arg max Ξ f * )] ≤ E ξ∼P [lim inf k→∞ c * (ξ, arg max Ξ {f k -λ k c(ξ, •)})] ≤ lim inf k→∞ E ξ∼P [c * (ξ, arg max Ξ {f k -λ k c(ξ, •)})] ≤ ρ crit - ϵ 2 .
Since,

ρ crit ≤ E ξ∼P [c * (ξ, arg max Ξ f * )], this yields a contradiction. Finally, lim λ→0 + ρ max (λ) = ρ crit .

D.2 Regularized WDRO: Lipschitz maximal radius and upperbound

For λ ≥ 0, we consider the regularized counterparts

ρ τ,ϵ crit = inf f ∈F E ξ∼P [-∂ λ ϕ τ,ϵ (0, f, ξ)], ρ τ,ϵ max (λ) = inf f ∈F E ξ∼P [-∂ λ ϕ τ,ϵ (λ, f, ξ)]. D.2.1 Lipschitz continuity of the maximal radius Lemma D.2. ρ τ,ϵ max : [0, ∞) → R is Lipschitz continuous with constant 2 ϵ τ 2 ϵ 2 ∥F∥ 2 ∞ + m 2,c e ∥F ∥∞ ϵ +min{ mc τ , 2∥F ∥∞mc (ρ-mc)ϵ } .
In particular, if

λ τ,ϵ low := ϵρ τ,ϵ crit 8 τ 2 ϵ 2 ∥F∥ 2 ∞ + m 2,c e ∥F ∥∞ ϵ +min{ mc τ , 2∥F ∥∞mc (ρ-mc)ϵ } , (27)
then ρ max (λ) ≥ ρ crit 2 for all λ ∈ [0, 2λ τ,ϵ low ].
Proof. ϕ τ,ϵ is differentiable with respect to λ and we can verify that its derivative is given by

∂ λ ϕ τ,ϵ (λ, f, ξ) = -E ζ∼π f -λc(ξ,•) ϵ+λτ 0 (•|ξ) τ f (ζ) + ϵc(ξ, ζ) ϵ + λτ + τ log E ζ∼π 0 (•|ξ) e f (ζ)-λc(ξ,ζ) ϵ+λτ .
For f ∈ F and ξ ∈ Ξ, our goal is to compute the Lipschitz constant of λ → ∂ λ ϕ τ,ϵ (λ, f, ξ). The Lipschitz constant of ρ τ,ϵ max will then be obtained by integration and taking the infimum over Lipschitz functions. We compute the appropriate quantities:

1. We compute the derivative with respect to λ of u

1 : (λ, ζ) → -τ f (ζ)+ϵc(ξ,ζ) ϵ+λτ e f (ζ)-λc(ξ,ζ) ϵ+λτ
. This is

∂ λ u 1 (λ, ζ) = τ 2 f (ζ) + ϵτ c(ξ, ζ) (ϵ + λτ ) 2 + (τ f (ζ) + ϵc(ξ, ζ)) 2 (ϵ + λτ ) 3 e f (ζ)-λc(ξ,ζ) ϵ+λτ .
2. We compute the derivative with respect to λ of u

2 : (λ, ζ) → e f (ζ)-λc(ξ,ζ) ϵ+λτ , this is ∂ λ u 2 (λ, ζ) = - τ f (ζ) + ϵc(ξ, ζ) (ϵ + λτ ) 2 e f (ζ)-λc(ξ,ζ) ϵ+λτ .
3. We compute the derivative of

U 3 : λ → τ log E ζ∼π 0 (•|ξ) e f (ζ)-λc(ξ,ζ) ϵ+λτ
. This is

U ′ 3 (λ) = - E ζ∼π 0 (•|ξ) τ 2 f (ζ)+τ ϵc(ξ,ζ) (ϵ+λτ ) 2 e f (ζ)-λc(ξ,ζ) ϵ+λτ 2 E ζ∼π 0 (•|ξ) e f (ζ)-λc(ξ,ζ) ϵ+λτ .
Combining 1, 2 and 3, we are able to compute the derivative of ∂ λ ϕ τ,ϵ :

∂ 2 λ ϕ τ,ϵ (λ, f, ξ) = - E ζ∼π 0 (•|ξ) [u 1 (λ, ζ)]E ζ∼π 0 (•|ξ) [∂ λ u 2 (λ, ζ)] E ζ∼π 0 (•|ξ) [u 2 (λ, ζ)] 2 + U ′ 3 (λ) = E ζ∼π 0 (•|ξ) (τ f (ζ)+ϵc(ξ,ζ)) 2 (ϵ+λτ ) 3 e f (ζ)-λc(ξ,ζ) ϵ+λτ E ζ∼π 0 (•|ξ) e f (ζ)-λc(ξ,ζ) ϵ+λτ - E ζ∼π 0 (•|ξ) τ f (ζ)+ϵc(ξ,ζ) (ϵ+λτ ) 2 e f (ζ)-λc(ξ,ζ) ϵ+λτ E ζ∼π 0 (•|ξ) τ f (ζ)+ϵc(ξ,ζ) ϵ+λτ e f (ζ)-λc(ξ,ζ) ϵ+λτ E ζ∼π 0 (•|ξ) e f (ζ)-λc(ξ,ζ) ϵ+λτ = 1 ϵ + λτ Var ζ∼π f -λc(ξ,•) ϵ+λτ (•|ξ) τ f (ζ) + ϵc(ξ, ζ) ϵ + λτ ,
where Var

ζ∼π f -λc(ξ,•) ϵ+λτ (•|ξ)
is the variance with respect to π

f -λc(ξ,•) ϵ+λτ (•|ξ).
Note that all quantities can be differentiated under the (conditional) expectation since the derivatives with respect to λ involve functions that are continuous on the compact sample space Ξ (they are therefore bounded by a constant), see e.g. Theorem A.5.3 from [START_REF] Durrett | Probability: Theory and Examples[END_REF]. By the property of the variance, we obtain

|∂ 2 λ ϕ τ,ϵ (λ, f, ξ)| ≤ 1 ϵ + λτ E ζ∼π f -λc(ξ,•) ϵ+λτ 0 (•|ξ) τ f (ζ) + ϵc(ξ, ζ) ϵ + λτ 2 ≤ 2 ϵ 3 E ζ∼π f -λc(ξ,•) ϵ+λτ 0 (•|ξ) τ 2 ∥F∥ 2 ∞ + ϵ 2 c(ξ, ζ) 2 . ( 28
)
Now we bound the right-hand side of the last inequality. First, we have

E ζ∼π 0 (•|ξ) c(ξ, ζ) 2 e f (ζ)-λc(ξ,ζ) ϵ+λτ ≤ m 2,c e ∥F ∥∞ ϵ (29)
On the other hand, by Jensen's inequality, we have

E ζ∼π 0 (•|ξ) e f (ζ)-λc(ξ,ζ) ϵ+λτ ≥ e -λmc ϵ+λτ - ∥F ∥∞ ϵ (30)
We have the alternatives λmc ϵ+λτ ≤ λupmc ϵ = 2∥F ∥∞mc (ρ-mc)ϵ in any case, and λmc ϵ+λτ ≤ mc τ whenever τ > 0. This means λmc ϵ+λτ ≤ min mc τ , 2∥F ∥∞mc (ρ-mc)ϵ

. Dividing ( 29) by [START_REF] Redmon | You only look once: Unified, real-time object detection[END_REF], we obtain

E ζ∼π f -λc(ξ,•) ϵ+λτ 0 (•|ξ) [c(ξ, ζ) 2 ] ≤ m 2,c e min{ mc τ , 2∥F ∥∞mc (ρ-mc)ϵ } e 2∥F ∥∞ ϵ
.

Reinjecting this inequality in [START_REF] Peyré | Computational optimal transport: With applications to data science[END_REF] gives

|∂ 2 λ ϕ τ,ϵ (λ, f, ξ)| ≤ 2 ϵ τ 2 ϵ 2 ∥F∥ 2 ∞ + m 2,c e 2∥F ∥∞ ϵ +min{ mc τ , 2∥F ∥∞mc (ρ-mc)ϵ } := L. (31)
This means that for f ∈ F, the function g : (λ, f ) → E ξ∼P [-∂ λ ϕ τ,ϵ (λ, f, ξ)] is L-Lipschitz where L is given by [START_REF] Rockafellar | Variational Analysis[END_REF].

We then show that ρ τ,ϵ max :

= inf f ∈F g(•, f ) is L-Lipschitz continuous. Let (λ, λ ′ ) ∈ R 2 , and let (f k ) k∈N be a sequence from F such that g(λ ′ , f k ) → k→∞ ρ τ,ϵ max (λ ′ ).
Then by definition of ρ τ,ϵ max , we have for all k ∈ N,

ρ τ,ϵ max (λ) -g(λ ′ , f k ) ≤ g(λ, f k ) -g(λ ′ , f k ) ≤ L|λ -λ ′ |. Taking the limit as k → ∞ gives ρ τ,ϵ max (λ) -ρ τ,ϵ max (λ ′ ) ≤ L|λ -λ ′ |. Exchanging the roles of λ and λ ′ gives |ρ τ,ϵ max (λ) -ρ τ,ϵ max (λ ′ )| ≤ L|λ -λ ′ |, hence ρ τ,ϵ max is L-Lipschitz. Now, set 2λ τ,ϵ low := sup {λ ∈ R + : ρ τ,ϵ max (λ) ≥ ρ τ,ϵ crit /2}
. Then either λ τ,ϵ low = ∞ (in which case any value λ τ,ϵ low satisfies the desired property), or by continuity of ρ τ,ϵ max , ρ τ,ϵ max (2λ τ,ϵ low ) = ρ τ,ϵ crit /2 and we have ρ τ,ϵ crit -2Lλ τ,ϵ low ≤ ρ max (2λ τ,ϵ low ) = ρ τ,ϵ crit /2. Finally we thus get [START_REF] Esfahani | Data-driven distributionally robust optimization using the wasserstein metric: performance guarantees and tractable reformulations[END_REF].

D.2.2 Dual upper-bound

The following result allows to bound the dual solution above. This requirement is specific to the regularized setting, see in particular Proposition F.2 for an example.

Lemma D.3 (Upper bound for the regularized problem Lemma 4.5). Assume ρ > m c and let λ up := 2∥F ∥∞ ρ-mc . For all f ∈ F and

Q ∈ P(Ξ), inf λ∈[0,∞) {λρ + E ξ∼Q [ϕ τ,ϵ (λ, f, ξ)]} = inf λ∈[0,λup) {λρ + E ξ∼Q [ϕ τ,ϵ (λ, f, ξ)]} .
Proof. Let ξ ∈ Ξ be arbitrary. Recall that

∂ λ ϕ τ,ϵ (λ, f, ξ) = -E ζ∼π f -λc(ξ,•) ϵ+λτ 0 (•|ξ) τ f (ζ) + ϵc(ξ, ζ) ϵ + λτ + τ log E ζ∼π 0 (•|ξ) e f (ζ)-λc(ξ,ζ) ϵ+λτ .
We bound -∂ λ ϕ τ,ϵ (λ, f, ξ) above, uniformly in f ∈ F and ξ ∈ Ξ. For readability of the proof, we set π0 = π f -λc(ξ,•) ϵ+λτ 0 with a slight abuse of notation. In this case, we have

E ζ∼π 0 (•|ξ) τ f (ζ) + ϵc(ξ, ζ) ϵ + λτ = E ζ∼π 0 (•|ξ) λτ f (ζ) + λϵc(ξ, ζ) -ϵf (ζ) + ϵf (ζ) λ(ϵ + λτ ) = 1 λ E ζ∼π 0 (•|ξ) [f (ζ)] - ϵ λ E ζ∼π 0 (•|ξ) f (ζ) -λc(ξ, ζ) ϵ + λτ ≤ ∥F∥ ∞ λ - ϵ λ log E ζ∼π 0 (•|ξ) e f (ζ)-λc(ξ,ζ) ϵ+λτ ≤ ∥F∥ ∞ λ - ϵ λ(ϵ + λτ ) E ζ∼π 0 (•|ξ) [f (ζ) -λc(ξ, ζ)] ≤ ∥F∥ ∞ λ + ϵ∥F∥ ∞ λ(ϵ + λτ ) + ϵm c ϵ + λτ , (32)
where for the third line, we used Lemma C.2, and for the fourth line, we used Jensen's inequality. On the other hand,

-τ log E ζ∼π 0 (•|ξ) e f (ζ)-λc(ξ,ζ) ϵ+λτ ≤ - τ ϵ + λτ E ζ∼π 0 (•|ξ) [f (ζ) -λc(ξ, ζ)] ≤ λτ λ(ϵ + λτ ) ∥F∥ ∞ + λτ ϵ + λτ m c (33)
Summing [START_REF] Sander | Fast, differentiable and sparse top-k: A convex analysis perspective[END_REF] and [START_REF] Shafieezadeh-Abadeh | Distributionally robust logistic regression[END_REF] gives

-∂ λ ϕ τ,ϵ (λ, f, ξ) ≤ 2∥F∥ ∞ λ + m c ,
whence assuming ρ > m c , and taking λ = λ up := 2∥F ∥∞ ρ-mc , we obtain for all f ∈ F and all ξ ∈ Ξ, 0 ≤ ρ + ∂ λ ϕ τ,ϵ (λ up , f, ξ).

Integrating with respect to a distribution Q ∈ P(Ξ) yields

0 ≤ ρ + E ξ∼Q [∂ λ ϕ τ,ϵ (λ up , f, ξ)],
which is the derivative at λ up of the convex function λ → λρ

+ E ξ∼Q [ϕ τ,ϵ (λ, f, ξ)]. This means inf λ∈[0,∞) {λρ + E ξ∼Q [ϕ τ,ϵ (λ, f, ξ)]} = inf λ∈[0,λup) λρ + E ξ∼ Pn [ϕ τ,ϵ (λ, f, ξ)] .

E Proof of the main results

In this section, we prove the main results of the paper: Theorems 3.1 and 3.2. First, we establish the core concentration results in E.1 that apply to standard and regularized WDRO.

In particular, the slope condition presented in Section 4.4 is used there to establish the dual lower bound with high probability. Then we deduce the main theorems in E.2 and compute the generalization constants.

E.1 Dual bounds with high probability on the empirical problem

All the results of this subsection hold for both standard and regularized cases. The proofs hold as is, replacing ϕ, ψ, ρ crit , ρ max and λ low by ϕ τ,ϵ , ψ τ,ϵ , ρ τ,ϵ crit , ρ τ,ϵ max and λ τ,ϵ low respectively.

For λ ≥ 0, we recall the quantities

ρ crit = inf f ∈F E ξ∼P [-∂ + λ ϕ(0, f, ξ)], ρ max (λ) = inf f ∈F E ξ∼P [-∂ + λ ϕ(λ, f, ξ)].
Problem's constants. Before proving the next results, we introduce several quantities: Proposition E.1 (Dual lower bound in the true problem). Under Assumption 2.1, there exists λ low > 0 such that for all λ ∈ [0, 2λ low ], ρ max (λ) ≥ ρ crit 2 . In particular, for all f ∈ F,

E ξ∼P [∂ + λ ϕ(λ, f, ξ)] ≤ -ρ crit 2 .
Proof. This comes from lim λ→0 + ρ max (λ) = ρ crit . See lemma D.1 for standard WDRO and lemma D.2 for the regularized case.

Let λ low > 0 be given by Proposition E.1. For the next results, we define the following quantities:

• Φ is the length of a segment I such that ϕ(λ, f, ξ) ∈ I for all λ ∈ {λ low , 2λ low }, f ∈ F and ξ ∈ Ξ,

• Ψ is the length of a segment J such that ψ(µ, f, ξ) ∈ J for all µ ∈ (0, λ -1 low ], f ∈ F and ξ ∈ Ξ,

• L ψ and λ up ∈ [0, ∞] are such that ψ(•, •, ξ) is L ψ -Lipschitz on [λ -1 up , λ -1 low ] × F for all ξ ∈ Ξ.
With the above quantities, we can prove the following: Proposition E.2 (Dual lower bound with high probability). Under Assumption 2.1, let λ low be given by Proposition E.1, and

λ up ∈ [λ low , ∞]. If ρ ≤ ρ crit 2 -2C(δ) λ low √ n where C(δ) := 48I(F, ∥ • ∥ ∞ ) + Φ 2 log
E ξ∼ Pn [ϕ(2λ low , f, ξ)] -E ξ∼P [ϕ(2λ low , f, ξ)] ≤ 48I(F, ∥ • ∥ ∞ ) √ n + Φ 2 log 4 δ n (34)
and with probability at least 1 -δ 4 , for all f ∈ F,

E ξ∼P [ϕ(λ low , f, ξ)] -E ξ∼ Pn [ϕ(λ low , f, ξ)] ≤ 48I(F, ∥ • ∥ ∞ ) √ n + Φ 2 log 4 δ n . (35)
We set C(δ) := 48I(F, ∥ • ∥ ∞ ) + Φ 2 log 4 δ . Intersecting the events [START_REF] Shafieezadeh-Abadeh | Regularization via mass transportation[END_REF] and [START_REF] Sinha | Certifying some distributional robustness with principled adversarial training[END_REF], we obtain that with probability 1 -δ 2 , for all f ∈ F,

E ξ∼ Pn [ϕ(2λ low , f, ξ)] -E ξ∼ Pn [ϕ(λ low , f, ξ)] λ low ≤ 1 λ low E ξ∼P [ϕ(2λ low , f, ξ)] -E ξ∼P [ϕ(λ low , f, ξ)] + 2C(δ) √ n ≤ E ξ∼P [∂ + λ ϕ(2λ low , f, ξ)] + 2C(δ) λ low √ n ≤ - ρ crit 2 + 2C(δ) λ low √ n , (36)
where we recall that for λ low > 0, satisfies for all λ ∈ [0, 2λ low ] and all f ∈ F, E ξ∼P [∂ + ϕ(λ, f, ξ)] ≤ -ρ crit 2 . For λ ≥ 0 and f ∈ F, we set g f (λ) = λρ + E ξ∼ Pn [ϕ(λ, f, ξ)]. Then from (36), we deduce with probability at least 1 -δ 2 , for all f ∈ F,

g f (2λ low ) -g f (λ low ) λ low = ρ - ρ crit 2 + 2C(δ) λ low √ n .
This means that if ρ ≤ ρ crit 2 -2C(δ) λ low √ n , then with probability at least 1 -δ 2 , for all f ∈ F,

inf λ∈[0,λup) λρ + E ξ∼ Pn [ϕ(λ, f, ξ)] = inf λ∈[λ low ,λup) λρ + E ξ∼ Pn [ϕ(λ, f, ξ)] .
This implies a generalization bound on the dual problem of (regularized) WDRO:

Proposition E.3 (Generalization bound on the dual problem). Under Assumption 2.1, let λ low > 0 be given by Proposition E.1.

If B(δ) √ n ≤ ρ ≤ ρ crit 2 -2C(δ) λ low √ n where • B(δ) = 48L ψ I(F, ∥ • ∥ ∞ ) + 2 λ low + Ψ 2 log 2 δ , • C(δ) = 48I(F, ∥ • ∥ ∞ ) + Φ 2 log 4 δ ,
then with probability at least 1δ, for all f ∈ F,

inf λ∈[0,λup) λρ + E ξ∼ Pn [ϕ(λ, f, ξ)] ≥ inf λ∈[0,∞) λ ρ - B(δ) √ n + E ξ∼P [ϕ(λ, f, ξ)] .
Proof. We assume λ up > λ low . By Theorem A.2, applied to (µ, f ) → µϕ(µ -1 , f, ξ), we obtain with probability at least 1 -δ 2 ,

α n := sup (µ,f )∈(λ -1 up ,λ -1 low ]×F {E ξ∼P [ψ(µ, f, ξ)] -E ξ∼ Pn [ψ(µ, f, ξ)]} ≤ B(δ) √ n (37)
where B(δ) = 48L ψ I([0, λ -1 low ] × F, dist) + Ψ 2 log 2 δ and dist((µ, f ), (µ ′ , f ′ )) := |µµ ′ | + ∥ff ′ ∥ ∞ . Furthermore, we have the inequality

I([0, λ -1 low ] × F) ≤ I(F, ∥ • ∥ ∞ ) + 1 2λ low (1 + 2 log 2) ≤ I(F, ∥ • ∥ ∞ ) + 2 λ low , see Lemma A.3, hence we may refine B(δ) as B(δ) = 48L ψ I(F, ∥ • ∥ ∞ ) + 2 λ low +Ψ 2 log 2 δ . By Proposition E.2, if ρ ≤ ρ crit 2 -2C(δ) λ low √ n where C(δ) := 48I(F, ∥ • ∥ ∞ ) + Φ 2 log 4 δ , then with probability at least 1 -δ 2 , for all f ∈ F, inf λ∈[0,λup) λρ + E ξ∼ Pn [ϕ(λ, f, ξ)] = inf λ∈[λ low ,λup) λρ + E ξ∼ Pn [ϕ(λ, f, ξ)] . (38)
Finally, combining [START_REF] Wang | Sinkhorn distributionally robust optimization[END_REF] and [START_REF] Wainwright | High-Dimensional Statistics: A Non-Asymptotic Viewpoint[END_REF], and if

B(δ) √ n ≤ ρ ≤ ρ crit 2 - 2C(δ) λ low √ n ,
we can write with probability 1δ, for all f ∈ F,

inf λ∈[0,λup) λρ + E ξ∼ Pn [ϕ(λ, f, ξ)] = inf λ∈[λ low ,λup) λρ + E ξ∼ Pn [ϕ(λ, f, ξ)] ≥ inf λ∈[λ low ,λup) λρ + E ξ∼P [ϕ(λ, f, ξ)] -λ E ξ∼P [ϕ(λ, f, ξ)] -E ξ∼ Pn [ϕ(λ, f, ξ)] λ ≥ inf λ∈[λ low ,λup) {λρ + E ξ∼P [ϕ(λ, f, ξ)] -λα n } ≥ inf λ∈[λ low ,λup) λ ρ - B(δ) √ n + E ξ∼P [ϕ(λ, f, ξ)] ≥ inf λ∈[0,∞) λ ρ - B(δ) √ n + E ξ∼P [ϕ(λ, f, ξ)] ,
If λ up ≤ λ low , this means, by convexity of the inner function,

inf λ∈[0,λup) λρ + E ξ∼ Pn [ϕ(λ, f, ξ)] = λ low ρ + E ξ∼ Pn [ϕ(λ low , f, ξ)] ≥ λ low (ρ -α ′ n ) + E ξ∼P [ϕ(λ low , f, ξ)] ≥ inf λ∈[0,∞) λ ρ - B(δ) √ n + E ξ∼P [ϕ(λ, f, ξ)] ,
where we refined

α n into α ′ n = sup f ∈F E ξ∼P [ψ(λ -1 low , f, ξ)] -E ξ∼ Pn [ψ(λ -1 low , f, ξ)] .

E.2 Proof of the main results

We are now ready to prove our main results.

The following is an extended version of the generalization result in standard WDRO (Theorem 3.1). Note that the extended bound (39) involves a control of R ρ-α √ n (f ), which means that R ρ (f ) also generalize well against for distribution shifts.

Theorem E.1 (Generalization guarantee, standard WDRO). Under Assumption 2.1, there exists

λ low > 0 such that if α √ n < ρ < ρ crit 2 - β √ n ,
where

• α = 48 ∥F∥ ∞ + 1 λ low I(F, ∥ • ∥ ∞ ) + 2 λ low + 2∥F ∥∞ λ low 2 log 2 δ • β = 96I(F ,∥•∥∞) λ low + 4∥F ∥∞ λ low 2 log 4 δ , then with probability at least 1 -δ, for all f ∈ F, R ρ (f ) ≥ R ρ-α √ n (f ) ≥ E ξ∼P [f (ζ)]. (39)
Proof. Under Assumption 2.1, let λ low be given by Proposition E.2. Our goal is to apply Proposition E.3 in the standard WDRO case and to compute its constants thanks to Lemma C.1. By Lemma C.1, we have the following constants:

• Φ = 2∥F∥ ∞ , • Ψ = 2∥F ∥∞ λ low , • λ up = ∞, and L ψ = ∥F∥ ∞ + λ -1 low .
α corresponds to B(δ) in Proposition E.3 and β corresponds 2C(δ) λ low , whence we obtain

• α = 48 ∥F∥ ∞ + 1 λ low I(F, ∥ • ∥ ∞ ) + 2 λ low + 2∥F ∥∞ λ low 2 log 2 δ • β = 2 λ low 48I(F, ∥ • ∥ ∞ ) + 2∥F∥ ∞ 2 log 4 δ = 96I(F ,∥•∥∞) λ low + 4∥F ∥∞ λ low 2 log 4 δ .
By strong duality, Proposition B.1, R ϱ (f ) and R ϱ (f ) admit the representations

R ϱ (f ) = inf λ∈[0,∞) {λϱ + E ξ∼P [ϕ(λ, f, ξ)]} R ϱ (f ) = inf λ∈[0,∞) λϱ + E ξ∼ Pn [ϕ(λ, f, ξ)] ,
for any ϱ > 0 and f ∈ F.

By Proposition E.3, if α √ n < ρ < ρ crit 2 -β √ n , then with probability at least 1 -δ, we have for all f ∈ F, R ρ (f ) ≥ R ρ-α √ n (f ), hence the result.
The next result corresponds to the generalization guarantee for WDRO with double regularization, Theorem 3.2: Theorem E.2 (Generalization guarantee, regularized WDRO). Under Assumption 2.1, there exists λ low > 0 such that if

max m c , α τ,ϵ √ n < ρ < ρ τ,ϵ crit 2 - β τ,ϵ √ n where • α τ,ϵ = 48 ∥F∥ ∞ + 1 λ τ,ϵ low + 2∥F ∥∞mcϵ ϵ(ρ-mc)+2τ ∥F ∥∞ I(F, ∥ • ∥ ∞ ) + 2 λ τ,ϵ low + 2∥F ∥∞ λ τ,ϵ low + m c 2 log 2 δ • β τ,ϵ = 96I(F ,∥•∥∞) λ τ,ϵ low + 4 ∥F ∥∞ λ τ,ϵ low + m c 2 log 4 δ ,
then with probability at least 1δ, for all f ∈ F,

R τ,ϵ ρ (f ) ≥ R τ,ϵ ρ-α τ,ϵ √ n (f ) ≥ E ζ∼Q [f (ζ)] -ϵ KL(π P,Q ∥π 0 ) whenever W τ c (P, Q) ≤ ρ. Proof. Under Assumption 2.1, let λ τ,ϵ
low > 0 be given by P roposition E.2, and assume ρ > m c . As for standard WDRO, our goal is to apply Proposition E.3 and to compute its constants thanks to Lemma C.3. By Lemma C.3, and taking λ up = 2∥F ∥∞ ρ-mc , we have the following constants:

• Φ = ∥F∥ ∞ -(-∥F∥ ∞ -2λ τ,ϵ low m c ) = 2(∥F∥ ∞ + λ τ,ϵ low m c ) • Ψ = 2∥F ∥∞ λ τ,ϵ low + m c • λ up = 2∥F ∥∞ ρ-mc and L ψ = ∥F∥ ∞ + 1 λ τ,ϵ low + 2∥F ∥∞mcϵ ϵ(ρ-mc)+2τ ∥F ∥∞ .
In Proposition E.3, α τ,ϵ corresponds to B(δ) and β τ,ϵ corresponds to 2C(δ) λ τ,ϵ low . In this case, we have:

• α τ,ϵ = 48 ∥F∥ ∞ + 1 λ τ,ϵ low + 2∥F ∥∞mcϵ ϵ(ρ-mc)+2τ ∥F ∥∞ I(F, ∥ • ∥ ∞ ) + 2 λ τ,ϵ low + 2∥F ∥∞ λ τ,ϵ low + m c 2 log 2 δ • β τ,ϵ = 2 λ τ,ϵ low 48I(F, ∥ • ∥ ∞ ) + 2(∥F∥ ∞ + λ τ,ϵ low m c ) 2 log 4 δ = 96I(F ,∥•∥∞) λ τ,ϵ low + 4 ∥F ∥∞ λ τ,ϵ low + m c 2 log 4 δ .
By strong duality, Proposition B.2, and by the dual upper-bound, Lemma D

.3, R τ,ϵ ϱ (f ) and R τ,ϵ ϱ (f ) admit the representations R τ,ϵ ϱ (f ) = inf λ∈[0,λup) {λϱ + E ξ∼P [ϕ τ,ϵ (λ, f, ξ)]} R τ,ϵ ϱ (f ) = inf λ∈[0,λup) λϱ + E ξ∼ Pn [ϕ τ,ϵ (λ, f, ξ)] ,
for any ϱ > 0 and

f ∈ F. Recall that ρ > m c . If furthermore α τ,ϵ √ n < ρ < ρ τ,ϵ crit 2 -β τ,ϵ
√ n , then with probability at least 1δ, we have for all

f ∈ F, R τ,ϵ ρ (f ) ≥ R τ,ϵ ρ-α √ n
(f ) by Proposition E.3 hence we obtain the first inequality. Now, toward the second inequality, let

Q ∈ P(Ξ) such that W τ c (P, Q) ≤ ρ. Let π P,Q ∈ P(Ξ × Ξ) satisfying [π P,Q ] 1 = P , [π P,Q ] 2 = Q and E (ξ,ζ)∼π P,Q [c(ξ, ζ)] + τ KL(π P,Q ∥π 0 ) = W τ c (P, Q). We finally obtain for all f ∈ F, R ρ-α √ n (f ) ≥ E ζ∼Q [f (ζ)] -ϵ KL(π P,Q ∥π 0 ).

F Side remarks

This part contains results supporting various remarks made in the main text.

F.1 Interpretation of the critical radius in the regularized case.

The following result gives an interpretation of the critical radius ρ τ,ϵ crit in regularized WDRO appearing in Theorem 3.2. We show that when the radius ρ is larger than this value, then some robust losses become degenerated. Precisely, they become independent of ρ and are equal to a regularized version of the worst-case loss max Ξ f . Proposition F.1. Assume ρ > ρ τ,ϵ crit . Then there exists

f ∈ F such that R τ,ϵ ρ (f ) = sup π∈P(Ξ×Ξ) [π] 1 =P E ζ∼[π] 2 [f (ζ)] -ϵ KL(π∥π 0 ) .
Proof. In the regularized case, we can verify that the critical radius has the expression

ρ τ,ϵ crit = inf f ∈F E ξ∼P E ζ∼π f /ϵ 0 (•|ξ) τ ϵ f (ζ) + c(ξ, ζ) -τ log E ζ∼π 0 (•|ξ) e f (ζ) ϵ , (40)

F.2 Necessity of the dual upper-bound

We exhibit an example where the function µ → ψ τ,ϵ (µ, f, ξ) is not Lipschitz as µ → 0. This justifies the necessity of bounding the dual solution above in the regularized case, as done in Lemma D.3.

Proposition F.2. Consider τ = 0, ϵ > 0, Ξ = [0, 1], c(ξ, ζ) = |ξ -ζ| and assume that the reference distribution is a truncated Laplace π 0 (dζ|ξ) ∝ e -|ξ-ζ| 1 [0,1] (ζ)dζ. Assume furthermore F is a family of functions from [0, 1] to R which satisfies e -2∥F ∥∞ ϵ ≥ ϵ. Then for almost all ξ ∈ [0, 1] and all f ∈ F, µ → ψ τ,ϵ (µ, f, ξ) is not Lipschitz at 0 + . Proof. Let ξ ∈ (0, 1) and f ∈ F. The expression of the derivative of ψ 0,ϵ with respect to µ is given by ( 23):

∂ µ ψ 0,ϵ (µ, f, ξ) = E
We then have the following:

• 2e -ξ µϵe -(1-ξ) µϵ converges to 2 as µ → 0,

• For all u ∈ R, 1 [ ξ-1 µϵ , ξ µϵ ] (u)e -|u| φ(ξ + µϵu)du converges to e -|u| φ(ξ) as µ → 0, hence its integral with respect to u converges to 2φ(ξ) by dominated convergence theorem. F.3 On the compactness condition, Assumption 5.1 from [START_REF] Azizian | Exact generalization guarantees for (regularized) wasserstein distributionally robust models[END_REF] We justify the importance of relaxing Assumption 5.1 from [START_REF] Azizian | Exact generalization guarantees for (regularized) wasserstein distributionally robust models[END_REF] which corresponds to compactness of F with respect to the distance D F (f, g) := ∥f -g∥ ∞ + d H (arg max Ξ f, arg max Ξ g). We show that this condition is actually equivalent to assuming continuity on f → arg max f , which is a strong condition and difficult to verify in practice. Proof. We prove (⇒). Assume (F, D F ) is compact. Let f ∈ F, and let (g k ) k∈N be an arbitrary sequence from F such that g k converges to f for ∥ • ∥ ∞ . We want to show that arg max Ξ g k converges to arg max Ξ f for d H , proving the continuity of the arg max map. By compactness of (F, D F ), (g k ) k∈N admits accumulation points for D F . Let h be any one of them. We may extract a subsequence from (g k ) k∈N converging to h, say g n k → k→∞ h ∈ F. In particular, g n k converges to h for ∥ • ∥ ∞ . We necessarily have h = f by definition of the sequence (g k ) k∈N . It means that (g k ) k∈N admits only one possible accumulation point for D F , which is f . This implies g k converges to f for D F , hence arg max Ξ g k converges to arg max Ξ f . Now, we prove (⇐). Let (f k ) k∈N be a sequence from F. By compactness of (F, ∥ • ∥ ∞ ), we may extract a converging subsequence f n k → k→∞ f for ∥ • ∥ ∞ . Assuming f → arg max Ξ f is continuous gives that arg max Ξ f n k converges to arg max Ξ f , which is the desired result.

Figure 1 :

 1 Figure 1: Probability of the generalization bound (3) to hold, estimated from 500 logistic regression instances and their ℓ 1 -robust counterparts (see at the end of Section 3). For large ρ, the bound always holds, whereas it does not for small ρ. Our aim is to quantify this phenomenon, which is not explained by existing results.

Figure 2 :

 2 Figure 2: A central object of our analysis: the maximal radius ρ max , defined from the lower envelope of derivatives of ϕ.

Figure 3 :

 3 Figure 3: Bounding from below the empirical dual solution λ * expresses as a slope condition (thanks to convexity of the objective).

Lemma 4 . 5 .

 45 Let Q ∈ P(Ξ) and λ up := 2∥F ∥∞ ρ-mc . Then for all f ∈ F,

(

  ii) X(•, ξ) almost surely belongs to [a, b].

  see for instance the proof of Lemma D.2. Let f ∈ F be arbitrary. Consider a coupling π * ∈ P(Ξ × Ξ) such that [π * ] 1 = P and π * (•|ξ) = π f ϵ 0 (•|ξ) for almost all ξ ∈ Ξ. We first verify that for a good choice of f , it is included in the uncertainty set defining R τ,ϵ ρ (f ). We compute KL(π * ∥π 0 ). Below, we set Z(ξ):= E ζ∼π 0 (•|ξ) e f (ζ) ϵ . KL(π * ∥π 0 ) = E ξ∼P E ϵ log E ζ∼π 0 (•|ξ) e f (ζ) ϵ = E (ξ,ζ)∼π * f (ζ) ϵ -E ξ∼P log E ζ∼π 0 (•|ξ) e f (ζ) ϵ . (41)This leads toE (ξ,ζ)∼π * [c(ξ, ζ)] + τ KL(π * ∥π 0 ) = E ξ∼P E ζ∼π f /ϵ 0 (•|ξ) τ ϵ f (ζ) + c(ξ, ζ)τ log E ζ∼π 0 (•|ξ) e f (ζ) ϵwhich is the term in the infimum (40). Since f was chosen arbitrary, this means that if ρ > ρ τ,ϵ crit , then there exists f ∈ F such that the coupling π * defined above (depending on f ) satisfiesE (ξ,ζ)∼π * [c(ξ, ζ)] + τ KL(π * ∥π 0 ) ≤ ρ, and we obtain R τ,ϵ ρ (f ) ≥ E ζ∼[π * ] 2 [f (ζ)]ϵ KL(π * ∥π 0 ). On the other hand by the computation (41), we haveR τ,ϵ ρ (f ) ≥ E ζ∼[π * ] 2 [f (ζ)]ϵ KL(π * ∥π 0 ) = ϵE ξ∼P log E ζ∼π 0 (•|ξ) e f (ζ) ϵ . (42)By Donsker-Varadhan variational formula[START_REF] Donsker | Asymptotic evaluation of certain markov process expectations for large time, i[END_REF], for almost all ξ ∈ Ξ, we havelog E ζ∼π 0 (•|ξ) e f (ζ) ϵ = sup ν∈P(Ξ) {E ζ∼ν [f (ζ)/ϵ] -KL(ν∥π 0 (•|ξ))} .(43)Reinjecting (43) in (42) givesR τ,ϵ ρ (f ) ≥ ϵE ξ∼P sup ν∈P(Ξ) {E ζ∼ν [f (ζ)/ϵ] -KL(ν∥π 0 (•|ξ))} ≥ sup π∈P(Ξ×Ξ) [π] 1 =P E ξ∼P E ζ∼π(•|ξ) [f (ζ)]ϵ KL(π(•|ξ)∥π 0 (•|ξ)) = sup π∈P(Ξ×Ξ) [π] 1 =P E ζ∼[π] 2 [f (ζ)]ϵ KL(π∥π 0 ) ,where we used the chain rule for KL divergence (see e.g. Theorem 2.15 in [29]): KL(π∥π 0 ) = E ξ∼P [KL(π(•|ξ)∥π 0 (•|ξ))] + KL([π] 1 ∥[π 0 ] 1 ) ≥ E ξ∼P [KL(π(•|ξ)∥π 0 (•|ξ))]. Since we clearly have R τ,ϵ ρ (f ) ≤ sup π∈P(Ξ×Ξ) [π] 1 =P E ζ∼[π] 2 [f (ζ)]ϵ KL(π∥π 0 ) , this yields the result.

- 1 0e

 1 ζ∼π µf -c(ξ,•) µϵ 0 (•|ξ) ϵc(ξ, ζ) µϵ + ϵ log E ζ∼π 0 (•|ξ) e µf (ζ)-c(ξ,ζ) µϵ.In particular, it satisfies∂ µ ψ 0,ϵ (µ, f, ξ) ≤ e 2∥F ∥∞ ϵ E ζ∼π -c(ξ,•) µϵ 0 (•|ξ) c(ξ, ζ) µ + ϵ log E ζ∼π 0 (•|ξ) e -c(ξ,ζ) µϵ + ∥F∥ ∞ .(44)On the other hand, by Donsker-Varadhan formula[START_REF] Donsker | Asymptotic evaluation of certain markov process expectations for large time, i[END_REF], we can writelog E ζ∼π 0 (•|ξ) e ) π 0 (•|ξ) .Reinjecting this in (44) and using e -2∥F ∥∞ ϵ ≥ ϵ gives∂ µ ψ τ,ϵ (µ, f, ξ) ≤ ∥F∥ ∞ -KL π ) π 0 (•|ξ) .Consequently, to prove non-Lipschitzness of ψ 0,ϵ (•, f, ξ) at 0, we show thatKL π -c(ξ,•) µϵ 0 (•|ξ) π 0 (•|ξ) → ∞as µ → 0. We show that π -|ξ-•| µϵ 0 (•|ξ) converges in law to δ ξ . Let φ : R → R be of class C ∞ with compact support. With the change of variable u ← ξ-ζ µϵ , we have -|ξ-ζ| µϵ φ(ζ)dζ = µϵ R 1 [ ξ-1 µϵ , ξ µϵ ] (u)e -|u| φ(ξ + µϵu)du. Also, we easily verify that µϵ 0 [φ(ζ)] = R 1 [ ξ-1 µϵ , ξ µϵ ] (u)e -|u| φ(ξ + µϵu)du 2e -ξ µϵe -(1-ξ) µϵ.

  ζ)] → φ(ξ). This means that π -|ξ-•| µϵ 0 (•|ξ) converges in law to δ ξ . We have KL(δ ξ ∥π 0 (•|ξ)) = ∞, hence by lower semicontinuity of the KL-divergence for the convergence in law (or weak convergence), see e.g. Theorem 4.9 from [29], we obtain KL π -c(ξ,•) µϵ 0 (•|ξ) π 0 (•|ξ) -→ µ→0∞. This means that ψ 0,ϵ (•, f, ξ) is not Lipschitz near 0.

Proposition F. 3 .

 3 For (f, g) ∈ F × F, define D F (f, g) := ∥f -g∥ ∞ + d H (arg max Ξ f, arg max Ξ g)where d H is the Hausdorff distance on the set of compact subsets of Ξ, K(Ξ) . Assume (F, ∥ • ∥ ∞ ) is compact. Then we have the equivalence(F, D F ) is compact ⇐⇒ f → arg max Ξ f is continuous from (F, ∥ • ∥ ∞ ) to (K(Ξ), d H ).

  Proof. Let λ ∈ {λ low , 2λ low }. For ξ ∈ Ξ, the function f → ϕ(λ, f, ξ) is Lipschitz with constant 1, see Lemma C.1 and Lemma C.3. Then we can apply Theorem A.2, to have with probability at least 1 -δ 4 , for all f ∈ F,

		4 δ , then with probability 1 -δ 2 , for all f ∈ F,
	inf λ∈[0,λup)	λρ + E ξ∼ Pn [ϕ(, λ, f, ξ)] =	inf λ∈[λ low ,λup)	λρ + E ξ∼ Pn [ϕ(λ, f, ξ)] .

The constant I(X , dist) is the standard Dudley's entropy integral measuring the complexity of the space X , that we further discuss in Definition A.4.

Although the factor 2 may not seem necessary at the moment, its role will become clearer in Section

4.4

Acknowledgements

This research was partially supported by MIAI@Grenoble Alpes (ANR-19-P3IA-0003).