# Generalization Bounds with Minimal Dependency on Hypothesis Class via
Distributionally Robust Optimization

Yibo Zeng
Columbia University
<EMAIL_ADDRESS>
&Henry Lam
Columbia University
<EMAIL_ADDRESS>

###### 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.

##  1 Introduction

We study generalization error in the following form. Let
$\ell:\mathcal{F}\times\mathcal{Z}\rightarrow\mathbb{R}$ be a loss function
over the function class $\mathcal{F}$ and sample space
$\mathcal{Z}\subset\mathbb{R}^{d}$. Let $\mathbb{E}_{P}[\ell(f,z)]$ be the
expected loss under the true distribution $P$ for the random object $z$. This
$\mathbb{E}_{P}[\ell(f,z)]$ can be an objective function ranging from various
operations research applications to the risk of a machine learning model.
Given iid samples $\\{z_{i}\\}_{i=1}^{n}\sim P$, we solve a data-driven
optimization problem or fit model to give solution $f_{\text{data}}$. The
_excess risk_ , or optimality gap of $f_{\text{data}}$ with respect to the
oracle best solution
$f^{*}\in\arg\min_{f\in\mathcal{F}}\mathbb{E}_{P}[\ell(f,z)]$, is given by

$\mathbb{E}_{P}[\ell(f_{\text{data}},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]$ (1)

This gap measures the relative performance of a data-driven solution in future
test data, giving rise to a direct measurement on the generalization error.
Established approaches to obtain high probability bounds for (1) have
predominantly focused on empirical risk minimization (ERM)

$\hat{f}^{*}\in\arg\min_{f\in\mathcal{F}}\mathbb{E}_{\hat{P}}[\ell(f,z)]$

for empirical distribution $\hat{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 $\mathcal{F}$ or $\mathcal{L}:=\\{\ell(f,\cdot)\mid f\in\mathcal{F}\\}$
and leads to well-known measures such as the Vapnik-Chervonenkis (VC)
dimension [1]. On a high level, these complexity measures arise from the need
to uniformly control the empirical error, which in turn arises from the a
priori uncertainty on the decision variable $f$ in the optimization.

In this paper, we present an alternate route to obtain concentration bounds
for (1) on solutions obtained from distributionally robust optimization (DRO).
The latter started as a decision-making framework for optimization under
stochastic uncertainty [2, 3, 4], and has recently surged in popularity in
machine learning, thanks to its abundant connections to regularization and
variability penalty [5, 6, 7, 8, 9, 10, 11, 12] and risk-averse
interpretations [13, 14]. Instead of replacing the unknown true expectation
$\mathbb{E}_{P}[\cdot]$ by an empirical expectation
$\mathbb{E}_{\hat{P}}[\cdot]$, DRO hinges on the creation of an _uncertainty
set_ or _ambiguity set_ $\mathcal{K}$. This set lies in the space of
probability distribution $\mathcal{P}$ on $z$ and is calibrated from data. It
obtains a solution $f_{\text{dro}}^{*}$ by minimizing the worst-case expected
loss among $\mathcal{K}$

$\displaystyle
f_{\text{dro}}^{*}\in\arg\min_{f\in\mathcal{F}}\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f,z)].$
(2)

The risk-averse nature of DRO is evident from the presence of an adversary
that controls $Q$ in (2). Also, if $\mathcal{K}$ is suitably chosen so that it
contains $P$ with confidence (in some suitable sense) and shrinks to singleton
as data size grows, then one would expect $f_{\text{dro}}^{*}$ to eventually
approach the true solution, which also justifies the approach as a consistent
training method. The latter can often be achieved by choosing $\mathcal{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 (1) for DRO solutions,
i.e.,

$\mathbb{E}_{P}[\ell(f_{\text{dro}}^{*},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]$ (3)

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 $\mathcal{K}$, i.e.,
$\mathbb{P}[P\in\mathcal{K}]$ and, (ii) given that this occurs, the difference
between the robust and true objective functions evaluated at the true solution
$f^{*}$, i.e.,
$\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f^{*},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]$.
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
$\phi$-divergence as a statistical distance in DRO, our analysis implies
generalization bounds whose dependence on the hypothesis class $\mathcal{L}$
appears the minimal possible: The bound depends solely on the true loss
function $\ell(f^{*},\cdot)$, independent of any other
$\ell(f,\cdot)\in\mathcal{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 on the data-
driven algorithmic output $f_{\text{data}}$, 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 $f_{\text{data}}$ ([15, Definition 3 and Theorem 11]; [18,
Theorem 4.2]) or taking a uniform bound over $\mathcal{F}$ ([16, Definition 2
and Theorem 1]; [17, Theorem 4.2]). In contrast, our bound depends on the
hypothesis class through the deterministic $\ell(f^{*},\cdot)$, 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 a comprehensive review on 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 2 before we present our main results (Section 3 \- 5) and numerical
experiments (Section 6).

##  2 Related Work and Comparisons

DRO can be viewed as a generalization of (deterministic) robust optimization
(RO) [19, 20]. 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 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 $\mathcal{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
$\mathcal{K}$ based on data when available. The construction can be roughly
categorized into two approaches: (i) neighborhood ball using statistical
distance, which include most commonly $\phi$-divergence [27, 28, 29, 30, 31]
and Wasserstein distance [32, 33, 34, 6]; (ii) partial distributional
information including moment [35, 2, 3, 4, 36], distributional shape [37, 38,
39, 40] and marginal [41, 42, 43] constraints. The former approach has the
advantage that the ambiguity set or the attained robust objective value
consistently approaches the truth [27, 44]. The second approach, on the other
hand, provides flexibility to decision-maker when limited data is available
which proves useful on a range of operational or risk-related settings [45,
46, 47].

The first approach above, namely statistical-distance-based 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 on Expected Loss

The classical approach to obtain guarantees for data-driven DRO is to
interpret the ambiguity set $\mathcal{K}$ as a nonparametric confidence
region, namely that $\mathbb{P}[P\in\mathcal{K}]\geq 1-\delta$ for small
$\delta\in(0,1)$. In this case, the confidence guarantee on the set can be
translated into a confidence bound on the true expected loss function
evaluated at the DRO solution $f^{*}_{\text{dro}}$ in the form

$\mathbb{P}[\mathbb{E}_{P}[\ell(f^{*}_{\text{dro}},z)]\leq\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f^{*}_{\text{dro}},z)]]\geq
1-\delta$ (4)

via a direct use of the worst-case definition of
$\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\cdot]$. This implication is very
general, with $\mathcal{K}$ taking possibly any geometry (e.g., [2, 27, 44,
32]). A main concern on results in the form (4) is that the bound could be
loose (i.e., a large
$\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f^{*}_{\text{dro}},z)]$). This, in
some sense, is unsurprising as the analysis only requires a confidence
guarantee on the set $\mathcal{K}$, with no usage of other more specific
properties, which is also the reason why the bound (4) is general. When
$\mathcal{K}$ is suitably chosen, a series of work has shown that the bound
(4) can achieve tightness in some well-defined sense. [48, 49] show that when
$\mathcal{K}$ is a Kullback-Leibler divergence ball,
$\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f^{*}_{\text{dro}},z)]$ in (4) is
the minimal among all possible data-driven formulations that satisfy a given
exponential decay rate on the confidence. [8, 50, 51] show that for
divergence-based $\mathcal{K}$,
$\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f,z)]$ matches the confidence bound
obtained from the standard central limit theorem by deducing that it is
approximately $\mathbb{E}_{\hat{P}}[\ell(f,z)]$ 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 (1). We caution that (4) is
a result on the validity of the estimated objective value
$\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f_{\text{dro}}^{*},z)]$ in bounding
the true objective value $\mathbb{E}_{P}[\ell(f_{\text{dro}}^{*},z)]$. The
excess risk (1), on the other hand, measures the generalization performance of
a solution in comparison with the oracle best. The latter is arguably more
intricate as it involves the unknown true optimal solution $f^{*}$ and, as we
will see, (4) provides an intermediate building block in our analysis of (1).

###  2.2 Variability Regularization

In a series of work [30, 31, 7, 9, 51], it is shown that DRO using divergence-
based ball, i.e., $\mathcal{K}=\\{Q\in\mathcal{P}:D(Q,\hat{P})\leq\eta\\}$ for
some threshold $\eta>0$ and $D$ a $\phi$-divergence (e.g., Kullback-Leibler,
$\chi^{2}$-distance), satisfies a Taylor-type expansion

$\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f,z)]=\mathbb{E}_{\hat{P}}[\ell(f,z)]+C_{1}(f)\sqrt{\eta}+C_{2}(f)\eta+\cdots$
(5)

where $C_{1}(f)$ is the standard deviation of the loss function,
$\sqrt{\text{Var}[\ell(f,z)]}$, multiplied by a constant that depends on
$\phi$. Similarly, if $D$ is the Wasserstein distance and $\eta$ is of order
$1/n$, (5) holds with $C_{1}(f)$ being the gradient norm or the Lipschitz norm
[12, 10, 5, 52]. Furthermore, [17], which is perhaps closest to our work,
studies MMD as the DRO statistical distance and derives a high-probability
bound for $\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f,z)]$ similar to the RHS
of (5), with $C_{1}(f)$ being the reproducing kernel Hilbert space (RKHS) norm
of $\ell(f,\cdot)$. Results of the form (5) can be used to show that
$\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f,z)]$, upon choosing $\eta$
properly (of order $1/n$), gives a confidence bound on
$\mathbb{E}_{P}[\ell(f,z)]$ [8, 51]. Moreover, this result can be viewed as a
duality of the empirical likelihood theory [53, 12, 51, 54].

In connecting (5) to the solution performance, there are three implications.
First, the robust objective function
$\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f,z)]$ can be interpreted as
approximately a mean-variance optimization, and [7, 55] prove that, thanks to
this approximation, the DRO solution can lower the variance of the attained
loss which compensates for its under-performance in the expected loss, thus
overall leading to a desirable risk profile. [7, 55] have taken a 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
$\mathbb{E}_{P}[\ell(f,z)]$, is the sole consideration, the approximation (5)
is used in two ways. One way is to obtain bounds in the form

$\mathbb{E}_{P}[\ell(f^{*}_{\text{dro}},z)]\leq\min_{f\in\mathcal{F}}\\{\mathbb{E}_{P}[\ell(f,z)]+C_{1}(f)/\sqrt{n}\\}+O(1/n)$
(6)

thus showing that DRO performs optimally, up to $O(1/n)$ error, on the
variance-regularized objective function [9]. From this, [9] deduces that under
special situations where there exists $f$ with both small risk
$\mathbb{E}_{P}[\ell(f,z)]$ and variance $\text{Var}[\ell(f,z)]$, (6) can be
translated into a small excess risk bound of order $1/n$. Moreover, such an
order also desirably appears for DRO in some non-smooth problems where ERM
could bear $1/\sqrt{n}$. The second way is to use DRO as a mathematical route
to obtain uniform bounds in the form

$\mathbb{E}_{P}[\ell(f,z)]\leq\mathbb{E}_{\hat{P}}[\ell(f,z)]+C_{1}(f)/\sqrt{n}+O(1/n),\
\forall f\in\mathcal{F},$ (7)

which is useful for proving the generalization of ERM. In particular, we can
translate (7) into a high probability bound for
$\mathbb{E}_{P}[\ell(\hat{f}^{*},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]$ of order
$1/\sqrt{n}$. This use is studied in, e.g., [56] in the case of Wasserstein
and [17] in the case of MMD.

Despite these rich results, both (6) and (7), and their derived bounds on the
excess risk (1), still depend on other candidates in the hypothesis class
through the choice of the ball size $\eta$ or the coefficient $C_{1}(f)$. Our
main message in this paper is that this dependence can be 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 on other
candidates still exists and cannot be removed.

###  2.3 Risk Aversion

It is known that any coherent risk measure (e.g., conditional value-at-risk)
[13, 14] of a random variable (in our case $\ell(f,z)$) is equivalent to the
robust objective value $\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f,z)]$ with
a particular $\mathcal{K}$. Thus, DRO is equivalent to a risk measure
minimization, which in turn explains its benefit in controlling tail
performances. In machine learning, this rationale has been adopted to enhance
performance on minority subpopulations and in safety or fairness-critical
systems [58]. 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 [59, 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 a degradation to the
average-case performance [63, 60, 64] (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 a
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 $\mathcal{Z}\subset\mathbb{R}^{d}$ be a sample space, $P$ be a
distribution on $\mathcal{Z}$, $\\{z_{i}\\}_{i=1}^{n}$ be iid samples from
$P$, and $\mathcal{F}$ be the function class. For loss function
$\ell:\mathcal{F}\times\mathcal{Z}\rightarrow\mathbb{R}$, DRO solution
$f^{*}_{\text{dro}}\in\arg\min_{f\in\mathcal{F}}\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f,z)]$
satisfies that for any $\varepsilon>0$,

$\mathbb{P}[\mathbb{E}_{P}\ell(f^{*}_{\text{dro}},z)-\mathbb{E}_{P}\ell(f^{*},z)>\varepsilon]\leq\mathbb{P}[P\notin\mathcal{K}]+\mathbb{P}[\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*},z)-\mathbb{E}_{P}\ell(f^{*},z)>\varepsilon|P\in\mathcal{K}].$
(8)

###### Proof of Theorem 3.1..

We first rewrite
$\mathbb{E}_{P}[\ell(f^{*}_{\text{dro}},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]$ as
the following three terms:
$[\mathbb{E}_{P}[\ell(f^{*}_{\text{dro}},z)]-\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f^{*}_{\text{dro}},z)]]+[\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f^{*}_{\text{dro}},z)]-\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f^{*},z)]]+[\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f^{*},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]].$
Note that the second term
$\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*}_{\text{dro}},z)-\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*},z)\leq
0$ almost surely by the DRO optimality of $f^{*}_{\text{dro}}$. Also, by
definition of $\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\cdot]$ as the worst-case
objective function, we have
$\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f,z)]\geq\mathbb{E}_{P}[\ell(f,z)]$
for all $f\in\mathcal{F}$ as long as $P\in\mathcal{K}$. Thus,

