# Robust Optimal Transport with Applications in Generative Modeling and Domain
Adaptation

Yogesh Balaji
Department of Computer Science
University of Maryland
College Park, MD
<EMAIL_ADDRESS>
&Rama Chellappa
Electrical and Computer Engineering
and Biomedical Engineering Departments
Johns Hopkins University
Baltimore, MD
<EMAIL_ADDRESS>
&Soheil Feizi
Department of Computer Science
University of Maryland
College Park, MD
<EMAIL_ADDRESS>

###### Abstract

Optimal Transport (OT) distances such as Wasserstein have been used in several
areas such as GANs and domain adaptation. OT, however, is very sensitive to
outliers (samples with large noise) in the data since in its objective
function, every sample, including outliers, is weighed similarly due to the
marginal constraints. To remedy this issue, robust formulations of OT with
unbalanced marginal constraints have previously been proposed. However,
employing these methods in deep learning problems such as GANs and domain
adaptation is challenging due to the instability of their dual optimization
solvers. In this paper, we resolve these issues by deriving a computationally-
efficient dual form of the robust OT optimization that is amenable to modern
deep learning applications. We demonstrate the effectiveness of our
formulation in two applications of GANs and domain adaptation. Our approach
can train state-of-the-art GAN models on noisy datasets corrupted with outlier
distributions. In particular, our optimization computes weights for training
samples reflecting how difficult it is for those samples to be generated in
the model. In domain adaptation, our robust OT formulation leads to improved
accuracy compared to the standard adversarial adaptation methods. Our code is
available at https://github.com/yogeshbalaji/robustOT.

##  1 Introduction

Estimating distances between probability distributions lies at the heart of
several problems in machine learning and statistics. A class of distance
measures that has gained immense popularity in several machine learning
applications is Optimal Transport (OT) [29]. In OT, the distance between two
probability distributions is computed as the minimum cost of transporting a
source distribution to the target one under some transportation cost function.
Optimal transport enjoys several nice properties including structure
preservation, existence in smooth and non-smooth settings, being well defined
for discrete and continuous distributions [29], etc.

Two recent applications of OT in machine learning include generative modeling
and domain adaptation. In Wasserstein GAN [1], a generative model is trained
by minimizing the (approximate) Wasserstein distance between real and
generative distributions. In the dual form, this objective reduces to a two-
player min-max game between a generator and a discriminator. Similar ideas
involving distance minimization between source and target feature
distributions are common in domain adaptation [10]. In [26, 2], Wasserstein
distance is used as the choice of distance measure for minimizing the domain
gap.

(a) Clean dataset

(b) Dataset with outliers

(c) Dataset with outliers

Figure 1: Visualizing couplings of Wasserstein computation between two
distributions shown in red and blue. In (a), we show the couplings when no
outliers are present. In (b), we show the couplings when $5\%$ outliers are
added to the data. The Wasserstein distance increases significantly indicating
high sensitivity to outliers. In (c), we show the couplings produced by the
Robust Wasserstein measure. Our formulation effectively ignores the outliers
yielding a Wasserstein estimate that closely approximates the true Wasserstein
distance.

One of the fundamental shortcomings of optimal transport is its sensitivity to
outlier samples. By outliers, we mean samples with large noise. In the OT
optimization, to satisfy the marginal constraints between the two input
distributions, every sample is weighed equally in the feasible transportation
plans. Hence, even a few outlier samples can contribute significantly to the
OT objective. This leads to poor estimation of distributional distances when
outliers are present. An example is shown in Fig. 1, where the distance
between distributions shown in red and blue are computed. In the absence of
outliers (Fig. 1(a)), proper couplings (shown in green) are obtained. However,
even in the presence of a very small fraction of outliers (as small as $5\%$),
poor couplings arise leading to a large change in the distance estimate (Fig.
1(b)).

The OT sensitivity to outliers is undesirable, especially when we deal with
large-scale datasets where the noise is inevitable. This sensitivity is a
consequence of exactly satisfying the marginal constraints in OT’s objective.
Hence, to boost OT’s robustness against outliers, we propose to utilize recent
formulations of unbalanced optimal transport [6, 13] which relax OT’s marginal
constraints. The authors in [6, 13] provide an exact dual form for the
unbalanced OT problem. However, we have found that using this dual
optimization in large-scale deep learning applications such as GANs results in
poor convergence and an unstable behaviour (see Section 3.1 and the appendix
for details).

To remedy this issue, in this work, we derive a computationally efficient dual
form for the unbalanced OT optimization that is suited for practical deep
learning applications. Our dual simplifies to a weighted OT objective, with
low weights assigned to outlier samples. These instance weights can also be
useful in interpreting the difficulty of input samples for learning a given
task. We develop two solvers for this dual problem based on either a discrete
formulation or a continuous stochastic relaxation. These solvers demonstrate
high stability in large-scale deep learning applications.

We show that, under mild assumptions, our robust OT measure (which is similar
in form to the unbalanced OT) is upper bounded by a constant factor of the
true OT distance (OT ignoring outliers) for any outlier distribution. Hence,
our robust OT can be used for effectively handling outliers. This is
visualized in Figure 1(c), where couplings obtained by robust OT effectively
ignores outlier samples, yielding a good estimate of the true OT distance. We
demonstrate the effectiveness of the proposed robust OT formulation in two
large-scale deep learning applications of generative modeling and domain
adaptation. In generative modeling, we show how robust Wasserstein GANs can be
trained using state-of-the-art GAN architectures to effectively ignore
outliers in the generative distrubution. In domain adaptation, we utilize the
robust OT framework for the challenging task of synthetic to real adaptation,
where our approach improves adversarial adaptation techniques by $\sim 5\%$.

##  2 Background on Optimal Transport

Let $\mathcal{X}$ denote a compact metric space, and $Prob(\mathcal{X})$
denote the space of probability measures defined on $\mathcal{X}$. Given two
probability distributions $\mathbb{P}_{X}$, $\mathbb{P}_{Y}\in
Prob(\mathcal{X})$ and a continuous cost function
$c:\mathcal{X}\times\mathcal{X}\to\mathbb{R}$, optimal transport finds the
minimum cost for transporting the density $\mathbb{P}_{X}$ to $\mathbb{P}_{Y}$
[29], given by the following cost function

$\displaystyle\mathcal{W}(\mathbb{P}_{X},\mathbb{P}_{Y})$
$\displaystyle=\min_{\pi\in\Pi(\mathbb{P}_{X},\mathbb{P}_{Y})}\int\int
c(x,y)\pi(x,y)dxdy$ (1)

where $\Pi(\mathbb{P}_{X},\mathbb{P}_{Y})$ is set of all joint distributions
(couplings) whose marginals are $\mathbb{P}_{X}$ and $\mathbb{P}_{Y}$,
respectively. That is, $\int\pi(x,y)dy=\mathbb{P}_{X}$ and
$\int\pi(x,y)dx=\mathbb{P}_{Y}$. These set of constraints enforce that the
marginals of couplings exactly match the distributions $\mathbb{P}_{X}$ and
$\mathbb{P}_{Y}$. Hence, when the input distributions have outliers, they are
forced to have non-zero weights in couplings leading to a large transportation
cost. In practice, the dual form of the optimization $\eqref{eq:OT_primal}$ is
often used.

##### Kantrovich Duality:

The dual formulation of optimal transport problem [29] is given by:

$\displaystyle\min_{\pi\in\Pi(\mathbb{P}_{X},\mathbb{P}_{Y})}$
$\displaystyle\int\int c(x,y)\pi(x,y)dxdy=\max_{\phi\in
Lip-1}\int\phi(x)d\mathbb{P}_{X}-\int\phi(x)d\mathbb{P}_{Y}.$ (2)

Optimization (2) is the celebrated Kantorovich-Rubinstein duality. This is a
simpler optimization problem compared to (1) since the maximization is over a
class of 1-Lipschitz functions. In practice, $\phi(\cdot)$ function is
implemented using a neural network, and the $1$-Lipscitz constraint is
enforced using weight clipping [1] or a penalty on the gradients [11].

The use of optimal transport has gained popularity in machine learning [28,
26, 1], computer vision [27, 4] and many other disciplines. Several
relaxations of the OT problem have been proposed in the literature. Two
popular ones include entropy regularization [8, 3] and marginal relaxation
[13, 6, 7, 9, 12]. In this work, we utilize the marginal relaxations of [13,
6] for handling outlier noise in machine learning applications involving OT.
To the best of our knowledge, ours is the first work to demonstrate the
utility of unbalanced OT in large-scale deep learning applications. Only other
paper that is similar in spirit to our work is [30]. However, [30] provides a
relaxation for the Monge unbalanced OT, which is different from the unbalanced
Kantrovich problem we consider in this paper.

##  3 Robust Optimal Transport

Our objective is to handle outliers in deep learning applications involving
OT. For this, we use relaxed OT formulations. In this section, we first
formally define the outlier model we use. Then, we discuss the existing
marginal relaxation formulations in OT and the issues that arise in deep
learning when using these formulations. We then propose a reformulation of the
dual that is suited for deep learning.

##### Outlier Model:

We consider outliers as samples with large noise. More specifically, let
$\mathbb{P}_{X}$ and $\mathbb{P}_{Y}$ be two distributions whose Wasserstein
distance we desire to compute. Let
$\mathbb{P}_{X}=\alpha\mathbb{P}_{X}^{c}+(1-\alpha)\mathbb{P}_{X}^{a}$; i.e.,
the clean distribution $\mathbb{P}_{X}^{c}$ is corrupted with $(1-\alpha)$
fraction of noise $\mathbb{P}_{X}^{a}$. Then, $\mathbb{P}_{X}^{a}$ is
considered an oulier distribution if
$\mathcal{W}(\mathbb{P}_{X}^{c},\mathbb{P}_{Y})\ll\mathcal{W}(\mathbb{P}_{X}^{a},\mathbb{P}_{Y})$.
For an example, refer to Fig. 1(b).

###  3.1 Unbalanced Optimal Transport

As seen in Fig. 1, sensitivity to outliers arises due to the marginal
constraints in OT. If the marginal constraints are relaxed in a way that the
transportation plan does not assign large weights to outliers, they can
effectively be ignored. [6, 13] have proposed one such relaxation using
$f$-divergence on marginal distributions. This formulation, called _Unbalanced
Optimal Transport_ , can be written as

$\displaystyle\mathcal{W}^{ub}(\mathbb{P}_{X},\mathbb{P}_{Y})$
$\displaystyle=\min_{\pi\in\Pi(\mathbb{P}_{\tilde{X}},\mathbb{P}_{\tilde{Y}})}\int
c(x,y)\pi(x,y)dxdy+\mathcal{D}_{f}(\mathbb{P}_{\tilde{X}}||\mathbb{P}_{X})+\mathcal{D}_{f}(\mathbb{P}_{\tilde{Y}}||\mathbb{P}_{Y})$
(3)

where $\mathcal{D}_{f}$ is the $f$-divergence between distributions, defined
as $\mathcal{D}_{f}(P||Q)=\int f(\frac{dP}{dQ})dQ$. Furthermore, [13] derived
a dual form for the problem. Let $f$ be a convex lower semi-continuous
function. Define $r^{*}(x):=\sup_{s>0}\frac{x-f(s)}{s}$ where
$f^{\prime}_{\infty}:=\lim_{s\to\infty}\frac{f(s)}{s}$. Then,

$\displaystyle\mathcal{W}^{ub}(\mathbb{P}_{X},\mathbb{P}_{Y})$
$\displaystyle=\max_{\phi,\psi}\int\phi(x)d\mathbb{P}_{X}+\int\psi(y)d\mathbb{P}_{Y}$
(4) $\displaystyle\text{ s.t. }r^{*}(\phi(x))+r^{*}(\psi(y))\leq c(x,y)$

##### Computational issues using this dual form in deep learning:

