Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 205 / 6 / c / Solution

A sufficient set of assumptions is: the columns of the deterministic designs have Euclidean norm at most $\sqrt{n}$; the true support has size $s$; the compatibility constant on that support is bounded below uniformly; $\log p=o(n)$; and $s\log p/\sqrt{n}\to 0$. Choose $A$ large enough that the Gaussian score eventhas probability tending to one. The standard compatibility oracle inequality then givesPart b consequently yieldsEquivalently, for a sufficiently large constant $c$,