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

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.