# On Certifying and Improving
Generalization to Unseen Domains

Akshay Mehra1, Bhavya Kailkhura2, Pin-Yu Chen3 and Jihun Hamm1
1Tulane University 2Lawrence Livermore National Laboratory 3IBM Research
{amehra<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Domain Generalization (DG) aims to learn models whose performance remains high
on unseen domains encountered at test-time by using data from multiple related
source domains. Many existing DG algorithms reduce the divergence between
source distributions in a representation space to potentially align the unseen
domain close to the sources. This is motivated by the analysis that explains
generalization to unseen domains using distributional distance (such as the
Wasserstein distance) to the sources. However, due to the openness of the DG
objective, it is challenging to evaluate DG algorithms comprehensively using a
few benchmark datasets. In particular, we demonstrate that the accuracy of the
models trained with DG methods varies significantly across unseen domains,
generated from popular benchmark datasets. This highlights that the
performance of DG methods on a few benchmark datasets may not be
representative of their performance on unseen domains in the wild. To overcome
this roadblock, we propose a universal certification framework based on
distributionally robust optimization (DRO) that can efficiently certify the
worst-case performance of any DG method. This enables a data-independent
evaluation of a DG method complementary to the empirical evaluations on
benchmark datasets. Furthermore, we propose a training algorithm that can be
used with any DG method to provably improve their certified performance. Our
empirical evaluation demonstrates the effectiveness of our method at
significantly improving the worst-case loss (i.e., reducing the risk of
failure of these models in the wild) without incurring a significant
performance drop on benchmark datasets.

##  1 Introduction

A major challenge in machine learning is to develop models that can generalize
well to domains unseen during training. For example, a self-driving car or a
drone deployed in the wild can encounter complex spatial or temporal changes
such as object variations, camera blur, unseen weather changes, etc., which
are not seen during training. This domain shift at test-time leads to drastic
degradation in the performance of the models and increases the risk of
deploying these models in the real world [11, 32]. The area of Domain
Generalization (DG) [69] studies this crucial problem and aims to develop
models whose performance remains high on unseen domains (or variations).
Analyses in recent works have demonstrated that the distributional distance
between the source and the unseen domains is a key metric to predict the
generalization performance of the model on unseen domains [62, 40, 39, 26, 19,
63, 7, 70, 6, 1]. To ensure that the unseen domain lies close to the source
domains some works in DG impose additional assumptions [9, 1, 38, 40, 70] on
the unseen domains whereas others learn a representation space in which the
divergence between multiple source domains can be reduced while ensuring high
performance on these domains [1, 24, 79, 76]. By learning such a
representation space, these methods aim to potentially reduce the divergence
between source and unseen domains, thereby guaranteeing generalization.
However, due to the openness of the DG goal, it is challenging to evaluate the
quality of the representation learned by DG algorithms comprehensively only
through empirical evaluations. Furthermore, it is unclear if the performance
of a DG algorithm on benchmark datasets is representative of its performance
in the wild. In Fig. 1, we demonstrate these difficulties by considering a
number of possible target domains such as Arts and Photos from PACS [43],
having variations in the image style as well as various corrupted versions
[32, 52] of domains in PACS. We plot the performance of various DG methods
versus the distance of these domains from the sources in the representation
space. Although, the accuracy of DG methods degrades quickly as the unseen
domain becomes farther from the source (as expected), what is surprising is
the high variability in the accuracy of the models even on unseen domains
equidistant from the sources (e.g., the accuracy varies from 90%-75% at a
normalized distance of 1.2 for G2DM [1] in Fig. 1). Moreover, the performance
of a DG method relative to another method is not consistent over different
unseen domains, making it difficult to assess the progress of DG as a field
(see Sec. 4.1 for a detailed discussion). This highlights the _insufficiency
of empirical evaluation on benchmark datasets to reliably assess the true
generalization performance of DG methods_ and motivates the need for a more
rigorous and reliable method for evaluation of DG algorithms.

(a) G2DM [1] (b) CDAN [45] (c) WM (see Sec. 3) (d) VREX [38]

Figure 1: (Best viewed in color.) Hardness of empirically evaluating the
generalization performance of DG methods: The high variability in the accuracy
at the same distance from the sources demonstrates that the performance of a
DG method on a few domains is not representative of their performance on other
unseen domains. The triangles denote unseen benchmark distributions (Photos
and Art from PACS [43] here (left to right)) and lines denote distributions
under common corruptions.

Thus, we propose a universal, target-independent, and computationally-
efficient certification framework that quantifies the risk of deploying a DG
model in the real world in terms of its worst-case performance. Our
certification framework, _Cert-DG_ , considers the space of probability
distributions with Wasserstein distance as a metric and computes the loss of
the worst-case distribution in a ball around the source distributions (see
Fig. 2) in the representation space. Building on existing works on the strong
duality of distributionally robust optimization (DRO) [26, 62, 7] we show the
ease of computing the dual optimal value with common losses including cross-
entropy, hinge, and 0-1 loss. One issue with measuring distances in the
representation space is that each representation space has an arbitrary scale,
making it difficult to compare the certificates across models trained with
different methods, data, or initializations. To remedy this, we propose a
distance normalization approach, for a fair model comparison that measures all
distances relative to a reference distribution in the representation space. We
propose to use the distribution consisting of the closest misclassified points
of the source domains in the representation space as the reference
distribution (see Sec 3), because of its existence in models trained with any
method, its intuitive meaning, and ease of computation.

For models trained with DG methods, we observe a large gap between the
certified loss and the empirical loss on benchmark and synthetic domains (see
Fig. 3). Therefore, to improve the certified loss of the models trained with
DG methods, we also propose a DRO-based iterative training algorithm, _DR-DG_
, that augments the training data with samples incurring high loss under the
current model. DR-DG can be used to improve the certified loss of models
trained with any DG method and effectively reduces the worst-case loss over a
large distance from the sources with computational complexity similar to
adversarial training [46, 67, 62]. Our results demonstrate a significant
improvement in the certified loss of the models trained with DR-DG with a
minor decrease in the accuracy of the models on the source domains. The
reduction in the gap between the empirical and the certified loss of the
models suggests that DR-DG trained models are more generalizable to unseen
domains as well their performance on benchmark datasets is representative of
their performance in the wild. Thus, our certification framework, which
explicitly provides performance guarantees based on distance, and our
algorithm DR-DG, which trains to minimize the worst-case loss, are efficient
and effective ways for certifying and improving the generalization of models
to unseen domains.

Our main contributions are as follows.

  * •

We highlight a fundamental limitation with the evaluation of DG methods using
a few benchmark datasets, that could lead to a biased evaluation and an
incorrect understanding of their generalization to other unseen domains.

  * •

To achieve provably reliable DG, we propose a target-independent certification
framework that can certify the worst-case performance of any DG method solely
based on the distance in the representation space. We show its computational
efficiency with common losses including cross-entropy, hinge, and 0-1 loss.

  * •

We present a simple intuitive distance normalization technique that allows
comparison of any performance metric across different models in relation to
distances in the representation space.

  * •

We propose a computationally efficient algorithm that improves the
generalization performance of models on unseen domains by reducing the worst-
case loss at different distances.

##  2 Related Work

Domain generalization and domain adaptation: The key problem addressed by
works in these areas is to improve the performance of the models when training
and test distributions are different. Analytical works in these areas [6, 5,
47, 61, 49, 78, 36, 10] have shown that model’s generalization performance
remains high under distribution shifts when the training (source) and test
(target) distributions are close under certain divergence measures.
Distributional divergence measures studied in previous works include the
Wasserstein distance [62, 40, 39, 26], maximum mean discrepancy [63],
$f$-divergence [7, 70], $\mathcal{H}$-divergence [6, 1]. Since generalization
to arbitrary domains is not possible, previous works make additional
assumptions on the unseen domains such as [9] assumes that the source and
target distributions are derived from the same hyper-distribution, [1, 38]
assumes that the target distributions belong to the convex hull of the source
distribution(s), [40] considers shifts generated by different parameterized
transformations. Another line of work considers learning a representation
space by minimizing different divergence measures between the source
distributions [1, 73, 25, 79, 55, 30]. Yet another line of research in DG
learns a representation space that disentangles [3, 74, 20, 51] domain-
specific features from the domain invariant features such that predictors
learned on top of these invariant features also become domain invariant.
Another popular approach for DG uses data augmentation approaches [34, 68, 37,
12, 64] that make the models invariant to common/natural variations of the
data from the source.

Certified robustness: Point-wise certification guarantees on the performance
of the classifier has been extensively studied in the area of certified
adversarial robustness [65, 46, 41, 42, 71, 56, 58, 72, 62, 48], where the
certification outputs a radius around a test point within which classifier
predictions remain constant. Our work is different from these works since we
are concerned with distributional robustness guarantees for DG, i.e., a
certification that allows us to quantify the generalization performance on an
unseen distribution rather than certifying the instance-wise performance (see
Appendix C.3 for a comparison between point-wise and distributional
robustness). Recently, certified robustness has gained attention in the
context of certifying the performance of the classifier (in a distributional
sense) on bounded distribution shifts [40, 70, 59].

Distributionally robust optimization: DRO has been extensively used in machine
learning to quantify the performance of a model on distributions belonging to
different uncertainty sets [7, 50, 21, 77, 26, 8]. Previous works have
considered the uncertainty sets to be the Wasserstein balls [62, 26, 60, 16,
39, 10, 67, 55], $f$-divergence balls [7, 21, 31, 35, 70] around the source
distribution as well as shifts over different groups [57]. Our certification
framework considers the uncertainty set to be the Wasserstein ball around the
source distributions in the representation space.

##  3 A framework for provable domain generalization

Notation: Let $\mathcal{X}$ denote the data domain, $\mathcal{Y}$ denote the
labels, and $P_{S/T}(x,y)$ be the joint distributions of features and labels
for the source/target domain. Let $\mathcal{D}_{S/T}$ denotes examples drawn
from $P_{S/T}(x,y)$. When there are multiple sources, $P_{S}^{i}(x,y)$ denotes
the $i^{th}$ source. Let $g:\mathcal{X}\rightarrow\mathcal{Z}$ be the
representation map of an input $x$ to its features in the representation space
$\mathcal{Z}$ and let $h:\mathcal{Z}\rightarrow\mathcal{Y}$ be the classifier
on top of $\mathcal{Z}$. A distribution on $\mathcal{Z}\times\mathcal{Y}$ can
be a new distribution or a push-forward distribution ($g_{\sharp}\mathcal{P}$)
of an input-space distribution, which can be distinguished from the context.

###  3.1 Domain Generalization via minimizing Wasserstein Distance

Consider the space of joint probability distributions $\Pi(P,Q)$ with marginal
distributions $P$ and $Q$, and suppose $c$ is the cost of transporting mass
from $(x_{1},y_{1})$ to $(x_{2},y_{2})$. The Optimal Transport (OT) distance
[66, 54, 2] is the minimum expected cost
$\inf_{\pi\in\Pi(P,Q)}\mathbb{E}_{\pi}[c((x_{1},y_{1}),(x_{2},y_{2}))]$,
denoted by $OT_{c}(P,Q)$. When the cost $c$ is a $\ell_{2}$-norm, OT distance
is also known as the type-2 Wasserstein distance:
$W_{2}(P,Q)=(\inf_{\pi\in\Pi(P,Q)}\mathbb{E}_{(x_{1},y_{1}),(x_{2},y_{2})\in\pi}[c((x_{1},y_{1}),(x_{2},y_{2}))^{2}])^{\frac{1}{2}}$.
Following [62, 67], we measure $OT_{c}$ between distributions in the
representation space $\mathcal{Z}$ with the cost
$c((z_{1},y_{1}),(z_{2},y_{2}))=\|z_{1}-z_{2}\|^{2}_{2}+\infty\cdot
I[y_{1}\neq y_{2}]$, which allows couplings only between points of the same
class. With this choice of $c$, we have $OT_{c}=W_{2}^{2}$. Previous works
have shown that the Wasserstein distance can be computed efficiently using
linear programming [54, 23], entropic regularization, [17] or the dual
formulation [27, 61, 4] for small-scale problems and specific norms. For
large-scale problems, regularized version of OT is often used [44, 28].

Figure 2: The space of probability distributions with Wasserstein distance as
a metric. $P_{S}$ and $P_{T}$ are the sources and the unseen target
distributions. The color indicates the performance of the given model on a
distribution (Green: good, Red: bad). Naively, the empirical performance
(solid color on each point) of a target $P_{T}$ is only loosely correlated
with its distance from $P_{S}$. On the other hand, the worst-case performance
(gradually changing color from the center to outside) can be efficiently
certified for any distance $\rho$ and is independent of targets.
The adversarial distribution $P_{S_{adv}}$ is a unique reference point whose
distance from the source serves as a unit to normalize distances outside of
which the performance becomes very low.

Many DG methods minimize different divergence measures to align source
distributions in the representation space [1, 63] (see Appendix B for a review
of DG). As concrete examples, G2DM [1] and CDAN [45] learn a representation
space by minimizing the classification loss on multiple source domains and
uses one-vs-all type discrimination losses to minimize the divergence between
different source domains. Following these works, we propose a Wasserstein
Matching (WM) based algorithm which uses one-vs-all type Wasserstein distance-
based loss to minimize the divergence between the source distributions (see
Appendix B for details). The WM method performs competitively with G2DM, CDAN,
and other state-of-the-art DG methods on benchmark datasets. To compute and
optimize Wasserstein distances between distributions we follow [18] which
computes the distance cost matrix per batch and then optimizes the coupling
for that batch. One challenge with measuring distances in the representation
space is that the representation map learned by different DG methods or even
the same method for different model initialization has arbitrary scales and
therefore the distances are not directly comparable across models or methods.
To address this, we propose a distance normalization technique that uses the
distance between the source $P_{S}$ and a unique reference distribution
$P_{S_{adv}}$ as the unit length in the representation space. This
distribution $P_{S_{adv}}$ consists of points $(z^{\prime},y)$ generated
similarly to the CW-attack [59, 13]: for each $z$ from the source,
$z^{\prime}$ is the closest misclassified point ($h(z^{\prime})\neq y$). Using
this, we report all distances in this paper as the normalized distance
$\frac{W_{2}(P_{S},\cdot)}{\rho_{adv}:=W_{2}(P_{S},P_{S_{adv}})}$. The unit
distance $\rho_{adv}$ (see Fig. 2) is dependent on the learned representation
map and the classification boundary. As the adversarial distribution
$P_{S_{adv}}$ is the closest distribution whose accuracy is zero (since all
points $z^{\prime}$ are misclassified by construction), the normalized
distance of 1 provides a sense of distance from the source where the
generalization performance is expected to be low in general (and in particular
the accuracy is zero for the adversarial distribution $P_{S_{adv}}$).

Algorithm 1 Cert-DG: Certifying Domain Generalization

Input: Radius $\rho$, Representation map $g_{\theta}$, Classifier $h_{\zeta}$,
Source data $\mathcal{D}_{S}$,
$T_{1}$, $T_{2}=1$, $\alpha$, $\beta$,
$\gamma_{init},\gamma_{min},\gamma_{max}$.
Output: $l_{worst}$ (worst-case loss within a ball of radius $\rho$)

Init: $\gamma\leftarrow\gamma_{init}$,
$\mathcal{D}\leftarrow(g_{\theta}(\mathcal{X}_{S}),\mathcal{Y}_{S})$

for $m=1,\;\cdots\;,T_{1}$ do

for a batch ${(x,y)}\sim\mathcal{D}_{\mathrm{S}}$ and corresponding batch
$z\sim\mathcal{D}$ of size $n$ do

for $t=1,\cdots,T_{2}$ do

for $i=1,\cdots,n$ do

$\phi_{\gamma}\leftarrow\ell(h_{\zeta}(z^{i}),y^{i})-\gamma\|z^{i}-g_{\theta}(x^{i})\|_{2}^{2}$
$\triangleright$ Compute $\phi_{\gamma}$

$z^{i}\leftarrow z^{i}+\alpha\nabla_{z}\phi_{\gamma}$ $\triangleright$ Update
$z$ and store back in $\mathcal{D}$

$\gamma\leftarrow\gamma-\beta\\{\rho^{2}-\frac{1}{n}\sum_{i=1}^{n}\|z^{i}-g_{\theta}(x^{i})\|_{2}^{2}\\}$
$\triangleright$ Update $\gamma$ using the gradient

$\gamma\leftarrow\mathrm{Clip}(\gamma,\gamma_{min},\gamma_{max})$$\triangleright$
Clip the value of $\gamma$

$\ell_{worst}\leftarrow\\{\gamma\rho^{2}+\frac{1}{N}\sum_{(x,y)\sim\mathcal{D}_{S},z\sim\mathcal{D}}[\phi_{\gamma}((x,y,z))]\\}$
$\triangleright$ Return the worst-case loss in the $\rho$ ball

###  3.2 Certifying Domain Generalization

As demonstrated in Figs. 1 and 6 (in Appendix), the empirical loss of various
distributions has high variability and is not a deterministic function of the
distance to the source. Thus, to provide a data-independent measure of DG
performance, we propose to use the worst-case loss at a particular distance,
as used in distributionally robust optimization [7, 50, 21, 77, 26, 8].
Considering the space of joint distributions on $\mathcal{X}\times\mathcal{Y}$
with 2-Wasserstein distance as a metric [54] (see Fig. 2). The worst-case loss
of any distribution $P$ whose distance is at most $\rho$ from source
distribution $Q$ is then

$\sup_{P:W_{2}(P,Q)\leq\rho}\;\mathbb{E}_{(x,y)\sim P}[\ell(h(g(x)),y)].$ (1)

This (primal) optimization problem is an infinite-dimensional problem over a
convex set $P$, which makes it difficult to solve it directly, in general.
However, the optimal value can be computed through a finite-dimensional
optimization problem through the following equality

$\sup_{P:W_{2}(P,Q)\leq\rho}\mathbb{E}_{P}[\ell(h(g(x)),y)]=\inf_{\gamma\geq
0}\\{\gamma\rho^{2}+\mathbb{E}_{(x_{0},y_{0})\sim
Q}[\phi_{\gamma}(x_{0},y_{0})]\\},\;\;\mathrm{where}$ (2)
$\phi_{\gamma}(x_{0},y_{0}):=\sup_{x\in\mathcal{X}}\;\\{\ell(h(g(x)),y_{0})-\gamma
c((g(x_{0}),y_{0}),(g(x),y_{0}))\\}$ (3)

is the Moreau envelope or the surrogate function [62, 67]. The equality in Eq.
2 is called the strong duality and is proven under different assumptions on
$c$, $\ell$ and whether the nominal distribution $Q$ is continuous, empirical
($\frac{1}{N}\sum_{i}\delta(z-z_{i})$, where $N$ denotes number of points in
the empirical distribution) or both [26, 62, 50, 77, 10]. To certify the data-
independent worst-case loss of any DG method, we solve Eq. 2 using the
algorithm presented in Alg. 1 called Cert-DG. The proposed algorithm is
different from existing works in the following ways. [62, 67] proposed to
solve the Lagrangian relaxed penalized version while we solve the non-relaxed
problem by minimizing over the dual variable $\gamma$ (Eq. 2) as well as
computing the surrogate loss (Eq. 3). More importantly, since DG methods align
the distributions in the representation space (one layer before the
logit/softmax layer [1, 45]), we solve Eq. 2 directly in this space using the
following surrogate loss

$\phi_{\gamma}(z_{0},y_{0}):=\sup_{z\in\mathcal{Z}}\;\\{\ell(Wz+b,y_{0})-\gamma\|z-z_{0}\|_{2}^{2}\\}.$
(4)

Since the maximization is in the representation space (see Appendix C for a
discussion on input space vs representation space), we do not require
assumptions such as Lipschitzness of $\nabla_{z}\ell(z;\theta)$ and
$\nabla_{\theta}\ell(z;\theta)$, as made in [62], which are prohibitive for
the certification of deep neural nets (and can be NP-hard with ReLU networks,
as shown in [62]). For Eq. 4 to have a finite optimal value that is also
computationally easy to find, we do not necessarily require differentiability
or even continuity of $\ell$ [26]. This allows us to use various types of
losses such as cross-entropy, hinge, and 0/1-loss. To solve Eq. 4, we propose
to use SGD for cross-entropy and modified hinge loss. For 0/1-loss the
surrogate loss is given in the closed-form (see Appendix C.1 for the details
for different losses). For these losses, the problem in Eq. 2 is a saddle
point problem that is convex in the scalar $\gamma$ and is strongly concave in
$z$ (for hinge loss and for cross-entropy loss with $\gamma>\gamma_{0}$, for
some $\gamma_{0}$). Thus, the problem can be solved efficiently by alternating
SGD as proposed in Alg. 1. For example, certifying a model in the experiments
at a distance $\rho$ using a sample of 1000 points takes only about a minute
on a GPU enabled machine. Thus, we propose a _computationally efficient method
of certifying the worst-case loss of any deep NN-based DG method at an
arbitrary distance $\rho$ in the representation space, that is compatible with
different types of loss functions._

Algorithm 2 DR-DG: Distributionally-Robust Domain Generalization

Input: $F$, $T_{1}$, $T_{2}$, $\alpha$, $\beta$, $\eta$,
$\gamma_{init},\gamma_{min},\gamma_{max}$,
$\mathcal{D}_{S}=\\{\mathcal{D}_{S}^{j}\\}_{j=1}^{N_{S}}$,
$\mathcal{D}_{S}^{j}=\\{(x^{j}_{i},y^{j}_{i})\\}_{i=1}^{N_{S}^{j}}$,
$\ell_{dg}$
Output: Representation model parameters $\theta$, Classifier parameters
$\zeta$.

Init: Initialize parameters of the representation $g_{\theta}$ and
classification $h_{\zeta}$ models.

Init: $\gamma\leftarrow\gamma_{init}$, $\mathcal{D}\leftarrow
g_{\theta}(\mathcal{X}_{S})$

for $m=1,\;\cdots\;,T_{1}$ do

$\mathcal{D}_{adv}\leftarrow\mathrm{GenAdvDist}(\mathcal{D}_{S},g_{\theta},h_{\zeta})$
$\triangleright$ Generate adversarial distribution via CW-attack [13]

$\rho\leftarrow$F$\cdot
W_{2}(\mathcal{D}_{adv},(g_{\theta}(\mathcal{X}_{S}),\mathcal{Y}_{S}))$
$\triangleright$ Initialize the ball size $\rho$

for a batch ${(x,y)}\sim\mathcal{D}_{\mathrm{S}}$ and corresponding batch
$z\sim\mathcal{D}$ of size $n$ do

for $t=1,\cdots,T_{2}$ do

for $i=1,\cdots,n$ do

$\phi_{\gamma}\leftarrow\ell(h_{\zeta}(z^{i}),y^{i})-\gamma\|z^{i}-g_{\theta}(x^{i})\|_{2}^{2}$
$\triangleright$ Compute $\phi_{\gamma}$

$z^{i}\leftarrow z^{i}+\alpha\nabla_{z}\phi_{\gamma}$ $\triangleright$ Update
and store $z$

$\gamma\leftarrow\gamma-\beta\\{\rho^{2}-\frac{1}{n}\sum_{i=1}^{n}\|z^{i}-g_{\theta}(x^{i})\|_{2}^{2}\\}$
$\triangleright$ Update $\gamma$ using the gradient

$\gamma\leftarrow\mathrm{Clip}(\gamma,\gamma_{min},\gamma_{max})$$\triangleright$
Clip the value of $\gamma$

$\ell_{dro}\leftarrow\frac{1}{n}\sum_{i=1}^{n}\ell(h_{\zeta}(z^{i}),y^{i})$
$\triangleright$ Loss on the worst-case distribution in $\rho$-ball

$\ell_{total}\leftarrow\ell_{dro}+\ell_{dg}$ $\triangleright$ $\ell_{dg}$ is
the loss of a given DG method.

$\theta\leftarrow\theta-\eta\nabla_{\theta}\ell_{total}$ $\triangleright$
Update Representation model params

$\zeta\leftarrow\zeta-\eta\nabla_{\zeta}\ell_{total}$ $\triangleright$ Update
Classification model params

###  3.3 Improving Domain Generalization with DRO

The results of using our certification (see Fig. 3 and Figs. 7, 8 in the
Appendix) on models trained with Vanilla DG methods show a large gap between
the worst-case performance and performance on benchmark tasks. This gap exists
since the vanilla models are not optimized to learn a representation space
where the loss of the worst-case distribution is small at any given distance
from the sources. Thus, to improve the worst-case performance of a given DG
algorithm, we propose to perform distributionally-robust model training
($\min_{\zeta,\theta,\gamma\geq
0}\\{\gamma\rho^{2}+\mathbb{E}_{Q}[\phi_{\gamma}]\\}$) in addition to
minimizing losses of specific DG algorithm. Our algorithm takes the losses of
specific DG algorithms as input and optimizes those along with the DRO loss.
Our proposed algorithm, DR-DG, is presented in Alg. 2. Similar to Cert-DG, DR-
DG can be used in conjunction with any existing DG method to improve their
worst-case loss at various distances. DR-DG improves the worst-case loss by
alternating between two steps. In the first step, we generate the data which
approximates the loss the worst-case distribution by solving the dual problem
in Eq. 2 over a mini-batch. The size of the Wasserstein ball $\rho$ is
computed relative to the distance to the adversarial distribution $\rho_{adv}$
(see Fig. 2) i.e. $\rho=F\cdot\rho_{adv}$, where $F$ is a factor specified as
an input parameter. In the second step, we minimize the objectives of the DG
algorithm and additionally minimize the loss of the worst-case samples
generated in the first step. In the experiments, we demonstrate that this
simple training procedure leads to a significant reduction in the worst-case
loss of the model. This makes models trained with our method certifiably more
generalizable to unseen domains than their vanilla counterparts. To run the
optimization end-to-end with SGD, the choice of loss needs to be restricted to
(a.e.) differentiable losses. However, separate from the training procedure,
the trained model can be certified with any loss (see Fig. 4). In practice,
the additional objective of generating and training on samples that
approximate the loss of the worst-case distribution only adds a small overhead
to vanilla DG training. The overall run-time increase is proportional to the
number of maximization steps executed per batch ($T_{2}$ in Alg. 2). For
$T_{2}$=20 on PACS with WM and G2DM the run-time increases by mere $\sim$3
seconds per epoch in our experiments. Lastly, while we are minimizing the
worst-case loss of the empirical distribution in practice, it also minimizes
the worst-case loss of the unknown true distribution as shown in Theorem 3
[62]:
$\sup_{P:W_{2}(P,{Q})\leq\rho}\mathbb{E}_{Q}[\ell]\leq\gamma\rho^{2}+\mathbb{E}_{\hat{Q}}[\phi_{\gamma}]+O(n^{-1/2})$
with high probability, where $\hat{Q}$ is the $n$-sample empirical training
(source) distribution of $Q$. Thus, DR-DG reduces the worst-case loss and
improves its generalization on unseen domains in a principled way.

##  4 Experiments

In this section, we present empirical evaluations of Cert-DG and DR-DG. As
mentioned in Sec. 3, we use various DG algorithms that learn a representation
space by minimizing the divergence between the source distributions during
training. In particular, we use Wasserstein matching (WM), which explicitly
reduces the Wasserstein distance between the source distributions in the
representation space (see Appendix B), G2DM [1] and CDAN [45] which use
discriminators to align the source distributions. We also present results on
another popular DG algorithm VREX [38] in the Appendix. We use benchmark
datasets Rotated MNIST (R-MNIST) [29], PACS [43] and VLCS [22]. Dataset
details are present in Appendix D. Similar to [30], we use a convolutional
neural network for R-MNIST and fine-tune a ResNet50 model pre-trained on
Imagenet for PACS and VLCS. For all our experiments, we arbitrarily chose two
domains for training ($0^{\circ}$ and $15^{\circ}$ for R-MNIST, Cartoon and
Sketch for PACS, Caltech101 and SUN09 for VLCS), while reserving others for
various evaluations. We used the Python OT library [23] to measure Wasserstein
distances. As described in Sec. 3, we use the $W_{2}$ Wasserstein distance in
our work. During the training of WM, we use batch-wise computation of
Wasserstein distance similar to [18]. To be able to compare the distances
across different representation spaces, as shown in Sec. 3, we normalize the
distance by the distance between the source and its adversarial distribution
in the representation space. The distance computation and Alg. 2 rely on the
computation of the adversarial distribution. We use the Cleverhans [53]
implementation of the CW attack [14] in the representation space for computing
this distribution. Additional results on Cert-DG and DR-DG are in Appendix A
along with experimental details in Appendix D. Our codes are available at
https://github.com/akshaymehra24/CertifiableDG.

###  4.1 Performance of DG algorithms on unseen distributions

To understand how the accuracy of the models trained with DG methods changes
on the unseen domains in relation to the distance of the unseen domains in the
representation space, we evaluate the models on several benchmark and
synthetic domains. For models trained with R-MNIST, we use,
$30^{\circ},45^{\circ},60^{\circ},75^{\circ}$ as unseen domains, and for
models trained with PACS, we use Art and Photo as unseen domains. We generate
additional unseen target domains by adding natural corruptions [32, 52] to
test data of the source domains. For R-MNIST we use corruptions from MNIST-C
[52] and for PACS we used corruptions from Imagenet-C [33] (see Appendix D.3).
We chose to use common corruptions to create the unseen domains since they
resemble some of the variations that may be encountered at test time. We
control the severity level to create a number of unseen domains whose distance
changes with severity. As observed in Fig 1 and 6, accuracy of DG methods on
distributions lying at similar distances in the representation space from the
source has high variability. In particular, the smaller-range plots show that
the accuracy of these models varies by about 5-7% on different unseen domains.
This variability in the accuracy is not only observed for corrupted
distributions but also on benchmark distributions, where the distributions of
Art and Photo lie at a similar distance to the sources in the representation
space but have about 15% performance variation. Moreover, the results also
highlight the limitation of evaluating DG methods only on benchmark datasets
since the performance of the models on these datasets is not representative of
the model’s performance on unseen domains. In particular, the high performance
on Photos domain in Fig 1, does not imply that the model’s performance on
other domains at that distance will also be high. Lastly, across algorithms
performance of models can be different in different domains. For instance on
R-MNIST (Fig. 6 in Appendix), WM is good on scaling compared to all other
methods but performs worse on shot noise. These differences in the performance
of the models trained with DG methods make it difficult to assess the
generalization of these models to unseen domains by only empirical evaluation
and motivates the need for a principled certification framework for DG.

###  4.2 Certifying the worst-case loss of models trained with DG methods

In this section, we use Cert-DG, Alg. 1, to compute the worst-case loss of the
DG methods at different distances from the source distribution in the
representation space. As seen in Fig. 3, the high worst-case loss, even close
to the source, indicates the existence of distributions that can potentially
lead to a drastically different performance than that expected from the
evaluation on benchmark datasets.

Figure 3: Comparison of certified loss (Cross-entropy (left) and modified
hinge loss (right)) and empirical loss on corrupted and adversarial domains of
a model trained with WM on R-MNIST. The large gap between the certified and
empirical losses indicates the insufficiency of evaluation of DG methods on a
few unseen domains to guarantee generalization on other domains.

In addition to corrupted domains, we also plot adversarial domains, in Fig. 3,
crafted by PGD [46] attacks in the input as well as the representation space
(see Appendix D.4). The large gap between the certified loss and the empirical
loss indicates the existence of distributions beyond corruptions and
adversarial examples, which could degrade the performance of the models. Since
the worst-case distribution computed by Cert-DG can contain points distorted
by different amounts, its loss can be higher than the loss incurred by a PGD
attack which constrains the distortion of every point to be the same [46, 40].
This highlights that Cert-DG considers a more general worst-case distribution
than the adversarial distribution with a fixed perturbation budget. As shown
in Sec. 3, our certification framework is compatible with various loss
functions. Here we demonstrate the certification performance of DG methods
with the cross-entropy and modified hinge loss. As seen from Fig. 3, the
certification produces similar results when using different loss functions
although we found that the modified hinge loss makes the inner maximization
better behaved (see Appendix C.1).

###  4.3 Certifying the worst-case loss of models trained with DR-DG

Figure 4: (Best viewed in color.) Improvement in the worst-case loss
(certified loss) with models trained with DR-DG and cross-entropy loss with a
$F$ = 0.5 using WM on R-MNIST. Compared to results in Fig. 3, DR-DG has
significantly reduced the variability in the loss of different unseen
distributions as well as reduced the worst-case loss. The red dotted line
denotes the certified worst-case loss of the model trained with WM without DR-
DG (as shown in Fig. 3 and has been shown for reference.

The large gap between the certified worst-case and empirical loss of the
models trained with DG methods indicates that their performance can have high
variability even on distributions lying at similar distances in the
representation space. DR-DG Alg. 2, is proposed to improve the worst-case
performance by training on examples drawn from the worst-case distributions
lying at different distances in the representation space. DR-DG requires a $F$
which is used to determine the radius $\rho$ of the Wasserstein ball around
the source distributions. DRO training aims to improve the loss on the worst-
case distributions lying in this ball of radius $\rho$. The larger the $F$,
the larger will be the radius $\rho$ of the ball that will be considered for
finding the worst-case distributions. Similar to point-wise adversarial
robustness procedures such as adversarial training [46] or randomized
smoothing [15], DR-DG with larger values of $\rho$ can improve the worst-case
loss but can lead to a reduction in the performance of the model near the
source distributions. Thus, there exists a trade-off between lowering the
worst-case loss at a larger distance versus maintaining the low loss near the
source(s). To demonstrate this trade-off we use three different values of $F$.
The results in Fig. 5 demonstrate that models trained with DR-DG achieve
significantly better worst-case loss in comparison to the models trained with
vanilla DG methods with only a minor increase in the loss on the source
distribution(s). Moreover, compared to the results in Fig. 3, we observe that
in Fig. 4 DR-DG has 1) significantly reduced the variability in the
performance of the models across various unseen distributions and 2) lowered
the loss of the worst-case distribution at most distances. This demonstrates
that DR-DG has improved the generalization of DG methods to unseen domains. We
observe similar results on other benchmark datasets and algorithms and present
those in Fig. 7, 8 in the Appendix.

