Universal generalization guarantees for Wasserstein distributionally robust models
Authors: Tam Le
Jerome Malick
Venue: ICLR 2025 Spotlight (2025)
Keywords: generalization guarantees
optimal transport
distributionally robust optimization
nonsmooth analysis
Primary area: optimization
TL;DR: Exact generalization guarantees for Wasserstein distributionally robust models with dimension-free sample rates.

Abstract: 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 generalization guarantees of robust models based on the Wasserstein distance have generalization guarantees that do not suffer from the curse of dimensionality. However, these results are either approximate, obtained in specific cases, or based on assumptions difficult to verify in practice. In contrast, we establish exact generalization guarantees that cover a wide range of cases, with arbitrary transport costs and parametric loss functions, including deep learning objectives with nonsmooth activations. We complete our analysis with an excess bound on the robust objective and an extension to Wasserstein robust models with entropic regularizations.

Published as a conference paper at ICLR 2025
UNIVERSAL GENERALIZATION GUARANTEES FOR WASSERSTEIN DISTRIBUTIONALLY ROBUST MODELS
Tam Le Jérôme Malick
Univ. Grenoble Alpes, CNRS, Grenoble INP, LJK
Grenoble, 38000, France
ABSTRACT
Distributionally robust optimization has emerged as an attractive way to train ro- bust machine learning models, capturing data uncertainty and distribution shifts. Recent statistical analyses have proved that generalization guarantees of robust models based on the Wasserstein distance have generalization guarantees that do not suffer from the curse dimensionality. However, these results are either ap- proximate, obtained in specific cases, or based assumptions difficult to verify in practice. In contrast, we establish exact generalization guarantees that cover a wide range of cases, with arbitrary transport costs and parametric loss functions, including deep learning objectives with nonsmooth activations. We complete our analysis with an excess bound on the robust objective and an extension Wasser- stein robust models with entropic regularizations.
INTRODUCTION
1.1 WASSERSTEIN ROBUSTNESS; MODELS AND GENERALIZATION
Machine learning models are challenged in practice by many obstacles, such as biases in data, adver- sarial attacks, 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 Kuhn et al. 2019 Blanchet et 2021a).
More specifically, the approach consists in minimizing the worst-risk among all distributions in neighborhood the empirical data distribution. A natural way (Mohajerin Esfahani & Kuhn 2018) to define such neighborhood is to use the optimal transport distance, called the Wasserstein distance (Cédric & Villani 2009). Between two suitable distributions Q and Q' on a sample space E, we may define the optimal transport cost among all coupling on E E having Q and Q' as marginals:
We(Q,Q')
inf REP(EXE) m)==
E (tc.))=/c(EEC)))
where x R is nen-negative cost function. When c is the power p > 1 of a distance E, this corresponds to the p- p-Wasserstein distance. For class of loss functions F. the Wasserstein distributionally robust counterpart of the standard empirical risk minimization (ERM) then writes
min JEF
sup D.P.E)... Be-o(f(E))
(2)
for a chosen radius p of the Wasserstein ball centered at the empirical data distribution, denoted P This procedure is often referred to as Wasserstein Distributionally Robust Optimization (WDRO). In the degenerate case p O, we have Q P., and (2) boils down to ERM. If > 0. the training captures data uncertainty and provides more resilient learning models: see e.g. the discussions and
illustrations in Shafieczadeh--lee Abadeh et al. (2015): Sinha et al. (2018); Zhao & Guan (2018) ; Kwon
et al. 2020); Li et al. 2020); Taskesen et al. (202 ): Gao et al. (2022) Arrigo et al. 2022) Belbasi
al.
2023

---

