2024/06/10 by Sloan Nietert, Nietert, Sloan, Ziv Goldfeld +3 · 2 citations
Computer Science · Mathematics · #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and ELM #Survey Sampling and Estimation Techniques
paper · pdf · doi:10.48550/arxiv.2406.06509
openalex publication_date 2024/06/10 · openalex created_date 2024/06/12 · openalex updated_date 2026/07/28
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 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 Π∈ ℝ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) + ρ+ O(d√(k)n-1/(k ∨ 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 ρ= ε = 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.