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

With the centred data, no intercept is needed. Use the Lasso normalizationWrite $r=Y-Xb$ and $c=X^{\mathsf{T}}r/n$. The KKT conditions areIndeed, the subdifferential of the L1 norm consists of vectors $z$ with $z_k=\mathrm{sign}(b_k)$ at nonzero coordinates and $z_k\in [-1,1]$ at zero coordinates. The subgradient optimality condition is $0=-X^{\mathsf{T}}(Y-Xb)/n+\lambda z$. convexity makes these conditions sufficient as well as necessary. These are the Karush-Kuhn-Tucker conditions for the Lasso.

Here is a correlation-parameter version of least angle regression. Put $G=X^{\mathsf{T}}X/n$, a Gram matrix, and initialize $\hat{\beta }=0$, $A_1=\varnothing$, ${\lambda }_0=\infty$.

The two hitting formulas come from $c_j(t)-h{a}_j=\pm (t-h)$. This is LAR hitting time. Active variables are not dropped if a coefficient crosses zero: that is the distinction between this algorithm and the modified Lasso path algorithm.

The active Gram matrix is an invertible matrix under the assumed unique positive hits. Inductively, a candidate column in the span of the current active columns would have $c_j(\lambda )$ equal to a fixed linear combination of their correlations, hence proportional to $\lambda$ on the whole segment. Its ratio $|c_j(\lambda )|/\lambda$ could not first reach one at a positive interior knot. Thus every uniquely entering column adds a new independent direction. This also allows more predictors than observations; the algorithm stops before a dependent direction needs to be added at zero correlation.

We now prove the requested invariant. At the first positive knot the newly active correlation has magnitude ${\lambda }_1$. At a later knot the old active correlations have that knot's magnitude by induction, and the entering correlation has the same magnitude by the hitting rule. Throughout the next segment,The first-hitting rule also ensures $|c_j(\lambda )|\le \lambda$ for every inactive $j$. If no positive hit remains, this inequality continues to zero, where all correlations vanish. Consequently, on every printed closed segment,This is the LAR active correlation invariant.

If active nonzero coefficients have the same signs as their residual correlations, the active equalities are precisely the nonzero-coordinate Lasso KKT conditions. An active coefficient which is zero also satisfies the zero-coordinate KKT conditions, because its correlation is within $[-\lambda ,\lambda ]$. Inactive coefficients are zero and satisfy those same inequalities by construction. Thus every point of the least angle regression path is a Lasso minimizer for $\lambda >0$. Under the stated uniqueness assumption,This proves the desired implication, in fact under the weaker sign compatibility of LAR and Lasso condition requiring agreement only at nonzero coefficients.

There is an endpoint convention in the printed sufficient condition. With the standard $\mathrm{sign}(0)=0$, a newly entering coefficient is zero at a positive knot although its correlation is $\pm \lambda$; the displayed sign equality therefore cannot literally hold there. At the final zero knot the correlation signs are zero as well. Interpret sign compatibility on positive open segments, or in the nonzero-coefficient/subgradient sense just proved. The KKT conditions already handle zero coefficients at knots, and no equality of solution paths at $\lambda =0$ is needed for the requested conclusion.

Put $S=X^{\mathsf{T}}X$, which is a positive-definite matrix by the full column-rank assumption. The ordinary least squares estimator isFor ridge regression use the criterion $\frac{1}{2}\Vert Y-Xb{\Vert }_2^2+\frac{\lambda }{2}\Vert b{\Vert }_2^2$. Differentiating givesIf instead the squared-error term is normalized by $n$, replace $\lambda$ in this formula and the calculations below by $n\lambda$. Only the scale of the tuning parameter changes.

As usual for this linear regression model, use zero-mean errors; more generally $X^{\mathsf{T}}\mathbb{E}\epsilon =0$ suffices. Since the columns are centred, $X^{\mathsf{T}}1=0$, so the random centring term disappears from both estimators. ThusLet $A=(S+\lambda I{)}^{-1}$. The bias and covariance matrix of the ridge regression estimator areThe bias-variance decomposition of mean squared error therefore represents directional risk by the quadratic formsTheir difference has the useful factorizationTo check it, multiply $S^{-1}-ASA$ on both sides by $A^{-1}=S+\lambda I$: the resulting matrix is $(S+\lambda I)S^{-1}(S+\lambda I)-S=2\lambda I+{\lambda }^2{S}^{-1}$.