###  4.4 Performance of models trained with DR-DG on benchmark datasets

In this section, we evaluate the performance of models trained with DR-DG,
Alg. 2, on various target distributions used for comparing the performance of
DG methods in previous works. As demonstrated in Table 1, our algorithm
improves the certified loss of the models for all benchmark distributions.
This reduces the gap between the empirical loss of the model on a particular
unseen distribution and the worst-case distribution at that distance (from the
sources). The reduced gap not only leads to a provably reduced variability in
the performance of the model on target distributions lying at that distance
but also makes evaluation on benchmark datasets more representative of the
generalization of the models to unseen distributions. However, as discussed in
the previous section, gaining robustness to the worst-case distributions may
lead to a decrease in the performance of the model on sources as well as on
some unseen domains. This is similar to the accuracy vs robustness trade-off
observed in point-wise adversarial robustness literature. Recent research in
that area has shown that it is possible to maintain the accuracy of the model
and gain robustness by using different loss functions [75] and modifying the
training procedure. While this is an interesting direction, we leave the use
of different techniques for keeping the performance of DG methods on sources
and benchmark targets for future work.

(a) WM with R-MNIST (b) G2DM with R-MNIST (c) WM with PACS (d) G2DM with PACS

Figure 5: (Best viewed in color.) DR-DG proposed in Alg. 2 significantly
reduces the worst-case loss of the models trained with DG methods on different
datasets. The reduced worst-case loss provably improves the generalization of
the models to unseen distributions in comparison to models trained without DR-
DG.  Table 1: DR-DG trained models on two source domains from R-MNIST
($F_{1}=0.5,F_{2}=1,F_{3}=1.5$) and PACS ($F_{1}=0.25,F_{2}=0.5,F_{3}=0.75$),
incur small worst-case (certified) loss. DR-DG also helps reduce the gap
between the empirical loss of the models on unseen domains in these datasets
and the worst-case loss. This makes the performance of DG models on benchmark
datasets more representative of their performance on unseen domains lying at a
similar distance.

