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

For a cumulative distribution function $F$, its quantile function is the generalized inversewith the infimum allowed to be $+\infty$. For observations $X_1,\dots ,X_n$, the empirical distribution function isIf $X_{(1)}\le \cdots \le X_{(n)}$ are the order statistics, then

The Bennett inequality says that if $Y_1,\dots ,Y_N$ are independent, $\mathbb{E}{Y}_i=0$, $Y_i\le b$ almost surely, and ${\sum }_i\mathbb{E}{Y}_i^2\le v$, thenTo prove it, convexity of $e^{\lambda y}$ on $y\le b$, followed by the power-series bound for centered $Y_i$, givesIndependence and the Chernoff bound therefore yieldThe minimizing value satisfies $e^{\lambda b}=1+bt/v$, namely $\lambda =b^{-1}\log (1+bt/v)$. Substitution gives the stated exponent.

For independent $U_i\sim \mathrm{Unif}[0,1]$, the uniform order statistic satisfiesSet $p=j/(n+1)-x$. The event $U_{(j)}\le p$ means that at least $j$ sample points lie in $[0,p]$. If this occurs, some $j$-element subset consists entirely of such points. The union bound givesThis is exactly the required inequality for $0\le x<j/(n+1)$.

Put $r=\lceil \beta \rceil -1$ and $\alpha =\beta -r\in (0,1]$. The density Hölder class $\mathcal{F}(\beta ,L)$ consists of nonnegative functions $f$ integrating to one, with derivatives through order $r$, such thatThis is the density version of the Hölder class. A kernel for density estimation is an integrable function $K$ with $\int K=1$. It has order $\ell$ when $\int u^{j}K(u)du=0$ for $1\le j<\ell$ and $\int |u{|}^{\ell }|K(u)|du<\infty$.

Choose a bounded kernel of order at least $\lceil \beta \rceil$ with $\int |u{|}^{\beta }|K(u)|du<\infty$, and use the kernel density estimatorTaylor's theorem at $x$ and the vanishing kernel moments cancel every polynomial term below the remainder. Hence, for a constant depending only on $\beta$ and the fixed kernel,

We also need a uniform density bound. The standard Hölder interpolation argument combines nonnegativity, $\int f=1$, and the Hölder constraint to giveIndeed, near a point where $f$ is close to its maximum $M$, Taylor's theorem and the derivative bounds implied by the Hölder constraint keep $f$ of order $M$ on an interval of length comparable to $(M/L{)}^{1/\beta }$; integrating over that interval gives $M^{1+1/\beta }\le C_{\beta }{L}^{1/\beta }$.

Using this bound and independence,ThusChooseBoth terms then have order $L^{2/(\beta +1)}{n}^{-2\beta /(2\beta +1)}$. Since the infimum over all measurable estimators is no larger than the risk of this particular estimator,This is the pointwise minimax rate for Hölder density estimation upper bound.

Write $t_i=(x_i-x)/h$, $r_p(t)=(1,t,\dots ,t^p{)}^T$, and defineThe degree-$p$ local polynomial regression fit minimizesAssume its local polynomial Gram matrixis positive definite. The normal equations then give

Because the polynomial is written in the scaled coordinate, the local polynomial derivative estimator is ${\hat{m}}_n^{\prime }(x)={\hat{\beta }}_1/h$. If $e_1=(0,1,0,\dots ,0{)}^T$, thenFor a polynomial $R$ of degree at most $p$, the local least-squares fit to $Y_i=R(x_i)$ is exactly the Taylor polynomial $R(x+ht)$, so its scaled linear coefficient is $h{R}^{\prime }(x)$. Therefore the polynomial reproduction property of local polynomial regression gives

Positive definiteness and the fixed finite-dimensional basis provide a number ${\lambda }_0>0$ such thatSince $K(t_i)=0$ outside $|x_i-x|\le h$,and

The regular design has at most $2nh+2\le 4nh$ points in this window when $h\ge 1/(2n)$. Since the errors are independent with variance at most ${\sigma }^2$,

Finally let ${\beta }_0=\lceil \beta \rceil -1$ and take the degree-${\beta }_0$ Taylor polynomial $R$ of $m$ at $x$. The Hölder class remainder satisfiesPolynomial reproduction removes $R$ from the bias. On the kernel window the remainder is at most $L{h}^{\beta }/{\beta }_0!$, so the weight-sum bound gives

The total variation distance and Kullback-Leibler divergence arewith the divergence $+\infty$ when $P$ is not absolutely continuous with respect to $Q$.

For $P=\mathrm{Laplace}(0)$ and $Q=\mathrm{Laplace}(\mu )$,If $X\sim P$, direct integration on the intervals cut by $0$ and $\mu$ givesConsequently

One squared-loss form of Assouad's lemma is as follows. Suppose $(P_{\omega },{\theta }_{\omega }{)}_{\omega \in \{0,1{\}}^k}$ is an Assouad hypercube such thatand every pair of neighboring vertices satisfies $\mathrm{TV}(P_{\omega },P_{{\omega }^{\prime }})\le \eta$. ThenTo prove it, decode from $\hat{\theta }$ a nearest hypercube vertex. The separation condition converts estimation loss into a constant multiple of its Hamming error. Average this error under the uniform prior on $\omega$ and sum coordinatewise. For each coordinate, the two equally weighted mixtures with that bit equal to zero or one have total variation at most $\eta$ by convexity. The minimum average error of any binary test is $(1-\mathrm{TV})/2$, which gives the displayed bound after the nearest-vertex factor.

We now build such a hypercube inside the monotone cone. Let $k=\lfloor c_0{n}^{1/3}\rfloor$ and $m=\lfloor n/k\rfloor$. Divide the first $km$ coordinates into $k$ consecutive blocks. For $\omega \in \{0,1{\}}^k$, set on block $j$and extend the remaining coordinates at the last level. If $c_0,c_1$ are sufficiently small universal constants, every signal is nondecreasing and belongs to $[0,1{]}^n$.

Neighboring vertices differ by $\delta$ on one block, so their squared Euclidean separation is $m{\delta }^2$. Their product experiments differ only on that block and haveBy Pinsker's inequality, choosing $c_1$ small makes every neighboring total variation distance at most, say, $1/4$.

Apply Assouad's lemma with normalized squared loss $d^2(\theta ,{\theta }^{\prime })=n^{-1}\Vert \theta -{\theta }^{\prime }{\Vert }^2$. Here $a=m{\delta }^2/n=c_1^2/n$, and henceThis proves the lower half of the minimax rate for isotonic sequence estimation.