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

A procedure controls the familywise error rate at level $\alpha$ when, for every configuration of true nulls $I$,Let $i_{\ast }=\min I$. The step-down procedure can reject any true null only if it reaches and rejects $H_{i_{\ast }}$, which requires $p_{i_{\ast }}\le \alpha$. Since a valid p-value under its null satisfies $\mathbb{P}(p_{i_{\ast }}\le \alpha )\le \alpha$, the procedure controls FWER without any assumption on dependence among the p-values.

A distribution $P$ has the global Markov property for a directed acyclic graph $G$ when every D-separation statement $A{\perp }_{G}B\mid C$ implies the corresponding conditional independence $Z_A\perp \perp Z_B\mid Z_C$ under $P$.

If $G\in \mathcal{S}$ has nonadjacent vertices $j,k$, choose a topological ordering. Suppose $j$ precedes $k$. Then $j$ is a non-descendant and non-parent of $k$, so the directed local Markov property givesThe reversed ordering case is analogous. HenceUse the intersection-union test: reject $H_0$ exactly when $p_S\le \alpha$ for every $S$. Under $H_0$, at least one $H_{S_{\ast }}$ is true, soThis is nontrivial because it rejects whenever every tested conditional independence is rejected.

The Gaussian maximum-likelihood covariance estimate isFor each $i,k$,so $\Vert AB{\Vert }_{\infty }\le \Vert A{\Vert }_{\infty }\Vert B{\Vert }_{L^1}$. If $A$ is square and symmetric, its maximum row sum equals its maximum column sum, and the same calculation gives

Both the objective $\Vert \Omega {\Vert }_1={\sum }_j\Vert {\Omega }_j{\Vert }_1$ and the constraints separate by columns. Replacing one column of a global minimizer by a better feasible column would improve the global objective. Therefore each ${\hat{\Omega }}_j$ minimizesMoreover,Thus ${\Omega }_j^0$ is feasible andFor every column,Finally $\hat{\Omega }-{\Omega }^0={\Omega }^0{\Sigma }^0(\hat{\Omega }-{\Omega }^0)$, and symmetry of ${\Omega }^0$ givesThis is the basic error bound for the CLIME precision-matrix estimator.

A positive-semidefinite kernel on $\mathcal{X}$ is a symmetric function $k:{\mathcal{X}}^2\to \mathbb{R}$ such that, for every $x_1,\dots ,x_n$ and $c_1,\dots ,c_n$,If $k(x,x^{\prime })=⟨\varphi (x),\varphi (x^{\prime })⟩$ for a feature map into an inner-product space, thenThus every feature-map inner product is a kernel. If ${\alpha }_1,{\alpha }_2\ge 0$, then each finite quadratic form for ${\alpha }_1{k}_1+{\alpha }_2{k}_2$ is the corresponding nonnegative linear combination, so nonnegative linear combinations of kernels are kernels.

For fixed $x_1,\dots ,x_n$ and coefficients $c_i$, every $k_m$ satisfiesThe sum is finite, so pointwise convergence permits passage to the limit:Symmetry also passes to the limit. Hence a pointwise limit of kernels is a kernel.

For a finite sample, the Gram matrix of $k_1{k}_2$ is the entrywise product of the two positive-semidefinite Gram matrices. The Schur product theorem makes it positive semidefinite, proving the product closure.

The Gaussian kernel with bandwidth ${\sigma }^2$ isFactor it asThe linear kernel $x^T{x}^{\prime }$ is positive semidefinite; products and nonnegative scalar multiples preserve positivity, as does multiplication by $a(x)a(x^{\prime })$. The partial sums are therefore kernels, and pointwise-limit closure proves that the Gaussian kernel is positive semidefinite.

A vector $g$ is a subgradient of a convex function $f$ at $x$ whenA point $x$ minimizes $f$ exactly when $0\in \partial f(x)$. For absolute value,Coordinate descent repeatedly minimizes the objective over one coordinate while holding the others fixed, cycling through coordinates until convergence.

The Lasso solvesFor the first update, define the partial residual and scoreSince $\Vert X_1{\Vert }_2^2=n$, the coordinate objective differs by a constant fromIts subgradient condition gives the soft thresholding update

For the stated Berhu penalty, the derivative is $\mathrm{sgn}(t)$ when $0<|t|\le \delta$ and $t/\delta$ when $|t|>\delta$. The coordinatewise Karush-Kuhn-Tucker conditions therefore give

Put $\Delta =\Theta -\Sigma$ and let $\beta$ lie in the compatibility cone. ThenSubtracting this from the defining lower bound for ${\beta }^T\Sigma \beta$ and taking the infimum gives the stability of a compatibility constant under entrywise perturbation:

A centered random variable $W$ is a sub-Gaussian random variable with parameter $\sigma$ whenThe Chernoff bound gives $\mathbb{P}(W>t)\le e^{-t^2/(2{\sigma }^2)}$.

For fixed $j,k$, the variablesare independent, centered, and lie in $[-2,2]$, hence are sub-Gaussian with parameter $2$. Their mean is sub-Gaussian with parameter $2/\sqrt{n}$, soA union bound over at most $p^2$ pairs with $t=4\sqrt{2\log (p)/n}$ yields

The minimum-eigenvalue bound and Cauchy-Schwarz inequality implyso ${\varphi }_{\Sigma }^2(S)\ge c_{\min }$. A sufficient uniform condition isIndeed, on the concentration event the entrywise error is at most $c_{\min }/(32s)\le {\varphi }_{\Sigma }^2(S)/(32|S|)$ for every $0<|S|\le s$. The perturbation result then gives ${\varphi }_{\hat{\Sigma }}^2(S)\ge c_{\min }/2$ simultaneously, with probability at least $1-2p^{-2}$.

The term $\gamma \Vert \beta {\Vert }_2^2/2$ is strictly convex, while the remaining terms are convex, so the elastic net objective is strictly convex and its minimizer is unique. If two columns of $X$ are identical, swapping their coefficients leaves the objective unchanged. Uniqueness then forces those coefficients to be equal.

The Karush-Kuhn-Tucker conditions arewhereAssume $Y=X{\beta }^0$ and $\mathrm{sgn}(\hat{\beta })=\mathrm{sgn}({\beta }^0)=s$. The active equations giveThe inactive KKT inequalities becomeConversely, define ${\tilde{\beta }}_N=0$ andIf the displayed inequality holds and $\mathrm{sgn}({\tilde{\beta }}_S)=s_S$, the active equations and inactive inequalities together satisfy every KKT condition. Convexity and uniqueness imply $\tilde{\beta }=\hat{\beta }$, proving sign recovery.

The final sign condition printed in the question omits the factor $n$ before $\lambda$. For the objective as stated, the corrected expression above is required; without that correction, the claimed converse does not follow from the KKT equations.