$\displaystyle\mathbb{P}[\mathbb{E}_{P}\ell(f^{*}_{\text{dro}},z)-\mathbb{E}_{P}\ell(f^{*},z)>\varepsilon]\leq$
$\displaystyle~{}\mathbb{P}[P\notin\mathcal{K}]+\mathbb{P}[\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*},z)-\mathbb{E}_{P}\ell(f^{*},z)>\varepsilon,P\in\mathcal{K}]$
$\displaystyle\leq$
$\displaystyle~{}\mathbb{P}[P\notin\mathcal{K}]+\mathbb{P}[\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*},z)-\mathbb{E}_{P}\ell(f^{*},z)>\varepsilon|P\in\mathcal{K}].$

This completes our proof. ∎

A key feature of the bound in Theorem 3.1 is that it requires only the true
loss function $\ell(f^{*},\cdot)$. 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
$\mathbb{E}_{P}[\ell(f^{*}_{\text{dro}},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]$
into three parts where the second term is trivially $\leq 0$ and the third
term depends only on the true loss. The key is that the first term satisfies
$\mathbb{E}_{P}[\ell(f^{*}_{\text{dro}},z)]-\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f^{*}_{\text{dro}},z)]\leq
0$ as long as $P\in\mathcal{K}$, thanks to the worst-case definition of the
robust objective function
$\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(\cdot,z)]$. In contrast, in the ERM
case for instance, the same line of analysis gives
$[\mathbb{E}_{P}[\ell(\hat{f}^{*},z)]-\mathbb{E}_{\hat{P}}[\ell(\hat{f}^{*},z)]]+[\mathbb{E}_{\hat{P}}[\ell(\hat{f}^{*},z)]-\mathbb{E}_{\hat{P}}[\ell(f^{*},z)]]+[\mathbb{E}_{\hat{P}}[\ell(f^{*},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]]$,
and while the second and third terms are handled analogously, the first term
depends on $\hat{f}^{*}$ that varies randomly among the hypothesis class and
is typically handled by the uniform bound
$\sup_{f\in\mathcal{F}}|\mathbb{E}_{P}[\ell(f,z)]-\mathbb{E}_{\hat{P}}[\ell(f,z)]|$
that requires empirical process analysis [66] and the complexity of the
hypothesis class $\mathcal{F}$ or $\mathcal{L}$. Thus, in a sense, the worst-
case nature of DRO “transfers” the uniformity requirement over the hypothesis
class into alternate geometric 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 a
concrete DRO formulation. In the following, we use ambiguity set $\mathcal{K}$
as a neighborhood ball of the empirical distribution measured by statistical
distance, namely

$\mathcal{K}=\\{Q\in\mathcal{P}:D_{\text{MMD}}(Q,\hat{P})\leq\eta\\}$ (9)

for a threshold $\eta>0$. Moreover, we specialize in max mean discrepancy
(MMD) [67] as the choice of distance $D_{\text{MMD}}(\cdot,\cdot)$. MMD is a
distance derived from the RKHS norm, by using test functions constrained by
this norm in an Integral Probability Metric (IPM) [68]. Specifically, let
$k:\mathcal{Z}\times\mathcal{Z}\rightarrow\mathbb{R}$ be a positive definite
kernel function on $\mathcal{Z}$ and $(\mathcal{H},\langle\cdot,\cdot\rangle)$
be the corresponding RKHS. For any distributions $Q_{1}$ and $Q_{2}$, the MMD
distance is defined by the maximum difference of the integrals over the unit
ball $\\{h\in\mathcal{H}:\|h\|_{\mathcal{H}}\leq 1\\}$. That is,
$D_{\text{MMD}}(Q_{1},Q_{2}):=\sup_{h\in\mathcal{H}:\|h\|_{\mathcal{H}}\leq
1}\int h\mathrm{d}Q_{1}-\int h\mathrm{d}Q_{2}.$ In this way, MMD-DRO can be
formulated as

$\min_{f\in\mathcal{F}}\max_{Q:D_{\text{MMD}}(Q,\hat{P})\leq\eta}\mathbb{E}_{Q}[\ell(f,z)]$
(10)

MMD is known to be less prone to the curse of dimensionality [69, 70, 71], a
property that we leverage in this paper, and such a property has allowed
successful applications in statistical inference [67], generative models [72,
73], reinforcement learning [74], and DRO [17, 75]. In particular, [76]
studies the duality and optimization procedure for MMD DRO. For a recent
comprehensive review of MMD, we refer readers to [77].

In the sequel, we adopt bounded kernels, i.e.,
$\sup_{z,z^{\prime}\in\mathcal{Z}}\sqrt{k(z,z^{\prime})}<+\infty$, to conduct
our analysis. This assumption applies to many popular choices of kernel
functions and more importantly, guarantees the so-called kernel mean embedding
(KME) [77] is well-defined in RKHS. That is, $\mu_{Q}:=\int
k(z,\cdot)\mathrm{d}Q\in\mathcal{H},~{}\forall~{}Q\in\mathcal{P}.$ This well-
definedness of KME gives two important implications. One is that MMD is
equivalent to the norm distance in KME:
$D_{\text{MMD}}(P,Q)=\|\mu_{P}-\mu_{Q}\|_{\mathcal{H}}$ [78, 67]. Second, it
bridges the expectation and the inner product in the RKHS space [70]:
$\forall~{}f\in\mathcal{H}$, $\mathbb{E}_{x\sim P}[f(x)]=\int_{x}\langle
f,k(x,\cdot)\rangle\mathrm{d}P(x)=\langle f,\mu_{P}\rangle.$ Both properties
above will facilitate our analysis. We refer the reader to Appendix A for
further details on KME.

######  Theorem 4.1 (Generalization Bounds for MMD DRO).

Adopt the notation and assumptions in Theorem 3.1. Let $\mathcal{Z}$ be a
compact subspace of $\mathbb{R}^{d}$,
$k:\mathcal{Z}\times\mathcal{Z}\rightarrow\mathbb{R}$ be a bounded continuous
positive definite kernel, and
$(\mathcal{H},\langle\cdot,\cdot\rangle_{\mathcal{H}})$ be the corresponding
RKHS. Suppose also that (i) $\sup_{z\in\mathcal{Z}}\sqrt{k(z,z)}\leq K$; (ii)
$\ell(f^{*},\cdot)\in\mathcal{H}$ with
$\|\ell(f^{*},\cdot)\|_{\mathcal{H}}\leq M$. Then, for all $\delta\geq 0$, if
we choose ball size $\eta=\frac{K}{\sqrt{n}}(1+\sqrt{2\log(1/\delta)})$ for
MMD DRO (10), then MMD DRO solution $f^{*}_{\text{M-dro}}$ satisfies

$\mathbb{E}_{P}[\ell(f^{*}_{\text{M-dro}},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]\leq\frac{2KM}{\sqrt{n}}(1+\sqrt{2\log(1/\delta)})$

with probability at least $1-\delta$.

We briefly overview our proof of Theorem 4.1, leaving the details to Appendix
B. In view of Theorem 3.1, the key lies in choosing the ball size $\eta$ to
make a good trade-off between $\mathbb{P}[D_{\text{MMD}}(P,\hat{P})\geq\eta]$
and an upper bound of
$\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f^{*},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]$
when $D_{\text{MMD}}(P,\hat{P})\leq\eta$. The former can be characterized by
the established concentration rate of KME (See Proposition B.1). To get the
latter bound, we use the properties of KME to translate expectations into
inner products:

$\displaystyle~{}\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f^{*},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]=\max_{Q\in\mathcal{K}}\langle\ell(f^{*},\cdot),\mu_{Q}-\mu_{P}\rangle\leq\max_{Q\in\mathcal{K}}\|\ell(f^{*},\cdot)\|_{\mathcal{H}}D_{\text{MMD}}(Q,P)$
$\displaystyle\leq$
$\displaystyle~{}\|\ell(f^{*},\cdot)\|_{\mathcal{H}}\max_{Q\in\mathcal{K}}\\{D_{\text{MMD}}(Q,\hat{P})+D_{\text{MMD}}(\hat{P},P)\\}\leq\|\ell(f^{*},\cdot)\|_{\mathcal{H}}\cdot
2\eta.$ (11)

From these, we can choose $\eta$ as indicated in Theorem 4.1 to conclude the
result. In a nutshell, here we harness the compatibility between $\mathcal{K}$
and the true loss function $\ell(f^{*},\cdot)$, more specifically the RKHS
norm on $\ell(f^{*},\cdot)$, and the dimension-free concentration of KME. Our
general bound in Theorem 3.1 allows us to stitch these two ingredients
together to obtain generalization bounds for MMD DRO.

Figure 1: Let $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ be two hypothesis
classes with the same true loss function $\ell(f^{*},\cdot)$.
$\mathcal{L}_{1}$ corresponds to functions in the oval and $\mathcal{L}_{2}$
corresponds to functions below the straight line. In ERM, the uniform bound is
taken directly over $\mathcal{L}_{1}$ (blue area) or $\mathcal{L}_{2}$ (pink
area), while DRO gives the same bound that corresponds to uniformity over
$\mathcal{H}_{\|\ell(f^{*},\cdot)\|_{\mathcal{H}}}$ (orange area).

###  4.2 Strengths and Limitations Compared with ERM

Our generalization bound in Theorem 4.1 in fact still utilizes a uniformity
argument, hidden in the distance construction. Note that our bound comprises
essentially the product of $\|\ell(f^{*},\cdot)\|_{\mathcal{H}}$, which
depends on the true loss function, and $\eta$, the size of the ambiguity set.
The latter is controlled by $D_{\text{MMD}}(P,\hat{P})$, which is equivalent
to the supremum of the empirical process indexed by $\mathcal{H}_{1}:=\\{h\mid
h\in\mathcal{H},\|h\|_{\mathcal{H}}\leq 1\\}$. Note that this supremum is
expressed through $\sup_{z\in\mathcal{Z}}\sqrt{k(z,z)}$, which is independent
of the hypothesis class.

To understand this further, Figure 1 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 hypothesis class. In
ERM, the uniform bound is taken directly over the hypothesis class, say
$\mathcal{L}$. In DRO, from our discussion above, the uniform bound is taken
over a dilation of the $\mathcal{H}_{1}$-ball by a factor
$\|\ell(f^{*},\cdot)\|_{\mathcal{H}}$, equivalently
$\mathcal{H}_{\|\ell(f^{*},\cdot)\|_{\mathcal{H}}}:=\\{h\mid
h\in\mathcal{H},\|h\|_{\mathcal{H}}\leq\|\ell(f^{*},\cdot)\|_{\mathcal{H}}\\}$.
Thus, if two hypothesis classes contain the same true loss function
$\ell(f^{*},\cdot)$, 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 $\|\ell(f^{*},\cdot)\|_{\mathcal{H}}$ is small
compared to the size of $\mathcal{L}$. _ Though one may argue that
$\ell(f^{*},\cdot)$ is typically unknown and hence we ultimately resort to
using uniformity over $\mathcal{L}$ to obtain any computable bound, our bound
in terms of $\ell(f^{*},\cdot)$ explains why DRO can sometimes substantially
outperform ERM. In Section 6, we provide an example where
$\|l(f^{*},\cdot)\|_{\mathcal{H}}=0$ and the excess risk of DRO achieves zero
with high probability. (ii) _When uniformly bounding over $\mathcal{H}_{1}$ is
“cheap”._ Many commonly used kernel spaces are bounded and therefore uniform
bounds over $\mathcal{H}_{1}$ are trivial to establish (by Proposition B.1),
which in turn leads to generalization bounds that depend only on a dilation
(by $\|\ell(f^{*},\cdot)\|_{\mathcal{H}}$) of these uniform bounds over
$\mathcal{H}_{1}$. This is regardless of how complex the hypothesis class
$\mathcal{L}$ is, including when $\|\mathcal{L}\|_{\mathcal{H}}=\infty$ or
$\mathcal{L}=\mathcal{H}$. ERM, in contrast, uses uniformity over
$\mathcal{L}$ and can result in an exploding generalization bound when
$\|\mathcal{L}\|_{\mathcal{H}}=\infty$. (iii) _When $\mathcal{L}$ resembles
the geometry of $\mathcal{H}$._ For instance, when
$\mathcal{L}=\mathcal{H}_{B}:=\\{h\mid h\in\mathcal{H},\|h\|_{\mathcal{H}}\leq
B\\}$, the ERM bound yields $2B\sup_{h\in\mathcal{H}_{1}}\\{Ph-\hat{P}h\\}$
since $B=\sup_{\ell\in\mathcal{L}}\|\ell(\cdot)\|_{\mathcal{H}}$, while the
DRO bound gives
$2\|\ell(f^{*},\cdot)\|_{\mathcal{H}}\sup_{h\in\mathcal{H}_{1}}\\{Ph-\hat{P}h\\}$
that depends only on the true loss function and is smaller.

Despite the strengths, our bound in Theorem 4.1 also reveals situations where
DRO could underperform ERM: When $\mathcal{L}$ has a shape deviating from the
RKHS ball such that
$\mathcal{L}\subset\mathcal{H}_{\|\ell(f^{*},\cdot)\|_{\mathcal{H}}}$, then
taking uniform bounds over $\mathcal{H}_{\|\ell(f^{*},\cdot)\|_{\mathcal{H}}}$
is costly compared to over $\mathcal{L}$, in which case DRO generalization
bound is worse than ERM. Moreover, note that $\ell(f^{*},\cdot)$, the optimal
loss within $\mathcal{L}$, can shift when $\mathcal{L}$ becomes richer. In
this sense Theorem 4.1 cannot completely remove the dependency on the
hypothesis class, but rather diminishes it to the minimum possible: The
resulting bound does not rely on any other candidates in the hypothesis class
except $\ell(f^{*},\cdot)$.

######  Remark 4.2.

