Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 210 (Topics in Statistical Theory)

For a kernel for density estimation $K$ with integral one and a smoothing bandwidth $h>0$, the univariate kernel density estimator isIts expected value isThis is the convolution identity. It holds wherever the integral is defined, in particular everywhere for the bounded kernel used below. For a nonnegative kernel for density estimation, Tonelli theorem also gives the identity as an extended nonnegative integral. A signed kernel for density estimation instead requires absolute integrability for this interchange.

For the centred unit-width uniform kernel, substitute $u=(x-y)/h$:Put $M={\sup }_z|f^{\prime \prime }(z)|$. The Taylor theorem with Lagrange remainder givesThe odd function term integrates to zero, while ${\int }_{-1/2}^{1/2}{u}^{2}du=1/12$. Hence the bias of a kernel density estimator obeysThis is a second-order pointwise bias bound for kernel density estimation. Existence and boundedness of the second derivative suffice for the stated remainder; continuity of that derivative is not an extra assumption.

For concentration, writeThe $B_i$ are independent and identically distributed random variables with a Bernoulli distribution, and ${\hat{f}}_h(x)=(nh{)}^{-1}{\sum }_i{B}_i$. The required concentration bound follows from the Hoeffding lemma. We prove its Bernoulli case directly. Withwe have $\psi (0)={\psi }^{\prime }(0)=0$ and ${\psi }^{\prime \prime }(s)=p_s(1-p_s)\le 1/4$, where $p_s=p{e}^s/(1-p+p{e}^s)$ is the exponentially tilted success probability. Therefore $\psi (s)\le s^2/8$ for every real $s$. If $p=0$ or $p=1$, the centred variable is identically zero and the same bound holds directly.

Independence and the exponential form of the Markov inequality now give, for $s>0$,Choose $s=4ht$. Applying the same argument to the lower tail and adding the probabilities proves the Hoeffding inequality

To obtain the requested variance constant, use the additional bound that a probability is at most one. Set $Z={\hat{f}}_h(x)-\mathbb{E}{\hat{f}}_h(x)$ and $a=2n{h}^2$. The tail integral formula for moments, justified by Tonelli theorem, yieldsThusThe clipping at one is essential for this integration argument to give that constant. It is an instance of a second moment bound from a clipped Gaussian tail. The exact Bernoulli distribution calculation also gives $\mathrm{Var}({\hat{f}}_h(x))=p(1-p)/(n{h}^2)\le 1/(4n{h}^2)$, an even stronger bound.

Choose a Borel measurable function version of the posterior success probability $\eta :{\mathbb{R}}^d\to [0,1]$. Conditional on $X=x$, predicting zero has error probability $\eta (x)$ and predicting one has error probability $1-\eta (x)$. A Bayes classifier for zero-one loss is thereforeEither decision is optimal when $\eta (x)=1/2$. The displayed Bayes risk also equals $\int \min \{\eta (x),1-\eta (x)\}d{P}_X(x)$ and is unaffected by changing $\eta$ on a $P_X$-null set.

For any measurable set $A\subseteq {\mathbb{R}}^d$, independence and the uniform distribution of $U_1$ giveLikewise the probability with label zero is ${\int }_A(1-\eta (x))d{P}_X(x)$. These sets determine the joint probability distribution, soThe same construction makes all training pairs independent and identically distributed random variables.

Fix a feature-measurable nearest-neighbour tie-breaking rule, for example increasing original index for observations at equal Euclidean norm distance from the query. This is important: the ordering may depend on the features, but not on the $U_i$ or labels. Let $Y_{(j)}(x)$ be the label attached to the $j$th ordered feature. The classifier from the K-nearest neighbors algorithm isThe displayed rule resolves a tied vote in favour of one; any fixed vote convention would also define the method. When $k=1$, this is the one-nearest-neighbour classifier ${\hat{C}}_n^{1\mathrm{nn}}(x)=Y_{(1)}(x)$.

