Outlier-Robust Optimal Transport

Abstract

Optimal transport (OT) measures distances between distributions in a way that depends on the geometry of the sample space. In light of recent advances in computational OT, OT distances are widely used as loss functions in machine learning. Despite their prevalence and advantages, OT loss functions can be extremely sensitive to outliers. In fact, a single adversarially-picked outlier can increase the standard $W_2$-distance arbitrarily. To address this issue, we propose an outlier-robust formulation of OT. Our formulation is convex but challenging to scale at a first glance. Our main contribution is deriving an \emph{equivalent} formulation based on cost truncation that is easy to incorporate into modern algorithms for computational OT. We demonstrate the benefits of our formulation in mean estimation problems under the Huber contamination model in simulations and outlier detection tasks on real data.

arXiv commentAccepted in Proceedings of the 38th International Conference on Machine Learning, PMLR 139, 2021

References in corpus (11)

• Scikit-learn: Machine Learning in Python
• Generalized Wasserstein distance and its application to transport equations with source
• Stochastic Optimization for Large-scale Optimal Transport
• Learning with Bad Training Data via Iterative Trimmed Loss Minimization
• Single-Model Uncertainties for Deep Learning
• Large-Scale Optimal Transport and Mapping Estimation
• Hierarchical Optimal Transport for Document Representation
• Multilevel Clustering via Wasserstein Means
• Scalable Bayes via Barycenter in Wasserstein Space
• Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation
• When OT meets MoM: Robust estimation of Wasserstein Distance

Cited by in corpus (5)

• Unbalanced minibatch Optimal Transport; applications to Domain Adaptation
• Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
• Unbalanced Optimal Transport through Non-negative Penalized Linear Regression
• Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe
• A Pseudo-Metric between Probability Distributions based on Depth-Trimmed Regions