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

arXiv: https://arxiv.org/abs/2202.05453 · HTML: https://mlsanity.com/paper/2202.05453/

## 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 (most cited first, 24 of 24)

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Robust Estimation via Robust Gradient Estimation](https://mlsanity.com/paper/1802.06485/) (2018)
- [Efficient Algorithms and Lower Bounds for Robust Linear Regression](https://mlsanity.com/paper/1806.00040/) (2018)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [Robust regression with covariate filtering: Heavy tails and adversarial contamination](https://mlsanity.com/paper/2009.12976/) (2020)
- [Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers](https://mlsanity.com/paper/1703.04940/) (2017)
- [Robustly Learning a Gaussian: Getting Optimal Error, Efficiently](https://mlsanity.com/paper/1704.03866/) (2017)
- [Generalized Resilience and Robust Statistics](https://mlsanity.com/paper/1909.08755/) (2019)
- [High Dimensional Robust Sparse Regression](https://mlsanity.com/paper/1805.11643/) (2018)
- [Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination](https://mlsanity.com/paper/2010.04157/) (2020)
- [Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering](https://mlsanity.com/paper/1911.08085/) (2019)
- [Robust Regression Revisited: Acceleration and Improved Estimation Rates](https://mlsanity.com/paper/2106.11938/) (2021)
- [Learning Discrete Distributions from Untrusted Batches](https://mlsanity.com/paper/1711.08113/) (2017)
- [Optimal Robust Learning of Discrete Distributions from Batches](https://mlsanity.com/paper/1911.08532/) (2019)
- [Efficiently Learning Structured Distributions from Untrusted Batches](https://mlsanity.com/paper/1911.02035/) (2019)
- [Learning Structured Distributions From Untrusted Batches: Faster and Simpler](https://mlsanity.com/paper/2002.10435/) (2020)
- [A General Method for Robust Learning from Batches](https://mlsanity.com/paper/2002.11099/) (2020)
- [Robust Estimation for Random Graphs](https://mlsanity.com/paper/2111.05320/) (2021)

## Built on by (most cited first, 4 of 4)

- [Distribution Learnability and Robustness](https://mlsanity.com/paper/2406.17814/) (2024)
- [The Broader Landscape of Robustness in Algorithmic Statistics](https://mlsanity.com/paper/2412.02670/) (2024)
- [Robust Regression with Adaptive Contamination in Response: Optimal Rates and Computational Barriers](https://mlsanity.com/paper/2604.04228/) (2026)
- [TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm](https://mlsanity.com/paper/2202.07172/) (2022)

## 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.