Robust Distribution Learning with Local and Global Adversarial Corruptions

We consider learning in an adversarial environment, where an -fraction of samples from a distribution P are arbitrarily modified (*global* corruptions) and the remaining perturbations have average magnitude bounded by (*local* corruptions). Given access to n such corrupted samples, we seek a computationally efficient estimator Pₙ that minimizes the Wasserstein distance W₁ (Pₙ, P). In fact, we attack the fine-grained task of minimizing W₁ (_\# Pₙ, _\# P) for all orthogonal projections R^d d, with performance scaling with rank () = k. This allows us to account simultaneously for mean estimation (k=1), distribution estimation (k=d), as well as the settings interpolating between these two extremes. We characterize the optimal population-limit risk for this task and then develop an efficient finite-sample algorithm with error bounded by k + + d^O (1) O (n^-1/k) when P has bounded moments of order 2+, for constant > 0. For data distributions with bounded covariance, our finite-sample bounds match the minimax population-level optimum for large sample sizes. Our efficient procedure relies on a novel trace norm approximation of an ideal yet intractable 2-Wasserstein projection estimator. We apply this algorithm to robust stochastic optimization, and, in the process, uncover a new method for overcoming the curse of dimensionality in Wasserstein distributionally robust optimization.