When does the Tukey median work?

Abstract

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.

References in corpus (1)

• Generalized Resilience and Robust Statistics

Cited by in corpus (4)

• Robust estimation via generalized quasi-gradients
• All-In-One Robust Estimator of the Gaussian Mean
• Robust and Differentially Private Mean Estimation
• Robust Mean Estimation in High Dimensions via ${\ell }_0$ Minimization