| $30^{\circ}$ | $45^{\circ}$ | Art | Photo
---|---|---|---|---
Method | Accuracy | Loss |  Certified Loss | Gap | Accuracy | Loss |  Certified Loss | Gap | Accuracy | Loss |  Certified Loss | Gap | Accuracy | Loss |  Certified Loss | Gap
WM | 92.11 | 0.26 | 1.87 | 1.61 | 65.59 | 1.21 | 3.76 | 2.55 | 73.24 | 0.82 | 2.63 | 1.82 | 91.55 | 0.35 | 2.14 | 1.79
DR-DG${}_{F_{1}}$ | 89.61 | 0.38 | 0.85 | 0.47 | 61.12 | 1.24 | 2.02 | 0.82 | 71.48 | 0.92 | 2.21 | 1.29 | 85.93 | 0.49 | 1.87 | 1.39
DR-DG${}_{F_{2}}$ | 88.25 | 0.52 | 0.80 | 0.28 | 54.26 | 1.36 | 1.78 | 0.44 | 69.58 | 1.01 | 2.12 | 1.11 | 87.12 | 0.52 | 1.60 | 1.08
DR-DG${}_{F_{3}}$ | 86.90 | 0.61 | 0.87 | 0.26 | 54.46 | 1.41 | 1.77 | 0.36 | 74.23 | 0.88 | 1.53 | 0.64 | 89.41 | 0.48 | 1.27 | 0.79
G2DM | 93.86 | 0.24 | 4.54 | 4.29 | 70.58 | 1.25 | 7.21 | 5.97 | 75.68 | 1.16 | 11.57 | 10.41 | 89.64 | 0.45 | 11.23 | 10.78
DR-DG${}_{F_{1}}$ | 93.24 | 0.23 | 3.27 | 2.99 | 69.23 | 1.14 | 5.34 | 4.20 | 69.14 | 1.19 | 9.61 | 8.42 | 84.43 | 0.58 | 9.51 | 8.93
DR-DG${}_{F_{2}}$ | 90.43 | 0.31 | 2.24 | 1.93 | 63.72 | 1.24 | 4.06 | 2.82 | 67.23 | 1.32 | 9.59 | 8.23 | 89.40 | 0.41 | 9.45 | 9.05
DR-DG${}_{F_{3}}$ | 87.94 | 0.39 | 1.48 | 1.08 | 60.08 | 1.25 | 2.84 | 1.58 | 70.65 | 1.05 | 8.26 | 7.22 | 85.74 | 0.50 | 8.29 | 7.78

