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

Assume first that $0<ϵ<1/2$, set $k=\lfloor ϵn\rfloor$, and replace the last $k$ observations by $100$. Among the remaining $m=n-k$ observations, letThe contaminated median exceeds $ϵ$ wheneverThe right-hand threshold divided by $m$ tends toTherefore, for all sufficiently large $n$, it is at most $p_{ϵ}-{\delta }_{ϵ}$ for some ${\delta }_{ϵ}>0$. The Hoeffding inequality givesThe supremum over adversarial perturbations is at least this explicit construction, proving the claim. When $ϵ\ge 1/2$, replacing at least half the sample makes the conclusion immediate.

Replace the same last $k$ vectors by $(100,\dots ,100)$. Applying part a to each independent Gaussian coordinate shows that the probability its contaminated coordinate median exceeds $ϵ$ is at least $1-e^{-c_{ϵ}n}$. Independence across coordinates and Bernoulli's inequality giveFor $n$ sufficiently large as a function of $d$ and $ϵ$, the last expression is at least $1/2$. On this event,which proves the stated lower bound for the supremum over adversarial perturbations.

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.