There exists another line of work that establishes generalization bounds with
a faster rate $O(n^{-1})$ for ERM [79, 57, 80, 81] and $\phi$-divergence DRO
[9]. However, they are all based on additional curvature conditions on
$\mathcal{F}$ or $\mathcal{L}$ to relate the loss/risk and variance. Improving
our bounds towards $O(n^{-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 a 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
$\mathbb{E}_{P}[\ell(f,z)]-\mathbb{E}_{\hat{P}}[\ell(f,z)],~{}\forall
f\in\mathcal{F}$. More specifically, the main argument for their Theorem 4.2
is that, with high probability, one has
$\mathbb{E}_{P}[\ell(f,z)]-\mathbb{E}_{\hat{P}}[\ell(f,z)]=O(\|\ell(f,\cdot)\|_{\mathcal{H}}\sqrt{\frac{\log(1/\delta)}{n}})$
for any given $f$. Although this bound seems to depend on a single loss
function $\ell(f,\cdot)$, any algorithmic output, say $f_{\text{data}}$, needs
to be learnt from data and is thus random. This means that to construct a
generalization bound, one has to either average over $f_{\text{data}}$ or take
a supremem over $f\in\mathcal{F}$. [17] adopts the latter approach and
establishes a bound
$\mathbb{E}_{P}[\ell(f,z)]-\mathbb{E}_{\hat{P}}[\ell(f,z)]=O(\sup_{f\in\mathcal{F}}\|\ell(f,\cdot)\|_{\mathcal{H}}\sqrt{\frac{\log(1/\delta)}{n}}),~{}\forall~{}f\in\mathcal{F}$
in their Theorem 4.2. Our Theorem 4.1, in contrast, only depends on
$\|\ell(f^{*},\cdot)\|_{\mathcal{H}}$ 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 $f^{*}_{\text{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\in\mathcal{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_{f\in\mathcal{F}}\ell(f,z)+\eta\|f\|_{\mathcal{H}}.$ (12)

When we additionally assume $\mathcal{L}\subset\mathcal{H}$, it is known that
MMD DRO is equivalent to

$\min_{f\in\mathcal{F}}\ell(f,z)+\eta\|\ell(f,\cdot)\|_{\mathcal{H}}$ (13)

according to [17, Theorem 3.1]. Although (12) and (13) appear similar, their
rationales are different. When regularizing $\|f\|_{\mathcal{H}}$, the goal is
to 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 [17] to consider regularizing
$\ell(f,\cdot)$ instead of $f$ itself. Our Theorem 4.1 reveals the benefit of
regularizing $\ell(f,\cdot)$ at a new level: Regularizing
$\|\ell(f,\cdot)\|_{\mathcal{H}}$ increases the likelihood of
$\mathbb{E}_{P}[\ell(f^{*}_{\text{M-dro}},z)]-\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f^{*}_{\text{M-dro}},z)]\leq
0$, 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 $\ell(f^{*},\cdot)$
for RKHS-regularized ERM when the regularization is on $\ell(f,\cdot)$.
Furthermore, thanks to this we can relax the assumption
$\mathcal{L}\subset\mathcal{H}$ adopted in (13) to merely
$\ell(f^{*},\cdot)\in\mathcal{H}$ which is 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 to $\ell(f^{*},\cdot)\notin\mathcal{H}$

In Theorem 4.1, we assume (i) $\sup_{x\in\mathcal{X}}\sqrt{k(x,x)}\leq K$;
(ii) $\ell(f^{*},\cdot)\in\mathcal{H}$ with
$\|\ell(f^{*},\cdot)\|_{\mathcal{H}}\leq M$. Although (i) is natural for many
kernels, (ii) can be restrictive since many popular loss functions do not
satisfy $\ell(f^{*},\cdot)\in\mathcal{H}$. For instance, if $k$ is a Gaussian
kernel defined on $\mathcal{Z}\subset\mathbb{R}^{d}$ that has nonempty
interior, then any nonzero polynomial on $\mathcal{Z}$ does not belong to the
induced RKHS $\mathcal{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\in\mathcal{H}$ for
simplicity, e.g., [84, 85, 17]. This theory-practice gap motivates us to
extend our result to $\ell(f^{*},\cdot)\notin\mathcal{H}$.

To this end, note that under universal kernels [86], any bounded continuous
function can be approximated arbitrarily well (in $L^{\infty}$ norm) by
functions in $\mathcal{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, 83]. This therefore
requires analyzing a trade-off between the function approximation error and
RKHS norm magnitude. More specifically, we define the approximation rate
$I(\ell(f^{*},\cdot),R):=\inf_{\|g\|_{\mathcal{H}}\leq
R}\|\ell(f^{*},\cdot)-g\|_{\infty}$, and
$g_{R}:=\arg\inf_{\|g\|_{\mathcal{H}}\leq
R}\|\ell(f^{*},\cdot)-g\|_{\infty}$.111$g_{R}$ is well-defined since for fixed
$R$, $h(g)=\|\ell(f^{*},\cdot)-g\|_{\infty}$ is a continuous function over a
compact set $\\{g:g\in\mathcal{H},\|g\|_{\mathcal{H}}\leq R\\}.$ As a concrete
example, we adopt the Gaussian kernel and the Sobolev space to quantify such a
rate and establish Theorem 4.3 below.

######  Theorem 4.3 (Generalization Bounds for Sobolev Loss Functions).

Let $(\mathcal{H},\|\cdot\|_{\mathcal{H}})$ be the RKHS induced by
$k(z,z^{\prime})=\exp(-\|z-z^{\prime}\|^{2}_{2}/\sigma^{2})$ on
$\mathcal{Z}=[0,1]^{d}$. Suppose that $\ell(f^{*},\cdot)$ is in the Sobolev
space $H^{d}(\mathbb{R}^{d})$. Then, there exists a constant $C$ independent
of $R$ but dependent on $\ell(f^{*},\cdot)$, $d$, and $\sigma$ such that for
all $\delta\geq 0$, if we choose ball size
$\eta=\frac{1}{\sqrt{n}}(1+\sqrt{2\log(1/\delta)})$ for MMD DRO (10), then MMD
DRO solution $f^{*}_{\text{M-dro}}$ satisfies

$\mathbb{E}_{P}[\ell(f^{*}_{\text{M-dro}},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]\leq\\\
2\inf_{R\geq 1}\Big{\\{}C(\log
R)^{-\frac{d}{16}}+\frac{R}{\sqrt{n}}(1+\sqrt{2\log(1/\delta)})\Big{\\}}$ (14)

with probability at least $1-\delta$.

We briefly outline our proof, leaving the details to Appendix C. When
$\ell(f^{*},\cdot)\notin\mathcal{H}$, we cannot use KME to rewrite expectation
as inner products as shown in (11). Rather, we will approximate
$\ell(f^{*},\cdot)$ by some $g_{R}\in\mathcal{H}$ and obtain
$\mathbb{E}_{P}[\ell(f^{*},z)]\leq\mathbb{E}_{P}[g_{R}(z)]+I(\ell(f^{*},\cdot),R).$
Since $g_{R}\in\mathcal{H}$, similar to (11) we can derive a generalization
bound of $g_{R}$, which appears in the second term of (14). Then, it suffices
to take infinum over $R\geq 1$ to establish the aforementioned trade-off
between the approximation error $I(\ell(f^{*},\cdot),R)$ (the first term of
(14)) and the RKHS norm $\|g_{R}\|_{\mathcal{H}}\leq R$ (the second term of
(14)).

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.e.,
$\ell(f^{*},\cdot)\notin\mathcal{H}$. Concretely, in the setting of Theorem
4.3, $I(\ell(f^{*},\cdot),R)\leq C(\log R)^{-d/16}$ [87] and this results in a
worse convergence rate in $n$. For example, inserting $R=\sqrt{n}(\log
n)^{-d/16}$ into (14) yields
$\mathcal{O}(\max\\{C,\sqrt{\log(1/\delta)}\\}(\log n)^{-16/d}).$ This
convergence rate is rather slow. However, it mainly results from the slow
approximation rate $I(\ell(f^{*},\cdot),R)$ established by non-parametric
analysis. If we further utilize the structure of $\ell(f^{*},\cdot)$, then a
faster convergence rate or even close to $O(n^{-1/2})$ rate can be potentially
achieved. Nonetheless, our main message in Theorem 4.3 is that even if
$\ell(f^{*},\cdot)\notin\mathcal{H}$, our bound (14) still depends minimally
on the hypothesis class $\mathcal{L}$: The bound depends solely on the true
loss function $\ell(f^{*},\cdot)$, independent of any other
$\ell(f,\cdot)\in\mathcal{L}$.

##  5 Specialization to 1-Wasserstein and $\chi^{2}$-divergence DRO

Our framework can also be specialized to DROs using other statistical
distances. Below, we derive results for DROs based on the 1-Wasserstein
distance and $\chi^{2}$-divergence, and discuss their implications and
comparisons with MMD DRO. Due to page limit, we delegate more detailed
discussions to Appendix D. Let $f^{*}_{\text{W-dro}}$ be the solution to
1-Wasserstein DRO (See Appendix D.1) and $f^{*}_{\text{$\chi^{2}$-dro}}$ be
the solution to $\chi^{2}$-divergence DRO (See Appendix D.2). Also denote
$\|\cdot\|_{\text{Lip}}$ as 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:=\mathbb{E}_{P}[\exp\left(\|z\|^{a}\right)]<\infty.$ Then,
there exists constants $c_{1}$ and $c_{2}$ that only depends on $a,A,$ and $d$
such that for any given $0<\delta<1$, if we choose ball size
$\eta=\big{(}\frac{\log(c_{1}/\delta)}{c_{2}n}\big{)}^{1/\max\\{d,2\\}}$ and
$n\geq\frac{\log(c_{1}/\delta)}{c_{2}}$, then $f^{*}_{\text{W-dro}}$ satisfies
$\mathbb{E}_{P}[\ell(f^{*}_{\text{W-dro}},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]\leq
2\|\ell(f^{*},\cdot)\|_{\text{Lip}}(\frac{\log(c_{1}/\delta)}{c_{2}n})^{1/\max\\{d,2\\}}$
with probability at least $1-\delta$.

######  Theorem 5.2 (Generalization Bounds for $\chi^{2}$-divergence DRO on
Discrete Distributions).

Suppose that $P$ is a discrete distribution with $m$ support with
$\mathbb{P}[z=z_{i}]=p_{i}$. Suppose that (i) $p_{\min}=\min_{1\leq i\leq
m}p_{i}>0$; (ii) $\|\ell(f^{*},\cdot)\|_{\infty}<+\infty$. Then, for all
$0<\delta<1$, if we choose ball size
$\eta=\frac{1}{n}(m+2\log(4/\delta)+2\sqrt{m\log(4/\delta)})$ for
$\chi^{2}$-divergence DRO, then for all
$n\geq\frac{10^{6}m^{2}}{p^{3}_{\min}\delta^{2}}$,
$f^{*}_{\chi^{2}\text{-dro}}$ satisfies
$\mathbb{E}_{P}[\ell(f^{*}_{\chi^{2}\text{-dro}},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]\leq\|\ell(f^{*},\cdot)\|_{\infty}\\{\frac{1}{\sqrt{n}}\sqrt{m+2\log(4/\delta)+2\sqrt{m\log(4/\delta)}}+\sqrt{\frac{2\log(2/\delta)}{n}}\\}$
with probability at least $1-\delta$.

Like Theorem 4.1, Theorems 5.1 and 5.2 are obtained by analyzing the two
components in Theorem 3.1, which correspond to: (1) the ambiguity set contains
true distribution $P$ with high confidence and (2) compatibility of the
statistical distance with $\ell(f^{*},\cdot)$. The bounds in Theorems 5.1 and
5.2 involve only $\ell(f^{*},\cdot)$ but not other candidates in the
hypothesis class. Notice that if $P$ is continuous, then using
$\chi^{2}$-divergence, and more generally $\phi$-divergence (See Definition
D.3), for DRO entails a bit more intricacies than MMD and Wasserstein DRO. Due
to the absolute continuity requirement in the definition, if $P$ is
continuous, then $\phi$-divergence ball centered at $\hat{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 $\phi$-divergence DRO depend on the hypothesis class, we present an
explicit bound for discrete $P$ and $\chi^{2}$-divergence, for which we can
use $\hat{P}$-centered ambiguity set. To remedy for continuous $P$, one can
set the ball center using kernel density estimate or a parametric
distribution, albeit with the price of additional approximation errors coming
from the “smoothing” of the empirical distribution. In Appendix D.2, we
present a general bound (Theorem D.4) for $\phi$-divergence DRO that leaves
open the choice of the ball center and the function $\phi$. Once again, this
generalization bound involves only $\ell(f^{*},\cdot)$ 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, to separate
future work.

(a) Performance of ERM and DRO under varying $n$ (b) Performance of ERM and
DRO under varying $\eta$

Figure 2: Excess risks of ERM and DRO

Moreover, in our result for Wasserstein DRO, the rates in terms of $n$ is
$n^{-1/\max\\{d,2\\}}$, 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 (8). Specifically, the ball size is controlled by
the 1-Wasserstein distance $D_{W_{1}}(P,\hat{P})$, which is equivalent to the
supremum of the empirical process indexed by
$\text{Lip}_{1}:=\\{h\mid\|h\|_{\text{Lip}}\leq 1\\}$ by the dual
representation of $D_{W_{1}}(\cdot,\cdot)$ [88]. Similar to our discussion in
Section 4.2, Theorem 5.1 shows a tradeoff between the hypothesis class
dependence and the rate in $n$ that differs from ERM. More precisely,
Wasserstein DRO has a generalization that favorably relies only on the true
loss $\ell(f^{*},\cdot)$, but scales inferiorly in terms of $n$ (due to
uniformity over $\text{Lip}_{1}$). It 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, $\chi^{2}$-divergence DRO retains a
rate of $1/\sqrt{n}$. 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 $\hat{P}$), we expect the
rate of $\chi^{2}$-divergence DRO to deteriorate much like the case of
Wasserstein DRO and there may exist a similar tradeoff.

##  6 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 [9, Section 5.2] and consider a
quadratic loss with linear perturbation:
$l(\theta,z)=\frac{1}{2}\|\theta-v\|_{2}^{2}+z^{\top}(\theta-v),$ where
$z\sim\operatorname{Unif}[-B,B]^{d}$ with constant $B$ varying from
$\\{1,10,100\\}$ in the experiment. Here,
$\mathcal{F}=\\{\theta\mid\theta\in\Theta\\}$ and we use $f$ and $\theta$
interchangeably. $v$ is chosen uniformly from $[1/2,1]^{d}$ and is known to
the learner in advance. In applying MMD DRO, we use Gaussian kernel
$k(z,z^{\prime})=\exp(-\|z-z^{\prime}\|_{2}^{2}/\sigma^{2})$ with $\sigma$ set
to the median of $\\{\|z_{i}-z_{j}\|_{2}\mid\forall~{}i,j\\}$ according to the
well-known median heuristic [67]. 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 M1 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.,
$\mathbb{E}_{P}[\ell(f_{\text{data}},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]$, where
$f_{\text{data}}$ denotes the ERM or DRO solution. We set $d=5$ and tune the
ball size via the best among
$\eta\in\\{0.01,0.05,0.1,0.15,0.2,0.3,\ldots,1.0\\}$ (more details to be
discussed on Figure 2(b) momentarily). Figure 2(a) shows that, as $n$
increases, both DRO and ERM incur a decreasing loss. More importantly, DRO
appears to perform much better than ERM. For $n=200$ and $B=100$ for instance,
the expected loss of DRO is less than $10^{-20}$, yet that of ERM remains at
around $10^{1}$.

We attribute the outperformance of DRO to its dependency on the hypothesis
class only through the true loss function $\ell(f^{*},\cdot)$. This can be
supported by an illustration on the effect of ball size $\eta$. In Figure
2(b), we present excess risk
$\mathbb{E}_{P}[\ell(f_{\text{data}},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]$ for
$B=1,d=5,n=50$, and varying $\eta$. We see that the excess risk of the DRO
solution drops sharply when $\eta$ is small, and then for sufficiently big
$\eta$, i.e., $\eta\in[0.5,1]$, it remains at a fixed level of $10^{-19}$,
which is close to the machine accuracy of zero (such an “L”-shape 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^{*}=v$ and the optimal loss function satisfies
$\|\ell(f^{*},\cdot)\|_{\mathcal{H}}=\|0\|_{\mathcal{H}}=0$, so that our
assumptions in Theorem 4.1 are satisfied. Recall that by Theorem 3.1,

$\mathbb{P}[\mathbb{E}_{P}\ell(f^{*}_{\text{M-dro}},z)-\mathbb{E}_{P}\ell(f^{*},z)>\varepsilon]\leq\mathbb{P}[P\notin\mathcal{K}]+\mathbb{P}[\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*},z)-\mathbb{E}_{P}\ell(f^{*},z)>\varepsilon|P\in\mathcal{K}].$

Conditioning on $P\in\mathcal{K}$, we have $f^{*}_{\text{M-dro}}=f^{*}=v$ and
$\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f^{*}_{\text{M-dro}},z)]=\mathbb{E}_{P}[\ell(f^{*},z)]=0$.
Thus, the above inequality yields
$\mathbb{P}[\mathbb{E}_{P}[\ell(f^{*}_{\text{M-dro}},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]>\varepsilon]\leq\mathbb{P}[P\notin\mathcal{K}].$
The proof of Theorem 4.1 reveals that $\forall~{}\delta>0$, if the ball size
is big enough, namely $\eta\geq\frac{K}{\sqrt{n}}(1+\sqrt{2\log(1/\delta)}),$
then excess risk will vanish, i.e.,
$\mathbb{E}_{P}[\ell(f^{*}_{\text{M-dro}},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]=0$
with probability $\geq 1-\delta$. This behavior shows up precisely in Figure
2(b).

Our discussion above is not to suggest the choice of $\eta$ 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 previous 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.1) or using variability regularization (Section 2.2) whose
bounds, when converted to excess risks, typically increase in $\eta$ when
$\eta$ is sufficiently large and, moreover, involve complexity measures on the
hypothesis class (e.g., the $\phi$-divergence case in [9, Theorems 3, 6] and
the Wasserstein case in [56, Corollaries 2, 4]). Our developments in Section 3
thus appear to provide a unique explanation for the significant outperformance
of DRO in this example.

## Acknowledgments and Disclosure of Funding

We gratefully acknowledge support from the National Science Foundation under
grants CAREER CMMI-1834710 and IIS-1849280. We also thank Nathan Kallus and
Jia-Jie Zhu for the greatly helpful discussion that helps improve this paper.

## References

  * Vapnik and Chervonenkis [1991] Vladimir Vapnik and Alexey Chervonenkis.  The necessary and sufficient conditions for consistency in the empirical risk minimization method.  _Pattern Recognition and Image Analysis_ , 1(3):283–305, 1991.
  * Delage and Ye [2010] Erick Delage and Yinyu Ye.  Distributionally robust optimization under moment uncertainty with application to data-driven problems.  _Operations Research_ , 58(3):595–612, 2010.
  * Goh and Sim [2010] Joel Goh and Melvyn Sim.  Distributionally robust optimization and its tractable approximations.  _Operations Research_ , 58(4-Part-1):902–917, 2010.
  * Wiesemann et al. [2014] Wolfram Wiesemann, Daniel Kuhn, and Melvyn Sim.  Distributionally robust convex optimization.  _Operations Research_ , 62(6):1358–1376, 2014\.
  * Gao et al. [2017] Rui Gao, Xi Chen, and Anton J Kleywegt.  Wasserstein distributionally robust optimization and variation regularization.  _arXiv preprint arXiv:1712.06050_ , 2017.
  * Chen and Paschalidis [2018] Ruidi Chen and Ioannis C Paschalidis.  A robust learning approach for regression models based on distributionally robust optimization.  _Journal of Machine Learning Research_ , 19(13), 2018.
  * Gotoh et al. [2018] 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):448–452, 2018.
  * Lam [2019] Henry Lam.  Recovering best statistical guarantees via the empirical divergence-based distributionally robust optimization.  _Operations Research_ , 67(4):1090–1105, 2019\.
  * Duchi and Namkoong [2019] John C Duchi and Hongseok Namkoong.  Variance-based regularization with convex objectives.  _Journal of Machine Learning Research_ , 20:68–1, 2019\.
  * Shafieezadeh-Abadeh et al. [2019] Soroosh Shafieezadeh-Abadeh, Daniel Kuhn, and Peyman Mohajerin Esfahani.  Regularization via mass transportation.  _Journal of Machine Learning Research_ , 20(103):1–68, 2019.
  * Kuhn et al. [2019] 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.
  * Blanchet et al. [2019a] Jose Blanchet, Yang Kang, and Karthyek Murthy.  Robust Wasserstein profile inference and applications to machine learning.  _Journal of Applied Probability_ , 56(3):830–857, 2019a.
  * Ruszczyński and Shapiro [2006] Andrzej Ruszczyński and Alexander Shapiro.  Optimization of convex risk functions.  _Mathematics of Operations Research_ , 31(3):433–452, 2006.
  * Rockafellar [2007] R Tyrrell Rockafellar.  Coherent approaches to risk in optimization under uncertainty.  In _OR Tools and Applications: Glimpses of Future Technologies_ , pages 38–61. Informs, 2007.
  * Bousquet and Elisseeff [2002] Olivier Bousquet and André Elisseeff.  Stability and generalization.  _Journal of Machine Learning Research_ , 2:499–526, 2002\.
  * Xu and Mannor [2012] Huan Xu and Shie Mannor.  Robustness and generalization.  _Machine Learning_ , 86(3):391–423, 2012.
  * Staib and Jegelka [2019] Matthew Staib and Stefanie Jegelka.  Distributionally robust optimization and generalization in kernel methods.  In _Advances in Neural Information Processing Systems_ , pages 9131–9141, 2019.
  * Jiang et al. [2022] Yiding Jiang, Vaishnavh Nagarajan, Christina Baek, and J Zico Kolter.  Assessing generalization of SGD via disagreement.  _International Conference on Learning Representations_ , 2022.
  * Ben-Tal et al. [2009] Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski.  _Robust Optimization_.  Princeton University Press, 2009.
  * Bertsimas et al. [2011] Dimitris Bertsimas, David B Brown, and Constantine Caramanis.  Theory and applications of robust optimization.  _SIAM Review_ , 53(3):464–501, 2011.
  * Xu et al. [2009] Huan Xu, Constantine Caramanis, and Shie Mannor.  Robustness and regularization of support vector machines.  _Journal of Machine Learning Research_ , 10(7), 2009.
  * Xu et al. [2010] Huan Xu, Constantine Caramanis, and Shie Mannor.  Robust regression and Lasso.  _IEEE Transactions on Information Theory_ , 56(7):3561–3574, 2010.
  * Scarf [1958] Herbert Scarf.  A min-max solution of an inventory problem.  _Studies in the Mathematical Theory of Inventory and Production_ , 1958.
  * Petersen et al. [2000] Ian R 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–412, 2000.
  * Hansen and Sargent [2008] Lars Peter Hansen and Thomas J Sargent.  _Robustness_.  Princeton University Press, 2008.
  * Glasserman and Xu [2014] Paul Glasserman and Xingbo Xu.  Robust risk measurement and model risk.  _Quantitative Finance_ , 14(1):29–58, 2014.
  * Ben-Tal et al. [2013] 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):341–357, 2013.
  * Bayraksan and Love [2015] Güzin Bayraksan and David K Love.  Data-driven stochastic programming using phi-divergences.  In _Tutorials in Operations Research_ , pages 1–19. INFORMS, 2015\.
  * Jiang and Guan [2016] Ruiwei Jiang and Yongpei Guan.  Data-driven chance constrained stochastic program.  _Mathematical Programming_ , 158(1):291–327, 2016\.
  * Lam [2016] Henry Lam.  Robust sensitivity analysis for stochastic systems.  _Mathematics of Operations Research_ , 41(4):1248–1275, 2016.
  * Lam [2018] Henry Lam.  Sensitivity to serial dependency of input processes: A robust approach.  _Management Science_ , 64(3):1311–1327, 2018\.
  * Esfahani and Kuhn [2018] Peyman Mohajerin Esfahani and Daniel Kuhn.  Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations.  _Mathematical Programming_ , 171(1-2):115–166, 2018.
  * Blanchet and Murthy [2019] Jose Blanchet and Karthyek Murthy.  Quantifying distributional model risk via optimal transport.  _Mathematics of Operations Research_ , 44(2):565–600, 2019.
  * Gao and Kleywegt [2016] Rui Gao and Anton J Kleywegt.  Distributionally robust stochastic optimization with Wasserstein distance.  _arXiv preprint arXiv:1604.02199_ , 2016.
  * Ghaoui et al. [2003] Laurent El Ghaoui, Maksim Oks, and Francois Oustry.  Worst-case value-at-risk and robust portfolio optimization: A conic programming approach.  _Operations Research_ , 51(4):543–556, 2003.
  * Hanasusanto et al. [2015] Grani A Hanasusanto, Vladimir Roitch, Daniel Kuhn, and Wolfram Wiesemann.  A distributionally robust perspective on uncertainty quantification and chance constrained programming.  _Mathematical Programming_ , 151(1):35–62, 2015\.
  * Popescu [2005] Ioana Popescu.  A semidefinite programming approach to optimal-moment bounds for convex classes of distributions.  _Mathematics of Operations Research_ , 30(3):632–657, 2005.
  * Van Parys et al. [2016] Bart PG Van Parys, Paul J Goulart, and Daniel Kuhn.  Generalized Gauss inequalities via semidefinite programming.  _Mathematical Programming_ , 156(1-2):271–302, 2016.
  * Li et al. [2017] Bowen Li, Ruiwei Jiang, and Johanna L Mathieu.  Ambiguous risk constraints with moment and unimodality information.  _Mathematical Programming_ , pages 1–42, 2017.
  * Chen et al. [2020] Xi Chen, Simai He, Bo Jiang, Christopher Thomas Ryan, and Teng Zhang.  The discrete moment problem with nonconvex shape constraints.  _Operations Research_ , 2020.
  * Chen et al. [2018] Louis Chen, Will Ma, Karthik Natarajan, David Simchi-Levi, and Zhenzhen Yan.  Distributionally robust linear and discrete optimization with marginals.  _Available at SSRN 3159473_ , 2018.
  * Doan et al. [2015] Xuan Vinh Doan, Xiaobo Li, and Karthik Natarajan.  Robustness to dependency in portfolio optimization using overlapping marginals.  _Operations Research_ , 63(6):1468–1488, 2015\.
  * Dhara et al. [2021] Anulekha Dhara, Bikramjit Das, and Karthik Natarajan.  Worst-case expected shortfall with univariate and bivariate marginals.  _INFORMS Journal on Computing_ , 33(1):370–389, 2021.
  * Bertsimas et al. [2018] Dimitris Bertsimas, Vishal Gupta, and Nathan Kallus.  Robust sample average approximation.  _Mathematical Programming_ , 171(1-2):217–282, 2018.
  * Zhang et al. [2016] Yiling Zhang, Siqian Shen, and Johanna L Mathieu.  Distributionally robust chance-constrained optimal power flow with uncertain renewables and uncertain reserves provided by loads.  _IEEE Transactions on Power Systems_ , 32(2):1378–1388, 2016.
  * Lam and Mottet [2017] Henry Lam and Clementine Mottet.  Tail analysis without parametric models: A worst-case perspective.  _Operations Research_ , 65(6):1696–1711, 2017\.
  * Zhao and Jiang [2017] Chaoyue Zhao and Ruiwei Jiang.  Distributionally robust contingency-constrained unit commitment.  _IEEE Transactions on Power Systems_ , 33(1):94–102, 2017.
  * Van Parys et al. [2020] Bart PG Van Parys, Peyman Mohajerin Esfahani, and Daniel Kuhn.  From data to decisions: Distributionally robust optimization is optimal.  _Management Science_ , 2020.
  * Sutter et al. [2020] Tobias Sutter, Bart PG Van Parys, and Daniel Kuhn.  A general framework for optimal data-driven optimization.  _arXiv preprint arXiv:2010.06606_ , 2020.
  * Gupta [2019] Vishal Gupta.  Near-optimal Bayesian ambiguity sets for distributionally robust optimization.  _Management Science_ , 65(9):4242–4260, 2019\.
  * Duchi et al. [2021] John C Duchi, Peter W Glynn, and Hongseok Namkoong.  Statistics of robust optimization: A generalized empirical likelihood approach.  _Mathematics of Operations Research_ , 2021.
  * Blanchet et al. [2019b] Jose Blanchet, Karthyek Murthy, and Nian Si.  Confidence regions in Wasserstein distributionally robust estimation.  _arXiv preprint arXiv:1906.01614_ , 2019b.
  * Lam and Zhou [2017] 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.
  * Blanchet and Kang [2021] Jose Blanchet and Yang Kang.  Sample out-of-sample inference based on Wasserstein distance.  _Operations Research_ , 2021.
  * Gotoh et al. [2021] Jun-ya Gotoh, Michael Jong Kim, and Andrew EB Lim.  Calibration of distributionally robust empirical optimization models.  _Operations Research_ , 2021.
  * Gao [2020] Rui Gao.  Finite-sample guarantees for Wasserstein distributionally robust optimization: Breaking the curse of dimensionality.  _arXiv preprint arXiv:2009.04382_ , 2020.
  * Bartlett et al. [2005] Peter L Bartlett, Olivier Bousquet, Shahar Mendelson, et al.  Local Rademacher complexities.  _The Annals of Statistics_ , 33(4):1497–1537, 2005.
  * Hashimoto et al. [2018] Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang.  Fairness without demographics in repeated loss minimization.  In _International Conference on Machine Learning_ , pages 1929–1938. PMLR, 2018.
  * Goodfellow et al. [2015] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  In _International Conference on Learning Representations_ , 2015.
  * Madry et al. [2018] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  In _International Conference on Learning Representations_ , 2018.
  * Sagawa et al. [2020] Shiori Sagawa, Pang Wei Koh, Tatsunori B. Hashimoto, and Percy Liang.  Distributionally robust neural networks.  In _International Conference on Learning Representations_ , 2020.
  * Liu et al. [2021] 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 on Artificial Intelligence_ , volume 35, pages 8662–8670, 2021.
  * Kurakin et al. [2017] Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio.  Adversarial machine learning at scale.  In _International Conference on Learning Representations_ , 2017.
  * Duchi and Namkoong [2021] John C Duchi and Hongseok Namkoong.  Learning models with uniform performance via distributionally robust optimization.  _The Annals of Statistics_ , 49(3):1378–1406, 2021.
  * Tsipras et al. [2019] 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.
  * Van Der Vaart and Wellner [1996] Aad W Van Der Vaart and Jon A Wellner.  _Weak Convergence and Empirical Processes_.  Springer, 1996.
  * Gretton et al. [2012] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola.  A kernel two-sample test.  _Journal of Machine Learning Research_ , 13(1):723–773, 2012.
  * Müller [1997] Alfred Müller.  Integral probability metrics and their generating classes of functions.  _Advances in Applied Probability_ , pages 429–443, 1997.
  * Shawe-Taylor et al. [2004] John Shawe-Taylor, Nello Cristianini, et al.  _Kernel Methods for Pattern Analysis_.  Cambridge University Press, 2004.
  * Smola et al. [2007] 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.
  * Grünewälder et al. [2012] Steffen Grünewälder, Guy Lever, Arthur Gretton, Luca Baldassarre, Sam Patterson, and Massimiliano Pontil.  Conditional mean embeddings as regressors.  In _International Conference on Machine Learning_ , 2012.
  * Li et al. [2015] Yujia Li, Kevin Swersky, and Rich Zemel.  Generative moment matching networks.  In _International Conference on Machine Learning_ , pages 1718–1727. PMLR, 2015.
  * Sutherland et al. [2017] 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.
  * Nguyen et al. [2020] Thanh Tang Nguyen, Sunil Gupta, and Svetha Venkatesh.  Distributional reinforcement learning with maximum mean discrepancy.  _arXiv preprint arXiv:2007.12354_ , 2020.
  * Kirschner et al. [2020] Johannes Kirschner, Ilija Bogunovic, Stefanie Jegelka, and Andreas Krause.  Distributionally robust Bayesian optimization.  In _Artificial Intelligence and Statistics_ , pages 2174–2184. PMLR, 2020.
  * Zhu et al. [2021] Jia-Jie Zhu, Wittawat Jitkrittum, Moritz Diehl, and Bernhard Schölkopf.  Kernel distributionally robust optimization: Generalized duality theorem and stochastic approximation.  In _Artificial Intelligence and Statistics_ , volume 130, pages 280–288. PMLR, 2021.
  * Muandet et al. [2017] Krikamol Muandet, Kenji Fukumizu, Bharath Sriperumbudur, and Bernhard Schölkopf.  Kernel mean embedding of distributions: A review and beyond.  _Foundations and Trends® in Machine Learning_ , 10(1-2):1–141, 2017.  ISSN 1935-8237.
  * Borgwardt et al. [2006] Karsten M Borgwardt, Arthur Gretton, Malte J Rasch, Hans-Peter Kriegel, Bernhard Schölkopf, and Alex J Smola.  Integrating structured biological data by kernel maximum mean discrepancy.  _Bioinformatics_ , 22(14):e49–e57, 2006.
  * Mendelson [2003] Shahar Mendelson.  On the performance of kernel classes.  _Journal of Machine Learning Research_ , 4:759–771, 2003\.
  * Bartlett et al. [2006] 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.
  * Wainwright [2019] Martin J Wainwright.  _High-Dimensional Statistics: A Non-Asymptotic Viewpoint_ , volume 48.  Cambridge University Press, 2019.
  * Minh [2010] 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.
  * Yu and Szepesvári [2012] Yaoliang Yu and Csaba Szepesvári.  Analysis of kernel mean matching under covariate shift.  In _International Conference on Machine Learning_ , 2012.
  * Cortes et al. [2008] 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.
  * Kanamori et al. [2012] Takafumi Kanamori, Taiji Suzuki, and Masashi Sugiyama.  Statistical analysis of kernel-based least-squares density-ratio estimation.  _Machine Learning_ , 86(3):335–367, 2012.
  * Steinwart [2001] 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.
  * Cucker and Zhou [2007] Felipe Cucker and Ding Xuan Zhou.  _Learning Theory: An Approximation Theory Viewpoint_ , volume 24.  Cambridge University Press, 2007.
  * Kantorovich and Rubinshtein [1958] Leonid Vasilevich Kantorovich and SG Rubinshtein.  On a space of totally additive functions.  _Vestnik of the St. Petersburg University: Mathematics_ , 13(7):52–59, 1958.
  * Grant and Boyd [2014] Michael Grant and Stephen Boyd.  CVX: Matlab software for disciplined convex programming, version 2.1, 2014.
  * ApS [2021] MOSEK ApS.  _The MOSEK optimization toolbox for Python manual. Version 9.2.46._ , 2021.  URL https://docs.mosek.com/9.2/pythonfusion/index.html.
  * Tolstikhin et al. [2017] Ilya Tolstikhin, Bharath K Sriperumbudur, and Krikamol Muandet.  Minimax estimation of kernel mean embeddings.  _Journal of Machine Learning Research_ , 18(1):3002–3048, 2017.
  * Zhou [2013] Ding-Xuan Zhou.  Density problem and approximation error in learning theory.  In _Abstract and Applied Analysis_ , volume 2013. Hindawi, 2013.
  * Fournier and Guillin [2015] Nicolas Fournier and Arnaud Guillin.  On the rate of convergence in Wasserstein distance of the empirical measure.  _Probability Theory and Related Fields_ , 162(3):707–738, 2015.
  * Gaunt et al. [2017] 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.
  * Laurent and Massart [2000] Beatrice Laurent and Pascal Massart.  Adaptive estimation of a quadratic functional by model selection.  _Annals of Statistics_ , pages 1302–1338, 2000.

##  Appendix A Review on Kernel Mean Embedding

We first review the definition of kernel mean embedding (KME).

######  Definition A.1 (Kernel Mean Embedding).

Given a distribution $Q$, and a positive definite kernel
$k:\mathcal{Z}\times\mathcal{Z}\rightarrow\mathbb{R}$, i.e., given
$n\in\mathbb{N},a_{1},\ldots,a_{n}\in\mathbb{R}$,

$\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}k\left(z_{i},z_{j}\right)\geq 0$

holds for any $z_{1},\ldots,z_{n}\in\mathcal{Z},$ the KME of $Q$ is defined
by:

$\mu_{Q}:=\int k(z,\cdot)Q(\mathrm{d}z).$

We have the following property.

######  Proposition A.2.

[70] For a positive definite kernel $k$ defined on compact space
$\mathcal{Z}\times\mathcal{Z}$, let $\mathcal{H}$ be the induced RKHS. If
$\mathbb{E}_{P}[k(z,z)]<+\infty$, then $\mu_{P}\in\mathcal{H}$ for all
$Q\in\mathcal{P}$.

It is easy to verify that for a bounded kernel,
$\mathbb{E}_{Q}[k(z,z)]<+\infty$ for all distribution $Q$. Therefore, as a
corollary of Proposition A.2, for any bounded kernel, KME is well-defined in
RKHS, i.e., $\mu_{P}\in\mathcal{H}$.

The following proposition provides the properties of KME that we utilize in
Section 4.1. Specifically, Proposition A.3 (i) establishes the equivalence
between MMD and the norm distance in KME. Proposition A.3 (ii) bridges the
expectation to inner product in RKHS in Eq. (15).

$\displaystyle\mathbb{E}_{x\sim P}[f(x)]=\int_{x}\langle
f,k(x,\cdot)\rangle\mathrm{d}P(x)=\langle f,\mu_{P}\rangle.$ (15)

######  Proposition A.3.

Assume the condition in Proposition A.2 for the existence of the kernel mean
embeddings $\mu_{Q_{1}},\mu_{Q_{2}}$ is satisfied. Then,

  1. (i)

[78, 67]
$D_{\text{MMD}}(Q_{1},Q_{2})=\|\mu_{Q_{1}}-\mu_{Q_{2}}\|_{\mathcal{H}}$;

  2. (ii)

[70] $\mathbb{E}_{Q_{1}}[f(z)]=\langle f,\mu_{Q_{1}}\rangle_{\mathcal{H}}.$

Finally, we review the result in [87] used in Section 4.5.

######  Theorem A.4.

[87, Theorem 6.1] Let $(\mathcal{H},\|\cdot\|_{\mathcal{H}})$ be the RKHS
induced by $k(z,z^{\prime})=\exp(-\|z-z^{\prime}\|^{2}_{2}/\sigma^{2})$ on
$\mathcal{Z}=[0,1]^{d}$. Suppose that $\ell(f^{*},\cdot)$ is in the Sobolev
space $H^{d}(\mathbb{R}^{d})$. Then, there exists a constant $C$ independent
on $R$ but dependent on $f$, $d$, and $\sigma$ such that

$\inf_{\|g\|_{\mathcal{H}}\leq R}\|\ell(f^{*},\cdot)-g\|_{\infty}\leq C(\log
R)^{-\frac{d}{16}},~{}\forall~{}R\geq 1.$

##  Appendix B Proof of Theorem 4.1

Starting from the bound (8) in Theorem 3.1, we separate our proof into two
parts. For $\mathbb{P}[P\notin\mathcal{K}]$, we set

$\eta=\frac{K}{\sqrt{n}}(1+\sqrt{2\log(1/\delta)}),$

noting that:

######  Proposition B.1.

[91, Proposition A.1] Let
$k:\mathcal{Z}\times\mathcal{Z}\rightarrow\mathbb{R}$ be a continuous positive
definite kernel on nonempty compact set $\mathcal{Z}\subset\mathbb{R}^{d}$
with $\sup_{z\in\mathcal{Z}}\sqrt{k(z,z)}\leq K<\infty$. Then for any
$\delta\in(0,1)$ with probability at least $1-\delta$,

$\left\|\mu_{\hat{P}}-\mu_{P}\right\|_{\mathcal{H}}\leq\frac{K}{\sqrt{n}}(1+\sqrt{2\log(1/\delta)}).$

For the second term
$\mathbb{P}[\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f^{*},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]>\varepsilon|P\in\mathcal{K}]$
in (8), conditional on $P\in\mathcal{K}$ we have that

$\displaystyle\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f^{*},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]=\max_{Q\in\mathcal{K}}\langle\ell(f^{*},\cdot),\mu_{Q}-\mu_{P}\rangle_{\mathcal{H}},$

where the second line follows from (15). Then, we have

$\displaystyle\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f^{*},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]=$
$\displaystyle~{}\max_{Q\in\mathcal{K}}\langle\ell(f^{*},\cdot),\mu_{Q}-\mu_{P}\rangle_{\mathcal{H}}$
$\displaystyle\leq$
$\displaystyle~{}\max_{Q\in\mathcal{K}}\|\ell(f^{*},\cdot)\|_{\mathcal{H}}\|\mu_{Q}-\mu_{P}\|_{\mathcal{H}}\leq
2M\eta,$

