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

A positive-semidefinite kernel on a nonempty set $\mathcal{X}$ is a symmetric function $k:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ such that, for every $n\ge 1$, every $x_1,\dots ,x_n\in \mathcal{X}$, and every $c_1,\dots ,c_n\in \mathbb{R}$,Equivalently, every finite kernel matrix $(k(x_r,x_s){)}_{r,s}$ is a positive semidefinite matrix.

The Gaussian kernel with bandwidth ${\sigma }^2>0$ is

Every $2\times 2$ principal submatrix of a kernel matrix is positive semidefinite, soThe Cauchy-Schwarz inequality for integrals therefore givesThus every entry of $k(x,y)=\int k_{\tau }(x,y)d\tau$ is well defined. For any finite coefficients $c_r$ and points $x_r$, linearity of the integral givesbecause the integrand is nonnegative. Hence $k$ is a positive-semidefinite kernel. This proves the integral closure of positive-semidefinite kernels.

The Gamma integral $u^{-1/2}={\pi }^{-1/2}{\int }_0^{\infty }{t}^{-1/2}{e}^{-ut}dt$ givesFor each $t>0$, the last factor is a Gaussian kernel, and the remaining weight is nonnegative. The diagonal integral equals ${\alpha }^{-1/2}<\infty$, so part ii shows that the displayed function is a positive-semidefinite kernel.

For points $x_1,\dots ,x_n$ and coefficients $c_1,\dots ,c_n$,The bound $|\hat{\varphi }|\le M$ ensures that this expected value is finite. Symmetry is immediate, so an expected outer product of a random feature map always defines a positive-semidefinite kernel.

Let $V_1,\dots ,V_d$ be independent standard Cauchy random variables. Their characteristic functions and independence giveTaking real parts yieldsFor each realization of $V$, both products are rank-one positive-semidefinite kernels. Their sum and then their expectation remain positive semidefinite by the closure property of positive-semidefinite kernels. This is a Random Fourier feature representation of the Laplace kernel.

The familywise error rate isThe Bonferroni correction rejects $H_i$ when $p_i\le \alpha /m$. Since a valid p-value is super-uniform under its null, the union bound givesNo independence assumption is needed.

For the closed testing procedure, form the intersection hypothesis $H_I={\bigcap }_{i\in I}{H}_i$ for every nonempty $I\subseteq \{1,\dots ,m\}$ and choose a level-$\alpha$ local test for each $H_I$. Reject $H_i$ exactly when every $H_I$ with $i\in I$ is rejected by its local test. If any true $H_i$ is rejected, then the intersection $H_{I_0}$ of all true nulls is rejected. Since its local test has significance level $\alpha$,This is the closed-testing control of the familywise error rate.

Write $W={\sum }_{j=1}^m{w}_j$. Procedure (A) is the Weighted Bonferroni correction: it rejects $H_i$ when $p_i\le \alpha w_i/W$. Therefore

Procedure (B) is the Weighted Holm step-down procedure. Let $k$ be the first rank in the ordering $q_{(1)}<\cdots <q_{(m)}$ whose hypothesis is a true null, and put $W_0={\sum }_{i\in I_0}{w}_i$. If any true null is rejected, the procedure reaches step $k$ andbecause every true null remains among ranks $k,\dots ,m$. Henceand another union bound gives FWER at most $\alpha$.

At step $k$, procedure (B) divides by the total weight still under consideration, which is no larger than $W$. Its critical values therefore increase as hypotheses are rejected. Moreover, if procedure (A) would reject a hypothesis, every earlier ordered $q$ also passes the initial threshold, so procedure (B) reaches and rejects it. Thus (B) contains every rejection of (A) and can make strictly more rejections while retaining the same strong FWER control.

Under the null, ${\epsilon }_1$ and ${\xi }_1$ have conditional independence given $z_1$. The law of total expectation gives

Conditional on the covariates and all responses used to construct $\hat{g}$, the residual ${\epsilon }_i$ has conditional second moment at most $C$; conditional independence under the null is what permits this conditioning. ConsequentlyThe Markov inequality proves

Next, the Cauchy-Schwarz inequality givesThe first factor converges to zero in probability. The weak law of large numbers and part a make the second $O_p(1)$, so the product converges to zero in probability.

Two applications of the Cauchy-Schwarz inequality giveandHere the empirical residual second moment is again $O_p(1)$ by the weak law of large numbers, while the assumed product error and the conclusion of part b are $o_p(1)$.

WriteExpanding $R_i^2$ gives the leading term ${\epsilon }_i^2{\xi }_i^2$ and terms of the forms treated in parts b and c, together with their versions obtained by interchanging $(\epsilon ,F)$ and $(\xi ,G)$. For example, the pure error terms are ${\epsilon }_i^2{G}_i^2$, ${\xi }_i^2{F}_i^2$, and $F_i^2{G}_i^2$, and each cross term is controlled by Cauchy-Schwarz from these. HenceAssuming this limit is positive, the continuous mapping theorem yields ${\tau }_D\stackrel{p}{\to }\{\mathbb{E}({\epsilon }_1^2{\xi }_1^2){\}}^{1/2}$. Combining this with the assumed convergence in distribution of $\sqrt{n}{\tau }_N$ and applying the Slutsky theorem givesThis is the studentization of the generalized covariance measure statistic.

