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

Estimate the signal by one-dimensional total variation denoising, which penalizes adjacent differences rather than the constant level:This is a fused Lasso objective. Its L1 norm penalty makes many adjacent differences exactly zero, producing a piecewise-constant fit. For change-point detection, estimate the locations by $\hat{S}=\{i:{\hat{\mu }}_i\ne {\hat{\mu }}_{i+1}\}$. The tuning parameter controls the strength of the penalty; it can be chosen, for example, using a validation criterion appropriate to the noise model.

For a general family of elementary nulls $H_1,\dots ,H_m$, the closed testing procedure forms every nonempty intersection $H_B={\bigcap }_{j\in B}{H}_j$ and gives it a local test of level $\alpha$. Reject $H_j$ precisely when all intersections with $j\in B$ are locally rejected. This gives strong control of the familywise error rate: let $T_0$ be the indices of the true elementary nulls. If $T_0$ is empty there is no false rejection. Otherwise, rejecting any $H_j$ with $j\in T_0$ requires rejection of the true intersection $H_{T_0}$. Its local test has rejection probability at most $\alpha$, henceThis proof of closed-testing control of the familywise error rate needs no independence of the tests.

For the interval procedure, a true tested interval is contained in one maximal constant block $B\in \mathcal{T}$. If $I\subseteq B$, the intervals over which $p_B$ takes its maximum are a subset of those used for $p_I$, so $p_I\ge p_B$. Therefore rejection of a true $I$ forces rejection of its containing block. Conversely, a rejected block is itself a rejected true null.

There is a small indexing issue in the PDF: its testing family excludes singleton intervals, while $\mathcal{T}$ may contain singleton blocks. Put ${\mathcal{T}}_{\ast }=\{B\in \mathcal{T}:|B|\ge 2\}$. Every true tested interval lies in one of these blocks, so the exact statement, using only hypotheses defined in the paper, isSingleton blocks contain no eligible tested interval and can be ignored. Equivalently, one may define their nulls as never rejected.

For each $B\in {\mathcal{T}}_{\ast }$, the term $J=B$ occurs in the maximum defining $p_B$, giving $p_B\ge n{q}_B/|B|$. A valid p-value is a super-uniform random variable under its null, so for $0\le \alpha \le 1$,The union bound and disjointness of the constant blocks now giveThis establishes weighted interval testing for a piecewise-constant mean even when the interval p-values are dependent. Values $p_I>1$ do not affect rejection at levels at most one.

Use the convention that ridge regression minimizes $\Vert Y-Xb{\Vert }_2^2/(2n)+(\gamma /2)\Vert b{\Vert }_2^2$. Its closed-form ridge regression estimator isThe factors $n$ and $1/2$ here specify the tuning convention. No intercept is needed for the centred responses and predictors.

For the two-component procedure, fix $\delta$ and put $\theta =Y-X\delta$. Differentiating the objective with respect to its dense coefficient $\beta$ givesThus, with $Q=(X^{T}X+2n{\lambda }_2{I}_p{)}^{-1}$,The inverse exists because ${\lambda }_2>0$, even for a rank-deficient design. The sum of the fitted sparse and dense components is the Lava estimator.

Multiplying by $2n$ and completing the square gives the exact profile calculationLet $B=I_n-XQ{X}^T$. A singular value decomposition of $X$ shows that its eigenvalues are $2n{\lambda }_2/(r_i^2+2n{\lambda }_2)$ in nonzero singular directions and one in the orthogonal complement. Hence $B$ is a positive-definite matrix. Take its symmetric principal square root of a positive semidefinite matrix, $A=B^{1/2}$. Profiling out $\beta$ therefore yields the Lasso reduction for the Lava estimator:No restandardization of $AX$ is needed: this is the exact transformed objective with its original penalty.

Write $\tilde{X}=AX$, $h={\hat{\delta }}_{\lambda }-{\delta }^0$, and $\eta =\tilde{X}{\beta }^0+A\epsilon$. Then $AY=\tilde{X}{\delta }^0+\eta$. Comparing the transformed Lasso objective at ${\hat{\delta }}_{\lambda }$ and ${\delta }^0$ gives the Basic inequality for the LassoOn $\Omega$, Holder inequality bounds the score by ${\lambda }_1\Vert h{\Vert }_1$. Using $\Vert h{\Vert }_1\le \Vert {\hat{\delta }}_{\lambda }{\Vert }_1+\Vert {\delta }^0{\Vert }_1$ cancels the fitted penalty and yields the slow-rate prediction bound for the Lasso:Finally, if $\kappa ={\lambda }_{\max }(XQ{X}^T)<1$, then $B⪰(1-\kappa )I_n$, soConsequentlyPositive ${\lambda }_2$ actually guarantees $\kappa <1$ for every finite design; the factor measures how much prediction norm the profiling transformation can remove.

