Generalization Bounds with Minimal Dependency on Hypothesis Class via Distributionally Robust Optimization
Authors: Yibo Zeng
Henry Lam
Venue: NeurIPS 2022 Accept (2022)
Keywords: distributionally robust optimization
generalization bound
maximum mean discrepancy
reproducing kernel Hilbert space
hypothesis class complexity

Abstract: Established approaches to obtain generalization bounds in data-driven optimization and machine learning mostly build on solutions from empirical risk minimization (ERM), which depend crucially on the functional complexity of the hypothesis class. In this paper, we present an alternate route to obtain these bounds on the solution from distributionally robust optimization (DRO), a recent data-driven optimization framework based on worst-case analysis and the notion of ambiguity set to capture statistical uncertainty. In contrast to the hypothesis class complexity in ERM, our DRO bounds depend on the ambiguity set geometry and its compatibility with the true loss function. Notably, when using statistical distances such as maximum mean discrepancy, Wasserstein distance, or $\phi$-divergence in the DRO, our analysis implies generalization bounds whose dependence on the hypothesis class appears the minimal possible: The bound depends solely on the true loss function, independent of any other candidates in the hypothesis class.  To our best knowledge, it is the first generalization bound of this type in the literature, and we hope our findings can open the door for a better understanding of DRO, especially its benefits on loss minimization and other machine learning applications.

