When does the Tukey median work?
This work addresses robustness in statistical estimation for high-dimensional data, providing theoretical guarantees for corruption models, but it is incremental as it builds on prior breakdown point results.
The paper analyzes the Tukey median estimator under total variation corruptions, showing its breakdown point reduces to 1/4 for high-dimensional halfspace-symmetric distributions, and presents a projection algorithm achieving an optimal breakdown point of 1/2 with linear sample complexity in dimension.
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.