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

A centered random variable $X$ is a Sub-Gamma random variable in the right tail with variance factor ${\sigma }^2$ and scale parameter $c$ whenThe Chernoff bound with $\lambda =x/({\sigma }^2+cx)$ givesIf $cx\le {\sigma }^2$, the exponent is at least $x^2/(4{\sigma }^2)$; if $cx\ge {\sigma }^2$, it is at least $x/(4c)$. Hence

Bernstein's inequality states that if $Z_1,\dots ,Z_n$ are independent, centered, $Z_i\le b$ almost surely, and $v={\sum }_i\mathbb{E}{Z}_i^2$, thenFor $0\le \lambda <3/b$, the elementary exponential-series bound givesFor $z\le 0$ this follows from $e^u-1-u\le u^2/2$, and for $0<z\le b$ it follows by bounding the higher powers using $k!\ge 23^{k-2}$. Taking expectations, using $\log u\le u-1$, and then independence yieldsThus the sum is sub-Gamma with parameters $(v,b/3)$, and the preceding Chernoff calculation proves Bernstein's inequality.

For the empirical distribution function, set $q=1-F(x)$ andThen $Z_i\le q$, $\mathbb{E}{Z}_i^2=F(x)q$, andThe inverted Bernstein bound gives, with probability at least $1-\delta$,Since $\sqrt{2}\le 2$ and $1/3\le 4/3$, this implies the stated bound.

A kernel for density estimation is an integrable function $K$ with $\int K=1$. With $K_h(u)=h^{-1}K(u/h)$, the kernel density estimator isA kernel of order ell satisfies

Split the integrated $L^p$ risk into stochastic and bias terms:For fixed $x$, put $A_i(x)=K_h(x-X_i)$ and $W_i(x)=A_i(x)-\mathbb{E}{A}_i(x)$. The supplied Rosenthal inequality givesNowAlso $\mathbb{E}{W}_1(x{)}^2\le (K_h^2\ast f)(x)$. The Young convolution inequality with exponent $p/2$ givesAfter integration and multiplication by the outer factor $2^{p-1}$, the stochastic contribution is at most

It remains to control the bias. Here $\ell =\lceil \beta \rceil =m+1$. The Taylor formula with integral remainder, the vanishing kernel moments, and Minkowski integral inequality giveThe defining Nikol'skii smoothness bound is $L|hu{|}^{\beta -m}$, soRaising to the $p$th power and applying the outer factor $2^{p-1}$ proves

A cubic spline with knots $x_1<\cdots <x_n$ is twice continuously differentiable and restricts to a polynomial of degree at most three between consecutive knots. It is a natural cubic spline when it is linear outside $[x_1,x_n]$, equivalently when its second derivative vanishes at the two outer knots and on the exterior intervals.

Let $s$ be the natural cubic spline interpolating prescribed values and let $\tilde{g}=s+h$ be any other interpolant in $S_2[a,b]$. Then $h(x_i)=0$. Piecewise integration by parts, using that $s^{\prime \prime \prime \prime }=0$ between knots, $s^{\prime \prime }$ is continuous, $s^{\prime \prime }=0$ on the exterior intervals, and every jump of $s^{\prime \prime \prime }$ is multiplied by $h(x_i)=0$, givesConsequentlyEquality forces $h^{\prime \prime }=0$ almost everywhere. Then $h$ is affine and its zeros at at least two distinct knots force $h=0$, proving uniqueness.

For the penalized problem, fix a vector $u=(u_1,\dots ,u_n{)}^T$ of fitted values. The preceding variational result says that its natural spline interpolant has the least roughness among all functions taking those values, and by assumption that roughness is $u^{T}Ku$. The infinite-dimensional problem therefore reduces toBecause $K$ is positive semidefinite, $I+\lambda K$ is positive definite. The unique fitted-value vector isand ${\hat{g}}_{\lambda }$ is its unique natural cubic spline interpolant.

For Leave-one-out cross-validation, let ${\hat{g}}_{-i,\lambda }$ minimizeand defineIf $u_j^{(-i)}={\hat{g}}_{-i,\lambda }(x_j)$, its normal equations sayThus $u^{(-i)}=A_{\lambda }{\tilde{Y}}^{(i)}$, whereTaking the $i$th coordinate and writing $\hat{u}=A_{\lambda }Y$ givesTherefore one spline fit and the diagonal of its smoothing matrix give

One form of Assouad's lemma is as follows. Let $\{P_{\omega }:\omega \in \{0,1{\}}^m\}$ be a statistical experiment and suppose parameters satisfyIf adjacent vertices of the hypercube satisfythen every estimator obeysup to the inessential convention-dependent universal constant.

Construct a hypercube inside the convex cone. Start from $f_{\ast }(x)=x^2$. Partition most of $[0,1]$ into $m=\lfloor n/k\rfloor$ consecutive blocks of $k$ grid intervals. On block $j$, let ${\varphi }_j$ be the chord joining the two endpoint values of $f_{\ast }$ minus $f_{\ast }$ inside the block, and zero outside. For $\omega \in \{0,1{\}}^m$, setReplacing a convex arc by its chord leaves a convex, nondecreasing function. Its values remain in $[0,1]$, so every ${\theta }_{\omega }$ belongs to $C_n\cap M_n\cap [0,1{]}^n$, and hence also to the larger parameter set in the first claim.

The perturbations have disjoint supports. For neighboring hypercube vertices their squared Euclidean separation is independent of the block and, using the supplied sum, satisfiesThe observations have identity covariance, so the Kullback-Leibler divergence between normal distributions for neighboring vertices is ${\rho }^2/2$. Choosewith a sufficiently small universal $c_0>0$. Then ${\rho }^2$ is bounded above by a small constant and below by another positive constant for all sufficiently large $n$. Pinsker's inequality makes every neighboring total-variation distance at most some fixed $\alpha <1$.

Assouad's lemma, with squared Euclidean loss divided by $n$, now gives

The same hypercube already lies in $C_n\cap M_n\cap [0,1{]}^n$. Therefore that smaller class has the same $c{n}^{-4/5}$ minimax lower bound. An upper bound $C{n}^{-\gamma }$ with $\gamma >4/5$ would eventually be smaller, which is impossible. Thus no estimator with the proposed uniform rate can exist.