Exact Generalization Guarantees for (Regularized) Wasserstein Distributionally Robust Models
Authors: Waïss Azizian
Franck Iutzeler
Jérôme Malick
Venue: NeurIPS 2023 poster (2023)
Keywords: robust optimization
distributionally robust optimization
optimization under uncertainty
generalization
Wasserstein distance
optimal transport

Abstract: Wasserstein distributionally robust estimators have emerged as powerful models for prediction and decision-making under uncertainty. These estimators provide attractive generalization guarantees: the robust objective obtained from the training distribution is an exact upper bound on the true risk with high probability. However, existing guarantees either suffer from the curse of dimensionality, are restricted to specific settings, or lead to spurious error terms. In this paper, we show that these generalization guarantees actually hold on general classes of models, do not suffer from the curse of dimensionality, and can even cover distribution shifts at testing. We also prove that these results carry over to the newly-introduced regularized versions of Wasserstein distributionally robust problems.

Exact Generalization Guarantees for (Regularized) Wasserstein Distributionally Robust Models
Waiss Azizian, Franck Iutzeler, Jérôme Malick
Univ. Grenoble Alpes, CNRS, Grenoble INP Grenoble, 38000, France
firstname Sesttteeeuii--rrennbaeee alpes fr
Abstract
Wasserstein distributionally robust estimators have emerged powerful models for prediction and decision-making under uncertainty. These estimators provide attractive generalization guarantees: the robust objective obtained from the train- ing distribution is an exact upper bound on the true risk with high probability. However, existing guarantees either suffer from the curse of dimensionalityy, are re- stricted to specific settings, or lead to spurious error terms. In this paper, we show that these generalization guarantees actually hold on general classes of models, do not suffer from the curse of dimensionality. and can even cover distribution shifts testing. We also prove that these results carry over the eewly-introduced regularized versions of Wasserstein distributionally robust problems.
Introduction
1.1 Generalization and (Wasserstein) Distributionally Robust Models
We consider the fundamental question of generalization machine learning models. Let us denote by fo the loss induced by model parametrized by 0 for some uncertain variable & (typically data point). When follows some distribution P. seeking the best parameter writes as minimizing the expected loss
min [g-r[So(E)]- 8EB
We usually do not have a direct knowledge of P but rather we have access to samples (E:) independently drawn from P. The empirical risk minimization approach then consists in minimizing the expected loss over the associated empirical distribution P.. =n Ei (as a proxy for the expected loss over P), i.e.,
(- (- (o(S))
min (o(EE)
PEB
Classical statistical learning theory ensures that, with high probability, Ep(fe] is close to Ep, [fa] up to (L//V)) error terms, see e.g., the monographs Boucheron et al. (2013); Wainwright (2019).
A practical drawback of empirical risk minimization is that it can lead to over-confident decisions (when Ep, [fo] Er]foo. the real loss can be higher that the empirical one (Esfahani and Kuhn, 2018)). In addition, this approach also sensitive distribution shifts between training and ap- plication. To overcome these drawbacks, an approach gaining momentum in machine learning is distributionally robust optimization, which consists in minimizing the worst expectation of the loss when the distribution lives a neighborhood of P,:
min 6cB
sup Be-q(fo(())
(1)
QEU(P..)
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

where the inner sup is thus taken over Q in the neighborhood of Pn in the space of probability distributions. Popular choices of distribution neighborhoods are based on the Kullback-Leibler (KL) divergence (Laguel et al., 2020; Levy et al., 2020). kernel tools (Zhu et al., 2021a; Staib and Jegelka, 2019; Zhu et al., 2021b), moments (Delage and Ye, 2010; Goh and Sim, 2010), or Wasserstein dis- tance (Shaficezadeh Abadeh et al.. 2015; Esfahani and Kuhn, 2018). If P E U(P.). distributionally robust models can benefit from direct generalization guarantees as,
[e-O(fo(EE] 2 Bg-r(fo(E))- QEU((P))
sup
Thus, for well-chosen neighborhoods (PPP). w), distributionally robust objectives are able to provide exact upper-bounds on the expected loss over distribution P, i.e., the true risk.
Wasserstein distributionally robust optimization (WDRO) problems correspond to (1) with
u(Pp)) = {o E P(E) : W(P,,, Q) sp:
where W(P,, Q) denotes the Wasserstein distance between P, and Q and p > controls the re- quired level of robustness around P,.. As a natural metric to compare discrete and absolutely contin- uous probability distributions, the Wasserstein distance has attracted a lot of interest in both machine learning (Shafieezadeh Abadeh et al.. 2015; Sinha et al., 2018; Shafieezadeh- Abaadhh et al., 2019; Li et al., 2020; Kwon et al., 2020) and operation research (Zhao and Guan, 2018; Arrigo et al., 2022) communities; see e.g., the review articles Blanchet et al. (2021); Kuhn et al. (2019).
WDRO benefits from out-of-the-box. generalization guarantees in the form of (2) since it inherits the concentration properties of the Wasserstein distance (Esfahani and Kuhn, 2018). More precisely, under mild assumptions on P. (Fournier and Guillin, 2015) establishes that W(P,,, P) S P with high probability as soon as p ~ 1/ne/d where d denotes the dimension of the samples space. Thus, a major issue is the prescribed radius p suffers from the curse of the dimensionality: when is large, decreases slowly as the number of samples n increases. This constrasts with other distri- butionally robust optimization ambiguity sets, such as Maximum Mean Discrepancy (MMD) (Staib and Jegelka. 2019; Zeng and Lam, 2022), where the radius scales as 1/vR. Moreover, the existing scaling for WDRO is overly conservative for WDRO objectives since recent works (Blanchet et al., 2022a; Blanchet and Shapiro, 2023) prove that a radius behaving as 1//ri is asymptotically optimal. The main difference with (Esfahani and Kuhn, 2018) is that they - and us - consider the WDRO objective whole, instead of proceeding in two steps: first considering the Wasserstein distance independently and invoking concentration results on the Wasserstein distance and then plugging this result in the WDRO problem.
Wiit
1.2 Contributions and related works
In this paper, we show that WDRO provides exact upper-bounds on the true risk with high proba- bility. More precisely, we prove non-asymptotic generalization bounds of the form of (2), that hold for general classes of functions, and that only require p to scale as 1 1/vū and not 1/n To do so, we construct an interval for the radius p for which it is both sufficiently large so that we can go from the empirical to the true estimator (i.e., at least of the order of 1/vr) and sufficiently small so that the robust problem does not become degenerate (i.e., smaller than some critical radius, that we introduce as an explicit constant). Our results imply proving concentration results on Wasserstein Distributionally Robust objectives that are of independent interest.
This work is part of rich and recent line of research about theoretical guarantees on WDRO for machine learning. One of this first results, Lee and Raginsky (2018), provides generalization guar- antees, for general class of models and a fixed p. that, however, become degenerate as the radius goes to zero. In the particular case of linear models, WDRO models admit an explicit form that allows Shafieezadeh-Abadee et al. (2019); Chen and Paschalidis (2018) to provide generalization guarantees (2) with the radius scaling 1/ The case of general classes of models, possibly non-linear, is more intricate. Sinha et al. (2018) showed that a modified version of (2) holds at the price of non-negligible error terms. Gao (2022); An and Gao (2021) made another step towards broad generalization guarantees for WDRO but with error terms that vanish only when p goes to zero.
2

---

In contrast, our analysis provides exact generalization guarantees in the form (2) without additional error terms, that hold for general classes of functions and allow for non-vanishing uncertainty radius to cover for distribution shifts at testing. Moreover, our guarantees also carry over to the recently introduced regularized versions WDRO (Wang al., 2023; Azizian et al., 2023), whose statistical properties have not been studied yet.
This paper organized as follows. Section 2, we introduce notations and our blanket assumptions. In Section 3, we present our main results, an idea of proof, and discussions. The complete proofs deferred to the appendix.
Setup and Assumptions
In this section, we formalize our setting and introduce Wasserstein Distributionally Robust risks.
2.1 Wasserstein Distributionally Robust risk functions
In this paper, we consider as samples space =\t subset of Rd equipped with the Euclidean norm ||-II. We rely Wasserstein distances of order 2, in line with the seminal work Blanchet et al. (2022a) on generalization of WDRO. This distance is defined for two distributions Q, Q' in the set of probability distributions on E, denoted by P(3),
_ - 331s-(1ee) -(rl))
1/2
inf W2(Q, = (EE -
E (E,C)~
where P(E x E) is the set of probability distributions in the product space x E, and n (resp. T2) denotes the first (resp. second) marginal of n.
We denote by f E + R the loss function some model over the sample space. The model may depend some parameter 0, that we drop for now lighten the notations; instead, we consider a class of functions F encompassing our various models and losses of interest (we come back to classes of parametric models of the form F {fe 8 ) in Section 4).
We define the empirical Wasserstein Distributionally Robust risk Rfa(f) centered on P. and simi- larly the true robust risk R,² (f) centered on as
R (f) =
sup QEP(E) (P....Q)SP
E (f(E))
and R₂²(1)=
sup QEP(E) (P..)PP
E [S(E)
(3)
Note that R₂ (f), which is based on the empirical distribution P,. computable proxy for the true robust risk RGp(()) Note also that the true robust risk (f) immediately upper-bounds the true (non-robust) risk Eç-p [f( and also upper-bounds Eç.Q [f(] for neighboring distributions
Q that correspond to distributions shifts of magnitude smaller than p in Wasserstein distance.
2.2 Regularized versions
Entropic regularization of WDRO problems was recently studied in Wang et al. (2023); Blanchet and Kang (2020); Piat et al. (2022); Azizian et al. (2023) and used in Dapogny et al. (2023); Song et al. (2023); Wang and Xie (2022); Wang et al. (2022). Inspired by the entropic regularization in optimal transport (OT) (Peyré and Cuturi, 2019, Chap. 4), the idea is to regularize the objective by adding a KL divergence, that is defined, for any transport plan π E P(E x E) and a fixed reference PE x E), by
[ d when πT & π otherwise.
KL(T [.)
di 11 +00
Unlike in OT though, the choice of the reference measure in WDRO is not neutral and introduces a bias in the robust objective (Azizian et al., 2023). For their theoretical convenience, we take reference measures that have Gaussian conditional distributions
18-012 2
(dClE) 1
dc,
for all & E,
(4)
3

---

where o > 0 controls the spread of the second marginals, following Wang et al. (2023); Azizian al. (2023). Then, the regularized version of (f) (WDRO empirical risk) is given by
Re (J) = sup
B BE [S(E) - KL (L (=")
with To = Pa (dE) n. (dcle) (5)
TEP - 1
and similarly, the regularized version of Rp² (f) is given by RS (f)
sup TT Be..0m (1.l0--(3316-11111 -1l
RE [S()) e KT. (* (T,)
with To = P(dd))
(6)
These regularized risks have been studied in terms of computational approximation properties, but their statistical properties have not been investigated yet. The analysis we develop for WDRO estimators is general enough to carry over to these settings.
In (5) and (6), note finally that the regularization is added penalization in the supremum, rather than in the constraint. As in Wang et al. (2023), penalizing in the constraint leads to an ambiguity set defined by the regularized Wasserstein distance, that we introduce in Section 3.2. We refer to Azizian et al. (2023) for a unified presentation of the two penalizations.
2.3 Blanket assumptions
Our analysis is carried under the following of assumptions that will be in place throughout the paper. First, we assume that the sample space E C IRd is convex and compact, which is in line with previous work, c.g., (Lee and Raginsky, 2018; An and Gao, 2021).
Assumption (On the set E). The sample space E is a compact convex subset of Rd.
Second, require the class of loss functions F to be sufficiently regular. In particular, we assume that they have Lipschitz continuous gradients.
Assumption 2 (On the function class). The functions of F are twice differentiable, uniformly bounded, and their derivatives are uniformly bounded and uniformly Lipschitz.
Finally, we assume that P,, is made of independent and identically distributed (i.i.d.) samples of P and that supported on the interior of E (which can be done without loss of generality by slightly enlarging E if needed).
Assumption (On the distributions). P, + Σx= 6g. where EI...., are i.i.d. samples of P. We further assume that there is some R > such that satisfies supp P +B, R) C E.
Main results and discussions
The main results of paper establish that the empirical robust risk provide high probability bounds, of the form of (2), on the true risk. Since the results and assumptions slightly differ between the WDRO models and their regularized counterparts,
present them separately in Section 3.1 and Section 3.2. In Section 3.3, we provide the common outline for the proofs of these results, the proofs themselves being provided in the appendix. Finally, in Section 4, we detail some examples.
3.1 Exact generalization guarantees for WDRO models
In this section, we require the two following additional assumptions on the function class. The first assumption is common in the WDRO litterature, see e.g., Blanchet et al. (2022a); Blanchet and Shapiro (2023); Gao (2022); An and Gao (2021).
Assumption 4. The quantity yer Ep [||V [|]"] is positive.
The second assumption we consider in this section makes use of the notation d(E, A), for a set A C E and point & E, to denote the distance between and A. i.e., A) infçe ClI.

---

Assumption 5.
1. For any R > there exists A
such that,
VfEF,VÇEE, d(c, arg max f) R f(() max AA
2. The following growth condition holds: there exist μ 0 and L such that, for all
f E FFEE and 5* projection of & on arg max f, i.e., 5" E arg min arg max y ||I - -ll-
- --1 S(5)) Z f(E) + -1
- 1
The first item of this assumption has natural interpretation: we show in Lemma A.7, that it is equivalent to the relative compactness the function space F w.r.t to the distance
D(Sg) = II - glle< + D max f, arg max g),
where DH denotes the (Hausdorff) distance between sets and I| supre=lf(E) the in- finity norm. The last one is structural assumption the functions FF that is in our context but actually very close the so-called parametric Morse-Bou Bott condition, introduced of bilevel optimization (Arbel and Mairal, 2022), Section A.5.
We now state our main generalization result for WDRO risks.
Theorem 3.1. Under Assumptions 4 and 5. there is an explicit constant Pe depending only on F and P such that for any E (0, 1) and n 2 1, if
of
1 log 1/8 (vi
-0(v log 1/8 2
Pe S SPS
n
n
then, there is Pn = =0 1 (
such that, with probability 1 6,
n
VfEF, 2 [f(E)
for all Q such that (P S p(p - pn).
(8)
In particular, with probability - 8, we have
VfEF, R₂)()) BE-P(f((E)
The second part of the result, (9), is exact generalization bound: it is actual upper-boune bound on the true risk (E)), that we cannot access in general, through a quantity that we can actually compute with P.. The first part of the result, (8) gives insight into the robustness guarantees offered by WDRO risk. Indeed, tells us that, when p is greater than the minimal radius Pn & 1/vn by some margin, the empirical robust risk (f) is an upper-bound on the loss even with some perturbations of the true distribution. Hence, long p is large enough, the WDRO objective enables us to guarantee the performance of our model even in the event of a distribution shift testing time. In other words, the empirical robust risk is exact upper-bound on the true robust risk (p(p-pa)())) with a reduced radius.
The range of admissible radiuses is described by (7). The lower-bound, roughly proportional to 1/vn, is optimal, following the results of Blanchet et al. (2022a). The upper-bound, almost in- dependent of n. depends interpretation, that we formalize the following remark. Note, finally, that, the big-O notation in this theorem has slightly stronger meaning! than the usual one, being non-asymptotic in and 5.
constant P.. that call critical radius and that has interesting
Remark 3.2 (Interpretation of critical radius). The critical radius Per appearing in (7), is defined by
[ df (E, arg max f)
2
inf Eg-P JEF
2
'gg. (0(
1+log 1/6
means that 3C 0 such that Pn S Cv.
1+log 1/8
for all & (0. 1) and 2 1.
5

---

It can be interpreted as the threshold at which the WDRO problem W.F.f. P starts becoming degen- erate. Indeed, when p² 2 Eg-p/ } (5, arg max f)] for some f E that we fix, the distribution Q
given by the second marginal of the transport plan π defined by,
T(dE, d() = P(dE)) (e)())(-())(d())
where (*
arg min (E, (EArK max f
satisfies
[
1 <1P = BeWP
d arg max n) S sp²
(2( S ((
-
2
2
As consequence, the robust problem is equal to
R₂
sup
EE-Q [f(E)
max f(E).
QEP(E) (P.).))
feB
Thus, when the radius exceeds Pe, there is some such that the robust problem becomes degenerate as it does not depend on nor anymore.
Finally, note that we can obtain the same generalization guarantee as Theorem 3.1 without Assump- tion 5 at the expense of losing the above interpration on the condition on the radius. More precisely, have the following result.
Theorem 3.3. Let Assumption 4 hold. For any E 10. and n 2 1, if p satisfies (7), and if, in addition, it is smaller than positive constant which depends only on P, F and E. then both conclusions of Theorem 3.1 hold.
This theorem can be compared to existing results, and in particular with Gao (2022); An and Gao (2021). These two papers provide generalization bounds for WDRO under a similar assumption on FF and weakened version of Assumption 3. However, these generalization bounds involve extra error terms, that require to be vanishing. In comparison, with a similar set assumptions, Theorem 3.3 improves these two issues, by allowing p not to vanish - do and by providing the exact upper-bound (9). Allowing non-vanishing radiuses is an attractive feature our results that enables us cover distribution shifts.
3.2 Regularized WDRO models
The analysis that we develop for the standard WDRO estimators is general enough also cover the regularized versions presented in Section 2.2. We thus obtain the following Theorem 3.4 which is the first generalization guarantee for regularized WDRO. This theorem is very similar to Theorem 3.1 with still couple of differences. First, the regularization leads to ambiguity sets defined in terms of W2,7 (P,-) +), the regularized Wasserstein distance to the true distribution P, defined, for some regularization parameter 0, as
= inf Ex
<112 + + KLL(T To) : P(E E). T1 =, n2 Q
where To appears the definition of the regularized robust risk (6). Besides, the regularization allows us to avoid Assumptions 4 and 5 to show generalization result.
Theorem 3.4. For a dup with do > 0, E = EOP with Eo > such that so/ o is small enough depending F, P, 3, there is an explicit constant Pe depending only F, P and = such that for all E (0, 1) and n 2 1, if
0 + log 1/5 p <
0
(()) (vr)
and Pe 2020
(
1 n//6
1 (
+
log log 1/8
1/4
n
then, there are T = O(pp) and Pn = =0
(V L+log 1/6
such that, with probability at least 1 - 8,
VFEF, RS E [f(
for all Q such that W.2, - (opp-pp)) (10)
Furthermore, when dg and a are small enough depending on P and E, with probability 8. 8.
Vf F. Rip(1) BENP (-19) [f(()).

---

The first part of the theorem, (10), guarantees that the empirical robust risk is an upper-bound on the loss even with some perturbations of the distribution, As in OT, the regularization added to the Wasserstein metric induces bias that may prevent - (P, P) from being null. As a result, the second part of the theorem involves a smoothed version of the true risk: the empirical robust risk provides an exact upper-bound the true expectation of a convolution of the loss with Wo-
few additional comments are in order:
Our result prescribes the scaling of the regularization parameters: and should be taken proportional to p.
The critical radius Pe has a slighlty more intricate definition, yet the same interpretation as in the standard WDRO case inRemark 3.2; see Section D.2.
The regularized OT distances not suffer from the curse of dimensionality (Genevay et al., 2019). However this property does not directly carry over to regularized WDRO. Indeed, we cannot choose the same reference measure as in OT and we have to fix the measure Nr, introducing a bias. As consequence, we have to extend the analysis of the previous section to obtain the claimed guarantees that avoid the curse of dimensionality.
3.3 Idea of the proofs
In this section, we present the main ideas of the proofs of Theorem 3.1, Theorem 3.3, and Theo- rem 3.4. The full proofs are detailed in appendix; we point to relevant sections along the discussion. First, we recall the duality results for WDRO that play crucial role in analysis. Second, present rough sketch of proofs that is common to both the standard and the regularized cases. Finally, we provide refinement of our results that a by-product of our analysis.
Duality in WDRO. Duality has been central tool in both the theoretical analyses and compu- tational schemes of WDRO from the onset (Shafieezadeh Abadeh et al., 2015; Esfahani and Kuhn, 2018). The expressions of the dual of WDRO problems for both the standard case (Gao and Kley- wegt, 2016; Blanchet and Murthy, 2019) and the regularized case (Wang et al., 2023; Azizian al., 2023) can be written with the following dual generator function e defined as
supce=( - Âll - -
if =
(,, & llog (Ecwro((15)) exp [(0) A CIP/2)
(11)
if > 0,
where À is the dual variable associated to the Wasserstein constraint in (3), (5) and (6). The effect of regularization appears here clearly as smoothing of the supremum. Note also that this function depends the conditional reference measures T (.()) but not on other probability distributions. Then, under some general assumptions (specified in Section 2.3 in appendix). the existing strong duality results yield that the (regularized) empirical robust risk writes
(5)(0) inf Ap² + EE-., (,,,,, X20
(12)
and, similarly, the (regularized) true robust risk writes
(5) inf Xp² Egar ((
(13)
X
These expressions for the risks are the bedrock of our analysis.
Sketch of proof. In both the standard case and the regularized case, proof is built on two main parts: the first part is to obtain a concentration bound on the dual problems that crucially relies on a lower bound of the dual multiplier; the second part then consists in establishing such a lower bound. All the bounds are valid with high probability, and we drop the dependency on the confidence level 8 of the theorems for simplicity.
For the first part of the proof (Section B), we assume that there is a deterministic lower-bound > on the optimal dual multiplier in (12) that holds with high- pigbbbrbbbbility. As consequence, we can
7

---

restrict the range of À in (12) to obtain:
RS
inf A22 ())
Ap= + E (0 [,,,,,)
Ap + Eşap [() PsmPlo(f.S,AA
- B Boo (o(f,,,,,,,,)
inf
X2A
A
inf
Ap + Eg-p [((.
sup
12A
X21
X
inf
{Ap²
+ Egpr
Ap App
A21
R 72 (f).
(14)
In the above, used that the inner supremum, which is random, can be bounded by deterministic and explicit quantity that we call Ph. i.e.,
Be-p Ce-Plo(ffE,..e..0k EE (o(f.E.N.e,o))
with high probability.
X2A
X
Hence, we obtain an upper-bound on the robust risk w.r.t the true distribution with radius p² P Moreover, we show that 7 = (11(Av/) which highlights the need for a precise lower bound X to control the decrease radius.
The second part of the proof thus consists in showing that the dual variable indeed bounded away from 0, which means that the Wasserstein constraint is sufficiently active. We have to handle two cases differently;
when p is small, i.e., close to Pn. (Section C).
when p is large, i.e., close to the critical radius Pe. (Section D). Note that the additional Assumption is required here: where we need to control the behaviors of f E F close to their maxima (sce (11) for 0 and small A).
In both cases we obtain that À scales as 1/p for the respective ranges of admissible radiuses. As consequence P is bounded by ppn with Pr. = O(1/vn) and (14) becomes
(f) 2 R (f)-
(15)
which leads to our main results.
Extension: upper and lower bounds on the empirical robust risk. The proof that we sketched above actually shows that Re Pip--p)) is a lower bound of R5)()) This proof technique also yields an upper bound by exchanging the roles of P and P...
Theorem 3.5. In the setting of either Theorem 3.1, Theorem 3.3 Theorem 3.4 (with or e > 0), with probability at least 1 1- ö, it holds that
VfEF, Rolo-na) Rip(()) S R Re(tta)())
with Pr. =0 =O(V2tlos 1/5
Hog
This result shows how two robust objectives w.r.t. P provide upper and lower bounds on the empiri- cal robust risk, with only slight variations in the radius. Furthermore, when the number of data points n grows, both sides of the bound converge to the same quantity Re, (f). Hence our generalization bounds of the form (15) are asymptotically tight.
As final remark, underline that the proofs of this theorem and of the previous ones rely on the cost being the squared Euclidean norm and the extension to more general cost functions left as future work. In particular, the Laplace approximation of Section A.3 in the regularized case and the analysis of Section D.I in the standard WDRO case would need further work to accomodate general cost functions.

---

4 Examples: parametric models
Our main theorems Theorems 3.1, 3.3 and 3.4 involve a general class F of loss functions. We explain in this section how to instantiate our results in the important class of parametric models. We then illustrate this setting with logistic regression and linear regression in Examples 4. I and 4.2.
Let us consider the class of functions of the form
F= = (5 + f(0 E) : 0 E )
with f: f
(16)
where O the parameter space, a subset of Rº and E, the sample space, is a subset of R2d
For instance, this covers the case of linear models of the form f(0.{) = {((. 0)) with f' a convex loss. This class of models is studied by Shafiezzadeh-Abadeh et al. (2019); Chen and Paschalidis
(2018) in a slightly different setting, where they obtain a closed form for the robust objective and then establish generalization bound similar to (9).
Let us show how to instantiate our theorems in the case of (16).
If f is twice continuously differentiable on a neighborhood of θ E with O and E both compact, then Assumption 2 is immediately satisfied. Therefore, Theorem 3.4 can be read- ily applied and its generalization guarantee hold.
As for Assumption 4, it is equivalent to, for all 0 O, P(V ((,.5) + 0) 0. Thus disregarding the degenerate case of V. f(0, {) being null for P-almost every (e.g., when the loss does not depend on {). are in the setting of Theorem 3.3.
Satisfying Assumption 5, needed for Theorem 3.1, requires some problem-dependent de- velopments, see the examples below. Note though that the second item of Assumption is implied by the parametric Morse- Bott property (Arbel and Mairal, 2022); see Section A.5.
We discuss linear and non-linear examples of this framework. In light of the above, we focus our discussion Assumption 5. We first present the examples of linear models, Examples 4.1 and 4.2, where the latter assumption is satisfied. We then consider several examples of nonlinear models: kernel regression (Example 4.3), smooth neural networks (Example 4.4) and families of invertible mappings (Example 4.5). In Section H, we also provide numerical illustrations for linear models.
Example 4.1 (Logistic Regression). For a training sample (ar, y) E RP x {-1,+1}, the logistic loss for a parameter 0 E IP is given by log(1 [1 + =vvi,.))). It fits into our framework by defining f(0, {)- = log(1 + c(t.9)) with & playing the role of - x. We assume that θ is a compact set that does not include the origin, and, for the sake of simplicity, we take as closed Euclidean ball, i.e., E = B)), We are going to show that Assumption 5 is satisfied, and, for this, we need the following elements. For any 0, the maximizer of f(0,-) over E = B(0,r) ) is reached at 8" = 11011 Besides, for any & E, it holds that
r
2 2 11E112 = 115" + - )²) + 115 --
so that, since ||5*|| = r, we have
-- - 1-
(17)
We can now turn to the verification of Assumption 5.
1. Take some R >> 0 and some & E E such that -- 2 R. Then, yields
|| (E" -
|8|
115 - 1 < d(0. R)R²
(0.E) - (0,E)-(0,E7)
(18)
2r
2r
Since u + log(1 + e²) is increasing, this yields that f(0, - f(0,g*) is bounded away from O by a negative constant uniformly in O. The first item of Assumption 5 is thus satisfied.
2. Fix 0 E θ; by Taylor expanding u + log(1 + e²a around (0, 50) we get
1
f(0,E) f(0,5") + 1+ e (0.5%) (0.5 - 5*) ( -

---

where the big O remainder is uniform over 0 E O. Using the first inequality in (18), we get for & close enough to E*
1
1101
T(0,E) S [(0,5)) 2(1 + (0,5 --) S S(0.5))
4r
This shows that the second item of Assumption 5 is satisfied locally around E*. It can be made global by using the uniform Lipschitz-coninnity of J, which introduces a term of the form 6 61l55 g=
Example 4.2 (Linear Regression). With samples of the form E = (x. y) E RP x R and parameters O E TRP,, the loss is given by [(0,E) = 4((0, y) Similarly the previous example, we take θ as a compact set of IRd that does not include the origin and E of the form B(0,r) r) x [-r',r"]. The maximizers of f(0, .) on E are {
can restrict to the case of Ei and (0,z) - y 2 0; the same rationale as above can then be applied.
(r1//|[0],,-r and &j = = (-r0/ //0l/()),rr)) By symmetry.
Example 4.3 (Kernel Ridge Regression). Using a kernel k : X' x X + R with X compact and k. smooth, for instance Gaussian or polynomial, we consider the following class of loss functions:
5(0, - 2 Σ oak(o,, x.) -
2 la12
1)
where { = (x. y). E is some compact subset of X x R. 0 = (a1..... Omm: 31, ;1,...,,m, Imm) A Am Xm, m. a fixed integer, A a compact subset of R Xm can be any closed subset of xm and p 2 0 is the regularization parameter. A typical choice for Nmm would be the datapoints of the training set. This class then fits into our framework of parametric models above. Finally, further information on the kernel would be needed to ensure that Assumption 5 is satisfied.
Example 4.4 (Smooth Neural Networks). Denote by NN 0, σ') multi-linear perceptron that takes x as input, has weights and a smooth activation function 0, for instance the hyperbolic tangent or the Gaussian Error Linear Units (GELU). We choose fij, y) smooth loss function and we consider the loss [(O,, (I, y)) (xN 0, 0,)), y) with 0 E O some compact set. Provided that the inputs (Ir, y) lie in a compuct set E, this class fits the paramelric framework above. Note that we require a to be smooth, further work would be required for non-smooth activation functions.
Example 4.5 (Family of diffeomorphisms). Consider maps h: E - E and (0,E) E θ x x + go(E) E E and define the parametric loss {(.E) = h(go(E)). Assume that these functions are twice differentiable, that h satisfies the second item of Assumption 5 and that, for every 9 E O. 9a has inverse 90 which is also continuously differentiable in a neighborhood of θ x E.
As before, this setting fits into the framework above. We now show that Assumption 5 is satisfied.
1. Since h is continuous, h satisfies the first item of Assumption 5. It is satisfied by F as well thanks 90 being pppschitz--ontinnun in & uniformly in 0 by compactness of O E.
2. Take C such that both go and 90 -1 are C-Lipschitz in & uniformly in 0. Since arg max max [(0,-) = 96 ming Earg max ((e)))l90({) go(("))) )|l which lies between C-1 (--miingen Earg max ((8.))l5- =* and C' mings Earg uax 100-)]15 - (l Combined with h satisfying the second item of As- sumption 5, this shows that ff satisfies this condition as well.
2 (arg max h)), it holds that minle- inlggmaxx (ll))(E) S*1l
5 Conclusion and perspectives
In this work, we provide generalization guarantees for WDRO models that improve over existing literature in the following aspects: our results avoid the curse of dimensionality, provide exact upper bounds without spurious error terms, and allow for distribution shifts during testing. We obtained these bounds through the development of original concentration result on the dual of WDRO. Our framework is general enough to cover regularized versions of the WDRO problem: they enjoy similar generalization guarantees as standard WDRO, with less restrictive assumptions.
Our work could be naturally extended several ways. For instance, might be possible to relax any of the assumptions (on the sample space, the sampling process, the Wasserstein metric, and the class of functions) at the expense of additional technical work. Moreover, the crucial role played by the radius of the Wasserstein ball calls for principled and efficient procedure to sclect it.
10

---

Acknowledgments and Disclosure of Funding
This work has been supported by MIAI Grenoble Alpes (ANR-19-P31A-0003)
References
Y. An and R. Gao. Generalization bounds for (wasserstein) robust optimization, Advances Neural Information Processing Systems, 34:10382-1033 2021.
M. Arbel and J. Mairal. Non-Convex Bilevel Games with Critical Point Selection Maps. Advances in Neural Information Processing Systems, 36:1-34, 2022.
A. Arrigo, C. Ordoudis, Kazempour, Z. De Grève, J.-F. Toubeau, and Vallée. Wasserstein distributionally robust chance-constrainedd optimization for energy and reserve dispatch: An exact and physically-boune -ouunde formulation. European Journal of Operational Research, 296(1):304 322, 2022.
W. Azizian, F. Iutzeler, and J. Malick. Regularization for Wasserstein distributionally robust opti- mization. ESAIM: COCV, 29:33, 2023.
Blanchet and Y. Kang. Semi-supervised learning based on distributionally robust optimiza- tion. Data Analysis and Applications 3: Computational, Classification, Financial, Statistical and Stochastic Methods, 5:1-33, 2020.
J. Blanchet and K. Murthy, Quantifying distributional model risk via optimal transport. Mathematics of Operations Research, 44(2):565-600, 2019.
J. Blanchet and A. Shapiro. Statistical limit theorems in distributionally robust optimization. arXiv preprint ar arXiv:2303.1 14867, 2023.
J. Blanchet, K. Murthy, and V. A. Nguyen. Statistical analysis of wasserstein distributionally robust estimators. In Tutorials in Operations Research: Emerging Optimization Methods and Modeling Techniques with Applications, pages 227-254. INFORMS, 2021.
J. Blanchet, K. Murthy, and N. Si. Confidence regions in wasserstein distributionally robust estima- tion. Biometrika, 109(2):295-315, 2022a.
Blanchet, K. Murthy, and F. Zhang. Optimal transport-based distributionally robust optimization: Structural properties and iterative schemes. Mathematics of Operations Research, 47(2):1500- 1529, 2022b.
Boucheron, G. Lugosi, and Massart. Concentration Inequalities: Nonasymptotic Theory of Independence. Oxford University Press, 2013.
N. Boumal. An introduction to optimization on smooth manifolds. Cambridge University Press, 2023.
R. Chen and I. C. Paschalidis. A robust learning approach for regression models based on distribu- tionally robust optimization. Journal of Machine Learning Research, 19(13), 2018.
C. Dapogny, F. lutzeler, A. Meda, and B. Thibert. Entropy-regularizeed wasserstein distributionally robust shape and topology optimization. Structural and Multidisciplinary Optimization, 66(3): 42, 2023.
E. Delage and Y. Ye. Distributionally Robust Optimization Under Moment Uncertainty with Appli- cation Data-Driven Problems. Operations Research, 58:595-612, 2010.
P. M. Esfahani and D. Kuhn. Data-driven distributionally robust optimization using the wasserstein metric: Performance guarantees and tractable reformulations. Mathematical Programming, 171 (1):115-166, 2018.
J. Feydy, T. Séjoumé, F.-X. Vialard, S.-i. Amari, A. Trouvé, and G. Peyré. Interpolating between optimal transport and MMD using Sinkhorn divergences. The 22nd International Conference Artificial Intelligence and Statistics, pages 2681-2690. PMLR, 2019.
N. Fournier and A. Guillin. On the rate of convergence in wasserstein distance of the empirical measure. Probability Theory and Related Fields, 162(3):707-738 2015.
R. Gao. Finite- sample guarantees for wasserstein distributionally robust optimization: Breaking the curse of dimensionality, Operations Research, 2022.

---

R. Gao and A. J. Kleywegt. Distributionally robust stochastic optimization with wasserstein dis- tance. Mathematics of Operations Research, 2016.
A. Genevay, M. Cuturi, G. Peyré, and F. Bach. Stochastic Optimization for Large-scale Optimal Transport. In NIPS 2016 - Thirtieth Annual Conference on Neural Information Processing System,
Proc. NIPS 2016, 2016.
A. Genevay, L. Chizat, F. Bach, M. Cuturi, and G. Peyré. Sample complexity of sinkhorn diver- gences. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1574-1583. PMLR, 2019.
J. Goh and M. Sim. Distributionally Robust Optimization and Its Tractable Approximations. Oper- ations Research, 58:902-917, 2010.
D. Kuhn, P. M. Esfahani, V. A. Nguyen, and S. Shafieezadeh-Abadehh Wasserstein distributionally robust optimization: Theory and applications machine learning. In Operations Research & Management Science in the Age of Analytics. INFORMS, 2019.
Y. Kwon, W. Kim, J.-H. Won, and M. C. Paik. Principled learning method for wasserstein distri- butionally robust optimization with local perturbations. In International Conference on Machine Learning, pages 5567-5576. PMIR, 2020.
Y. Laguel, J. Malick, and Harchaoui. First-order optimization for superquantile-based supervised learning. In 2020 JEEE 30th International Workshop on Machine Learning Signal Processing (MISP), pages 1-6. IEEE, 2020.
J. Lee and M. Raginsky. Minimax statistical learning with wasserstein distances. Advances in Neural Information Processing Systems, 31, 2018.
J. M. Lee. Introduction to Riemannian manifolds, volume 2. Springer, 2018.
D. Levy, Y. Carmon, C. Duchi, and Sidford. Large-scale methods for distributionally robust optimization. Advances in Neural Information Processing Systems, 33, 2020.
J. Li, C. Chen, and A. M.-C. So. Fast Epigraphical Projection-based Incremental Algorithms for Wasserstein Distributionally Robust Support Vector Machine. In Advances in Neural Information Processing Systems, volume 33, pages 4029-4039, Curran Associates, Inc., 2020.
F.P. Paty and M. Cuturi. Regularized Optimal Transport is Ground Cost Adversarial. In ICML, 2020.
G. Peyré and M. Cuturi. Computational optimal transport: With applications to data science. Foun- dations and Trends@ in Machine Learning, 11(5-6):355-677, 2019.
W. Piat, J. Fadili, F. Jurie, and S. da Veiga. Regularized robust optimization with application to robust learning. 2022.
R. T. Rockafellar and R. J.-B. Wets. Variational Analysis. Grundlehren Der Mathematischen Wis- senschaften. Springer-Verte Verlag, 1998.
W. Rudin. Real and Complex Analysis. McGraw-Hill, 1987.
S. Shafieezadeh Abadeh, P. M. Mohajerin Esfahani, and D. Kuhn. Distributionally Robust Logistic Regression. In Advances in Neural Information Processing Systems, volume 28. Curran Asso- ciates, Inc., 2015.
S. Shafieezadeh--Aaadee D. Kuhn, and P. M. Esfahani. Regularization via Mass Transportation. Journal of Machine Learning Research, 20:1-68, 2019.
A. Sinha, H. Namkoong, and J. Duchi. Certifying some distributional robustness with principled adversarial training. In International Conference on Learning Representations, 2018.
J. Song, N. He, L. Ding, and C. 7hao. Provably convergent policy optimization via metric-aware trust region methods. arXiv preprint arXiv:2306. 14133, 2023.
M. Staib and S. Jegelka. Distributionally robust optimization and generalization in kernel methods. Advances in Neural Information Processing Systems, 32, 2019.
M. J. Wainwright. High--dimensionl statistics: non-asymptotic viewpoint, volume 48. Cambridge university press, 2019.
J. Wang and Y. Xie. A data-driven approach to robust hypothesis testing using sinkhorn uncertainty sets. In 2022 IEEE International Symposium on Information Theory (ISIT), pages 3315-3320. IEEE, 2022.
12

---

J. Wang, R. Moore, Y. Xie, and R. Kamaleswaran. Improving sepsis prediction model generalization with optimal transport. In Machine Learning for Health, pages 474-488. PMLR, 2022.
J. Wang, R. Gao, and Y. Xie. Sinkhorn distributionally robust optimization. arXiv preprint arXiv:2109. 1926, 2023.
Y. Zeng and Lam, Generalization bounds with minimal dependency on hypothesis class distributionally robust optimization. Advances in Neural Information Processing Systems, 35: 27576-27599 2022.
C. Zhao and Y. Guan. Data-driven risk-averse stochastic optimization with wasserstein metric. Operations Research Letters, 46(2):262-265 267, 2018.
J.J. Zhu, W. Jitkrittum, M. Diehl, and B. Schölkopf. Kernel distributionally robust optimization: Generalized duality theorem and stochastic approximation. In International Conference Arti- ficial Intelligence and Statistics, pages 280-288. PMLR, 2021a.
J.JJ. Zhu, Kouridi, Nemmour, and B. Schölkopf. Adversarially robust kernel smoothing. arXiv preprint www.i:2102.088//44... 2021b.
13


Reviews:
[{"review_id": "Orkj77XORE", "reviewer": "Reviewer_ZTJQ", "summary": "This paper provides generalization guarantees of Wasserstein DRO for a general class of functions, in which the radius scales as $1/\\sqrt{n}$ and does not suffer from the curse of dimensionality. Moreover, these guarantees hold for any distribution in the neigbourhood of the true distribution, so that they still apply when the distribution shifts at testing time. The results in this paper hold for both constrained and regularized version of Wasserstein DRO. The authors also provide a proof sketch that explains the main ideas and techniques used in the proof, and apply their results to logistic and linear regression.", "questions": "1. How does the setting considered in this paper compared with other works? Could you give a brief and high-level discussion of why the generalization guarantee is dimension-independent in your setting?\n\n2. Is it possible to obtain similar generalization guarantee for DRO with $\\phi$-divergence?", "limitations": "This paper does not have potential negative societal impact.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper provides novel generalization guarantees such that the robustness radius does not suffer from the curse of dimensionality. To the best of my knowledge, the results in this paper are novel and make a non-trivial contribution to the DRO community. Moreover, the authors consider the regularized version of Wasserstein DRO and provide similar guarantees as well.\n\n2. Most parts of the paper are well-written. The necessary backgrounds are clearly explained, and theorems are accompanied with detailed explanations of related definitions and concepts.", "weaknesses": "In Section 3.4, the authors considers logistic and linear regression as applications of their theorems. It would be better if more complicated and popular parametric models can be included in this section to justify the main assumptions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their reading, comments and questions. We very much appreciate the comment \"the results in this paper are novel and make a non-trivial contribution to the DRO community.\" Here are point-by-point answers to your questions.\n\n- *\"It would be better if more complicated and popular parametric models can be included in this section to justify the main assumptions.\"*: In the main rebuttal, we discuss additional examples of parametric models: in particular, kernel regression and neural networks. We will add them to the revision of the paper.\n\n- *\"How does the setting considered in this paper compared with other works?\"* We will provide a more detailled comparison of our setting with the closest previous works:\n    - Blanchet et al. (2022), Blanchet and Shapiro (2023): these works consider the parametric setting, where $f(\\theta, \\xi)$ is twice differentiable with Lipschitz gradient, satisfies a uniform quadratic growth condition and study the asymptotic concentration properties of the WDRO solution in the neighborhood of a minimizer of the true risk.\n    - Gao (2022), An and Gao (2021): these works are the closest to ours. They consider piecewise differentiable loss functions on a compact set with Hölder gradient (however, note that, for their bounds to have vanishing errors, the points of non-differentiability have to be sufficiently far from the data distribution). Note however that they obtain generalization guarantees with additional error terms compared to our bounds, see the discussion in our paper line 181.\n- *\"Could you give a brief and high-level discussion of why the generalization guarantee is dimension-independent in your setting?\"* Our bound indeed does not suffer form the curse of dimensionality: the minimal radius to obtain generalization bounds scales as $1 / \\sqrt n$ instead of $1 / n^{1/d}$ (Esfahani and Kuhn, 2018). The main difference with (Esfahani and Kuhn, 2018) is that we consider the WDRO objective as a whole, instead of proceeding in two steps: 1) considering the Wasserstein distance independently and invoking concentration results on the Wasserstein distance and 2) plugging this result in the WDRO problem.\n- *\"Is it possible to obtain similar generalization guarantee for DRO with $\\phi$-divergence?\"* Though some of their generalization properties have been studied (eg Blanchet and Shapiro (2023)), to the best of our knowledge, this is not possible to obtain exact upper-bounds like ours for $\\phi$-divergences. A possible explanation may be the following: unlike Wasserstein uncertainty sets, uncertainty sets defined with $\\phi$-divergences only contain distribution whose support is included in the one of $P_n$."}, {"review_id": "PhUakg2c5f", "reviewer": "Reviewer_wf5D", "summary": "This work proves generalization guarantees for Wasserstein DRO models that only require the radius of order $O(n^{-1/2})$ under mild assumptions for general classes of models. This provides concentration results that do not suffer from the curse of dimensionality.", "questions": "It might be better to split Section 3 into two shorter sections for better readability. And the discussion may also be extended by adding examples of failure cases with potential methods of relaxation. ", "limitations": "yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The theoretical contribution is the main strength. The empirical concentration of Wasserstein distance suffers from the curse of dimensionality, and this paper is able to prove the results (under some assumptions) that do not have this curse of dimensionality issue and provide statistical guarantees on the performance of WDRO solutions.", "weaknesses": "There is no significant weakness in this paper. Nevertheless, I think adding some discussion or examples for which the assumptions and thus the results in this paper do not hold can be beneficial; it can show failure cases and may also motivate future directions for the extension.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their reading, comments and suggestions.\n\n- *\"adding some discussion or examples for which the assumptions and thus the results in this paper do not hold can be beneficial;\"* We agree that such examples were missing in the submission. In the main rebuttal, we provide more examples of parametric models, in particular kernel methods and neural networks. We also point out which cases our framework fails to cover in this context, see e.g. the discussion at the end of the kernel example. We will use all this material to enrich the example section in the revision.\n\n- *\"It might be better to split Section 3 into two shorter sections for better readability.\"* Thank you for this suggestion which is well aligned with the addition of new examples. In the revision, we will create a section 4 dedicated to examples."}, {"review_id": "08AP4EtaHU", "reviewer": "Reviewer_A8VY", "summary": "This paper presents generalization bound for Wasserstein DRO and entropic regularized Wasserstein DRO (or called Sinkhorn DRO in Wang et al.) formulations. Those generalization bounds do not suffer from the curse of dimensionality. The theoreical analysis is also supported by two examples in Section 3.4. ", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The theoretical analysis is interesting from two aspects. First, the authors reveal that the radius selection of WDRO to make the empirical robust loss  dominate the true loss does not suffer from the curse of dimensionality. The analysis follows different techniques from existing literature such as Gao et al, Blanchet et. al, etc. Second, the technique is general enough so that it also applies to entropic regularized Wasserstein DRO (or called Sinkhorn DRO in Wang et al.) formulations. This is the first work that investigates the statistical properties of such formulations.\n- The authors also present two examples in machine learning to demonstrate the technique assumption holds and the proposed theoretical analysis applies.", "weaknesses": "- The writing of this paper could be potentially improved:\n 1. There should be a comma in Eq.(1), or equation between line 83-84, or Eq. (4), or equation between line 194-195, or equation between line 301-302. \n 2. There should be a period in Eq. (10).\n 3. The contribution and related work part in the introduction section should be separated.\n 4. It would be a little bit confusing to first introduce KL-divergence regularized WDRO risk in Eq.(5-6) and then introduce it corresponds to the Sinkhorn ambiguity set in line 194-195. The authors should put them together in Section 2.2\n 5. The notation could be potentially improved. For example, in Eq. (7) the authors use $\\hat{\\mathcal{R}}$ to refer to the risk based on empirical distribution $P_n$. I would suggest replace the notation $P_n$ with $\\hat{P}_n$ for consistency. Further, in Eq. (7) I think the authors are meaning $\\rho$ should at least scale in the order of $\\sqrt{(1+\\log(1/\\delta))/n}$, then why not write $\\Omega(\\sqrt{(1+\\log(1/\\delta))/n})\\le \\rho$ instead of $O(\\sqrt{(1+\\log(1/\\delta))/n})\\le \\rho$? The same applies for equation between line 199-200.\n\n- It is great that the authors present statistical analysis for entropic regularized Wasserstein DRO. I would suggest the authors add some explanation or numerical example to demonstrate the benefit of introducing entropic regularization. Will it bring extra benefits than standard WDRO?\n\n- The analysis is limited to quadratic cost function, which could be restrictive. From my own trial and reading, I think the major difficulty for generalization is that, it is difficult to apply Laplace approximation technique for general p-th power of norm function. In other words, it is difficult to obtain the p-th power of norm counterpart of Lemma A.3 and Lemma G.1.If so, I suggest the authors add explanation for the difficulty of extension.\n\n- Some literature is missing. For example, readers may wonder why consider adding entropic regularization to WDRO problem and what is the applications? I suggest the authors make the following revisions:\n   1. update reference [J. Wang, R. Gao, and Y. Xie. Sinkhorn distributionally robust optimization. arXiv preprint arXiv:2109.11926, 2021] as [J. Wang, R. Gao, and Y. Xie. Sinkhorn distributionally robust optimization. arXiv preprint arXiv:2109.11926, 2023]. In the updated version, the authors demonstrate that people can find $\\delta$-optimal solution to general entropic regularization WDRO problem with complexity $\\tilde{O}(1/\\delta^2)$. So one major benefit of adding entropic regularization is the computational tractability;\n  2. add several application papers brought by entropic regularization WDRO in literature review:\n     (i) Dapogny, Charles, et al. \"Entropy-regularized Wasserstein distributionally robust shape and topology optimization.\" Structural and Multidisciplinary Optimization 66.3 (2023): 42.\n     (ii) Song, Jun, et al. \"Provably Convergent Policy Optimization via Metric-aware Trust Region Methods.\" arXiv preprint arXiv:2306.14133 (2023).\n     (iii) Wang, Jie, and Yao Xie. \"A data-driven approach to robust hypothesis testing using sinkhorn uncertainty sets.\" 2022 IEEE International Symposium on Information Theory (ISIT). IEEE, 2022.\n     (iv) Wang, Jie, et al. \"Improving sepsis prediction model generalization with optimal transport.\" Machine Learning for Health. PMLR, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We heartwarmingly thank the reviewer for the numerous suggestions, comments and references. It is a pleasure for us to read that \"The theoretical analysis is interesting from two aspects [...]\"  and that \"it is great that the authors present statistical analysis for entropic regularized Wasserstein DRO [...]\".  Here is a point-by-point response.\n\n\n- About the writing: thank you for the suggestions that we will implement in the revision.\n\n- *\"I would suggest the authors add some explanation or numerical example to demonstrate the benefit of introducing entropic regularization.\"*\nOur work theoretically shows that regularized WDRO enjoys similar generalization guarantees as standard WDRO, with less restrictive assumptions: Thm. 3.4 for regularized WDRO requires less assumptions than both Thm. 3.1 and Thm. 3.3 on standard WDRO to obtain similar generalization results. On the numerical aspect, we will provide, in the revision, a discussion about the interest of entropic regularization. First, we will underline that J. Wang, R. Gao, and Y. Xie., (2023) illustrates that the out-of-sample performance of regularized WDRO is on par, if not better in some cases, than standard WDRO. We confirm this with some additional numerical simulations on linear and logistic regression in the main rebuttal, to be added to the revision.\n\n- *\"The analysis is limited to quadratic cost function, [...] I suggest the authors add explanation for the difficulty of extension.\"* The reviewer is indeed right: it is not clear how to apply the Laplace approximation when the squared norm is replaced by the norm to the power $p$, and so, in particular, how to extend appendix A.3. Moreover, the analysis of appendix D.1 also relies heavily on $p$ being equal to 2 and more work would needed to determine whether it can be extended or not. On the other hand, the appendix D.2 would seem to extend to general exponents, as would appendix C when $\\epsilon = 0$ (similarly to An and Gao (2021)). We will add this remark to the revision in conclusion.\n\n- About the additional references: we will gladly add them to the revision and update the reference  [J. Wang, R. Gao, and Y. Xie. 2023]."}, {"review_id": "EyMLX2MUBA", "reviewer": "Reviewer_6D6k", "summary": "The paper provides theoretical results characterizing the generalization capabilities of methods based on Wasserstein distributionally robust approaches. In particular, the results presented extend the conditions under which the performance guarantees are not affected by the curse of dimensionality and are applicable for general classes of models.", "questions": "Would it be possible to include numerical results describing the theoretical results presented?. The choice of the radius in practice is often problematic in Wasserstein methods. The theoretical results provide the scaling of such radius but not a concrete recipe to choose it. It would be useful to explore choices of such radius with the right scaling that result in small error and provide performance guarantees. ", "limitations": "The paper adequately describes the limitations of the methods proposed, mostly in terms of the specific assumptions needed for the results to hold.\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper shows that the usage of Wasserstein radius of the order 1/sqrt(n) can provide generalization bounds in situations more general than those considered in existing works (linear models). In addition, the results presented also cover regularized versions of WDRO. The more general results are obtained using a novel type of proof based on a concentration bound for the dual problem, which is of independent interest.", "weaknesses": "The paper contribution with respect to the state of the art needs to be better described. In particular, the extension to non-linear models of the scaling 1/sqrt(n). \n\nThe problematic dimension-dependent scaling arises in Wasserstein methods while other techniques based on robust risk minimization have been shown to provide performance guarantees with the scaling 1/sqrt(n). It would be good if the authors describe this fact and the related work. \n\nIf I am not mistaken, examples 3.6 and 3.7 correspond to cases for which the right scaling was already proven in previous works. In order to better assess the paper's contribution, it would be good if the authors discuss interesting examples for which the paper provides the right scaling while existing results cannot. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful comments and suggestions. Here is a detailed response to all remarks and questions.\n\n- *\"The paper contribution with respect to the state of the art needs to be better described. In particular, the extension to non-linear models of the scaling 1/sqrt(n).\"* Thank you for this important suggestion; we will clarify this point in the introduction. There are two points to make.\n    - To the best of our knowledge, the only existing *exact* generalization guarantees with the right $1 / \\sqrt n$ scaling are in the work Shafieezadeh-Abadeh et al. (2019), Thm. 39. These guarantees are shown in the restricted context of linear models with Lipschitz loss (eg robust linear regression, support vector machines, logistic regression) and leverage a closed form of the robust risk, to get an *exact* upper bound, as in our results.\n    - The work of An and Gao (2021), which is the closest to ours, covers non-linear models, but provides generalization guarantees with additional error terms.\n\n\n- *\"other techniques based on robust risk minimization have been shown to provide performance guarantees with the scaling 1/sqrt(n). It would be good if the authors describe this fact and the related work.\"* Other DRO neighborhoods indeed also provide similar generalization guarantees with the right scaling. In the revision, we will refer to, in particular, MMD DRO [1, 3]. A result very similar to ours -- an exact upper-bound on the true loss by the empirical robust -- indeed exist for MMD DRO [3, Cor. 3.1]. As other generalization guarantees for MMD DRO or its variants [2, 4], the radius of the MMD is indeed only required to scale as $1 / \\sqrt n$. Adding this discussion in the introduction will help us underline that, in this work, we focus on advancing the theoretical understanding of WDRO.\n\n- *\"it would be good if the authors discuss interesting examples for which the paper provides the right scaling while existing results cannot.\"* Thank you for this suggestion. We will improve the example section with  additional examples, namely kernel methods and neural networks, see the main rebuttal. For these models, our work is the first to give *exact* generalization guarantees in WDRO.\n\n- *\"Would it be possible to include numerical results describing the theoretical results presented?\"* We provide some numerical simulations on linear and logistic regression in the main rebuttal: we show that, both for standard and regularized WDRO, the robust risk with respect to the empirical training distribution is an upper bound on the test loss with probability almost one provided the radius $\\rho$ is large enough.\n\n- *\" The choice of the radius in practice is often problematic in Wasserstein methods [...]\"* We fully agree that choosing the Wasserstein radius remains a major challenge in practice. Though some works have started addressing this question (Esfahani and Kuhn, 2018; Blanchet et al. 2021), this issue is part of our future work. We will mention this in the conclusion.\n\nReferences for Kernel DRO:\n[1] Zhu JJ, Jitkrittum W, Diehl M, Schölkopf B. Kernel distributionally robust optimization: Generalized duality theorem and stochastic approximation. AISTATS 2021 \n\n[2] Jia-Jie Zhu, Christina Kouridi, Yassine Nemmour, Bernhard Schölkopf:\nAdversarially Robust Kernel Smoothing. AISTATS 2022: \n\n[3] Staib M, Jegelka S. Distributionally robust optimization and generalization in kernel methods. Advances in Neural Information Processing Systems. 2019\n\n[4] Zeng Y, Lam H. Generalization bounds with minimal dependency on hypothesis class via distributionally robust optimization. Advances in Neural Information Processing Systems. 2022"}]

Author rebuttal:
We thank the reviewers for suggesting adding non-linear examples to the paper. We discuss three examples (kernel models, neural networks and family of invertible mappings) that we will add to the revision of the paper.
We also discuss a numerical illustration of our main theorems that we will also add to the revision.
### Kernel ridge regression
We present the example of kernel ridge regression and show that both Thm. 3.3 and 3.4 apply. Our work is the first to provide *exact* generalization bounds that do not suffer from the curse of dimensionality for these non-linear models in WDRO.

Take a kernel $k : \mathcal{X} \times \mathcal{X} \to \mathbb R$ with $\mathcal{X}$ compact and $k$ smooth (eg Gaussian, polynomial...). We consider the following class of loss functions:
$$\left\\{(x, y) \in \mathcal X \times \mathbb R \mapsto \frac{1}{2} \left(\sum_{i = 1}^m \alpha_i k(x, x_i) - y\right)^2 + \frac{\mu}{2} ||\alpha||^2_2: (\alpha_1,\dots,\alpha_m) \in A_m,\, (x_1,\dots,x_m) \in \mathcal{X}_m\right\\}$$
 where $m$ is a fixed integer, $A$ is a compact subset of $\mathbb R^m$, $\mathcal X_m$ can be any closed subset of $\mathcal X^m$ and $\mu \geq 0$ is the regularization parameter. A typical choice for $X_m$ would be the data points of the training set.

This class fits into our framework of parametric models of $\S3.4$ by setting $\xi = (x, y)$, $\Xi$ to some compact subset of $\mathcal X \times \mathbb R$,  $\theta=(\alpha_1,\dots,\alpha_m,x_1,\dots,x_m)$, $\Theta = A_m \times \mathcal X_m$ and
$$f(\theta, \xi) = \frac{1}{2} \left(\sum_{i = 1}^m \alpha_i k(x, x_i) - y\right)^2 + \frac{\mu}{2} ||\alpha||^2_2$$
- With that setting, Assumption 2 is readily satisfied so that Thm 3.4 applies.
- To apply Thm 3.3, we further need to assume that Assumption 4 holds. This non-degeneracy assumption is common in the WDRO literature (eg Blanchet et al. (2022); Blanchet and Shapiro (2023); Gao (2022); An and Gao (2021)).
- However, Thm. 3.1 cannot be applied directly as it is not yet clear what conditions on $k$ could ensure that Assumption 5 is satisfied. Moreover, as in other related works on WDRO, it is also not obvious how to extend this framework to cover non-smooth kernels (eg Laplace).
Finally, note that kernel logistic regression is also covered by our framework by combining the arguments above with the the logistic regression example Example 3.6.

## Smooth neural networks
We present the example of neural networks: as in the case of kernels, we show that both Thm. 3.3 and 3.4 apply to smooth neural networks. Again, our work is the first to provide *exact* generalization bounds that do not suffer from the curse of dimensionality.

Denote by $\mathcal{NN}(x, \theta, \sigma)$ a multi-linear perceptron that takes $x$ as input, has weights and biases $\theta$ and a smooth activation function $\sigma$ (eg GELU, tanh, ...). Choose $\ell(\hat y, y)$ a smooth loss function.
Then, we consider the family of losses $\left\\{ (x, y) \mapsto \ell(\mathcal{NN}(x, \theta, \sigma), y): \theta \in \Theta \right\\}$
with $\Theta$ some compact set.
Provided that the inputs $(x, y)$ lie in a compact set $\Xi$, the situation is the same as for kernels.
- Thm. 3.4 applies since Assumption 2 is readily satisfied.
- Thm. 3.3 applies provided the non-degeneracy assumption Assumption 4 is satisfied.
- We do not know how to ensure that Assumption 5 of Thm. 3.1 is satisfied for general neural networks nor how to extend this framework to cover non-smooth activation functions (eg ReLU).

## Family of diffeomorphisms and generative modelling
In this example, we show how the three theorems Thm. 3.1, 3.3 and 3.4 apply.
Consider a parametric function of the form $f(\theta, \xi) = h(g(\theta, \xi))$ where $g : \Theta \times \Xi \to \Xi$ is such that for any $\theta$, $g(\theta, \cdot) : \Xi \to \Xi$ is a diffeomorphism and $h : \Xi \to \mathbb R$ satisfies a mild technical assumption (the standard Morse-Bott condition, see eg (Arbel and Mairal, 2022, A.1)). Normalizing flows, widely used in generative modeling and sampling, are diffeomorphisms and thus lead to loss functions of this form.

For these functions, we readily see that Thm. 3.4 applies since Assumption 2 is readily satisfied and Thm. 3.3 applies provided the non-degeneracy assumption Assumption 4 is satisfied.
To apply Thm. 3.1, we show that Assumption 5 holds, as follows.
1. The function $h$ alone satisfies the first item of Assumption 5 since it is continuous and $\Xi$ is compact. $f$ then also satisfies it since $g$ is Lipschitz in $\xi$ uniformly in $\theta$.
2. We now show that the second item of Assumption 5 is also satisfied. In $\S A.5$, we showed that the second item of Assumption 5 is implied by the so-called parametric Morse-Bott assumption of Arbel and Mairal, 2022. But lemma 1 in $\S A.2$ in their paper shows that this family does satisfy this assumption in Lemma 1 in $\S A.2$.
Hence, Assumption 5 is satisfied and Thm. 3.1 also applies.
## Numerical illustration
We present numerical experiments supporting our theoretical results. On linear and logistic regression models, we illustrate that, provided the radius $\rho$ is large enough, the robust loss on the training distribution is indeed an upper-bound on the true loss. For $f(\theta, \xi)$ as defined in examples 3.6 and 3.7, we estimate the following probability, as in (Esfahani and Kuhn, 2018, $\S 7.2.A$),

$P\left(\hat{\mathcal R}^\varepsilon_{\rho^2} (f(\hat\theta_n, \cdot))\geq E_{P}[f(\hat\theta_n, \xi)]\right)\quad \text{where} \quad \hat\theta_n = argmin_{\Theta}\hat{\mathcal{R}}^\varepsilon_{\rho^2}(f(\theta, \cdot)))$


We observe on the plots (cf pdf) that, for $\rho$ large enough, the above probability is close to 1, for both models and for both standard and regularized cases (as guaranteed by theorems 3.1 and 3.4).

Meta-review: The paper presents an interesting approach for robust generalization. Robust optimization turns to be instrumental in explaining the generalization of deep learning, and this work adds to this line of work. The work itself is very technical and better work could have been done by the authors to make the work accessible to the broader theoretical community of NeurIPS.
Decision: Accept (poster)