Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 205 (Modern Statistical Methods)

WriteIts score isThe Karush-Kuhn-Tucker conditions for L1-penalized logistic regression are therefore

The scalar logistic loss $u\mapsto -u+\log (1+e^u)$ is strictly convex because its second derivative is $e^u/(1+e^u{)}^2>0$. If $\hat{\beta }$ and $\tilde{\beta }$ are minimizers but $X\hat{\beta }\ne X\tilde{\beta }$, strict convexity of the loss as a function of the fitted vector and convexity of the L1 norm make the objective at their midpoint strictly smaller than the common minimum. This contradiction proves thatfor every pair of solutions.

Part b shows that all solutions have the same fitted vector, hence the same score and the same set $E$. The KKT conditions show that every nonzero coordinate of any solution belongs to $E$, since a nonzero coefficient forces the corresponding score to have absolute value $\lambda$. Thus every solution is supported on $E$ and satisfiesIf $\mathrm{rank}(X_E)=|E|$, the linear map $u\mapsto X_{E}u$ is injective. Consequently ${\beta }_E$ and hence $\beta$ are unique.

For $s=|S|>0$, the compatibility constant in the convention used here is

Let $D$ be the block-diagonal part of $\hat{\Sigma }=n^{-1}{X}^{T}X$. The within-block eigenvalue assumption gives ${\delta }^{T}D\delta \ge \eta \Vert \delta {\Vert }_2^2$. On the compatibility cone with $\Vert {\delta }_S{\Vert }_1=1$,The off-block assumption therefore givesIt follows that ${\delta }^T\hat{\Sigma }\delta \ge \eta /(2s)$, and hence

Because $\Vert X_j{\Vert }_2=\sqrt{n}$, each coordinate of $X^T\epsilon /n$ is $N(0,{\sigma }^2/n)$. The Gaussian tail bound and a union bound giveOn the complementary score event, the standard Basic inequality for the Lasso, cone argument, and compatibility oracle inequality give, for $S=\mathrm{supp}({\beta }^0)$,Using part b and ${\lambda }^2=A^2{\sigma }^2\log p/n$ proveswith the required probability.

For $u=0$ the assertion is immediate under the natural zero-vector convention. For $u\ne 0$, the rows $a_r$ of $A$ are independent and $a_r^{T}u/\Vert u{\Vert }_2$ is a centered unit-variance sub-Gaussian random variable. Its centered square is sub-exponential. The corresponding Bernstein estimate, in the explicit Rademacher Johnson–Lindenstrauss transform form, isSince the sum in the event is $\Vert Au{\Vert }_2^2/\Vert u{\Vert }_2^2$, this is the claimed inequality.

Apply part a to each of the at most $n(n-1)/2$ nonzero differences $u_i-u_j$. For $w_i=A{u}_i/\sqrt{d}$, the union bound makes the probability of any failure at mostThe assumed inequality $d>272\log (n/\sqrt{\epsilon })/t^2$ makes this smaller than $\epsilon$. Hence, simultaneously for every distinct pair,with probability at least $1-\epsilon$, which is the finite-set Johnson–Lindenstrauss lemma.

Regard each centered random variable $g(x)$ as a vector $h_x$ in the Hilbert space $L^2(\mathbb{P})$. Thenso $k$ is the Gaussian kernel on the finite subset $\{h_x:x\in \mathcal{X}\}$ of that Hilbert space. More explicitly,Every power of the inner-product kernel is positive semidefinite, and the closure property of positive-semidefinite kernels under nonnegative sums, pointwise limits, and multiplication by one-variable factors proves that $k$ is positive definite.

The kernel ridge regression estimator minimizesBy the representer theorem, its fitted-value vector isWriting $f$ for the true value vector, the variance contribution to $\mathbb{E}\Vert f-\hat{f}{\Vert }_2^2$ isThe squared bias is $\Vert \lambda (K+\lambda I{)}^{-1}f{\Vert }_2^2$. In an orthonormal eigenbasis of $K$, the scalar inequalitywhich is equivalent to $4d\lambda \le (d+\lambda {)}^2$, yieldsFor $\Vert f{\Vert }_2=1$, only the last term varies. The Rayleigh quotient of $K^{-1}$ is maximized by a unit eigenvector associated with its largest eigenvalue $1/d_n$, equivalently an eigenvector of $K$ associated with $d_n$.

Use the uncentered sample covariance matrixThen $v_{\ell }=a_{\ell }^T\Sigma a_{\ell }$ and, simultaneously for every unit vector $a_{\ell }$,Here $\Vert \Sigma {\Vert }_{\mathrm{op}}=1$ and the effective rank of a covariance matrix satisfiesThe Gaussian sample-covariance operator-norm bound therefore gives, with probability at least $1-e^{-\delta }$,Under the assumed upper bound on $\log d+1+\delta$, the second term is at most the first. Thus the stronger simultaneous estimateholds for every $\ell$. Squaring and using that the displayed ratio is at most one gives the inequality requested in the question after enlarging the universal constant $C$.

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