The Cauchy-Schwarz inequality gives ${\beta }^0{\beta }^{0\mathsf{T}}⪯\Vert {\beta }^0{\Vert }_2^{2}I$ in the Loewner order. Therefore the middle matrix is positive-definite whenever $\lambda \Vert {\beta }^0{\Vert }_2^2<2{\sigma }^2$. For example,works, independently of the eigenvalues of $S$. Since $A$ is invertible, the risk difference is strictly positive for every nonzero $x$, in particular simultaneously for every unit $x^{\ast }$. This proves uniform directional risk improvement by ridge regression. For the normalized-loss convention, take the displayed choice divided by $n$.

For the final assertion, fix any $\lambda >0$ and choose a unit eigenvector $v$ of $S$ with eigenvalue $d>0$. Put $x^{\ast }=v$ and ${\beta }^0=Bv$. Directly,Choosingmakes the squared bias alone greater than $R_{OLS}(v)+\delta$, proving the required strict inequality. Thus unbounded directional risk of fixed ridge shrinkage is compatible with the existence of a beneficial signal-dependent small penalty: no fixed positive penalty uniformly improves risk over all possible signals.

The mean assumption matters if the printed covariance condition is read in isolation. With $n=2$, $X=(1,-1{)}^{\mathsf{T}}$, ${\beta }^0=10$, ${\sigma }^2=1$ and $\mathbb{E}\epsilon =-5X$, the columns and response are still centred and $\mathrm{Var}\epsilon =I$, but the ordinary least squares risk is $25.5$. Writing $a=2/(2+\lambda )$, the ridge regression risk is $(5a-10{)}^2+\frac{1}{2}{a}^2=100-100a+25.5a^2>25.5$ for every $0<a<1$. Hence the standard zero-mean regression-error convention, or its stated orthogonality version, is necessary for the first risk comparison; covariance alone is insufficient.

The familywise error rate is the probability of rejecting at least one true null:A valid p-value is super-uniform under its null: $\mathbb{P}(p_i\le t)\le t$ for $0\le t\le 1$. The Bonferroni correction rejects $H_i$ if $p_i\le \alpha /m$. The union bound givesThis controls the familywise error rate for every configuration of true and false nulls, without any independence assumption on the p-values.

For a nonempty index set $I\subseteq \{1,\dots ,m\}$, the intersection hypothesis $H_I={\bigcap }_{i\in I}{H}_i$ asserts that every null indexed by $I$ holds. The closure of a family of statistical hypotheses consists of all these nonempty intersections, including the original hypotheses. For each intersection choose a local test ${\varphi }_I$ of size at most $\alpha$ under $H_I$. Such tests always exist: for example, within $I$ use the Bonferroni correction, rejecting $H_I$ if ${\min }_{i\in I}{p}_i\le \alpha /|I|$. More powerful local intersection tests can be substituted whenever valid.

The closed testing procedure rejects an elementary hypothesis $H_i$ only when every local test ${\varphi }_I$ with $i\in I$ rejects its intersection hypothesis. If $I_0\ne \varnothing$, the intersection $H_{I_0}$ is true. Rejecting any true $H_i$ requires rejection by its local test ${\varphi }_{I_0}$, soIf $I_0=\varnothing$, there is no possible false rejection. This proves closed-testing control of the familywise error rate. The same argument applies if intersection hypotheses themselves are reported as rejected: requiring all their supersets to reject includes $I_0$ whenever the reported intersection is true.

Finally, consider the given hierarchical family as a laminar family of sets. Call a set $I\in \mathcal{I}$ true when $I\subseteq I_0$, so its entire intersection hypothesis is true. Let $\mathcal{M}$ be the inclusion-maximal true sets in $\mathcal{I}$. Distinct members of $\mathcal{M}$ are disjoint: if they met, laminarity would make one contain the other, contradicting maximality. Consequently,Every true set $I$ lies in a maximal true $J$. If $H_I$ is rejected by the prescribed adjusted p-value rule, the maximum over its ancestors includes $J$, henceThus the event of any false rejection is contained in the union of these events over the disjoint maximal true sets. Using validity of each $p_J$ under its true intersection and the union bound,Equivalently, with probability at least $1-\alpha$ every rejection is correct. This proves familywise error control for a laminar hypothesis family. It requires neither independence nor the presence of all possible intersections or singletons in $\mathcal{I}$. Empty index sets are excluded, as required by the denominator $|J|$; if there are no true sets the result is immediate. Adjusted values exceeding one can be truncated at one without changing decisions for $\alpha <1$.