For a diagonal entry, put $Z_j={\sum }_{i=1}^d(A_{ij}^2-1)$. Independence and the given moment-generating function inequality for the chi-squared distribution giveThe Chernoff bound with $a=t/4$ yieldsApply the same argument to $-Z_j$ and sum the two tails:

To obtain the off-diagonal bound, set $U=(V+W)/\sqrt{2}$ and $D=(V-W)/\sqrt{2}$. They are jointly normal with unit variances and covariance zero, so independence of uncorrelated jointly normal variables makes them independent standard normals. Since $VW=(U^2-D^2)/2$, the moment-generating function of the product of two independent standard normal random variables isFor $j\ne k$, $(A^{T}A{)}_{jk}$ is a sum of $d$ independent such products. The given inequality implies $\mathbb{E}{e}^{a(A^{T}A{)}_{jk}}\le e^{d{a}^2}$ for $|a|\le 1/2$. Taking $a=t/2$, and repeating for the negative tail, gives

Now take $t=c\sqrt{\log p/d}\in (0,1)$ and $E=A^{T}A/d-I_p$. There are $p$ diagonal entries but only $p(p-1)/2$ distinct off-diagonal entries, since $E$ is symmetric. By the union bound, the event $\Vert E{\Vert }_{\max }\le t$ has probability at leastThis is the required entrywise concentration of a Gaussian Gram matrix.

On that single event, any vector $z$ supported on at most $s$ coordinates satisfieswhere the last step is the Cauchy-Schwarz inequality on the support. If $u,v$ each have at most $s/2$ nonzero coordinates, $z=u-v$ has at most $s$. The same entrywise event applies simultaneously to all of them, so no union over vectors is needed. The sparse norm preservation from entrywise Gram control givesThe printed ratio is undefined at $u=v$. Its equivalent quadratic statement, $|\Vert A(u-v){\Vert }_2^2/d-\Vert u-v{\Vert }_2^2|\le st\Vert u-v{\Vert }_2^2$, includes that case trivially. The nontrivial concentration argument assumes $p\ge 2,c>0$; at $p=1$ the stated probability lower bound is nonpositive and hence vacuous.

For a convex function $f$, its subdifferential at $x$ is the set of supporting slopesThe subgradient optimality condition isIndeed, the defining inequality with $g=0$ is exactly the global minimum inequality. For the subdifferential of the L1 norm, the coordinates vary independently:

Let $r=Y-X{\hat{\beta }}_{\lambda }$. The Karush-Kuhn-Tucker conditions for Lasso give a vector $z\in \partial \Vert {\hat{\beta }}_{\lambda }{\Vert }_1$ such that $X^{T}r/n=\lambda z$. If ${\hat{\sigma }}_{\lambda }=\Vert r{\Vert }_2/\sqrt{n}>0$, the unsquared residual norm is differentiable at this fit, with gradientUsing the subdifferential sum rule, choose $\gamma (\lambda )=\lambda /{\hat{\sigma }}_{\lambda }$ to obtainConvexity now proves the tuning relation between Lasso and square-root Lasso:The positive residual assumption is needed both for this gradient and for the quotient defining the tuning parameter.

For the final score calculation, use the usual fixed-design interpretation of the normal linear model: regard $X,Z$ and the tuning parameter $\gamma$ in the regression of $Z$ as fixed, and choose that regression's minimizer using only those inputs. Its nonzero residual $R=R_{\gamma }$ then has the Square-root Lasso optimality conditionExpanding the response residual givesSince $R/\Vert R{\Vert }_2$ is a fixed unit vector and $\epsilon \sim N_n(0,{\sigma }^2{I}_n)$, a linear image of a multivariate normal vector gives $W\sim N(0,{\sigma }^2)$. Finally, Holder inequality and the residual score bound yieldThis is the residual-score decomposition from square-root Lasso. The normality statement also holds conditionally on a design independent of the noise. If $\gamma$ were chosen from the response noise, for example through the preceding $\gamma (\lambda )$ formula, the direction $R$ would require a separate independence argument; the final calculation treats $\gamma$ as fixed.

The moral graph of a Directed acyclic graph is formed by joining any two parents of a common child and then removing the directions from all edges. For D-separation, a path in the underlying undirected graph is active given $S$ when every noncollider on it is outside $S$, and every collider has itself or a descendant in $S$. Disjoint vertex sets $A$ and $B$ are D-separated by $S$ if no such active path connects them.

The adjacency characterization isA one-edge path cannot be blocked by conditioning on other vertices. For a nonadjacent pair, choose the later vertex $v$ in a topological ordering. The earlier vertex $u$ is a nondescendant and is not a parent of $v$, so the parents of $v$ separate the pair by the local Markov property of a directed acyclic graph.