Training neural networks using this dual form is challenging as it involves
maximizing over two discriminator functions ($\phi$ and $\psi$), with
constraints connecting these functions. For $\chi^{2}$ divergence, we derived
the GAN objective using this dual and trained a model. However, we were
unsuccessful in making the model converge using standard SGD as it showed
severe instability. Please refer to Appendix for more details. This limits the
utility of this formulation in deep learning applications. In what follows, we
present a reformulation of the dual that is scalable and suited for deep
learning applications.

###  3.2 Our Duality

We start with a slightly different form than (3) where we keep the
$f$-divergence relaxations of marginal distributions as constraints:

$\displaystyle\mathcal{W}^{rob}_{\rho_{1},\rho_{2}}(\mathbb{P}_{X},\mathbb{P}_{Y}):=$
$\displaystyle\min_{\mathbb{P}_{\tilde{X}},\mathbb{P}_{\tilde{Y}}\in
Prob(\mathcal{X})}~{}\min_{\pi\in\Pi(\mathbb{P}_{\tilde{X}},\mathbb{P}_{\tilde{Y}})}\int\int
c(x,y)\pi(x,y)dxdy$ (5) $\displaystyle\text{ s.t.
}\mathcal{D}_{f}(\mathbb{P}_{\tilde{X}}||\mathbb{P}_{X})\leq\rho_{1},~{}\mathcal{D}_{f}(\mathbb{P}_{\tilde{Y}}||\mathbb{P}_{Y})\leq\rho_{2}.$

In this formulation, we optimize over the couplings whose marginal constraints
are the relaxed distributions $\mathbb{P}_{\tilde{X}}$ and
$\mathbb{P}_{\tilde{Y}}$. To prevent over-relaxation of the marginals, we
impose a constraint that the $f$-divergence between the relaxed and the true
marginals are bounded by constants $\rho_{1}$ and $\rho_{2}$ for distributions
$\mathbb{P}_{\tilde{X}}$ and $\mathbb{P}_{\tilde{Y}}$, respectively. As seen
in Fig. 1(c), this relaxation effectively ignores the outlier distributions
when $(\rho_{1},\rho_{2})$ are chosen appropriately. We study some properties
of robust OT in the appendix. Notably, robust OT does not satisfy the triangle
inequality.

Note that the Lagrangian relaxation of optimization (5) takes a similar form
to that of the unbalanced OT objective (3). Having a hard constraint on
$f$-divergence gives us an explicit control over the extent of the marginal
relaxation which is suited for handling outliers. This subtle difference in
how the constraints are imposed leads to a dual form of our robust OT that can
be computed efficiently for deep learning applications compared to that of the
unbalanced OT dual.

We consider the $\ell_{2}$ distance as our choice of cost function in the OT
formulation. In this case, the OT distance is also called the Wasserstein
distance. In that case, we have the following result:

######  Theorem 1.

Let $\mathbb{P}_{X}$ and $\mathbb{P}_{Y}$ be two distributions defined on a
metric space. The robust Wasserstein measure admits the following dual form

$\displaystyle\mathcal{W}^{rob}_{\rho_{1},\rho_{2}}(\mathbb{P}_{X},\mathbb{P}_{Y})$
$\displaystyle=\min_{\mathbb{P}_{\tilde{X}},\mathbb{P}_{\tilde{Y}}}\max_{k\in
Lip-1}\int D(x)d\mathbb{P}_{\tilde{X}}-\int D(x)d\mathbb{P}_{\tilde{Y}}$ (6)
$\displaystyle\text{ s.t
}\mathcal{D}_{f}(\mathbb{P}_{\tilde{X}}||\mathbb{P}_{X})\leq\rho_{1},~{}\mathcal{D}_{f}(\mathbb{P}_{\tilde{Y}}||\mathbb{P}_{Y})\leq\rho_{2}.$

Thus, we can obtain a dual form for robust OT similar to the Kantrovich-
Rubinstein duality. The key difference of this dual form compared to the
unbalanced OT dual (opt. (4)) is that we optimize over a single dual function
$D(.)$ as opposed to two dual functions in (4). This makes our formulation
suited for deep learning applications such as GANs and domain adaptation. Note
that the integrals in opt. (6) are taken with respect to the relaxed
distributions $\mathbb{P}_{\tilde{X}}$ and $\mathbb{P}_{\tilde{Y}}$ which is a
non-trivial computation.

In particular, we present two approaches for optimizing the dual problem (6):

##### Discrete Formulation.

In practice, we observe empirical distributions $\mathbb{P}_{X}^{(m)}$ and
$\mathbb{P}_{Y}^{(n)}$ from the population distributions $\mathbb{P}_{X}$ and
$\mathbb{P}_{Y}$, where $m$ and $n$ are sample sizes. Let
$\\{\mathbf{x}_{i}\\}_{i=1}^{m}$, $\\{\mathbf{y}_{i}\\}_{i=1}^{n}$ be the
samples corresponding to the empirical distribution $\mathbb{P}_{X}^{(m)}$ and
$\mathbb{P}_{Y}^{(m)}$, respectively. Following [19], we use weighted
empirical distribution for the perturbed distribution
$\mathbb{P}_{\tilde{X}}$, i.e., $\mathbb{P}_{X}^{(m)}(\mathbf{x}_{i})=1/m$ and
$\mathbb{P}_{\tilde{X}}(\mathbf{x}_{i})=w^{x}_{i}$. Let
$\mathbf{w}_{x}=[w^{x}_{1},\ldots w^{x}_{m}]$. For $\mathbb{P}_{\tilde{X}}$ to
be a valid pmf, $\mathbf{w}_{x}$ should lie in a simplex
($\mathbf{w}^{x}\in\Delta^{m}$) i.e., $w^{x}_{i}>0$ and $\sum_{i}w^{x}_{i}=1$.
Then, the robust Wasserstein objective can be written as

$\displaystyle\mathcal{W}^{rob}_{\rho_{1},\rho_{2}}(\mathbb{P}_{X},\mathbb{P}_{Y})=$
$\displaystyle\min_{\mathbf{w}_{x}\in\Delta^{m},\mathbf{w}_{y}\in\Delta^{n}}\max_{\mathbf{D}\in
Lip-1}(\mathbf{w}_{x})^{t}\mathbf{d}_{x}-(\mathbf{w}_{y})^{t}\mathbf{d}_{y}$
$\displaystyle\text{ s.t
}\frac{1}{m}\sum_{i}f(mw^{x}_{i})\leq\rho_{1},~{}~{}\frac{1}{n}\sum_{i}f(nw^{y}_{i})\leq\rho_{2}$

where
$\mathbf{d}_{x}=[\mathbf{D}(\mathbf{x}_{1}),\mathbf{D}(\mathbf{x}_{2})\ldots\mathbf{D}(\mathbf{x}_{m})]$,
and
$\mathbf{d}_{y}=[\mathbf{D}(\mathbf{y}_{1}),\mathbf{D}(\mathbf{y}_{2})\ldots\mathbf{D}(\mathbf{y}_{n})]$.
Since $f(.)$ is a convex function, the set of constraints involving
$\mathbf{w}_{x}$ and $\mathbf{w}_{y}$ are convex w.r.t weights. We use
$\chi^{2}$ as our choice of $f$-divergence for which $f(t)=(t-1)^{2}/2$. The
optimization then becomes

$\displaystyle\mathcal{W}^{rob}_{\rho_{1},\rho_{2}}(\mathbb{P}_{X},\mathbb{P}_{Y})=$
$\displaystyle\min_{\mathbf{w}_{x}\in\Delta^{m},\mathbf{w}_{y}\in\Delta^{n}}\max_{\mathbf{D}\in
Lip-1}(\mathbf{w}_{x})^{t}\mathbf{d}_{x}-(\mathbf{w}_{y})^{t}\mathbf{d}_{y}$
(7) $\displaystyle\text{ s.t
}\left\|\mathbf{w}_{x}-\frac{1}{m}\right\|_{2}\leq\sqrt{\frac{2\rho_{1}}{m}},~{}~{}\left\|\mathbf{w}_{y}-\frac{1}{n}\right\|_{2}\leq\sqrt{\frac{2\rho_{2}}{n}}$

We solve this optimization using an alternating gradient descent between
$\mathbf{w}$ and $\mathbf{D}$ updates. The above optimization is a second-
order cone program with respect to weights $\mathbf{w}$ (for a fixed
$\mathbf{D}$). For a fixed $\mathbf{w}$, $\mathbf{D}$ is optimized using
stochastic gradient descent similar to [1].

##### Continuous Stochastic Relaxation.

In (7), weight vectors $\mathbf{w}_{x}$ and $\mathbf{w}_{y}$ are optimized by
solving a second order cone program. Since the dimension of weight vectors is
the size of the entire dataset, solving this optimization is expensive for
large datasets. Hence, we propose a continuous stochastic relaxation for (6).
Let us assume that supports of $\mathbb{P}_{\tilde{X}}$ and $\mathbb{P}_{X}$
match (satisfied in real spaces). We make the following reparameterization:
$\mathbb{P}_{\tilde{X}}(\mathbf{x})=\mathbf{W}_{x}(\mathbf{x})\mathbb{P}_{X}(\mathbf{x})$.
For $\mathbb{P}_{\tilde{X}}$ to be a valid pdf, we require
$\int\mathbf{W}_{x}(\mathbf{x})d\mathbb{P}_{X}=1$, i.e.,
$\mathbb{E}_{\mathbf{x}\sim\mathbb{P}_{X}}[\mathbf{W}_{x}(\mathbf{x})]=1$. The
constraint on $f$-divergence becomes
$\mathbb{E}_{\mathbf{x}\sim\mathbb{P}_{X}}[f(\mathbf{W}_{x}(\mathbf{x}))]\leq\rho_{1}$.
Using these, the dual of robust Wasserstein measure can be written as

$\displaystyle\mathcal{W}^{rob}_{\rho_{1},\rho_{2}}(\mathbb{P}_{X},\mathbb{P}_{Y})=$
$\displaystyle\min_{\mathbf{W}_{x},\mathbf{W}_{y}}\max_{\mathbf{D}\in
Lip-1}\mathbb{E}_{\mathbf{x}\sim\mathbb{P}_{X}}[\mathbf{W}_{x}(\mathbf{x})\mathbf{D}(\mathbf{x})]-\mathbb{E}_{\mathbf{y}\sim\mathbb{P}_{Y}}[\mathbf{W}_{y}(\mathbf{y})\mathbf{D}(\mathbf{y})]$
(8) $\displaystyle\text{ s.t
}~{}\mathbb{E}_{\mathbf{x}\sim\mathbb{P}_{X}}[f(\mathbf{W}_{x}(\mathbf{x}))]\leq\rho_{1},~{}~{}\mathbb{E}_{\mathbf{y}\sim\mathbb{P}_{Y}}[f(\mathbf{W}_{y}(\mathbf{y}))]\leq\rho_{2}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}\mathbb{E}_{\mathbf{x}\sim\mathbb{P}_{X}}[\mathbf{W}_{x}(\mathbf{x})]=1,~{}~{}\mathbb{E}_{\mathbf{y}\sim\mathbb{P}_{Y}}[\mathbf{W}_{y}(\mathbf{y})]=1,\mathbf{W}_{x}(\mathbf{x})\geq
0,\mathbf{W}_{y}(\mathbf{y})\geq 0$

$\mathbf{W}_{x}(.)$ and $\mathbf{W}_{y}(.)$ are weight functions which can be
implemented using neural networks. One crucial benefit of the above
formulation is that it can be easily trained using stochastic GD.

###  3.3 Can robust OT handle outliers?

######  Theorem 2.

Let $\mathbb{P}_{X}$ and $\mathbb{P}_{Y}$ be two distributions such that
$\mathbb{P}_{X}$ is corrupted with $\gamma$ fraction of outliers i.e.,
$\mathbb{P}_{X}=(1-\gamma)\mathbb{P}_{X}^{c}+\gamma\mathbb{P}_{X}^{a}$, where
$\mathbb{P}_{X}^{c}$ is the clean distribution and $\mathbb{P}_{X}^{a}$ is the
outlier distribution. Let
$\mathcal{W}(\mathbb{P}_{X}^{a},\mathbb{P}_{X}^{c})=k\mathcal{W}(\mathbb{P}_{X}^{c},\mathbb{P}_{Y})$,
with $k\geq 1$. Then,