Put $\Omega ={\Sigma }^{-1}$, the precision matrix. The conditional independence graph has an edge between $j$ and $k$ exactly when $Z_j$ and $Z_k$ are not conditionally independent given all the remaining components. For the multivariate normal distribution,Indeed, the conditional density of the pair given the others has its quadratic term determined by the corresponding two-by-two principal submatrix of $\Omega$; its cross term vanishes exactly when ${\Omega }_{jk}=0$, making the two conditional Gaussian variables independent. This is a Gaussian graphical model.

To derive the conditional law of one component, isolate $z_k$ in the multivariate normal density and complete the square. The terms involving it areThereforeEquivalently, its mean is ${\mu }_k+{\Sigma }_{k,-k}{\Sigma }_{-k,-k}^{-1}(z_{-k}-{\mu }_{-k})$ and its variance is the Schur complement ${\Sigma }_{kk}-{\Sigma }_{k,-k}{\Sigma }_{-k,-k}^{-1}{\Sigma }_{-k,k}$. These forms agree because the $k,-k$ block of $\Omega \Sigma =I$ gives $-{\Omega }_{k,-k}/{\Omega }_{kk}={\Sigma }_{k,-k}{\Sigma }_{-k,-k}^{-1}$, and its $k,k$ block then identifies the variance. This proves the relevant conditional multivariate normal distribution formula.

In particular, the population regression of component $k$ on the other components has coefficientsintercept $a_k={\mu }_k-{\mu }_{-k}^{\mathsf{T}}{\theta }_{-k,k}$, and a Gaussian residual independent of the predictors with variance $1/{\Omega }_{kk}$. These are the conditional regression coefficients from a Gaussian precision matrix. The coefficient is zero exactly when the corresponding edge is absent. Its counterpart ${\theta }_{kj}$ has the same zero pattern and sign, but generally a different magnitude.

This motivates nodewise regression: for each $k$, regress $X_k$ on $X_{-k}$, estimating an intercept as well. For sparse graph estimation, use the Nodewise Lasso criterionThe Lasso penalty encourages many fitted coefficients to be zero and remains usable when the number of predictors exceeds the sample size. Ordinary unpenalized sample regressions would usually give a dense estimated graph. Separate regressions can disagree about a pair, so an undirected graph can use the OR rule for nodewise graph selection, retaining an edge if either fitted direction is nonzero, or the more conservative AND rule for nodewise graph selection, retaining it only if both are nonzero. These are choices for combining estimated neighbourhoods, rather than identities forced by finite-sample fits.

The printed joint objective uses a Group Lasso penalty on the unordered pairsThis is paired group Lasso for Gaussian graph estimation. Each group represents a single undirected edge, coupling its two directional regressions. A sum of group norms encourages entire pairs to be zero; a squared group norm would give smooth ridge-type shrinkage instead of edge deletion. The constraint ${\Theta }_{kk}=0$ removes self-prediction, and the intercepts are not penalized.

The free symbols called ${\mu }_k$ in the objective are regression intercepts, not generally the marginal means of the original Gaussian vector. Profiling them out givesand replaces all columns by their centred versions in the squared-error terms. This is profiling intercepts in nodewise regression. Scaling predictors to comparable units can also help interpret a common penalty, although the displayed objective itself is well defined on the given data.

The grouped KKT conditions make the sparsity mechanism precise. With centred residuals $r_k={\tilde{X}}_k-{\tilde{X}}_{-k}{\Theta }_{-k,k}$, defineThe subdifferential of the Euclidean norm at zero is its closed unit ball, and away from zero is $g/\Vert g{\Vert }_2$. Hence a minimizer satisfiesThese are the paired group Lasso optimality conditions. They jointly threshold the two directional scores, matching the population fact that both directions represent the same edge.

Estimate the graph by including $\{j,k\}$ exactly when $\Vert {\hat{g}}_{jk}{\Vert }_2>0$. This graph is undirected by construction. The penalty does not impose ${\Theta }_{jk}={\Theta }_{kj}$, nor does it mathematically require both coordinates of every selected pair to be nonzero. That distinction is appropriate because the population regression coefficients themselves need not have equal magnitudes. The fitted coefficient matrix is not automatically a symmetric positive definite precision matrix; its pair supports, rather than its entries as a precision estimate, supply the requested conditional independence graph.