##  5 Conclusion

Domain generalization aims to produce models whose performance remains high
even on data from domains unseen during training. However, the current
evaluation of these methods using a few benchmark datasets is a poor indicator
of their generalization to data from unseen domains. To make the evaluation of
DG reliable, we proposed a novel target-independent certification framework
that allows us to evaluate the worst-case performance of any DG method based
on the distance in the representation space. To reduce the large gap between
the certified loss and the empirical loss incurred by DG methods on different
benchmark distributions we proposed a novel training algorithm based on DRO
that can provably improve the worst-case loss of any DG method. Based on our
results, we believe that evaluation of DG methods via a target-independent
metric such as the worst-case loss at a given distance could provide
additional insights beyond empirical evaluation on benchmark datasets. Thus,
allowing us to objectively judge the progress made towards learning models
whose performance does not degrade when faced with data from domains unseen
during training.

## Acknowledgement

This work was supported by the NSF EPSCoR-Louisiana Materials Design Alliance
(LAMDA) program #OIA-1946231 and by the LLNL-LDRD Program under Project No.
20-ERD-014. This work was performed under the auspices of the U.S. Department
of Energy by Lawrence Livermore National Laboratory under Contract DE-
AC52-07NA27344.

## References

  * [1] Isabela Albuquerque, João Monteiro, Mohammad Darvishi, Tiago H Falk, and Ioannis Mitliagkas.  Generalizing to unseen domains via distribution matching.  arXiv preprint arXiv:1911.00804, 2019.
  * [2] David Alvarez-Melis and Nicolo Fusi.  Geometric dataset distances via optimal transport.  arXiv preprint arXiv:2002.02923, 2020.
  * [3] Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz.  Invariant risk minimization.  arXiv preprint arXiv:1907.02893, 2019.
  * [4] Martin Arjovsky, Soumith Chintala, and Léon Bottou.  Wasserstein generative adversarial networks.  In International conference on machine learning, pages 214–223. PMLR, 2017.
  * [5] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan.  A theory of learning from different domains.  Machine learning, 79(1):151–175, 2010.
  * [6] Shai Ben-David, John Blitzer, Koby Crammer, Fernando Pereira, et al.  Analysis of representations for domain adaptation.  Advances in neural information processing systems, 19:137, 2007\.
  * [7] 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.
  * [8] Dimitris Bertsimas, Vishal Gupta, and Nathan Kallus.  Data-driven robust optimization.  Mathematical Programming, 167(2):235–292, 2018.
  * [9] Gilles Blanchard, Gyemin Lee, and Clayton Scott.  Generalizing from several related classification tasks to a new unlabeled sample.  Advances in neural information processing systems, 24:2178–2186, 2011.
  * [10] Jose Blanchet and Karthyek Murthy.  Quantifying distributional model risk via optimal transport.  Mathematics of Operations Research, 44(2):565–600, 2019.
  * [11] Saikiran Bulusu, Bhavya Kailkhura, Bo Li, Pramod K Varshney, and Dawn Song.  Anomalous example detection in deep learning: A survey.  IEEE Access, 8:132330–132347, 2020.
  * [12] Dan A Calian, Florian Stimberg, Olivia Wiles, Sylvestre-Alvise Rebuffi, Andras Gyorgy, Timothy Mann, and Sven Gowal.  Defending against image corruptions through adversarial augmentations.  arXiv preprint arXiv:2104.01086, 2021.
  * [13] Nicholas Carlini and David Wagner.  Adversarial examples are not easily detected: Bypassing ten detection methods.  In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 3–14, 2017.
  * [14] Nicholas Carlini and David Wagner.  Towards evaluating the robustness of neural networks.  In 2017 ieee symposium on security and privacy (sp), pages 39–57. IEEE, 2017.
  * [15] Jeremy M Cohen, Elan Rosenfeld, and J Zico Kolter.  Certified adversarial robustness via randomized smoothing.  arXiv preprint arXiv:1902.02918, 2019.
  * [16] Zac Cranko, Zhan Shi, Xinhua Zhang, Richard Nock, and Simon Kornblith.  Generalised lipschitz regularisation equals distributional robustness.  In International Conference on Machine Learning, pages 2178–2188. PMLR, 2021.
  * [17] Marco Cuturi.  Sinkhorn distances: Lightspeed computation of optimal transport.  Advances in neural information processing systems, 26, 2013.
  * [18] Bharath Bhushan Damodaran, Benjamin Kellenberger, Rémi Flamary, Devis Tuia, and Nicolas Courty.  Deepjdot: Deep joint distribution optimal transport for unsupervised domain adaptation.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 447–463, 2018.
  * [19] James Diffenderfer, Brian Bartoldson, Shreya Chaganti, Jize Zhang, and Bhavya Kailkhura.  A winning hand: Compressing deep networks can improve out-of-distribution robustness.  Advances in Neural Information Processing Systems, 34, 2021.
  * [20] Andrea Dittadi, Frederik Träuble, Francesco Locatello, Manuel Wüthrich, Vaibhav Agrawal, Ole Winther, Stefan Bauer, and Bernhard Schölkopf.  On the transfer of disentangled representations in realistic settings.  arXiv preprint arXiv:2010.14407, 2020.
  * [21] John Duchi, Peter Glynn, and Hongseok Namkoong.  Statistics of robust optimization: A generalized empirical likelihood approach.  arXiv preprint arXiv:1610.03425, 2016.
  * [22] Chen Fang, Ye Xu, and Daniel N Rockmore.  Unbiased metric learning: On the utilization of multiple datasets and web images for softening bias.  In Proceedings of the IEEE International Conference on Computer Vision, pages 1657–1664, 2013.
  * [23] Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, Ievgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer.  Pot: Python optimal transport.  Journal of Machine Learning Research, 22(78):1–8, 2021.
  * [24] Yaroslav Ganin and Victor Lempitsky.  Unsupervised domain adaptation by backpropagation.  In International conference on machine learning, pages 1180–1189. PMLR, 2015.
  * [25] Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky.  Domain-adversarial training of neural networks.  The journal of machine learning research, 17(1):2096–2030, 2016\.
  * [26] Rui Gao and Anton J Kleywegt.  Distributionally robust stochastic optimization with wasserstein distance.  arXiv preprint arXiv:1604.02199, 2016.
  * [27] Aude Genevay, Marco Cuturi, Gabriel Peyré, and Francis Bach.  Stochastic optimization for large-scale optimal transport.  Advances in neural information processing systems, 29, 2016.
  * [28] Aude Genevay, Gabriel Peyré, and Marco Cuturi.  Learning generative models with sinkhorn divergences.  In International Conference on Artificial Intelligence and Statistics, pages 1608–1617. PMLR, 2018.
  * [29] Muhammad Ghifary, W Bastiaan Kleijn, Mengjie Zhang, and David Balduzzi.  Domain generalization for object recognition with multi-task autoencoders.  In Proceedings of the IEEE international conference on computer vision, pages 2551–2559, 2015.
  * [30] Ishaan Gulrajani and David Lopez-Paz.  In search of lost domain generalization.  arXiv preprint arXiv:2007.01434, 2020.
  * [31] 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.
  * [32] Dan Hendrycks and Thomas Dietterich.  Benchmarking neural network robustness to common corruptions and perturbations.  arXiv preprint arXiv:1903.12261, 2019.
  * [33] Dan Hendrycks and Thomas G Dietterich.  Benchmarking neural network robustness to common corruptions and surface variations.  arXiv preprint arXiv:1807.01697, 2018.
  * [34] Dan Hendrycks, Norman Mu, Ekin D Cubuk, Barret Zoph, Justin Gilmer, and Balaji Lakshminarayanan.  Augmix: A simple data processing method to improve robustness and uncertainty.  arXiv preprint arXiv:1912.02781, 2019.
  * [35] Weihua Hu, Gang Niu, Issei Sato, and Masashi Sugiyama.  Does distributionally robust supervised learning give robust classifiers?  In International Conference on Machine Learning, pages 2029–2037. PMLR, 2018.
  * [36] Fredrik D Johansson, David Sontag, and Rajesh Ranganath.  Support and invertibility in domain-invariant representations.  In The 22nd International Conference on Artificial Intelligence and Statistics, pages 527–536. PMLR, 2019.
  * [37] Klim Kireev, Maksym Andriushchenko, and Nicolas Flammarion.  On the effectiveness of adversarial training against common corruptions.  arXiv preprint arXiv:2103.02325, 2021.
  * [38] David Krueger, Ethan Caballero, Joern-Henrik Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang, Remi Le Priol, and Aaron Courville.  Out-of-distribution generalization via risk extrapolation (rex).  In International Conference on Machine Learning, pages 5815–5826. PMLR, 2021.
  * [39] 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.
  * [40] Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi.  Certifying model accuracy under distribution shifts.  arXiv preprint arXiv:2201.12440, 2022.
  * [41] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana.  Certified robustness to adversarial examples with differential privacy.  In 2019 IEEE Symposium on Security and Privacy (SP), pages 656–672. IEEE, 2019.
  * [42] Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin.  Certified adversarial robustness with additive noise.  In Advances in Neural Information Processing Systems, pages 9464–9474, 2019.
  * [43] Da Li, Yongxin Yang, Yi-Zhe Song, and Timothy M Hospedales.  Deeper, broader and artier domain generalization.  In Proceedings of the IEEE international conference on computer vision, pages 5542–5550, 2017.
  * [44] Ya Li, Xinmei Tian, Mingming Gong, Yajing Liu, Tongliang Liu, Kun Zhang, and Dacheng Tao.  Deep domain generalization via conditional invariant adversarial networks.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 624–639, 2018.
  * [45] Mingsheng Long, Zhangjie Cao, Jianmin Wang, and Michael I Jordan.  Conditional adversarial domain adaptation.  Advances in neural information processing systems, 31, 2018.
  * [46] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  arXiv preprint arXiv:1706.06083, 2017.
  * [47] Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh.  Domain adaptation: Learning bounds and algorithms.  arXiv preprint arXiv:0902.3430, 2009.
  * [48] Akshay Mehra, Bhavya Kailkhura, Pin-Yu Chen, and Jihun Hamm.  How robust are randomized smoothing based defenses to data poisoning?  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 13244–13253, 2021.
  * [49] Akshay Mehra, Bhavya Kailkhura, Pin-Yu Chen, and Jihun Hamm.  Understanding the limits of unsupervised domain adaptation via data poisoning.  In Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
  * [50] Peyman Mohajerin Esfahani and Daniel Kuhn.  Data-driven distributionally robust optimization using the wasserstein metric: Performance guarantees and tractable reformulations.  Mathematical Programming, 171(1):115–166, 2018.
  * [51] Milton Llera Montero, Casimir JH Ludwig, Rui Ponte Costa, Gaurav Malhotra, and Jeffrey Bowers.  The role of disentanglement in generalisation.  In International Conference on Learning Representations, 2020.
  * [52] Norman Mu and Justin Gilmer.  Mnist-c: A robustness benchmark for computer vision.  arXiv preprint arXiv:1906.02337, 2019.
  * [53] Nicolas Papernot, Fartash Faghri, Nicholas Carlini, Ian Goodfellow, Reuben Feinman, Alexey Kurakin, Cihang Xie, Yash Sharma, Tom Brown, Aurko Roy, Alexander Matyasko, Vahid Behzadan, Karen Hambardzumyan, Zhishuai Zhang, Yi-Lin Juang, Zhi Li, Ryan Sheatsley, Abhibhav Garg, Jonathan Uesato, Willi Gierke, Yinpeng Dong, David Berthelot, Paul Hendricks, Jonas Rauber, and Rujun Long.  Technical report on the cleverhans v2.1.0 adversarial examples library.  arXiv preprint arXiv:1610.00768, 2018.
  * [54] Gabriel Peyré, Marco Cuturi, et al.  Computational optimal transport: With applications to data science.  Foundations and Trends® in Machine Learning, 11(5-6):355–607, 2019.
  * [55] Fengchun Qiao, Long Zhao, and Xi Peng.  Learning to learn single domain generalization.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12556–12565, 2020.
  * [56] Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang.  Semidefinite relaxations for certifying robustness to adversarial examples.  In Advances in Neural Information Processing Systems, pages 10877–10887, 2018.
  * [57] Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang.  Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization.  arXiv preprint arXiv:1911.08731, 2019.
  * [58] Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang.  Provably robust deep learning via adversarially trained smoothed classifiers.  In Advances in Neural Information Processing Systems, pages 11292–11303, 2019.
  * [59] Vikash Sehwag, Saeed Mahloujifar, Tinashe Handina, Sihui Dai, Chong Xiang, Mung Chiang, and Prateek Mittal.  Robust learning meets generative models: Can proxy distributions improve adversarial robustness?  arXiv preprint arXiv:2104.09425, 2021.
  * [60] Soroosh Shafieezadeh-Abadeh, Daniel Kuhn, and Peyman Mohajerin Esfahani.  Regularization via mass transportation.  Journal of Machine Learning Research, 20(103):1–68, 2019.
  * [61] Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu.  Wasserstein distance guided representation learning for domain adaptation.  In Thirty-Second AAAI Conference on Artificial Intelligence, 2018\.
  * [62] Aman Sinha, Hongseok Namkoong, Riccardo Volpi, and John Duchi.  Certifying some distributional robustness with principled adversarial training.  arXiv preprint arXiv:1710.10571, 2017.
  * [63] Matthew Staib and Stefanie Jegelka.  Distributionally robust optimization and generalization in kernel methods.  Advances in Neural Information Processing Systems, 32, 2019.
  * [64] Jiachen Sun, Akshay Mehra, Bhavya Kailkhura, Pin-Yu Chen, Dan Hendrycks, Jihun Hamm, and Z Morley Mao.  Certified adversarial defenses meet out-of-distribution corruptions: Benchmarking robustness and simple baselines.  arXiv preprint arXiv:2112.00659, 2021.
  * [65] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  arXiv preprint arXiv:1312.6199, 2013.
  * [66] Cédric Villani.  Optimal transport: old and new, volume 338.  Springer, 2009.
  * [67] Riccardo Volpi, Hongseok Namkoong, Ozan Sener, John C Duchi, Vittorio Murino, and Silvio Savarese.  Generalizing to unseen domains via adversarial data augmentation.  Advances in neural information processing systems, 31, 2018.
  * [68] Haotao Wang, Chaowei Xiao, Jean Kossaifi, Zhiding Yu, Anima Anandkumar, and Zhangyang Wang.  Augmax: Adversarial composition of random augmentations for robust training.  Advances in Neural Information Processing Systems, 34, 2021.
  * [69] Jindong Wang, Cuiling Lan, Chang Liu, Yidong Ouyang, Wenjun Zeng, and Tao Qin.  Generalizing to unseen domains: A survey on domain generalization.  arXiv preprint arXiv:2103.03097, 2021.
  * [70] Maurice Weber, Linyi Li, Boxin Wang, Zhikuan Zhao, Bo Li, and Ce Zhang.  Certifying out-of-domain generalization for blackbox functions.  arXiv preprint arXiv:2202.01679, 2022.
  * [71] Eric Wong and Zico Kolter.  Provable defenses against adversarial examples via the convex outer adversarial polytope.  In International Conference on Machine Learning, pages 5286–5295. PMLR, 2018.
  * [72] Runtian Zhai, Chen Dan, Di He, Huan Zhang, Boqing Gong, Pradeep Ravikumar, Cho-Jui Hsieh, and Liwei Wang.  Macer: Attack-free and scalable robust training via maximizing certified radius.  arXiv preprint arXiv:2001.02378, 2020.
  * [73] Guojun Zhang, Han Zhao, Yaoliang Yu, and Pascal Poupart.  Quantifying and improving transferability in domain generalization.  arXiv preprint arXiv:2106.03632, 2021.
  * [74] Hanlin Zhang, Yi-Fan Zhang, Weiyang Liu, Adrian Weller, Bernhard Schölkopf, and Eric P Xing.  Towards principled disentanglement for domain generalization.  arXiv preprint arXiv:2111.13839, 2021.
  * [75] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan.  Theoretically principled trade-off between robustness and accuracy.  In International Conference on Machine Learning, pages 7472–7482. PMLR, 2019.
  * [76] Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael Jordan.  Bridging theory and algorithm for domain adaptation.  In International Conference on Machine Learning, pages 7404–7413. PMLR, 2019.
  * [77] Chaoyue Zhao and Yongpei Guan.  Data-driven risk-averse stochastic optimization with wasserstein metric.  Operations Research Letters, 46(2):262–267, 2018.
  * [78] Han Zhao, Remi Tachet Des Combes, Kun Zhang, and Geoffrey Gordon.  On learning invariant representations for domain adaptation.  In International Conference on Machine Learning, pages 7523–7532. PMLR, 2019.
  * [79] Han Zhao, Shanghang Zhang, Guanhang Wu, José MF Moura, Joao P Costeira, and Geoffrey J Gordon.  Adversarial multiple source domain adaptation.  Advances in neural information processing systems, 31, 2018.

