Outlier-Robust Optimal Transport

Debarghya Mukherjee, Aritra Guha, Justin M Solomon, Yuekai Sun, Mikhail Yurochkin
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:7850-7860, 2021.

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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v139-mukherjee21a, title = {Outlier-Robust Optimal Transport}, author = {Mukherjee, Debarghya and Guha, Aritra and Solomon, Justin M and Sun, Yuekai and Yurochkin, Mikhail}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {7850--7860}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/mukherjee21a/mukherjee21a.pdf}, url = {https://proceedings.mlr.press/v139/mukherjee21a.html}, 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.} }
Endnote
%0 Conference Paper %T Outlier-Robust Optimal Transport %A Debarghya Mukherjee %A Aritra Guha %A Justin M Solomon %A Yuekai Sun %A Mikhail Yurochkin %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-mukherjee21a %I PMLR %P 7850--7860 %U https://proceedings.mlr.press/v139/mukherjee21a.html %V 139 %X 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.
APA
Mukherjee, D., Guha, A., Solomon, J.M., Sun, Y. & Yurochkin, M.. (2021). Outlier-Robust Optimal Transport. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:7850-7860 Available from https://proceedings.mlr.press/v139/mukherjee21a.html.

Related Material