Technical Program

Paper Detail

Paper IDE.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

Visit Website!