Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 31 (Statistical Theory)

The expected check loss is finite because ${\rho }_{\tau }(u)\le |u|$. It is also Lipschitz in its location argument, with constant at most one. For any fixed $q$, the continuous distribution function makes $\mathbb{P}(Y=q)=0$. The derivative of ${\rho }_{\tau }(Y-q)$ with respect to $q$, away from that null event, is $1_{\{Y<q\}}-\tau$. Difference quotients are bounded by one, so the dominated convergence theorem givesThe continuous, strictly increasing distribution function has limits zero and one. Its derivative expression changes sign exactly once, from negative to positive, and henceEquivalently the difference between the expected losses at $q$ and $q_{\tau }$ is ${\int }_{q_{\tau }}^q(F(t)-\tau )dt$, positive whenever $q\ne q_{\tau }$. This proves population quantiles minimize check loss directly.

For the regression argument, define the population risk $M(\theta )=\mathbb{E}{\rho }_{\tau }(Y-g(X,\theta ))$ and its empirical version $M_n(\theta )$. Boundedness of $g$ and integrability of the error give integrability of $Y$ and of all these losses. Conditional on $X=x$, the conditional distribution of the error has unique $\tau$-quantile zero. Applying the preceding calculation conditionally shows that its expected loss is uniquely minimized when the fitted displacement $g(x,\theta )-g(x,{\theta }_0)$ equals zero. Thuswith strict inequality whenever that displacement is nonzero on an event of positive probability. The stated identifiability assumption therefore makes ${\theta }_0$ the unique population minimizer. This is conditional quantile identification.

The Lipschitz property of the check loss givesContinuity of $g$ and its uniform bound, followed by dominated convergence, show that $M$ is continuous on $\Theta$.

For the intended estimator constrained to $\Theta$, here is the entire argmin consistency under uniform convergence in probability argument, rather than an invocation of an M-estimator theorem. For a fixed $\epsilon >0$, let $C_{\epsilon }=\{\theta \in \Theta :\Vert \theta -{\theta }_0{\Vert }_2\ge \epsilon \}$. If this set is empty, there is nothing to prove. Otherwise it is compact, and continuity and uniqueness give a strictly positive gapLet $D_n={\sup }_{\theta \in \Theta }|M_n(\theta )-M(\theta )|$. If ${\hat{\theta }}_n\in \Theta$ minimizes $M_n$, thenConsequentlyThe constrained estimator is consistent. Existence of a constrained minimum follows from continuity of the sample criterion and compactness. The argument applies to any measurable choice of minimizer.

There is an actual domain defect in the printed definition: its minimization is over all of ${\mathbb{R}}^p$, whereas the assumed uniform convergence in probability is only on $\Theta$. That literal unconstrained consistency claim is false. The preceding conclusion needs minimization over $\Theta$, or another assumption that confines the selected minimizers to a set where the convergence and separation arguments apply. No change of question heading is needed to make this qualification explicit.

Here is a counterexample satisfying even identifiability over the whole line. Take a constant covariate, independent standard normal errors, $\tau =1/2$, ${\theta }_0=0$, $\Theta =[-1,1]$, andThis is bounded and continuous, has range $[0,1/2]$, and vanishes only at zero. The conditional error distribution function is continuous and strictly increasing with median zero. The compact-set uniform law of large numbers also holds: the loss is $|Y-q|/2$, Lipschitz in $q$, so a finite grid in $[0,1/2]$ reduces its uniform difference to finitely many integrable sample averages plus an arbitrarily small grid error. The weak law of large numbers then gives the asserted convergence.

Let $m_n$ be a sample median, and put $c_n=\min (1/2,\max (0,m_n))$. Absolute loss over the range $[0,1/2]$ is minimized at $c_n$. Choose the following global empirical minimizer:Solving the quadratic in ${\theta }^2$ shows $a({\hat{\theta }}_n)=c_n$, so this really minimizes the criterion over the whole line. For odd $n$, symmetry and continuity give $\mathbb{P}(m_n>0)=1/2$. Moreover $m_n\to 0$ in probability: for each fixed positive $\delta$, the proportion of observations below $\delta$ converges to a number greater than one half, and the analogous proportion below $-\delta$ converges to a number less than one half. Thereforealong odd $n$. The selected unconstrained estimator is not consistent. This illustrates why a global argmin may escape a compact convergence set.

Use the following normalization for the Lasso estimator, leaving the intercept unpenalized:A different convention for the factor in front of squared error rescales the regularization parameter. With this convention, centering of the columns gives $\hat{a}=\overline{Y}$. Put $Y_c=Y-\overline{Y}{1}_n$ and ${ϵ}_c=ϵ-\overline{ϵ}{1}_n$. Then $Y_c=X\beta +{ϵ}_c$ and $X^T{ϵ}_c=X^Tϵ$. The Lasso minimizes $\Vert Y_c-Xb{\Vert }_2^2/(2n)+\lambda \Vert b{\Vert }_1$. A minimum exists since $\lambda >0$ makes this continuous objective coercive; the bound below holds for every minimizer.

We first prove the needed sharp two-sided Gaussian tail bound. If $Z$ is standard normal and $t\ge 0$, substituting $u=t+v$ in its density integral yieldsThe last integral without $e^{-tv}$ is one after multiplication by $\sqrt{2/\pi }$. In particular this proves the two-sided bound with no extra factor of two.

Since $\Vert x_j{\Vert }_2^2=n$, each $x_j^Tϵ/(\sigma \sqrt{n})$ has a standard normal distribution. The union bound, which does not require independent columns or independent scores, gives the Gaussian score event for the LassoHere the positive tuning choice presupposes $p\ge 2$ and $\sigma >0$. When the displayed lower bound is negative it is simply a valid, vacuous lower bound. For $p=1$ the prescribed parameter is zero and the probability lower bound is also zero, so no positive-parameter assertion is supplied by that prescription.

Let $\delta ={\hat{\beta }}_{\lambda }^L-\beta$ and $Q=\Vert X\delta {\Vert }_2^2/n$. Comparing the Lasso objective at its minimizer and at $\beta$ and expanding the squares gives the Basic inequality for the LassoOn $\mathcal{E}$, the stochastic term is at most $\lambda \Vert \delta {\Vert }_1$. Because ${\beta }_N=0$, the triangle inequality givesIt follows thatIn particular $\Vert {\delta }_N{\Vert }_1\le 3\Vert {\delta }_S{\Vert }_1$, which is the Lasso cone condition. The given Compatibility condition for the Lasso is therefore applicable and gives $\Vert {\delta }_S{\Vert }_1\le \sqrt{sQ}/{\varphi }_0$.

Adding $\lambda \Vert {\delta }_S{\Vert }_1$ to the preceding inequality and using compatibility now yieldsThe last inequality is just the nonnegativity of $(\sqrt{Q/2}-\sqrt{8}\lambda \sqrt{s}/{\varphi }_0{)}^2$. Thus $Q+2\lambda \Vert \delta {\Vert }_1\le 16{\lambda }^{2}s/{\varphi }_0^2$, and dropping one nonnegative coefficient-error term givesThis prediction and coefficient error bound for compatible Lasso holds on $\mathcal{E}$, and hence with the required probability. If $s=0$, the earlier basic inequality directly forces $\delta =0$ on $\mathcal{E}$, so the zero right side is also correct.

With the same squared-error normalization as in Question 2, the ridge estimator solvesThe unpenalized intercept in ridge regression is $\hat{a}=\overline{Y}$ because the columns of $X$ are centered. Differentiating the remaining quadratic objective gives $(X^{T}X+n\lambda I_p){\hat{\beta }}_{\lambda }^R=X^T{Y}_c$. Since $\lambda >0$, the left matrix is positive definite even when $X$ is rank-deficient. Thus the closed-form ridge regression estimator isThe second equality again uses centering. If the penalty convention is $\lambda \Vert b{\Vert }_2^2/2$ with an unnormalized squared-error term $\Vert Y_c-Xb{\Vert }_2^2/2$, replace $n\lambda$ by $\lambda$ throughout; the limiting assertion is unchanged.

For the full-column-rank case, take a singular value decomposition $X=UD{V}^T$ with positive singular values $d_1,\dots ,d_p$. The ordinary least squares estimator, which is the slope maximum-likelihood estimator in this normal linear model, and the ridge regression estimator are respectivelyConsequently principal-component shrinkage by ridge regression multiplies the least-squares coordinate in direction $v_j$ by $d_j^2/(d_j^2+n\lambda )$. Ridge shrinks most strongly in directions with the smallest singular values. These are combinations of predictors that the data distinguish least well.

Near multicollinearity creates small singular values, and the factor $1/d_j$ in ordinary least squares greatly amplifies noise in those directions. Its coefficient variance there is ${\sigma }^2/d_j^2$, while the ridge variance iswhich is smaller. The price is bias: the expectation of the ridge coordinate is $d_j^2/(d_j^2+n\lambda )$ times the corresponding true coefficient. This bias-variance tradeoff can substantially reduce estimation and prediction error when the poorly identified directions do not contain an excessively large signal. It is not a guarantee of improvement for every coefficient vector. Adding $n\lambda$ to every eigenvalue also improves the condition number of the normal matrix and makes numerical inversion more stable.

