Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: SUMMARY
#######

The present paper proposes a way to robustify Optimal Transport (OT) with respect to outliers.

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

This problem is however hard to compute in practice, and an equivalent problem is proposed, based on a truncated cost.

It 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).

Experiments are proposed, both on robust mean estimation for simulated data, and outlier detection on MNIST.



OPINION
#######

As for positive aspects, I find that:
- the paper is globally clear and well written, despite some minor clarity flaws (see below)
- the intuitions are well exposed and easy to follow


However, I find this contribution insufficient with respect to the following points:

- my main concern is about the lack of theoretical grounding for the proposed contribution. In particular:
a) 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?
b) 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)?
c) 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.
d) 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".

- 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?

- p.1 "there are no methods in the literature for achieving outlier-robustness with MKE": the following two references might be relevant
a) Staerman, Guillaume, et al. "When OT meets MoM: Robust estimation of Wasserstein Distance." arXiv preprint arXiv:2006.10325 (2020).
b) Balaji, Yogesh, Rama Chellappa, and Soheil Feizi. "Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation." arXiv preprint arXiv:2010.05862 (2020).

- 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?

- p.5 1 algorithm + 1 explicative paragraph + 1 figure seems a bit too much for a procedure which is not that complex

- 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

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

- What happens if $\nu$ is also corrupted?



MINOR COMMENTS
##############

p.1 $\mu$ and $\nu$ instead of $P_1$ and $P_2$ in eq. (1.1)
p.1 $c$ is not defined in eq. (1.1)
p.1 $\nu_\theta$ is not defined in eq. (1.2) (although it is globally understandable)
p.2 $\epsilon$ should be in the interval [0, 1/2]?
p.2 and after TV *distance* and not *norm*
p.2 TV subscripts in the last paragraph
p.3 C\lambda*(x,y)* in eq. (2.3)
p.3 to formulate *a* discrete
p.3 *a* discrete analog of
p.3 $\Delta^{m-1}$ is not defined
p.3 it should be better explained why one needs to consider the augmented versions
p.4 $s_1$ and $t_1$ are not defined. Maybe $s$ and $t$ is enough, since there is not $s_2$
p.4 shouldn't it be + 2 *\lambda in eq. (2.4)?
p.4 $1_m$ is not defined
p.4 it is a bit misleading to have the same notation $\mu_n$ for the vectors and the distributions
p.4 "we can recover optimal solution" --> "optimal coupling" may be more clear, as the solutions are supposed to be the same
p.5 the block matrix notation of Sec. 3.2 is not very standard, and could be replaced by the one used in Alg. 1
p.5 we *are* not moving
p.6 in ou*r* second experiment
p.11 this is not an*d* optimal solution
p.12 *&* symbol, quite unusual



OVERALL EVALUATION
##################

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


--- EDIT POST REBUTTAL ---

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

PS: 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.
review_title: Lack of theoretical grounding

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.  

The 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])
+ 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])
+ 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.

It 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?

As 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

Some of my other concerns are as follow:  
+ 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.
+ 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. 

References:

[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.)

[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.)

[3] Yogesh Balaji, Rama Chellappa, Soheil Feizi. Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation. NeurIPS, 2020.



review_title: Outlier Robust Optimal Transport 

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes a modification of optimal transport to make it more robust with respect to outliers.

The 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).

Novelty 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).

Bibliography/background is insufficiently discussed. 
Formulation 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).
The 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.

Theoretical contribution: The equivalence between the two models is, to the best of my knowledge, new.

Experiments: 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. 
For this second application, a comparison with simple methods of outlier detection would have been welcome.

Writing: the paper is clearly written.

Valuable 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.
review_title: Outlier robust OT is particular case of Unbalanced OT.

final_score: rating: 7: Good paper, accept
review_content: My evaluation:
* 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. 
This 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.
A 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.
* 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. 
* The application and the experiments show the relevance of the approach and its efficiency.

More detailed comments:
1) 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.
2) "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.
3) 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.

review_title: Good paper, as an advocate of optimal transport with truncated cost for robust estimation of distributions in data science

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