Published as a conference paper at ICLR 2025
To support theoretically the modeling versatility and the practical success of these robust models, some statistical guarantees have been proposed in the literature. For population distribution P. ii.d. samples Ei,..., En drawn from P. and the associated empirical distribution P.. := - òg,- the best concentration results for the Wasserstein distance (Fournier & Guillin 2015) gives that the radius p is large enough, then the Wasserstein ball around P., contains the true distribution P with high probability, which in turn gives directly (see Mohajerin Esfahani & Kuhn (2018) generalization bound of the form
sup (P..
E Re-ol((E))
(e-r([(())
This bound is exact in the sense that it introduces no approximation term between the true risk and the robust risk, unlike standard generalization bounds of ERM [Vapmik ( Bartlett & Mendel- son (006)). This property (3) is specific WDRO and highlights its potential give more resilient models: : the left-hand-side, which is the quantity that we compute from data and optimize by train- ing, provides a control on the right-hand-sice which is the idealistic population risk.
In order to obtain such an attractive guarantee, Mohajerin Esfahani & Kuhn (2018) needs to take a large radius p. Indeed, the direct application of concentration results of Fournier Guilli (2013) requires radius scaling as O(1/ná), where d is the data dimension. Due to the exponential depen- dence, in high dimension, this value is almost constant with respect to hence suggesting that the exact bound (3) can hold only for conservative values p.
Recent works have proposed various statistical guarantees for WDRO by establishing generalization bounds that do not suffer from the above curse of the dimension; we further discuss them in the related work section in section 1.3 These results generally feature radius scaling O(1/ vn), which is the standard rate in ERM generalization bounds. Yet, no existing result on robust models precisely retrieve the original exact bound (3) with the 1/vnn rate, in general setting.
1.2 CONTRIBUTIONS AND OUTLINE
In this paper, we establish exact generalization guarantees of the form (3) under general assumptions that cover many machine learning situations. Our results apply to any kind of data lying in metric space (e.g. classification and regression tasks with mixed features) and general classes of continuous loss functions (e.g. from standard regression tasks to deep learning models) as long as standard compactness conditions are satisfied. For instance, results cover nonsmooth objectives that are particularly present in deep learning with the use of ReLU activation function, moxx-no operator, or optimization layers.
To avoid using concentration results of Fournier & Guillin (013)) involving a radius scaling as 0(1/2²), we develop a novel optimization-based proof, directly tackling the nonsmoothness of the robust objective function (2) with tools from variational analysis (Clarke) 1990, Rockafellar & Wets 1998 Aliprantis & Border 2006). We thus obtain general results with p scaling as O(1/ /n), capturing all possible nonsmoothness and coinciding with previous study for robust linear models
Shatieezadch-Abadeee et al. 2019).
Moreover, our approach is systematic enough to (i) provide estimates of the excess errors quantifying by how much the robust objective may exceed the true risk, and (ii) extend to the recent versions of Wasserstein/Sinkhenn
distributionally robust problems that involve (double) regularizations (Azizian et al. 2023b Wang et al.) 2023). We thus complete the only existing analysis of regularized WDRO (Azizian al. 2023a) by obtaining generalization results for double regularization (Azizian et al.) 2023b) when dealing with arbitrary costs and nonsmooth objectives.
The paper is structured as follows. First, Section introduesss and illustrates the setting of this work. Then Section 3 presents and discusses the main results: the generalization guarantees (Theorem 3.1 and Theorem B.2). the excess risk bounds (Proposition 3.1 and Proposition 3.3 and the specific case of linear models (Section 3.2) This section ends with Section 3.4 discussing the limitations of our study and potential extensions. Finally, Section 4 highlights our proof techniques, combining classical concentration lemma and advanced nonsmooth analysis.
2

---

Published as a conference paper at ICLR 2025
1.3
RELATED WORK
The majority of papers studying generalization bounds of Wasserstein distributionally robust models establish approximate generalization bounds. These approximate bounds introduce vanishing terms depending on v and p which embody the bias of WDRO. One of the first papers on such approximate bounds is [ee & Raginsky] (2018), and important results in this direction include [Blanchet et al. (202Ib); Blanchet & Shapiro (2023) about asymptotical results for smooth losses, and [Chnn & Paschalidis about non -oypttiyttll results for linear models and for smooth loss functions. Let us also mention Yang & Gao (2022) which deals with 0-1 loss, and Gao (2022) which focuses on Wasserstein-1 uncertainty and the connection with Lipschitz norm regularization. In this paper, we rather focus of exact bounds the form of 3 which are out of reach of ER.M-based models, and thus capture the essence of WDRO.
The literature about exact bounds is scarcer than the one about approximate bounds and signifi- cantly different in terms of proof techniques. Let mention Shafieezadeh-Abade
al. (2019) which establishes exact guarantees for linear regression models, and [aoo (2022) which proposes
tighter results for linear regression and Wasserstein-1 uncertainty. The closest work to our paper Azizian et al. 2023a), which initiates general study on exact bounds. There, the authors establish generalization results similar to ours, namely: exact bounds (3) in regime where p > O(1/vn). In sharp contrast with our work, the results from Azizian et al. (2023a) rely restrictive assumptions to overcome the nonsmoothness of the robust objective: the squared norm for the cost c, a Gaussian reference distribution, additional growth conditions, and abstract compactness conditions. We will further compare the setting and the results, in Section 2 and Section and in the supplemental. In work, directly deal with nonsmoothness, thanks to tools from nonsmooth analysis, and thus we are able to alleviate extra assumptions and capture nonsmooth losses.
The only other work regarding nonsmooth objectives is An & Gao (2021) which derives results piece-wise smooth losses, at the price of abstract approximating constants. We underline that none of the existing results properly covers nonsmooth losses, in particular deep learning objectives with nonsmooth activations.
Finally, let mention that there exist many works studying generalization guarantees for other distributionally robust models, involving different uncertainty quantification. For instance, [Zeng & Lam (2022) studies nonparametric families and divergence-based ambiguity, and Bennouna et al. 2023 considers deep learning models with ambiguity sets that combine KL divergence and ad- versarial corruptions. Though duality is always an important tool, we face in our framework to the specific difficulty of dealing with Wasserstein distances, so that the technicalities as well as the results of our paper are essentially different and disjoint from these works.
1.4 NOTATIONS
Throughout the paper (E, d) is metric space, where d is distance, F is a family of loss functions f: and c: = x E + IR is a cost function.
On probability spaces. We denote the space of probability measures on by P(E). For all E P(E x 3), E {1,2). we denote the 2hh marginal of by [r]; We denote the Dirac mass at { E E by dg. Given measurable function g IR, we denote the expectation of g with respect to Q E P(E) by Eg-o[s(E)] and we may also use the shorthand Eg]g)]
On function spaces. For a function / = + R. we denote the uniform norm by ||/ = supşe= [.f( By extension, we use the notation || = sup Il Whenever well-defined, denote the set of maximizers of f on = by arg maxg = {( E E f(C) maxçes f()).
We say f is Lipschitz with constant L > 0 if for all E E E. [ f(() < Ld(E, <). For function o. we denote 0x o the right-sided derivative with respect to E R, and o₂ its derivative, whenever well-defined.
3

---

Published as a conference paper at ICLR 2025
2 ASSUMPTIONS AND EXAMPLES
In this section, we present the general framework and illustrate it by standard examples. We make the following assumptions the sample space E, the space of loss functions F and the cost c. Assumption 2.1.
1. (E, d) is compact.
2. c is jointly continuous with respect to d, non-negative, and c(C. () if and only if = S.
3. Every f E F is continuous and (F. lloe) is compact. Furthermore, if (t, X, oloo) is the t-packing number of A then Dudley's entropy Ff
If Ix:= 1 Vlog N1, 11..lx)) l
is finite.
Our setting encompasses many machine learning scenarios, with parametric models, general loss functions, and general transport costs as illustrated in the two paragraphs below. In Section (34] we will also come back these assumptions discuss their reach and limitations.
Before this, let us underline that this set of assumptions is quite general and allows us to conduct a unified study and to relieve several restrictions found in previous works. In particular, we mention that the results of the closest work Aziziin et al. (2023a) require convexity of E. differentiability of losses f F. restriction to the squared Buclidean distance, together with a strong structural property on F (Azizian et al. [2023a] Assumption 5), aimed at overcoming the nonsmoothness of the WDRO objective. In our sketch of proof in Section 4 we explain how deal directly with nonsmoothness.
Parametric models and loss functions. Our setting covers a wide range of machine learning models. Consider parametric family F = (f(0.-) -) O E θ}. where the parameter space θ C R compact and the loss function f: E + jointly Lipschitz continuous. Since E is compact, such family is compact regarding || oloo and I,= is finite, proportional to vTr. This situation covers regression models, k-means clustering, and neural networks. For example: least-squares regression
f(0, (x. v)) (10, x² v)², ECR x R.
logistic regression
f(0, (z, v)) log (1+ (1+E-v(00)).
E C Rm X (-1,1},
and support vector machines with hinge loss
f(A, (z, y)) max {0, 1 v(O, x/},
E C Rd x (-1,1).
Note that the latter is not differentiable, due to the max term. The k-means model also introduces non-differentiable loss function:
[0, min 10, 10--x11 x112 θ RcRxx E R" K)
Finally, most deep learning models fall in our setting. Indeed, they involve loss functions of the form f(8, (x, 9)) ((h().z),)).
where é is dissimilarity measure and is parameterized prediction function, built as a compo- sition of affine transformations (which are parameters to train) with activation functions (see e.g. Krizhevsky et al. (2012): LeCun et al.] (2015); Redmon et al. (2016)). Our setting is gen- cral enough to encompass all continuous activation functions, even non-differentiable ones (as ReLU max(0, -)) well as other nonsmooth elementary blocks (as max-pooling (He et al. 2016), sorting procedures (Sander et al. 2023), and optimization layers (Amos & Kolter] (017)). As already underlined in introduction, these examples involving non-differentiable terms are not covered by existing results.
'The maximal number functions in F that are least at a distance from each other. We show in Proposition [.5 in the appendix that the compactness assumptions Azizian et al. Assumption hide strong conditions the maximizers.
2023a
4

---

Published as a conference paper at ICLR 2025
Sample space and transport costs. data and of the potential data uncertainty. For instance, if the variables are continuous with C R",, consider the distance d Ipp induced by E -p-norm (p [1, ool) and the cost power
The choice of the transport cost depends the nature of the
(q E [1, oo)) ) of the distance
d(E,E)) l| 5' 1l
the variables are discrete with C ,t....,J] J) m we consider the distance
d(c,E') = Σ 1l (C+EC 1=1
and the cost power of this distance. we deal with mixed data, i.c. they contain both continuous and discrete variables, sum of the previous costs can be considered. In classification, for instance, with the samples composed of features x E m and target y E 1),,1), we may take
((2, y). (x', v²) = | =²11 + x (u>t'}
for chosen 6 > 0. This cost is obviously continuous with respect to the natural distance
d((zz y), (I', y = | - 2'1pp + (vtt'}
This extends to mixed data with categorical, binary and continuous variables; see e.g. Belbasi et al. 2023).
MAIN RESULTS
3.1
WASSERSTEIN ROBUST MODELS
Our main result establishes generalization bound (3) for Wasserstein distributionally robust opti- mization (WDRO). Given a distribution Q E P(=) and a loss f E F, the robust risk around Q with radius p > 0 is defined as
sup Rf.e(f)== (.
B B
In particular, taking Q Q= Pn and Q= P the above expression, we consider the empirical robust risk, Rf),), and the true robust risk, R,(f)::
R₂(5)= = R P.P.. ( and R²()= Pp.
We also introduce the following constant, called the critical radius Perit.
Perit inf Eg-.P min (c(E.)) E arg max /
(5)
/EF
Note that Perit is defined from the true distribution P, which makes it deterministic quantity. In our results, we will make the further assumption that Perit > O, which exclude losses that remain constant across all samples from the ground truth distribution P. This assumption reasonably aligns with practice and is also in line with the previous works An Gao (202T); Azizian et al. (2023a). For instance, obtaining a predictor that precisely interpolates the ground truth distribution (leading to a loss equal to zero everywhere) unrealistic. In this context, our main result then establishes the generalization bound when n is large enough, for scaling with the standard 1/ V/ rate.
Theorem 3.1 (Generalization guarantee for Wasserstein robust models). If A'sssupption 2.7 holds and Per > then there exists Alow such that when n 16(a+))22 and p > v we have with probability at least 8.
p
(f) 2 Ee-r(f(E))
for all feF,
where a and are the two constants
2 00
2
2
96Iz
F1
/
4
||
2log
B
22
Nlow
Alow
Alo
Xoo
Alo
'See Proposition
F33
Appendix
F.1 about the interpretation of the critical radius.
5

---

Published as a conference paper at ICLR 2025
This result with p scaling with the dimension-free 1/v2 rate is similar to Aziziin al. 2023a Theorem 3.1), but guaranteed now in the wide setting of Assumption 2.1 We achieve this result through a novel proof technique that combines nonsmooth analysis rationale with classical concen- tration results; as depicted in Section
The eritical radius Parit be interpretated discuss it below in Remark B.1] The quantity Alow is positive constant related to the geometry of the Wasserstein ambiguity set; we discuss it in Section 4.2 Interestingly, in the case of linear and logistic regressions, we can establish estimates of these two quantities; see Section 3.2
degeneracy threshold of the robust problem;
We now extend the previous result to derive the following excess risk bound. Proposition 3.1
(Excess risk for Wasserstein robust models). Let be given by Theorem 3.1 Under
Assumption 2.1 if Parit 0,
16a² and
Pari 2 then with probability at least 1 8. Vn"
Per
(x( < Rpp 3m (f) for all f E.F.
In parficular, i d( with p [1, 20) and every F FsssTipp Tipp--ippsctt, then
R₂(() S Re-r + Tipz (p+
Vn
Remark 3.1 (The critical radius as a degeneracy threshold). The critical radius Peris defined in (5) plays the role of a degeneracy threshold for the problem, as follows. We can show that if 2 Perits there exists J E F satisfying Rp(s) maxegE [(E). Furthermore, for p 2 Parit + Ta with high
probability, there exists E F such that Rp(f) maxee= f(E)- In other words, if the radius is chosen too high compared to Perit, both generalization and excess bounds (Theorem 3.1 and Proposition 3.7 are vacuous. proof of this result is found in Appendix, Proposition F.I
3.2 GENERALIZATION GUARANTEES OF WASSERSTEIN ROBUST LINEAR MODELS
We now illustrate how our generalization guarantees from Section 3.1 apply to linear models. In this part, we assume the support of P to be contained ball of diameter centered
We recover estimates similar to the ones from the study of linear models (Shaficezadeh-Abadel al. 2019), hence showing the tightness of our approach. We consider the setting from Mlafeezzaeeh-Aaaee et al. (2019) where the parameter space is assumed to be bounded away from et al. 2019 Assumption 4.5):
zero (Shafieezadeh-Abaaee
Assumption 3.1 (Hypothesis domain). F (f(0),)
E θ}, where θ C RP is compact subset and c = - 1|2. There exists w > satisfying one of the following:
1. (Linear regression). f(0, (z, x)) (10, x) y) infage I1(0, -1)12 and w 2 1.
2. (Logistic regression). f(0, (x, v)) log( 1 + e -=10,=))) and inface |10|| 2 w.
Under this assumption, we obtain estimates for the constants Nlow and Perit- Proposition 3.2 (Linear models dual bound and critical radius). Under Assumption 3.1 supace ||0||2 Theorem 3.1 and Proposition 3./ hold with Perit 2 D2 and
ler =
1. (Linear regression) Alow 2 w under Assumption 3.1
w 2. (Logistic regression) Alow (1+eaa)
under Assumption 3.
These specific results show that we retrieve the constants from Shafieezadeh-Abale Abadeh et al. (2019) for normalized data in the case of logistic regression. In particular, our constant is proportional to 1/w2 for the linear regression. Remark that the tails parameters et al. (2019) correspond in our case to ||F] and D respectively, and Dud- ley's s constant is proportional to vp. In the case of linear regression, the dual lower bound is directly related to the parameter bound from seteeeezzadh--baddee et al. (2019). In more advanced set- tings (e.g. deep learning), the positivity of Xrow can be seen as an implicit definition of the hypothesis bound w.
(() and & ~ P. from
Shatieezadeh-Abadee

---

Published as a conference paper at ICLR 2025
3.3 REGULARIZED WASSERSTEIN ROBUST MODELS
Part of the success of optimal transport in machine learning is the use of regularization, and specifi- cally entropic regularization, opening the way nice properties and efficient computational schemes
(Cuturi 2013 Peyré & Cuturi 2019). Recall that the entropy-regularized optimal transport cost
writes, for reference coupling xo P(ExE) as
W (P, Q) =
min =EP(E (
[E,[cc + +
(6)
where () the Kullback-Leibler divergence w.r.t. Tg:
[L(T||=o) JExs
log du dr when < To dmp
00
otherwise.
Given the definition of [T. note that the minimum (6) is well-defined, attained at some cou- pling P.Q < To. see e.g. Peyré Cuturi (2019). Regularization have been recently studied in the context of WDRO: Wang et al. (2023) introduces an entropic regularization in constraints for computational interests, Azizian et al. (2023a) considers an entropic regularization the objective for generalization, and Azizian et al. (2023b) studies a general regularization in both constraints and objective.
Following the most general regularization
AAzizian et al.
2023bb consider the robust risk with double
sup (2)(()) SEP(EXE), [+ E-(c]+> KL(a
[f] DKL (
with two parameters c > 0 and r 2 0. We introduce the conditional momen of xa
m. max B ()),
EEE
and the regularized critical radius
Pert inf EENP 18 ( fer
+(()) + c(E, T log E8 (
(8)
(-15) (-10))
where dm! f/ (-1E) a ef//dmo(-1 (-1E) In this setting, the generalization guarantee states as follows.
Theorem 3.2 (Generalization for double regularization), Under Assumption 2.7 there exist The > and f 0 depending on C,E,C,,, and 6, such that if P >> 4m, when (par 4m,
4
and p max me: a- WT Q) p.
vol }. we have with probability at least 5, for all Q P(E) such that
P.Q (TO)
for all f E F,
where π P.Q. the optimal coupling in 6
This result is similar the one of Theorem 3.1 and is also similar to the only other generaliza-
tion result existing for regularized WDRO Azizian et al. 2023a). Let us explicit below the main differences.
Unlike Wasserstein robust models (Theorem 3.1 regularization leads to an inexact generalization guarantee, where the regularized empirical robust risk bounds proxy for the true risk Ey(f]. This is in line with the regularization in optimal transport that induces a bias in the Wasserstein metric, preventing W (P, P) from being null. In particular, given an arbitrary 5 0. WT (P, P) may not be lower than p.
The coefficients a TH and gr exhibit similar relations with Xi || and Iy to their counter- parts and B from Theorem 3.1 Their complete expressions can be found in the extended version
'F.g. if c(E, = -1 and mo(-)) is truncated Gaussian no (o(-)) x 1--e12 11, we have m. x o² 'Due the definition of the Kullback-I Leiblrr divergence 7 we necessarily have n. P.Q & no.

---

Published as a conference paper at ICLR 2025
of Theorem 3.2 (in Appendix, Theorem E.2) In particular, the expression of TM suggests me. c,
and p should be of comparable order. Compared to the standard setting, we have an estimate of the
lower bound low (Lemma D.2 showing dependence the loss family: Xoow 0 |
Compared to Azizian et al. (2023a), we underline that our result covers the double regularization
case. Moreover, it is valid for an arbitrary To whereas the one from Azizian al. (2023a) relies
the specific form of To involving Gaussian term. Our result is thus more flexible, allowing freedom
in the choice of To.
As for the standard case (Proposition 3.1 this setting that we lose the explicit control of the true risk. This is mainly due the inexactness brought by regularization.
we obtain an excess risk bound. The main difference in
Proposition 3.3 (Excess risk for doubly regularized robust models). Let a be given by Theo- 16a (Pen 4m.]]² and me < ps
rem 3.2 Under Assumption 2.1 if Perit 4me
Pait a.
then
VT
with probability at least
b.
R7 (f) S RTc pt vi
ane (f)
for all f FEF.
3.4 LIMITATIONS AND POTENTIAL EXTENSIONS
In the previous sections, we presented our results and their universality, underline that they are widely applicable in machine learning. In this section, we discuss three relative limitations of our results: the assumption of the compactness of sample space, the assumption of finite Dudley entropy, and the expression of constants.
Compactness of the sample space (Assumption 2.1 1) is essential to control worst-case distri- butions of the robust objective (2). given our level of generality. This assumption is in line with some recent studies (Azizian et al. 2023a; Blanchet & Shapiro, 2023); see also Gao et al. (2022)
which uses bounded growth assumptions. Such assumptions are reasonable, as standard statistical frameworks involving Gaussian or heavy tail distributions could be covered by truncating.
In study, considering loss families with finite Dudley's entropy (Assumption 2.1 3) is crucial to limit the dependence on the sample dimension. This assumption satisfied for Lipschitz para- metric losses with bounded parameter space, and it is not clear if a dimension- ffre generalization could be established for non- parametrei losses. For instance, ZZng & Lam (022) dealing with non- parametric losses, exhibits generalization guarantees with exponential dependence in the dimension.
Finally, regarding the generalization constants, we could improve them in several ways. For instance, leveraging the structure of specific models would allow obtain estimates of the constants Atow. Perit: this is what we did for the linear models in Section 3.2] Taking into account the optimization procedure which selects small set of solutions could also be interesting in order have sharper constants on the class F.
4 SKETCH OF THE PROOF
This section presents our strategy to prove the generalization results of Section 3 (Theorems 3.1 and The strength of our approach is use flexible nonsmooth analysis arguments, able to cover the general situation of arbitrary (continuous) cost and objective functions. We present the main approach in Section 4.1] based on a duality formula and lower bound \oo on the dual variable. In Section 4.2 we focus on the latter and shed lights on its role. Finally, we explain in Section 4.3 the extension to regularized models.
3.2).
4.1 MAIN APPROACI
Compared to the original formulation (4) the dual representation significantly diminishes the prob- lem's degrees of freedom, and is usually the starting point of most studies of WDRO; see e.g. Kuhn Azizian et al. (2023b). Given any distribution
al. 2019);
P(E) and radius p 0, it holds
Rf. inf (Ap + E Bg-o(o(A,
X
8

---

Published as a conference paper at ICLR 2025
where the dual generator is convex function with respect to X, and Lipschitz continuous with respect to f. For Wasserstein robust models, & has the expression (see e.g. Blanchet & Murthy 2019
O f.E) sup Xo(( CEE
Observe that é is naturally convex in X, but also nonsmooth. The originality of our approach is to build on this nonsmoothness by using rationale of nonsmooth analysis, which allows us to cover the case of other dual generators as for the regularized versions; see next section.
Let us then outline the main steps to establish Theorem 3.1
1. Dual lower bound. Given 3 >> appearing in Theorem 3.1 We establish the existence of
a dual lower bound Alow 0, which holds with high probability for all f F, for a small enough radius
I Porit 4
vn
Ra( inf (00)
{xp+ BE (1(1,
This done in Appendix E.1
2. Concentration of the radius. Let us write for all 2 Noo and f EF
Ap + Ep, (6(A, 2 ( [p] Ep, 1o, 11)) 1p,1ooA.111))+ + Er f)l
X
2 A(p - an) + Ep(o(A,
where we define the uniform gap On by
0₂ = sup (Eppd((> [1] Ep, [uØ(u
(f] (ap(((11)1 (4, E (0, ) xF].
(10)
This quantity can be bounded with high probability by रे - where > 0 is the constant from Theorem 3.1 To obtain such bound, we rely on known uniform concentration theorems for Lipschitz functions (Boucheron et al. (013). Concentration constants are computed in Appendix
3. Generalization bound. We can now obtain the result. Taking the infimum over À 2 Ajow in 9 we obtain with high probability for all F.
R₂(f) / Eg=e(f(E)),
whenever 3 < Vn
3.
This interval is nonempty if n > 16(a+ 333 Since
(f) is non-decreasing with respect p. have R,( Eg)p(f(E) for any p Vn as long 16(a + /P
4.2 DEFINITION OF THE LOWER BOUND
Alow defines dual lower bound on the true risk Rf),), making it independent from samples random- ness. In our proof, we then show that this lower bound holds with high probability on the empirical robust risk (f) using the convexity of Φb This is done in Proposition E.2 in Appendix.
(Er|-O>(N) ffE)
Perit
Pmax
We now explain the definition of \tow more precisely, We consider the maximal radius function
Prnxx (A) = -inf Fe-rl-0t ((A,,))) FEF
A
At a given X, this function indicates the maximum value p can take for the dual solution of RJ( to be
Figure A central object of our analysis: the maximal radius Pinax defined from the lower envelope of derivatives of &b

---

Published as a conference paper at ICLR 2025
higher than X. In particular, by convexity of o, can easily verify that: if I Punax (X) for all E [0, 2N then the dual bound 2Atow holds on the true robust risk, and we have:
Rp(f)
inf 222Atow
+ EE (A, f.E)..
(11)
As illustrated by Figure 1 Pmax reaches its highest value at zero, which is actually the critical radius, Perit. The crux of the proof is to show there exists a value Xoo allowing to choose radius values of order Perit. This comes by passing to the limit in Piax(X)
Lemma 4.1. We have limx-s0+ Pmax (A) = Perit- In particular, there exists Aoo > O such that if
P Perit then (1) holds for all f E F.
Such result may be surprising since & is nonsmooth function and Pmaxx. defined from the lower envelope of (discontinuous) derivatives of ái is in general highly discontinuous. In order to establish it, we use tools from nonsmooth analysis (Appendix A.1 and leverage compactness of the class F.
4.3 EXTENSION TO (DOUBLE) REGULARIZZTIION
The strategy of Section 4.J is flexible enough to be extended to the regularized setting of Section 3.3 Indeed, the regularized problem also has dual representation, with a dual generator defined by
((0) Ae(s()) <txr
(A, f.E) (e + Xr) log B-
where e >> 0 and T 2 0. Strong duality has been shown in Azizian et al. (023bb) We explain in
Appendix B Proposition B.2 how it applies our general setting, This regularized dual generator leads to a smooth counterpart of the key function Pmax from the proof and to the regularized critical radius (8. In particular, we can show the regularized version of Lemma 4.1
Lemma 4.2. lim Puiax (A) Perit- In particular, there exists TTe O such that if S Suga
inf {Ap Bg-plollott (A, (1))
for all f F.
22
Then we obtain Theorem 3.2 by repeating the proof scheme of Section
The core results that
simultaneously lead to Theorems 3.1 3.2 are gathered in Appendix E. Due the smoothness
of pi expression of Xoor can also be obtained; see Lemma D.2
The key difference brought by regularization is that Lipschitzness of (oo(=))..E) is lost when a - 0. This prevents us from using the concentration result essential bound the gap a, (TO) unless we can set lower bound on μl, or equivalently an upper bound on X. This issue is inherent to the regularized setting and may oceur over the whole family and the space E; we provide an example in Proposition [:4 to illustrate this. The next lemma aims to overcome this issue by establishing the existence of such an upper bound for any distribution (see Lemma D.3 for a proof).
2|1ll Then for all f E F. Lemma 4.3, Let Q P(E). p> m. and Aup p-m
(f
inf AE(O,Aup]
(Ap + (A,
CONCLUDING REMARKS
In this work, we provide exact generalization guarantees of (regularized) Wasserstein robust models, without restrictive assumptions (on the transport cost 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 it is not necessary to consider specific regimes for p in order expect good generalization from robust models. Further research can now focus on practical aspects: it would be of premier interest to design efficient procedures for selecting and more generally, scalable algorithms for solving distributionally robust optimization problems.
ACKNOWLEDGMENTS
This research was partially supported by MIAI@Grenohhe Alpes (ANR-19-P31A-00N)
10

---

Published as a conference paper at ICLR 2025
REFERENCES
C.D. Aliprantis and K.C. Border. Infinite Dimensional Analysis. Springer Berlin, Heidelberg, 2006.
Brandon Amos and J Zico Kolter. Optnet:
Differentiable optimization as a layer in neural networks In International Conference on Machine Learning, pp. 136-145. PMLR, 2017.
Yang An and Rui Gao, Generalization bounds for (wasserstein) robust optimization. In Advances in Neural Information Processing Systems, volume 34, pp. 10382-10392, 2021.
Adriano Arrigo, Christos Ordoudis, Jalal Kazempour, Zacharie De Grève, Jean-François Toubeau, and François Vallée. Wasserstein distributionally robust cannce-costrriined optimization for en- ergy and reserve dispatch: An exact and physically- bounded formulation. European Journal of Operational Research, :9304) 322, 2022.
Waiss Azizian, Franck lutzeler, and Jérôme Malick. Exact generalization guarantees for (regular- ized) wasserstein distributionally robust models. A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 14584-14596. Curran Associates, Inc., 2023a.
Waiss Azizian, Franck lutzeler, and Jérôme Malick. Regularization for wasserstein distributionally robust optimization. ESAMM: Control, Optimisation and Calculus of Variations, 29:33, 2023b.
Peter L. Bartlett and Shahar Mendelson. Empirical minimization. Probability Theory and Related Fields, 135(3):11-333,, Jul 2006. ISSN 1432-2064. doi: 10.1007750040000050446... URL
bttps://dof/ wwg.
0462-3
Reza Belbasi, Aras Selvi, and Wolfram Wiesemann. It's all in the mix: Wasserstein machine learning with mixed features. arXiv preprint arXiv:2312.1223:: 2023.
Amine Bennouna, Ryan Lucas, and Bart Van Parys. Certified robust neural networks: generaliza- tion and corruption resistance. In Proceedings of the 40th International Conference on Machine Learming. ICML'23, 23. JMLR.org, 2023.
Jose Blanchet and Karthyek Murthy, Quantifying distributional model risk via optimal transport. Mathematics of Operations Research, 44(2):565-60) -000 2019.
Jose Blanchet and Alexander Shapiro. Statistical limit theorems in distributionally robust optimiza- tion, 2023.
Jose Blanchet, Karthyek Murthy, and Viet Anh Nguyen. Statistical analysis of wasserstein distribu- tionally robust estimators. Tutorials in Operations Research: Emerging Optimization Methods and Modeling Techniques with Applications, pp. 227-254. INFORMS, 2021a.
Jose Blanchet, Karthyek Murthy, and Nian Si. Confidence regions in Wasserstein distributionally robust estimation. Biometrika, 109(2):295-315, 2021b.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymp- totic Theory of Independence. Oxford University Press, 2013.
Ruidi Chen and Ioannis Ch. Paschalidis. A robust learning approach for regression models based on distributionally robust optimization. Journal of Machine Learning Research, 19(13)11-48, 2018.
F.H. Clarke. Optimization and Nonsmooth Analysis. Classics in Applied Mathematics. Society for Industrial and Applied Mathematics, 1990.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems, volume 26, 2013.
Villani Cédric and Cédric Villani. Optimal transport: old and new / Cédric Villani. Grundlehren der mathematischen Wissenschaften. Springer, Berlin, 2009. ISBN 978-3-540--1149-3.
M. D. Donsker and S. R. Varadhan. Asymptotic evaluation of certain markov process expectations for large time, i. Communications Pure and Applied Mathematics, 28(1):1-49 1975.
11

---

Published as a conference paper at ICLR 2025
R. Durrett. Probability: Theory and Examples. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2010.
Nicolas Fournier and Arnaud Guillin. On the rate of convergence in wasserstein distance of the empirical measure. Probability Theory and Related Fields, 162(3):707-738, 2015.
Rui Gao. Finite-sample guarantees for wasserstein distributionally robust optimization: Breaking the curse of dimensionalityy. Oper. Res., 7166):2291-230000 2022.
Rui Gao and Anton Kleywegt. Distributionally robust stochastic optimization with wasserstein distance. Math. Oper. Res., 48(2):603-655, 2023.
Rui Gao, Xi Chen, and Anton Kleywegt. Wasserstein distributionally robust optimization and variation regularization. Operations Research, 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep volutional neural networks. In Advances in Neural Information Processing Systems, volume 25, 2012.
Daniel Kuhn, Peyman Mohajerin Esfahani, Viet Anh Nguyen, and Soroosh Shafieezadeh-Abiiee Abadeh. Wasserstein distributionally robust optimization: Theory and applications in machine learning. In Operations research & management science in the age of analytics, pp. 130-166. Informs, 2019.
Yongchan Kwon, Wonyoung Kim, Joong-Ho Won, and Myunghee Cho Paik. Principled learning method for wasserstein distributionally robust optimization with local perturbations. In Interna- tional Conference on Machine Learning, pp. 5567-5576. PMLR, 2020.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553))4364444 2015.
Jaeho Lee and Maxim Raginsky. Minimax statistical learning with wasserstein distances. In S. Ben- gio, H. Wallach, H. Larochelle, K. Grauman, N. Resa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Jiajin Li, Caihua Chen, and Anthony Man-Cho So. Fast epigraphical projection- based incremental algorithms for wasserstein distributionally robust support vector machine. In Advances in Neural Information Processing Systems, volume 33, pp. 002994039, 2020.
Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the wasserstein metric: performance guarantees and tractable reformulations. Mathematical Programming, (71(1):115-16) 2018
Gabriel Peyré and Marco Cuturi. Computational optimal transport: With applications to data sci- ence. Found. Trends Mach. Learn., (115-66)355-444 607, 2019.
Y. Polyanskiy and Y. Wu. Information theory: From coding to learning. prepublication, 2023.
J. Redmon, S. Divvala, R. Girshick, and A. Farhadi. You only look once: Unified, real-time object detection. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp- 779-788, Los Alamitos, CA, USA, 2016. IEEE Computer Society.
R. Tyrrell Rockafellar and Roger J. B. Wets. Variational Analysis. Springer Berlin Heidelberg, 1998.
Michael E. Sander, Joan Puigcerver, Josip Djolonga, Gabriel Peyré. and Mathieu Blondel. Fast, differentiable and sparse top-k: A convex analysis perspective. In Proceedings of the 40th Inter- national Conference Machine Learning, ICML'23. JMLR. 2023.
12

---

Published as a conference paper at ICLR 2025
Soroosh Shafieczadeh-Abadeee Peyman Mohajerin Esfahani, and Daniel Kuhn. Distributionally robust logistic regression. Proceedings of the 28th International Conference on Neural Infor- mation Processing Systems Volume NIPS 15, pp. 1576-1584, Cambridge, MA, USA, 2015.
MIT Press.
Soroosh Abadee, Daniel Kuhn, and Peyman Mohajerin Esfahani. Regularization via mass transportation. Journal of Machine Learning Research, 20(103):1-66, 2019.
Aman Sinha, Hongseok Namkoong, and John C. Duchi. Certifying some distributional robustness with principled adversarial training. In 6th International Conference Learning Representa- lions, 2018.
Bahar Taskesen, Man-Chi Man-Chung Yue, Jose Blanchet, Daniel Kuhn, and Viet Anh Nguyen. Sequential domain adaptation by synthesizing distributionally robust experts. In International Conference on Machine Learning, PMLR, pp. 10162-10172. 2021.
Vladimir Vapnik. The Nature of Statistical Learning Theory. Springer: New York, 1999.
Martin J. Wainwright. High--iimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
Jie Wang, Rui Gao, and Yao Xie. Sinkhorn distributionally robust optimization, 2023.
Zhen Yang and Rui Gao. Wasserstein regularization for 0-1 loss, 2022.
Yibo Zeng and Henry Lam. Generalization bounds with minimal dependency on hypothesis class via distributionally robust optimization. Advances in Neural Information Processing Systems, 35: 27576-27590, 2022.
Luhao Zhang, Jincheng Yang, and Rui Gao. A simple and general duality proof for wasserstein distributionally robust optimization. arXiv preprint arXiv:2205.000 220.00062, 2022.
Chaoyue Zhao and Yongpei Guan. Data-driven risk-averse stochastic optimization with wasserstein metric. Operations Research Letters, 46(2):262-267, 2018.
13

---

Published as a conference paper at ICLR 2025
Supplemental material
This supplemental gathers recalls, technical lemmas and definitions, examples, and detailed proofs of the results from the main text. The core of our contributions is presented in Appendices D and The whole supplemental is organized follows:
In Appendix A we recall some essential mathematical tools. They include continuity notions in nonsmooth analysis, the envelope formula differentiate supremum functions (Theorem A.T and a uniform concentration inequality (Theorem A.2).
In Appendix B we present strong duality results for WDRO and its regularized version. We explain in particular how the duality theorem from Azizian et al. (0023b) can be easily adapted to our setting.
Appendix C contains preliminary computations in view of applying the uniform concentration theorem.
we demonstrate the existence of a dual lower bound in the standard and regularized cases. particular, the proof' involve the maximal radius introduced Section 4.2
In Appendix D
By using these preliminary results, in Appendix we prove our main results. They include the generalization theorems (Theorem B.1 and 3.2 excess bounds (Proposition 3.1 and Proposi-
tion 3.3 and the constants of the linear models (Proposition B.2
Appendix F contains results supporting several remarks of the main. They include the interpreta- tion 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 Azizian
et al. 2023a
NOTATIONS
Throughout the proofs will use the following notations:
On probability spaces. Given the metrie space (E.d) where d is distance, denote the space of probability measures on by P(Z). For all π E P(E E), [1,2], we denote the 7t marginal of π by [T]: We denote the Dirac mass at & E by de. Given a measurable function g we denote the expectation of with respect to Q E P(z) by [g=o[l(E)] and we may also use the shorthand Eq(g) [g]. For E P(E), we use the notation 77 for the Gibbs distribution dx x eddæ.
RR
On function spaces. For continuous function f E + E. we denote the uniform norm by |l supçez [f( By extension, if J is a set of functions we denote || = sup Il Whenever well-defined, we denote the set of maximizers of f on E\t by arg max f == {c E f(() = max f Given metric space (X, dist), we say function
X + is Lipschitz with constant L > 0 if for all E X, [h(z) h(y) s L dist(z, y). For o: R x X' + R, we denote o the right-sided derivative with respect to A E I. and θgo the derivative, whenever well-defined.
In Wasserstein robust models.
o(A supçez (f(C) -c(EE
((,, = pÓ(μ ffE)
Perit = inf E.-P [min {c(E,C) ; Ç arg maxg f}]
In Wasserstein robust models with double regularization.
(T = (e Ar) log Ec A
14

---

Published as a conference paper at ICLR 2025
Porit = JeF Beao (Es (Ef(() + c(f.))) - log B Bc (-1e)
n(
A RECALLS AND TECHNICAL PRELIMINARIES
A.1 NONSMOOTH ANALYSIS
In this part, the notation G X 3 y denote function G defined X' and valued in the set of subsets of y.
Semicontinuity notions will be necessary understand the proof of Lemma D.1 notions recurrently arising when manipulating nonsmooth convex functions.
They are regularity
Definition A.1 (Lower and upper semicontinuity (Aliprantis & Border 2006 2.42)). Let (X, dist) be a metric space and let f : + R. Then
1. f is called lower semicontinuous for all x E H, liminff-ve f(y) 2 f(z).
2. f is called upper semicontinuous if for all x E X. lim sum-upy-e f(y) s f(z).
In particular, if f is lower semicontinuons, 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
E X if for all open subset V C y containing G(r)), there exists a neighborhood U of x which is such that for all w E U, G(w) C V.
Semicontinuity of maximum and arg max functions are central to the proof of Lemma D.I Lemma A.1 (Semicontinuity of maximum value (Aliprantis & Border 2006 17.30).. Let and be metric spaces and let G X = be outer semicontinuous with nonempty compact values, E x E continuous. Then the function
x + max(m((x o G(x)}
is upper semicontinuous. In particular, u + min v) u U G(x)) is lower semicontinuous. Lemma A.2 (Semicontinuity of maximizers (Aliprantis & Border 2006 17.31)). If X is metric spuce, (E, a compact metric spuce, and X x x + continuous, then the function max h(z,2) 2) is continuous, and the set-valued map + arg max,es henn,,ss(x,, is outer semicontinuous.
We recall the definition of gradient for nonsmooth convex function. This the subdifferential. Definition A.3 (Subdifferential of convex function). Let Φ Ram -> R be convex function. Then we call subdifferential of & the set-valued map do 1 = 1 such that for all x E 1.th and
y E m
σly) 2 (xx) + (v. - x) for all E dΦ(x).
In particular, we may apply the envelope formula to compute the subdifferential of maximum function:
Theorem A.1 (Envelope formula (Clarke 1990 Cor. 1, Chapter 2.8)). Let (E, be compact metric space and g I = + R such that
1. For all TM, g(æ, -) is continuous.
2. For all Ç E g(: () is convex with subdifferential Ozg(-.
Then G : supçe= g(=5)) is convex on R" and its subdifferential is given for all x E R by aG(x) = conv (u= v 0zg(x, {), Ç E arg max g(z, })
where conv denotes the convex hull of set.
15

---

Published as a conference paper at ICLR 2025
A.2 UNIFORM CONCENTRATION INEQUALITY
We recall concentration inequalities that gives high probability uniform bound for a family of bounded and Lipschitz functions. We refer the reader to Boucheron et al. (2013) for complete reference on concentration inequalities, and Lemma G.2 in Azizian et al. (2023a) for the proof of such a result.
Theorem A.2 (Uniform concentration (Azizian et al. 2023a Lem. G.2)). Let (X, dist) be (totally
bounded) separable metric space, probability distribution on probability space E, and P.. E 8g. with En. Lid. P. Consider a measurable mapping X X' TR and assume that,
(i) There is constant such that, for each E, (xx,() {) is L-Lipschitz
(ii) X(:E) almost surely belongs to (a,
Then, for any å E (0, we respectively have
1. With probability at least 1
(E (x(x, E)] Bx- 48LI dist)
log
sup EEX
+ (b - --ay// 2
Vn
2. With probability at least 5,
[emP[X(x, 0) - E E (x(x,)) 48 dist) + (b - 03/2
log
sup xEX
The quantity I(X, dist) is defined as follows: Definition A.A. Given compact metric space (X, dist), Dudley's entropy integral, I(X, dist), defined as
I(X, dist) = S Vlog (t, (t, X, dist
where Ntt, 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.
may recall some properties Dudley's entropy for Cartesian products and segments from IR. These are known results, e.g. Wainwright (2019) and Lemmas G.3 and G.4 from Azizian et al. 2023a) for proofs.
Lemma A.3 (Dudley's integral estimates).
1. (on Cartesian products) Let (Xi, dist,) and (X2, dist2) be two metric spaces. Consider the product space X : Xi x X2 equipped with the distance dist == dist + distg. Then we have the inequality
I(X' dist) S I((,, disti) + I I(X2, dist2).
2. (on R) Let e > O. Then we have the inequality
3c
I(10,,,,.1)
2
B STRONG DUALITY
In this section, we recall duality results for WDRO Blanchet Murthy 20099; Gao & Kleywegt (2023); Zhang et al. (2022) and its regularized version Azizian et al. (202bb). We recall the optimal transport cost with cost e for (Q, Q') E P(E) x (E))
Wa(Q, Q') inf (E (c(E.
P(E x [x) Q, 2=
16

---

Published as a conference paper at ICLR 2025
Proposition B.1 (Strong duality, standard WDRO). Under Assumption 2.1 for any Q P(E) and > 0, then
sup
B [f(E) inf {Ap + E X20
W.(
Proof. This an application of Theorem from Blanchet & Murthy (2019). In particular, Assump- tions and 2 from Blanchet & Murthy (2019) are satisfied through Assumption 2.1
Proposition B.2 (Strong duality, regularized WDRO), Under Assumption 2.1 for any Q E P(E) and p > 0, if there exists a E P(E 3) such that E [c] DKI. ( [|TT)) < p. then
sup TEPIEXEN Be KL(T
(Be ((()) KL(T||=)) inf {Ap+ + EE-Ol0 (A,5.))) (A
(12)
A20
In particular, if > m 12
holds.
Proof. This is application of Theorem 3.1 from Azizian al. (2023b), which corollary to Theorem 2.1 Azizian et al. (2023b). In particular, if mc the coupling satisfies Ew, [c] +
=DKL(To) mo) ET, I m. < p.
Note that the proof's of Theorems 2.1 and 3.1 from Azizian et al. (2033b) can be easily extended to general compact metric space (E, d), without being rewritten entirely. Precisely, only two arguments in their proofs rely on the real-valued RockaflRoo & Wets 1998) but can be directly extended general metric space as follows:
In the proof of Theorem 2.1 from Azizian et al. (2023b), one needs to justify
sup (EG-PlO(E,C(EE) : measurable) > Eg
sup ( ()
(13)
CEB
To this end, the authors use the notion of normal integrand from Rockafellar & Wets 1998).
Actually, (13) holds true in compact metric space: if yp is continuous, then by compactness of E, the set-valued map { + arg maxçes (p( admits measurable selection (*, by the measurable maximum theorem, see 18.19 in Aliprantii & Border (2006). Such selection then satisfies (E)) supçes (EE <) for all & E =, hence the result.
In the proof of Theorem 3.1 from Azizian et al. 2023b gr = supce= sf:; {) is actually continuous by Lemma A.2 and the approximation by the infimal convolutions (of )ee need not be done.
Note that the convexity of E\t is not required (although stated in Assumption from Azizian et al. 2023bb
C
CONCENTRATION CONSTANTS
In this part, we compute some constants view of applying Theorem A.2 for the main proofs of Appendix E
C.1 STANDARD WDRO
For standard WDRO, we compute bounds (i) and global Lipschitz constants (ii) for e and th.
Lemma C.1 (Concentration conditions for WDRO). we have the following:
1. (i) For all X > 0. f and & E E, d(A,
(ii) For À 2 and & E E, (A,, f) is Lipschitz continuous on F with constant
1.
2. (i) Given Aioo > for all μ. E (0, - and ʃ E 6(1, E
1 Fl Atow
Alow
17

---

Published as a conference paper at ICLR 2025
(ii) For all & B, (H, + (u, is Lipschitz continuous (0, Now! with constant || Voo
Proof. 1. (i Let (.5) E R+ x E. Recall that o(x, f.C) := sup {f(() de(5, ())- Since e is nonnegative, we have f.). 5 ol On the other hand, since c(,,E) = O, we also have (A, 2 f(() 2 -I|F Finally, we have (.) [- [F])
(ii) Let À 2 0, E E and (f.f) E x F. For all & E E, we have
f(() xc(5, 6 f) - f(() Ac(5, (f)(() Xc(
f() (()
< - /o
Taking the supremum over Ç on the left-hand side gives d(A, f.E) -1 Permuting the roles of f and f' yields f.() o ,) & Ilf fl We proved that (A,,', is 1-Lipschitz continuous.
(i) Now, let Nlow and let (n, f.E) E (0, Now! F be arbitrary. Then we have
uΦlu (ob(u=,,(E) 5( = sup (us(C) - -l,, ()) <
<EE
Alow
On the other hand, using c(E, {) = 0 we obtain
|| Alow
sup CE
-c((())((EEE) pf(E)
[-1--11 10 11 Atow
whence we have
E
Alom
(ii) Toward proof of (ii), let Nrow > O, and & E 3 and i E (0, Aoow). Remark that p ,, ((E)) supçez {us(() c). The function (μ,, f) + mub()1,,,, write as a com- position u v where u(h) == supce= (M(C) c(.C)) for h E C(E, R), and v(u, == μf for f (0, I. is 1-Lipschitz continuous with respect to llae. As v, we can write
#$ - -' = p( fd) f' R(),
whence e is clearly (||Fl + ) J-Liscchit continuous on (0, ATo x F. By composition, u o is Lipschitz continuous with constant Fl + APow
C.2 REGULARIZED WDRO
We now compute the analogous constants the regularized setting.
We will use the following convexity lemma repeatedly:
Lemma C.2 ((Azizian et al. 2023a Lem. G.7)). Let = + R. measurable bounded function
and Q P(E). Then one has the inequality
B B5-glo(()ens))
log Ee-q [eats] <
Esne(es(s)
The following the regularized version of Lemma Lemma C.3 (Concentration conditions for regularized WDRO). E E. Then
1. (i) For all X 2 0 and f F.F, (A,
- Xme. ||looo (ii) For all X 2 0, f + (T, J.E) is Lipschitz continuous with constant 1.
2. (i) Given Alow
>
for p E ( Noul and f F. (T f.E)
Ff Nlo
1f
ma:
Avoe
18

---

Published as a conference paper at ICLR 2025
(ii) Given Aup 0. (H, f) (p,
f.E) is Lipschitz continuous on Duu Now! F
with constant |Fol + Now +
Aupt ct2up
me-
(())An(5:()) ctxr
11 This gives
Proof. 1. Let (A, E R4 x F x For all Ç SEE,
I ct
1F etlAr
(T.
(c XT) log E (-
|| boo
(14)
- -
On the other hand, e
2
which gives
1F GEAT
Aete.() 6))
(A, 2 (e+ XT) log
E
c~
+4xT
Aelt.c) CTAA
2 =1 (r) log T ()(
e
2 - 00 Ama
(15)
where for the last inequality we used Jensen's incquality on the convex function + e cR
Combining (14) and (15) gives
(A, E |-1FF Ame, [F1loo]
(ii) Let E and À 220 0. To compute the Lipschitz constant of - (A, compute the derivative of hy : + "0'*(,,
(A, f + tv, () where t and for an arbitrary direction v E F. We have
(t) (e + XT) log (- e
is easy to verify that n
1 *EXT
[o({)], whence [M,(t)] S ||0||0e This means
<~a0
(1E)
that Th (), E) has Lipschitz constant 1.
2. (i) Let Alow > 0 and (1, E Aoul x FXE E. A. We deduce from 14 and 15 with that
| Alow
(f5)
Me:
Alow
(ii) Now, let & E E. Our goal is to compute Lipschitz constant of (H, f) + ( f.E) on Dru Aooul x F. We first compute Lipschitz constant of
: _ (n f, = (ue + r) log Bg
pe+t
on (up >o for arbitrary f E F. The derivative of hy is
1 E () (eo(E) Tf(())
#S( e(e.C) 10+7
wiit) cle.s) pc
hly(1) ne + Ee
log Eg f)
#((() o(E.6)
e
which we write
EC(E,)) + +f((s)
af(c)-e(e.e) He-T
Ny(p)= E of c(e-)
+ c clog E Be-xo((1))
(16)
To (11)
Me +
We bound M2 (n) above. By Lemma C.2 with Q To(-) and g uT-a(E.)
ue+t we have that
wSi ole-c)
(qp((s) (((E.5)
pe + [
clog Ecmmo(-1e)
el-ors pett
(
(-15)
which gives N1 (p) < E
et-o(en) [f(()] < || o0.
wetr
19

---

Published as a conference paper at ICLR 2025
Now bound (1) below. We start with the first term in (66). Since is nonnegative, clearly have
c)(5, +T((()
Fl
E of
(17)
50
(EE)
pC +
pec +
As to the second term of 16). have by Jensen's inequality,
2f())-ffe.d)
emT
log R (ovaa(-15)
RC
(18)
JUC Auprmme e+xup
pec +
Combining (17 and 18 gives R2((H) 2 11
Finally, by has Lipschitz constant
Aup ||
Since @ ( ,,,"",,;,)))))))) Lipschitz constant Ajow-
.) has Lipschitz constant 1, then μ S Xoor the function u ..r)) has
Now, obtain Lipschitz constant for
h: (H, f) + (HE + T) log ( [e
(((C)=u(s Nett
" f.E).
Indeed, for (d) E 1 Nool Drup Noow and (f, E we write
(k,, f) h(p', f')l s 1h(,, f) hul' 11(H', f) h(p' f')l Aupe
)) Iu w'l > llf f'lloo
|FFl10o (e+ AupT
hence has Lipschitz constant ||F|| + Noow + (xuupp
Mc..
D DUAL BOUNDS AND MAXIMAL RADIUS
We establish the existence of a dual lower bound on the true robust risk (Lemma 4.1 for the standard WDRO problem in D.I and for regularized WDRO in D.2] The results involve maximal radius
introduced in Section 4.2 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 2 0, we recall the expression of the maximal radius:
Pmax (A) inf E Eg=pl-Ot O(A.
fEF
Lemma D.1. Pmaxx (0) = Perit and lim--0 Pmax (A) Perit. In particular, there exists A 0 such that Premxe ()) 2 Parit for all [0, 2.
apply the envelope formula (Theorem A.I and the right-sided derivative of ó with respect to À is 0 of - -min {c(s.c) () E arg maxg {f )e(E,))) For convenience, we use the shorthand
Proof. For E E, f Xe(g,-) is continuous, hence
c²(5, K) minfc(g, 2), K}
whenever K C is compact. By integration and taking the infimum over F we obtain
Pmax (A) inf Pe= arg max { xc(E--))))-
(19)
Jer
In particular, Pmax (0) Parit-
To prove the result, it is sufficient to show that lim infx Pmaxx (Ax) 2 Perit for any positive sequence (Ae)eEN converging to O. Indeed, the functions (c are convex hence their right-sided derivatives Eç~pI-Ort f()) nonincreasing, and Pmax is nonincreasing since it an infimum over nonincreasing functions. This means lim simsup Pmax (Ax) S Pmax (0) for any
sequence oς. 0.
20

---

Published as a conference paper at ICLR 2025
Now assume toward contradiction that there exists 0 and sequence (AE)EEN from R4, such that A - as - oo, and Pmax Pmax(As) S Parit c for all & E N. From the expression fmax 19 this means that for each k. there exists fo such that Eg_ (E, arg max= X S Perit By compactness of F with respect to || || we may assume (fk) kEN to converge to some f E In partieular, for ş E E. fk. -AsoEE, converges f as k CO.
Let & E E be arbitrary. (). 4 arg max= (f - Ac(g,-)) is outer semicontinu- ous with compact values (Lemma A.2) and с is jointly continuous, hence (A, e² (5, arg max: {f Ac(E, }}} is lower semicontinuous, see Lemma A.1 We then have lim inf inf (5, arg max= {fx - >xc((E,)))) c²(E, to ~ P. we obtain
By integration with respect
Pe~Ple" pc (5, max
max [*] S Pe-pllim k-+00
[lim i (E, arg max {/r - Auc(E, H))
lim inf Be-ple (5, arg max {fr - A
k-
S Perit
Since, Parit I Eqwple arg f")], this yields contradiction, and allows to conclude.
D.2
REGULARIZED WDRO: LIPSCHITZ MAXIMAL RADIUS AND UPPER BOUND
D.2.1 LIPSCHITZ CONTINUITY OF THE MAXIMAL RADIUS
For À 2 0, we consider the regularized maximal radius,
Pinax (A)
inf E.
JEF
Compared to the standard setting, the maximal radius is Lipschitz continuous, leading to estimate of the dual lower bound.
The following result is the regularized version Lemma D.I.
Lemma D.2. P (0) = Perit and P is Lipschitz continuous on R_ with constant
22 c
Fl + m2,cl [1Fl +min ( me 21
(p-me)e 1).
In particular, setting
3epers
T,e low
(20)
8
1 + m2,ce
[[]
+min
{
21 me (p-mate
The for all X E 2
then Piixx (A)
Proof. tt is differentiable with respect to À and we can verify that its derivative is given by
Tf(() cc((s))) log Ec A
JiC)- Aefe.c) cIAT
Ox T (A, = -E
L- Ac CTAT
{~
(:1E)
This gives Pric (0) P For f F and E our goal is now compute the Lipschitz constant of À + Ox ",, (. The Lipschitz constant of pinxx 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 À of un (). -(= (I(())+ec(s.)) E+Ar
LI
(2 (T2f(() + eTC(E,S)
(Tf(C) + +c(E)
6 c+x
XT+
(c Ar)3
21

---

Published as a conference paper at ICLR 2025
20 110-AdE50 ctar
We compute the derivative with respect to uf (A, () H
(0 (T((s)+ +c((E.5)
(A, -- (x)
*+AT
(e+ (7)
110) Aeté.5) cTAr
3. We compute the derivative of U3 A T log B ((moo(
(*A(())reete.c) (ct2r)²
((4)-20511))
(2(A) = (-
180) (cl-k))
Be
ctxr
Combining 1, and 3, we able to compute the derivative of OxpTie;
B [ (A, (e) (Oxu2(A, ()
R (..
US(A)
Bganol- 6) (2(22(A {)]²
E ())
(e+Ar)s
+f(C)+so(E.E) (ctAr]"
((0))An(E.))
+(()) c+Ar
(x
BGNNT(-11))
1
Tf(S) + cc(E.s)
Var (-Actt.)
6 + Ao
(Mr (+E)
is the variance with respect to A-AotGich
where Var
Aute.)) G *EX
(-12).
(-1))
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 E (they are therefore bounded by constant), see e.g. Theorem A.5.3 from Durrett (010). By the property of the variance, we obtain
( (*f(() ( +cd(s.)) 27
)
JoR (A,
E
1- CPAT
c
Ar
(11)
2
3
E
Aele
[ [ Pe((,c))))
(21)
(~T
(1S)
Now we bound the right-hand side of the last inequality. First, we have
[ots, 2)
- el
< m2,ce 1f
E Bemmo(l
(22)
On the other hand, by Jensen's 's inequality, we have
(e
Ame 1F etAr
E EswTo(-1e)
(23)
We have the alternatives
Amc c+Ar
< Aupme
gl in any case, and (p-mal mele
Ame
whenever > 0.
A+
This means
Am
< min
m.
F1
(p Je
Dividing
12 by 23 we obtain E <
(-
[c( < m2
min{
21 mo 21
1o To-mek mele
Je
(1E)
Reinjecting this inequality in 21
gives
22

---

Published as a conference paper at ICLR 2025
2 T (² (2,1))
21 +min
7. (o-mele })
2 31 my
1111
m22,e
L. (24)
[.))] is T--Lipschiz where This means that for f E F, the function g: (2, - Bx- given by (24).
We then show that P == seF g( f) is L-Lipschitz continuous. Let (A, E R², and let (fa)ken sequence from F such that g(X, fs) have for all N,
Piiax (M)) Then by definition of P we
k=220
P (A) - sx) S Sb) (X, S - X
Taking the limit as k 00 gives Priux (A) Pinax(() S L./2 - X Exchanging the roles of À and X' gives | (2) P (X) S T.Jx X1, hence Pinax is T.-Lipschitz.
Now, set 2 == sup {} E ER Pmax (A) 2 P Then either NTon 00 (in which case any
value A Niw satisfies the desired property), or by continuity of p p (2 Perit/ / and we T, have T 2 S Pmax (2 = Perit/ /4. Finally, we obtain 20
T:C
D.2.2 DUAL UPPER BOUND
The following result allows bound the dual solution above. This step specific to the regularized setting, see in particular Proposition F.4 which illustrates this requirement.
Lemma D.3 (Upper bound for the regularized problem Lemma Assume Aup = lo For all f E F and Q P(E). p-m."
> me and let
inf (Ap + (A, xE(0,00)
inf {Ap + E (1, xE(0.Aup)
Proof.
Let & E be arbitrary. Recall that
A, = EE
f-
T(()) + cc((..) 6 + AT
T log (g-xo(-16)
KCY dete.C)
<~o0
FEAT
(-1)
We bound - -A, above, uniformly in f F and & E E. For readability of the proof, we (-xe(e.)
set mg = To
with a slight abuse of notation. In this case, we have
(f(())ec(EE5) c Ar
(Tf(() - declE, 5) - -f((s) + +f((s) A(E+ Ar)
(c
(cw
S(C) Ac(Es()
X Bec [5(C]] - [RCCWROO1E)
++
|| oo
loog Bcworo(-1E) [c -
|| x
X(c+A7) (EESNTa(HE) Ao(E,
|| 8
+ eme X(c+ X7) c+
F||
(25)
where for the third line, we used Lemma and for the fourth line, we used Jensen's inequality. On the other hand,
-T log Be 8)
fic)-Ar(e.))
T
E BE (eNT - -xc(E
+ At
AT
|| + AT
< A(e + AT)
me
(26)
c AT
Summing (25) and (26 gives
F 10
-
(2..E(
+ me:
X
23

---

Published as a conference paper at ICLR 2025
whence assuming p me, and taking À Aup 2 p-m
obtain for all f E F and all ç E,
p Ox0" (Aup: f.E)-
Integrating with respect to a distribution Q P(3) yields
0 p @ ( f((),
which is the derivative at Aup of the convex function À + Ap + BE (A. f,E)). This means
inf (Ap + Be-Q (A, = inf xE(O,Aup)
f E (A, S1
xE(0,00)
E PROOF OF THE MAIN RESULTS
In this section, we prove the main results the paper. First, we establish the core concentration results in [.I that apply to standard and regularized WDRO. In particular, we establish the dual lower bound with high probability on the empirical robust risk. We deduce Theorems 3.1 and 3.2
E.2 by computing the generalization constants. In E.3 we obtain the excess bounds (Proposition 3.1
and Proposition 3.3 Finally, the results on linear models (Proposition 3.2) are found in E.4
E. 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 is, replacing o, v. Perits Pmax and Noow by 6z T5T.,, Perit P and Aoo respectively.
For À 2 0, we recall the expression of the maximal radius:
Pmax (A) inf
Re-rl- (AE))
JEF
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 Alow > O such that for all X E [0, 2. Pmax (A) 1 In particular, EE- 10 ΦA, f. Past for
all f F.
Proof. This comes from limx-+0+ Pinax (A) lemma D.2 for the regularized case.
Perit- See lemma
D.1 for standard WDRO and
Remark E.1 (Refining the degeneracy threshold). The constant Ato may be refined to fix another threshold than 4 Moore precisely, for any r E (0, 1), may also find Noo > 0 such that for all
X E [0, 2Mowb Praax
?Perit- We choose
in Proposition E. to be consistent with the
study of linear models from Section
3.2
For the next results, we define the following quantities:
+
T is the length a segment / such that @(A, E for all X E (Noo 2Ajow); }. f F and & E.
Ap + E ((A))
the length a segment J such that (ln f.E) for all y E (0, Aoo J.
and & E. Lap and Aup E [0, ox] are such that ((+,5)) is Tng- Lipschitz on [Rpp A F for all & E.
Let Alow be the dual lower bound given by Proposi- tion E We now to show this quantity a lower bound on the empirical robust risk:
Alox
x
2A
Figure 2: Bounding from below the empirical dual solution X expresses slope condition (thanks to convexity of the objective).
24

---

Published as a conference paper at ICLR 2025
Proposition E.2 (Dual lower bound with high probability). Under Assumption
let Now be 2.1
given by Proposition E.1 and Aup E [Nlow, 20). If S Park
C(o) where C(0) vn
96I BbIFFFll::lss +
Akow
24 Alow
/ log 3. then with probability 5, for all E F.
{xp+ EE E. 16 10(, f.e1 Aup)
inf
inf Ae(Aiomidupp)
{1p B 16(2, (.
Proof. The proof consists in using the convexity of o(:: S.E). Indeed, given a convex function over Rt, the infimum of g has to occur on an interval (Noos too| if g has a negative slope between Alow and 2Alow (Figure (2\iow) of ((oow))))
0
inf g = inf g()).
Alow
X2ww Alow
A20
We want this condition satisfied for the empirical Lagrangian function g()) Ap + Ep, (0(A, DI with high probability. For convenience, this can be expressed with the slope of E (o(.,
s(f)= p, [d( f]] pRp, [s<(Aoo []] S -p
(27)
Alow This the condition we aim obtain. To this end, we proceed by comparing the empirical slope to the true one, that sff) = Ep Ep(d(2Aee (f) -ppplpppploooa
We can show that any func- tion (f.E) + f.,, with À E R4, satisfies the requirements for the concentration theorem Theorem A.2 which done Lemma C.I and Lemma C.3 Consequently, we can apply the concentration theorem twice, on each function <(2 and @(2)low; 's' ;)), to obtain that 3(f) approximates s(f) with probability at least
Atow
2'
vf F, 8(f) sf)+ Vn'
where C(6) will be computed afterwards. On the other hand, s(f) Ep10
((2) f)] by hence we
convexity of Φ. hence s(f) S -Perii
Perin by Proposition E.1 This means 8(f) S vi 4
Pers
have the desired condition 27 when < Fe
Perit
& for all Clai and with probability at least 1 3.
inf Aup))Aup)
{2o ( (o
S.11)
inf Ae(r
{Ap+ E,_
Concentration constant C(8). We now compute C()). Let E (Noo 2. By Theorem A.2 we have with probability at least 1 4. for all f E FF
48I(F, |1 1lo)
2 log 1
E E (o(2)oow f.E)]
f. s
+ ob
(28)
Vn
n
and with probability least 1 6. for all f FFF.
4SI || (loo)
2 log
Ee-r (eer((((nne (Nloow (( Re-.. (1() [,E)] Vn
$1
(29)
We set (8(8)= = 4SI(F, (1.F,)1111o0+ + + / 22og J. Intersecting the events probability 8 for all f FFF
28 and
29
we obtain with
E E. (2) {.() - E Pr P., (ob(Aoow S.5)]
Alow
$ Alow BgnPlo(2.0 f. (ooo f.E)++ 2C'(8)
Vn
< BEqxPl0 (22Xiow fooowff()) f.E)++ (C)(6)
Noow vn
< Perlt
+ (8)
(30)
Noow Vn'
25

---

Published as a conference paper at ICLR 2025
where we recall that for Alow 0, satisfies for all A E [0, 2Xoww and all f E F, Egmpl0* ((), $ Penit This means C(6) = 2C (6)/\1ow and we have the desired ex- pression.
This implies a generalization bound on the dual problem of (regularized) WDRO:
Proposition E.3 (Generalization bound on the dual problem). Under Assumption 2.7 let Alow be given by Proposition E.1
If
B(6)
I p S
Perit
C(d)
where
Vn
vn
( 48
I(F: || (lac)
Xlow )
2 log 8. + ///
.C(6)=
961(FrI1-lbx)
2
2log 8¹
Nlow
Atow
then with probability at least 1 for all f FFF,
{ x (2(p-
B(6)
inf
{ap+ (oAA z inf X,(0,00)
+ P.
vn
Proof. We assume Xup > Alow- By Theorem A.2 applied to (1, + uó(w (f,E) obtain with probability at least 2.
B(ő)
an =
sup
P1b E [e, f. S vn
(31)
(E 1xF
where B(8) = I8 Noow x F, dist) + v v log and dist((u, f), (4', f')) = 11 1l1 +
Ilf loo. Furthermore, have the inequality
1 (1 + 21og 2) S I(F (1,,)) + 2Alow
2
X x F) s I(F,11-111) +
Alow
Lemma A.3
hence we may refine B(6) as B()) 48 [[FF 11 11o0
2 Xtom
+ V
2 log 2
By Proposition E.2
if < Part 4 vn then with probability at least 1 - 5 for all f E FF
C(8)
inf AE(O.Aup))
{Ap+ + R EM o (A, 1.11] = inf
AE(Aron Aup)) {2p + R 1e [:
(32)
Finally, combining
32) and 31 and if
B()) Vn
Perit
C(a) Vn
Sps
4
we can write with probability 1 1- 8, for all f FE
inf {Ap+ + +lp+BeWA (0,, (0AA xe()
{ap+ E + E. E. (0(A, f.513
inf Ae(0,Aup)
Ap + Be- - A Be-p(((A, Egw (o(A,,
inf \a(M inf Ae(Atomidap)
Uxp Po f.E) - dan
{x(p p
B(0)
iul dupp)
+ +EG-plO(A, 1.11]
Vn
B(8)
inf xE(0,00)
+ BE (1E1
Vn
26

---

Published as a conference paper at ICLR 2025
If Aup Nlow this means, by convexity of the inner function,
inf {2p+ E. E,, [o(A,
Noow + E. ( Atoo f.E)
Xe (0(0,upp)
Nlo (p a'n) + Reggr((l ((oo f,()
{ {2(0- 0 B(0)
inf xE(0,00)
+ (E
vn
where we refined an into ai supyer (gw f:E]] - B P. (((()ou-FE)))
E.2 GENERALIZATION BOUNDS
We are now ready to prove the generalization bounds. The following is extended version of the generalization result standard WDRO (Theorem B.T). Note that the extended bound (33) involves a control of R 3/ (f), which means that (f) also generalizes well against distribution shifts.
Theorem E.1 (Generalization guarantee, standard WDRO). Under Assumption 2.7 there exists
Alow 0 such that if
Perit
B
< 4
n
where
48 (11
[IFF) 11.0)
Nrow
+
2 10c
Alow
2 llog
3
411
2 log 4.
Alow
Nlow
then with probability least 1 - for all E
Rp(f) 2 Rp-
(33)
In particular, for any p and n 16(a + /) with probability at least 6, Rp(f) 2
Vn
(g)r all f E F.
Proof.
Under Assumption 2.1 let Nlow be given by Proposition E.2 Our goal is to apply Propo-
sition the standard WDRO case and compute its constants thanks Lemma C.1
By
Lemma we have the following constants:
+ 2 Flooo
V Fl
Ajow
Amp co, and Ly || 30 X
a corresponds to B6)) in Proposition E.3 and 3 corresponds C(6), whence we obtain the desired expressions for and / with the quantities above.
By strong duality, Proposition B.1 Ry(f) and Rf( admit the representations
Ro(s) inf xE(0,00)
(Te (g.r(o(A.f..)
inf Ro(f)=
sxe E E P. (o(A.
xe(0,00)
for any 2 0 and E F. By Proposition
E.3 if
< <
Pari
then with probability at
Vn
least 1 5, we have for all F. R₂( > R
(f), hence the first part of the result.
27

---

Published as a conference paper at ICLR 2025
As to the last statement, if 16(a + / in Posts 3 For any
< Perit e
vR with probability at least 1 6. (J) > [gnP[[(E) for all f E F shown previously, For 2 Parts v since the quantity (f) is non-decreasing with respect to p. we also have Rf(() 2 (E))
v
v
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.7 there exists Alow> > such that if
T.E Perit
max
Me:
p
Vn
where Th and BT are the two constants
2 20 M
2
a T. 48
|1 +
I(F.
(5.11.1100) +
Mow
c(p mc) + 2T |F
low
T.C
21
+ me)
V
2 2log
You
96I(F,11 (1oo)
||
4 + me) V 220g 8¹
gT
+4
Now
low
then with probability at least 1 1 for all E F.
(
(f) 2 RT.e
are (f) 2 Ec=olf(()] -eDk((())lDedxT
p- vn
whenever (T)P,Q) S p.
In particular, if me < Puji and 16(0""=3reey (Perl 4m..² then for any p max mc: 7 with proba-
vn
bility at least 1 - 8, for all Q such that (P.Q) S p. R p (f) 2 Ec-olf(()) - cDKL ( P.P (T) for all f E F.
Proof. Under Assumption 2.1 let Now > 0 be given by Proposition E.2 and assume p > me. As for standard WDRO, our goal is to apply Proposition E.3 and compute its constants thanks to
Lemma
C.3
By Lemma
C.3 and taking Aup = p-me we have the following constants:
21
+-
11
(-1[FFl> 2 1l + NTo me)
2|| + me Xjow
Amp
Fl p-me
and Lap = |1 +
1 + X e(p (-p-ma)+ +f-mm))+2Fl1
2/|
In Proposition E.3 Te corresponds B6)) and f corresponds C(8) with the quantities above. In this case, we easily verify that T. and . have the desired expressions.
By strong duality, Proposition B.2 and by the dual upper bound, Lemma D.3 (F) and (F) admit the representations
(T)(f) = inf >E(U,Aup)
the (A
(T) inf xE(0,Aup)
{ {re ( 10 (A, f.
for any 2 0 and f E F. Recall that p m If furthermore
tte Vn p < P
gr
then with
vn
probability at least 8, we have for all f E F, (f) 2 R 3th (f) by Proposition
E.3
hence
obtain the first inequality.
28

---

Published as a conference paper at ICLR 2025
Now, toward the second inequality, let Q E P(3) such that (2 Let E P(E x E)
satisfying [x = P. | 2 Q and ( [c(5 + T = (P..
We finally obtain for all f E F, R (f) 2 B [f())] - = 1
As to the last statement, if m.
TLe
and =
Pen 4me)² then max mes Vn
T
Tie
T
Vn
For any max {
me: /a <
Pezit
go
the bound holds by the first part of the result. For Vx
p Pert g
since R (f) non-decreasing with respect p. the bound also holds.
v
E.3 EXCESS RISK BOUNDS
In this part, we prove the excess risk bounds (Proposition 3.1 and Proposition 3.3
The proofs
consist in adapting the previous proofs of the generalization bounds. For standard WDRO, the general excess bound specializes in the case of Wasserstein-P costs and Lipschitz losses.
Theorem E.3 (Excess risk WDRO). Let a be given by Theorem E.1 Under Assumption 2.1 if
Perit
then with probability at least 1-10 for all F.
Vn'
(f) S R (f).
In particular, if d(..-), where p 2 1, and there exists Lipy Lips-Lipschitz with respect to d, then
0 such that every f E F is
Ro(f) s Be-P[s(()) + Lip=
a Vn
p
Proof. By definition of Aoo and Proposition
E.1
we can write for any 0 < p' < Pun
(f)
inf XE( Aup)
(Ap' + (.
leading to
inf (₂) = xe xe dup)
(Ap' + FEEr
E EA (0(A, - Be-Plo(A,
inf inf Xe(Aiom:Aun
Ap + +R (6(A, -
ADl + Ne'+BewP. 10(1, [, -aa
(x B(d)
inf xe Ae(Aiom dup))
+ E f.
Vn
inf xe(0,,0)
x 0f'
B(8)
+ Eg
1o f.5)
R Big (f). vm
Vni
whenever p' > B(8)/ and the inequality holds with probability at least 1 d for all f f F.
- leads to the desired Recall also that B(6)- = a (see the proof of Theorem E. Taking p' = v
result as long p vn
Buii
Toward proof of the last part, assume that any i Lipschitz with constant Lip and d" with 2 I. For any couple (E, () E E E, we have
f()) S (() + Lipy d(E,)) C).
Integrating over an arbitrary coupling with first marginal P and second marginal Q satisfying W.(Q, P) S p a/ V gives
Bols] < [P(s] + Lip B2 S Epls] + Tip E, [c]=
where we used Jensen inequality. For any Q satisfying W.(Q, P) s p a vr, taking the infimum in the above inequality over such couplings gives
[qls] S Er(s] + +a//))///j
hence we obtain the result by definition of R (f).
29

---

Published as a conference paper at ICLR 2025
Theorem E,4 (Excess risk for regularized WDRO), Let a be given by Theorem E.2
Under
P ais V
Assumption 2.1 if me < P
then with probability at least 6, for all f E
R
R aT (f). VR
Proof. For p > me, strong duality holds (Proposition B.2 standard WDRO setting (Theorem) E.3
The proof is then identical to that of the
E.4 GENERALIZATION CONSTANTS OF LINEAR MODELS
The two following results correspond to Proposition 3.2 which is the estimation of the constants Perit and Alo for linear models in the framework of Shaficezadch- Abadeh et al. (2019). We assume the support of P belong an Euclidean ball of diameter D centered zero. We then define = as the closed ball of diameter 3D centered at zero.
Proposition E.4 (Linear regression). Consider the parametric loss f(0, (z, v)) where 0 belongs compact subset & C RR, and the transport cost c 11 Assume there exists w 0 such that
(00,z) - y)²
inf (0,-1)11
Then Theorem
3.1 and Proposition
3.1 hold with Perit 2 D2 and Nlow 2 4
Proof. In this setting, the expression of Pinax is
Prnax (A) = inf E min |15 - 1'11 ç' arg mag Alls- - c11²) -(1p3 | 6E
<e=
For any & and 0 O the term inside the argmax writes
f(0,C) AIE - <11 = (M - X/C + 2-
Consider Ç = (u, v), { = (mo, No), u, R. the representations in an orthonormal basis of IR", such that the first element (0. 100-11//1 1) (8, 1] the eigen vector M. We can write the above equation with and terms:
f(0,C) AllE 211 (I((0,-1)1
-1)11 Aju² 2Au uo A1ol12 2X(U, vo)
(34)
If A S w then we have [00,, 11)12 - > 0, hence the maximum of f(0. AlLa c with respect to Ç is only attained at the boundary of =\t (otherwise we could increase the quadratic term with respect to u). For all À S w, we thus can bound from below
Pinax (A) 2 Em-r(mmn ||g - <1i ||||| = =[I1=3D/2] 2 D2.
In particular, Perit of Alow (Proposition E.1
D2
We also remark that Parit 4D2 hence have 2A w by definition
Proposition E.5 (Logistic regression). Consider the parametric loss f(0, (x, v)) = log( [ + --(00a)) where 0 belongs to compact subset ④ C IR, and the transport cost = =l - Assume there exists w such that
inf ||0|| 2 w.
#Ee
Then Theorem 3.1 and Proposition 3.1 hold with Perit 2 D2 and Nlow 2 81 where Ω
supace |101|2.
30

---

Published as a conference paper at ICLR 2025
Proof. For the logistic regression, we have
{( - 2/lk E|I = log + el0.1)) X/< - -
(35)
Consider the representation = s0 + v, where E IR and is orthogonal to 0. Then we have
f(0, <) -lls- =1|² log (1 + e=1lo1")) s² ||llak 2sA(0, <) AlIo E11
The second order derivative with respect is
|0||
1 + e + + 21110113.
(36)
The term (1 + (1+e e+lle1)) (1 e-
=|1013) is lower than 2(1 + el+1119 2 < 2( c Hence we easily
deduce that (36) is positive for all < E
a(1+tDo) If this condition holds, then maximizers
of f(0, () - lLL - E for Ç E E are included in the boundary of E, meaning that Pruax (A) 2 D2 1
4(1+eDa) Since Perit I 4D?, then 2A 2 4 [++.
F SIDE REMARKS
This part contains results supporting various remarks made the main text.
F.1 INTERPRETATION OF THE CRITICAL RADIUS
The results this part justify the interpretation of the radius made in Remark 3.1 and Proposition F.3 Proposition F.1. If p 2 Perit, then there exists f E such that
Ro(f) = maxx ((E).
EEE
In particular, in the setting of Theorem 3.1 if 2 Perit + V.. with probability at least 1 - 5, there exists f E F such that
(f(
max f(E). EEE
Proof. The first part is identical to the square cost case, see (Azizian et al. 2023a Remark 3.2). The second part is obtained by Theorem E.I in the setting of Theorem E.I we have with probability at least 1 5, R,) Rp-a/vn for all f E F. Hence p 2 Peri: + a Vn, we obtain the result by applying the first part to the radius a/ Vn.
The following result gives an interpretation of the critical radius Perit in regularized WDRO appear- ing in Theorem 3.2 We show that when the radius p is larger than this value, then some robust losses become degenerated. Precisely, they become independent of and are equal to regularized version of the worst-case loss max= f.
Proposition F.2. Assume p 2 Perit. Then there exists f E F such that
RT)
sup (B<>)s)/((() - -cDKi( xEP(ExE) [=|==P
In particular, the setting of Theorem exists f E F such that
3.2 if 2 Pentt + a vn
with probability at least 1 5, there
RT)(())
sup rEP(ExE) [=|=
(Bew))) - -(0((())eDDDa -eDK((Tl(To)
31

---

Published as a conference paper at ICLR 2025
Proof. In the regularized case, verify that the critical radius has the expression
The Perit
inf JEF
(Be-p [ (11))
(()) + c(S, log Be no
(37)
Let f FF be arbitrary. Consider coupling *" P(E E) such that [T"]1 = and x (-KE) vo (-IE) for almost all E. We first verify that for
for instance the proof of Lemma D.2
a good choice of f, it is included in the uncertainty set defining (
We compute (n" |[ Below, we set Z(E) == (c
10
DKL(x"||To)) BEND
E
SoUTO (-15)
L
log
I(E)
f(5)
[16)
BEND
E
log Beg (-15)
SNOTO (-15)
[(())
Bear log R (o0
(38)
This leads to Ex [c] + DKL (x [[=0) = BENP E ( [((() + clS. c0] log Be (-1c)
+((())
which is the term in the infimum 377. Since f was chosen arbitrary, this means that if p > Porit then there exists f E F such that the coupling x* defined above (depending on f) satisfies (T= [[T))) $ p. and we obtain
B(E.c)~r. ic(E, ()) + T TDII. (TT"
(F) 2 1e (
On the other hand by the computation (38), we have
R (f) 2 Be- [f(() - eDu (x (| elea~p [log B 1o (-16)
3(3) ]]
(39)
By Donsker-Varadhan variational formula Donsker Varadhan 1975), for almost all & E E, we have
log E (- E
sup vEP(Z)
(40)
Reinjecting
in 139 gives
(f) (f) 2 P.
sup PEP(E)
{ (Ec=o/f(()/d (B (xa((()(m(((E)))
[Eę~ [B(n((1e][(()) (cDi((((())(()))
sup =Ex(E |=|==
(Bewi)jal(())) - (xl1o))))))
sup xEP(ExE) |a/=
where we used the chain rule for DKL divergence (see c.g. Theorem 2.15 in Polyanskiy & Wu. ): (TI(TT
(e= +
D [|] 2 Be (T())
Since we clearly have & S
sup (Ben(n)a [S()] e (x]l(=/llm))) (m|[)))) this yields the first part.
TEP(ExS) -=]=
The second part a direct consequence of the generalization bound Theorem E.2 as for the standard case (see the proof of Proposition F.I).
The following result allows to interpret Perit fluctuations measure on F: Proposition E.3 (Critical radius and loss fluctuations). Suppose supp = E. Under Assumption 2.7 Parit > if and only if F contains constant functions.
32

---

Published as a conference paper at ICLR 2025
Proof. We prove the equivalence by contraposition. For the first implication, assume there exists E F such that for all & and ( in E, f(E) = =(()- This means for all & E we have & E arg mrg f, whence min (c( Ç arg max= f) 0 because c(g. 0. By integrating with respect to Ç P, we obtain Perit = 0.
Now, towards the other implication assume Parit 0 and show that FF contains constant function. Let (fx) be a sequence functions from F such that
E min (ot..s) : S arg max fie fa)] 1-000
O.
By compactness of F. Assumption 2.13, we may assume (f*) to converge to some function f for the norm lls.. The set-valued map f + arg f is outer semicontinuous with compact values (I (Lemma A.2) and is jointly continuous, hence for any & E E, the function + min (c(E. CE arg maxe f lower semicontinuous on F, see Lemma A.1 Thus we have
{ ((E,5) E arg max fie
min { ((t, arg arg max f"
lim inf min
R-000 by lower semicontinuity (see Definition A.I.
By integration with respect to & ~ P. we have
0 lim inf B k-+00
min
((.c) E max Sk
2 BE-P
lim inf min k-+xc
c(E.C) ( arg fie
2 R
min c($, : max l") =
hence Egpp [min (c(5,5) : Ç arg maggaaxFaa f"] = O. Finally, for P-almost all { E E, min (c(E.C) arg max; f*) O. This means by compactness of arg max: f* that arg max= f for P-almost all & E E. Since supp P = and f is continuous, we obtain that f is constant.
F.2 NECESSITY 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.4. Consider 0, 0, E 00, 11. c(E, <) = K5 <) and assume that the reference distribution is truncated Laplace (o(d((E) x e 15-5 (o.j(S)CC. Assume furthermore F is
family of functions from [0, 1] to IR which satisfies e 21 2
Then for almost all g [0, and all E - 7) (J,, not Lipschitz at 0+.
Proof. Let (0,1) and f E F. The expression of the derivative of of with respect μ given by 16):
(ec(g.)
pfic)-oft.e) pe
0 (1,, f.E) E
#f clew) me
+ log (
(NoT
(-EE)
μee
In particular, it satisfies
0 (1, S
21
Te(E, {)
+ log E (1())
<f6.c)
+ ||
(41)
(-1E)
On the other hand, by Donsker-Varadhan formula Donsker & Varadhan
1975), we can write
log (c
c(E.C)
E
mate.s)
-c(E,5)
DKL
To
-ele..)
(-15)
no To(-1E)
C~
(-1E)
33

---

Published as a conference paper at ICLR 2025
2 gives
Reinjecting this in (41 and using e
0 (1, < |F DKL.
(mO
To
cfeml
mt
(-15)
Consequently, to prove non-Lipschitzness of 6o
(.E) (.
O. we show that
<ie
DKL "0 (-15) To(-1E))
+ 00
as μ + We show that Fu compact support. With the change of variable u t- م- we have
(-15) converges in law to 6g. Let up R. -> R be of class Co with
L.
E 1E=91
p({)d< pe / 11s2 Ly (u)e ((u))--"ll(( + ueu)du.
Also, we easily verify that
15-C1 dc
/ - dc {' - dc pe - -c -(1-8)
0
hence we obtain
Jg. 1 &.1,,,((uee (u)e + peu)du
E <~K
K-d
[p(()]
(1--2
(42)
e
We then have the following:
(1-4) 2 - -eTia jee
converges to 2 as O,
For all TR, (لs و
(w)e sp( p du converges e-Iuly((S) as μ -> O, hence
pe
its integral with respect to u converges to 2x((E) by dominated convergence theorem.
Combining both limits in
42 gives E
[p(()] ((E). This means that T (-1g)
{~mp
(-10)
converges in law to ōg. We have DKL (de (o())))) = oo, hence by lower semicontinuity of the DKL- divergence for the convergence in law (or weak convergence), see e.g. Theorem 4.9 from Polyanskiy
& Wu. (2023), we get DKL.
To
me
(-15)
To mo(-15)
cc. This means that (+, is not и=0
Lppschttz near 0.
F.3 ON CONTINUITY OF MAXIMIZERS
We justify the importance of relaxing Assumption 5.1 from Azizian et al. (203aa) which corresponds to compactness of F with respect the distance Dz(f.9 g) ff gllox oo + dy (arg max= f, arg max= g). We show that this condition is actually equivalent to assuming con- tinuity on f ++ arg max f, which a strong condition and difficult to verify in practice.
Proposition F.5. For (f.9) E F, define
Df(f.g) = II gllos + d (arg max f, arg max
where dæ is the Hausdorff distance the set of compact subsets of E, K(E) Assume (F, || (loo) compact. Then we have the equivalence
(F, Dx) is compact + f + arg max f is continuous from (1o0) to (KC(E),
34

---

Published as a conference paper at ICLR 2025
Proof. We prove (=). Assume Dy) is compact. Let f E F, and let (gk)keN be arbitrary sequence from such that 9k converges to for lllo. We want to show that arg max 9k converges arg max= f for dæ, proving the continuity of the arg (F, Dr), (9x) kEN admits accumulation points for Dr. Let h be any one of them. We may extract a subsequence from (gk)ee converging h, say you k-000
map. By compactness of
h E F. In particular, Ia, converges h
for || ll.. We necessarily have f by definition of the sequence (ge)ReN. means that (gk keN admits only one possible accumulation point for Dy, which is f. This implies Ok converges to f for Dr, hence arg max 9k converges to arg max= /.
Now, we prove (-). Let (Jk)KeN be sequence from F. By compactness of (F, |1 we may extract converging subsequence Jnu + I for || llxo. Assuming f + arg maxg continuous
k-+00 gives that arg maxe Iny converges arg maxe f. which is the desired result.
35


Reviews:
[{"review_id": "UB7x1jbnJK", "reviewer": "Reviewer_tSiX", "summary": "This paper presents novel bounds on for the DRO loss using the Wasserstein distance. In particular, they address the question of finding the minimal $\\rho$ used by the empirical robust loss such that the loss is an upper bound for the actual population loss. The main challenge is to overcome the dependency on the distance between W(P_n, P) \\sim n^{1/d}. While this problem has been studied in the literature, and dimension free bounds exist, this paper presents a proof requiring weaker assumptions.\n\n\n\n\n---------- after the rebuttal ------------\n\nI thank the authors for their response and increased the score accordingly.", "questions": "I am happy to increase my score and support this paper with a high confidence if the authors can provide an extensive discussion during the rebuttal on the assumptions in Azizian et al. (2023a) . In particular, my two major questions are: can the authors be more precise in which cases their assumptions are weaker than the ones in  Azizian et al. (2023a). In particular, can you give an example for a class of distributions that are covered by this paper but not by  Azizian et al. (2023a)? Moreover, can the authors explain why the proof in  Azizian et al. (2023a) breaks for your assumptions and why it is not trivial to extend the proof?\n\n\n\nSmaller question:\nIsn't assumption 3.1 (1) always true satisfied by w<=1. Is it possible that this is a typo?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper addresses an important problem is generalization bounds/theoretic ML. In particular:\n\n- The paper is well written and the results are nicely presented. \n- The proof sketch in Section 4 is excellent. It is very easy to follow and often neglected in these types of papers\n- The proof idea is smart, non-trivial and interesting.", "weaknesses": "Given that this is a more traditional field, I would expect a clearer comparison with the existing works. While the authors do a very good job in presenting the proof idea, it is not so clear how the proof fundamentally differs from existing works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NecMRzUaX9", "reviewer": "Reviewer_tsmX", "summary": "This paper provides exact generalization guarantees for Wasserstein Distributionally Robust Optimization (WDRO) for a wide variety of models with compactness and finite Dudley's entropy assumptions. The results apply to radius $\\rho$ scaling as $O(1/\\sqrt{n})$, which does not suffer from the curse of dimensionality. The results also cover the double regularization case.", "questions": "- What are the practical implications of the generalization guarantees compared to Azizian et al. (2023a)? Can you provide some numerical results analogous to Appendix H of Azizian et al. (2023a)?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The generalization guarantees of this work do not rely on restrictive assumptions like smoothness compared to the previous work (Azizian et al. 2023a). \n- This paper is well-structured, and the theoretical results and proof sketches are clearly presented.", "weaknesses": "- In Section 3.2, the authors discussed how their results on generalization guarantees apply to linear regression and logistic regression. However, more complicated models such as neural networks with ReLU or other smooth activation functions (e.g. GELU) are not discussed. \n- The theoretical results require a lower bound on $n$, while Theorem 3.4 of Azizian et al. (2023a) applies to all $n \\ge 1$. The implications of this requirement should be discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5UxCNRgZh6", "reviewer": "Reviewer_hWjP", "summary": "The proposed paper provides lower bounds on the robust empirical risk under unorthodox but interesting scaling limits on the radius of the Wasserstein ball around the empirical risk.  The paper uses some cool techniques which are not often seen in machine learning.  \n\nThe paper is relatively clearly written.  However, I think there are a few little things here and there which are either difficult to justify (in the current form) or perhaps not well-defined (see below). Also, the introduction is excessively general while the setting rapidly collapses to a much more specific setting shortly after.", "questions": "- Why not submit to JMLR?  The paper is very rigorous and rather long and technical for an ML conference?  You also examine the problem in good detail.\n\n- Could you provide a simple example in Theorem 3.2, where the optimal coupling is known under (say) Gaussianity assumptions?\n\n- I'm a bit confused.  What does $\\operatorname{argmax}_{\\Xi}\\,f$ mean in (5) a sup norm or something?  \n\n- Why is $\\min\\{ c(\\xi,\\zeta): ... \\}$ measurable?  In particular, (independent of the meaning of the argmax, above question), why is there a measurable selection $\\xi\\mapsto \\zeta$?  Without this, its not clear that $\\rho_{\\operatorname{crit}}$ is well defined.  I'm guessing this is Berge's theorem (which is in Aliprantis & Border) somehow, but please spell it out for us :)\n\n- Each result assumes that the (difficult to interpret) $\\rho_{\\operatorname{crit}}$ is \"large enough\".  Can you please provide a general set of conditions ensuring that $\\rho_{\\operatorname{crit}}$ can be bounded away from $0$. \n\n- Is it fair to compare, verbally, our results to those of Fournier et al. (and similar bounds, say, found in [1])?  Since you are considering a small ball around the empirical measure while their results guarantee a minimal radius such that the empirical measure contains the true measure whp.   Furthermore, those rates are only tight (afaik) when the measure is very spread out; more precisely, it is Alhors $d$-regular, see e.g. [3] for a nice clean proof.  \n\n- In theorem 3.2, why is $\\pi^{P,Q}\\ll \\pi_0$?  To be this isn't directly evident... I.e.\\ why is the RHS not trivially $-\\infty$ in general?\n\n\n\n[1] Graf, Siegfried, and Harald Luschgy. Foundations of quantization for probability distributions. Springer Science & Business Media, 2000.\n[2] Otto, Felix, and Cédric Villani. \"Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality.\" Journal of Functional Analysis 173.2 (2000): 361-400.\n[3] Kloeckner, Benoit. \"Approximation by finitely supported measures.\" ESAIM: Control, Optimisation and Calculus of Variations 18.2 (2012): 343-359.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well written, interesting, and theoretical and provides very nice lower bounds on the robust empirical risk.  The results are nice, and so is the use of set-valued analysis to derive them.  Several relevant examples are considered, making a large portion of how these results can be used nearly transparent.", "weaknesses": "Nevertheless,  I think some of the assumptions are a bit opaque (see below), and I'm not certain some quantities are well-defined.\n\n*Minor*\n- Citing Cuturi and Perée's book is odd when mentioning the Wasserstein distance.  Perhaps the original source or a book on optimal transport such as Villani's book, would be more natural, IMO.\n\n- The definition of Wasserstein distance circa (1) is incorrect, $\\Xi$ must be Polish, and  c *must* be a power $p\\in [1,\\infty)$ of a *metric* topologizing $\\Xi$; what you write is just some transport problem.  Eg if c is not symmetric, then $W_c$ is not a metric in general, or if $c(x,y)=0$ for all $x,y$ then $W_c$ cannot separate points.\n\n- Perhaps \"suitable\" distributions is more appropriate before (1), since the distance explodes if these have no finite moment. \n\n- Line 65: bad grammar: \"it does not introduce approximate term\" also imprecise.\n\n- Line 66: Is Wainright's book and Boucheron the best reference?  Perhaps older papers, e.g. on VC dimension, Bartlett's old papers on Rademacher complexity, or old papers on chaining are more natural references?\n\n- Line 69: \"This theoretical feature is specific to WDRO and highlights its potential to give more resilient models.\" This can be **much** less hand-wavy.  Please explain more precisely/mathematically.\n\n- Line 149: In a metric space $(x,..)$ not \"In (X,..) a metric space\".\n\n- Assumption 1 vs. Line 145: You say that $\\Xi$ is just a measurable space, then later you say its a compact metric space.  Why no   be forthright and say its a metric space on line 145.  Similarly, why is $\\mathcal{F}$ an arbitrary family of functions, then straightaway after is actually a compact set of continuous functions.\n\n- Line 176: Why jointly Lipschitz?  If $\\Theta$ is compact, then since you already assumed $\\Xi$ is compact, then it is enough for $\\Theta\\times\\Xi\\ni (\\theta,\\xi)\\mapsto f(\\theta,\\xi)\\in \\mathbb{R}$ to be continuous; to deduce the compactness of $\\{f(\\theta,\\cdot):\\,\\theta \\in \\Theta\\}$ by the currying Lemma.  \n\n- Line 176: Not sure why you say \"if $\\Xi$ is compact, since this was assumed a few lines earlier on the same page.\n\n- Maybe more natural examples come from Arzela-Ascoli...\n\n- Should the definition of the Dudley entropy integral really be in a footnote, while more basic ideas are in the main text.\n\n- Line 221: The words \"the metric\" are missing.\n\n- Line 223: There are many more references of the use of this type of metric, especially in exponential convergence rate results for Markov chains (wrt $W_1$ over countable metric spaces with this distance).\n\n- Line 245: \"sample randomness\" (I know what you mean...but the word independent is misleading as this \n\n- Assumption 1: Why call (2) jointly continuous, it is just standard continuity (actually inform continuity by compactness).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)