mlsanityData to 14 Oct 2026

Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Error

arXiv 2410.17230 ↗First posted 22 Oct 2024cs.DS cs.LG math.STcited by 2

Not on the map. Why?

Abstract (arXiv)

Algorithmic robust statistics has traditionally focused on the contamination model where a small fraction of the samples are arbitrarily corrupted. We consider a recent contamination model that combines two kinds of corruptions: (i) small fraction of arbitrary outliers, as in classical robust statistics, and (ii) local perturbations, where samples may undergo bounded shifts on average. While each noise model is well understood individually, the combined contamination model poses new algorithmic challenges, with only partial results known. Existing efficient algorithms are limited in two ways: (i) they work only for a weak notion of local perturbations, and (ii) they obtain suboptimal error for isotropic subgaussian distributions (among others). The latter limitation led [NGS24, COLT'24] to hypothesize that improving the error might, in fact, be computationally hard. Perhaps surprisingly, we show that information theoretically optimal error can indeed be achieved in polynomial time, under an even stronger local perturbation model (the sliced-Wasserstein metric as opposed to the Wasserstein metric). Notably, our analysis reveals that the entire family of stability-based robust mean estimators continues to work optimally in a black-box manner for the combined contamination model. This generalization is particularly useful in real-world scenarios where the specific form of data corruption is not known in advance. We also present efficient algorithms for distribution learning and principal component analysis in the combined contamination model.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 21 of its 37 references that are in the map. First posted on arXiv 22 Oct 2024.

Builds on

21 of 37 references.

References · 21

  1. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  2. 2016Agnostic Estimation of Mean and Covariancecited by 131
  3. 2021SPECTRE: Defending Against Backdoor Attacks Using Robust Statisticscited by 130
  4. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  5. 2020Outlier Robust Mean Estimation with Subgaussian Rates via Stabilitycited by 50
  6. 2024Statistical optimal transportcited by 47
  7. 2019Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detectioncited by 41
  8. 2020Robust Meta-learning for Mixed Linear Regression with Small Batchescited by 41
  9. 2018High-Dimensional Robust Mean Estimation in Nearly-Linear Timecited by 39
  10. 2019Robust subgaussian estimation of a mean vector in nearly linear timecited by 37
  11. 2020Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packingcited by 35
  12. 2017Outlier-robust moment-estimation via sum-of-squarescited by 27
9 more
  1. 2019Minimax Confidence Intervals for the Sliced Wasserstein Distancecited by 24
  2. 2022Robust Sparse Mean Estimation via Sum of Squarescited by 24
  3. 2022Streaming Algorithms for High-Dimensional Robust Statisticscited by 21
  4. 2019How Hard Is Robust Mean Estimation?cited by 16
  5. 2020High-Dimensional Robust Mean Estimation via Gradient Descentcited by 16
  6. 2019Deconstructing Generative Adversarial Networkscited by 15
  7. 2023Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCAcited by 10
  8. 2021Robust W-GAN-Based Estimation Under Wasserstein Contaminationcited by 9
  9. 2024Black-Box k-to-1-PCA Reductions: Theory and Applicationscited by 7

Built on by

Cited by year

Citing papers per year: 2025: 2.

2 papers.

  1. 2025Distributionally Robust Optimization with Adversarial Data Contaminationcited by 1
  2. 2025Estimation of Stochastic Optimal Transport Mapscited by 1