$\displaystyle\mathcal{W}^{rob}_{\rho,0}$
$\displaystyle(\mathbb{P}_{X},\mathbb{P}_{Y})\leq\max\Big{(}1,1+k\gamma-k\sqrt{2\rho\gamma(1-\gamma)}\Big{)}\mathcal{W}(\mathbb{P}_{X}^{c},\mathbb{P}_{Y}).$

The above theorem states that robust OT obtains a provably robust distance
estimate under our outlier model. That is, the robust OT is upper bounded by a
constant factor of the true Wasserstein distance. This constant depends on the
hyper-parameter $\rho$: when $\rho$ is appropriately chosen, robust OT measure
obtains a value approximately close to the true distance. Note that we derive
this result for one-sided robust OT ($\mathcal{W}^{rob}_{\rho,0}$), which is
the robust OT measure when marginals are relaxed only for one of the input
distributions. This is the form we use for GANs and DA experiments (Section.
4).

##### Choosing $\rho$ and the tightness of the bound:

The constant $\rho$ in our formulation is a hyper-parameter that needs to be
estimated. The value of $\rho$ denotes the extent of marginal relaxation. In
applications such as GANs or domain adaptation, performance on a validation
set can be used for choosing $\rho$. Or when the outlier fraction $\gamma$ is
known, an appropriate choice of $\rho$ is $\rho=\frac{\gamma}{2(1-\gamma)}$.
More details and experiments on tightness of our upper bound are provided in
the Appendix.

(a) CIFAR-10 + MNIST

(b) CIFAR-10 + Uniform noise

Figure 2: FID scores of GAN models trained on CIFAR-10 corrupted with outlier
noise. In (a), samples from MNIST dataset are used as the outliers, while in
(b), uniform noise is used. FID scores of WGAN increase with the increase in
outlier fraction, while robust WGAN maintains FID scores.  Figure 3:
Visualizing samples and weight histograms. In the top panel, we show samples
generated by WGAN and robust WGAN trained on CIFAR-10 dataset corrupted with
MNIST samples as outliers. WGAN fits both CIFAR and MNIST samples, while
robust WGAN ignores the outliers. In the bottom panel, we visualize the
weights (output of the $\mathbf{W}(.)$ function) for in-distribution and
outlier samples. Outlier samples are assinged low weights while in-
distribution samples get large weights.

##  4 Experiments

For all our experiments, we use one-sided robust Wasserstein
($\mathcal{W}^{rob}_{\rho,0}$) where the marginals are relaxed only for one of
the input distributions. Please refer to Appendix for all experimental
details. Code for our experiments is available at
https://github.com/yogeshbalaji/robustOT.

###  4.1 Generative modeling

In this section, we show how our robust Wasserstein formulation can be used to
train GANs that are insensitive to outliers. The core idea is to train a GAN
by minimizing the robust Wasserstein measure (in dual form) between real and
generative data distributions. Let $\mathbf{G}$ denote a generative model
which maps samples from random noise vectors to real data distribution. Using
the one-directional version of the dual form of robust Wasserstein measure
(8), we obtain the following optimization problem

$\displaystyle\min_{\mathbf{W},\mathbf{G}}~{}$
$\displaystyle\max_{\mathbf{D}\in
Lip-1}\mathbb{E}_{\mathbf{x}\sim\mathbb{P}_{X}}[\mathbf{W}(\mathbf{x})\mathbf{D}(\mathbf{x})]-\mathbb{E}_{\mathbf{z}}[\mathbf{D}(\mathbf{G}(\mathbf{z}))]$
$\displaystyle\text{ s.t
}~{}~{}\mathbb{E}_{\mathbf{x}\sim\mathbb{P}_{X}}[(\mathbf{W}(\mathbf{x})-1)^{2}]\leq
2\rho,~{}~{}\mathbb{E}_{\mathbf{x}\sim\mathbb{P}_{X}}[\mathbf{W}(\mathbf{x})]=1,~{}~{}\mathbf{W}(\mathbf{x})\geq
0$

The first constraint is imposed using a Lagrangian term in the objective
function. To impose the second constraint, we use ReLU as the final layer of
$\mathbf{W}(.)$ network and normalize the weights by the sum of weight vectors
in a batch. This leads to the following optimization

$\displaystyle\min_{\mathbf{W},\mathbf{G}}$ $\displaystyle\max_{\mathbf{D}\in
Lip-1}\mathbb{E}_{\mathbf{x}}[\mathbf{W}(\mathbf{x})\mathbf{D}(\mathbf{x})]-\mathbb{E}_{\mathbf{z}}[\mathbf{D}(\mathbf{G}(\mathbf{z}))]+\lambda\max\left(\mathbb{E}_{\mathbf{x}}[(\mathbf{W}(\mathbf{x})-1)^{2}]-2\rho,0\right)$
(9)

We set $\lambda$ to a large value (typically $\lambda=1000$) to enforce the
constraint on $\chi^{2}$-divergence. A detailed algorithm can be found in
Appendix. Our robust Wasserstein formulation can easily be extended to other
GAN objective functions such as non-saturating loss and hinge loss, as
discussed in Appendix.

Figure 4: Visualizing samples generated on Domainnet sketch dataset. In panels
(a), (b) and (c), we show the real data, samples generated by SNGAN and robust
SNGAN, respectively. Robust SNGAN only generates images of sketches ignoring
outliers. In panel (d), we visualize real samples sorted by weights. Low
weights are assigned to outliers, while sketch images get large weights.

##### Datasets with outliers:

First, we train the robust Wasserstein GAN on datasets corrputed with outlier
samples. For the ease of quantitative evaluation, the outlier corrupted
dataset is constructed as follows: We artificially add outlier samples to the
CIFAR-10 dataset such they occupy $\gamma$ fraction of the samples. MNIST and
uniform noise are used as two choices of outlier distributions. Samples
generated by Wasserstein GAN and robust Wasserstein GAN on this dataset are
shown in Fig. 3. While Wasserstein GAN fits outliers in addition to the CIFAR
samples, robust Wasserstein GAN effectively ignores outliers and generates
samples only from the CIFAR-10 dataset.

For a quantitative evaluation, we report the FID scores of the generated
samples with respect to the clean CIFAR-10 distribution (Figure 2). Since
Wasserstein GAN generates outlier samples in addition to the CIFAR-10 samples,
the FID scores get worse as the outlier fraction increases. Robust Wasserstein
GAN, on the other hand, obtains good FID even for large fraction of outliers.
This trend is consistent for both outlier distributions MNIST and uniform
noise.

Next, we train our robust GAN model on a dataset where outliers are naturally
present. We use Sketch domain of DomainNet dataset [20] for this purpose. As
shown in Figure 4(a), the dataset contains many outlier samples (non-sketch
images). Samples generated by spectral normalization GAN and robust spectral
normalization GAN (both using Resnet) are shown in Figure 4(b, c). We observe
that the SNGAN model generates some non-sketch images in addition to sketch
images. Robust SNGAN, on the other hand, ignores outliers and only generates
samples that look like sketches.

Table 1: Quantitative evaluation of robust WGAN on clean datasets. In each
cell, the top row corresponds to the Inception score and the bottom row
corresponds to the FID score.

Dataset | Arch | WGAN | RWGAN
---|---|---|---
$\rho=0$ | $\rho=0.3$
CIFAR-10 | DCGAN | 6.86 | 6.84 | 6.91
28.46 | 29.11 | 29.45
CIFAR-10 | Resnet | 7.49 | 7.35 | 7.36
21.73 | 21.98 | 21.57
CIFAR-100 | Resnet | 9.01 | 8.79 | 8.93
15.60 | 15.61 | 15.32

Table 2: Cross-domain recognition accuracy on VISDA-17 dataset using Resnet-18
model averaged over $3$ runs.

Method | Accuracy (in $\%$)
---|---
Source only | 44.7
Adversarial (no ent) | 55.4
Robust adversarial (no ent) | 62.9
Adversarial (with ent) | 59.5
Robust adversarial (with ent) | 63.9

##### Clean datasets:

In the previous section, we demonstrated how robust Wasserstein GAN
effectively ignores outliers in the data distributions. A natural question
that may arise is what would happen if one uses the robust WGAN on a clean
dataset (dataset without outliers). To understand this, we train robust
Wasserstein GAN on CIFAR-10 and CIFAR-100 datasets. The Inception and FID
scores of generated samples are reported in Table. 2. We observe no drop in
FID scores, which suggest that no modes are dropped in the generated
distribution.

##### Usefulness of sample weights:

In the optimization of the robust GAN, each sample is assigned a weight
indicating the difficulty of that sample to be generated by the model. In this
section, we visualize the weights learnt by our robust GAN. In Figure 3, we
plot the histogram of weights assigned to in-distribution and outlier samples
for robust WGAN trained on CIFAR-10 dataset corrupted with MNIST outliers.
Outliers are assigned smaller weights compared to the in-distribution samples,
and there is a clear separation between their corresponding histograms. For
the GAN model trained on the Sketch dataset, we show a visualization of
randomly chosen input samples sorted by their assigned weights in Figure 4(d).
We observe that non-sketch images are assigned low weights while the true
sketch images obtain larger weights. Hence, the weights learnt by our robust
GAN can be a useful indicator for assessing how difficult it is to generate a
given sample.

Table 3: Adaptation accuracy on VISDA-17 using Resnet-50 model averaged over 3
runs

| Method | Accuracy (in $\%$)
---|---|---
| Source Only | 50.7
| DAN [14] | 53.0
| RTN [16] | 53.6
| DANN [10] | 55.0
| JAN-A [17] | 61.6
| GTA [25] | 69.5
| SimNet [22] | 69.6
| CDAN-E [15] | 70.0
Ours | Adversarial (no ent) | 62.9
Robust adversarial (no ent) | 68.6
Adversarial (with ent) | 65.5
Robust adversarial (with ent) | 71.5

Table 4: Adaptation accuracy on VISDA-17 using Resnet-101 model averaged over
3 runs

| Method | Accuracy (in $\%$)
---|---|---
| Source only | 55.3
| DAN [14] | 61.1
| DANN [10] | 57.4
| MCD [23] | 71.9
Ours | Adversarial (no ent) | 65.5
Robust adversarial (no ent) | 69.3
Adversarial (with ent) | 69.3
Robust adversarial (with ent) | 72.7

Table 5: Sensitivity Analysis of $\rho$

GAN exp | $\rho$ | 0 | 0.01 | 0.05 | 0.1 | 0.15
---|---|---|---|---|---|---
CIFAR + MNIST | FID | 37.5 | 34.7 | 31.9 | 29.9 | 30.2
DA exp | $\rho$ | 0.0 | 0.05 | 0.1 | 0.2 | 0.4
Resnet-18 | Acc | 59.5 | 62.8 | 63.1 | 63.9 | 63.6

###  4.2 Domain adaptation

In Unsupervised Domain Adaptation (UDA) problem, we are given a labeled source
dataset and an unlabeled target dataset. The source and target domains have a
covariate shift i.e., the conditional distribution of the data given labels
differ while the marginal distribution of labels match. Due to the covariate
shift, a model trained solely on the source domain performs poorly on the
target. A conventional approach for UDA involves training classification model
on the source domain while minimizing a distributional distance between source
and target feature distributions. Commonly used distance measures include
Wasserstein distance [26] and non-saturating loss [10]. For the ease of
explanation, we use Wasserstein as our choice of distance measure.

