|When does the Tukey Median work?
|Banghua Zhu, Jiantao Jiao, Jacob Steinhardt, University of California, Berkeley, United States
|E.3: Estimation Theory
|Detection and Estimation
|Click here to download the manuscript
|Click here to watch in the Virtual Symposium
|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 the algorithm projecting under the halfspace metric to the set of halfspace-symmetric distributions can improve the breakdown point to 1/2. Both the Tukeymedian estimator and the projection algorithm achieve sample complexity linear in dimension.