Write $I_n(x)$ for the selected original index. Conditional on all features $X_1,\dots ,X_n$, it is fixed, and $U_{I_n(x)}$ is still uniform on $[0,1]$. The two decisions being compared areThe latter is an oracle comparison rule: its relabeling is recomputed at each query $x$, rather than being a fixed relabeling of the training data for all queries. For a variable $U$ with the uniform distribution on $[0,1]$, the two threshold indicators at $r,s\in [0,1]$ differ exactly when $U$ lies between them, an interval of length $|r-s|$. This Bernoulli coupling by a shared uniform random variable proves

Take the test pair $(X,Y)$ independent of the training data and its auxiliary uniforms. Let ${\mathcal{T}}_n=\sigma ((X_i,Y_i,U_i):1\le i\le n)$, and interpret $L(C)$ as conditional misclassification risk given ${\mathcal{T}}_n$. The tower property of conditional expectation gives $\mathbb{E}L(C)=\mathbb{P}(C(X)\ne Y)$. Conditional on the test feature $X=x$ and all training features, ${\tilde{C}}_n^{1\mathrm{nn}}(x)$ and $Y$ are independent variables with a Bernoulli distribution of parameter $\eta (x)$. Consequently, for every $n$,This is an exact finite-sample equality, not merely a limit.

The two error indicators can differ only if the two classifiers disagree, soThe permitted nearest-neighbour approximation theorem states that the last expected value tends to zero for the feature-based selection rule. This establishes the one-nearest-neighbour asymptotic risk

For $r\in [0,1]$, put $a=\min (r,1-r)\in [0,1/2]$. Then $2r(1-r)=2a(1-a)$, and $a\le 2a(1-a)\le 2a$. Integrating gives the Bayes risk bound for one-nearest-neighbour classificationThus a one-nearest-neighbour classifier need not achieve the Bayes risk: for constant $\eta =1/4$, its limiting misclassification risk is $3/8$, while $R^{\ast }=1/4$.

Feature-based neighbour tie-breaking is required. The convention cannot be dropped for arbitrary $P_X$. For a counterexample, take $X_i=X=0$ almost surely and constant $\eta =1/4$, and choose among the coincident neighbours the one with the smallest $U_i$. Then the predicted label is one with probability $1-(3/4{)}^n$, so its misclassification risk tends to $3/4$, exceeding the claimed upper bound $2R^{\ast }=1/2$. The corrected theorem uses ties determined independently of the uniforms and labels, as above.

Let $p=dP/d\nu$ and $q=dQ/d\nu$ be Radon-Nikodym derivatives. Use the following normalizations of the Kullback-Leibler divergence, total variation distance and unnormalized Hellinger distance:We use $0\log (0/q)=0$ and assign infinite Kullback-Leibler divergence if $Pot\ll Q$, where $\ll$ denotes absolute continuity of measures. Common domination alone also suffices for the inequalities with the extended-value convention. The negative part of the logarithmic integral is integrable: on $p<q$, $p\log (q/p)\le q-p\le q$. Thus the extended-value integral defining the Kullback-Leibler divergence is well-defined. These expressions do not depend on which common dominating measure is chosen. The Kullback-Leibler divergence is generally asymmetric and therefore fails a defining property of a metric.

For completeness, the integral formula for total variation distance follows by taking $A=\{p\ge q\}$: since $\int (p-q)d\nu =0$, the positive and negative parts of $p-q$ have the same integral, and this set attains the supremum.