where the first inequality follows from the Cauchy-Schwarz inequality, and the
last inequality holds since for all $P\in\mathcal{K}$,

$\displaystyle\|\mu_{Q}-\mu_{{P}}\|_{\mathcal{H}}\leq\|\mu_{Q}-\mu_{\hat{P}}\|_{\mathcal{H}}+\|\mu_{\hat{P}}-\mu_{P}\|_{\mathcal{H}}\leq
2\eta$

by the triangle inequality. Hence,

$\displaystyle\mathbb{P}[\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f^{*},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]>\varepsilon|P\in\mathcal{K}]\leq$
$\displaystyle~{}\mathbb{P}[\max_{P\in\mathcal{K}}\|\ell(f^{*},\cdot)\|_{\mathcal{H}}\|\mu_{Q}-\mu_{P}\|_{\mathcal{H}}>\varepsilon|P\in\mathcal{K}]=0.$

provided that $\varepsilon\geq 2M\eta$. Therefore, with probability at least
$1-\delta$,

$\displaystyle\mathbb{E}_{P}[\ell(f^{*}_{\text{M-dro}},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]\leq
2M\eta=\frac{2KM}{\sqrt{n}}(1+\sqrt{2\log(1/\delta)}).$

This completes our proof.

##  Appendix C Proof of Theorem 4.3

For notational simplicity, we denote

$g_{R}:=\arg\inf_{\|g\|_{\mathcal{H}}\leq R}\|\ell(f^{*},\cdot)-g\|_{\infty}$

for all $R\geq 1$, where $g_{R}$ is well-defined since for fixed $R$,
$h(g)=\|\ell(f^{*},\cdot)-g\|_{\infty}$ is a continuous function over a
compact set $\\{g:\|g\|_{\mathcal{H}}\leq R\\}.$ Then, by Theorem 3.1 and
Proposition B.1, for any $\delta>0$, once we set
$\eta=\frac{1}{\sqrt{n}}(1+\sqrt{2\log(1/\delta)}),$ we have that

$\mathbb{P}[\mathbb{E}_{P}[\ell(f^{*}_{\text{M-dro}},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]>\varepsilon]\leq\delta+\mathbb{P}[\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f^{*},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]>\varepsilon|P\in\mathcal{K}].$

By definition, we obtain

$\displaystyle\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f^{*},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]=$
$\displaystyle~{}\max_{Q\in\mathcal{K}}\Big{\\{}\int\ell(f^{*},z)Q(\mathrm{d}z)-\int\ell(f^{*},z)P(\mathrm{d}z)\Big{\\}}$
$\displaystyle\leq$ $\displaystyle~{}\max_{Q\in\mathcal{K}}\Big{\\{}\int
g_{R}Q(\mathrm{d}z)-\int
g_{R}P(\mathrm{d}z)\Big{\\}}+2\|\ell(f^{*},\cdot)-g_{R}\|_{\infty}$
$\displaystyle\leq$
$\displaystyle~{}\max_{Q\in\mathcal{K}}\\{\|g_{R}\|_{\mathcal{H}}\|\mu_{Q}-\mu_{P}\|_{\mathcal{H}}\\}+2\|\ell(f^{*},\cdot)-g_{R}\|_{\infty}$
$\displaystyle\leq$ $\displaystyle~{}2(\eta
R+\|\ell(f^{*},\cdot)-g_{R}\|_{\infty}),$

