= Solution
Replace the same last $k$ vectors by $(100,\ldots,100)$. Applying part a to each independent Gaussian coordinate shows that the probability its contaminated coordinate median exceeds $\epsilon$ is at least $1-e^{-c_\epsilon n}$. Independence across coordinates and <Bernoulli's inequality> give
$$
\mathbb P\!\left(
\widehat\mu_j>\epsilon\text{ for every }j
\right)
\geq(1-e^{-c_\epsilon n})^d
\geq1-de^{-c_\epsilon n}.
$$
For $n$ sufficiently large as a function of $d$ and $\epsilon$, the last expression is at least $1/2$. On this event,
$$
\|\widehat\mu\|_2>\epsilon\sqrt d,
$$
which proves the stated lower bound for the supremum over adversarial perturbations.
Back to article page
