[edit]
Robust Distribution Learning with Local and Global Adversarial Corruptions (extended abstract)
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4007-4008, 2024.
Abstract
We consider learning in an adversarial environment, where an ε-fraction of samples from a distribution P are arbitrarily modified (\emph{global} corruptions) and the remaining perturbations have average magnitude bounded by ρ (\emph{local} corruptions). Given access to n such corrupted samples, we seek a computationally efficient estimator ˆPn that minimizes the Wasserstein distance W1(ˆPn,P). In fact, we attack the fine-grained task of minimizing W1(Π♯ˆPn,Π♯P) for all orthogonal projections Π∈Rd×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+ρ+˜O(k√dn−1/k) when P has bounded covariance. 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.