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.

Solution

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

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/iii/paper-223/4/b/solution