Appendix

We present additional evaluation results of Cert-DG and DR-DG in Appendix A,
followed by details of our experiments and model architectures in Appendix D.
We also provide a brief review of various DG algorithms used in our paper
along with existing analyses of the DG problem in Appendix B. Lastly, we
discuss certification using different loss functions and the difference
between input-space and representation-space certification in Appendix C.

##  Appendix A Additional experimental results

###  A.1 Variability in the performance of models trained with various DG
methods

As discussed in the introduction and Sec. 4.1, models trained with different
DG methods can have high variability in their performance. Surprisingly, this
variability happens even on distributions at the same distance from the
sources in the representation space. In addition to Fig. 1, Fig. 6
demonstrates this variability on models trained with WM, G2DM, CDAN [45], and
VREX [38] on the R-MNIST dataset. The variability in the performance of models
on unseen distributions lying at the same distance from the sources in the
representation space, makes it hard to evaluate the generalization performance
of models trained with DG methods using only a few benchmark datasets.

###  A.2 Additional results of Cert-DG and DR-DG on CDAN and VREX

Similar to Fig. 5, we demonstrate the effect of using different $F$ values for
DR-DG training on other popular DG methods, namely, CDAN [45] and VREX [38] on
R-MNIST, PACS and VLCS in Fig. 9. As noted in Sec. 4.3, we observe that DR-DG
training using CDAN and VREX with different $F$ values improves the worst-case
loss of models over models trained with their vanilla counterparts. Larger
values of $F$ lead to a higher decrease in the worst-case loss but can
increase the loss on the source distributions and other distributions that lie
close to the sources in the representation space. This again suggests a trade-
off between improving the worst-case loss of the models at a larger distance
from the sources at the cost of potentially increasing the loss of models on
distributions lying close to the sources.

###  A.3 Additional results of Cert-DG and DR-DG on VLCS dataset

Here, we present the results of using our certification and training method on
the VLCS [22] dataset. Last column in Fig. 9 demonstrates that models trained
on this dataset with different algorithms also achieve improved worst-case
loss when trained with DR-DG, similar to the results presented on R-MNIST and
PACS datasets in Fig. 5. For training models on this dataset, we used
Caltech101 and SUN09 as our source data. We observe that models trained with
this setting using different (vanilla) DG methods (WM, G2DM, CDAN, and VREX)
achieve comparable performance on the source test sets as well as other unseen
domains in the dataset (LabelMe and VOC2007).

###  A.4 Detailed certification results on models trained with DG methods