where the second equality follows from the Cauchy-Schwarz inequality. We have

$\|\ell(f^{*},\cdot)-g_{R}\|_{\infty}=I(\ell(f^{*},\cdot),R)\leq C(\log
R)^{-d/16}$

according to [87, Theorem 6.1] (and see [92, Proposition 18] for details on
the constants). Then, taking infimum over $R\geq 1$ and combining the
equations above yield the desired result.

##  Appendix D Extensions to Other DRO Variants

We provide more details in applying our framework to Wasserstein and
$\phi$-divergence DROs in support of Section 5.

###  D.1 1-Wasserstein DRO

We focus on the 1-Wasserstein distance, which is defined as:

######  Definition D.1 (1-Wasserstein distance).

For two distributions $Q_{1},Q_{2}\in\mathcal{P}$ on domain $\mathbb{R}^{d}$,
the 1-Wasserstein distance
$D_{W_{1}}:\mathcal{P}\times\mathcal{P}\rightarrow\mathbb{R}_{+}$ is defined
by

$D_{W_{1}}(Q_{1},Q_{2}):=\inf\Big{\\{}\int_{\mathcal{Z}^{2}}\left\|z_{1}-z_{2}\right\|\Pi\left(\mathrm{d}z_{1},\mathrm{~{}d}z_{2}\right):\begin{array}[]{l}\Pi\text{
is a joint distribution of }z_{1}\text{ and }z_{2}\\\ \text{with marginals
}Q_{1}\text{ and }Q_{2}\text{, respectively }\end{array}\Big{\\}},$

