Robust Distribution Learning with Local and Global Adversarial Corruptions

Abstract

We consider learning in an adversarial environment, where an $\epsilon$-fraction of samples from a distribution $P$ are arbitrarily modified (global corruptions) and the remaining perturbations have average magnitude bounded by $\rho$ (local corruptions). Given access to $n$ such corrupted samples, we seek a computationally efficient estimator ${\hat{P}}_n$ that minimizes the Wasserstein distance ${\mathsf{W}}_1({\hat{P}}_n,P)$. In fact, we attack the fine-grained task of minimizing ${\mathsf{W}}_1({\Pi }_{\#}{\hat{P}}_n,{\Pi }_{\#}P)$ for all orthogonal projections $\Pi \in {\mathbb{R}}^{d\times d}$, with performance scaling with $\mathrm{rank}(\Pi )=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 $\sqrt{\epsilon k}+\rho +\tilde{O}(d\sqrt{k}{n}^{-1/(k\vee 2)})$ when $P$ has bounded covariance. This guarantee holds uniformly in $k$ and is minimax optimal up to the sub-optimality of the plug-in estimator when $\rho =\epsilon =0$. 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.

Accepted for presentation at the Conference on Learning Theory (COLT) 2024