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

A symmetric function $k:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ is a positive-semidefinite kernel when, for every $m$, every $x_1,\dots ,x_m\in \mathcal{X}$, and every $c\in {\mathbb{R}}^m$,Equivalently, every associated kernel matrix is a positive semidefinite matrix.

A Reproducing-kernel Hilbert space $\mathcal{H}$ on $\mathcal{X}$ is a Hilbert space of real-valued functions such that every point-evaluation map $f\mapsto f(x)$ is continuous. The Riesz representation theorem then gives a function $k(x,\cdot )\in \mathcal{H}$ satisfying the reproducing propertyIts reproducing kernel is $k(x,y)=⟨k(x,\cdot ),k(y,\cdot ){⟩}_{\mathcal{H}}$.

Suppose a feature map $\varphi :{\mathbb{R}}^d\to {\mathbb{R}}^p$ represented the Gaussian kernel. Choose $n>p$, a unit vector $e$, and points $x_i=iae$ for $i=0,\dots ,n-1$. Their kernel matrix isFor sufficiently large $a$, hence sufficiently small $r$, every row satisfiesThus $K$ is a symmetric strictly diagonally dominant matrix with positive diagonal and is therefore a positive-definite matrix, so $\mathrm{rank}K=n$.

On the other hand, if $\Phi$ is the $n\times p$ matrix whose $i$th row is $\varphi (x_i{)}^T$, then $K=\Phi {\Phi }^T$ and $\mathrm{rank}K\le p<n$, a contradiction. Hence every feature-space realization of the Gaussian kernel requires an infinite-dimensional vector space.

For $x,y>0$, the Laplace transform identityexhibits $k_1$ as an inner product of the feature functions $t\mapsto e^{-tx}$ in $L^2(0,\infty )$. More explicitly, for any real $c_i$ and positive $x_i$,Therefore $k_1$ is a positive-semidefinite kernel.

PutThe numerator is the linear kernel, while the reciprocal of the denominator is the kernel from part c applied to $\Vert x{\Vert }^2$ and $\Vert y{\Vert }^2$. The product of positive-semidefinite kernels therefore shows that $a$ is a positive-semidefinite kernel. The Cauchy-Schwarz inequality and the arithmetic-geometric mean inequality give $|a(x,y)|\le 1/2$, soEach power is positive semidefinite by the Schur product theorem, and the convergent sum is positive semidefinite.

Moreover $k_2(x,x)=1$. If $\Phi$ is its canonical feature map, thenThe feature-space norm gives symmetry and the triangle inequality. Finally, $d(x,y)=0$ implies $k_2(x,y)=1$, hence $a(x,y)=1/2$ andwhich is equivalent to $\Vert x-y{\Vert }^2=0$. Thus $d$ is a metric rather than merely a pseudometric.

The matrix $S$ is the sample covariance matrixChanging $n$ to $n-1$ is another convention, but the objective must use the same convention throughout.

The differential of the log-determinant is $d\log \det \Omega =\mathrm{Tr}({\Omega }^{-1}d\Omega )$. The subdifferential of the entrywise ${\ell }^1$ norm consists of symmetric matrices $Z$ withThe Karush-Kuhn-Tucker conditions for the Graphical Lasso are thereforeBecause $-\log \det \Omega$ is strictly convex on the positive-definite matrices, these conditions characterize the unique minimizer whenever it exists.

Multiply the Karush-Kuhn-Tucker conditions on the right by $\hat{\Omega }$ and take the matrix trace:Symmetry and the defining property of the subgradient of the absolute value giveConsequently the last two terms in the objective sum to $p$, and hence

Let ${\hat{\Omega }}^{(k)}$ solve the $k$th diagonal-block problem and setIts inverse is block diagonal. On each diagonal block, the Graphical-Lasso Karush-Kuhn-Tucker conditions hold by the definition of ${\hat{\Omega }}^{(k)}$. On the off-diagonal blocks chooseThe assumed inequalities $|S_{ij}|\le \lambda$ ensure that every entry lies in $[-1,1]$, exactly the allowed subgradient at a zero entry of $\tilde{\Omega }$.

Thus $-{\tilde{\Omega }}^{-1}+S+\lambda Z=0$ on every block. The KKT conditions and the fact that the objective is strictly convex prove that $\tilde{\Omega }=\hat{\Omega }$, giving the claimed block decomposition.