Let $\mathbb{P}_{s}=\\{(\mathbf{x}^{s}_{i},y^{s}_{i})\\}_{i=1}^{n_{s}}$ and
$\mathbb{P}_{t}=\\{(\mathbf{x}^{t}_{i})\\}_{i=1}^{n_{t}}$ denote the source
and target distributions, respectively. Let $\mathbf{F}$ denote a feature
network, and $\mathbf{C}$ denote a classifier. Then, the UDA optimization that
minimizes the robust OT distance between source and target feature
distributions can be written as

$\displaystyle\min_{\mathbf{F},\mathbf{C}}~{}\frac{1}{n_{s}}\sum_{i}\mathcal{L}_{cls}(\mathbf{F}(\mathbf{x}_{i}),y_{i})+\lambda\left[\min_{\mathbf{w}\in\Delta^{n_{t}}}\max_{\mathbf{D}}\frac{1}{n_{s}}\sum_{i}\mathbf{D}(\mathbf{F}(\mathbf{x}^{s}_{i}))-\frac{1}{n_{t}}\sum_{j}w_{j}\mathbf{D}(\mathbf{F}(\mathbf{x}^{t}_{j}))\right]$
(10) $\displaystyle\quad\quad\quad\text{ s.t
}\|n_{t}\mathbf{w}-1\|_{2}\leq\sqrt{2\rho n_{t}}$

where $\mathbf{w}=[w_{1},w_{2}\ldots w_{n_{t}}]$. While we describe this
formulation for the Wasserstein distance, similar ideas can be applied to
other adversarial losses. For instance, by replacing the second and third
terms of (10) with binary cross entropy loss, we obtain the non-saturating
objective. Note that we use the discrete formulation of dual objective
(Section 3.2) instead of the continuous one (Section 3.2). This is because in
our experiments, small batch sizes ($\sim 28$) were used due to GPU
limitations. With small batch sizes, continuous relaxation gives sub-optimal
performance.

For experiments, we use VISDA-17 dataset [21], which is a large scale
benchmark dataset for UDA. The task is to perform $12$\- class classification
by adapting models from synthetic to real dataset. In our experiments, we use
non-saturating loss instead of Wasserstein to enable fair comparison with
other adversarial approaches such as DANN. In addition to the adversarial
alignment, we use an entropy regularizer on target logits, which is a standard
technique used in UDA [5]. The adaptation results using Resnet-18, Resnet-50
and Resnet-101 models are shown in Tables 2, 5 and 5, respectively. Our robust
adversarial objective gives consistent performance improvement of
$\mathbf{\sim 5\%}$ over the standard adversarial objective in all
experiments. By using a weighted adversarial loss, our approach assigns low
weights to samples that are hard to adapt and high weights to target samples
that look more similar to source, thereby promoting improved adaptation. Also,
with the use of entropy regularization, our generic robust adversarial
objective reaches performance on par with other competing approaches that are
tuned specifically for the UDA problem. This demonstrates the effectiveness of
our approach.

##### Ablation: Sensitivity of $\rho$

In Table. 5, we report the sensitivity of $\rho$ for both GANs and domain
adaptation experiments. In case of GANs, performance is relatively low only
for very low values of $\rho$ and stable for higher values. For DA,
sensititivity is low in general. For all DA experiments, we used $\rho=0.2$
without tuning it individually for each setting.

##  5 Conclusion

In this work, we study the robust optimal transport which is insensitive to
outliers (samples with large noise) in the data. The applications of previous
formulations of robust OT are limited in practical deep learning problems such
as GANs and domain adaptation due to the instability of their optimization
solvers. In this paper, we derive a computationally efficient dual form of the
robust OT objective that is suited for deep learning applications. We
demonstrate the effectiveness of the proposed method in two applications of
GANs and domain adaptation, where our approach is shown to effectively handle
outliers and achieve good performance improvements.

##  6 Broader Impact

The use of optimal transport (OT) distances such as the Wasserstein distance
have become increasingly popular in machine learning with several applications
in generative modeling, image-to-image translation, inpainting, domain
adaptation, etc. One of the shortcomings of OT is its sensitivity to input
noise. Hence, using OT for large-scale machine learning problems can be
problematic since noise in large datasets is inevitable. Building on
theoretical formulations of unbalanced OT which suffer from computational
instability in deep learning applications, we have developed an efficient
learning method that is provably robust against outliers and is amenable to
complex deep learning applications such as deep generative modeling and domain
adaptation. These attributes ensure broader impacts of this work in both
theoretical and applied machine learning communities and can act as a bridge
between the two. To the best of our knowledge, this work does not lead to any
negative outcomes either in ethical or societal aspects.

##  7 Acknowledgements

This project was supported in part by NSF CAREER AWARD 1942230, a Simons
Fellowship on Deep Learning Foundations, and a MURI program from the Army
Research Office under the grant W911NF17-1-0304.

## References

  * [1] Martin Arjovsky, Soumith Chintala, and L’eon Bottou.  Wasserstein generative adversarial networks.  In Proceedings of the 34nd International Conference on Machine Learning, ICML 2017, Sydney, Australia, 7-9 August, 2017, 2017.
  * [2] Yogesh Balaji, Rama Chellappa, and Soheil Feizi.  Normalized wasserstein for mixture distributions with applications in adversarial learning and domain adaptation.  In The IEEE International Conference on Computer Vision (ICCV), October 2019.
  * [3] Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel PeyrÃ©.  Iterative bregman projections for regularized transportation problems.  SIAM Journal on Scientific Computing, 2015.
  * [4] Nicolas Bonneel, Gabriel Peyré, and Marco Cuturi.  Wasserstein Barycentric Coordinates: Histogram Regression Using Optimal Transport.  ACM Transactions on Graphics (SIGGRAPH 2016), 35(4), 2016.
  * [5] Fabio Maria Carlucci, Lorenzo Porzi, Barbara Caputo, Elisa Ricci, and Samuel Rota Bulo.  Autodial: Automatic domain alignment layers.  In International Conference on Computer Vision (ICCV), 2017.
  * [6] Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavier Vialard.  Unbalanced optimal transport: Dynamic and kantorovich formulation.  arXiv preprint arXiv:1508.05216, 2015.
  * [7] Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavier Vialard.  Scaling algorithms for unbalanced transport problems.  arXiv preprint arXiv:1607.05816, 2016.
  * [8] Marco Cuturi.  Sinkhorn distances: Lightspeed computation of optimal transport.  In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 26, pages 2292–2300. Curran Associates, Inc., 2013.
  * [9] Charlie Frogner, Chiyuan Zhang, Hossein Mobahi, Mauricio Araya, and Tomaso A Poggio.  Learning with a wasserstein loss.  In Advances in Neural Information Processing Systems, pages 2053–2061, 2015.
  * [10] Yaroslav Ganin and Victor Lempitsky.  Unsupervised domain adaptation by backpropagation.  In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 1180–1189, Lille, France, 07–09 Jul 2015\. PMLR.
  * [11] Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville.  Improved training of wasserstein gans.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 5767–5777. Curran Associates, Inc., 2017.
  * [12] Stanislav Kondratyev, Léonard Monsaingeon, Dmitry Vorotnikov, et al.  A new optimal transport distance on the space of finite radon measures.  Advances in Differential Equations, 21(11/12):1117–1164, 2016.
  * [13] Matthias Liero, Alexander Mielke, and Giuseppe Savaré.  Optimal entropy-transport problems and a new hellinger–kantorovich distance between positive measures.  Inventiones mathematicae, 211(3):969–1117, Mar 2018.
  * [14] Mingsheng Long, Yue Cao, Jianmin Wang, and Michael I. Jordan.  Learning transferable features with deep adaptation networks.  In Proceedings of the 32nd International Conference on Machine Learning, pages 97–105, 2015.
  * [15] Mingsheng Long, ZHANGJIE CAO, Jianmin Wang, and Michael I Jordan.  Conditional adversarial domain adaptation.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 1640–1650. Curran Associates, Inc., 2018.
  * [16] Mingsheng Long, Jianmin Wang, and Michael I. Jordan.  Unsupervised domain adaptation with residual transfer networks.  CoRR, abs/1602.04433, 2016.
  * [17] Mingsheng Long, Han Zhu, Jianmin Wang, and Michael I. Jordan.  Deep transfer learning with joint adaptation networks.  In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 2208–2217. PMLR, 2017.
  * [18] Takeru Miyato and Masanori Koyama.  cGANs with projection discriminator.  In International Conference on Learning Representations, 2018.
  * [19] Hongseok Namkoong and John C Duchi.  Stochastic gradient methods for distributionally robust optimization with f-divergences.  In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 2208–2216. Curran Associates, Inc., 2016.
  * [20] Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang.  Moment matching for multi-source domain adaptation.  arXiv preprint arXiv:1812.01754, 2018.
  * [21] Xingchao Peng, Ben Usman, Neela Kaushik, Judy Hoffman, Dequan Wang, and Kate Saenko.  Visda: The visual domain adaptation challenge.  CoRR, abs/1710.06924, 2017.
  * [22] Pedro Oliveira Pinheiro.  Unsupervised domain adaptation with similarity learning.  CoRR, abs/1711.08995, 2017.
  * [23] Kuniaki Saito, Kohei Watanabe, Yoshitaka Ushiku, and Tatsuya Harada.  Maximum classifier discrepancy for unsupervised domain adaptation.  arXiv preprint arXiv:1712.02560, 2017.
  * [24] Maziar Sanjabi, Jimmy Ba, Meisam Razaviyayn, and Jason D Lee.  On the convergence and robustness of training gans with regularized optimal transport.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 7091–7101. Curran Associates, Inc., 2018.
  * [25] Swami Sankaranarayanan, Yogesh Balaji, Carlos D. Castillo, and Rama Chellappa.  Generate to adapt: Aligning domains using generative adversarial networks.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
  * [26] Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu.  Wasserstein distance guided representation learning for domain adaptation.  In AAAI, pages 4058–4065. AAAI Press, 2018.
  * [27] Justin Solomon, Fernando de Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du, and Leonidas J. Guibas.  Convolutional wasserstein distances: efficient optimal transportation on geometric domains.  ACM Trans. Graph., 34(4):66:1–66:11, 2015.
  * [28] Justin Solomon, Raif M. Rustamov, Leonidas J. Guibas, and Adrian Butscher.  Wasserstein propagation for semi-supervised learning.  In ICML, volume 32 of JMLR Workshop and Conference Proceedings, pages 306–314. JMLR.org, 2014.
  * [29] Cédric Villani.  Optimal transport: old and new, volume 338.  Springer Science & Business Media, 2008.
  * [30] Karren D. Yang and Caroline Uhler.  Scalable unbalanced optimal transport using generative adversarial networks.  In International Conference on Learning Representations, 2019.

##  Appendix A Proofs

In this section, we present the proofs:

### Duality:

######  Theorem 3.

Let $\mathbb{P}_{X}$ and $\mathbb{P}_{Y}$ be two distributions defined on a
metric space. The robust Wasserstein measure admits the following dual form

$\displaystyle\mathcal{W}^{rob}_{\rho_{1},\rho_{2}}(\mathbb{P}_{X},\mathbb{P}_{Y})=$
$\displaystyle\min_{\mathbb{P}_{\tilde{X}},\mathbb{P}_{\tilde{Y}}}\max_{k\in
Lip-1}\int D(x)d\mathbb{P}_{\tilde{X}}-\int D(x)d\mathbb{P}_{\tilde{Y}}$ (11)
$\displaystyle\text{ s.t.
}\mathcal{D}_{f}(\mathbb{P}_{\tilde{X}}||\mathbb{P}_{X})\leq\rho_{1},~{}\mathcal{D}_{f}(\mathbb{P}_{\tilde{Y}}||\mathbb{P}_{Y})\leq\rho_{2}.$

##### Proof:

We begin with the primal form of the robust optimal transport defined as

