2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | E.3.4 | ||
| Paper Title | When does the Tukey Median work? | ||
| Authors | Banghua Zhu, Jiantao Jiao, Jacob Steinhardt, University of California, Berkeley, United States | ||
| Session | E.3: Estimation Theory | ||
| Presentation | Lecture | ||
| Track | Detection and Estimation | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| 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 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. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
