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

Taking $\Theta =0$ gives $\Vert \Sigma \Theta -I{\Vert }_{\max }=1$, so every matrix is $1$-invertible. The smallest admissible value isThe map inside the norm is affine in $\Theta$, and a norm composed with an affine map is a convex function. The space of matrices is a convex feasible set, so this is a convex optimization problem.

Put $\hat{\Sigma }=X^{T}X/n$. Direct substitution of $Y=X{\beta }^0+\epsilon$ into the Debiased Lasso givesConditionally on the deterministic design,The assumed approximate inverse of a Gram matrix property and Holder inequality implyThus $\rho (n,p)=\sqrt{\log p}$.

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$,