where $\|\cdot\|$ is a given norm in $\mathbb{R}^{d}$.

Similar to (10), we define 1-Wasserstein DRO as

$\min_{f\in\mathcal{F}}\max_{Q:D_{W_{1}}(Q,\hat{P})\leq\eta}\mathbb{E}_{Q}[\ell(f,z)]$
(16)

and denote $f^{*}_{\text{W-dro}}$ as the solution to (16). Also define
$\|\cdot\|_{\text{Lip}}$ as the Lipschitz norm.

Recall that in Theorem 5.1, we have the following generalization bound:

$\mathbb{E}_{P}[\ell(f^{*}_{\text{W-dro}},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]\leq
2\|\ell(f^{*},\cdot)\|_{\text{Lip}}\Big{(}\frac{\log(c_{1}/\delta)}{c_{2}n}\Big{)}^{1/\max\\{d,2\\}}.$

As discussed in Section 5, Theorem 5.1 is obtained via analyzing the two
components in Theorem 3.1, which respectively correspond to: (1) the ambiguity
set contains true distribution $P$ with high confidence and (2) compatibility
of the Wasserstein distance with $\ell(f^{*},\cdot)$. For the first component,
we use the concentration of $D_{W_{1}}(P,\hat{P})$ established in [93, Theorem
2]:

######  Lemma D.2.

[93, Theorem 2] Suppose that $P$ is a light-tailed distribution in the sense
that there exists $a>1$ such that

$A:=\mathbb{E}_{P}[\exp\left(\|z\|^{a}\right)]<\infty.$

Then, there exists constants $c_{1}$ and $c_{2}$ that only depends on $a,A,$
and $d$ such that for all $\delta\geq 0$, if
$n\geq\frac{\log(c_{1}/\delta)}{c_{2}}$, then

$D_{W_{1}}(P,\hat{P})\leq\Big{(}\frac{\log(c_{1}/\delta)}{c_{2}n}\Big{)}^{1/\max\\{d,2\\}}$

with probability at least $1-\delta$.

For the second component, we use the bound

$\mathbb{E}_{Q_{1}}[\ell(f^{*},z)]-\mathbb{E}_{Q_{2}}[\ell(f^{*},z)]\leq\|\ell(f^{*},\cdot)\|_{\text{Lip}}D_{W_{1}}(Q_{1},Q_{2})$

which follows from the dual representation of $D_{W_{1}}(\cdot,\cdot)$ [32].
With these, a similar analysis as that for Theorem 4.1 yields Theorem 5.1. The
detailed proof is deferred to Appendix F.1.

###  D.2 $\phi$-divergence DRO

Next we consider the use of $\phi$-divergence, defined as:

######  Definition D.3 ($\phi$-divergence).

Let $Q_{1}$ and $Q_{2}$ be two probability distributions over a space $\Omega$
such that $Q_{1}\ll Q_{2}$, i.e., $Q_{1}$ is absolutely continuous with
respect to $Q_{2}$. Then, for a convex function
$\phi:[0,\infty)\rightarrow(-\infty,\infty]$ such that $\phi(x)$ is finite for
all $x>0,\phi(1)=0$, and $\phi(0)=\lim_{t\rightarrow 0^{+}}\phi(t)$ (which
could be infinite), the $\phi$-divergence of $Q_{1}$ from $Q_{2}$ is defined
as

$D_{\phi}(Q_{1}\|Q_{2})=\int_{\Omega}\phi\Big{(}\frac{\mathrm{d}Q_{1}}{\mathrm{d}Q_{2}}\Big{)}\mathrm{d}Q_{2}.$

As discussed in Section 5, using the $\phi$-divergence for DRO entails a bit
more intricacies than Wasserstein DRO due to the absolute continuity
requirement in defining the $\phi$-divergence. In particular, if the true
distribution $P$ is continuous, then setting the center of a $\phi$-divergence
ball as the empirical distribution $\hat{P}$ would make the ball never cover
the truth, which violates the conditions required in developing our
generalization bounds. To remedy, one can set the ball center using kernel
density estimate or a parametric distribution, albeit with the price of
additional approximation errors coming from the “smoothing” of the empirical
distribution. In the following, we first present a general bound for
$\phi$-divergence DRO that leaves open the choice of the ball center, which we
denote $P_{0}$, and the function $\phi$. We then recall and discuss further
Theorem 5.2 that gives a more explicit bound for the case of
$\chi^{2}$-divergence and when the true distribution $P$ is finitely discrete,
for which we could use the empirical distribution $\hat{P}$ as the ball center
and hence avoid the additional smoothing error.

Like above, we define $\phi$-divergence DRO as

$\min_{f\in\mathcal{F}}\max_{Q:D_{\phi}(Q\|P_{0})\leq\eta}\mathbb{E}_{Q}[\ell(f,z)]$
(17)

where $P_{0}$ is a baseline distribution constructed from iid samples
$\\{z_{i}\\}_{i=1}^{n}$. We denote $f^{*}_{\text{$\phi$-dro}}$ as the solution
to (17). We have the following result:

######  Theorem D.4 (General Generalization Bounds for $\phi$-divergence DRO).

Suppose that for a given $0<\delta<1$, we construct ambiguity set
$\mathcal{K}=\\{Q:D_{\phi}(Q\|P_{0})\leq\eta\\}$ such that

  1. (i)

(high-confidence ambiguity set) $\mathbb{P}[P\in\mathcal{K}]\geq 1-\delta/2$;

  2. (ii)

(bound of DRO above the baseline)
$\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}[\ell(f^{*},z)]-\mathbb{E}_{P_{0}}[\ell(f^{*},z)]\leq
C_{1}(\ell(f^{*},\cdot),\sqrt{\eta},\phi)$;

  3. (iii)

(approximation error)
$\mathbb{E}_{P_{0}}[\ell(f^{*},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]\leq
C_{2}(\ell(f^{*},\cdot),n,\delta)$ with probability at least $1-\delta/2$.

where $C_{1}$ and $C_{2}$ are quantities that depend on the respective
arguments. Then, the $\phi$-divergence DRO solution
$f^{*}_{\text{$\phi$-dro}}$ satisfies

$\mathbb{E}_{P}[\ell(f^{*}_{\text{$\phi$-dro}},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]\leq
C_{1}(\ell(f^{*},\cdot),\sqrt{\eta},\phi)+C_{2}(\ell(f^{*},\cdot),n,\delta)$

with probability at least $1-\delta$.

Theorem D.4 is derived by expanding the analysis for Theorem 3 to incorporate
the error between the DRO optimal value over its baseline $P_{0}$, and also
the approximation error induced by $P_{0}$ over $P$. This additional
decomposition facilitates the analysis of specific $\phi$-divergences. The
proof is deferred to Appendix F.2.

Next, we can apply the above to the $\chi^{2}$-divergence with $P_{0}$ set to
be the empirical distribution in the finitely discrete case. First we define
$\chi^{2}$-divergence as follows:

######  Definition D.5 ( $\chi^{2}$-divergence).

Let $Q_{1}$ and $Q_{2}$ be two probability distributions over a space $\Omega$
such that $Q_{1}\ll Q_{2}$, i.e., $Q_{1}$ is absolutely continuous with
respect to $Q_{2}$. Then, the $\chi^{2}$-divergence of $Q_{1}$ from $Q_{2}$ is
defined as

$D_{\chi^{2}}(Q_{1}\|Q_{2})=\int_{\Omega}\Big{(}\frac{\mathrm{d}Q_{1}}{\mathrm{d}Q_{2}}-1\Big{)}^{2}\Big{/}\Big{(}\frac{\mathrm{d}Q_{1}}{\mathrm{d}Q_{2}}\Big{)}\mathrm{d}Q_{2}.$

With this, we consider $\chi^{2}$-divergence DRO

$\min_{f\in\mathcal{F}}\max_{Q:D_{\chi^{2}}(Q\|\hat{P})\leq\eta}\mathbb{E}_{Q}[\ell(f,z)]$
(18)

where we now set the empirical distribution $\hat{P}$ as the ball center. We
denote $f^{*}_{\text{$\chi^{2}$-dro}}$ as the solution to (18). Now recall the
generalization bound in Theorem 5.2:

$\mathbb{E}_{P}[\ell(f^{*}_{\chi^{2}\text{-dro}},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]\leq\|\ell(f^{*},\cdot)\|_{\infty}\Big{\\{}\frac{1}{\sqrt{n}}\sqrt{m+2\log(4/\delta)+2\sqrt{m\log(4/\delta)}}+\sqrt{\frac{2\log(2/\delta)}{n}}\Big{\\}}$

Deriving this bound utilizes Theorem D.4 and the finite-sample approximation
error of $\chi^{2}$-statistics established in [94]. The detailed proof is
deferred to Appendix F.3. Once again, this bound in Theorem 5.2 involves only
$\ell(f^{*},\cdot)$ but not other candidates in the hypothesis class. To
consider cases using smoothed $P_{0}$ such as kernel density estimate and with
continuous ground-truth $P$, we would need to derive bounds on their
divergence and analyze the approximation error on the expected loss between
$P_{0}$ and $P$. These are both substantial investigation that we delegate to
future work.

##  Appendix E Extensions to Distributional Shift Setting

We extend our framework to the setting of distributional shift as follows. We
have iid samples from the training distribution $P_{\text{train}}$. Our
testing distribution $P_{\text{test}}$, however, is different from
$P_{\text{train}}$, i.e., $P_{\text{test}}\neq P_{\text{train}}$. Let

$f^{*}_{\text{test}}\in\text{argmin}_{f\in\mathcal{F}}\mathbb{E}_{P_{\text{test}}}[\ell(f,z)]$

be the oracle best solution under $P_{\text{test}}$. Our goal is derive a
data-driven solution $f_{\text{data}}$ to bound the excess risk for the
_testing_ objective

$\mathbb{E}_{P_{\text{test}}}\ell(f_{\text{data}},z)-\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{test}},z).$
(19)

We first provide a general DRO bound as Theorem 3.1 that allows for
distribution shift:

######  Theorem E.1 (A General DRO Bound under Distributional Shift).

Let $\mathcal{Z}\subset\mathbb{R}^{d}$ be a sample space, $P_{\text{train}}$
be a distribution on $\mathcal{Z}$, $\\{z_{i}\\}_{i=1}^{n}$ be iid samples
from $P_{\text{train}}$, and $\mathcal{F}$ be the function class. For loss
function $\ell:\mathcal{F}\times\mathcal{Z}\rightarrow\mathbb{R}$ and DRO
$\min\limits_{f\in\mathcal{F}}\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f,z),$
DRO solution $f^{*}_{\text{dro}}$ satisfies that for any $\varepsilon>0$,