A centered random variable $X$ is sub-Gaussian with parameter $a>0$ whenfor every $t\in \mathbb{R}$.

The Bernstein concentration inequality for products of sub-Gaussian variables quoted in the course says that if each coordinate of the identically distributed pairs $(U_i,V_i)$ is sub-Gaussian with parameter $\sigma /4$, thenSince $U^{T}V={\sum }_i{U}_i{V}_i$, this is the required bound. It follows by observing that a product of sub-Gaussian variables is sub-exponential and applying Bernstein's inequality to the independent centered products.

For any vector $\delta$ admissible in the definition of ${\varphi }_{\Sigma }^2$, one has $\Vert \delta {\Vert }_1\le 4$. The entrywise maximum norm bound therefore impliesBy the definition of the compatibility constant, ${\delta }^T\Sigma \delta \ge {\varphi }_{\Sigma }^2/s$, and henceTaking the infimum proves ${\varphi }_{\Theta }^2\ge {\varphi }_{\Sigma }^2/2$. This is the stability of a compatibility constant under entrywise perturbation.

Put $C=X^{T}X/n$. Applying the product concentration bound with the stated $t$ and using $t\le {\sigma }^2/3$ gives, for every $j,k$,There are $p(p+1)/2$ distinct entries in the symmetric matrix, so the union bound shows that the eventhas probability at least $1-p/(p+1{)}^2\ge p/(p+1)$.

On $\mathcal{E}$, $|C_{jj}-1|\le t$. Since $|{\Sigma }_{jk}|\le 1$ by Cauchy-Schwarz, normalization of the sample columns givesChoosing one coordinate of $S$ in the infimum shows ${\varphi }_{\Sigma }^2\le s$, so the assumed bound on $t$ is below one and, more precisely,The perturbation result now gives ${\varphi }_{\hat{\Sigma }}^2\ge {\varphi }_{\Sigma }^2/2$ throughout $\mathcal{E}$, and therefore

With the normalization used in the question, ridge regression solvesDifferentiating with respect to $\mu$ and using the centered columns $X^{T}1=0$ gives $\hat{\mu }=\overline{Y}$. The normal equation for $\beta$ issoThe push-through identity then gives the equivalent dual form

Fix $j\in A$ and writeThe matrix $R$ is positive definite. Applying the Sherman–Morrison formula to $R+X_j{X}_j^T$ yields

For the active set $A_k$, maintainThe initial $n\times n$ matrix inverse costs $O(n^3)$. At step $k$, compute $v_k=M_k^{-1}Y$ in $O(n^2)$ operations and all active ridge coefficients $X_{A_k}^T{v}_k$ in $O(|A_k|n)$ operations; their smallest absolute value determines $j_k$.

After deleting $j_k$,Part b ensures that the denominator in the Sherman–Morrison formula is positive, and the rank-one downdatecosts $O(n^2)$. Summing over the $p$ steps givesSince $p\ge n$, both earlier terms are bounded by $O(p^{2}n)$, proving the claimed computational complexity within computational complexity theory.

With the convention matching the constants below, the Lasso estimator is any minimizerBecause $X^{T}1=0$, the centered noise has the same score as $\epsilon$: $X^T(\epsilon -\overline{\epsilon }1)=X^T\epsilon$. Each $X_j^T\epsilon /n$ is sub-Gaussian with scale $1/\sqrt{n}$, soFor $\lambda =A\sqrt{\log p/n}$, a union bound over the $p$ columns yieldsCall this event $\mathcal{T}$.

The Karush-Kuhn-Tucker conditions for the Lasso say that there is $\hat{z}\in {\mathbb{R}}^p$ such thatEquivalently, $\hat{z}$ belongs to the subdifferential of the ${\ell }^1$ norm at $\hat{\beta }$.

Let $\delta =\hat{\beta }-{\beta }^0$. Comparing the Lasso objective at $\hat{\beta }$ and ${\beta }^0$ gives the Basic inequality for the Lasso. On $\mathcal{T}$ it impliesSincewe obtain the Lasso cone condition

The Karush-Kuhn-Tucker conditions also giveso on $\mathcal{T}$,The assumed cone invertibility condition therefore yieldsIf ${\min }_{j\in S}|{\beta }_j^0|>3\lambda /(2\psi )$, then every active coefficient remains nonzero and retains its sign. Substituting $\lambda =A\sqrt{\log p/n}$ proveson an event of the required probability. This is Lasso sign recovery from cone invertibility.

On the same event, the Lasso cone condition and the coordinatewise bound from part a giveWith $\lambda =A\sqrt{\log p/n}$ this is exactly