Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 223 / 4 / c / Solution

The coordinatewise median suffers a contamination error of order $ϵ\sqrt{d}$ with constant probability. In contrast, the Tukey median under an isotropic Gaussian model satisfies a high-probability Euclidean error bound of orderwith probability at least $1-\delta$, up to universal constants. Its contamination term is dimension-free. Thus coordinatewise estimation loses a factor $\sqrt{d}$ in its dependence on adversarial contamination.