To handle every rank and every relation between $n$ and $p$, put $G=X^{T}X$ and use its spectral theorem for real symmetric matrices. Choose an orthonormal eigenbasis $v_1,\dots ,v_p$ with eigenvalues ${\gamma }_j\ge 0$, and put $z=X^{T}Y$. ThenIf ${\gamma }_j=0$, then $\Vert X{v}_j{\Vert }_2^2=v_j^{T}G{v}_j=0$, so $X{v}_j=0$ and $v_j^{T}z=(X{v}_j{)}^{T}Y=0$. Thus these terms are exactly zero for every positive $\lambda$; there is no divergent component in the null space. Each remaining term converges to $(v_j^{T}z/{\gamma }_j)v_j$. By the definition of the Moore-Penrose pseudoinverse,and thereforeThis proves the vanishing-penalty ridge limit without an invertibility assumption. The limit is the minimum-norm least-squares solution: every other least-squares solution differs by a vector in $\ker X$, orthogonal to the displayed solution, and therefore has at least as large a Euclidean norm.

Let $I_0$ be the indices of the true null hypotheses, let $m_0=|I_0|$, and let $V$ count false rejections. The familywise error rate isThe Bonferroni correction rejects a null exactly when its p-value is at most $\alpha /m$. The union bound givesThis controls the familywise error rate for every configuration of true and false nulls, with arbitrary dependence between their p-values. Marginal super-uniformity, $\mathbb{P}(P_i\le t)\le t$, would also suffice.

For the Holm step-down procedure, inspect the ordered p-values in ascending order and stop at the first failed comparison. If the first comparison fails, reject none; this is the convention $k=0$ when the defining set is empty. Ties can be ordered by any fixed rule.

If $m_0=0$ there can be no false rejection. Otherwise let $j$ be the rank of the first true null. Since at most $m-m_0$ false nulls precede it, $j\le m-m_0+1$ and thus $m-j+1\ge m_0$. If any true null is rejected, the step-down rule must have rejected this first true null, which requiresUsing the union bound on the true-null p-values provesThis first true null argument for Holm control also requires no independence. Holm controls the familywise error rate at level $\alpha$ under arbitrary dependence.

Now let $R$ count all rejections. The false discovery rate is the expected proportion of rejections that are false, with zero assigned when nothing is rejected:It differs from the familywise error rate: several false rejections can still represent a small proportion of a large collection of discoveries.

The BH procedure is a step-up rule. SetIf $K=0$, reject nothing; otherwise reject all hypotheses with $P_i\le \alpha K/m$. Exactly $K$ hypotheses are rejected: if more than $K$ p-values were below that threshold, the next ordered value would also satisfy its own larger threshold, contradicting maximality. Thus $R=K$. Unlike the step-down rule, a failed early comparison does not make this procedure stop.

For the proof, assume that each true-null p-value is uniform on $[0,1]$ and independent of the entire vector of the other p-values. Joint independence of all p-values is a sufficient condition; the false-null marginal distributions can be arbitrary. Mere uniformity of the true-null marginals without a dependence condition is insufficient for this argument or for general unmodified BH control.

Fix a true null $i$. Replace its p-value by zero and let $R^{(i)}$ be the number of rejections made by the Benjamini-Hochberg procedure on the modified vector. This variable depends only on the other p-values, and $R^{(i)}\ge 1$. The Benjamini-Hochberg leave-one-out identity isTo prove it, suppose $i$ is rejected with $R=r$. Decreasing its p-value to zero leaves every ordered value above rank $r$ unchanged, since it was already among the first $r$ values. Those higher ranks still fail their thresholds, while rank $r$ still succeeds; hence $R^{(i)}=r$. Conversely, suppose $R^{(i)}=r$ and $P_i\le \alpha r/m$. Restoring $P_i$ still leaves at least $r$ values at most $\alpha r/m$, so $R\ge r$. Increasing one p-value cannot increase the maximal successful rank, so $R\le R^{(i)}=r$. This gives equality and rejection of $i$.

Independence and uniformity now giveSumming over the $m_0$ true nulls proves the exact false discovery rate under independent null p-values:If the independent true-null p-values are only super-uniform, the same calculation gives the inequality instead of equality. The distinction between the two types of error control and the dependence conditions is essential: Bonferroni and Holm have the preceding guarantees without independence, while the BH proof here explicitly uses it.