$\displaystyle~{}\mathbb{P}[\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{dro}},z)-\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{test}},z)>\varepsilon]$
(20) $\displaystyle\leq$
$\displaystyle~{}\mathbb{P}[P_{\text{test}}\notin\mathcal{K}]+\mathbb{P}[\max_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*}_{\text{test}},z)-\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{test}},z)>\varepsilon|P_{\text{test}}\in\mathcal{K}].$

###### Proof.

The proof is identical to that of Theorem 3.1, except that we put subscript
“test” in $P$ and $f^{*}$ there. ∎

Theorem E.1, and its proof that is virtually identical to that of Theorem 3.1,
shows that our main framework in Section 3 can be naturally employed under
distribution shift. In particular, the ambiguity set $\mathcal{K}$ needs to be
constructed from the training set, otherwise there is no restriction on its
application. The key now is the choice of ambiguity set size and how it
distorts generalization more explicitly when distribution shift happens.
Below, we investigate the cases of MMD DRO and 1-Wasserstein DRO whose
explicit distribution shift bounds could be readily derived.

First, we define MMD DRO under distribution shift as

$\min_{f\in\mathcal{F}}\max_{Q:D_{\text{MMD}}(Q,\hat{P}_{\text{train}})\leq\eta}\mathbb{E}_{Q}[\ell(f,z)]$
(21)

where $\hat{P}_{\text{train}}$ is the empirical distribution constructed by
iid samples $\\{z_{i}\\}_{i=1}^{n}$ from $P_{\text{train}}$. We now denote
$f^{*}_{\text{M-dro}}$ as the solution of (21).

######  Theorem E.2 (Generalization Bounds for MMD DRO under Distributional
Shift).

Let $\mathcal{Z}$ be a compact subspace of $\mathbb{R}^{d}$,
$k:\mathcal{Z}\times\mathcal{Z}\rightarrow\mathbb{R}$ be a bounded continuous
positive definite kernel, and
$(\mathcal{H},\langle\cdot,\cdot\rangle_{\mathcal{H}})$ be the corresponding
RKHS. Suppose also that (i) $\sup_{z\in\mathcal{Z}}\sqrt{k(z,z)}\leq K$; (ii)
$\ell(f^{*}_{\text{test}},\cdot)\in\mathcal{H}$ with
$\|\ell(f^{*}_{\text{test}},\cdot)\|_{\mathcal{H}}<+\infty$; (iii)
$D_{\text{MMD}}(P_{\text{train}},P_{\text{test}})<+\infty$. Then, for all
$\delta\geq 0$, if we choose ball size
$\eta=D_{\text{MMD}}(P_{\text{train}},P_{\text{test}})+\frac{K}{\sqrt{n}}(1+\sqrt{2\log(1/\delta)})$
for MMD DRO, then MMD DRO solution $f^{*}_{\text{M-dro}}$ satisfies

$\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{M-dro}},z)-\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{test}},z)\leq
2\|\ell(f^{*}_{\text{test}},\cdot)\|_{\mathcal{H}}\Big{\\{}D_{\text{MMD}}(P_{\text{train}},P_{\text{test}})+\frac{K}{\sqrt{n}}(1+\sqrt{2\log(1/\delta)})\Big{\\}}$

with probability at least $1-\delta$.

Compared to Theorem 4.1, Theorem E.2 has the extra condition that
$D_{\text{MMD}}(P_{\text{train}},P_{\text{test}})<+\infty$ which signifies the
amount of distribution shift. Correspondingly the MMD ball size needs to be
chosen to cover this shift amount. We provide the proof that details these
modifications in Appendix F.4.

Next, we define 1-Wasserstein DRO under distribution shift as

$\min_{f\in\mathcal{F}}\max_{Q:D_{W_{1}}(Q,\hat{P}_{\text{train}})\leq\eta}\mathbb{E}_{Q}[\ell(f,z)]$
(22)

where $\hat{P}_{\text{train}}$ is the empirical distribution constructed by
iid samples $\\{z_{i}\\}_{i=1}^{n}$ from $P_{\text{train}}$. We now denote
$f^{*}_{\text{W-dro}}$ as the solution of (22).

######  Theorem E.3 (Generalization Bounds for 1-Wasserstein DRO under
Distributional Shift).

Suppose that $D_{W_{1}}(P_{\text{train}},P_{\text{test}})<+\infty$ and
$P_{\text{train}}$ is a light-tailed distribution in the sense that there
exists $a>1$ such that

$A:=\mathbb{E}_{P_{\text{train}}}[\exp\left(\|z\|^{a}\right)]<\infty.$

Then, there exists constants $c_{1}$ and $c_{2}$ that only depends on $a,A,$
and $d$ such that for all $\delta\geq 0$, if we choose ball size
$\eta=D_{W_{1}}(P_{\text{train}},P_{\text{test}})+\big{(}\frac{\log(c_{1}/\delta)}{c_{2}n}\big{)}^{1/\max\\{d,2\\}}$
and $n\geq\frac{\log(c_{1}/\delta)}{c_{2}}$, then 1-Wasserstein DRO solution
$f^{*}_{\text{W-dro}}$ satisfies

$\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{W-dro}},z)-\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{test}},z)\leq
2\|\ell(f^{*}_{\text{test}},\cdot)\|_{\text{Lip}}\Big{\\{}D_{W_{1}}(P_{\text{train}},P_{\text{test}})+\Big{(}\frac{\log(c_{1}/\delta)}{c_{2}n}\Big{)}^{1/\max\\{d,2\\}}\Big{\\}}$

with probability at least $1-\delta$.

Similar to the MMD DRO case, Theorem E.3, compared to Theorem 5.1, involves
the amount of distribution shift
$D_{W_{1}}(P_{\text{train}},P_{\text{test}})<+\infty$ and correspondingly a
ball size that is chosen to cover this amount. The detailed proof of Theorem
E.3 is deferred to Appendix F.5.

With the generalization bounds in Theorems E.2 and E.3, we now explain how MMD
and Wasserstein DROs can have potential amplified strengths over ERM under
distribution shift. To this end, let us consider using the classical analysis
of ERM to bound the excess risk for the testing objective (19). This entails a
decomposition

$\displaystyle~{}\mathbb{E}_{P_{\text{test}}}\ell(\hat{f}^{*},z)-\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{test}},z)$
$\displaystyle=$
$\displaystyle~{}[\mathbb{E}_{P_{\text{test}}}\ell(\hat{f}^{*},z)-\mathbb{E}_{\hat{P}_{\text{train}}}\ell(\hat{f}^{*},z)]+[\mathbb{E}_{\hat{P}_{\text{train}}}\ell(\hat{f}^{*},z)-\mathbb{E}_{\hat{P}_{\text{train}}}\ell(f^{*}_{\text{test}},z)]+[\mathbb{E}_{\hat{P}_{\text{train}}}\ell(f^{*}_{\text{test}},z)-\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{test}},z)]$

where the second term is $\leq 0$ and the third term depends only on the true
loss $\ell(f^{*}_{\text{test}},\cdot)$. The key is to analyze the first term,
which we decompose into

$\mathbb{E}_{P_{\text{test}}}\ell(\hat{f}^{*},z)-\mathbb{E}_{\hat{P}_{\text{train}}}\ell(\hat{f}^{*},z)=[\mathbb{E}_{P_{\text{test}}}\ell(\hat{f}^{*},z)-\mathbb{E}_{P_{\text{train}}}\ell(\hat{f}^{*},z)]+[\mathbb{E}_{P_{\text{train}}}\ell(\hat{f}^{*},z)-\mathbb{E}_{\hat{P}_{\text{train}}}\ell(\hat{f}^{*},z)].$

If we use the standard approach of uniformly bounding over the hypothesis
class $\mathcal{L}$, then from the first component above we would obtain a
bound that involves

$\sup_{f\in\mathcal{F}}\|l(f,\cdot)\|_{\mathcal{H}}D_{\text{MMD}}(P_{\text{train}},P_{\text{test}})$
(23)

or

$\sup_{f\in\mathcal{F}}\|l(f,\cdot)\|_{\text{Lip}}D_{W_{1}}(P_{\text{train}},P_{\text{test}}).$
(24)

Now, consider the situation where there is a large distribution shift, i.e.,
$D(P_{\text{train}},P_{\text{test}})$ is big, to the extent that it dominates
the error coming from the training set noise that scales with $n$. In this
case, the quantity (23) or (24) could become the dominant term in the ERM
bound. In contrast, in MMD DRO and Wasserstein DRO, the dominant terms are

$2\|\ell(f^{*}_{\text{test}},\cdot)\|_{\mathcal{H}}D_{\text{MMD}}(P_{\text{train}},P_{\text{test}}),$
(25)

and

$2\|\ell(f^{*}_{\text{test}},\cdot)\|_{\text{Lip}}D_{W_{1}}(P_{\text{train}},P_{\text{test}})$
(26)

respectively. Comparing (25) and (26) with (23) and (24), we see that ERM
could amplify the impact of distribution shift
$D_{\text{MMD}}(P_{\text{train}},P_{\text{test}})$ or
$D_{W_{1}}(P_{\text{train}},P_{\text{test}})$ by a factor that involves a
uniform bound on $\\{\ell(f,\cdot):f\in\mathcal{F}\\}$, while the
corresponding factor in DROs only involves the true loss function
$\ell(f^{*}_{\text{test}},\cdot)$. This reveals a potentially significant
benefit of DRO over ERM in the presence of distribution shift.

##  Appendix F Missing Proofs of Additional Results

###  F.1 Proof of Theorem 5.1

Starting from the bound (8) in Theorem 3.1, we separate our proof into two
parts. First, to control $\mathbb{P}[P\notin\mathcal{K}]$, we set

$\eta=\Big{(}\frac{\log(c_{1}/\delta)}{c_{2}n}\Big{)}^{1/\max\\{d,2\\}}.$

Then, by Lemma D.2, for all $n\geq\frac{\log(c_{1}/\delta)}{c_{2}}$, we have
that $\mathbb{P}[P\notin\mathcal{K}]\leq\delta$. For the second term
$\mathbb{P}[\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*},z)-\mathbb{E}_{P}[\ell(f^{*},z)]>\varepsilon|P\in\mathcal{K}]$
in (8), conditional on $P\in\mathcal{K}$ we have that

$\displaystyle\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*},z)-\mathbb{E}_{P}[\ell(f^{*},z)]\leq\max_{Q\in\mathcal{K}}\|\ell(f^{*},\cdot)||_{\text{Lip}}D_{W_{1}}(Q,P),$

by using [88]. Then, we have

$\displaystyle\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*},z)-\mathbb{E}_{P}[\ell(f^{*},z)]\leq$
$\displaystyle~{}\max_{Q\in\mathcal{K}}\|\ell(f^{*},\cdot)||_{\text{Lip}}D_{W_{1}}(Q,P)$
$\displaystyle\leq$
$\displaystyle~{}\max_{Q\in\mathcal{K}}\|\ell(f^{*},\cdot)||_{\text{Lip}}(D_{W_{1}}(Q,\hat{P})+D_{W_{1}}(\hat{P},P))\leq
2\|\ell(f^{*},\cdot)||_{\text{Lip}}\eta,$

where the last line follows from the triangle inequality. Hence,

$\displaystyle\mathbb{P}[\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*},z)-\mathbb{E}_{P}[\ell(f^{*},z)]>\varepsilon|P\in\mathcal{K}]\leq$
$\displaystyle~{}\mathbb{P}[2\|\ell(f^{*},\cdot)||_{\text{Lip}}\eta>\varepsilon|P\in\mathcal{K}]=0.$

provided that $\varepsilon\geq 2\|\ell(f^{*},\cdot)||_{\text{Lip}}\eta$.
Therefore, with probability at least $1-\delta$,

$\displaystyle\mathbb{E}_{P}[\ell(f^{*}_{\text{W-dro}},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]\leq
2\|\ell(f^{*},\cdot)||_{\text{Lip}}\eta=2\|\ell(f^{*},\cdot)\|_{\text{Lip}}\Big{(}\frac{\log(c_{1}/\delta)}{c_{2}n}\Big{)}^{1/\max\\{d,2\\}}.$

This completes our proof.

###  F.2 Proof of Theorem D.4

For simplicity, let

$\mathcal{E}_{1}=\\{P\in\mathcal{K}\\},\quad\mathcal{E}_{2}=\\{\mathbb{E}_{P_{0}}\ell(f^{*},z)-\mathbb{E}_{P}[\ell(f^{*},z)]\leq
C_{2}(\ell(f^{*},\cdot),n,\delta)\\}.$

Similar to proof of Theorem 3.1, we have that

$\displaystyle~{}\mathbb{P}[\mathbb{E}_{P}[\ell(f^{*}_{\text{$\phi$-dro}},z)]-\mathbb{E}_{P}[\ell(f^{*},z)]>\varepsilon]$
$\displaystyle\leq$
$\displaystyle~{}\mathbb{P}[[\mathbb{E}_{P}\ell(f^{*}_{\text{$\phi$-dro}},z)-\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*}_{\text{$\phi$-dro}},z)]+[\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*},z)-\mathbb{E}_{P}\ell(f^{*},z)]>\varepsilon]$
$\displaystyle\leq$
$\displaystyle~{}\mathbb{P}[\mathcal{E}_{1}^{\complement}]+\mathbb{P}[\\{[\mathbb{E}_{P}\ell(f^{*}_{\text{$\phi$-dro}},z)-\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*}_{\text{$\phi$-dro}},z)]+[\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*},z)-\mathbb{E}_{P}\ell(f^{*},z)]>\varepsilon\\}\cap\mathcal{E}_{1}]$
$\displaystyle\leq$
$\displaystyle~{}\delta/2+\mathbb{P}[\\{\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*},z)-\mathbb{E}_{P}[\ell(f^{*},z)]>\varepsilon\\}\cap\mathcal{E}_{1}],$