Use faithfulness of a directed acyclic graph to mean that graphical and probabilistic independences agree, for all disjoint sets:This includes the global Markov property of a directed acyclic graph as well as the absence of extra independences. The conditional independence graph of $P$ is the undirected graph in which $u-v$ is absent exactly when $Z_u\perp Z_v\mid Z_{V\setminus \{u,v\}}$.

To identify this graph, condition on every vertex other than $u,v$. Any noncollider in the interior of a path is then conditioned on, so an active path must have only colliders internally. Two adjacent interior vertices cannot both be colliders: the arrow joining them has an arrowhead at only one of its ends. Thus an active path can have no interior vertex, giving a direct edge, or just one, giving $u\to w\leftarrow v$. In the latter case the conditioned common child $w$ activates the path. These possibilities are exactly the edges added or retained by moralization. Faithfulness therefore provesThis is why the moral graph equals the conditional independence graph under faithfulness.

For Gaussian graph estimation, collect the data into an $n\times p$ matrix $D$ and let $S_n=n^{-1}{\sum }_i{x}_i{x}_i^T$. The precision matrix $\Theta ={\Sigma }^{-1}$ has ${\Theta }_{jk}=0$ precisely for absent graph edges, by Gaussian conditional independence. In neighbourhood selection, fit a Lasso regression of each column on the others:Select the nonzero coefficients as neighbours of $j$, then make the graph undirected using either the OR rule, retaining an edge selected in at least one regression, or the AND rule, requiring both. These are instances of Nodewise Lasso.

The Graphical Lasso estimates the whole precision matrix jointly, for example byRead off its nonzero off-diagonal entries as graph edges. This expression uses an off-diagonal penalty; an all-entry penalty is another convention.

To reduce computation in the PC algorithm, start its skeleton search from an estimate of the conditional independence graph rather than the complete graph. The exact graph contains the true DAG skeleton, so oracle tests can remove its extra edges while retaining the true adjacencies. Fewer initial edges and smaller neighbourhoods reduce both candidate pairs and candidate conditioning sets.

For correctness of the orientation stage, preserve valid separating-set records. With an exact conditional independence graph, an initially absent pair $u,v$ has the full complement $V\setminus \{u,v\}$ as a separating set. Record that set, and record the usual discovered sets for edges removed later. Leaving an initially absent pair with an empty default could falsely mark an unshielded noncollider as a collider. This describes PC initialization from a conditional independence graph; with an estimated initial graph, screening errors can propagate into the output.

Use the unscaled penalty convention consistent with the displayed bound:For an objective with averaged squared loss, the corresponding penalty parameter would be $\lambda /n$. We retain the unscaled $\lambda$ throughout.

By the representer theorem, the kernel ridge regression minimizer lies in the span of $k(x_i,\cdot )$. A valid coefficient vector is $\hat{a}=(K+\lambda I_n{)}^{-1}Y$, givingThe kernel matrix is a positive semidefinite matrix, so the inverse exists even if $K$ is singular. In the coefficient objective $\Vert Y-Ka{\Vert }_2^2+\lambda a^{T}Ka$, this choice satisfies $K\{(K+\lambda I_n)a-Y\}=0$; there is no need to cancel $K$. The function itself is unique because of the strictly convex squared Hilbert norm. The matrix $H$ is the kernel-ridge hat matrix in the present normalization.

Let $m^0=(f^0(x_i){)}_{i=1}^n$. Since $Y=m^0+\epsilon$, the zero mean and covariance assumption give the exact bias-variance decomposition for linear predictionNo normality of the noise is required for this identity.

Choose an orthonormal eigenbasis $v_i$ of $K$, with eigenvalues $d_i\ge 0$. Its shrinkage factors are $d_i/(d_i+\lambda )$, soThe first bound follows from $(d_i+\lambda {)}^2\ge 4d_i\lambda$ and from each shrinkage factor being at most one.

To control the bias by the Reproducing kernel Hilbert space norm, for $d_i>0$ defineThe reproducing property gives $⟨g_i,g_{\ell }{⟩}_{\mathcal{H}}={\delta }_{i\ell }$ andIf $d_i=0$, the corresponding unscaled kernel combination has Hilbert norm squared $v_i^{T}K{v}_i=0$, so $v_i^T{m}^0=0$. There is therefore no bias component in a zero-eigenvalue direction. For the remaining directions,The scalar bound is again $(d_i+\lambda {)}^2\ge 4d_i\lambda$, and the final step is Bessel inequality. Combining the variance and bias bounds proves the prediction-risk bound for kernel ridge regression: