Outlier-Robust Optimal Transport: Duality, Structure, and Statistical Analysis

The Wasserstein distance, rooted in optimal transport (OT) theory, is a\npopular discrepancy measure between probability distributions with various\napplications to statistics and machine learning. Despite their rich structure\nand demonstrated utility, Wasserstein distances are sensitive to outliers in\nthe considered distributions, which hinders applicability in practice. We\npropose a new outlier-robust Wasserstein distance $\\mathsf{W}_p^\\varepsilon$\nwhich allows for $\\varepsilon$ outlier mass to be removed from each\ncontaminated distribution. Under standard moment assumptions,\n$\\mathsf{W}_p^\\varepsilon$ is shown to achieve strong robust estimation\nguarantees under the Huber $\\varepsilon$-contamination model. Our formulation\nof this robust distance amounts to a highly regular optimization problem that\nlends itself better for analysis compared to previously considered frameworks.\nLeveraging this, we conduct a thorough theoretical study of\n$\\mathsf{W}_p^\\varepsilon$, encompassing robustness guarantees,\ncharacterization of optimal perturbations, regularity, duality, and statistical\nestimation. In particular, by decoupling the optimization variables, we arrive\nat a simple dual form for $\\mathsf{W}_p^\\varepsilon$ that can be implemented\nvia an elementary modification to standard, duality-based OT solvers. We\nillustrate the virtues of our framework via applications to generative modeling\nwith contaminated datasets.\n