Here we present detailed results (Rows 1 and 3 of Figs. 7 and 8) of using our
certification method Cert-DG on models trained using WM, G2DM [1] and CDAN
[45] on R-MNIST, PACS, and VLCS datasets as presented in Sec. 4.2. Similar to
the results in Fig 3, our results in the rows 1 and 3 of Figs. 7 and 8 show
that models trained with vanilla DG methods incur high certified loss even
very close to the source. The high certified loss implies that the performance
of DG methods can vary substantially on different distributions at the same
distance and thus good performance on certain benchmark datasets is not enough
to guarantee good generalization performance of these methods on unseen
domains. Comparing different algorithms on same datasets we observe that
models trained with WM achieve comparatively smaller worst-case loss than the
models trained with G2DM, CDAN and VREX. This is due to the fact that WM,
which explicitly minimizes the Wasserstein distance between the distributions
in the representation space, is closely related to the certification procedure
which also uses the Wasserstein distance. On the other hand, G2DM and CDAN
rely on discriminators to align the two domains which minimize the divergence
between distributions but as seen in our results their performance is less
certifiable. Moreover, VREX does not explicitly consider reducing the distance
of the sources in the representation space and focuses on making the
hypothesis yield similar risk/loss on the source domains. Although the
objective of VREX is different from those of the other algorithms considered
here but we include it in our evaluation to demonstrate that our certification
procedure can be used with any DG method. A detailed empirical/theoretical
comparison of which DG algorithm works the best across the board still remains
open although we can now use our target independent certification procedure to
gain better insights into this problem rather than only relying on the
performance of these methods on a small number of unseen domains available in
benchmark datasets.

Lastly, in addition to the certified loss, we also plot loss on different
corruption of the data in Figs. 7 and 8. Similar to Fig 3, we observe that
certified loss is much higher than the loss on the corrupted versions of the
source test sets which indicates the existence of other unseen distributions
that can lower the performance of the DG models.

(a) WM (b) G2DM (c) CDAN (d) VREX

Figure 6: (Best viewed in color.) Difficulty of empirically evaluating the
generalization performance of a DG method: The difference in the performance
of DG methods on data from different unseen domains demonstrates that
comparing the performance of DG methods using a few benchmark datasets is not
sufficient for assessing the generalization performance of DG methods. The
triangles denote unseen benchmark distributions
($30^{\circ},45^{\circ},60^{\circ},75^{\circ}$ for R-MNIST (left to right))
and lines denote distributions under common corruptions.

(a) WM on R-MNIST (b) WM on PACS (c) WM on VLCS (d) DR-DG ($F$ = 0.5) with WM
on R-MNIST (e) DR-DG ($F$ = 0.75) with WM on PACS (f) DR-DG ($F$ = 0.75) with
WM on VLCS (g) G2DM on R-MNIST (h) G2DM on PACS (i) G2DM on VLCS (j) DR-DG
($F$ = 1.5) with G2DM on R-MNIST (k) DR-DG ($F$ = 0.75) with G2DM on PACS (l)
DR-DG ($F$ = 0.4) with G2DM on VLCS

Figure 7: (Best viewed in color.) Comparison of the certified (worst-case)
loss of the models trained with WM and G2DM on R-MNIST, PACS, and VLCS
dataset. Rows 1 and 3 show models trained with Vanilla DG methods and rows 2
and 4 show models trained with DR-DG using additional losses from WM and G2DM,
respectively. The models trained with DR-DG incur smaller certified loss
compared to their vanilla counterparts and only slightly higher loss on unseen
distributions created through common corruptions.

(a) R-MNIST (b) PACS (c) VLCS (d) DR-DG ($F$ = 1.5) on R-MNIST  (e) DR-DG
($F=0.5$) on PACS (f) DR-DG ($F=1.0$) on VLCS (g) R-MNIST (h) PACS (i) VLCS
(j) DR-DG ($F$ = 1.5) on R-MNIST (k) DR-DG ($F=0.3$) on PACS (l) DR-DG
($F=0.2$) on VLCS

Figure 8: (Best viewed in color.) Comparison of the certified (worst-case)
loss of the models trained with CDAN and VREX methods on R-MNIST, PACS, VLCS.
Rows 1 and 3 show models trained with Vanilla DG methods and rows 2 and 4 show
models trained with DR-DG using additional losses from CDAN and VREX. The
models trained with DR-DG incur smaller certified loss compared to their
vanilla counterparts and only slightly higher loss on unseen distributions
created through common corruptions.

###  A.5 Certification results of models trained with DR-DG

Here we present the full certification results (Rows 2 and 4 in Figs. 7 and 8)
of models trained with DR-DG. In addition to minimizing the loss on the worst-
case distribution in the representation space, we use losses of four DG
methods for DR-DG training. Specifically, we use WM, G2DM [1], CDAN [45], and
VREX [38] with DR-DG. Similar to the results presented in the main paper in
Fig. 4, we observe that the DR-DG significantly improves the worst-case loss
of the models compared to training with vanilla DG methods. Specifically, the
dotted lines, depicting the certified loss, in the rows 2 and 4 are much lower
than the dotted lines in the rows 1 and 3 of Figs. 7 and 8. This improvement
in the worst-case loss suggests that the models trained with DR-DG are more
robust to unseen domains than their vanilla counterparts. We also observe that
the gap between the certified and the empirical loss of the models is much
smaller for the models trained with WM in comparison to models trained with
G2DM, CDAN and VREX. As mentioned in the previous section, this difference is
due to the similarity certification and WM both relying on Wasserstein
distance. In comparison to G2DM and CDAN, we observe marginally better results
with using a conditional discriminator as suggested by CDAN although we found
the CDAN algorithm to be more stable when used in DR-DG.

Another important observation that makes DR-DG models better than their
vanilla counterparts is that after DR-DG training the corrupted distributions
lie closer to the source as evident from the higher density of points in
regions close to the source data. This suggests that the additional objective
of minimizing the worst-case loss helps to align the distributions closer to
the source in the representation space. Thus, helping DG methods reduce the
divergence between the source and unseen distributions. Lastly, we also note
that compared to vanilla counterparts, the performance of DR-DG trained models
is slightly worse on the source and distribution of corrupted data. As noted
in Sec. 4.4, this is similar to the accuracy versus robustness trade-off
observed in area of adversarial robustness. Efficient methodologies exist for
solving this problem specifically by using different loss functions and
gradually increasing $\rho$ for DR-DG training which will be explored in
future work.

###  A.6 Comparison of accuracy of models trained with and without DR-DG

Here, we provide a comparison of the accuracy of the models trained with DR-DG
and models trained with vanilla DG methods on distributions generated by
adding common corruptions to the test set. Fig. 12 shows that the accuracy of
DR-DG models doesn’t degrade significantly compared to models trained with
vanilla methods on these distributions. We emphasize that improving the
performance on the distributions of corrupted data is not the primary goal of
DR-DG and these results are presented for completeness.

(a) WM with R-MNIST (b) WM with PACS (c) WM with VLCS (d) G2DM with R-MNIST
(e) G2DM with PACS (f) G2DM with VLCS (g) CDAN with R-MNIST (h) CDAN with PACS
(i) CDAN with VLCS (j) VREX with R-MNIST (k) VREX with PACS (l) VREX with VLCS

Figure 9: (Best viewed in color.) Improved worst-case loss of models trained
with CDAN [45] and VREX [38] using DR-DG proposed in Alg. 2 on R-MNIST, PACS
and VLCS datasets.

##  Appendix B Review of DG algorithms and analyses

###  B.1 DG algorithms

In this section, we review the DG methods used in this work and describe their
objective functions. For detailed descriptions of these algorithms, we refer
the reader to original works.

G2DM [1]: This algorithm relies on using $N_{S}$ one-vs-all discriminators to
distinguish a source domain from other $N_{S}-1$ source domains. By learning a
representation that fools the discriminator this method aims to align the
source domains in the representation space. Mathematically, it solves the
following problem

$\min_{g,h}\max_{\tau_{1},\cdots,\tau_{N_{S}}}\;\mathcal{L}(\mathcal{D}_{S};h,g)-\sum_{k=1}^{N_{S}}\mathcal{L}_{k}(D_{k}(g(x)),y_{k}),$

where $\mathcal{L}$ denotes the average loss of a given loss $\ell$ (we used
cross-entropy loss) on all points in the the sources, $D_{k}$ denotes the
$k^{th}$ discriminator with parameters $\tau_{k}$, $y_{k}$ denotes binary
labels such that the points belonging to the $k^{th}$ source domain are
labeled as zeros and points from all other domains are labeled as ones and
$\mathcal{L}_{k}$ denotes the classification loss of the $k^{th}$
discriminator.

CDAN [45]: Similar to G2DM, this method also utilizes discriminators to align
the source distributions. The discriminators used in this approach are
conditioned to use the labels of the source domain data for alignment. The
overall mathematical objective remains the same as G2DM except for the
discriminators in G2DM are replaced by conditional discriminators which use
multi-linear conditioning (see [45] for more details). For CDAN, we used
binary discriminators which use a one-vs-all strategy similar to G2DM.

Wasserstein Matching (WM): Many previous works have demonstrated the
effectiveness of using Wasserstein distance for domain alignment, especially
in the domain adaptation literature [61, 18]. Building on that we propose to
use Wasserstein matching to reduce the divergence between the source domains
in the representation space similar to G2DM and CDAN. Mathematically, our
objective still remains the same as G2DM, except that the discriminators are
now replaced with Wasserstein distance-based terms which consider alignment in
a one-vs-all fashion. Concretely, our objective becomes

$\min_{g,h}\;\mathcal{L}(\mathcal{D}_{S};h,g)+\sum_{k=1}^{N_{S}}W_{2}^{2}(\mathcal{D}_{S}^{k},\mathcal{D}_{S}\backslash\mathcal{D}_{S}^{k}),$

where $\mathcal{D}_{S}\backslash\mathcal{D}_{S}^{k}$ denotes all source
domains except the $k^{th}$ source domain. To efficiently solve this problem
we use the methodology proposed in [18], where the coupling is computed batch-
wise using a fixed cost matrix and then this coupling is used to optimize the
cost matrix. The dissimilarity cost between points $(x,y)$ and
$(x^{\prime},y^{\prime})$ used to populate the cost matrix is computed using
the feature distance i.e. $\|g(x)-g(x^{\prime})\|_{2}^{2}$ and label distance
i.e. $\|y-y^{\prime}\|_{2}^{2}$ (assuming $y$ are one-hot encoded vector of
labels). Thus the overall dissimilarity cost between two points $(x,y)$ and
$(x^{\prime},y^{\prime})$ is
$\|g(x)-g(x^{\prime})\|_{2}^{2}+\lambda\|y-y^{\prime}\|_{2}^{2}$. In our
experiments we set $\lambda=1$.

VREX [38]: This work proposed to use variance of the risks as a regularizer
(VREX) to learn models which can generalize well to unseen domains. In
particular, they proposed adding an additional objective to the average error
of the source domains, thereby solving

$\min_{g,h}\mathcal{L}(\mathcal{D}_{S};h,g)+\beta\mathrm{Var}(\\{\mathcal{L}(\mathcal{D}^{1}_{S};h,g),\cdots,\mathcal{L}(\mathcal{D}^{N_{S}}_{S};h,g)\\}).$

In our experiments we fix the parameter $\beta$ to be 1.

###  B.2 Analyses of DG using distributional divergence

In this section, we review some of the recent analyses of the DG problem which
have demonstrated that generalization to an unseen domain can be studied in
terms of the distributional distance between the source and the unseen
distributions. Please refer to the original works for detailed descriptions of
the assumptions and results.

[6], [61]: In one of the early works, it was shown that performance on an
unknown target domain can be estimated based on the performance on the source
domain and the distance between the marginal distributions and labeling
functions of the two domains. Let a domain be $(P,f)$, where $P$ denotes the
distribution on inputs $\mathcal{X}$ and $f:\mathcal{X}\rightarrow[0,1]$
denotes the labeling function. Let $h:\mathcal{X}\rightarrow\\{0,1\\}$ be a
hypothesis and $\mathcal{E}_{P}(h,f):=\mathbb{E}_{x\sim P}[|h(x)-f(x)|]$
denote the risk of the hypothesis $h$. Then it was shown in Theorem 1 of [6]
that