With the normalization used here, the Lasso estimator minimizesOptimality at $\hat{\beta }$ relative to the feasible point ${\beta }^0$ givesThe columns of $X$ are centered, so $X^{T}1=0$ and the centered noise produces the same score function as $\epsilon$. Expanding the two squared norms and cancelling the noise norm yields the standard Basic inequality for the LassoThus the displayed inequality in the question has a factor-of-two typo: its left side should be $\Vert X(\hat{\beta }-{\beta }^0){\Vert }_2^2/(2n)$, or both terms on its right should be doubled. No scaling of the usual squared-error Lasso objective produces the three displayed coefficients simultaneously. Parts b and d explicitly ask us to use the stated inequality, so their requested constants follow from that stated version.

Write $\delta =\hat{\beta }-{\beta }^0$. On $\Omega$, Hölder's inequality givesSince ${\beta }_N^0=0$, the triangle inequality givesSubstitution in the Basic inequality for the Lasso, followed by discarding the nonnegative prediction-error term, yieldsTherefore $\Vert {\hat{\beta }}_N-{\beta }_N^0{\Vert }_1\le 3\Vert {\hat{\beta }}_S-{\beta }_S^0{\Vert }_1$, the Lasso cone condition.

For each column $X_j$, the normalized score isThe errors are independent Rademacher random variables, and $\Vert X_j{\Vert }_2^2=n$. The Hoeffding lemma therefore makes $W_j$ a sub-Gaussian random variable with variance proxy $1/n$, soThe union bound with $t=\lambda /2$ givesFor $\lambda =A\sqrt{\log p/n}$ this becomesIn particular, if $A>\sqrt{8}$, the lower bound tends to one as $p\to \infty$.

Part b places $\delta =\hat{\beta }-{\beta }^0$ in the Lasso cone condition. Keeping the prediction-error term in the same argument giveswhere the second step is the Cauchy-Schwarz inequality. The restricted eigenvalue condition givesfor nonzero $\delta$ in this cone. Division by $\Vert \delta {\Vert }_2$ provesThe result is immediate when $\delta =0$.

The Square-root Lasso estimator with regularization parameter $\gamma >0$ isUnlike the ordinary Lasso, its tuning parameter does not require prior knowledge of the noise standard deviation $\sigma$.

One standard construction uses the Debiased Lasso. Starting from the Square-root Lasso estimate $\hat{\beta }$, estimate a vector ${\hat{\Theta }}_j$ that approximately inverts the $j$th column of the empirical Gram matrix $\hat{\Sigma }=X^{T}X/n$, for example by a Nodewise Lasso. Defineand estimate $\sigma$ by $\hat{\sigma }=\Vert Y-X\hat{\beta }{\Vert }_2/\sqrt{n}$. The approximate two-sided level-$\alpha$ test rejects $H_j^{\beta }$ whenwhere $z_{1-\alpha /2}$ is a standard normal quantile.

Sufficient high-dimensional conditions include a Compatibility condition for the Lasso bounded away from zero, $\gamma \asymp \sqrt{\log p/n}$, $\log p=o(n)$, andtogether with the corresponding sparsity and consistency conditions for the nodewise inverse-Gram estimate. Under these assumptions the Debiased-Lasso asymptotic normality makes the rejection probability under $H_j^{\beta }$ tend to $\alpha$.

If $B=\varnothing$, then for every $j$ at least one of $H_j^{\beta }$ and $H_j^{\eta }$ is true. Sincevalidity of the p-value for whichever component null is true implies $\mathbb{P}(q_j\le t)\le t$. Therefore the union bound givesThis is the Bonferroni correction for the composite intersection alternatives.

Let $I_0=B^c$ and $m_0=|I_0|$. Each $q_j$ with $j\in I_0$ is a valid p-value by the argument in part c. If the Holm step-down procedure selects any index from $I_0$, let $r$ be the rank of the first such index. All $r-1$ earlier selections belong to $B$, soSelection through rank $r$ impliesConsequentlyThus the procedure controls the familywise error rate without requiring independence among the p-values.

The kernel ridge regression estimator isBy the representer theorem, ${\hat{f}}_{\lambda }={\sum }_{j=1}^n{\alpha }_{j}k(x_j,\cdot )$. If $K_{ij}=k(x_i,x_j)$, substitution and differentiation giveThusThe matrix $H_{\lambda }$ is the kernel-ridge hat matrix.

The leave-one-out residual identity for a linear smoother, obtained from the block matrix inverse or the Sherman–Morrison formula, isHence

Compute once the spectral decomposition $K=U\mathrm{diag}(d_1,\dots ,d_n)U^T$ in $O(n^3)$ operations and the vector $U^{T}Y$ in $O(n^2)$. For each ${\lambda }_{\ell }$, setThen computeBoth calculations take $O(n^2)$ operations per tuning parameter, after which the displayed leave-one-out formula costs $O(n)$. All $L$ scores therefore require $O(n^3+L{n}^2)$ operations.