where the last line follows from
$\mathbb{P}[\mathcal{E}_{1}^{\complement}]\leq\delta/2$ by definition and
$\mathbb{E}_{P}\ell(f^{*}_{\text{$\phi$-dro}},z)-\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*}_{\text{$\phi$-dro}},z)\leq
0$ if $\mathcal{E}_{1}$ occurs according to worst case definition of DRO. Now
we consider

$\mathbb{P}[\\{\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*},z)-\mathbb{E}_{P}[\ell(f^{*},z)]>\varepsilon\\}\cap\mathcal{E}_{1}],$

where we set
$\varepsilon=C_{1}(\ell(f^{*},\cdot),\sqrt{\eta},\phi)+C_{2}(\ell(f^{*},\cdot),n,\delta)$.
This can be rewritten as

$\displaystyle~{}\mathbb{P}[\\{\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*},z)-\mathbb{E}_{P}[\ell(f^{*},z)]>\varepsilon\\}\cap\mathcal{E}_{1}]$
$\displaystyle=$
$\displaystyle~{}\mathbb{P}[\\{\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*},z)-\mathbb{E}_{P}[\ell(f^{*},z)]>\varepsilon\\}\cap\mathcal{E}_{1}\cap\mathcal{E}_{2}]+\mathbb{P}[\\{\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*},z)-\mathbb{E}_{P}[\ell(f^{*},z)]>\varepsilon\\}\cap\mathcal{E}_{1}\cap\mathcal{E}_{2}^{\complement}]$
$\displaystyle\leq$
$\displaystyle~{}\mathbb{P}[\\{\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*},z)-\mathbb{E}_{P_{0}}\ell(f^{*},z)>\varepsilon-
C_{2}(\ell(f^{*},\cdot),n,\delta)\cap\mathcal{E}_{1}\cap\mathcal{E}_{2}\\}]+\mathbb{P}[\mathcal{E}_{2}^{\complement}]$
$\displaystyle\leq$ $\displaystyle~{}0+\delta/2,$

where the last line follows from

$\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*},z)-\mathbb{E}_{P_{0}}\ell(f^{*},z)\leq
C_{1}(\ell(f^{*},\cdot),\sqrt{\eta},\phi)<\varepsilon-
C_{2}(\ell(f^{*},\cdot),n,\delta).$

This completes our proof.

###  F.3 Proof of Theorem 5.2

It suffices to verify assumptions (i)(ii)(iii) in Theorem D.4 with
$C_{1}(\ell(f^{*},\cdot),\sqrt{\eta},\phi)=\sqrt{\eta}\|\ell(f^{*},\cdot)\|_{\infty}$,
$C_{2}(\ell(f^{*},\cdot),n,\delta)=\|\ell(f^{*},\cdot)\|_{\infty}\sqrt{\frac{2\log(2/\delta)}{n}}$.

First, by [94, (4.2)], we have that

$\mathbb{P}[\chi^{2}(P\|\hat{P})>\eta]\leq\mathbb{P}[\chi^{2}_{(m-1)}>n\eta]+\frac{250m}{\sqrt{n}p_{\min}^{3/2}},$

where $\chi^{2}_{(m-1)}$ is a $\chi^{2}$ random variable with degree of
freedom $m-1$. According to [95, Lemma 1],

$\mathbb{P}[\chi^{2}_{(m-1)}>(m-1)+2\sqrt{(m-1)x}+2x]\leq e^{-x}.$

Therefore, for all $n\geq\frac{10^{6}m^{2}}{p^{3}_{\min}\delta^{2}}$,

$\mathbb{P}[\mathbb{P}\notin\mathcal{K}]=\mathbb{P}[\chi^{2}(P\|\hat{P})>\eta]\leq\delta/4+\delta/4=\delta/2$

and (i) is satisfied. Second, note that

$\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*},z)-\mathbb{E}_{\hat{P}}\ell(f^{*},z)=\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{\hat{P}}[(L-1)\ell(f^{*},z)],$

where $L=\frac{\mathrm{d}Q}{\mathrm{d}\hat{P}}$ is the likelihood ratio. Then,
by Cauchy-Schwarz inequality,

$\displaystyle\big{|}\mathbb{E}_{\hat{P}}[(L-1)\ell(f^{*},z)]\big{|}\leq$
$\displaystyle~{}\sqrt{\mathbb{E}_{\hat{P}}[((L-1)/\sqrt{L})^{2}]}\sqrt{\mathbb{E}_{\hat{P}}[(\sqrt{L}\ell(f^{*},z))^{2}]}$
$\displaystyle\leq$
$\displaystyle~{}\sqrt{\mathbb{E}_{\hat{P}}[(L-1)^{2}/L]}\sqrt{\mathbb{E}_{Q}[\ell(f^{*},z)^{2}]}$
$\displaystyle\leq$
$\displaystyle~{}\sqrt{\chi^{2}(Q\|\hat{P})}\sqrt{\|\ell(f^{*},\cdot)\|_{\infty}^{2}}=\sqrt{\eta}\|\ell(f^{*},\cdot)\|_{\infty},$

This gives (ii). Third, by Hoeffding’s inequality,

$\mathbb{P}[\mathbb{E}_{P_{0}}\ell(f^{*},z)-\mathbb{E}_{P}[\ell(f^{*},z)]>t]\leq
e^{-\frac{nt^{2}}{2\|\ell(f^{*},\cdot)\|_{\infty}^{2}}}$

and (iii) is satisfied. This completes our proof.

###  F.4 Proof of Theorem E.2

Starting from the bound (20) in Theorem E.1, we separate our proof into two
parts. First, to control $\mathbb{P}[P_{\text{test}}\notin\mathcal{K}]$, we
set

$\eta=D_{\text{MMD}}(P_{\text{train}},P_{\text{test}})+\frac{K}{\sqrt{n}}(1+\sqrt{2\log(1/\delta)}).$

Then, by Proposition B.1, we have that

$\mathbb{P}[P_{\text{test}}\notin\mathcal{K}]=\mathbb{P}[D_{\text{MMD}}(P_{\text{test}},\hat{P}_{\text{train}})>\eta]\leq\mathbb{P}\Big{[}D_{\text{MMD}}(P_{\text{train}},\hat{P}_{\text{train}})>\frac{K}{\sqrt{n}}(1+\sqrt{2\log(1/\delta)})\Big{]}\leq
1-\delta.$

For the second term
$\mathbb{P}[\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*}_{\text{test}},z)-\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{test}},z)>\varepsilon|P_{\text{test}}\in\mathcal{K}]$
in (8), conditional on $P_{\text{test}}\in\mathcal{K}$, we have that

$\displaystyle\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*}_{\text{test}},z)-\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{test}},z)=\max_{Q\in\mathcal{K}}\langle\ell(f^{*}_{\text{test}},\cdot),\mu_{Q}-\mu_{P_{\text{test}}}\rangle_{\mathcal{H}},$

which follows from (15). Then, we have

$\displaystyle\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*}_{\text{test}},z)-\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{test}},z)=$
$\displaystyle~{}\max_{Q\in\mathcal{K}}\langle\ell(f^{*}_{\text{test}},\cdot),\mu_{Q}-\mu_{P_{\text{test}}}\rangle_{\mathcal{H}}$
$\displaystyle\leq$
$\displaystyle~{}\max_{Q\in\mathcal{K}}\|\ell(f^{*}_{\text{test}},\cdot)\|_{\mathcal{H}}\|\mu_{Q}-\mu_{P_{\text{test}}}\|_{\mathcal{H}}\leq
2\|\ell(f^{*}_{\text{test}},\cdot)\|_{\mathcal{H}}\eta,$

where the first inequality follows from the Cauchy-Schwarz inequality, and the
last inequality holds since for all $P\in\mathcal{K}$,

$\displaystyle\|\mu_{Q}-\mu_{P_{\text{test}}}\|_{\mathcal{H}}\leq\|\mu_{Q}-\mu_{\hat{P}_{\text{train}}}\|_{\mathcal{H}}+\|\mu_{\hat{P}_{\text{train}}}-\mu_{P_{\text{test}}}\|_{\mathcal{H}}\leq
2\eta$

by the triangle inequality. Hence,

$\displaystyle\mathbb{P}[\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*}_{\text{test}},z)-\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{test}},z)>\varepsilon|P_{\text{test}}\in\mathcal{K}]\leq$
$\displaystyle~{}\mathbb{P}[2\|\ell(f^{*}_{\text{test}},\cdot)||_{\mathcal{H}}\eta>\varepsilon|P_{\text{test}}\in\mathcal{K}]=0.$

provided that $\varepsilon\geq
2\|\ell(f^{*}_{\text{test}},\cdot)||_{\mathcal{H}}\eta$. Therefore, with
probability at least $1-\delta$,

$\displaystyle\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{M-dro}},z)-\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{test}},z)\leq$
$\displaystyle~{}2\|\ell(f^{*}_{\text{test}},\cdot)||_{\mathcal{H}}\eta$
$\displaystyle\leq$
$\displaystyle~{}2\|\ell(f^{*}_{\text{test}},\cdot)\|_{\mathcal{H}}\Big{\\{}D_{\text{MMD}}(P_{\text{train}},P_{\text{test}})+\frac{K}{\sqrt{n}}(1+\sqrt{2\log(1/\delta)})\Big{\\}}.$

This completes our proof.

###  F.5 Proof of Theorem E.3

Starting from the bound (20) in Theorem E.1, we separate our proof into two
parts. First, to control $\mathbb{P}[P_{\text{test}}\notin\mathcal{K}]$, we
set

$\eta=D_{W_{1}}(P_{\text{train}},P_{\text{test}})+\Big{(}\frac{\log(c_{1}/\delta)}{c_{2}n}\Big{)}^{1/\max\\{d,2\\}}.$

Then, by Lemma D.2, for all $n\geq\frac{\log(c_{1}/\delta)}{c_{2}}$, we have
that

$\mathbb{P}[P_{\text{test}}\notin\mathcal{K}]=\mathbb{P}[D_{W_{1}}(P_{\text{test}},\hat{P}_{\text{train}})>\eta]\leq\mathbb{P}\Big{[}D_{W_{1}}(P_{\text{train}},\hat{P}_{\text{train}})>\Big{(}\frac{\log(c_{1}/\delta)}{c_{2}n}\Big{)}^{1/\max\\{d,2\\}}\Big{]}\leq
1-\delta.$

For the second term
$\mathbb{P}[\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*}_{\text{test}},z)-\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{test}},z)>\varepsilon|P_{\text{test}}\in\mathcal{K}]$
in (8), conditional on $P_{\text{test}}\in\mathcal{K}$ we have that

$\displaystyle\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*}_{\text{test}},z)-\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{test}},z)\leq\max_{Q\in\mathcal{K}}\|\ell(f^{*}_{\text{test}},\cdot)||_{\text{Lip}}D_{W_{1}}(Q,P_{\text{test}}),$

by using [88]. Then, we have

$\displaystyle~{}\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*}_{\text{test}},z)-\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{test}},z)$
$\displaystyle\leq$
$\displaystyle~{}\max_{Q\in\mathcal{K}}\|\ell(f^{*}_{\text{test}},\cdot)||_{\text{Lip}}D_{W_{1}}(Q,P_{\text{test}})$
$\displaystyle\leq$
$\displaystyle~{}\max_{Q\in\mathcal{K}}\|\ell(f^{*}_{\text{test}},\cdot)||_{\text{Lip}}(D_{W_{1}}(Q,\hat{P}_{\text{train}})+D_{W_{1}}(\hat{P}_{\text{train}},P_{\text{test}}))\leq
2\|\ell(f^{*}_{\text{test}},\cdot)||_{\text{Lip}}\eta,$

where the last line follows from the triangle inequality. Hence,

$\displaystyle\mathbb{P}[\max\limits_{Q\in\mathcal{K}}\mathbb{E}_{Q}\ell(f^{*}_{\text{test}},z)-\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{test}},z)>\varepsilon|P_{\text{test}}\in\mathcal{K}]\leq$
$\displaystyle~{}\mathbb{P}[2\|\ell(f^{*}_{\text{test}},\cdot)||_{\text{Lip}}\eta>\varepsilon|P_{\text{test}}\in\mathcal{K}]=0.$

provided that $\varepsilon\geq
2\|\ell(f^{*}_{\text{test}},\cdot)||_{\text{Lip}}\eta$. Therefore, with
probability at least $1-\delta$,

$\displaystyle\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{W-dro}},z)-\mathbb{E}_{P_{\text{test}}}\ell(f^{*}_{\text{test}},z)\leq$
$\displaystyle~{}2\|\ell(f^{*}_{\text{test}},\cdot)||_{\text{Lip}}\eta$
$\displaystyle\leq$
$\displaystyle~{}2\|\ell(f^{*}_{\text{test}},\cdot)\|_{\text{Lip}}\Big{\\{}D_{W_{1}}(P_{\text{train}},P_{\text{test}})+\Big{(}\frac{\log(c_{1}/\delta)}{c_{2}n}\Big{)}^{1/\max\\{d,2\\}}\Big{\\}}.$

This completes our proof.