$\mathcal{E}_{T}(h,f_{T})\leq\mathcal{E}_{S}(h,f_{S})+d_{1}(P_{S},P_{T})+\min\\{\mathbb{E}_{P_{S}}[|f_{S}(x)-f_{T}(x)|],\mathbb{E}_{\mathcal{D}_{T}}[|f_{S}(x)-f_{T}(x)|]\\},$

where $d_{1}$ denotes the total variation distance. [61], showed a similar
result (Theorem 1 of [61]) using type-1 Wasserstein distance for all
$K-$Lipschitz continuous hypotheses i.e.,

$\mathcal{E}_{T}(h,f_{T})\leq\mathcal{E}_{S}(h,f_{S})+2K\cdot
W_{1}(P_{S},P_{T})+\lambda,$

where $\lambda$ is the combined error of the ideal hypothesis $h^{\ast}$ that
minimizes the combined error
$\mathcal{E}_{S}(h,f_{S})+\mathcal{E}_{T}(h,f_{T})$.

[40]: Recent work showed that the accuracy of smoothed classifiers, smoothed
using different smoothing functions under distribution shifts can also be
bounded using a function dependent on the Wasserstein distance between the
source and target domains. Theorem 4.1 [40] shows that for a function
$h:\mathcal{X}\times\mathcal{Y}\to[0,1]$, whose smoothed version is defined as
$\overline{h}(x,y):=\mathbb{E}_{x^{\prime}\sim S(x)}[h(x^{\prime},y)]$,

$|\mathbb{E}_{(x_{1},y_{1})\sim
S}[\overline{h}(x_{1},y_{1})]-\mathbb{E}_{(x_{2},y_{2})\sim
T}[\overline{h}(x_{2},y_{2})]|\leq\psi(\rho),$

where $\rho$ is the radius of the Wasserstein ball around $S$.

[59]: Another recent work showed that distribution divergence can also be used
to explain the transfer of robustness across the two domains. In particular,
Theorem 1 [59] shows that the difference in the average margin
($Rob(h,P):=\mathbb{E}_{(x,y)\sim P}[\inf_{h(x^{\prime})\neq
y}\|x^{\prime}-x\|]$) of the classifier $h:\mathcal{X}\rightarrow\mathcal{Y}$
under distribution shift is bounded by conditional Wasserstein distance
between the two domains (see the original paper for definition).

$|Rob(h,P_{S})-Rob(h,P_{T})|\leq W_{cond}(P_{S},P_{T}).$

Assuming robust error (REϵ) at a perturbation $\epsilon$ is defined as the
probability of having margin ($mar:=\inf_{h(x^{\prime})\neq
y}\|x-x^{\prime}\|$) less than $\epsilon$ i.e.,
$RE_{\epsilon}:=Pr[mar<\epsilon]$ and average margin $\mathbb{E}[mar]$. Using
Markov’s inequality, we have
$1-RE_{\epsilon}\leq\epsilon^{-1}\mathbb{E}[mar]$. Since
$1-RE_{\epsilon}=RA_{\epsilon}$, the robust accuracy at $\epsilon$, we get a
bound on the robust error under distribution shift, as follows

$|RE_{\epsilon}(P_{S})-RE_{\epsilon}(P_{T})|\leq\epsilon^{-1}W_{cond}(P_{S},P_{T}).$

Along with these works, a large body of works exists in the DRO literature
which explicitly considers their uncertainty set to be based on different
divergence measures such as the Wasserstein distance, $f-$divergences such as
Jenson Shannon, Kullback–Leibler, Hellinger distance as discussed in the
related work section of the main paper. This highlights the important role of
distributional divergence in certification as we are proposing in the paper to
assess the performance of domain generalization methods on new unseen domains.

##  Appendix C Additional discussions

In this section, we discuss certification using different loss functions in
Cert-DG and also present a comparison of input space versus representation
space certification.

(a) CE loss (b) Modified hinge loss (c) 0/1 loss

Figure 10: (Best viewed in color.) Comparison of certified loss and empirical
loss on corrupted and adversarial domains of a model trained with WM on
R-MNIST. The models trained with Vanilla WM on R-MNIST are certified using
Cert-DG with three loss functions.

###  C.1 Certification using different loss functions

As discussed in the main paper, the proof of strong duality (Eq. 2) has been
shown to hold under different assumptions as well as loss functions. Here we
show that Cert-DG can be used with the hinge loss and the 0/1 loss; the latter
can be used to certify the accuracy of the DG models.

####  C.1.1 Hinge loss

When the loss is piece-wise affine $l(z)=\max_{k\leq K}\;[a_{k}^{T}z+b_{k}]$
such as the hinge loss, the dual problem can be written as a simple linear
programming (Corollary 5.1, Remark 6.6 [50], Remark 9 [26]), and therefore the
optimum $\inf_{\gamma\geq
0}\left[\gamma\rho^{2}+E[\phi_{\gamma}(z_{0},y_{0})]\right]$ can be computed
accurately and efficiently. Furthermore, we try to find the optimum for an
unconstrained saddle-point problem using SGD in our approach. However, the
vanilla hinge loss requires modification to be used with SGD, because the loss
gradient is zero ($\nabla_{z}\ell(z)=0$) for correctly classified point $z$,
and therefore SGD does not progress. We address this by using the modified
hinge loss (similar to leaky ReLU)

$\ell_{\mathrm{modified\\_hinge}}(t)=\max\\{0,\;1-t\\}-\alpha\max\\{0,\;t-1\\}$
(5)

where $t$ denotes the difference between the logit of the true class and the
maximum logit of the other classes i.e., $t=h_{y}(x)-h_{other}(x)$ for a point
$(x,y)$ and $\alpha$ is a small constant such as 0.1. Different from the
vanilla hinge loss, the modified loss can have negative values for correctly
classified points. This may be undesirable when the objective is loss
minimization but has no impact when the objective is loss maximization as is
required for certification.

####  C.1.2 0/1 loss

Here we describe how our certification method can be used to certify the
accuracy of the models trained with DG methods. We consider 0/1 loss for
certifying accuracy. Using the 0/1 loss, the solution to the robust surrogate
loss, Eq. 4, can be computed in closed form as shown below:

$\sup_{z}\;\\{\ell(z)-\gamma
c(z,z_{0})\\}=\max\\{0,\;1-\gamma\|z_{0}-z_{adv}\|_{2}^{2}\\},$ (6)

where $(z_{0},y_{0})$ is the initial point and
$z_{adv}=\arg\min_{z}\;\|z-z_{0}\|_{2}^{2}\;\;\mathrm{s.t.}\;\;h(z)\neq
y_{0}$. Therefore the objective for certification is

$\inf_{\gamma\geq
0}\;\left\\{\gamma\rho^{2}+\frac{1}{N}\sum_{i}\max\\{0,\;1-\gamma\|z^{i}_{0}-z^{i}_{adv}\|\\}\right\\}.$
(7)

The objective function is therefore a non-negative, piece-wise linear, non-
continuous, and convex function of $\gamma$. The non-continuity of the
function prevents us from using SGD to optimize over $\gamma$. However,
minimization over $\gamma$ is just a one-dimensional convex optimization even
though it’s non-differentiable. This problem can be efficiently solved using
simple scalar minimization methods (such as “scipy.optimize.minimize_scalar”)
based on the bisection method to solve for the optimal $\gamma$. For
practically solving the certification problem we compute $z_{adv}$ using CW
attack [14] and then solve the minimization problem over $\gamma$ using the
$minimize\\_scalar$ function with the bounded solver and bound the value of
$\gamma$ to be in [1E-20, 100]. We present certification results on a model
trained with WM on R-MNIST in Fig. 10(c). The certified loss at normalized
distance of 1 is the highest since our definition of normalized distance use
the adversarial distribution which is the nearest distribution (to the sources
in the representation space) with zero accuracy.

While our method can be used for certifying the model performance with
different loss functions such as the cross-entropy loss, hinge loss, or the
misclassification (0/1) loss efficiently, we consider only cross-entropy loss
for DR-DG. This choice is due to the differentiability of the worst-case loss
and also the practical observations that most deep learning models perform
better when trained with the cross-entropy loss compared to other losses such
as hinge loss.

###  C.2 Input-space vs representation-space certification

In this section, we discuss the differences in certifying the worst-case loss
considering the Wasserstein-ball in the input space (Eq. 3) versus in the
representation space (Eq. 4) and discuss why certification in the
representation space is easier both from a theoretical and a practical
standpoint.

Certification guarantees when distance between the distributions is measured
in the input space are vacuous since the distributional distance between the
source distributions and the unseen distributions can be large (i.e., when
$c((x_{0},y_{0}),(x_{1},y_{1}))=\|x_{0}-x_{1}\|_{2}^{2}+\infty\cdot
I[y_{0}\neq y_{1}]$ in the Wasserstein distance). For example, many previous
works have shown that DG methods perform reasonably well on the R-MNIST
dataset. But, we observe that the Wasserstein distance measured in the input
space between the source distributions and the well-performing target
distribution is very large. In particular, models trained with WM on rotation
angles $0^{\circ},15^{\circ},30^{\circ},45^{\circ}$, and 60∘ yield $\sim$95%
accuracy on a domain with rotation angle 75∘. But the normalized distance of
the 75∘ domain from the sources is roughly 5, which is too far from the
sources to provide any meaningful guarantees. Thus, the high performance of DG
methods is uncertifiable in the input space i.e. as depicted in Fig. 2, there
could be other distributions ($P_{T_{bad}}$) at the same distance from the
source with a worse loss. In contrast, the representation space learned by DG
methods is much more useful for certification since the distance between the
distributions is explicitly reduced by either using Wasserstein matching or
discriminator-based approaches or DR-DG. Although there are distinct trade-
offs between different methods of alignment, unseen distributions in general
lie much closer to the sources compared to their distances in the input space.
As long as DG algorithms can achieve this, certification using the
representation-space distance is preferable compared to the input-space
distance.

A major advantage of computing the worst-case loss by considering the
Wasserstein ball in the representation space is the ease of solving the robust
surrogate in Eq. 4) compared to solving the version in Eq. 3, which considers
the ball in the input space. As discussed extensively in [62], finding the
maximizer of the robust surrogate loss is in general an NP-hard problem for
networks with ReLU activations. Even if the ReLU activations are changed to
smoother ones, there are still problems with provably maximizing the robust
surrogate loss which has been shown to be possible only when additional
assumptions such as bounded Lipschitz gradient w.r.t to the input and the
model parameters are imposed. These assumptions are prohibitive and restrict
certification only for small to medium size problems. However, when certifying
in the representation space, we don’t need these assumptions since
representation space is usually followed by a single softmax layer, and
maximization of the robust surrogate is much easier both theoretically and
practically. In this work we restrict the certification only in the second to
last layer. Although certification can be applied to other layers but
additional assumptions are needed to guarantee convergence of the
certification procedure. Some of these assumptions, as discussed earlier,
could be prohibitive for large neural networks or may require changes to the
architecture. Moreover, as we consider layers closer to the input, it becomes
more difficult for DG algorithms to reduce the distance between the sources,
thereby leading to poor/vacuous certification guarantees.