Put $a=\int \sqrt{pq}d\nu \le 1$, by the Cauchy-Schwarz inequality. A second application givesThe logarithmic inequality in the hint implies $\log t\le t-1$ for $t>0$. Apply it to $t=\sqrt{q/p}$ on $\{p>0\}$:Multiplying by $p$ and integrating provesIf $q=0<p$ on a set of positive $P$-measure, the right side is finite but the Kullback-Leibler divergence is infinite, so the inequality is immediate. ThusThis total variation–Hellinger–relative entropy inequality requires the stated Hellinger distance normalization for its first constant. With the alternative convention ${\bar{h}}^2=\frac{1}{2}\int (\sqrt{p}-\sqrt{q}{)}^2$, the correct comparison is $\mathrm{TV}\le \sqrt{2}\bar{h}$ and $\bar{h}\le \sqrt{\mathrm{KL}/2}$. In particular, $P=\mathrm{Bernoulli}(0.6)$ and $Q=\mathrm{Bernoulli}(0.4)$ have $\mathrm{TV}=0.2>\bar{h}\approx 0.1421$.

Here is a testing form of the Le Cam two-point lemma. Suppose two parameter values ${\theta }_0,{\theta }_1$ in a metric space have separation $\Delta =d({\theta }_0,{\theta }_1)>0$, and let $P_0,P_1$ be the corresponding observation laws. Every estimator $T$ satisfiesTo prove it, classify $T$ by the closer of the two parameters, breaking a tie in favour of one. Let $A=\{d(T,{\theta }_1)\le d(T,{\theta }_0)\}$. On $A$, the triangle inequality implies $d(T,{\theta }_0)\ge \Delta /2$, while on $A^c$ it implies $d(T,{\theta }_1)>\Delta /2$. Hence the sum of the two probabilities in the display is at leastAt least one is at least half the sum, proving the claim. It also gives a lower bound $\Delta (1-\mathrm{TV})/4$ for the maximum expected metric loss.

For absolute-error loss, or any loss given by a metric, there is a stronger expectation form. Take densities $p_0,p_1$ relative to $m=P_0+P_1$ and use the triangle inequality under their overlap:Therefore the Le Cam lower bound under absolute-error loss isBoth arguments are valid for randomized estimators as well, by adjoining the independent randomization to the observation; doing so does not change total variation distance.

For the normal distribution model, assume the usual nondegenerate convention $\sigma >0$ and use the full product observation laws. ChooseFor one observation, its Gaussian log likelihood ratio isUnder the first law, ${\mathbb{E}}_0(X-{\mu }_1{)}^2={\sigma }^2+({\mu }_1-{\mu }_0{)}^2$ and ${\mathbb{E}}_0(X-{\mu }_0{)}^2={\sigma }^2$. Thus the Kullback-Leibler divergence between normal distributions isFor the independent and identically distributed random variables, the joint log likelihood ratio is the sum of the individual ones, so the Kullback-Leibler divergence of the two full statistical samples is $n({\mu }_1-{\mu }_0{)}^2/(2{\sigma }^2)=1/4$. The comparison just proved implies $\mathrm{TV}(P_0,P_1)\le 1/2$. Applying the expectation form of the Le Cam two-point lemma givesThis is a Gaussian location minimax lower bound under absolute-error loss. The constant may depend on the fixed known $\sigma$, but neither on the estimator nor on $n$. If a signed nonzero scale were used, the same result holds with $|\sigma |$ in place of $\sigma$. If zero noise were allowed, $X_1=\mu$ would estimate $\mu$ exactly, so a positive lower bound would be false; positive variance is necessary.

Use the natural cubic spline convention appropriate to the interior design knots: the spline is linear on $[a,x_1]$ and $[x_n,b]$. We also need $n\ge 2$. These points will be important for uniqueness.

A cubic spline is a function in $C^2[a,b]$ whose restriction to each of $[a,x_1]$, $[x_1,x_2]$, through $[x_n,b]$ is a polynomial of degree at most three. A spline knot is a junction between consecutive pieces. For a natural cubic spline, the two exterior pieces are affine functions; equivalently, one uses the natural endpoint conditions $g^{\prime \prime }(x_1)=g^{\prime \prime }(x_n)=0$ on the spline over $[x_1,x_n]$ and then extends linearly with matching derivatives. Merely prescribing $g^{\prime \prime }(a)=g^{\prime \prime }(b)=0$ on otherwise arbitrary exterior cubic pieces is a different condition and does not provide the unique interpolant invoked in this question.

