mlsanityData to 14 Oct 2026

Robust estimation algorithms don't need to know the corruption level

arXiv 2202.05453 ↗First posted 11 Feb 2022cs.LG stat.MLcited by 4

Not on the map. Why?

Abstract (arXiv)

Real data are rarely pure. Hence the past half-century has seen great interest in robust estimation algorithms that perform well even when part of the data is corrupt. However, their vast majority approach optimal accuracy only when given a tight upper bound on the fraction of corrupt data. Such bounds are not available in practice, resulting in weak guarantees and often poor performance. This brief note abstracts the complex and pervasive robustness problem into a simple geometric puzzle. It then applies the puzzle's solution to derive a universal meta technique that converts any robust estimation algorithm requiring a tight corruption-level upper bound to achieve its optimal accuracy into one achieving essentially the same accuracy without using any upper bounds.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 24 of its 43 references that are in the map. First posted on arXiv 11 Feb 2022.

Builds on

24 of 43 references.

References · 24

  1. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  2. 2016Agnostic Estimation of Mean and Covariancecited by 131
  3. 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 125
  4. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 101
  5. 2016Learning from Untrusted Datacited by 90
  6. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  7. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  8. 2018Robust Estimation via Robust Gradient Estimationcited by 76
  9. 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
  10. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  11. 2020Robust regression with covariate filtering: Heavy tails and adversarial contaminationcited by 50
  12. 2017Resilience: A Criterion for Learning in the Presence of Arbitrary Outlierscited by 43
12 more
  1. 2017Robustly Learning a Gaussian: Getting Optimal Error, Efficientlycited by 39
  2. 2019Generalized Resilience and Robust Statisticscited by 37
  3. 2018High Dimensional Robust Sparse Regressioncited by 29
  4. 2020Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contaminationcited by 26
  5. 2019Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filteringcited by 23
  6. 2021Robust Regression Revisited: Acceleration and Improved Estimation Ratescited by 15
  7. 2017Learning Discrete Distributions from Untrusted Batchescited by 14
  8. 2019Optimal Robust Learning of Discrete Distributions from Batchescited by 10
  9. 2019Efficiently Learning Structured Distributions from Untrusted Batchescited by 8
  10. 2020Learning Structured Distributions From Untrusted Batches: Faster and Simplercited by 8
  11. 2020A General Method for Robust Learning from Batchescited by 8
  12. 2021Robust Estimation for Random Graphscited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 0; 2024: 2; 2025: 0; 2026: 1.

4 papers.

  1. 2024Distribution Learnability and Robustnesscited by 4
  2. 2024The Broader Landscape of Robustness in Algorithmic Statisticscited by 2
  3. 2026Robust Regression with Adaptive Contamination in Response: Optimal Rates and Computational Barrierscited by 1
  4. 2022TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithmcited by 0