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

After the replacement, the objective isby Euclidean norm duality. It is nonnegative and equals zero exactly at $\mu ={\mu }_0$, so ${\mu }_0$ is the unique minimizer.

DefineFor every unit-ball vector $v$, the triangle inequality givesTaking the supremum and using optimality, $R_X(\hat{\mu })\le R_X({\mu }_0)$, yields

Choose a fixed $\alpha <1/2$. On the stated high-probability event, strictly more than half of the block means satisfy, simultaneously for every $\Vert v{\Vert }_2\le 1$,The median of a collection with a strict majority in an interval lies in that interval. Hence the same bound holds for $|{\mathrm{MOM}}_k(Xv)-{\mu }_0^{T}v|$ uniformly in $v$. Part b then giveswith probability at least $1-e^{-k/c_{\alpha }}$. Renaming the constant proves the claim.

Use the quoted event with, for example, $\alpha =1/4$, so at least $3k/4$ clean block means obey the uniform bound. Replacing at most $ϵn$ observations can corrupt at most $ϵn$ blocks. If $k\ge 4\max \{nϵ,1\}$, at least $3k/4-ϵn\ge k/2$ block means remain both uncorrupted and good; adjusting constants handles equality and integer rounding. Their strict majority forces every projected median to obey the same uniform bound. Applying part b and absorbing fixed constants giveswith probability at least $1-e^{-c^{\prime }k}$.

For $\Sigma =I_d$, $\mathrm{tr}(\Sigma )=d$ and $\Vert \Sigma {\Vert }_2=1$. Taking $k$ of order $\max \{nϵ,1\}$ in part d givesFor Gaussian data under Huber contamination, the Tukey median has the sharper dependenceup to universal constants in its valid contamination range. Both have the same sampling term $\sqrt{d/n}$, but the Tukey median is linear rather than square-root in the contamination fraction.