The natural cubic spline interpolant $N\mathbf{v}$ to values $\mathbf{v}=(v_1,\dots ,v_n{)}^T$ is the natural cubic spline satisfying $(N\mathbf{v})(x_i)=v_i$. Its existence and uniqueness for $n\ge 2$ are the interpolant fact allowed in the PDF. The interpolation map $N$ is a linear map: a linear combination of interpolants satisfies the same spline, boundary and value conditions, so uniqueness identifies it with the interpolant to the corresponding linear combination of value vectors.

Let $g=N\mathbf{v}$, let $\tilde{g}\in C^2[a,b]$ have the same values, and put $r=\tilde{g}-g$. Then $r(x_i)=0$. We prove the orthogonalityApply integration by parts twice on each polynomial interval. On an interior interval, $g^{\prime \prime \prime \prime }=0$, andThe $g^{\prime \prime \prime }r$ terms vanish because $r$ vanishes at the knots. The $g^{\prime \prime }{r}^{\prime }$ terms cancel at internal knots because $g^{\prime \prime }$ and $r^{\prime }$ are continuous, and vanish at $x_1,x_n$ because $g^{\prime \prime }$ is zero there. On the exterior intervals, $g^{\prime \prime }=0$ identically. Summing therefore gives the claimed orthogonality without assuming that $g^{\prime \prime \prime }$ is continuous across knots.

Expanding the square now gives the minimum roughness property of the natural cubic spline interpolantEquality forces $r^{\prime \prime }=0$ everywhere, since $r^{\prime \prime }$ is continuous. Thus $r$ is an affine function. It vanishes at two distinct design points, so $r=0$, proving equality if and only if $\tilde{g}=g$.

For the penalized fit, take the allowed spline roughness penalty matrix $\Gamma$ to be a symmetric matrix with ${\mathbf{z}}^T\Gamma \mathbf{z}\ge 0$; thus it is a positive semidefinite matrix. If its supplied representative were not symmetric, its symmetric part defines the same quadratic form and is all that is needed. For any $\tilde{g}$, let $\mathbf{v}=(\tilde{g}(x_i){)}_{i=1}^n$. Replacing it by $N\mathbf{v}$ preserves every fitted value and can only decrease the second derivative roughness penalty. Therefore it is enough to minimizeover ${\mathbb{R}}^n$. The matrix $A_{\lambda }=I_n+\lambda \Gamma$ is a positive-definite matrix, sinceCompleting the quadratic or differentiating gives the unique solutionThis is the cubic smoothing spline. More explicitly, the normal equations are $(I_n+\lambda \Gamma ){\hat{\mathbf{v}}}_{\lambda }=\mathbf{Y}$, andFor an arbitrary function with fitted vector $\mathbf{v}$, the earlier orthogonality also givesBoth terms are nonnegative. Equality forces $\mathbf{v}={\hat{\mathbf{v}}}_{\lambda }$ and, by the proved interpolation equality case, $\tilde{g}=N\mathbf{v}={\hat{g}}_{\lambda }$. This proves both existence in $C^2[a,b]$ and uniqueness over the entire stated function class, not just over splines.

The argument is deterministic for each observed $\mathbf{Y}$. The fixed-design nonparametric regression and homoscedasticity assumptions motivate the squared-error loss, but Gaussian errors are not required.

At least two distinct design points are required for uniqueness. Question 4 does not explicitly restate $n\ge 2$, and this hypothesis is necessary. With one design point, every function $\tilde{g}(x)=Y_1+c(x-x_1)$ has zero residual and zero second derivative roughness penalty, for any real $c$. Thus the printed unrestricted uniqueness conclusion would be false for $n=1$. The corrected theorem assumes at least two distinct knots and the stated linear-tail convention. At $\lambda =0$, uniqueness over all of $C^2[a,b]$ also fails; the stipulated $\lambda >0$ eliminates that degeneracy.