A potential disadvantage of our certification method is that it considers the
uncertainty set to be distributions in the representation space. This may
overestimate the worst-case loss since this space can have a worst-case
distribution that is not a push-forward distribution, i.e., one that is not
generated through the representation map. Considering only push forward
distributions is possible by adding additional constraints to our uncertainty
set but it significantly increases the computational complexity of both Cert-
DG and DR-DG since the maximizer of the robust surrogate must be computed
through the representation map (Eq. 3). Although solving Eq. 3, restricts the
worst-case distribution to be the push forward distributions, we find the
worst-case loss to be very similar in both cases, as shown in Fig. 11. The gap
between the worst-case losses computed becomes even smaller when the models
are trained by DR-DG. This small gap demonstrates that our representation
space based certification is not significantly overestimating the loss of the
worst-case distribution compared to the input space certification. We thus
prefer solving Eq. 4 due to its ease of computation compared to Eq. 3 which
gives us the ability to use Cert-DG and DR-DG on even large-scale problems.

(a) WM (b) G2DM (c) DR-DG ($F$ = 0.5) with WM  (d) DR-DG ($F$ = 1.5) with G2DM

Figure 11: (Best viewed in color.) Comparison of the certified (worst-case)
loss computed in the representation space (by using Eq. 4 as the surrogate
loss) versus the certified loss computed in the input space (by using Eq. 3 as
the surrogate loss) with WM and G2DM trained on R-MNIST dataset.

###  C.3 Point-wise adversarial robustness versus distributional robustness

Point-wise adversarial robustness focuses on ensuring the predictions of a
data point remains constant when it is perturbed by a specific amount (usually
within an $\ell_{p}$ ball). In contrast, distributional robustness deals with
how the performance of the models changes on average when faced with a
distribution different from the one used during training. Specifically,
distributional robustness does not focus on how the model behaves for a
specific point from the distribution but rather focuses on how the model
behaves on average on points from a distribution. In this context, the worst-
case and average-case point-wise robustness of the models can be evaluated
using the following objectives

$\mathbb{E}_{(x,y)\in
Q}[\max_{\delta\in\Delta(x)}[\ell(h(g(x+\delta)),y)]]\;\mathrm{and}\;\mathbb{E}_{(x,y)\in
Q}[\mathbb{E}_{\delta\in T(x)}[\ell(h(g(x+\delta)),y)]]$

where $\Delta(x)$ denotes the permissible perturbations set around a point
$x$, $T(x)$ is the distribution of permissible perturbations and $Q$ is the
source distribution. Notice the above problems are different from the problem
in Eq. 1, which focuses on generating a worst-case distribution in the
Wasserstein ball around the source. The above problems can be approximately
solved using PGD [46] attack and by evaluating the model’s performance on
known transformations in $T(x)$ but solving for the worst-case distribution as
required in Eq. 1 is not possible directly since the problem is infinite-
dimensional. Methodology to solve the problem in Eq. 1 is the focus of our
work and has been discussed extensively in Sec. 3. Moreover, our work focuses
on solving the problem certifiably and providing a guarantee on the
performance of the model on the worst-case distribution in the Wasserstein
ball around the source distribution in the representation space. Thus, our
work can be considered as a distributional analog of point-wise certified
robustness works such as those based on randomized smoothing or interval bound
propagation (for adversarial robustness) which aim to provide a certified
radius within which performance of the model remains constant (for that
point).

Our certification algorithm, Cert-DG, aims to compute the loss of the worst-
case distribution in the Wasserstein ball in the representation space. Since
we consider the distribution in the representation space, we are able to solve
the robust surrogate loss in Eq. 4, without requiring any prohibitive
assumptions, which are needed if the worst-case distribution is considered in
the input space [62]. Similar to point-wise certification guarantees [15],
models trained with empirical risk minimization (ERM) achieve small certified
distributional robustness which implies that the loss of the worst-case
distribution even close to the source distribution can be high. However, this
gap does not imply that the certification results are not tight but shows the
existence of distributions that could lead to a much higher loss. Although, by
imposing additional assumptions on the target distributions it may be possible
to obtain better certification results but it would limit the kind of
distribution shift that the model is certified for and is less general than
the setting we consider. To make models provably more robust than the models
trained with ERM, we proposed the DRO-based training approach, DR-DG. The
point-wise analog of which are approaches proposed in [58, 72] which provided
new training methods that can make models certifiably more robust. Similar to
their results we observe that DR-DG lowers the worst-case loss of the models
under distribution shift without significantly lowering the empirical
performance of the models. Thus, making the models provably robust to unseen
distributions which is crucial for enabling their deployment in critical
applications.

(a) WM on R-MNIST (b) G2DM on R-MNIST (c) CDAN on R-MNIST (d) DR-DG ($F$ =
0.5) with WM on R-MNIST (e) DR-DG ($F$ = 1.5) with G2DM on R-MNIST (f) DR-DG
($F$ = 1.5) with CDAN on R-MNIST (g) WM on PACS (h) G2DM on PACS  (i) CDAN on
PACS  (j) DR-DG ($F=0.75$) with WM on PACS  (k) DR-DG ($F=0.75$) with G2DM on
PACS  (l) DR-DG ($F=0.5$) with CDAN on PACS  (m) WM on VLCS (n) G2DM on VLCS
(o) CDAN on VLCS (p) DR-DG ($F=0.75$) with WM on VLCS  (q) DR-DG ($F=0.4$)
with G2DM on VLCS  (r) DR-DG ($F=1.0$) with CDAN on VLCS

Figure 12: (Best viewed in color.) Comparison of accuracy of the models on
unseen distributions created by adding common corruptions to the source test
set trained with Vanilla DG methods (rows 1, 3 and 5) and DR-DG (rows 2, 4,
and 6) on R-MNIST (rows 1 and 2), PACS (rows 3 and 4), and VLCS (rows 5 and
6).

##  Appendix D Experimental details

All codes are written in Python using Tensorflow/Keras and were run on Intel
Xeon(R) W-2123 CPU with 64 GB of RAM and dual NVIDIA TITAN RTX. Dataset
details and model architectures used are described below.

###  D.1 Dataset description

We have used three popular DG benchmark datasets in our work as described
below.

Rotated MNIST (R-MNIST) [29]: This is a variant of the popular MNIST dataset
where domains are created by rotating images at different angles. The rotation
angles present in the datasets are $\\{0,15,30,45,60,75\\}$. Domains in our
dataset comprise of 2000 images from each rotation angle. We use 1000 images
from the domain for our model training and reserve the other 1000 images for
testing. For evaluating the performance of models trained with DG we use the
images from the test set (although for unseen domains distinguishing training
and test set is not required).

PACS [43]: This dataset contains images for different styles from four domains
Art, Cartoons, Photos, and Sketches. It contains 9991 images belonging to 7
different classes. For evaluating the performance of DG methods on source
domains we hold out 10% of the data from each source domain. However, for
evaluating performance on the unseen domains use all the data from those
domains.

VLCS [22]: This dataset contains images from four domains Caltech101, LabelMe,
SUN09, VOC2007. It contains 10729 images belonging to 5 different classes.
Similar to PACS, we evaluate the performance of DG methods on source domains
using a held-out dataset comprising 10% of the data from each source domain
and use all the data from unseen domains for evaluating the performance of the
models.

###  D.2 Model description

The representation network for R-MNIST uses a convolutional neural network
similar to the one described in Table 7 [30] and we fine-tune a Resnet-50
model for PACS and VLCS. Additionally, for PACS and VLCS we add 2 additional
fully connected layers on top of the 512-dimensional output of the Resnet-50
to reduce the size of the output dimension to 128. This is needed since
estimating Wasserstein distance in a high dimensional space required a large
number of samples. Due to the limited size of these datasets and even smaller
size of the test sets, we reduce the dimension to estimate the Wasserstein
distance better. For discriminators used in G2DM and CDAN, we use two fully
connected layers and feed in the output of the representation network. For
G2DM we do not use the random projection layers in the network and for CDAN we
use multi-linear conditioning. Our classifier just comprises of a fully
connected layer on top of the representation network.

###  D.3 Corruptions used in Figs. 1 and 6

To evaluate the performance of models trained with DG methods on unseen
domains in relation to their distance from the source domains, we chose to add
common corruptions to the test set of the source domain data. The ability to
change the severity of the corruption allows us to create multiple unseen
domains at different distances from the sources. We emphasize that the use of
common corruptions is just an easy and efficient way of generating multiple
unseen domains and only covers a small subset of all possible unseen domains.
Moreover, our task here is not to show that the performance of models trained
with different DG methods deteriorates on these corrupted domains but it is
rather to highlight the high variability in their performance even when
distributions lie at the same distance. For R-MNIST we use the corruptions
from the MNIST-C dataset [52] (shot noise, impulse noise, glass blur, shear,
scale, translate, fog, spatter, elastic transform) and for PACS and VLCS we
use corruptions from the Imagenet-C dataset [33] (Gaussian noise, shot noise,
impulse noise, speckle noise, Gaussian blur, defocus blur, zoom blur, spatter,
contrast, brightness, saturate, elastic transform).

###  D.4 PGD adversarial attacks

We consider adversarial attacks using PGD [46] to demonstrate the existence of
distributions beyond common corruptions which can degrade the performance of
DG methods as predicted by our certification in Fig. 3. We consider two
variants of this attack. The first is the usual PGD attack where the
adversarial examples are crafted in the input space by maximizing the loss of
the perturbed examples (denoted by the grey dashed line with square markers in
Fig. 3). The distance between the adversarial example and the clean example is
measured in the input space in this case. The second variant is the PGD attack
created in the representation space. In this attack, the distortion between
the clean and adversarial examples is measured in the representation space and
the perturbation is applied to the representation of the clean examples, i.e.,
$\max_{z^{\prime}}\ell(h(z^{\prime}),y)\;\mathrm{s.t.}\;\|z^{\prime}-z\|_{2}\leq\epsilon_{g}$
where $z^{\prime}$ is the adversarial example in the representation space for
the point $(z=g(x),y)$ and $\epsilon_{g}$ is the bound on the distortion in
the representation space. The result of this attack is shown as the green
dashed line in Fig. 3).

###  D.5 Implementation details of Cert-DG and DR-DG

Here we briefly describe some of the implementation details for our
certification and training algorithms. Cert-DG requires to compute
distributions which have an average distortion of $\rho^{2}$. Solving the
certification problem requires maximization of the robust surrogate loss Eq. 4
for every point. We solve the problem batch-wise and keep track of the
perturbation applied to the points. Since the network parameters are fixed
during certification, using the previously saved perturbation as the starting
point helps the algorithm converge faster with minimal tuning of the
hyperparameters such as the learning rates in Alg. 1. For DR-DG, since the
representation space changes we find that keeping track of the perturbations
is not as helpful for some DG methods specially on PACS and VLCS where the
representation is fine-tuned starting from a pre-trained ResNet-50 models.
Thus, for G2DM, CDAN and VREX, we opt to increase the number of maximization
steps per batch rather than using the previous perturbation on VLCS and PACS.
On the other hand, for WM on these datasets we use a fewer maximization steps
and keep track of the perturbations since we empirically found that the
representation changes gradually when trained WM and using the previous
perturbations help generate distributions perturbed by $\rho^{2}$ just as in
Cert-DG. Due to the simplicity of the R-MNIST dataset we do not observe any
difference in behavior of the algorithms while training with DR-DG and thus we
chose to keep track of the perturbations applied to the points to solve the
problem more efficiently. The main advantage of keeping track of the
perturbation is that it helps eliminate the problem of doing a large number of
steps to generate distributions with perturbation $\rho^{2}$ which can slow
down DR-DG training.

Our distance computations and DR-DG algorithm rely on estimating the
adversarial distribution in the representation space. We rely on the
Cleverhans implementation of the CW-attack [14] for generating this
distribution. We use 1000 points from the test set and compute the adversarial
examples for these points and measure $\rho_{adv}$ (in Fig. 2) using the
original and the perturbed points. Since we work in the representation space
estimating the adversarial distribution is computationally easy and we require
approximately 2 minutes for computing points which achieve greater than 95%
attack success on models trained with vanilla DG methods.