$\displaystyle\mathcal{W}^{rob}_{\rho_{1},\rho_{2}}(\mathbb{P}_{X},\mathbb{P}_{Y})$
$\displaystyle=\min_{\mathbb{P}_{\tilde{X}},\mathbb{P}_{\tilde{Y}}\in
Prob(\mathcal{X})}\min_{\pi}\int\int c(x,y)\pi(x,y)dxdy$ $\displaystyle\text{
s.t.
}\mathcal{D}_{f}(\mathbb{P}_{\tilde{X}}||\mathbb{P}_{X})\leq\rho_{1},~{}\mathcal{D}_{f}(\mathbb{P}_{\tilde{Y}}||\mathbb{P}_{Y})\leq\rho_{2}$
$\displaystyle\quad\quad\int\pi(x.y)dy=\mathbb{P}_{\tilde{X}},\int\pi(x.y)dx=\mathbb{P}_{\tilde{Y}}$

The constraint $\mathbb{P}_{\tilde{X}},\mathbb{P}_{\tilde{Y}}\in
Prob(\mathcal{X})$ states that $\mathbb{P}_{\tilde{X}}$ and
$\mathbb{P}_{\tilde{Y}}$ are valid probability distributions. For brevity, we
shall ignore explicitly stating it in the rest of the proof. Now, we write the
Lagrangian function with respect to marginal constraints.

$\displaystyle L=$
$\displaystyle\min_{\mathbb{P}_{\tilde{X}},\mathbb{P}_{\tilde{Y}}}\min_{\pi>0}\max_{\phi(x),\psi(y)}\int\int
c(x,y)\pi(x,y)dxdy+\int\phi(x)\left(\int\mathbb{P}_{\tilde{X}}-\pi(x,y)dy\right)dx$
$\displaystyle\quad\quad\quad\quad+\int\psi(y)\left(\int\pi(x,y)dx-\mathbb{P}_{\tilde{Y}}\right)dy$
$\displaystyle\text{ s.t.
}\mathcal{D}_{f}(\mathbb{P}_{\tilde{X}}||\mathbb{P}_{X})\leq\rho_{1},~{}\mathcal{D}_{f}(\mathbb{P}_{\tilde{Y}}||\mathbb{P}_{Y})\leq\rho_{2}$
$\displaystyle=$
$\displaystyle\min_{\mathbb{P}_{\tilde{X}},\mathbb{P}_{\tilde{Y}}}\min_{\pi>0}\max_{\phi(x),\psi(y)}\int\int\left[c(x,y)-\phi(x)+\psi(y)\right]\pi(x,y)dxdy+\int\phi(x)d\mathbb{P}_{\tilde{X}}-\int\psi(y)d\mathbb{P}_{\tilde{Y}}$
$\displaystyle\text{ s.t.
}\mathcal{D}_{f}(\mathbb{P}_{\tilde{X}}||\mathbb{P}_{X})\leq\rho_{1},~{}\mathcal{D}_{f}(\mathbb{P}_{\tilde{Y}}||\mathbb{P}_{Y})\leq\rho_{2}$

Since $\pi>0$, we observe that