Generalization Bounds with Minimal Dependency on Hypothesis Class via Distributionally Robust Optimization
Yibo Zeng Columbia University yibo. zeng@columbia, edu
Henry Lam Columbia University henry comm@columba edu
Abstract
Established approaches to obtain generalization bounds in data-driven optimization and machine learning mostly build solutions from empirical risk minimization (ERM), which depend crucially on the functional complexity of the hypothesis class. In this paper, present an alternate route to obtain these bounds the solution from distributionally robust optimization (DRO), recent data-driven optimization framework based on worst-case analysis and the notion of ambiguity statistical uncertainty. In contrast to the hypothesis class complexity in ERM, our DRO bounds depend on the ambiguity set geometry and its compatibility with the true loss function. Notably, when using statistical distances such as maximum mean discrepancy, Wasserstein distance, or o-divergence in the DRO, our analysis implies generalization bounds whose dependence on the hypothesis class appears the minimal possible: The bound depends solely on the true loss function, independent of any other candidates in the hypothesis class. To our best knowledge, is the first generalization bound of this type in the literature, and we hope our findings can open the door for a better understanding of DRO, especially benefits on loss minimization and other machine learning applications.
capture
Introduction
We study generalization error in the following form. Let l F Z - E be a loss function over the function class F and sample space 2 C Rd. Let Ep[[(f,))] be the expected loss under the true distribution for the random object z. This Ep[[(f, z)] can be an objective function ranging from various operations research applications Given iid samples {2 P. we solve a data-driven optimization problem or fit model to give solution faam- The excess risk, optimality gap of faa with respect to the oracle best solution f E arg minfer Ep([([,))], is given by
the risk of machine learning model.
Er [y(a(fasm =)] Er(((f"..))
This gap measures the relative performance of data-driven solution in future test data, giving rise to direct measurement the generalization error. Established approaches to obtain high probability bounds for (T) have predominantly focused on empirical risk minimization (ERM)
i" E arg min E [p(((f,))
fE
for empirical distribution P. or its regularized versions. A core determination of the quality of these bounds is the functional complexity of the model, or hypothesis class, which dictates the richness of the function class F or L = {((f.) f E F} and leads to well-known measures such as the Shpmik-Chervonenkis (VC) dimension M. On high level, these complexity measures arise from
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

need to uniformly control the empirical enror, which in turn arises from the priori uncertainty on the decision variable f in the optimization.
In this paper, we present an alternate route to obtain concentration bounds for ① on solutions obtained from distributionally robust optimization (DRO). The latter started as a ppcision-making framework for optimization under stochastic uncertainty 1244, and has recently surged in popularity in machine learning, thanks to its abundant connections regularization and variability penalty [5-12] and risk-averse interpretations [3 14]. Instead of replacing the unknown true expectation Ep[-] by an
empirical expectation Ep DRO hinges on the creation of an uncertainty set or ambiguity set K.
This set lies in the space of probability distribution P on and is calibrated from data. It obtains a solution fūr by minimizing the worst-case expected loss among XC
fam E arg min max Eq So(((ff=))
fEF QEA
The risk-averse nature of DRO is evident from the presence of an adversary that controls Q in (2). Also, if KC is suitably chosen so that contains P with confidence (in some suitable sense) and shrinks to singleton as data size grows, then one would expect Jim to eventually approach the true solution, which also justifies the approach as a consistent training method. The latter can often be achieved by choosing K. as a neighborhood ball surrounding a baseline distribution that estimates the ground truth (notably the empirical distribution), and the ball size is measured via a statistical distance.
Our main goal is to present a line of analysis to bound ( for DRO solutions, i.c.,
Eple(São: =)] - Ep(e((",))) =)]
which, instead of using functional complexity measures as in ERM, relies on the ambiguity set geometry and its compatibility with only the true loss function. More precisely, this bound depends on two ingredients: (i) the probability that the true distribution lies in K,, i.e., PP[P E X.] and, (ii) given that this occurs, the difference between the robust and true objective functions evaluated at the true solution f", i... maxqex [éf" :)]] [p[e(f" 2)]. These ingredients allow us to attain generalization bounds that depend on the hypothesis class in a distinct, less sensitive fashion from ERM. Specifically, when using the maximum mean discrepancy (MMD), Wasserstein distance, or 6-divergence as a statistical distance in DRO, our analysis implies generalization bounds whose dependence the hypothesis class L appears the minimal possible: The bound depends solely on the true loss function {(f", .), independent of any other {(f.) )) E L.
Note that although there exist generalization bounds that do not utilize conventional complexity measures like the VC dimension [1, they are all still dependent on other candidates in the hypothesis class and therefore, are different from our results. Examples include generalization bounds based on hypothesis stability [15), algorithmic robustness [16), the RKHS norm [17], and generalization disagreement [18.. These approaches all rely the data-driven algorithmic output fdaa. which varies randomly among the hypothesis class due to its dependence on the random training data. Therefore, to translate into generalization bounds, they subsequently require taking expectation over fasta ([I5) Definition 3 and Theorem 1 11]; [8 Theorem 4.2l) or taking a uniform bound over F (16) Definition 2 and Theorem 1]: [17] Theorem 4.2l). In contrast, our bound depends on the hypothesis class through the deterministic {(f", ), in a way that links to the choice of ambiguity set distance. To our best knowledge, generalization bounds of our type have never appeared in the literature (not only for DRO but also other ML approaches). We hope such a unique property will be useful in developing better machine learning algorithms in the future, especially in harnessing DRO on loss minimization and broader statistical problems.
Finally, our another goal is to conduct comprehensive review how DRO intersects with machine learning, which serves to position our new bounds over an array of motivations and interpretations of DRO. This contribution is in Section numerical experiments (Section(6)
2 before we present our main results (Section 3 and
2 Related Work and Comparisons
The latter advocates the handling of unknown or uncertain parameters in optimization problems via a worst-case perspective, which often leads to minimax formulations. 21 22 show the equivalence of
DRO can be viewed as a generalization of (deterministic) robust optimization (RO) 19 20

---

ERM regularization with RO in some statistical models, and [16] further concretizes the relation of generalization with robustness.
DRO, which first appeared in 23 in the context of inventory management, applies the worst-case idea to stochastic problems where the underlying distribution is uncertain. Like in RO, it advocates a minimax approach to decision-making, but with the inner maximization resulting in the worst- case distribution over an ambiguity set K. of plausible distributions. This idea has appeared across various disciplines like stochastic control [24] and economics [25] 26]. Data-driven DRO constructs and calibrates I. based on data when available. The construction can be roughly categorized into
two approaches: (i) neighborhood ball using statistical distance, which include most commonly o-divergence (27/31] and Wasserstein distance (32 [ (ii) partial distributional information
including moment 35 2 4
36). distributional shape [37 40] and marginal 4T4 constraints.
The former approach has the advantage that the ambiguity set or the attained robust objective value consistently approaches the truth (27 The second approach, on the other hand, provides flexibility
to decision-mate maker when limited data is available which proves useful on a range of operational or
risk-related settings 47
The first approach above, namely qadistialldiistane--aase DRO, has gained momentum especially in statistics and machine learning in recent years. We categorize its connection with statistical performance into three lines, and position our results in this paper within each of them.
2.1 Absolute Bounds Expected Loss
The classical approach to obtain guarantees for data-driven DRO is to interpret the ambiguity set K. as nonparametric confidence region, namely that IP K] 2 1 - 5 for small 5 E (0, 1). In this case, the confidence guarantee on the set can be translated into confidence bound on the true expected loss function evaluated at the DRO solution fãro in the form
P [e][fe 2)] S max (Elle(fao 2)Il 2 1 1-6 8
QEK
via a direct use of the worst-case definition of maxoex Eol.. This implication is very general, A main concern on results in the form (4) is that the bound could be loose (i.e., a large maxqex Eq [( 2)]). This, in some sense, is unsurprising the analysis only requires a confidence guarantee on the set IC, with no usage of other more specific properties, which is also the reason why the bound (4) is general. When K. is suitably chosen, a series of work has shown that the bound (4) can achieve tightness in some well-defined show that when IC is a Kullback-Leible divergence ball, maxqex TE [ =)] in (4) is the minimal among all possible data-driven formulations that satisfy given exponential decay rate on the confidence. [8] [50 51] show that for divergence- bbased KC, maxqex EEq (e(,,)) matches the confidence bound obtained from the standard central limit theorem by deducing that is
with K. taking possibly any geometry (e.g.. 22 27 32)
sense. 48 49
approximately [p(e(, =)] plus a standard deviation term (see more related discussion momentarily).
Our result leverages part of the above "confidence translation" argument, but carefully twisted to obtain excess risk bounds for ([. We caution that (4) is a result on the validity of the estimated objective value maxqex IQQ [f 2)] in bounding the true objective value Ep(((fã z)]. The excess risk (T). on the other hand, measures the generalization performance of solution in comparison with the oracle best. The latter is arguably more intricate it involves the unknown true optimal solution f and, as we will see, provides an intermediate building block in our analysis of
2.2 Variability Regularization
In a series of work 30
31
9 51], it is shown that DRO using divergence-based ball, i.e., n for some threshold 1) > 0 and D é-divergence (e.g.. Kullback-
K. 1Q E P D(Q, P)
Leibler, x -diitannce satisfies a Taylor-type expansion
max E [Q(((s=))] QEk:
where (f) is the standard deviation of the loss function, \Var[{[[ z)], multiplied by a constant
that depends on ø. Similarly, if D is the Wasserstein distance and v is of order 1/n, (5) holds
with Ci (f) being the gradient norm or the Lipschitz norm 112 5 52]. Furthermore, 17).
which is perhaps closest to our work, studies MMD as the DRO statistical distance and derives
3

---

boghhprobability bound for maxQex Eo(((f,z)] similar to the RHS of (5), with Ci(f) being the reproducing kernel Hilbert space (RKHS) norm of .(f.)). Results of the form ( can be used to show that maxoex Bo [Q[[[[] upon choosing ?) properly (of order 1 1/n), gives a confidence bound on B [[ =)
8
51
Moreover, this result can be viewed as a duality of the empirical likelihood
theory 55 12 51
54
In connecting (5) the solution performance, there are three implications. First, the robust objective function maxQex [e((e(())) can be interpreted as approximately mean-variance optimization, and 550 prove that, thanks to this approximation, the DRO solution can lower the variance of the attained loss which compensates for its under-pedt peadlr--erformance in the expected loss, thus overall leading to a desirable risk profile.
7 [55] have taken viewpoint that the variance of the attained loss is
important in the generalization. On the other hand, when the expected loss, i.e., the true objective
function E [ef( 2)], the sole consideration, the approximation (5) is used in two ways. One way
is to obtain bounds in the form
Ep =)] min (Ey [[(, C(U)//) O(1/n) JEF
(6)
thus showing that DRO performs optimally, up to ((1/n) error, on the variance- variance-regularrized objective function [9]. From this, [9] deduces that under special situations where there exists / with both small risk Ep (é({: =)] and variance Var({(J, (6) can be translated into a small excess risk bound of order 1 f/n. Moreover, such an order also desirably appears for DRO in some non-smooth problems
where ERM could bear 1/ The second way is to use DRO as a mathematical route to obtain uniform bounds in the form
Eple(S, =)] Ep(((s,))] C(OD/VV + O((/)) Ef
which is useful for proving the generalization of ERM. In particular, we can translate 7 into a high probability bound for Ep(e( =)] Ep(e("" =)] of order 1/ This use studied in, e.g., (56)
in the case of Wasserstein and in the case of MMD.
Despite these rich results, both 66 and (7). and their derived bounds on the excess risk ( still depend on other candidates in the hypothesis class through the choice of the ball size or the coefficient (f). Our main message in this paper is that this dependence can completely removed, when using the solution of a suitably constructed DRO. Note that this is different from localized results for ERM, e.g., local Rademacher complexities [57]. Although the latter establishes better generalization bounds by mitigating some dependence on the hypothesis class, local dependence other candidates still exists and cannot removed.
2.3 Risk Aversion
It is known that any coherent risk measure (e.g., conditional value-at-risk) 13 14] of random variable (in our case {(f,z) is equivalent the robust objective value maxqex Eo(e(f =)] with a particular K. Thus, DRO is equivalent to a risk measure minimization, which in turn explains its benefit in controlling tail performances. enhance performance on minority subpopulations and in safety or faimess- critiscl systems [38] A related application is adversarial training in deep learning, in which RO or DRO is used to improve test performances on perturbed input data and adversarial examples (39 60). DRO has also been used to tackle distributional shifts in transfer learning 61 62). In these applications, numerical results suggest that RO and DRO can come at degradation to the average-cast performance (63 60 64]
machine learning, this rationale has been adopted to
(though not universally, e.g., [65] observes that robust training can help reduce generalization error with very few training data). To connect, our result in this paper serves to justify generalization performance of DRO even in the average case that can potentially outperform ERM.
3 General Results
We first present a general DRO bound.
Theorem 3.1 (A General DRO Bound). Let Z C. IRd be a sample space. P be a distribution on Z, { be iid samples from P. and F be the function class. For loss function E F Z + R. DRO
solution fân E arg minser maxqex Ee[e(f, f(2)) 2)) satisfies that for any > 0,
P PPEpp(ffar 2) -E-EE x) > E] < P[P & K] +I PPImax (o)(((")))E(( =x)_") 2) > 8 p K3. (8)
QEK
4

---

Proof of Theorem 3.7 We first rewrite Ep Eple[far: 2)] - Bp - [p 2)] as the following three terms:
[E [ 2)] maX Eole(fao 2]]] + maxxexx 1erex:E2@ee 1 [[] 2)] maxqex Egle(f 2]]] +
(maxqex Eq ((f" =]] Ep (r(e(s" =]]] Note that the second term maxqex: Rol(Jan: =)
maxqek Eol(s" 2) I 0 almost surely by the DRO optimality of fum Also, by definition of
maxqer [ol.] as the worst-case objective function, we have maxqex Ro(((f.2) z)) 2 Ep(e(f,)) x)]
for all f E F as long as P E K. Thus,
P[Ep([fáro 2) Epl(f 2) > E] S
PIP
K + P max Ba Bolif Epl(f ,2) E, P
QEA
f PIP $ Kj
+
PP
mmxxE - Epp(f 2) > e P K..
QEX
This completes our proof.
key feature of the bound in Theorem 3.1 that it requires only the true loss function {(f":) This contrasts sharply with other bounds that rely on other candidates in the hypothesis class. To see where this distinction arises, note that in proof of Theorem 3.1 we divide Ep(e[fāno =)] [e( =)]
into three parts where the second term is trivially S 0 and the third term depends only on the true
loss. The key is that the first term satisfies Eplé[Sán =)] maxgex Eg (B]( =)] < 0 as long as
P E KC thanks to the worst-case definition of the robust objective function maxqex Eq (o]((( =)]. In
contrast, in the ERM case for instance, the same line of analysis gives [Er-[e(f* =) E [e(f =)]]
[E>l(ff,,) - E =]]l + [p(e(f", =]] - Ep [L[ [[]]",))]]]]_"""" and while the second and third terms handled analogously, the first term depends on f that varies randomly among the hypothesis class and is typically handled by the uniform bound y [p]{[[,=)]
[=](([,z)]] that requires empirical process analysis [66] and the complexity of the hypothesis class F or L. Thus, in sense, the worst-case nature of DRO "transfers" the uniformitt requirement over the hypothesis class into alternate geometrie requirements on only the true loss function.
4 Specialization to MMD DRO
4.1 Generalization Bounds
Our next step is to use Theorem 3.1 to derive generalization bounds for concrete DRO formulation. In the following, we use ambiguity set K. as a neighborhood ball of the empirical distribution measured by statistical distance, namely
(9) for a threshold v > O. Moreover, we specialize in max mean discrepancy (MMD) 667 as the choice of distance DMMMD(s.). -) MMD is distance derived from the RKHS norm, by using test functions constrained by this norm in an Integral Probability Metric (IPM) (68. Specifically, let k 2 x 2 - IR be positive definite kernel function on Z and (H. (.-)) be the corresponding RKHS. For any distributions Q1 and Q2, the MMD distance is defined by the maximum difference of the integrals over
K= K= E P PAMD <n}
the unit ball {h E H. ||A]] H S 1). That is, DMMD (Q1, Q2) == suphe H:IMM)N J hdQ - J hdQ2. In this way, MMD-DRO can be formulated as
min JEJ Q: D. P)
max
(10)
MMD is known to be less prone to the curse of dimensionality (69 711. a property that we leverage in this paper, and such property has allowed successful applications in statistical inference [67]. generative models (72 [3). reinforcement learning (74), and DRO 777 In particular, (76] studies the duality and optimization procedure for MMD DRO. For recent comprehensive review of MMD, we refer readers to
In the sequel, we adopt bounded kernels, i.c., sup v 2(2,2" < +00, to conduct our analy- sis. This assumption applies to many popular choices of kernel functions and more importantly, guarantees the so-called kernel mean embedding (KME) [77] is well-defines in RKHS. That is, uQ := f (((2.-)dg E H. A Q E P. This well-definedness of KME gives two important implica- tions. One is that MMD is equivalent to the norm distance in KME: DMMD Q) = ||p uall
78 67 Second, it bridges the expectation and the inner product in the RKHS space 77) A V E H. [f()] = fe (J, k(r, P(r) = (S. pr). Both properties above will facilitate our analysis. We refer the reader to Appendix A for further details on KME.
5

---

Theorem 4.1 (Generalization Bounds for MMD DRO). Adopt the notation and assumptions in Theorem 3.1 Let Z be a compact subspace of R. k Z x R be a bounded continu- ous positive definite kernel, and (H, (5)))) be the corresponding RKHS. Suppose also that (i) sup=E2 V /k(z,z) S K; (ii) e(f* E H. with [|e[f* 1l S M. Then, for all 6 2 0. if we choose ball size 1j vn (1+ + / log ( for MMD DRO (T)). then MMD DRO solution M satisfies
2KM
Eple( =)] Ep(e( =
vn (1 + 2llg((1)))
with probability at least 1 5.
We briefly overview our proof of Theorem 4.1 leaving the details Appendix B In view of Theo-
rem 3.1 the key lies in choosing the ball size 77 to make good trade-off between MMD (P.P) P) 2 n]
and an upper bound of maxqex Eg[e( =)] Ep[e(S" =)] when DMM P) < 7/. The former
can be characterized by the established concentration rate of KME (See Proposition B.T. To get the
latter bound, we use the properties of KME to translate expectations into inner products:
QEK max Eqle(S" =)] - Er(e( =)]
max(e(f" .Q pP) max [le( DRMD (Q, Q,P. P) QEK
QEK
S |le(ff" 112x max DMMD (Q, P) + DMMD (P, P)} - [e(( 11 27.
(11)
QEK
From these, we can choose 1) as indicated in Theorem 4.1 to conclude the result. In nutshell, here we harness the compatibility between K. and the true loss function ((f*, :). more specifically the RKHS norm on {(f", -), and the dimension-fre concentration of KME. Our general bound in Theorem 3.1
allows us stitch these two ingredients together to obtain generalization bounds for MMD DRO.
4.2 Strengths and Limitations Compared with ERM
Our generalization bound in Theorem 4.1 in fact still uti- lizes a uniformity argument, hidden in the distance con- struction. Note that our bound comprises essentially the product of [[((ff--)llx, which depends on the true loss function, and 77, the size of the ambiguity set. The lat- ter is controlled by DMMMD P). which is equivalent to the supremum of the empirical process indexed by Hi = (h h E H. ||/l/H S 1}. Note that this supre- mum is expressed through sup=c2 2k(2,,), which is independent of the hypothesis class.
L
e(
H1
Hyau
L2
Figure Let Li and L2 be two hy- pothesis classes with the same true loss function ((f".-). Li corresponds to functions in the oval and Le corre- sponds to functions below the straight line. In ERM, the uniform bound is taken directly over L1 (blue area) or La (pink area), while DRO gives the same bound that corresponds to uniformity over H Hger (orange area).
To understand this further, Figure I provides geometric representations on the classes of functions over which ERM and our DRO apply uniform bounds. From this we also argue how DRO relies less heavily on the hypothe- sis class. In ERM, the uniform bound is taken directly over the hypothesis class, say L. In DRO, from our dis- cussion above, the uniform bound is taken over dila- tion of the ball by a factor [[{ .) 1)l, equivalently -ijrrr.->>l>>> := {h E H. |//| [[((f", .>bb)). Thus, if two hypothesis classes contain the same true loss function {((*.) their DRO generalization bounds would be the same, while ERM could differ. In this sense, DRO generalization exhibits less reliance on the hypothesis class.
With the above understanding, we can see several situations where DRO could outperform ERM: (i) When [[(f", I is small compared to the size of L. Though one may argue that {(f",)) -) is typically unknown and hence we ultimately resort to using uniformity over L obtain any computable bound, our bound in terms of E(f".") :) explains why DRO can sometimes substantially outperform ERM. In Section 6. we provide an example where [|(([",))\lx = and the excess risk of DRO achieves zero with high probability. (ii) When uniformly bounding over Hi is "cheup". Many commonly used kernel spaces are bounded and therefore uniform bounds over Hi are trivial to establish (by Proposition B. which in turn leads to generalization bounds that depend only

---

dilation (by ([(ff,))]l>) of these uniform bounds over H1. This is regardless of how complex the hypothesis class C is. including when || 30 or C = H. ERM. contrast, uses uniformity
over &. and can result in exploding generalization bound when || = co. (iii) When L. E H. || S B}. the ERM bound yields 2B su {Ph- - ph} since B = supre [|((-)]l z. while the DRO bound gives 21|e(f", supee,, {Ph- ph} that depends only on the true loss function and is smaller.
resembles the geometry of H. For instance, when & HB == (h
Suрлeи,
Despite the strengths, our bound in Theorem 4.1 also reveals situations where DRO could under- perform ERM: When L has a shape deviating from the RKHS ball such that L C H (llee then taking uniform bounds over Hi eif" , is costly compared to over L, which case DRO generalization bound is worse than ERM. Moreover, note that ((f",)) the optimal loss within L, can shift when & becomes richer. In this sense Theorem 4.1 cannot completely remove the dependency on the hypothesis class, but rather diminishes to the minimum possible: The resulting bound does not rely on any other candidates in the hypothesis class except ((f".)).
Remark 4.2. There exists another line of work that establishes generalization bounds with faster rate O( -1 for ERM [79 57 80 8T] and d-divergence DRO [9] However, they are all based on additional curvature conditions F or C to relate the loss/risk and variance. Improving our bounds towards On 1) rate is potentially achievable and constitutes future work.
4.3 Comparison with [17]
For bounds that do not utilize conventional complexity measures, to the best of our knowledge, they are still dependent on other candidates in the hypothesis class; recall our discussion in Section [1] As concrete example, we compare our results with [17). which also studies generalization related to MMD DRO and appears the most relevant to our paper. First, different from our research goal, [17 aims to
use MMD DRO as an analysis tool to derive uniform bounds for Ep =)] - Ep(e(f. =)]. Aʃ E F. More specifically, the main argument for their Theorem 4.2 is that, with high probability, one has
Ep -Ep [)]((
log(1/6) for any given f. Although this bound seems to depend on a single loss function {(f, -), any algorithmic output, say faama- needs be learnt from data and is thus random. This means that to construct a generalization bound, one has to either average over fama take supremem over f E F. (17) adopts the latter approach and establishes bound
0(1
Ep([ff, 2)] pe( 2)] = Osuuye== Il((f.-)llxy log(1/8)), ) v E F in their Theorem 4.2. Our Theorem 4.1 in contrast, only depends on [|((ff,-)]lx which is potentially much tighter and provides a distinct perspective.
Second, our Theorem 4.1 also distinguishes from 17 in that our bound applies specifically to the MMD DRO solution M-dro and reveals a unique property of this solution. This should be contrasted to 17 whose result is a uniform bound for any f E F, without any specialization to the DRO solution. This also relates to our next discussion.
4.4 Comparison with RKHS Regularized ERM
We also compare our results to RKHS regularized ERM:
min { + xl
(12)
JEF
When we additionally assume L c H. it is known that MMD DRO is equivalent to min
E(f, 2) + r]]((ff-))lx JEF
(13)
according to [17 Theorem 3.1]. Although (12) and 13) appear similar, their rationales are different.
When regularizing |l the goal is maintain the simplicity of f. In comparison, through (13)
we are in disguise conducting DRO and utilizing its variability regularization property (Recall
Section 2.2 This observation motivates [77 to consider regularizing f(f.-) instead of f itself. Our Theorem 4.1 reveals the benefit of regularizing ((f.-) -) at new level: Regularizing [
increases the likelihood of Ep[e(Sáidr:: =)] - maxqex I [ =)] S O, which is argued by looking at the distribution space, instead of the loss function space, more specifically from the likelihood of a DRO ambiguity set covering P. Because of this, we can establish generalization bounds that depend on the hypothesis class only through the true loss {ff", .-) for EKHS-regularize
7

---

ERM when the regularization is on ((f. Furthermore, thanks to this we can relax the assumption C H.. adopted in (T3) to merely {(f" H which all we need in MMD DRO. Lastly, we point out that our analysis framework is not confined only to MMD, but can be applied to other distances
in defining DRO (See Section (5)
4.5 Extension {((",)) $ H
In Theorem 4.1 we assume (i) supzEx v << S K: (i) (i) ((f",) E H. with [|((ff. S M. Although (i) Is natural for many kernels, (ii) can be restrictive since many popular loss functions do not satisfy ((f*,)) E H. For instance, if k is a Gaussian kernel defined on
F that has nonempty interior, then any nonzero polynomial on Z does not belong to the induced RKHS H [82]. This is in fact a common and well-known problem for almost all kernel methods [83] though many theoretical kernel method papers just assume the concerned function g E H. for simplicity, e.g., [84, 85 17. This theory-practicn gap motivates us to extend our result E(f", & H.
To this end, note that under universal kernels 86), any bounded continuous function can be ap- proximated arbitrarily well (in 7 norm) by functions in H. However, the RKHS norm of the approximating function, which appears in the final generalization bound, may grow arbitrarily large as the approximation becomes finer [87 [3]. This therefore requires analyzing trade-off between the function approximation error and RKHS norm magnitude. More specifically, we define the approxima- tion rate [E((", -), R) == inf [لsl s. ||e(f" -) gl and gn == arg [ell S. [e((", gll
As concrete example, we adopt the Gaussian kernel and the Sobolev space to quantify such a rate and establish Theorem 3 below.
Theorem 4.3 (Generalization Bounds for Sobolev Loss Functions). Let (H, ||
(lx)) be the RKHS induced by k(z,z') exp(-liz- 1o/za==1p 21122/²²) on 2 = [0, 1] Suppose that E(f",)) is in the Sobolev space H Then, there exists a constant C independent of R but dependent on ((f .)) d, and o
such that for all 8 2 0, if we choose ball size 1) = - (1 + / (og()))) for MMD DRO (0). then
MMD DRO solution dm satisfies
R (1+ /2 2log(110))
Ep Pe dro =)] Er(e(f 22 2))
inf C(loog R + 121
(14)
with probability at least 1 5.
We briefly outline our proof, leaving the details to Appendix C When {(f",-) :)) & H. we cannot use KME to rewrite expectation as inner products as shown in (11. Rather, we will approximate ((f*.-) by some On E H and obtain Er(e(f" =)] S Er(gn(>)] T(((f".)). R). Since gn E H. similar to [1] we can derive generalization bound of gR. which appears in the second term of (1).. Then, suffices to take infinum over Rt 2 1 to establish the aforementioned trade-off between the approximation error I(E( R) (the first term of (14) and the RKHS norm [|rR|| S R (the
second term of (4)
Compared to Theorem 4.1 here we have to pay an extra price on the solution quality when the loss function is less compatible with the chosen RKHS, i.c., E(f", & H. Concretely, in the setting of Theorem 4.3 T(e(f" -), R) I C(log R)- d/16
87 and this results in a worse convergence rate in n. For example, inserting R = /villo n) -d/1 into (14 yields O(max(C: / (To) (log n) -16/d). This convergence rate is rather slow. However, it mainly results from the slow approximation rate I(((f", -), R) established by non-parametric analysis. If we further utilize the structure of ((f",.), then a faster convergence rate or even close to O(n -1/2) rate can potentially achieved. Nonetheless, our main message in Theorem 4.3 is that even if (((",)) :) & H. our bound (14) still depends minimally on the hypothesis class L: The bound depends solely on the true loss function E(f", ((f",.). :), independent of any other f(f,-) L.
5 Specialization to I-Wasserstein and x2 -ddieergeece DRO
Our framework can also be specialized to DROs using other statistical distances. Below, we derive results for DROs based on the I-Wasserstein distance and x² -iveerggee, and discuss their implica-
9R is well-defined since for tixed H, h(g) = (|é(S",) glloo is continuous function over compact set {g: g H. [1 & R).
8

---

tions and comparisons with MMD DRO. Due to page limit, we delegate more detailed discussions to Appendix D Let fw-dro be the solution 1- 1-Wasserstein DRO (See Appendix D.I. and f dro be the solution to --dvvergeenc DRO (See Appendix D.2). Also denote || I|ui the Lipschitz norm. Then, we have the following generalization bounds.
Theorem 5.1 (Generalization Bounds for 1-Wasserstein DRO). Suppose that P is a light-tailed distribution in the sense that there exists a > 1 such that A := Eplexp [[]=][)] < 00. Then, there exists constants e1 and 0g that only depends on a, and d such that for any given <
5 < 1, if we choose ball size = - (los(es/81) max(d.2) m and 2 log(cr/8), then fw-r satisfies Ep Ep(e(f W-dro: =)] Ep[e(f", 2) S 21(e(f" :>llpppp
(oggle//0) m/x/(,,)))) with probability at least - 8. con
Theorem 5.2 (Generalization Bounds for x2 diverggee DRO on Discrete Distributions), Suppose that P is discrete distribution with m support with Pf= z3] Pi- Suppose that (i) Pmin minigism Ps > 0: (ūi) [[e[]", Ilooo < +00. Then, for all < 8 < 1, if we choose ball size 7 (m + 2 (0og(4/0) + 2 2/m (4464)))) (2 DRO, then for all n 2 m0
Fanin 521 dr
satisfies [p[e(f
x² dm 2) Eple(f" 2)1 ()e((f)-)))) vn v m + log((4/5) + 2 mm log 446)) +
2log(2/6) with probability at least 1 6.
Theorems 5.1 and 5.2 are obtained by analyzing the two components in Theorem contains true distribution P with high confidence and (2) compatibility of the statistical distance with ((f The bounds in Theorems 5.1 and 5.2 involve only -() but not other candidates in the hypothesis class. Notice that if P continuous, then using x- -dvverrgence, and more generally o-divergence (See Definition D.3). for DRO entails bit more intricacies than MMD and Wasserstein DRO. Due the absolute contimuity requirement the definition, if continuous, then ş-divergence ball centered P will never cover the truth, which violates the conditions required in developing our generalization bounds. In Theorem 5.2 to showcase how generalization bounds of ø-divergence DRO depend on the hypothesis class, we present an explicit bound for discrete P and x² diveeeege,, for which we can use P-centered ambiguity set. To remedy for continuous P', one can set the ball center using kernel density estimate or parametric distribution, albeit with the price of additional approximation errors coming from the "smoothing" of the empirical distribution. In Appendix D.2. present general bound (Theorem D.4] for o-divergence DRO that leaves open the choice of the ball center and the function Φ. Once again, this generalization bound involves only [(f", -) but not other candidates in the hypothesis class. However, we would leave the explicit bounds of other cases than that of Theorem 5.2 including the choice and usage of the remedial smoothing distributions in the continuous case, separate future work.
Like Theorem 4.1
3.1 which correspond to: (1) the ambiguity
Moreover, in our result for Wasserstein DRO, the rates in terms of n is n 1/ max(d.)). which is slower than our result for MMD DRO in Theorem 4.1 and the classical ERM rate n 1/2 The slow rate of Wasserstein DRO comes from the large ball size needed to confidently cover the true P and control
the first term of Specifically, the ball size is controlled by the 1-Wasserstein distance Dw; (P, P). which is equivalent to the supremum of the empirical process indexed by Lip, := - ||t||Lip < 1} by the dual representation of Dw, ( [88). Similar to our discussion in Section 4.2 Theorem 5.
shows a tradeoff between the hypothesis class dependence and the rate in n that differs from ERM.
More precisely, Wasserstein DRO has generalization that favorably relies only on the true loss
10"
10
10
10"
ERM, B=1
10%
ERM, B=1, n:30
e00380 flok
ERM, B=10
ERW, B=1, n=10
ERM, B-100
10" 11
ERM, B-1 n-20
DRO, B=1
DRO, B=1, n=30
DRO. B-10
10"
DRO, B-1, 1=00
DRO. B- 100
DRO, B-1, 2000
10"
10
50
75
100
125
150
175
200
0.01
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
sample size
(a) Performance of ERM and DRO under varying n
(b) Performance of ERM and DRO under varying 7)
Figure 2: Excess risks of ERM and DRO
9

---

:()" ). but scales inferiorly in terms of n (due to uniformity over Lip,). ). is thus most suited when the complexity of hypothesis class outweighs the convergence rate consideration. In Appendix E we will describe the distribution shift setting where such a tradeoff can be amplified.
We also note that, unlike Wasserstein DRO, x -iveeeneeee DRO retains rate of 1/vn. However, this is because Theorem 5.2 has focused on the finite-support case, where the number of support points m comes into play in the multiplicative factor instead of the rate. If we consider continuous P and use a smooth baseline distribution (instead of P), we expect the rate of x² divergencce DRO to deteriorate much like the case of Wasserstein DRO and there may exist a similar tradeoff.
Numerical Experiments
We conduct simple experiments to study the numerical behaviors of our MMD DRO and compare
with ERM on simulated data, which serves to illustrate the potential of MMD DRO in improving
generalization and validate our developed theory. We adapt the experiment setups from O Section
5.2] and consider a quadratic loss with linear perturbation: I(0, 2) = 2 ||0 - v1 + 2 (A v). where
2 ~ Unif[- [B, B]d with constant B varying from {1, 10, 100) in the experiment. Here, F = (0)
0 E } and we use f and 9 interchangeably. v is chosen uniformly from [1/2, 1] and is known to the learner in advance. In applying MMD DRO, we use Gaussian kernel k(z, x exp(-112 2 o=! with a set to the median of 21 - 2ا112 A i. according to the well-known median heuristic 667. To solve MMD DRO, we adopt the semi-infinite dual program and the constraint sampling approach from (76). where we uniformly sample a constraint set of size equal to the data size n. The sampled program is then solved by CVX [89] and MOSEK [90]. Each experiment takes the average performance of 500 independent trials. Our computational environment is a Mac mini with Apple MI chip, 8 GB RAM and all algorithms are implemented in Python 3.8.3.
In Figure 2 a), we present the excess risks of ERM and DRO, i.e., Ep[e(faan;: -Epp =)], where /aata denotes the ERM DRO solution. We set d = 5 and tune the ball size via the best among 7 E {0.01, 0.05, 0.1, 0.15, ...........
(more details to be discussed on Figure (
momentarily). Figure 2 a) shows that, increases, both DRO and ERM incur decreasing loss. More importantly, DRO appears to perform much better than ERM. For n = 200 and = 100 for instance, the expected loss of DRO is less than 10-20, yet that of ERM remains around 10º.
We attribute the outperformance of DRO to its dependency on the hypothesis class only through the true loss function ((f", :). This can be supported by an illustration on the effect of ball size 17. In Figure (b), we present excess risk Ep]e(famn: }]] - Ep( [=]((((,))) =)] for = 1, = 5, n = 50, and varying 1/. We see that the excess risk of the DRO solution drops sharply when 1) is small, and then for sufficiently big 7, i.e., 1) E [0.5. 1]. it remains at a fixed level of 10-19, which is close to the machine accuracy of zero (such "L" -hashh excess loss also occurs under other choices of sample size n, and we leave out those results to avoid redundancy). Such a phenomenon coincides with our theorems. First, note that f and the optimal loss function satisfies ||{(f= 1| ||0| 0. so that our assumptions in Theorem 4.1 are satisfied, Recall that by Theorem
3.1
PlEppe(f dmo 2) - Epf(f" 2) > c] < P(P & K. + PP mmxx Eol(f", 22 E Ep((f* > E E E K].
QEA
Conditioning on P IC, we have Mi f and maxoex Eg [MMi 2)] EplE(f =)]
0. Thus, the above inequality yields [ dno =]] - Ep[ =)] > E| < PP $ K.. The proof
of T'ehhrrmma 4.1 reveals that V 8 > 0. if the ball size is big enough, namely 17 2 V (1+ /2
K
then excess risk will vanish, i.e., E (e(
/ M =]] Ep(e( =)] = 0 with probability 2
This
behavior shows up precisely in Figure (b).
Our discussion above is not suggest the choice of r) in practice. Rather, it serves as a conceptual proof for the correctness of our theorem. In fact, to the best of our knowledge, none of the previ- ous results, including the multiple approaches to explain the generalization of DRO reviewed in Section
2 can explain the strong outperformance of DRO with the "L""shape phenomenon in this example. These previous results focus on either absolute bounds (Section 2 or using variability regularization (Section 2.2) whose bounds, when converted to excess risks, typically increase in when v is sufficiently large and, moreover, involve complexity measures on the hypothesis class (e.g., the didivergence case in [ Theorems 3, 6] and the Wasserstein case in [56] Corollaries 2, 4J). Our developments in Section 3 thus appear to provide a unique explanation for the significant outperformance of DRO in this example.
10

---

Acknowledgments and Disclosure of Funding
We gratefully acknowledge support from the National Science Foundation under grants CAREER CMMI-183471I and IIS- 18S-1849280. We also thank Nathan Kallus and Jia-Jie Zhu for the greatly helpful discussion that helps improve this paper.
References
[1] Vladimir Vapnik and Alexey Chervonenkis. The necessary and sufficient conditions for consis- tency in the empirical risk minimization method. Pattern Recognition and Image Analysis, 1(3): 283-305, 1991.
[2] Erick Delage and Yinyu Ye. Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations Research, 58(3):595 612, 2010.
[3] Joel Goh and Melvyn Sim. Distributtonaally robust optimization and its tractable approximations. Operations Research, 28(4-Part-1)):022 917000299971-000 2010.
[4] Wolfram Wiesemann, Daniel Kuhn, and Melvyn Sim. Distributionally robust convex optimiza- tion. Operations Research, (366):358-111) 2014.
[5] Rui Gao, Xi Chen, and Anton Kleywegt. Wasserstein distributionally robust optimization and variation regularization. arXiv preprint arXiv:1712.060550 2017.
[6] Ruidi Chen and loannis Paschalidis. robust learning approach for regression models based on distributionally robust optimization. Journal of Machine Learning Research, 19(13), 2018.
[7] Jun-ya Gotoh, Michael Jong Kim, and Andrew EB Lim. Robust empirical optimization is almost the same as mean-variance optimization. Operations Research Letters, 46(4)):48-452, 2018.
[8] Henry Lam. Recovering best statistical guarantees via the empirical divergence- distribu- tionally robust optimization. Operations Research, 6700):100 2019.
[9] John C Duchi and Hongseok Namkoong. Variance-based regularization with convex objectives. Journal of Machine Learning Research, 2019.
[10] Sorcosh Shafieczadeh-Abate Abadeh, Daniel Kuhn, and Peyman Mohajerin Esfahani. Regularization via mass transportation. Journal of Machine Learning Research, 20(103):1 2019.
[11] Daniel Kuhn, Peyman Mohajerin Esfahani, Viet Anh Nguyen, and Soroosh Shafieezadeh- Abadeh. Wasserstein distributionally robust optimization: Theory and applications in machine learning. In Operations Research & Management Science in the Age of Analytics, pages 130-166. INFORMS, 2019.
[12] Jose Blanchet, Yang Kang, and Karthyek Murthy. Robust Wasserstein profile inference and applications to machine learning. Journal of Applied Probability, 56(3):830-83 857, 2019.
[13] Andrzej Ruszezyński and Alexander Shapiro. Optimization of convex risk functions. Mathe- matics of Operations Research, 31(3):433 452, 2006.
[14] R Tyrrell Rockafellar. Coherent approaches to risk in optimization under uncertainty. In OR Tools and Applications: Glimpses of Future Technologies, pages 38-61 61. Informs, 2007.
[15] Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2:499-526, 2002.
[16] Huan Xu and Shie Mannor. Robustness and generalization. Machine Learning, 86(3):391-433, 2012.
[17] Matthew Staib and Stefanie Jegelka. Distributionally robust optimization and generalization in kernel methods. In Advances Neural Information Processing Systems, pages 9131-9141, 2019.

---

[18] Yiding Jiang, Vaishnavh Nagarajan, Christina Back, and Zico Kolter. Assessing generalization of SGD via disagreement. International Conference on Learning Representations, 2022.
[19] Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust Optimization. Princeton University Press, 2009.
[20] Dimitris Bertsimas, David Brown, and Constantine Caramanis. Theory and applications of robust optimization. SIAM Review, 534));464-501, 2011.
[21] Huan Xu, Constantine Caramanis, and Shie Mannor.
Robustness and regularization of support vector machines. Journal of Machine Learning Research, 10(7), 2009.
[22] Huan Xu, Constantine Caramanis, and Shie Mannor. Robust regression and Lasso. IEEE Transactions Information 56
2010.
[23] Herbert Scarf. A min-max solution an inventory problem. Studies in the Mathematical Theory of Inventory and Production, 1958.
[24] lan Petersen, Matthew R James, and Paul Dupuis. Minimax optimal control of stochastic uncertain systems with relative entropy constraints. IEEE Transactions on Automatic Control, 45(3):398-413 2000.
[25] Lars Peter Hansen and Thomas J Sargent. Robustness. Princeton University Press, 2008.
[26] Paul Glasserman and Xingbo Xu. Robust risk measurement and model risk. Finance, 14(1):29-58, 2014.
Quantitative
[27] Aharon Ben-Tal, Dick Den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 59(2)3341-357, 2013.
[28] Güzin Bayraksan and David Love. Data-driven stochastic programming using phi-divergences. In Tutorials in Operations Research, pages 1-19. INFORMS, 2015.
[29] Ruiwei Jiang and Yongpei Guan. Data-driven chance constrained stochastic program. Mathe- matical Programmingg 158(1):911337,, 2016.
[30] Henry Lam. Robust sensitivity analysis for stochastic systems. Mathematics of Operations Research, 4144): 2016.
[31] Henry Lam. Sensitivity to serial dependency of input processes: robust approach. Manage- ment Science, 64(3):111111327, 2018
[32] Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations. Mathemati- cal Programming. (71(1-2):115-16) 2018.
[33] Jose Blanchet and Karthyek Murthy. Quantifying distributional model risk via optimal transport. Mathematics of Operations Research, 44(2):555-600, 2019.
[34] Rui Gao and Anton J Kleywegt. Distributionaaly robust stochastic optimization with Wasserstein distance. arXiv preprini 1644v:1604.02//99 /99 2016.
[35] Laurent El Ghaoui, Maksim Oks, and Francois Oustry. Worst-case value-at-risk and robust portfolio optimization: A conic programming approach. Operations Research, (1(4):543-556 2003.
[36] Grani A Hanasusanto, Vladimir Roitch, Daniel Kuhn, and Wolfram Wiesemann. A distribu- tionally robust perspective on uncertainty quantification and chance constrained programming. Mathematical Programming, 151(1):35 -2, 2015.
[37] Ioana Popescu. semidefinite programming approach to optimal-moment bounds for convex classes of distributions. Mathematics of Operations Research, 30(3):632-653 2005.
12

---

[38] Bart PG Van Parys, Paul J Goulart, and Daniel Kuhn. Generalized Gauss inequalities via semidefinite programming. Mathematical Programming. 156(1-2)2711302 2016.
[39] Bowen Li, Ruiwei Jiang, and Johanna L Mathieu. Ambiguous risk constraints with moment and unimodality information. Mathematical Programming, pages 1-42, 2017.
[40] Xi Chen, Simai He, Bo Jiang. Christopher Thomas Ryan, and Teng Zhang. The discrete moment problem with nonconvex shape constraints. Operations Research, 2020.
[41] Louis Chen, Will Ma, Karthik Natarajan, David Simchi-Levi, and Zhenzhen Yan. Distribu- tionally robust linear and discrete optimization with marginals. Available at SSRN 3159473, 2018.
[42] Xuan Vinh Doan, Xiaobo Li, and Karthik Natarajan. Robustness to dependency in portfolio optimization using overlapping marginals. Operations Research, (3(6))1468-1444 2015.
[43] Anulekha Dhara, Bikramjit Das, and Karthik Natarajan. Worst-case expected shortfall with univariate and bivariate marginals. INFORMS Journal on Computing, 33(():370-389) 2021.
[44] Dimitris Bertsimas, Vishal Gupta, and Nathan Kallus. Robust sample average approximation. Mathematical Programming. 171(1-2):217-28,, 2018
[45] Yiling Zhang. Siqian Shen, and Johanna L. Mathieu. Distributionally robust Chance-constrainee optimal power flow with uncertain renewables and uncertain reserves provided by loads. IEEE Transactions on Power Systems, 32(2):1378 -188888888888----111111888888888
1388, 2016.
[46] Henry Lam and Clementine Mottet. Tail analysis without parametric models: A worst-case perspective. Operations Research, 1596)116961711, 2017.
[47] Chaoyue Zhao and Ruiwei Jiang. Distributionally robust contingency--conttriined unit commit- ment. IEEE Transactions on Power Systems, 33(1):94-102, 2017.
[48] Bart PG Van Parys, Peyman Mohajerin Esfahani, and Daniel Kuhn. From data decisions: Distributionally robust optimization is optimal. Management Science, 2020.
[49] Tobias Sutter, Bart PG Van Parys, and Daniel Kuhn. A general framework for optimal data- driven optimization. arXiv preprint Xii:20000006600 2020.
[50] Vishal Gupta. Near-optimal Bayesian ambiguity sets for distributionally robust optimization. Management Science, 65(9):4242-4466 2019.
[51] John Duchi, Peter W Glynn, and Hongseok Namkoong. Statistics of robust optimization: generalized empirical likelihood approach. Mathematics of Operations Research, 2021.
[52] Jose Blanchet, Karthyek Murthy, and Nian Si. Confidence regions in Wasserstein distributionally robust estimation. arXiv preprint arXiv: 1966006614 2019.
[53] Henry Lam and Enlu Zhou. The empirical likelihood approach to quantifying uncertainty in sample average approximation. Operations Research Letters, 45(4):301 - 307, 2017. ISSN 0167-6377.
[54] Jose Blanchet and Yang Kang. Sample out-of-sample inference based on Wasserstein distance. Operations Research, 2021.
[55] Jun-ya Gotoh, Michael Jong Kim, and Andrew EB Lim. Calibration of distributionally robust empirical optimization models. Operations Research, 2021.
[56] Rui Gao. Finite-sample guarantees for Wasserstein distributionally robust optimization: Break- ing the curse of dimensionality. arXiv preprint arXiv:2009.04388 2020.
[57] Peter L Bartlett, Olivier Bousquet, Shahar Mendelson, et al. Local Rademacher complexities. The Annals of Statistics, 4374):197711537 2005.
[58] Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness without demographies in repeated loss minimization. In International Conference on Machine Learning, pages 1929-1938. PMLR, 2018.
13

---

[59] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adver- sarial examples. International Conference on Learning Representations, 2015.
[60] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. International Conference on Learning Representations, 2018
[61] Shiori Sagawa, Pang Wei Koh, Tatsunori Hashimoto, and Percy Liang. Distributionally robust neural networks. In International Conference on Learning Representations, 2020.
[62] Jiashuo Liu, Zheyan Shen, Peng Cui, Linjun Zhou, Kun Kuang, Bo Li, and Yishi Lin. Stable adversarial learning under distributional shifts. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 8662-8670, 8670, 2021.
[63] Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial machine learning at scale. In International Conference on Learning Representations, 2017.
[64] John C Duchi and Hongseok Namkoong. Learning models with uniform performance via distributionally robust optimization. The Annals of Statistics, 49(3):1378-1400 2021.
[65] Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. In International Conference on Learning Representations, 2019.
[66] Aad W Van Der Vaart and Jon A Wellner, Weak Convergence and Empirical Processes. Springer, 1996.
[67] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. kernel two-sample test. Journal of Machine Learning Research, 13(1):723-773 2012.
[68] Alfred Müller. Integral probability metries and their generating classes of functions. Advances in Applied Probability, pages 429-443, 1997.
[69] John Shawe-Taylor, Nello Cristianini, et al. Kernel Methods for Pattern Analysis. Cambridge University Press, 2004.
[70] Alex Smola, Arthur Gretton, Le Song, and Bernhard Schölkopf. A Hilbert space embedding for distributions. In International Conference on Algorithmic Learning Theory, pages 13-31. Springer, 2007.
[71] Steffen Grünewälder, Guy Lever, Arthur Gretton, Luca Baldassarre, Sam Patterson, and Massi- miliano Pontil. Conditional mean embeddings as regressors, In International Conference on Machine Learning, 2012.
[72] Yujia Li, Kevin Swersky, and Rich Zemel. Generative moment matching networks. In Interna- tional Conference on Machine Learning, pages 1718-1727. PMLR, 2015.
[73] Danica J. Sutherland, Hsiao- Yu Tung, Heiko Strathmann, Soumyajit De, Aaditya Ramdas, Alexander J. Smola, and Arthur Gretton. Generative models and model criticism via optimized maximum mean discrepancy. In International Conference on Learning Representations, 2017.
[74] Thanh Tang Nguyen, Sunil Gupta, and Svetha Venkatesh. Distributional reinforcement learning with maximum mean discrepancy. arXiv preprint arXiv:2007.12354, 2020.
[75] Johannes Kirschner, Ilija Bogunovic, Stefanie Jegelka, and Andreas Krause. Distributionally robust Bayesian optimization. In Artificial Intelligence and Statistics, pages 2174-2184, PMLR, 2020.
[76] Jia-Jie Zhu, Wittawat Jitkrittum, Moritz Diehl, and Bernhard Schölkopf. Kernel distributionally robust optimization: Generalized duality theorem and stochastic approximation. Artificial Intelligence and Statistics, volume 130, pages 280-288. PMLR, 2021.
14

---

[77] Krikamol Muandet, Kenji Fukumizu, Bharath Sriperumbudur, and Berhhard Schölkopf. Kernel mean embedding distributions: A review and beyond. Foundations and Trends@ in Machine Learning, 10(1-2):1-141, 2017. ISSN 1935-8237.
[78] Karsten M Borgwardt, Arthur Gretton, Malte J Rasch, Hans-Peter Kriegel, Bernhard Schölkopf, and Alex Smola. Integrating structured biological data by kernel maximum mean discrepancy. Bioinformatics, 22 (2(1))c49-e55 2006.
[79] Shahar Mendelson. On the performance of kernel classes. Journal of Machine Learning Research, 4:759-771, 2003.
[80] Peter L Bartlett, Michael I Jordan, and Jon D McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-156 2006.
[81] Martin Wainwright. High-Dimensional Statisties: Non-Asymptotic Viewpoint, volume 48. Cambridge University Press, 2019.
[82] Ha Quang Minh. Some properties of Gaussian reproducing kernel Hilbert spaces and their implications for function approximation and learning theory. Constructive Approximation, 32 (2):307-338, 2010.
[83] Yaoliang Yu and Csaba Szepesvári. Analysis of kernel mean matching under covariate shift. In International Conference on Machine Learning, 2012.
[84] Corinna Cortes, Mehryar Mohri, Michael Riley, and Afshin Rostamizadeh. Sample selection bias correction theory. In International conference on algorithmic learning theory, pages 38-53. Springer, 2008.
[85] Takafumi Kanamori, Taiji Suzuki, and Masashi Sugiyama. Statistical analysis of kernel-based least-squares density-ratio estimation. Machine Learning, 86(3):335-367, 2012.
[86] Ingo Steinwart. On the influence of the kernel on the consistency of support vector machines. Journal of Machine Learning Research, 2(Nov):67-93, 2001.
[87] Felipe Cucker and Ding Xuan Zhou. Learning Theory: An Approximation Theory Viewpoint, volume 24. Cambridge University Press, 2007.
[88] Leonid Vasilevich Kantorovich and SG Rubinshtein. On space of totally additive functions. Vestnik of the St. Petersburg University: Mathematics, 13(7):52-59 1958.
[89] Michael Grant and Stephen Boyd. CVX: Matlab software for disciplined convex programming, version 2.1, 2014.
[90] MOSEK ApS. The MOSEK optimization toolbox for Python manual. Version 9.2.46., 2021. URL https::///ooo mosek. . com/ 99 wtt.///hooffssioo///nnooooa www.ooniiininieiieee html
[91] Iyya Tolstikhin, Bharath K Sriperumbudur, and Krikamol Muandet. Minimax estimation of kernel mean embeddings. Journal of Machine Learning Research, 18(1 (8(1):3002-3048 2017.
[92] Ding-Xuar Xuag Zhou. Density problem and approximation error in learning theory. In Abstract and Applied Analysis, volume 2013. Hindawi, 2013.
[93] 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-73,, 2015.
[94] Robert E Gaunt, Alastair M Pickett, and Gesine Reinert. Chi-square approximation by stein's method with application to pearson's statistic. The Annals of Applied Probability, 27(2): 720-756, 2017.
[95] Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, pages 1302-1338, 2000.
15


Reviews:
[{"review_id": "sGBTQUelIwu", "reviewer": "Reviewer_J945", "summary": "The paper presents novel bounds that hold for the DRO hypothesis. Interestingly, unlike ERM, uniform bounds are not required and for MMD-DRO the final bound depends only on the optimal hypothesis. Also, unlike local RA bounds, there is no dependence on few other hypothesis.\n\nThe bound follows from the key theorem3.1, which though is a simple observation, seems to be special to DRO and does not hold for ERM etc. The final bound for MMD-DRO is presented in theorem4.1. Again, though a simple derivation, is nevertheless interesting.\n\nApart from the main results, the paper presents other discussions on related bounds, and section 5, where a technical requirement in theorem 4.1 is dropped.\n\nFinally, simulations supporting the theory are presented.", "questions": "1. While the methodology proposed is general, details are given only for the MMD-DRO case. Another related case that has been shown to be promising is the Wasserstein-DRO case. Can this case be analysed in detail? Will it also lead to bounds dependent on f^* only? why/why not?\n\n2. Distributional shift is another related case. Can Appendix D be expanded into a main section providing some insights?", "limitations": "Yes, insightful discussions are presented in sec4.2.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well-written and is a pleasure to read. The result in theorem4.1 is indeed interesting as it has no dependence on any other hypothesis than the optimal.\n\nThe bounds also open up many interesting questions, while they explain why DRO performs well in practice. Though the work tries to answer some of them in section5,appD etc., the work would have been far more stronger with a deeper discussion of them. A couple of these questions I summarize in the subsequent section.\n\nOverall, I feel the main strength of the work is the elegant bounds, while weakness is perhaps presentation of a bit fewer results than a good article would contain.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1MtB0IxorwS", "reviewer": "Reviewer_fMCk", "summary": "In this paper, authors present generalization bounds on the solution from distributionally robust optimization (DRO). In contrast to the hypothesis class complexity in ERM, DRO bounds presented depend on the ambiguity set geometry and its compatibility with the true loss function. They instantiate the DRO bound by using the maximum mean discrepancy DRO distance metric. Their analysis derives generalization bounds that depend solely on the true loss function, independent of any other candidates in the hypothesis class.", "questions": "See questions in the detailed weaknesses above. ", "limitations": "This work has no potential negative societal impact. However, no discussion on limitations or future work is provided. It would insightful if the authors could elaborate on this in the context of the last sentence in the abstract. ", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**: \n- Author presents an alternate route avoiding dependency on the complexity class of the function to obtain generalization bounds on the solution from distributionally robust optimization. \n- A general DRO bound in Theorem 3.1 is provided before instantiating it in the MMD DRO framework. \n\n**Weakness**: \n\n- The main result in the paper is hard to parse, mainly because of a missing Problem setup section. It would be great if the authors can add a small section describing the notation and the setup very clearly. \n- In equation 8, what is the probability measure for the first term in RHS, i.e., what is the measure under which this probability is evaluated $\\mathrm{P}(P \\not \\in \\mathcal{K})$? \n- While the related work section covers papers on DRO, it misses discussion and references to some other papers where an alternative non-traditional approach has been explored in the context of deep learning[1,2,3]. The generalization bounds presented in these papers also don't directly depend on the complexity of the underlying hypothesis class. \n- Extension to MMD DRO is discussed. While the result is interesting and in specific situations tighter than the usual uniform convergence bound. However, the significance and practical relevance of this result are not clear to me. Specifically, it would be insightful to expand on the last sentence in abstract: \"...we hope our findings can open the door for a better understanding of DRO, especially its benefits on loss minimization and other machine learning applications.\"\n- Experimental details are missing. While authors redirect the reader to a reference [9] from their paper, authors are encouraged to add more details on the experiments. \n- (Minor) Conclusion section with a discussion on limitations and future work is missing. \n- Other minor issues or issues that hinder understanding: \n  - Theorem 3.1, line 173, What is the first word \"DRO\"? if it $f_DRO = ...$\n\n[1] Jiang et al. 2021. Assessing Generalization of SGD via Disagreement https://arxiv.org/abs/2106.13799\n\n[2] Garg et al. 2021. RATT: leveraging unlabeled data to guarantee generalization https://arxiv.org/abs/2105.00303\n\n[3] Zhou et al. 2020.  On uniform convergence and low-norm interpolation learning. https://arxiv.org/abs/2006.05942", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-hP17zh9lWm", "reviewer": "Reviewer_xNyC", "summary": "The authors present a DRO framework to derive generalization bounds, where the bounds crucially depend on the chosen ambiguity set, but not on the complexity of the hypothesis class, as opposed to existing ERM-type generalization bounds. The authors then exemplify the presented genearlization bounds for the maximum mean discrepancy (MMD) ambiguity set.", "questions": "1) In Theorem 4.1, how can you practically verify the assumption \\|\\ell(f^*,.)\\|_H \\leq M? Since you don’t know f^*, I guess you require a uniform bound of the form \\sup_{f\\in H} \\ell(f,.)? How would you practically estimate M?\n2) Do you have any idea how tight the bound in Theorem 4.1 is? Do there exist lower bounds?\n3) Let us assume to be in the setting of Theorem 5.1. How do you compute f^*_DRO? Is there a tractable reformulation? Is that similar to [18]?\n\nIn general the paper is well written and easy to follow. I just have the following (minor) suggestions to improve the presentation:\n1) I don’t see the benefit of introducing the non-standard notation of P\\ell(f,.) for E_P[\\ell(f,z)]. I find this notation mathematically imprecise (since P is a probability measure and therefore cannot act on functions, unless you overload notation. Moreover, I find this notation confusing and would prefer to use the expected value notation.\n2) Please correct the following typos:\n- line 121, “bals\n- line 290, “supremum\n3) As you mention distributional shifts in transfer learning, there is a recent DRO-related work on that topic you might want to compare your work against (Sutter, Krause, Kuhn, NeurIPS 2021, Robust Generalization despite Distribution Shift via Minimum Discriminating Information)\n4) It would be nice to remind the reviewer about the definition of a Sobolev space (required to understand Theorem 5.1)", "limitations": "I see the “usual” DRO limitations also in this work, which are: (i) assumption of iid data, (ii) subjectivity of which ambiguity set to choose and (iii) need of a tractable reformulation to solve the DRO problem.\n\nThere are, however, good answers in the DRO literature to all three limitations, so I assume the presented framework in subsequent works can address these limitations.\n", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: I agree with the authors that most existing DRO works derive upper-confidence-type results where a data-driven decision f_data and a corresponding upper-confidence bound $J_{data}$ are generated with the corresponding statistical certificate $P[ E[\\ell(f_{data},z)] <= J_{data} ]>= 1-\\beta$. This work presents “true” generalization bounds quantifying the excess risk. Therefore, this approach clearly is novel and of high interested to a learning community.\n\nWeaknesses: I think in the presented framework, there could me more properties being explored. For example, can you derive explicit generalization bounds for ambiguity sets other than MMD, e.g., f-divergence balls, moment-ambiguity sets? Moreover, how would a decision maker decide which ambiguity set to choose?\n\n\nPost-Revision Comment:\nI would like to thank the authors for the careful revision and for providing convincing explanations to all my questions. I will raise my rating to 7 and recommend acceptance of this paper. ", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept