Outlier Robust Optimal Transport
Authors: Debarghya Mukherjee
Aritra Guha
Justin Solomon
Yuekai Sun
Mikhail Yurochkin
Venue:  (2021)
Keywords: Optimal transport
outliers
robustness

Abstract: Optimal transport (OT) provides a way of measuring distances between distributions that depends on the geometry of the sample space. In light of recent advances in solving the OT problem, OT distances are widely used as loss functions in minimum distance estimation. Despite its prevalence and advantages, however, OT is extremely sensitive to outliers. A single adversarially-picked outlier can increase OT distance arbitrarily. To address this issue, in this work we propose an outlier-robust OT formulation. Our formulation is convex but challenging to scale at a first glance. We proceed by deriving an equivalent formulation based on cost truncation that is easy to incorporate into modern stochastic algorithms for regularized OT. We demonstrate our model applied to mean estimation under the Huber contamination model in simulation as well as outlier detection on real data.

Under review as a conference paper at ICLR 2021
OUTLIER-ROBUST OPTIMAL TRANSPORT
Anonymous authors Paper under double-blind review
ABSTRACT
Optimal transport (OT) provides way of measuring distances between distribu- tions that depends on the geometry of the sample space. In light of recent ad- vances in solving the OT problem. OT distances in minimum distance estimation. Despite its prevalence and advantages, however, outlier
widely used as loss functions
OT is extremely sensitive to outliers. A single adversarially-picke increase OT distance arbitrarily. To address this issue, in this work we propose outlier-rouust OT formulation. Our formulation is convex but challenging scale at a first glance. We proceed by deriving an equivalemt formulation based on cost truncation that is easy incorporate into modern stochastic algorithms for regularized OT. We demonstrate our model applied to mean estimation under the Huber contamination model in simulation as well as outlier detection on real data.
INTRODUCTION
Optimal transport a fundamental problem in applied mathematics. its original form (Monge) 1781). the problem entails finding the minimum cost way transport mass from prescribed prob- ability distribution j on X to another prescribed distribution y on X. Kantorovich (1942) relaxed
Mongels s formulation of the optimal transport problem obtain the Kantorovich formulation:
(T v) A min (xx, [c(X1,
(1.1)
HEF(ur)
where F(,, 2/) is the set of couplings between j and (probability distributions on X' X whose
marginals are and v) and e is a cost function, where we typically assume c(E, y) 2 0 and c(x,,2) Compared to other notions of distance between probability distributions, optimal transport uniquely depends on the geometry of the sample space.
Recent advancements in optimization for optimal transport (Cuturi 2013 Solomon al. 2015
Genevay et al. 2016: Seguy et al. (018)) enabled its broad adaptation in machine learning applica- tions where geometry of the data is important. See (Peyré & Cuturi 2018) for survey. Optimal transport has found applications in natural language processing (Kusner et al.) 2015 Huang et al.,
2016 Alvarez-Melis & Jaakkolal 2018 Yurochkin et al.) 2019), generative modeling (Arjovsky) et al. 2017), clustering (Ho et al. 2017). domain adaptation (Courty et al., 2014 2017), large-scale Bayesian modeling (Srivastava et al. 2018), and many other domains.
Many applications use OT loss in optimization problem of the form:
arg mingge OT Mg).
(1.2)
where {"a}eEe is a collection of parametric models, Pn is the empirical distribution of the samples. Such estimators are called minimum Kantorovich estimators (MKE) (Bassetti et al.) 2006). They are popular alternatives to likelihood-baid bbaeed estimators, especially generative modeling. For example, when OT(,, -) is the Wasserstein-1 distance and is generator parameterized by neural network with weights 0, equation 1.2 corresponds to the Wasserstein GAN (Arjovsky et af. 2017).
One drawback of optimal transport is its sensitivity to outliers. Because all the mass in μ must be transported to v, a small fraction of outliers can have an outsized impact on the optimal transport problem. For statistics and machine learning applications in which the data is corrupted this is a major issue. For example, the poor performance of Wasserstein GANs in the presence of outliers noted in the recent works outlier-robust generative learning with f-divergence GANs (Chao et al., 2018)) Wu et al.) 2020). The problem of rublier-robusteess in MKE has not been studied, with the exception of two concurrent works (Staerman al. 2020: Balaji et al. 2020).
noisy,

---

Under review as a conference paper at ICLR 2021
In this paper, propose modification of OT address its sensitivity to outliers. Our formulation can be used as loss in equation I.2] so that it is robust to a small fraction of outliers in the data. To keep things simple, consider the e-contamination model (Huber & Ronchetti 2009). Let Vo, be
a member of a parametric model (vo : E } and let
== (1 M0 +
where ja is the data-gen gentraannn distribution, > 0 is the fraction of outliers, and i is the distribution of the outliers. Although the fraction outliers is capped e, the value of the outliers is arbitrary, so the outliers may have an arbitrarily large impact on the optimal transport problem. Our goal is modify the optimal transport problem so that more robust to outliers. We have in mind the downstream application of learning 8, from (samples from) in the e-contamination model. Our main contributions are follows:
1. We propose robust OT formulation that is suitable for statistical estimation in the contamination model using MKE.
We show that our formulation equivalent to the original OT problem with a clipped transport cost. This connection enables us to leverage the voluminous literature on computational optimal transport to develop efficient algorithm to perform MKE robust to outliers.
3. Our formulation enables new application of optimal transport: outlier detection in data.
PROBLEM FORMULATION
2.1 ROBUST OT FOR MKE
in MKE, need allow the corresponding OT problem to ignore the outliers in the data distribution μ. The e-contamination model imposes a cap on the fraction of outliers, it is not hard see that || vo, ||Tv I where || ||Tv is the total-variation norm defined as ||l||T = 2 [x(z))] This suggests we solve a TV-constrainnddrggulliize version of equation 1.2 The constrained version
To promote
min f
OT( vo)
subject to 1 S
suffers from identification issues. In particular, it cannot distinguish between "clean" distributions within TV distance of vo,- This makes it unsuitable loss function for statistical estimation, because it cannot lead to consistent estimator. However, its regularized counterpart
min OT(μ + vp) + >|| #Ee,
(2.1)
where À > O is a regularization parameter, does not suffer from this issue. In the rest of this paper, we work with the TV-regularized formulation equation 2.1
The main idea of our formulation is to allow for modifications of while penalizing their magnitude and ensuring that the modified μ is still probability measure. Below we formulate this intuition in an optimization problem titled ROBOT (ROBust Optimal Transport):
Formulation 1:
/ C(a,v) I1(dr, dy) - A||s|/TV
mill (B xR²) #EF(R")
Sa I[drr = (u(dx) + s(dx)) 2 0
subject to
BxR
ROBOT(P, v)
BB E B(R") (Borel o-algebra)
(2.2)
[
I1(dr, dy) v(dy) VC e B(R")
Rdxx
/ s(dz) = 0.
2

---

Under review as a conference paper at ICLR 2021
Here F(RR) denotes the set of all signed measures with finite total variation R F (RR Rd) is the set of all measures with finite total variation on R x Rd
The first and the last constraints ensure that μ + is a valid probability measure, while A||s||Tv penalizes the amount of modifications in μ. It is worth noting that we can identify exact locations of outliers in j by inspecting la + 8, i.e. if μu(=) + s(x) O, then got eliminated and is outlier.
ROBOT, unlike classical OT, guarantees that an adversarially picked outliers can not increase the distance arbitrarily. Let f (1 c) tqe, Le. is μ contaminated with outliers from Me. and let be an arbitrary measure (in MKE, jı is the contaminated data and v is the model we learn). Adversary arbitrarily increase (ā, v) by manipulating the outlier distribution PAc- For ROBOT we have the following bound:
Theorem 2.1. Lel jr = (1 - e) + Efte for some e E [0, 1), then
ROBOT( v) S (OT(H, + dell - (ellTv) A A|IA - v/ITV A OT(
(2.3)
This bound has two key takeaways: since TV norm of any two distributions is bounded by I, ad- versary can not increase ROBOT (i,, v) arbitrarily; in the absence of outliers, ROBOT is bounded by classical OT. See Appendix C for the proof.
Related work We note connection between equation 2.2 and unbalanced OT (UOT) (Chizat, 2017 Chizat et al. 2018). UOT is typically formulated by replacing TV norm with KL. + s and adding an analogous term for v. [Ciiat et al. (2018) studied entropy regularized UOT with various divergences penalizing marginal violations. Optimization problems similar to equation 2.2
have also been considered outside of the ML literature (Piccoli & Rossi 2014 Liero et al.) 201 8). We are unaware of prior applications of UOT to outlier-robustness. but it studied in the current work of Balaji et al. (2020). Another relevant variation of OT is partial OT (Figalli) 2010 Caffarelli & McCann 20TO). It may also be considered for outlier-robustnest but it has drawback of forcing mass destruction rather than adjusting marginals to ignore outliers when they are present. A concurrent work by (Staerman et al. (2020) took different path: they replaced the expectation in the Wasserstein- I dual with a median-ol- corresponding primal, making it hard interpret as an optimal transport problem.
to promote robustness. It is unclear what is the
A major challenge with the aforementioned methods, including our Formulation 1, is the difficulty of the optimization problem. This is especially the case for MKEs, where transport problem has to be solved in every iteration obtain the gradient of the model parameters. Chizat et al. (2018) proposed a Sinkhorn-like algorithm for entropy regularized UOT, but it is not amenable to stochastic optimization. [Balaji et al. (2020) proposed stochastic optimization algorithm based the UOT dual, but it requires two additional neural networks (total of four including dual potentials) to pa- rameterize modified marginal distributions (i.e., |4 and analogous one for v). Optimizing with a median-of means the objective function as in (Staerman et al., 2020) is also challenging. The key contribution of our work is formulation equivalent to equation 2.2 which is easily comparible
with the large body of classical OT optimization techniques (Cuturi 2013 Solomon et al. 2015
Genevay al. 2016: Seguy al. 2018).
More efficient equivalent formulation At first glance, there two issues with equation 2.2 appears asymmetric and it is unclear if it can be optimized efficiently. Below we present an equivalent formulation that is free of these issues:
Formulation 2:
/ (x(l,,))I(ar dy)
minner+(R4xR9)
S I[dx dy) / p(dx) B B(R))
ROBOT(H, v) subject
(2.4)
[ J
Tīdd,, dy) ( u(dy) VC (R*)
where C2 is the truncated cost function defined as C Cx(x, y) = C(æ,y) v) A 2X. Looking at equa- tion 2.4 it is not apparent that it adds robustness to MKE, but it is symmetric, easy to combine
3

---

Under review as a conference paper at ICLR 2021
with entropic regularization by simply truncating the cost, and benefits from stochastic optimization algorithms (Genevay et al. 2016 Seguy et al. 2018). This formulation also has a distant relation to the idea of loss truncation for achieving robustness (Shen & Sanghavi 2019). Pele & Werman (2009) considered the Earth Mover Distance (discrete OT) with truncated cost to achieve computa- tional improvements; they also mentioned its potential to promote robustness against outlier noise but did not explore this direction.
In Section 3 we establish equivalence between the two ROBOT formulations, equation 2.2 and
equation 2.4 This equivalence allows us to obtain an efficient algorithm based on equation 2.4 for
robust MKE. We also provide a simple procedure for computing optimal in equation 2.2 foom the solution of equation enabling new OT application: outlier detection. We verify the effec- tiveness of robust MKE and outlier detection in our experiments in Section Before presenting the equivalence proof, we formulate the discrete analogs of the two ROBOT formulations for their practical value.
2.2 DISCRETE ROBOT FORMULATIONS
In practice we typically encounter samples from the distributions, rather then the distributions them- selves. Sampling is also built into stochastic optimization. In this subsection, we present the discrete versions of the ROBOT formulations. The key detail is that, in equation 2.2, p. and are all sup- ported on IRd while the discrete case the empirical measures Pn E nn-1 and Vm E m supported on set of points (A' is the unit probability simplex in RR). As result, to for- mulate a discrete version of equation 2.2 we need to augment (4n and Vm with each others' sup- ports. To be precise, let (nn) (1,- X,) and supp(pm) (Yı,..., 1m). Define C= (7,, Zz...., 7mta]= (X,...., X,, K,,Y, V Ym Then discrete analog of equation 2.2 is
Formulation (discrete):
min min mer (eteeoooiieeee ())((m)))))
(Caug: IT) + A [[|88]]] 1|1 + [|1]]1]
SERm*
ROBOT (pn, 1m)
subject to
M mntn
U/ + 81
t1
1
mmtn
0 Um
(2.5)
II = O,
1 1 0,
where Cang E (I)())))((m+)) is the augmented cost function Caugi.j cl 2j) is the ground cost, e.g., squared Euclidean distance), s = (s1, t1) and 1, is the vector all ones R". The TV norm got replaced with its discrete analog, the L1 norm. Similarly to its continuous counterpart, the optimization problem is harder than the typical OT due to additional constraint optimization variable and increased cost matrix size.
The discrete analog of equation 2.4 is straightforward:
Formulation 2 (discrete):
minneRoxx
(Cx, II)
ROBOT(H Vm))
(2.6)
subject to IT = pay
I1 1m Ums
IT > 0,
where Cx.i.j c(X,, A2), As in the continuous case, it is easy to adapt modern (regularized) OT solvers without any computational overhead. As in the continuous case, formulations of equation 2.5 and equation 2.6 are equivalent. It is also possible to recover s of equation 2.5 from the solution of equation 2.6 perform outlirr detection.
Two-sided formulation So far we have assumed that one the input distributions does not have outliers, which is the setting of MKE, where the clean distribution corresponds to the model lear. In some applications, both distributions may be corrupted. To address this case, we provide an equivalent tio-sided formulation, analogous to UOT with TV norm:
4

---

Under review as a conference paper at ICLR 2021
Formulation 3 (two-sided):
min le (1)mm))))00))))))
(Caug IT) + X x [11 + [|1ll + ||82|11 + +1t22111]
8, EB ER 8
ROBOT (n, (n pm)
subject to
MT m+n
Mn 81
IT 1m+n
82
4
Umm + 12
II
1 m 0,
m 0.
(2.7)
where $ (8] t and $2 (s) TT
3 EQUIVALENCE OF THE ROBOT FORMULATIONS
In this section we present our main theorem, which demonstrates the equivalence between two formulations of the robust optimal transport:
Theorem 3.1. For any two measures μ and v. ROBOT(,, v) has same value for both the formu- lations, i.e., Formulation 1 is equivalent to Formulation 2 both for continuous and discrete case. Moreover, we can recover optimal coupling of one formulation from the other.
Below we sketch the proof of this theorem and highlight some important techniques used in the proof. We focus the discrete case as it is more intuitive and has concrete practical implications in our experiments. complete proof can be found in Appendix [ Please also see Appendix A.2 for the proof of equivalence between Formulations 1, and 3 in the discrete case.
3.1 PROOF SKETCH
In the remainder this section consider the discrete case, i.e., equation 2.5 for Formulation (FI) and equation 2.6 for Formulation 2 (F2). Suppose 11; is an optimal solution of F2. Then we construct feasible solution 11j, sj (si. Fl based I1; with the same value of the objective function as F2 and claim that (II, st) ) is an optimal solution. We prove the claim by contradiction: if (TT,, sT) is not optimal, then there exists another pair (iT, $1) which is optimal for F1 with strictly less objective value. We then construct another feasible solution nez Formulation 2 which has the same objective value as of (f1,,8, 8,) for F1. This implies IT; new has strictly less objective value for F2 than II;, which is a contradiction.
The two main pillars of this proof are (1) to construct feasible solution of Fl starting from a feasible solution of F2 and (2) to show that the solution constructed is indeed optimal for F1. Hence step (1) gives recipe construct optimal solution of F1 starting from optimal solution of F2. We elaborate the first point in the next subsection, which has practical implications for outlier detection. The other point is more technical; interested readers may go through the proof in Appendix A.1
Algorithm 1 Generating optimal solution of Fl from F2
1: Start with IT E R2xm, an optimal solution of Formulation 2.
2: Create augmented matrix II tmtaxm+n with all 0. Divide II into four blocks:
Un
1112
rT
nXR
I121
1l
mxn
m Xm
3: Set 1T TT; and collect all the indices I = {(i,]) Ci. > 21).
4: Set [T2 <- for (i.j) E I.
5: Set (izz( <- Σt 113 (i) for all 1 < j 5 and set 1I; <- 1l.
6: Set (i) < >E (1, j) (Ljezz for all 1 < i < m.
7: Set (T) [zz(j.j) for all 1 & m.
8: return s7.
5

---

Under review as a conference paper at ICLR 2021
3.2 GOING FROM FORMULATION TO FORMULATION 1
Let ΙI₃ (respectively II1) be optimal solution of F2 (respectively FI). Recall that II; has di- mension (m + n) X (m + n). From the column sum constraint F1, we need to take the first n columns of ITΙ to be exactly 0, whereas the last columns must sum up to Vin- For any matrix A, we denote by A[(a: :b) x (c: d)] the submatrix consisting of rows from a to and columns from c d. Our main idea is to put a modified version 1E [1; n) (n
+ n)] and make 11[(++1 m++n)++++) x x (n++1 m+n)] diagonal. First we describe how to modify ILz Observe that, if for some (i.j) Ct > 2X, we expect X, supp( to be outlier resulting in high transportation cost, which is why we truncate the cost in F2. Therefore, to get an optimal solution of FI, we make the corresponding value of optimal plan and dump the mass into the corresponding slack variable i in the diagonal of the bottom right submatrix. This changes the row sum, which is taken care of by si. But, as we are not moving this mass outside the corresponding column, the column sum of 191(1 (m + n)) ((n + 1) (m + R)]] remains same column sum of IIz, which is Pn. We summarize this procedure in Algorithm
b
81
c
0
a
t =
b b
Figure I: Constructing optimal solution of Formulation from optimal solution of Formulation 2.
Example. In Figure T provide example to visualize the construction. On the left, we have II5 an optimal solution of Formulation The blue triangles denote the positions where the corre- sponding cost value is I 2X, and gight-green squares denote the positions where the corresponding value of the cost matrix is > 2x. To construct an optimal solution II of Formulation from this II. first create augmented matrix of size 6 6. We keep all the entries of of left x 3 sub-matrix as 0 (in this picture blank elements indicate 0). On the right submatrix, we put II; into the top-right block, but remove the masses from light-green squares, Le. where
value is > 2A, and put it in the diagonal entries of the bottom right block as shown in Figure [ This mass contributes to the slack variables 81 and 1, and this augmented matrix along with 81, t give us an optimal solution of Formulation 1.
3.3 OUTLIER DETECTION WITH ROBOT
Our construction algorithm has practical consequences for outlier detection. Suppose we have two datasets, a clean dataset Vm (i.e., has no outliers) and an outlicr-contaminated dataset fn, We can detect the outliers in fh, without directly solving costly Formulation by following Algorithm 2 In this algorithm, À a regularization parameter that can be chosen via cross-validation or heuristically (see Section 4..2 for an example). In Section 4.2 on image data.
this algorithm to perform outlier detection
Algorithm 2 Outlier detection in contaminated data
1: Start with pa. (contaminted data) and Pm. (clean data).
2: Solve Formulation and obtain IT; using suitable value of X.
3: Use Algorithm|] to obtain IT; . 1 from ITr
4: Find I, the set of all the indices where An + Sf 0.
5: Return I the indices of outliers pn-

---

Under review as a conference paper at ICLR 2021
Table 1: Robust mean estimation with GANs using different distribution divergences. True mean is Yo = Os: sample size n 1000; contamination proportion 0.2. We report results over 30 experiment restarts.
Contamination
JS Loss
SH Loss
RKL Loss
ROBOT
UOT
N(0.1 15,
0.09 0.03
0.11 + 0.03
0.115 = 0.03
0.1 = 0.03
0.1 = 0.04
[(0.5 15)
0.23 + 0.04
0.24 0.05
0.24 0.05
0.117 + 0.03
0.2 0.04
W(1 1s,
0.43 = 0.05
0.43 + 0.06
0.43 + 0.06
0.261 + 0.06
0.25 + 0.05
((2 1s, 15)
0.67 +: 0.07
0.67 + 0.08
0.67 + 0.08
0.106 + 0.03
0.1 + 0.03
1:
0.05
1n =
==1.1
M1
2
Estimation error
0.15
Estimation error
1.5
0.2
1] 0
0.25
1.0
1.0
0.5
0.5
0.0
0.0
1.11
1og1o(A)
log1o(A)
(a) Varying proportion of contamination
(b) Varying outlier distribution
Figure 2: Empirical study of regularization hyperparameter À sensitivity
4 EMPIRICAL STUDIES
To evaluate effectiveness of ROBOT, we consider the task of robust mean estimation under the Huber contamination model. The data is generated from (1 - e) Ia) + eN La) and the goal is estimate No. Prior work has advocated for using f-divergence GANs (Chao et al.) 2018 Wu et al. 2020) for this problem and pointed out inefficiencies of Wasserstein GAN in the presence of outhers. We show that robust OT formulation allows to estimate the uncontaminated mean Yo comparably or better than variety of /diieergence GANs. We also use this simulated setup to study sensitivity the regularization hyperparameter X.
In our second experiment, we present new application of optimal transport enabled by ROBOT. Suppose we have collected curated dataset V' (i.e., know that it has outliers)-uchh data collection is expensive, and we want to benefit from it to automate subsequent data collection. Let Nn be second dataset collected "in the wild," i.e., it may or may not have outliers. We demonstrate how ROBOT can be used to identify outliers in An using the curated dataset 1/m-
4.1 ROBUST MEAN ESTIMATION
Following Wu 2020), we consider a simple generator of the form go(x) (0, I2), d is the data dimension. The basic idea of robust mean estimation with GANs is to minimize various distributional divergences between samples from ge and observed data simulated from (1 e))o Ia) + eN(m,, La). The goal is to estimate To with 0. To efficiently implement ROBOT GAN, we use standard min- max optimization approach: solve the inner max (ROBOT) and use gradient descent for the outer min parameter. To solve ROBOT. it is straightforward to adopt any of the prior stochastic regularized OT solvers: the only modification is the truncation the cost entries in equation 2.6 We use the stochastic algorithm for semi-discrete regularized OT from
0, x

---

Under review as a conference paper at ICLR 2021
(Genevay et al. 2016 Algorithm 2). We summarize ROBOT GAN in Algorithm S Line 5 Line 10 perform the inner optimization where we solve entropy regularized OT dual with truncated cost and Line 11 Line 12 perform gradient update of 8.
Algorithm: 3 ROBOT GAN
1: Input: robustness regularizion X, entropic regularization a, data distribution Pn supp()(,) = ===== [[x,,... xn), steps sizes r and 7
A An-1
2: Initialize: Initialize 0 = finits set number of iterations M and L, i = v v-=
3: for j= i...... .......... M do
4: Generate غ ~ (O, Ia) and set 2 1 + 0.
5: Set the cost vector с E IR" as c(k) = c(Xx, 2) A2 for = 1
6: for = ,,,
& solve entropy regularized OT dual
7: Set h + シ=c and do the normalized exponential transformation u + (1.eh5.
8:
Calculate the gradient Vv & Pn Update + V and v f- (1/(j + +)) + (j+ i))v. Do the same transformation of v as in Step 7, i.e. set h f x=- and set II
9:
10:
(1.eh)
11: Set (k) for such that C(X,, 2) > 2 for k I.....n.
Calculate gradient with respect to V0 2 Σn l1(k)) x
13:
Update 0 + 0 v0.
14:
Ouput: 0
For the f-divergence GANs Nowozin et al. 2016) we use the code of Wu et al. 2020) for GANs with Jensen- -hannnon (JS) loss, squared Hellinger (SH) loss and Reverse Kullback- Leibler (RKL) loss. For the exact expression of these divergences see Table of Wu et al. (2020). We report estimation error measured by the Euclidean distance between true uncontaminated mean yoo and estimated mean 0 for various contamination distributions in Table ROBOT GAN performs well across all considered contamination distributions. As the difference between true mean To and contamination mean 7) increases, the estimation error of all methods tends to increase. However, when it becomes easier to distinguish outliers from clean samples, i.e., 7 = 2 15, performance of ROBOT noticeably improves.
We also compared to the Sinkhom-bbsed UOT algorithm (Chizat et al. 2018 available in the Python Optimal Transport (POT) library (Flamary & Courty| 2017); to obtan a UOT GAN, we modified steps 5-11 of Algorithm 3 for computing II. Unsurprisingly. both ROBOT and UOT perform simi- larly: recall equivalence to Formulation which is similar UOT with TV norm. The key insight of our work is the equivalence to classical OT with truncated cost, that greatly simplifies optimization and allows use existing stochastic OT algorithms. In this experiment, the sample size n 1000 UOT POT implementation to be effective, but it breaks
is sufficiently small for the Sinkhorn-basse in the experiment we present in Section 4.2 We also tried the code of Balaji al. (2020) based on CVXPY (Diamond & Boyd 2016), but it is too slow even for the n 1000 sample size.
In the previous experiment, we set À 0.5. Now we demonstrate empirically that there is broad range of À values performing well. In Figure 2a we study sensitivity of X under various contamina- tion proportions holding 7/ = 15 and 7/1
1, fixed. Horizontal lines correspond ie., vanilla OT. The key observations are: there is wide range of X efficient at all contamination proportions, and ROBOT always at least as good as vanilla OT (even when there no contam- ination 0). In Figure 2b we present similar study varying the mean of the contamination distribution and holding c = 0.2 fixed. We see that as the contamination distribution gets closer to the true distribution, it becomes harder pick good X, but the performance is always least as good as the vanilla OT (horizontal lines).
= co,
4.2 OUTLIER DETECTION FOR DATA COLLECTION
Our robust OT formulation equation 2.5 enables outlier identification. Let Vm be a clean dataset and Pa potentially contaminated with outliers. Recall that ROBOT allows modification of one of the input distributions to eliminate potential outliers. We can identify outliers in μ., as follows: ye, (f) + (T) 0, then X,, the ith point in fn, is outlier. Instead of directly solving equation 2.5
8

---

Under review as a conference paper at ICLR 2021
Figure 3:
Random sample of outliers detected by ROBOT from dataset of MNIST digits contami- nated with Fashion MNIST images.
which may be inefficient, we use our equivalence results and solve an easier optimization problem equation 2.6 followed by recovering to find outliers via Algorithm 2
Let Pm be a clean dataset consisting of 10k MNIST digits and Ynn be dataset collected "in the wild" consisting of (different) 8k MNIST digits and 2k Fashion MNIST images. We compute ROBOT( vm) to identify outlier Fashion MNIST images in /un For each point in jhn we ob- tain a prediction, outlier or clean, which allows us to evaluate accuracy. ROBOT outlier detection is 90% accurate in this experiment. We also comment on À selection: since we know that V/m is clean, we can subsample two datasets from it, compute vanilla OT to obtain transportation plan II and set A to be half the maximum distance between matched elements, i.e. 2 max,,; {Ca II, > 0), where C' is the cost matrix for the two subsampled datasets. This procedure is essentially estimating maximum distance between matched clean samples. We also present random sample of outliers identified by our method in Figure 3 All of the sampled outliers are Fashion MNIST images, al- though 90% accuracy suggests that some of the outliers were not identified. Decreasing À can help to find more outliers, but may result in some clean samples being mistaken for outliers. We con- clude that ROBOT can be used to assist in data collection once an initial set of clean data has been acquired. As we mentioned previously, the Sinkhorn based UOT POT implementation is too expen- sive for this experiment due to larger sample size, yielding memory errors on a personal laptop with 16GB RAM.
For comparison, we also consider a heuristic distance-based approach for identifying outliers. We estimate diameter of the set of clean dataset Vm by taking the 99th percentile of the pairwise distance matrix of samples in V'- If outliers and clean data have disjoint support, we can adopt a simple heuristic: for each sample in the potentially contaminated fnn compute average distance to the clean samples in Vmn and declare a sample as an outlier if this average distance is greater than the diameter of the clean data. The accuracy of this procedure is 85.4%, inferior to the ROBOT accuracy of 90%. The disjoint support assumption justifying the distance-based heuristic might be strong in practice. ROBOT continues to be effective even when the supports of clean and outlier distributions are not easily separable.
5 SUMMARY AND DISCUSSION
We proposed and studied ROBOT, robust formulation of optimal transport. We showed that al- though the problem seemingly asymmetric and challenging optimize, there is an equivalent formulation based on cost truncation that is symmetric and compatible with modern stochastic opti- mization methods for OT.
ROBOT closely resembles unbalanced optimal transport (UOT). In our formulation, we added a TV regularizer to the vanilla optimal transport problem. This is motivated by the e-contamination model. In UOT, the TV regularizer is typically replaced with a KI. divergence. Other choices of the regularizer may lead to new properties and applications. Studying equivalent, simpler formulations of UOT with different divergences may be fruitful future work direction.
From the practical perspective, in our experiments we observed no degradation ROBOT GAN in comparison to OT GAN, even when there were outliers. It is possible that replacing OT with ROBOT may be beneficial for various machine learning applications of OT. Data encountered in practice may not be explicitly contaminated with outliers, but often has errors and other deficien- cies, suggesting that a "no-harm" robustness is desirable.

---

Under review as a conference paper at ICLR 2021
REFERENCES
David Alvarez-Melis and Tommi S Jaakkola. Gromov-Wasserstcin alignment of word embedding spaces. urXiv:/809. 009,00013, 2018.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein GAN. arXiv:1701.07875 [cs, stat], January 2017.
Yogesh Balaji, Rama Chellappa, and Soheil Feizi Robust optimal transport with applications in generative modeling and domain adaptation. Advances in Neural Information Processing Systems, 33, 2020.
Federico Bassetti, Antonella Bodini, and Eugenio Regazzini. On minimum Kantorovich distance estimators. Statistics Probability Letters, 76(12):1298-134)) 2006.
Luis A Caffarelli and Robert J McCann. Free boundaries in optimal transport and Monge-Ampere obstacle problems. Annals of Mathematics, pp. 673-730, 2010.
Gao Chao, Yao Yuan, and Zhu Weizhi. Robust estimation via generative adversarial networks. In International Conference on Learning Representations, 2018.
Lenaic Chizat, Gabriel Peyré. Bernhard Schmitzer, and François- Xavier Vialard. Scaling algorithms for unbalanced optimal transport problems. Mathematics of Computation, 87(314):2563-660) 2018.
Lenaic Chizat. Unbalanced optimal transport: Models, numerical methods, applications. Numerical Analysis [math.NA]. Université Paris sciences et lettres, 2017.
Nicolas Courty, Rémi Flamary, and Devis Tuia. Domain adaptation with regularized optimal transport. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 274-289, Springer, 2014.
Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamonjy. Joint distribution optimal transportation for domain adaptation. In Advances in Neural Information Processing Systems, pp. 3730-3739, 2017.
Marco Cuturi. Sinkhorn Distances: Lightspeed Computation of Optimal Transport. In C. C. Burges, I.. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger (eds.), Advances Neural Information Processing Systems 26, pp. 2292-2300. Curran Associates, Inc., 2013.
Steven Diamond and Stephen Boyd. CVXPY: A Python-embeddded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5,0115
Alessio Figalli. The optimal partial transport problem. Archive for Rational Mechanics and Analysis, 195(2):533-566 -600 2010.
Rémi Flamary and Nicolas Courty. POT Python optimal transport library, 2017. URL https:
7/ //pythonot. gitti.ggttthe trtthbb.oo
Aude Genevay, Marco Cuturi, Gabriel Peyré, and Francis Bach. Stochastic optimization for large- scale optimal transport. In Advances in Neural Information Processing Systems, pp. 3440-3444 2016.
Nhat Ho, XuanLong Nguyen, Mikhail Yurochkin, Hung Hai Bui, Viet Huynh, and Dinh Phung. Multilevel clustering via Wasserstein means. In International Conference on Machine Learning, pp. 1501-1509, 2017.
Gao Huang, Chuan Guo, Matt J Kusner, Yu Sun, Fei Sha, and Kilian Q Weinnergerr Supervised word mover's distance. In Advances in Neural Information Processing Systems, pp. 4862-4870, 2016.
Peter J. Huber and Elvezio Ronchetti. Robust Statistics. Wiley Series in Probability and Statistics. Wiley, Hoboken, N.J, 2nd ed edition, 2009. ISBN 978-0-470-12999-6.
10

---

Under review as a conference paper at ICLR 2021
Leonid Vitalievich Kantorovich. On the translocation of masses. In Dokl. Akad. Nauk. USSR (NS), volume 37, pp. 199-201, 1942.
Matt Kusner, Yu Sun, Nicholas Kolkin, and Kilian Weinberger. From Word Embeddings To Docu- ment Distances. In International Conference on Machine Learning, pp. 957-966, June 2015.
Matthias Liero, Alexander Mielke, and Giuseppe Savaré. Optimal entropyy new Hellinger
problems and Bettinger-Kattrrviion Kantorovich distance between positive measures. Inventiones Mathematicae, 211 (3):969 1117, 2018.
Gaspard Monge. Mémoire sur la théorie des déblais et des remblais. De I'Imprimeric Royale, 1781.
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-GAN: Training generative neural sam- plers using variational divergence minimization. In Advances in Neural Information Processing Systems, pp. 271-279, 2016.
Ofir Pele and Michael Werman. Fast and robust earth mover's distances. In 2009 IEEE 12th Inter- national Conference on Computer Vision, pp. 460-467. IEEE, 2009.
Gabriel Peyré and Marco Cuturi. Computational Optimal Transport. arXiv:1803.0056 [stat], March 2018
Benedetto Piccoli and Francesco Rossi. Generalized Wasserstein distance and its application to transport equations with source. Archive for Rational Mechanics and Analysis, 211(1):33,-358, 2014.
Vivien Seguy, Bharath Bhushan Damodaran, Rémi Flamary, Nicolas Courty, Antoine Rolet, and Mathieu Blondel. Large-Scale Optimal Transport and Mapping Estimation. orXiv:/711.022 [stat], February 2018.
Yanyao Shen and Sujay Sanghavi. Learning with bad training data via iterative trimmed loss mini- mization. In International Conference Machine Learning, pp. 5739-5748. PMLR, 2019.
Justin Solomon, Fernando De Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du, and Leonidas Guibas. Convolutional Wasserstein distances: Efficient optimal transporta- tion on geometric domains. ACM Transactions Graphies (TOG), 34(4):1-11, 2015,
Sanvesh Srivastava, Cheng Li, and David Dunson. Scalable Bayes via Barycenter in Wasserstein Space. wrxiv:/508.00 058800 [stat], June 2018.
Guillaume Staerman, Pierre Laforgue, Pavlo Mozharovskyi, and Florence d' Alché Buc. When OT meets MOM: Robust estimation of Wasserstein distance. arXiv:2006. 10325, 2020.
C. Villani. Optimal Transport: Old and New. Grundlehren der Mathematischen Wissenschafien [Fundamental Principles of Mathemtical Sciences). Springer, Berlin, 2009.
Kaiwen Wu, Gavin Weiguang Ding, Ruitong Huang, and Yaoliang Yu. On Minimax Optimality of GANs for Robust Mean Estimation. In International Conference on Artificial Intelligence and Statistics, pp. 4541-4551, June 2020.
Mikhail Yurochkin. Sebastian Claici, Edward Chien, Farzaneh Mirzazadeh, and Justin Solomon. Hierarchical Optimal Transport for Document Representation. /906. 10827 (cs, stat), June 2019.

---

Under review as a conference paper at ICLR 2021
A PROOF OF THEOREM 3.1
A.1 PROOF OF DISCRETE VERSION
Proof. Define a matrix 11 as:
O, (1,
if (i. 22 otherwise
IT(,))
Also define 8 R and E Re as:
m si >
and similarly define:
G0 = Σ () =
These vectors corresponds to the row sums and the column sums the elements of the optimal transport plan of Formulation 2, where the cost function exceeds 2A. Note that, these co-ordinates of the optimal transport plan corresponding to those co-ordinates of cost matrix, where the cost is greater than 2 and contribute to the objective value via their sum only, hence any different arrangement of these transition probabilities with same sum gives the same objective value.
Now based on this II obtained we construct feasible solution of Formulation following Algorithm
11 = 0 IT 0
diag(ti)
The row sums of II; is:
Pn + s1
I1
ti
and it is immediate from the construction that the column of IT is um. Also as:
Σ st = Σ GG== = Σ m,,)))
(2
and s 3 0, 2 O, have:
1 1 (Mn + s +() =1
Therefore, we have (II, s1 (T) is feasible solution of Formulation 1. Now suppose this is not an optimal solution. Pick optimal solution 11, 5, & of Formulation 1 so that:
(Caug: III [[] + [| (Coug. IIi) + A [|]s + [[t]]]]]]
The following two lemmas provide some structural properties of any optimal solution of Formulation 1:
Lemma A.1. Suppose si, G are optimal solution for Formulation 1. Divide II; into four parts corresponding augmenlation as in algorithm 7
TI IT
IT: IT.
T1.12
11
Then we have II 1,11 21 = 0 and IT; is a diagonal matrix.
Lemma A.2. IT, sT, t is optimal solution of Formulation then:
1. If Cf > 2A then (i.j)=
2. If IfC 2A for some i and for all < < then si (1) 0.
If C. < 2A for some j and for all $ < m, then (i( = O.
4. If CfC < 2X then (5) 0.
12

---

Under review as a conference paper at ICLR 2021
We provide the proofs in the next subsection. By Lemma A.1 ality:
assume without loss of gener-
0 11
diag(t)
Now based on (îi, 8, we create a feasible solution namely nnew of Formulation as follows: Define the of indices fei,"". it} and fi......th as:
8ig , Siz O and En f Ej > 0.
Then by part (4) of Lemma A.2 we have Ca > 2A for a E [l....,k) and [ E {l..... ............. Also by part (2) Lemma A.. the value of transport plan at these co-ordinates O. Now distribute the mass of slack variables in these co-ordinates such that the marginals of new transport plan becomes exactly An and V'- This new transport plan our IT new Recall that, || ||8||2. Hence, here the regularizer value decreases by | ||] and the cost value increased by exactly 2|| as we are truncating the cost. Hence we have:
(l (Caug: [1I [|]5]] + [0h]]
(Cang: [Ti) + X |||ii|| 1 + [11
(Cx,
which is contradiction as TTğ is the optimal solution of Formulation 2. This completes the proof for the discrete part.
A.2 PROOF OF EQUIVALENCE FOR TWO SIDED FORMULATION
Here prove that two sided formulation, i.e. Formulation 3 (equation 2.7 is equivalent to Formulation I (equation 2.5) for the discrete case. Towards that end, we introduce another auxiliary formulation and show that both Formulation and Formulation 3 are equivalent the following auxiliary formulation of the problem.
Formulation 4:
(C, > [[|s]]] + [|22||1]
an subject to
I11, p $1
WR.L,,(,.))
(A.1)
11" 1m q $2 I 0
First we show that Formulation 1 and Formulation 4 are equivalent in a sense that they have the same optimal objective value.
Theorem A.3. Suppose C cost function such that C(x,x) 0. Then Formulation and Formulation 4 has same optimal objective value.
Proof. Towards that end, we show that given one optimal variables of one formulation we can get optimal variables of other formulation with the same objective value. Before going into details need the following lemma whose proof is provided in Appendix B:
Lemma A.4. Suppose I1; $2,1,52, are the optimal variables of Formulation 4. Then si = 0 and $1 = 0.
Now we prove that optimal value of Formulation 1 and Formulation 4 are same. Let (T is optimal solution of Formulation 1. Then we claim that (II, .,,,,t is also an optimal solution of Formulation Clearly it is feasible solution of Formulation Suppose is not optimal, ie.. there exists another optimal solution (f14, 84,1, 84,2) such that:
(C, MT)) + A(1|5,,1lI + [1,4,2112) (C, (T, A(I (1a.)h)
13

---

Under review as a conference paper at ICLR 2021
Now based on (II,, 81,2)
construct feasible solution of Formulation 1 as follows:
0
IT, diag (4.22)
i =
0
Note that we proved in Lemma A.4 $4,2 3 O, hence we have IT, t Now as the column sums of
Ii, is + 84,2, we have column sums of II, = [0 g q=]T and the row sums are [(p 34,1) $7,21
Hence take $1,1 54,1 and $1,2 84,2. Then it follows:
(Cang, M1) > || + [| = (C, M4) + A (1 |1 + [
< 12, + A [[I [1a [|]]
=C [T;) [[|s,, [ti,,lla
This is contradiction as we assumed (TTi, si,1, (1,2) is an optimal solution of Formulation 1. There- fore we conclude (IT), s (7,1) is also an optimal solution of Formulation 4 which further con- cludes Formulation 1 and Formulation have same optimal values. This completes the proof of the theorem.
Theorem A.5. The optimal objective value of Formulation 3 and Formulation 4 are same.
Proof. Like in the proof of Theorem A.3 we also prove couple of lemmas.
Lemma A.6. Any optimal transport plan IIğ of Formulation 3 has the following structure: If write.
11
113.12
11
I 3,21
IT [T
then 113,11 and I1 are diagonal matrices and IT
=0.
Lemma A.7. If 53,1 1 22 tä are four optimal slack variables in Formulation then $3,1, (3, 3 0 and 83,; 4,2 = O.
Proof. The line of argument is same as in proof of Lemma A.4
Next we establish equivalence. Suppose (I1 $3.1, S32, (5,2) are optimal values Formulation
We claim that (Mg.12 +5.1 23.2 (,1 (3,2) forms an optimal solution Formulation The
objective value will then also be same as 85 = 0, 83,2 z 0 (Lemma A.7 implies || - $3
||s ||1 + ||$ and similarly f5, 3 0, t22 ł 0 implies || 12 =I(č_ ll2 + 11t5,2l12 2ll2-
Feasibility is immediate. Now for optimality, we again prove by contradiction. Suppose they are not optimal. Then lets say 4T, 84,1, 84,2 are an optimal triplet of Formulation 4. Now construct another
feasible solution of Formulation 3 as follows: Set 23.2 f3.2 = 0, $3,1 54,1 and fs,1 = $4.2. Set the matrix as:
0
IL diag 54.2)
o
Then it follows that (iss, 33,1 33,2, E2,1, F2.2) is feasible solution of Formulation 3. Finally we have:
(Caug: Agg) + A | + | + || + [
(Cangr Maa) + À (4, + [|x,
(C, ) + A [[| | 1, || + [|,]
(C, [[]+ - + || [
= (Cang, (T]) + []] | + 1|8 + || + [|
This contradicts the optimality of (IT, $ 23.2 15,1 (-2) This completes the proof.
14

---

Under review as a conference paper at ICLR 2021
A.3 PROOF OF CONTINUOUS VERSION
Proof. In this proof we denote by Fi the optimization problem of equation equation 2.2 and by F2 the optimization problem equation equation 2.4 Assume that Mmn and Vm. denote the respective empirical measures relative to μr, v. From Villani (2009), we know that Pas nn converge weakly to I and y respectively. Therefore, ROBOT2(Mm p) O. Similary for Pn and Thus, by triangle inequality,
lim [F2 Un) Fa v)
11 110000
But ROBOT (Pas Un) ROBOROOOH,,. Un). Therefore, our proof is complete we can show that Fi (Jhn vm)) Fi (11 0. lim n.m-00
Let 8 {s signed measure 1 is probability measure in RR.). For E L, define
/ C(a, Ul(dx dy) + A||s||TV
minne
/ I(dx, dy) 2 AAAAE D( x Rd)
subject to
W(++S, p(dx) + s(dx)) 20
B E 3(R
[Idrr, dy) = 1 v(dy) VC E 3(R")
J
By Lemma A.8 3 E 9 such that ROBOT (1, v) = W( + S.V) + A||s||/v. Let s = s - 8 where s and positive measures Rd. Let ||s|lvv r. Then, |s 11ıv [|stllr = 7/2.
Then consider XI...., Xn ~ -P-ss//(11 - 7). Yi,... Yn ~ S 171 Zz.... .a....,a. Un st //y. Then for any bounded continuous function f.
/ [(x) (P-8))
lim Σ
(1-7) (dx)
lim Ef(zi)/n / f(z) 8+ (dx)
(A.2)
Therefore, the distribution given by (P+ +)n (1 7) E, 6x. + + -, 8z, satisfies, (P+s), 3 P + 8, and therefore from (Villani 2009). 1im Wc((P (P- + S)n: vn)) W(P + S, Q). Here dz 7 [, 8z. - dv))
the Dirac mass at J. Moreover, sall = ||+||. where on satisfies
n
Also, BOBOTT vn) & W(P + vx) + A||s||rv, and therefore ROBOTT(H,))) = lim sup,->xc ROBOT (Mn, vn) S. RO
Now, let 5n satisfy Wi Wi(mn + 3n, vn) + A A||5m|/TV = ROBOT(um,PP) Such an in exists by the proof of the discrete part because Pn, Vn discrete measures.
Then, similar to the Step in the proof of Lemma A.8 there exists probability measure O s and subsequence {n& h221 such that Unz 8nz almost surely converges weakly to μ @ s.
Moreover, similar to Step 2 of Lemma A.8 Wi (umg
+ Sng μl @ 5) + as well as ||5mg liv + W, Wi s, All ullrv. But ( Vnn = ROBOTT Pn.) + RO,OTT(p,v). A|[ ROBOTz(H, v)).
|| @+ f4llry. Thus, W (Mm 8ML Vna by the proof of the discrete part ROBOT Therefore, with / + μ. W, (μ 8,
A S Lv
Therefore, ROBOT, lim supsupp.ss (O 2 ROBOT((H))) Thus the equal- ity holds.
15

---

Under review as a conference paper at ICLR 2021
Lemma A.8. Assume that p.v is such that [/ [ < cc. Moreover, assume that C(z, y) in equation the I norm, i.e., C(z,3) y) = 1| - yll. Then, there exists s with μ + s being probability measure such that
Wi(u + s, + A|| ROBOT())))
(A.3)
where W1 is the Wosserstein-I norm with the cost function C(:,)) as mentioned above.
Proof. Let Pas Vm be the empirical measures relative to μ. respectively. We know that since An: Vm are discrete, there exists 8n satisfying W1 W1n + Sn, Vm) = ROBOT( Vm). We provide the proof in the following steps.
Step 1:
Almost surely /a x v, there exists a subsequence {n*1 such that (14n + snhn In and {vn}a 3n relatively compact.
and y are probability measures on Ed and are therefore tight.
Let K, be such that Px K.); PY K2) S se/4.
Consider the empirical distributions Vn= = E; /n, pmn E, 5x,/n of v, respectively. Here, X; ~ 1 and Y; ~y-
Fix an W. Then xx....,,,,, Y1, } is fixed. Now by the construction for the discrete case, 8n has support in (XI,.... Xn, ...... .....
Let Tn be the optimal transport map from pn to Vn. Then, for every i S n, there exists a unique j S n, such that (X.) Yj. Define Tn {I,...,9) n) {1,...;.) .. such that (i) = if Tn (X,) = Yj. Then pn + = E3 óz,/n, where Z, = X, or Y (i) and dg is the Dirac delta mass x.
Then, let Z ~ pn +
Pu & Kelun + 8n) S Σ /xsees/n++ + E LxxeK.)/n
(A.4)
Therefore, E(Pa(Z $ (K Ke 8x)) S S//2. Moreover, (ar (2 & Kelpn + +nn) 1) + O. Therefore, lim Pa-xu=(PPu (Z & Kelpn + 8x) c) + Therefore Nnn + Sn is almost surely tight and thus by Prokhorov's 's Theorem also relatively compact.
Step 2: Therefore, for w almost surely, there exists a subsequence {na)a21 such that Pas + Snz converges weakly to limit (dependent on w) @ which is probability measure. Moreover, [ + 8ny) < oo almost surely. By Dolrano-Weierstrass Theorem, there exists a further subsequence (nt, h such that f [|=]|d(H],, + S - J ||.||d(u s) almost surely. For the sake of convenience, without loss of generality, we will replace the sub-subsequence (nR;) with { henceforth.
Thus, by Theorem 6.9 of (Villani 2009). Wi Wi(nn + Smg. μ + s) + almost surely. Moreover, Wi (Pmge (1) + 0 almost surely. Therefore || l|v + || @ #||Tv almost surely.
Step 3: Consider an arbitrary S = S - -S, such that S and S are positive measures on Rd, and μ + S is probability measure. Let ||S||Tv = 7. Then, |S llrv = || || = 7/2.
Then consider XI...., Xn ~ (n-S* 1-)-S/// /((1 7),, Yi...., Yn ~ S /T, EI...,, ~ S St/7 Then for any bounded continuous function f.
Σ = f [(0) (P (P-s)
lim
(1-7)- (dx)
n +00
lim ΣS(z)/n / f(xx) 8t
st (dx)
(A.5)
200
Therefore, the distribution given by (μ4 + S)+ & p+ S. and therefore from (Villani 2009), lim, 12o (((H+)))::.))) + (,++
()+t)m S), = (1 71)) E, LxEEA + (n) 12EA satisfies,
?
Moreover, ||S.|lzv = ||S||r,, where S, satisfies (n( = Σ, 12,EA - -E, 1yEA-
16

---

Under review as a conference paper at ICLR 2021
But, Wi Wi + SmL Vn2y + 2m lv v Willu =5) : A1 llrv. Therefore, taking limits, Wi(p ① s. + X 11 + - pl & W + and thus the proof holds with p B p..
B PROOF OF ADDITIONAL LEMMAS
B. PROOF OF LEMMA A.I
Proof. The fact that I1; I 0 follows from the fact that II; ž 0 and [[;1 = Q. To prove that 22 is diagonal, we use the fact that the any diagonal entry the cost matrix 0. Now suppose Iī is not diagonal. Then define a matrix fI as following: set II fl = 0, I II 12 and:
Ei= == II 22 (k,
if = i if +
(i,2(
0,
S, f) is feasible solution of Formu- Also define $ st and & as t(i) (t. Then clearly (1,, lation 1. Note that:
|l = 1 i1221 = 1 1'I1i,22 ||till1
and by our construction (Caugs fit < (Caug. 3T Hence (II, s, f) reduces the value of the objective function of Formulation which is a contradiction. This completes the proof.
B.2 PROOF OF LEMMA A.2
Proof. 1. Suppose j) > 0. Then dump this mass to si() and make it 0. In this way (Caug: IIf) will decrease by (i.I) and the regularizer value will increase by atmost (i, resulting in overall reduction in the objective value, which leads to a contradiction. Suppose each entry of ith row of C is 2X. Then if (i) > we can distribute this mass in the hth row such that, (i) = a2 + am with the condition that tī( 2 aj- Now we reduce ff as:
5 + - aj
Hence the value (Caug. (i. 5)) will increase by a value < 2 (i) but the value of regularizer will decrease by the value of (1), resulting in overall decrease in the value of objective function.
3. Same proof of part (2) by interchanging
and column in the argument.
4. Suppose not. Then choose < si) A (i), Add e to 11; (i, Hence the cost function value (Caug: Ili) will increase by 2de but the regularizer value will decrease by 2 resulting in overall decrease in the objective function.
B.3 PROOF OF LEMMA A.4
Proof. For the notational simplicity, we drop the subscript now as we will only deal with the solution of Formulation 4 and there will be ambiguity. We prove the Lemma by contradiction. Suppose si > O. Then we show one can come up with another solution (II, $1, 52) of Formulation such that it has lower objective value. To construct this new solution, make:
si 0,
if i if ifj=
$1
Now to change the optimal transport plan, will only change ith row of II. We subtract 41, ......, On 2 0 from th column of II* in such a way, such that none of the elements are negative. Hence the column will be change, i.e. the value of will be:
$2. 22 aj
V1 S KisK n.
17

---

Under review as a conference paper at ICLR 2021
Now clearly from construction:
(C, ii) I (C,
For the regularization part, note that, as we only reduced 8 element of s7, we have || ||s 1I T. And by simple triangle inequality,
$2 - ||sā|| + |ail2 = | + si,
by construction a,'s as 2 0 and Σ; 0g = ii,-- Hence we have:
| ||/| || s || si. = ||sil|
||
Hence the value corresponding regularizer will also decrease. This completes the proof.
B.4 PROOF LEMMA A.6
Proof. We prove this lemma by contradiction. Suppose Iī₃ does not have the structure mentioned in the statement of Lemma. Construct another transport plan for Formulation π, follows: Keep 32,12 12 and set lI,12 Construct the other parts as:
Σ -= II (1, Eh= (k,
if j i
0,
and
Ek= I (k; 0,
ifi= j if i
N (1,
It is immediate from the construction that:
(Caug: is)) < (Caug, mT:)
As for the regularization term: Note the by our construction $4 will be same as s as column sum of 11,,29 is same as 113,22. For the other threc:
31(1) (i,,
Σ II (1,
II (k,
52(1) = (1,
Σ 12 (ks
and hence by construction:
[2 | 1 II 3,22 1 || 11 1.
|| 1 11 1 111121211 ||
And also by construction, š1 s + where (II 11. As consequence have ||c]] TT Then it follows:
Bel
||st + cll || 1 2 || + ||>]||
|| + ||e|la 1 1 21
So the objective value overall reduced. This contradicts the optimality of IIg which completes the proof.
18

---

Under review as a conference paper at ICLR 2021
C PROOF OF THEOREM 2.
Proof. The proof is immediate from the Formulation Recall that the Formulation can restruc- tured
ROBOT v) inf (OT(P, + A|IP - p
P
where the infimum is taking over all measure dominated by some common measure a (with respect to which μu, Pes v are dominated), Hence,
(),) S (T( - Ällrv
for any particular choice of P. Taking P y1 get that
ROBOT v) & (T(H, v) + A|I - ÄllTV OT(H,
v)) + dellp- HellTv
Taking P = v we get ROBOT(i, D) < A|| - jällv and finally taking = fa we get ROBOT v) & D), This completes the proof.
19


Reviews:
[{"review_id": "MbX5tBwchtP", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "My evaluation:\n* The main methodological contribution, claimed in the paper, is the equivalence between Formulation 1, which is an optimal transport (OT) problem regularized with the TV norm, and Formulation 2, which is a pure OT problem, with a truncated cost. \nThis equivalence is actually straightforward for people working with convex relaxations of nonconvex problems, more precisely linear programming (LP) relaxations. In fact, as soon as I read eq. 2.1, I wondered: why don't they consider instead the problem under the form, which appears later as eq. 2.3?! This equivalence is used for instance in the IEEE PAMI paper \"What Is Optimized in Convex Relaxations for Multilabel Problems: Connecting Discrete and Continuously Inspired MAP Inference\", 2014. Indeed, the truncated l1 cost is used with the same motivation as yours in convex relaxations of assignment problems in computer vision, for instance for depth map reconstruction in stereovision.\nA short proof of the equivalence can be derived based on duality arguments: since the functionals are 1-homogeneous, in the dual domain we have an intersection of constrains, or equivalently the l_infinity norm which appears. It is known that the TV distance corresponds to OT with the 0-1 cost. So, since the regularized OT formulation is nothing but the infimal convolution of two convex functions, in the dual domain the constraints add up and we have the intersection of the two sets of constraints, which yields the minimum C_lambda of the two costs in the primal domain.\n* Even if the methodological contribution is not a real one for experts in a specific area of optimization, in the context of robust methods for data science, the equivalence is interesting to present. So, the real contribution, in my opinion, is the application of this model to robust estimation, which in itself is sufficient for publication to ICLR. You should shorten the discussion about the equivalence and put it in the Appendix altogether. \n* The application and the experiments show the relevance of the approach and its efficiency.\n\nMore detailed comments:\n1) The regularized formulation 2.1 and the constrained formulation just before are completely equivalent: for every epsilon there exists lambda, and conversely, such that the solutions are the same (with ~mu = mu+s). So, if the constrained formulation \"cannot distinguish between clean distributions\", your formulation 2.1 has the exact same property.\n2) \"The ε-contamination model imposes a cap...\" to have epsilon and not 2.epsilon, you should first define the total variation norm as ||s||_TV = (1/2)|s|(R^d) (because the 1/2 factor is not standard). Then remove \"and ||s||_TV denotes...\" after 2.2.\n3) The Wasserstein-1 distance is in some sense robust to outliers. For instance, in 1-D, if one minimizes the OT with W1 cost between diracs at locations s_1,...,s_N, and searches over Theta = set of Diracs with amplitude N, the solution is one dirac at the median of the s_n. It is robust to outliers: changing one s_n to a very large or very small value does not change the median. But I agree that the truncated l1 cost is even more robust.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "HLW7-8aFEf0", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a modification of optimal transport to make it more robust with respect to outliers.\n\nThe basic idea is to truncate the cost used in the OT cost. The authors show the equivalence of this OT model and a TV regularization of OT (with a cost which coincides up to truncation).\n\nNovelty is rather weak, the first formulation can be found as a special case of « Scaling algorithms for unbalanced optimal transport problems », Chizat et al (not mentioned in the paper). The model is already presented in the EMD literature by Peele and Werman (as mentioned in the paper).\n\nBibliography/background is insufficiently discussed. \nFormulation 2.1 is essentially similar to that in « Generalized Wasserstein distance and its application to transport equations with source », by Piccoli and Rossi (Eq. 3).\nThe model shares also important similarities with partial optimal transport. Although the authors do discuss a link with Unbalanced OT, they mention relaxing the marginal constraint with Kullback-Leibler divergence, instead there is a closer link to partial OT.\n\nTheoretical contribution: The equivalence between the two models is, to the best of my knowledge, new.\n\nExperiments: there are two setups in which the model is used. First one on a mixture of gaussian distributions, a toy experiment comparing standard OT with truncated OT and shows as expected better performance in estimating the mean of the first « clean » distribution. Second experiment has the goal of identifying outliers and experiment it with GAN. \nFor this second application, a comparison with simple methods of outlier detection would have been welcome.\n\nWriting: the paper is clearly written.\n\nValuable improvements for this work would focus on the experiment section. Comparing with other methods such as unbalanced OT and comparing with other methods of outlier detection.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Bv-pHxTCQs", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose to address the robustness over outliers for optimal transport (OT). They propose a new formulation based on penalizing the contaminated probability measures by a signed measure (which shares a close relation with unbalanced OT). The authors further derive an equivalent formulation by adjusting the cost matrix for the corresponding standard OT. Empirically, the authors evaluate their proposed approach on a toy example of robust mean estimation and outlier detection for data collection.  \n\nThe idea to address the robustness over outliers for optimal transport is interesting. Although I have not checked the proof in detail, I think that the derived equivalence formulation (Formulation 2) which is a standard OT with the clipped cost. However, in my opinion, the problem (robustness to outliers) for OT is closely related to partial OT (and/or unbalanced OT) where one only optimal the partial alignment for probability measures (or relaxing the marginal constraints during optimization by divergence). (See [1])\n+ Indeed, Formulation 1 shares a close relationship with the entropy transport problem (in Liero et al. [1]) where the divergence is a total variation. (See also [2])\n+ There is a parallel work that appears in NeurIPS'2020 [3]. In [3], the authors also address the robustness of OT over outliers relying on unbalanced OT, and applies it into generative modeling, and domain adaptation.\n\nIt seems that the authors identify outliers from their distances to supports of the main distributions (which may explain the truncated cost in Formulation 2). Is it possible to just simply use a threshold to detect \"outliers\" as in applications in 4.2?\n\nAs in Algorithm 1 (and Figure 1), it seems that we can simply discard the constants $\\Pi_{11}$ and $\\Pi_{21}$ to reduce $\\Pi$ into a matrix (n+m) x m\n\nSome of my other concerns are as follow:  \n+ Although the new formulations are interesting, the authors should compare their approach with the partial OT and/or unbalanced OT which addresses the same concern for OT problem.\n+ The assumption about a \"clean\" distribution for 1 of the 2 input ones for ROBOT is quite strong in applications. In this sense, I think that the unbalanced OT (as in [3]) may be more advantageous. \n\nReferences:\n\n[1] Matthias Liero, Alexander Mielke, and GiuseppeSavaré. Optimal entropy-transport problems and a new hellinger–kantorovich distance between positive measures. Inventiones mathematicae,211(3):969–1117, 2018.)\n\n[2] Benedetto Piccoli and Francesco Rossi. Generalized wasserstein distance and its application to transport equations with source. Archive for Rational Mechanics and Analysis, 211(1):335–358,2014.)\n\n[3] Yogesh Balaji, Rama Chellappa, Soheil Feizi. Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation. NeurIPS, 2020.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "8AWoydPV_lb", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "SUMMARY\n#######\n\nThe present paper proposes a way to robustify Optimal Transport (OT) with respect to outliers.\n\nAssuming that one of the distributions on which OT is computed is $\\epsilon$ corrupted (the second distribution being a parametrized distribution one wants to make close to the first one), authors propose to solve Kantorovich's problem for all distributions that are within an $\\epsilon$-TV distance from distribution 1.\n\nThis problem is however hard to compute in practice, and an equivalent problem is proposed, based on a truncated cost.\n\nIt is formally proved that solving the second formulation gives a solution to the first one, and how to compute the optimal coupling matrix (in the discrete case).\n\nExperiments are proposed, both on robust mean estimation for simulated data, and outlier detection on MNIST.\n\n\n\nOPINION\n#######\n\nAs for positive aspects, I find that:\n- the paper is globally clear and well written, despite some minor clarity flaws (see below)\n- the intuitions are well exposed and easy to follow\n\n\nHowever, I find this contribution insufficient with respect to the following points:\n\n- my main concern is about the lack of theoretical grounding for the proposed contribution. In particular:\na) other works with a different approach (see point on related works below) have derived consistency and convergence results for their estimator in the presence of outliers, does something similar hold for ROBOT?\nb) formulation 1 uses explicitly the proportion of outliers $\\epsilon$. What happens if the latter is only approximately known (which is much more likely in practice)?\nc) formulation 2 uses an extra hyperparameter $\\lambda$, related to $\\epsilon$ in a very complex way that is hard to interpret, and for which no selection procedure is proposed except cross validation.\nd) in the end, the proposed method thus boils down to the introduction of a new threshold parameter $\\lambda$, and a \"test all possible values, one should yield a better result\" strategy. I find it a bit disappointing not to have more theoretical insights. I agree however that the threshold makes perfect sense here, and that ROBOT is \"always\" better than vanilla OT in the proposed experiments. But this behavior is not that uncommon for threshold parameters ($epsilon$-insensitive, huber loss) and it is difficult to say something else than \"we have added another hyperparameter\".\n\n- p.1 \"can have an outsized impact\": what if the cost function is already robust (e.g. Wasserstein 1)? Have authors noticed differences with respect to the cost used?\n\n- p.1 \"there are no methods in the literature for achieving outlier-robustness with MKE\": the following two references might be relevant\na) Staerman, Guillaume, et al. \"When OT meets MoM: Robust estimation of Wasserstein Distance.\" arXiv preprint arXiv:2006.10325 (2020).\nb) Balaji, Yogesh, Rama Chellappa, and Soheil Feizi. \"Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation.\" arXiv preprint arXiv:2010.05862 (2020).\n\n- p.2 \"the value of outliers is arbitrary\": the standard framework of OT is on bounded observations. In that case, how large can be the impact of bounded outliers?\n\n- p.5 1 algorithm + 1 explicative paragraph + 1 figure seems a bit too much for a procedure which is not that complex\n\n- from what I have seen in the core text and proofs, only getting a solution to Robot_1 from a solution to Robot_2 is proposed, while Thm 3.1 suggests both directions are possible\n\n- p.12 what does \"suppose\" mean? I might have missed something, but you cannot suppose anything here. Or the contradiction you get in the end might refute this assumption, rather than the fact that $\\Pi_2^*$ is optimal.\n\n- What happens if $\\nu$ is also corrupted?\n\n\n\nMINOR COMMENTS\n##############\n\np.1 $\\mu$ and $\\nu$ instead of $P_1$ and $P_2$ in eq. (1.1)\np.1 $c$ is not defined in eq. (1.1)\np.1 $\\nu_\\theta$ is not defined in eq. (1.2) (although it is globally understandable)\np.2 $\\epsilon$ should be in the interval [0, 1/2]?\np.2 and after TV *distance* and not *norm*\np.2 TV subscripts in the last paragraph\np.3 C\\lambda*(x,y)* in eq. (2.3)\np.3 to formulate *a* discrete\np.3 *a* discrete analog of\np.3 $\\Delta^{m-1}$ is not defined\np.3 it should be better explained why one needs to consider the augmented versions\np.4 $s_1$ and $t_1$ are not defined. Maybe $s$ and $t$ is enough, since there is not $s_2$\np.4 shouldn't it be + 2 *\\lambda in eq. (2.4)?\np.4 $1_m$ is not defined\np.4 it is a bit misleading to have the same notation $\\mu_n$ for the vectors and the distributions\np.4 \"we can recover optimal solution\" --> \"optimal coupling\" may be more clear, as the solutions are supposed to be the same\np.5 the block matrix notation of Sec. 3.2 is not very standard, and could be replaced by the one used in Alg. 1\np.5 we *are* not moving\np.6 in ou*r* second experiment\np.11 this is not an*d* optimal solution\np.12 *&* symbol, quite unusual\n\n\n\nOVERALL EVALUATION\n##################\n\nAlthough the equivalence result is interesting, I find the contribution slightly insufficient to warrant acceptance, as the proposed method essentially boils down to adding an extra threshold hyperparameter, without more theoretical discussion.\n\n\n--- EDIT POST REBUTTAL ---\n\nI thank the authors for their answer and their efforts in editing the submission. I have also read other reviews and replies. However, my stance on the paper did not really change as I find the contribution insufficient for acceptance. \n\nPS: when I wrote \"Formulation 1 uses explicitly the proportion of outliers\", I was referring to the display equation above eq. (2.1). I did not realize the term \"formulation\" was already formally used in the paper to refer to another equation.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a novel approach to detect outliers using Optimal transport. the authors prove a very interesting relation between Outlier robust OT and solving OT with a  thresholded loss. Numerical experiments show that the proposed approach indeed work for outlier detection. 

The paper had mixed reviews and the comments and changes from the authors were appreciated. The comments about recent (and contemporary) references were not taken into account in the final decision following ICLR guidelines. 

One major concern that appeared during discussion was the fact that one important claimed contribution is the ability to perform outlier detection, the proposed method is never evaluated or compared to the numerous existing outlier detection methods. It works on a toy example and seem to provide a robust way to train a robust GAN but the experiments are very limited. Also the claim from the authors that the method scales are not really true. The proposed approach requires solving an exact OT of complexity O(N^3log(N)), while one can use an approximated entropic solver on the thresholded loss it does not solve the ROBOT problem anymore and the relations between the problem does not exist anymore in this case (or are more similar to UOT).

The concerns detailed above and the limited novelty of the contributions (most of the formulations proposed in the paper are already existing in the literature) suggest that the paper in its current iteration  is too borderline for being accepted in a selective venue such as ICLR. The method and the relations uncovered are interesting and the AC encourages the authors to continue work on the proposed method and provide more detailed experiments illustrating and comparing the method to baselines for outlier detection.

Decision: Reject