$\displaystyle
c(x,y)-\phi(x)+\psi(y)=\left\\{\begin{array}[]{ll}\infty&\mbox{if
}c(x,y)-\phi(x)+\psi(y)>0\\\ 0&\mbox{otherwise}\end{array}\right.$

Hence, the dual formulation becomes

$\displaystyle\mathcal{W}^{rob}_{\rho_{1},\rho_{2}}(\mathbb{P}_{X},\mathbb{P}_{Y})$
$\displaystyle=\min_{\mathbb{P}_{\tilde{X}},\mathbb{P}_{\tilde{Y}}}\max_{\phi(x),\psi(y)}\int\phi(x)d\mathbb{P}_{\tilde{X}}-\int\psi(y)d\mathbb{P}_{\tilde{Y}}$
(12) $\displaystyle\text{ s.t. }\phi(x)-\psi(y)\leq c(x,y)$
$\displaystyle~{}~{}\mathcal{D}_{f}(\mathbb{P}_{\tilde{X}}||\mathbb{P}_{X})\leq\rho_{1},~{}\mathcal{D}_{f}(\mathbb{P}_{\tilde{Y}}||\mathbb{P}_{Y})\leq\rho_{2}$

Furthermore, when the distributions lie in a metric space, we can further
simplify this duality. Define

$\displaystyle k(x):=\inf_{y}c(x,y)+\psi(y)$ (13)

Since the feasible set in the dual problem satisfies $\phi(x)-\psi(y)\leq
c(x,y)$, $\phi(x)\leq k(x)$, and by using $y=x$ in Eq (13), we obtain,
$k(x)\leq\psi(x)$. Hence, $\phi(x)\leq k(x)\leq\psi(x)$.

$\displaystyle|k(x)-k(x^{\prime})|$
$\displaystyle=|\inf_{y}[c(x,y)+\psi(y)]-\inf_{y}[c(x^{\prime},y)+\psi(y)]|$
$\displaystyle\leq|c(x,y)-c(x^{\prime},y)|$

Hence, $k(.)$ is $1$-Lipschitz. Using the above inequalities in (12), we
obtain,

$\displaystyle\mathcal{W}^{rob}_{\rho_{1},\rho_{2}}(\mathbb{P}_{X},\mathbb{P}_{Y})~{}\leq$
$\displaystyle\min_{\mathbb{P}_{\tilde{X}},\mathbb{P}_{\tilde{Y}}}\max_{k\in
Lip-1}\int k(x)d\mathbb{P}_{\tilde{X}}-\int k(x)d\mathbb{P}_{\tilde{Y}}$
$\displaystyle\text{ s.t.
}\mathcal{D}_{f}(\mathbb{P}_{\tilde{X}}||\mathbb{P}_{X})\leq\rho_{1},~{}\mathcal{D}_{f}(\mathbb{P}_{\tilde{Y}}||\mathbb{P}_{Y})\leq\rho_{2}$

Also, $\phi(x)=k(x)$ and $\psi(x)=k(x)$ is a feasible solution in optimization
(12). Since (12) maximizes over $\phi(.)$ and $\psi(.)$, we obtain

$\displaystyle\mathcal{W}^{rob}_{\rho_{1},\rho_{2}}(\mathbb{P}_{X},\mathbb{P}_{Y})~{}\geq$
$\displaystyle\min_{\mathbb{P}_{\tilde{X}},\mathbb{P}_{\tilde{Y}}}\max_{k\in
Lip-1}\int k(x)d\mathbb{P}_{\tilde{X}}-\int k(x)d\mathbb{P}_{\tilde{Y}}$
$\displaystyle\text{ s.t
}\mathcal{D}_{f}(\mathbb{P}_{X},\mathbb{P}_{\tilde{X}})\leq\rho_{1},~{}\mathcal{D}_{f}(\mathbb{P}_{Y},\mathbb{P}_{\tilde{Y}})\leq\rho_{2}$

Combining these two inequalities, we obtain

$\displaystyle\mathcal{W}^{rob}_{\rho_{1},\rho_{2}}(\mathbb{P}_{X},\mathbb{P}_{Y})~{}=$
$\displaystyle\min_{\mathbb{P}_{\tilde{X}},\mathbb{P}_{\tilde{Y}}}\max_{k\in
Lip-1}\int k(x)d\mathbb{P}_{\tilde{X}}-\int k(x)d\mathbb{P}_{\tilde{Y}}$ (14)
$\displaystyle\text{ s.t
}\mathcal{D}_{f}(\mathbb{P}_{X},\mathbb{P}_{\tilde{X}})\leq\rho_{1},~{}\mathcal{D}_{f}(\mathbb{P}_{Y},\mathbb{P}_{\tilde{Y}})\leq\rho_{2}$

The above equation is similar in spirit to the Kantrovich-Rubinstein duality.
An important observation to note is that the above optimization only maximizes
over a single discriminator function (as opposed to two functions in
optimization (12)). Hence, it is easier to train it in large-scale deep
learning problems such as GANs.

### Provable robustness:

######  Theorem 4.

Let $\mathbb{P}_{X}$ and $\mathbb{P}_{Y}$ be two distributions such that
$\mathbb{P}_{X}$ is corrupted with $\gamma$ fraction of outliers i.e.,
$\mathbb{P}_{X}=(1-\gamma)\mathbb{P}_{X}^{c}+\gamma\mathbb{P}_{X}^{a}$, where
$\mathbb{P}_{X}^{c}$ is the clean distribution and $\mathbb{P}_{X}^{a}$ is the
outlier distribution. Let
$\mathcal{W}(\mathbb{P}_{X}^{a},\mathbb{P}_{X}^{c})=k\mathcal{W}(\mathbb{P}_{X}^{c},\mathbb{P}_{Y})$,
with $k\geq 1$. Then,

$\displaystyle\mathcal{W}^{rob}_{\rho,0}$
$\displaystyle(\mathbb{P}_{X},\mathbb{P}_{Y})\leq\max\Big{(}1,1+k\gamma-k\sqrt{2\rho\gamma(1-\gamma)}\Big{)}\mathcal{W}(\mathbb{P}_{X}^{c},\mathbb{P}_{Y}).$

##### Proof:

We consider the case of empirical distributions. Let
$\\{\mathbf{x}^{a}_{i}\\}_{i=1}^{n_{a}}$ be the samples in the anomaly
distribution $\mathbb{P}_{X}^{a}$, $\\{\mathbf{x}^{c}_{i}\\}_{i=1}^{n_{c}}$ be
the samples in the clean distribution $\mathbb{P}_{X}^{c}$, and
$\\{\mathbf{y}_{i}\\}_{i=1}^{m}$ be the samples in the distribution
$\mathbb{P}_{Y}$. We also know that $\frac{n_{a}}{n_{a}+n_{c}}=\gamma$.

$\mathcal{W}^{rob}_{\rho,0}(\mathbb{P}_{X},\mathbb{P}_{Y})$ is defined as

$\displaystyle\mathcal{W}^{rob}_{\rho,0}(\mathbb{P}_{X},\mathbb{P}_{Y})=$
$\displaystyle\min_{\mathbb{P}_{\tilde{X}}\in
Prob(\mathcal{X})}\min_{\pi}\sum_{i}\sum_{j}\pi_{ij}c_{ij}$ s.t.
$\displaystyle\sum_{j}\pi_{ij}=\mathbb{P}_{\tilde{X}},~{}~{}\sum_{i}\pi_{ij}=\mathbb{P}_{Y},~{}~{}\mathcal{D}_{\chi^{2}}(\mathbb{P}_{\tilde{X}}||\mathbb{P}_{X})\leq\rho$

Let $\pi^{c*}$ and $\pi^{a*}$ be the optimal transport plans for
$\mathcal{W}(\mathbb{P}_{X}^{c},\mathbb{P}_{Y})$ and
$\mathcal{W}(\mathbb{P}_{X}^{a},\mathbb{P}_{Y})$ respectively. We consider
transport plans of the form $\beta\pi^{a*}+(1-\beta)\pi^{c*}$, for
$\beta\in[0,1]$. The marginal constraints can then be written as

$\displaystyle\int\beta\pi^{a*}+(1-\beta)\pi^{c*}dx$
$\displaystyle=\beta\mathbb{P}_{X}^{a}+(1-\beta)\mathbb{P}_{X}^{c}$
$\displaystyle\int\beta\pi^{a*}+(1-\beta)\pi^{c*}dy$
$\displaystyle=\mathbb{P}_{Y}$

For this to be a feasible solution for
$\mathcal{W}^{rob}_{\rho,0}(\mathbb{P}_{X},\mathbb{P}_{Y})$, we require

$\displaystyle\mathcal{D}_{\chi^{2}}(\beta\mathbb{P}_{X}^{a}+(1-\beta)\mathbb{P}_{X}^{c}||\gamma\mathbb{P}_{X}^{a}+(1-\gamma)\mathbb{P}_{X}^{c})\leq\rho$

The distribution $\beta\mathbb{P}_{X}^{a}+(1-\beta)\mathbb{P}_{X}^{c}$ can be
characterized as

$[\underbrace{\frac{\beta}{n_{a}},\ldots}_{n_{a}\text{ terms
}}~{},\underbrace{\frac{1-\beta}{n_{c}},\ldots}_{n_{c}\text{ terms }}].$

Using this, the above constraint can be written as

$\displaystyle(\beta-\gamma)^{2}\leq 2\rho\gamma(1-\gamma)$ (15)

Hence, all transport plans of the form $\beta\pi^{a*}+(1-\beta)\pi^{c*}$ are
feasible solutions of
$\mathcal{W}^{rob}_{\rho,0}(\mathbb{P}_{X},\mathbb{P}_{Y})$ if $\beta$
satisfies $(\beta-\gamma)^{2}\leq 2\rho\gamma(1-\gamma)$. Therefore, we have:

$\displaystyle\mathcal{W}^{rob}_{\rho,0}(\mathbb{P}_{X},\mathbb{P}_{Y})\leq$
$\displaystyle\min_{\beta}\sum_{i}\sum_{j}c_{i,j}[\beta\pi^{a*}_{i,j}+(1-\beta)\pi^{c*}_{i,j}]$
$\displaystyle\leq$
$\displaystyle\min_{\beta}\beta\mathcal{W}(\mathbb{P}_{X}^{a},\mathbb{P}_{Y})+(1-\beta)\mathcal{W}(\mathbb{P}_{X}^{c},\mathbb{P}_{Y})$
$\displaystyle\text{ s.t. }(\beta-\gamma)^{2}\leq 2\rho\gamma(1-\gamma)$

By the assumption, we have:

$\displaystyle\mathcal{W}(\mathbb{P}_{X}^{c},\mathbb{P}_{X}^{a})$
$\displaystyle=k\mathcal{W}(\mathbb{P}_{X}^{c},\mathbb{P}_{Y})$
$\displaystyle\mathcal{W}(\mathbb{P}_{X}^{a},\mathbb{P}_{Y})$
$\displaystyle\leq\mathcal{W}(\mathbb{P}_{X}^{a},\mathbb{P}_{X}^{c})+\mathcal{W}(\mathbb{P}_{X}^{c},\mathbb{P}_{Y})$
$\displaystyle\leq(k+1)\mathcal{W}(\mathbb{P}_{X}^{c},\mathbb{P}_{Y})$

Hence,

$\displaystyle\mathcal{W}^{rob}_{\rho,0}(\mathbb{P}_{X},\mathbb{P}_{Y})\leq$
$\displaystyle\min_{\beta}(1+\beta
k)\mathcal{W}(\mathbb{P}_{X}^{c},\mathbb{P}_{Y})$ $\displaystyle\text{ s.t.
}(\beta-\gamma)^{2}\leq 2\rho\gamma(1-\gamma)$

The smallest value $\beta$ can take is $\gamma-\sqrt{2\rho\gamma(1-\gamma)}$.
This gives

$\displaystyle\mathcal{W}^{rob}_{\rho,0}(\mathbb{P}_{X},\mathbb{P}_{Y})\leq\max\Big{(}1,1+k\gamma-k\sqrt{2\rho\gamma(1-\gamma)}\Big{)}\mathcal{W}(\mathbb{P}_{X}^{c},\mathbb{P}_{Y})$

##### Note:

The transport plan $\beta\pi^{a*}+(1-\beta)\pi^{c*}$ is not the the optimal
transport plan for the robust OT optimization between corrupted distribution
$\mathbb{P}_{X}$ and $\mathbb{P}_{Y}$. However, this plan is a “feasible”
solution that satisfies the constraints of the robust OT. Hence, the cost
obtained by this plan is an upper bound to the true robust OT cost.

##  Appendix B Practical Issues with Unbalanced Optimal Transport Dual

###  B.1 Dual Objective

The primal form of unbalanced OT [13, 6] is given by

$\displaystyle\mathcal{W}^{ub}(\mathbb{P}_{X},\mathbb{P}_{Y})$
$\displaystyle=\min_{\pi\in\Pi(\mathbb{P}_{\tilde{X}},\mathbb{P}_{\tilde{Y}})}\int
c(x,y)\pi(x,y)dxdy+\mathcal{D}_{f}(\mathbb{P}_{\tilde{X}}||\mathbb{P}_{X})+\mathcal{D}_{f}(\mathbb{P}_{\tilde{Y}}||\mathbb{P}_{Y})$
(16)

where $\mathcal{D}_{f}$ is the $f$-divergence between distributions, defined
as $\mathcal{D}_{f}(P||Q)=\int f(\frac{dP}{dQ})dQ$. Furthermore, the authors
of [13] derived a dual form for the problem. Let $f$ be a convex lower semi-
continuous function. Define $r^{*}(x):=\sup_{s>0}\frac{x-f(s)}{s}$ where
$f^{\prime}_{\infty}:=\lim_{s\to\infty}\frac{f(s)}{s}$. Then,

$\displaystyle\mathcal{W}^{ub}(\mathbb{P}_{X},\mathbb{P}_{Y})$
$\displaystyle=\max_{\phi,\psi}\int\phi(x)d\mathbb{P}_{X}+\int\psi(y)d\mathbb{P}_{Y}$
(17) $\displaystyle\text{ s.t. }r^{*}(\phi(x))+r^{*}(\psi(y))\leq c(x,y)$

In our case, $f(x)=(x-1)^{2}/2$. Let us now, write the dual for this case.
First, we need to find $r^{*}(x)$ for this function.

$\displaystyle r^{*}(x)$ $\displaystyle=\sup_{s>0}\frac{x-f(s)}{s}$
$\displaystyle=\sup_{s>0}\frac{x-(s-1)^{2}/2}{s}$
$\displaystyle=\sup_{s>0}\frac{2x-1-s^{2}+2s}{2s}$
$\displaystyle=\sup_{s>0}\frac{2x-1}{2s}-\frac{s}{2}+1$

We consider three cases:

##### Case 1: $x>1/2$.

In this case, $r^{*}(x)\to\infty$ as $s\to 0^{+}$.

##### Case 2: $x=1/2$.

In this case, $r^{*}(x)=1$.

##### Case 3: $x<1/2$.

In this case, for $s\to 0^{+}$, $r^{*}(x)\to-\infty$. Also, when $s\to\infty$,
$r^{*}(x)\to-\infty$. So, the maximizer has to lie somewhere in $(0,\infty)$.

Taking the derivative w.r.t. $s$, we obtain,

$\displaystyle\frac{1-2x}{2s^{2}}-\frac{1}{2}=0$

This gives

$\displaystyle s=\sqrt{1-2x}$

The second derivative is also negative at this point. Hence, it is the
maximizer point. Substituting this in $r^{*}(\cdot)$, we obtain

$\displaystyle r^{*}(x)=1-\sqrt{1-2x}$

This gives the solution,

$\displaystyle r^{*}(x)=\begin{cases}\infty&x>1/2\\\ 1-\sqrt{1-2x}&x\leq
1/2\end{cases}$

Hence, the dual form becomes

$\displaystyle\mathcal{W}^{ub}(\mathbb{P}_{X},\mathbb{P}_{Y})$
$\displaystyle=\max_{\phi,\psi}\int\phi(x)d\mathbb{P}_{X}+\int\psi(y)d\mathbb{P}_{Y}$
(18) $\displaystyle\text{ s.t. }1-\sqrt{1-2\phi(x)}+1-\sqrt{1-2\psi(y)}\leq
c(x,y)$ $\displaystyle~{}~{}~{}~{}\phi(x)\leq 1/2,~{}~{}\psi(y)\leq 1/2$

###  B.2 Practical Implementation and Training Issues

To simplify notation, we make a substitution $\mathbf{D}_{1}(x)\leftarrow
2\phi(x)$ and $\mathbf{D}_{2}(x)\leftarrow 2\psi(x)$ in (18). This gives

$\displaystyle\mathcal{W}^{ub}(\mathbb{P}_{X},\mathbb{P}_{Y})$
$\displaystyle=\max_{\mathbf{D}_{1},\mathbf{D}_{2}}\int\mathbf{D}_{1}(x)d\mathbb{P}_{X}+\int\mathbf{D}_{2}(y)d\mathbb{P}_{Y}$
(19) $\displaystyle\text{ s.t.
}1-\sqrt{1-\mathbf{D}_{1}(x)}+1-\sqrt{1-\mathbf{D}_{2}(y)}\leq c(x,y)$
$\displaystyle~{}~{}~{}~{}\mathbf{D}_{1}(x)\leq 1,~{}~{}\mathbf{D}_{2}(y)\leq
1$

Then, the second set of constraints (i.e. $\mathbf{D}_{1}(x)$ and
$\mathbf{D}_{2}(y)$ to be less or equal to one) can be integrated into the
network design. The first constraint can be implemented using a Lagrangian
constraint. This leads us to the following objective:

$\displaystyle\min_{\mathbf{G}}\max_{\mathbf{D}_{1},\mathbf{D}_{2}\leq 1}$
$\displaystyle\mathbb{E}_{\mathbf{x}\sim
p_{data}}\mathbf{D}_{1}(\mathbf{x})+\mathbb{E}_{\mathbf{z}\sim
p_{z}}\mathbf{D}_{2}(\mathbf{G}(\mathbf{z}))$ (20)
$\displaystyle-\lambda\mathbb{E}_{\mathbf{x},\mathbf{z}}\left[\max\left(\sqrt{1-\mathbf{D}_{1}(\mathbf{x})}+\sqrt{1-\mathbf{D}_{2}(\mathbf{G}(\mathbf{z}))}+c(\mathbf{x},\mathbf{G}(\mathbf{z}))-2,0\right)\right]$

The constraint $\mathbf{D}_{1},\mathbf{D}_{2}\leq 1$ means
$\mathbf{D}_{1}(\mathbf{x})\leq 1,\mathbf{D}_{2}(\mathbf{x})\leq
1,\forall\mathbf{x}$. We trained a model using this dual objective on CIFAR-10
dataset using Resnet architecture for generator and discrminator network.
However, partially due to the presence of two discriminator networks
$\mathbf{D}_{1}$ and $\mathbf{D}_{2}$, the training is challenging. Similar
training difficulties in GANs with multiple discriminator networks have been
observed in [24]. Even with a sweep of hyper-parameters, we were not able to
make the model based on optimization 20 to converge to a proper solution.

Training loss curves of our model vs. that of unbalanced OT are shown in
Figure. 5. Samples generated by our dual and unbalanced OT dual is shown in
Figure. 6. We observe that the model trained using the Unbalanced OT dual
produces loss curve that is flat and does not learn a proper solution. This is
also evident from Figure. 6. Models trained using our dual generates CIFAR-
like samples, while the one trained with unbalanced OT dual produces noisy
images.

(a) Our dual

(b) Unbalanced Optimal Transport dual

Figure 5: Loss curves of training GANs using practical implementations of our
proposed dual vs. the dual of Unbalanced OT. Our model converges to a proper
solution while the model trained using the dual of unbalanced OT does not
converge to a good solution.

(a) Our dual

(b) Unbalanced Optimal Transport dual

Figure 6: Samples generated by our dual and Unbalanced OT dual.

##  Appendix C Choosing $\rho$ and the tightness of the bound

The constant $\rho$ in our formulation is a hyper-parameter that needs to be
estimated. The value of $\rho$ denotes the extent of marginal relaxation. In
applications such as GANs or domain adaptation, performance on a validation
set can be used for choosing $\rho$. In the absence of validation set, we
present two techniques for estimating $\rho$.

##### When outlier fraction is known:

When the outlier fraction $\gamma$ is known, a good estimate of $\rho$ is
$\rho=\gamma/2(1-\gamma)$. Below we explain this claim.

Ideally, we desire the perturbed distribution $\mathbb{P}_{\tilde{X}}$ to be
such that

$\mathbb{P}_{\tilde{X}}=[\underbrace{\kappa,\kappa,\ldots\kappa}_{\text{normal
samples}}~{},\underbrace{0,0,\ldots 0}_{\text{outlier samples}}].$

Since the outlier fraction is $\gamma$, the number of normal samples is
$(1-\gamma)n$ and the number of outlier samples is $\gamma n$. For
$\mathbb{P}_{\tilde{X}}$ to be a valid pmf, we require,

$\displaystyle\kappa(1-\gamma)n=1$ $\displaystyle\kappa=\frac{1}{(1-\gamma)n}$

Also, we have a constraint on $f$-divergence to ensure
$\mathcal{D}_{\chi^{2}}(\mathbb{P}_{\tilde{X}}||\mathbb{P}_{X})\leq\rho$. This
condition simplifies to

$\displaystyle\frac{1}{2}\left[\frac{(\alpha-1/n)^{2}}{1/n}(1-\gamma)n+\frac{(0-1/n)^{2}}{1/n}\gamma
n\right]\leq\rho$

Therefore, we obtain

$\displaystyle\rho\geq\frac{\gamma}{1-\gamma}$

Hence, to get a proper estimate of the robust Wasserstein distance, we choose
$\rho=\gamma/2(1-\gamma)$. Note that by substituting $\rho=\gamma/2(1-\gamma)$
in Theorem 1, we obtain,
$\mathcal{W}^{rob}_{\rho,0}(\mathbb{P}_{X},\mathbb{P}_{Y})\leq\mathcal{W}(\mathbb{P}_{X},\mathbb{P}_{Y})$.

##### Heuristic:

In general, estimating $\rho$ is non-trivial. We now present a heuristic that
can be used for this purpose. First, we compute robust OT measure for various
values of $\rho$. This curve has an elbow shape, and its point of inflection
can be used as an estimate of $\rho$. We demonstrate this with an example. We
use the mixture of four Gaussians datasets as shown in Figure 1 of the main
paper as our input distributions. The means of the Gaussians are placed in a
circumference of a circle, with two distributions being the rotated versions
of each other. We introduce $5\%$ outlier samples in one distribution. A plot
of robust Wasserstein measure varying $\rho$ is shown in Fig. 7 (in blue). We
observe that initially as $\rho$ increases, the robust OT value decreases
sharply followed by a gradual descent, resembling the pattern of the elbow
curve in $k$-means clustering. The point of inflection in this elbow curve is
a proper estimate of $\rho$.

Figure 7: Plot of robust OT estimate for different values of $\rho$

##### Tightness of the upper bound:

In Figure. 7, we plot the upper bound of the robust OT estimate as given by
Theorem 4 in red. We observe that the upper bound is fairly tight in this
case. It closely approximates the true robust OT measure given by the blue
curve.

Table 6: Analyzing mode drop: Training robust GAN on imbalanced CelebA. Each
column denotes an experiment where GAN models are trained on input dataset
having the respective fraction of males as given in row 1. Rows 2 and 3 denote
the fraction of males in the generated dataset obtained by training Vanilla
and Robust GAN respectively. We observe that images of males are generated
even when the fraction of males in the input dataset is as low as $2\%$.

Model | Fraction of males (in $\%$)
---|---
Input dataset | 2.00 | 5.00 | 10.00 | 20.00
Vanilla GAN | 5.23 | 7.42 | 12.16 | 21.29
Robust GAN | 4.84 | 7.80 | 10.12 | 21.51

##  Appendix D Biases And Mode Drop

The model of outliers we assume in our paper is that of large noise (Section
3). Hence, our model drops samples that are far from the true data
distrubution in the Wasserstein sense. It is important that these dropped
samples do not correspond to rare modes in the dataset, or have a mechanism to
identify such mode dropping when it happens. In Table. 2, we observe no drop
in FID scores on clean CIFAR-10 dataset, which suggests that no mode drop has
occured. To further understand if biases in the dataset are exacerbated, we
train our robust Wasserstein GAN model on CelebA dataset with varying
male:female ratio. We then measure the male:female ratio of the generated
distribution obtained from the trained GAN (using an attribute classifier).
Table 6 shows the results. We observe that even when fraction of males in the
input dataset are as low as $2\%$, images of males are generated in robust GAN
model. This indicates that rare modes are not dropped. Instead, our robust GAN
model drops samples having large noise.

##### Identifying mode drop:

In some cases, as pointed by the reviewer, rare modes can potentially be
dropped. In this case, we can use the weights estimated by our weight network
$\mathbf{W}(x)$ to visualize which modes are dropped (Fig 3 and 4 of the main
paper). Samples with low weights are the ones that are dropped. We can use
these weights in a boosting framework to train a mixture model to generate
balanced datasets. This is a topic of future research.

##  Appendix E Properties of Robust OT

For a measure to be a distance metric, it has to satisfy four propeties of
non-negativity, identity, symmetry and triangle inequality.

##### Non-negativity

Robust Wasserstein measure
$\mathcal{W}^{rob}_{\rho_{1},\rho_{2}}(\mathbb{P}_{X},\mathbb{P}_{Y})$ is non-
negative. By definition,

$\displaystyle\mathcal{W}^{rob}_{\rho_{1},\rho_{2}}(\mathbb{P}_{X},\mathbb{P}_{Y}):=$
$\displaystyle\min_{\mathbb{P}_{\tilde{X}},\mathbb{P}_{\tilde{Y}}\in
Prob(\mathcal{X})}~{}\min_{\pi\in\Pi(\mathbb{P}_{\tilde{X}},\mathbb{P}_{\tilde{Y}})}\int\int
c(x,y)\pi(x,y)dxdy$ $\displaystyle\text{ s.t.
}\mathcal{D}_{f}(\mathbb{P}_{\tilde{X}}||\mathbb{P}_{X})\leq\rho_{1},~{}\mathcal{D}_{f}(\mathbb{P}_{\tilde{Y}}||\mathbb{P}_{Y})\leq\rho_{2}.$

Since the cost function $c(.)$ and the transportation map $\pi(.)$ are non-
negative, the robust OT measure is non-negative.

##### Identity:

Robust Wasserstein measure satisfies identity. In other words,
$\mathcal{W}^{rob}_{\rho_{1},\rho_{2}}(\mathbb{P}_{X},\mathbb{P}_{X})=0$. To
prove this, consider the following solution: $\pi(x,y)=1$ if $x=y$, and
$\pi(x,y)=0$ otherwise, $\mathbb{P}_{\tilde{X}}=\mathbb{P}_{X}$ and
$\mathbb{P}_{\tilde{Y}}=\mathbb{P}_{Y}$. Clearly, this is a feasible solution.
Also, under this solution, the OT cost is $0$ as $c(x,x)=0$. Since, robust OT
is non-negative, this is the optimal solution.

##### Symmetry:

In general, robust Wasserstein is not symmetric
$\mathcal{W}^{rob}_{\rho_{1},\rho_{2}}(\mathbb{P}_{X},\mathbb{P}_{Y})=0\neq\mathcal{W}^{rob}_{\rho_{1},\rho_{2}}(\mathbb{P}_{Y},\mathbb{P}_{X})=0$.
This is because when $\rho_{1}\neq\rho_{2}$, different $f$-divergence
constraints are imposed on the two marginals leading to different solutions.
However, $\mathcal{W}^{rob}_{\rho,\rho}(\mathbb{P}_{X},\mathbb{P}_{Y})$ is
symmetric. This is because $\int\int c(x,y)\pi(x,y)dxdy=\int\int
c(y,x)\pi(y,x)dydx$, and constraints on two marginals are the same for both
optimization problems
$\mathcal{W}^{rob}_{\rho,\rho}(\mathbb{P}_{X},\mathbb{P}_{Y})$ and
$\mathcal{W}^{rob}_{\rho,\rho}(\mathbb{P}_{Y},\mathbb{P}_{X})$.

##### Triangle inequality:

$\mathcal{W}^{rob}_{\rho_{1},\rho_{2}}(\mathbb{P}_{X},\mathbb{P}_{Y})$ does
not satisfy triangle inequality.

##  Appendix F Experiments

###  F.1 Generative modeling

The formulation of robust Wasserstein GAN is discussed in Section 5 of the
main paper. The idea is to modulate the discriminator loss using a weight
network $\mathbf{W}(.)$. The output of the $\mathbf{W}(.)$ has a ReLU
transform to make it non-negative, and for each batch, the weights are
normalized to satisfy
$\mathbb{E}_{\mathbf{x}\in\mathbb{P}_{X}}[\mathbf{W}(\mathbf{x})]=1$. Then,
the objective of robust Wasserstein GAN can be written as

##### Robust Wasserstein GAN:

$\displaystyle\min_{\mathbf{W},\mathbf{G}}~{}\max_{\mathbf{D}\in
Lip-1}\mathbb{E}_{\mathbf{x}\sim\mathbb{P}_{X}}\left[\mathbf{W}(\mathbf{x})\mathbf{D}(\mathbf{x})\right]-\mathbb{E}_{\mathbf{z}}\left[\mathbf{D}(\mathbf{G}(\mathbf{z}))\right]+\lambda\max\left(\mathbb{E}_{\mathbf{x}\sim\mathbb{P}_{X}}[(\mathbf{W}(\mathbf{x})-1)^{2}]-2\rho,0\right)$
(21)

We can similarly extend the robust GAN formulations to other GAN variants such
as spectral normalization GAN or non-saturating GAN as follows.

##### Robust Non-saturating GAN:

$\displaystyle\min_{\mathbf{W},\mathbf{G}}~{}\max_{\mathbf{D}}\mathbb{E}_{\mathbf{x}\sim\mathbb{P}_{X}}[\mathbf{W}(\mathbf{x})\log(\mathbf{D}(\mathbf{x}))]+\mathbb{E}_{\mathbf{z}}[\log(1-\mathbf{D}(\mathbf{G}(\mathbf{z})))]+\lambda\max\left(\mathbb{E}_{\mathbf{x}\sim\mathbb{P}_{X}}[(\mathbf{W}(\mathbf{x})-1)^{2}]-2\rho,0\right)$
(22)

##### Robust Spectral Normalization GAN:

$\displaystyle\min_{\mathbf{W},\mathbf{G}}~{}\max_{\mathbf{D}}\mathbb{E}_{\mathbf{x}\sim\mathbb{P}_{X}}$
$\displaystyle[\mathbf{W}(\mathbf{x})\max(1-\mathbf{D}(\mathbf{x}),0)]+\mathbb{E}_{\mathbf{z}}[\max(1+\mathbf{D}(\mathbf{G}(\mathbf{z})),0)]$
$\displaystyle+\lambda\max\left(\mathbb{E}_{\mathbf{x}\sim\mathbb{P}_{X}}[(\mathbf{W}(\mathbf{x})-1)^{2}]-2\rho,0\right)$
(23)

Algorithm 1 Robust Wasserstein GAN training algorithm

1:$N_{iter}$: Number of training iterations, $N_{critic}$: Number of critic
iterations, $N_{batch}$: Batch size, $N_{weight}$: Number of weight update
iterations

2:for $t$ in $1:N_{iter}$ do

3: Sample a batch of real samples
$\\{\mathbf{x}_{i}\\}_{i=1}^{N_{batch}}\sim\mathcal{D}$

4: Sample a batch of noise vectors
$\\{\mathbf{z}_{i}\\}_{i=1}^{N_{batch}}\sim\mathcal{D}$

5: Normalize weight vectors as
$\mathbf{W}(\mathbf{x}_{i})\leftarrow\mathbf{W}(\mathbf{x}_{i})/\sum_{i=1}^{N_{batch}}\mathbf{W}(\mathbf{x}_{i})$

6: Obtain GAN loss as  $\displaystyle\mathcal{L}_{GAN}=$
$\displaystyle\frac{1}{N_{batch}}\sum_{i}\mathbf{W}(\mathbf{x}_{i})\mathbf{D}(\mathbf{x}_{i})-\frac{1}{N_{batch}}\sum_{i}\mathbf{D}(\mathbf{G}(\mathbf{z}_{i}))$
$\displaystyle+\lambda\max\left(\frac{1}{N_{batch}}\sum_{i}[(\mathbf{W}(\mathbf{x}_{i})-1)^{2}]-2\rho,0\right)+\lambda_{GP}\frac{1}{N_{batch}}\sum_{i}(\|\mathbf{D}(\hat{\mathbf{x}_{i}})\|-1)^{2}$

7: Update discriminator as
$\mathbf{D}\leftarrow\mathbf{D}+\eta_{D}\nabla_{\mathbf{D}}\mathcal{L}_{GAN}$

8: if $t~{}\%N_{weight}==0$ then

9: Update weight network as
$\mathbf{W}\leftarrow\mathbf{W}-\eta_{w}\nabla_{\mathbf{W}}\mathcal{L}_{GAN}$

10: end if

11: if $t~{}\%N_{critic}==0$ then

12: Update generator as
$\mathbf{G}\leftarrow\mathbf{G}-\eta_{g}\nabla_{\mathbf{G}}\mathcal{L}_{GAN}$

13: end if

14:end for

Figure 8: Visualizing samples generated on CIFAR-10 dataset corrupted with
MNIST outliers. Figure 9: Visualizing samples generated on CIFAR-10 dataset
corrupted with uniform noise outliers.

In what follows, we provide more details on the experimental settings used in
main paper.

####  F.1.1 Dataset with outliers

In Section 5.1.1 of the main paper, we show experiments on CIFAR-10 dataset
artificially corrupted with MNIST and uniform noise outliers. Each experiment
is conducted with a different outlier fraction $\gamma$. For a given $\gamma$,
the outlier-corrupted dataset is constructed so that outliers occupy $\gamma$
fraction of samples. In all experiments, the total size of the dataset
(including outliers) was maintained as $50000$. All models were trained using
robust Wasserstein loss given in Eq. (21). Experiments were performed on two
architectures - DCGAN and Resnet.

For quantitative evaluation, FID scores with respect to clean CIFAR-10 dataset
are reported. That is, let $m_{c}$ and $C_{c}$ denote the mean and covariance
matrices of Inception network features obtained from clean CIFAR-10 dataset
(CIFAR-10 without outliers), and $m$ and $C$ denote the mean and covariance of
Inception network features obtained from generated samples. Then, the FID
score is computed as

$\displaystyle
FID=\|m-m_{c}\|_{2}^{2}+Tr\left(C+C_{c}-2(CC_{c})^{1/2}\right).$

To compute the FID score, the mean and covariance matrices were computed over
$50000$ samples.

On sketch domain on DomainNet dataset, robust spectral normalization GAN (Eq.
(F.1)) was trained. Resnet architectures were used for both discriminator and
generator.

Table 7: Architectures and hyper-parameters: Resnet model Generator | Discriminator
---|---
$z\in\mathbb{R}^{128}\sim\mathcal{N}(0,1)$ | Input $\mathbf{x}\in\mathbb{R}^{32\times 32\times 3}$
Dense, $4\times 4\times 128$ | ResBlock down $128$
ResBlock up $128$ | ResBlock down $128$
ResBlock up $128$ | ResBlock $128$
ResBlock up $128$ | ResBlock $128$
BN, ReLU, Conv $3\times 3$ | ReLU, Global sum pooling
Tanh | Dense $\to 1$
Hyperparameters
Generator learning rate | $0.0002$
Discriminator learning rate | $0.0002$
Weight net learning rate | $0.0002$
Generator optimizer | Adam, Betas $(0.0,0.999)$
Discriminator optimizer | Adam, Betas $(0.0,0.999)$
Weight net optimizer | Adam, Betas $(0.0,0.999)$
Number of critic iterations | 5
Weight update iterations | 5
Gradient penalty | 10
Batch size | 128
Table 8: Architectures and hyper-parameters: DCGAN model Generator | Discriminator
---|---
$z\in\mathbb{R}^{128}\sim\mathcal{N}(0,1)$ | Input $\mathbf{x}\in\mathbb{R}^{32\times 32\times 3}$
Dense, $4\times 4\times 512$ \+ BN + ReLU | Conv $3\times 3$, str $1$, ($64$) + LReLU
ConvTranspose $4\times 4$, str $2$, $(256)$ \+ BN + ReLU | Conv $4\times 4$, str $2$, $(128)$ \+ BN + LReLU
ConvTranspose $4\times 4$, str $2$, $(128)$ \+ BN + ReLU | Conv $4\times 4$, str $2$, $(256)$ \+ BN + LReLU
ConvTranspose $4\times 4$, str $2$, $(64)$ \+ BN + ReLU | Conv $4\times 4$, str $2$, $(512)$ \+ BN + LReLU
Conv $3\times 3$, str $1$, $(3)$ \+ TanH | Conv $4\times 4$, str $1$, $(1)$
Hyperparameters
Generator learning rate | $0.0001$
Discriminator learning rate | $0.0001$
Weight net learning rate | $0.0001$
Generator optimizer | Adam, Betas $(0.5,0.9)$
Discriminator optimizer | Adam, Betas $(0.5,0.9)$
Weight net optimizer | Adam, Betas $(0.5,0.9)$
Number of critic iterations | 5
Weight update iterations | 5
Gradient penalty | 10
Batch size | 128
Table 9: Architectures of weight network Weight network
---
Input $\mathbf{x}\in\mathbb{R}^{32\times 32\times 3}$
Conv $3\times 3$, str $1$, ($64$) + ReLU + Maxpool($2\times 2$)
Conv $3\times 3$, str $1$, ($128$) + ReLU + Maxpool($2\times 2$)
Conv $3\times 3$, str $1$, ($256$) + ReLU + Maxpool($2\times 2$)
Conv $4\times 4$, str $1$, $(1)$

####  F.1.2 Clean datasets

In Section 5.1.2 of the main paper, robust Wasserstein GANs were trained on
clean datasets (datasets with no outlier noise). Expeirments were performed on
CIFAR-10 and CIFAR-100 datasets. On CIFAR-10, unconditional model was trained,
whereas on CIFAR-100, conditional GAN using conditional batch normalization
(similar to [18]) was trained.

####  F.1.3 Architectures and Hyper-parameters

Models and hyperparameters used for DCGAN and Resnet models are provided in
Tables 7 and 8. For both models, the architecture used for the weight network
is provided in Table 9.

###  F.2 Domain Adaptation

In all domain adaptation experiments, we update the weight vectors using
discrete optimzation version discussed in Section 4.3.1 of the main paper. For
all models, an entropy regularization on target logits is used. A complete
algorithm is provided in Alg. 2. We evaluate our approach on VISDA-17 dataset
using Resnet-18, 50 and 101 architectures as discussed in Section 5.2 of the
main paper.

Algorithm 2 Domain adaptation training algorithm

1:$N_{iter}$: Number of training iterations, $N_{critic}$: Number of critic
iterations, $N_{batch}$: Batch size, $N_{weight}$: Number of weight update
iterations

2:Intialize weight bank $\mathbf{w}_{b}=[w_{1},w_{2},\ldots w_{N_{t}}]$ ,
where each $w_{i}$ corresponds to weight of target $\mathbf{x}^{t}_{i}$

3:for $t$ in $1:N_{iter}$ do

4: Sample a batch of labeled source images
$\\{\mathbf{x}^{s}_{i},y^{s}_{i}\\}_{i=1}^{N_{batch}}\sim\mathcal{D}_{s}$ and
unlabeled target images
$\\{\mathbf{x}^{t}_{i}\\}_{i=1}^{N_{batch}}\sim\mathcal{D}_{t}$

5: Obtain the weight vectors $w^{t}_{i}$ corresponding to the target samples
$\mathbf{x}^{t}_{i}$ from the weight bank $\mathbf{w}_{b}$

6: Obtain discriminator loss as
$\displaystyle\mathcal{L}_{disc}=\frac{1}{N_{batch}}\sum_{i}L_{BCE}(\mathbf{D}(\mathbf{F}(\mathbf{x}^{s}_{i})),0)+\frac{1}{N_{batch}}\sum_{i}w^{t}_{i}L_{BCE}(\mathbf{D}(\mathbf{F}(\mathbf{x}^{t}_{i})),1)$

7: Obtain source label prediction loss as
$\displaystyle\mathcal{L}_{cls}=\frac{1}{N_{batch}}\sum_{i}L_{CE}(\mathbf{C}(\mathbf{F}(\mathbf{x}^{s}_{i})),y^{s}_{i})$

8: Update discriminator
$\mathbf{D}\leftarrow\mathbf{D}-\eta_{d}\nabla_{\mathbf{D}}\mathcal{L}_{disc}$

9: Update feature network and classifier
$\mathbf{F}\leftarrow\mathbf{F}-\eta_{f}\nabla_{\mathbf{F}}\mathcal{L}_{cls}$,
$~{}\mathbf{C}\leftarrow\mathbf{C}-\eta_{c}\nabla_{\mathbf{C}}\mathcal{L}_{cls}$

10: if $t~{}\%N_{weight}==0$ then

11: Update weight bank $\mathbf{w}_{b}$ using Algorithm 3

12: end if

13: if $t~{}\%N_{critic}==0$ then

14: Update feature network as
$\mathbf{F}\leftarrow\mathbf{F}+\eta_{f}\nabla_{\mathbf{F}}\mathcal{L}_{disc}$

15: end if

16:end for

Algorithm 3 Algorithm for updating weights

1:Form the discriminator vector
$\mathbf{d}=[\mathbf{D}(\mathbf{x}^{t}_{1}),\mathbf{D}(\mathbf{x}^{t}_{2}),\ldots\mathbf{D}(\mathbf{x}^{t}_{N_{t}})]$

2:Obtain $\mathbf{w}_{b}$ as the solution of the following second-order cone
program  $\displaystyle\min_{\mathbf{w}}$
$\displaystyle(\mathbf{w})^{t}\mathbf{d}$ s.t
$\displaystyle\left\|\mathbf{w}-1\right\|_{2}\leq\sqrt{2\rho_{1}N_{t}}$
$\displaystyle\mathbf{w}\geq 0,~{}(\mathbf{w})^{t}\mathbf{1}=N_{t}$

3:Return $\mathbf{w}_{b}$

##### Baselines:

Two standard baselines for the domain adaptation problem include source only
and Adversarial alignment. In the source only model, the feature network
$\mathbf{F}$ and the classifier $\mathbf{C}$ are trained only on the labeled
source dataset. In the adversarial alignment, domain discrepancy between
source and target feature distributions is minimized in addition to the source
classification loss. This is essentially an unweighted version of our
adaptation objective.

##### Architectures:

In our experiments, the feature network $\mathbf{F}$ is implemented using
Resnet architectures (Resnet-18, 50 and 101). Following the usual transfer
learning paradigm, the last linear layer is removed in the Resnet network. The
feature network is intialized with weights pretrained on Imagenet. The
classifier network $\mathbf{C}$ is a linear layer mapping the features to
probability vector with dimension equal to the number of classes. The
classifier network is trained from scratch. The discriminator is realized as a
3-layer MLP with ReLU non-linearities and hidden layer dimension $256$.
Spectral normalization is used on the discriminator network. The hyper-
parameters used in all experiments are described in Table 10.

Table 10: Hyper-parameters for domain adaptation experiments Hyperparameters
---
$\mathbf{F}$ network learning rate | $0.0005$
$\mathbf{C}$ network learning rate | $0.0005$
$\mathbf{D}$ network learning rate | $0.0001$
$\mathbf{F}$ network optimizer | SGD with Inv LR scheduler
$\mathbf{C}$ network learning rate | SGD with Inv LR scheduler
$\mathbf{D}$ network learning rate | Adam betas $(0.9,0.999)$
Number of critic iterations | 5
Batch size | 28
Entropy weight | 0.25
Weight update iterations | 500
Outlier fraction $\rho$ | 0.2

##### Weight visualization:

We visualize the weights learnt by our domain adaptation module by plotting
the histogram of weights in Figure 11. Additionally, target samples sorted by
weights are shown in Figure 10.

Figure 10: Visualizing target domain samples sorted by learnt weights Figure
11: Visualizing histograms of weights learnt in robust domain alignment