# When does the Tukey median work?

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jan 2020.

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

- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Sentence-level Privacy for Document Embeddings](https://mlsanity.com/paper/2205.04605/) (2022)
- [Robust Estimation for Nonparametric Families via Generative Adversarial Networks](https://mlsanity.com/paper/2202.01269/) (2022)
- [Differentially private multivariate medians](https://mlsanity.com/paper/2210.06459/) (2022)
- [Noisy Computing of the mathsfOR and mathsfMAX Functions](https://mlsanity.com/paper/2309.03986/) (2023)

## Abstract (arXiv)

We analyze the performance of the Tukey median estimator under total variation (TV) distance corruptions. Previous results show that under Huber's additive corruption model, the breakdown point is 1/3 for high-dimensional halfspace-symmetric distributions. We show that under TV corruptions, the breakdown point reduces to 1/4 for the same set of distributions. We also show that a certain projection algorithm can attain the optimal breakdown point of 1/2. Both the Tukey median estimator and the projection algorithm achieve sample complexity linear in dimension.