Past exam of the algorithmic foundations of learning course of the University of Oxford / 2025 / 3

The statement necessarily treats $P_0,P_1$ as probability measures, as required by the sampling model $X\sim P_J$. The word "measures" in the introduction must be read with this normalization. Use the paper's convention $H^2(P,Q)=\frac{1}{2}\int (\sqrt{p}-\sqrt{q}{)}^{2}d\mu$ for the Squared Hellinger distance throughout this question.

A measurable binary hypothesis test $\psi$ is determined by the measurable set $A=\{x:\psi (x)=1\}$. Under the uniform prior on the two hypotheses, its error probability isSince the two measures have equal total mass,Indeed, the integral over any set is at most the integral of the positive part, and equality holds for $A=\{p_1>p_0\}$. This is also the total variation distance. The likelihood ratio rule choosing hypothesis $1$ precisely on that set therefore attains the infimum, provingArbitrary choices on the tie set $\{p_1=p_0\}$ leave the error unchanged. This is the exact link between total variation distance and optimal binary statistical hypothesis testing.

Put $h=H^2(P_0,P_1)$ with the paper's normalized Hellinger distance. The Hellinger affinity isThe last bound follows from the Cauchy-Schwarz inequality and the unit integrals of the two probability density functions. Using a common dominating probability measure, for example $(P_0+P_1)/2$, makes the product calculation immediate. The probability density functions of the product measures factor, and Tonelli's theorem givesThe Squared Hellinger distance is independent of the choice of common dominating measure, so this calculation applies to the original distributions. We obtain the exact identity and then apply Bernoulli's inequality:For completeness, the scalar bound follows by induction: $(1-h{)}^1=1-h$, and multiplying $(1-h{)}^n\ge 1-nh$ by the nonnegative $1-h$ gives $(1-h{)}^{n+1}\ge 1-(n+1)h+n{h}^2\ge 1-(n+1)h$.

Use two translated uniform distributions, with parameters $0$ and $a=1/(2n)$. Their distance in the usual metric is $a$, so take the separation radius $\delta =a/2=1/(4n)$ and the loss function $\Phi (r)=r^2$. The supplied testing reduction, equivalently the Le Cam two-point lemma, and part (a)(i) implyTo see the reduction directly, turn any estimator into a binary hypothesis test by choosing the closer of $0$ and $a$. If the test is wrong, the absolute estimation error is at least $a/2$. The worst quadratic risk is at least its average over these two parameters, giving precisely this bound.

Under Lebesgue measure on ${\mathbb{R}}^n$, the two sample probability density functions are the indicators of the cubes $[0,1{]}^n$ and $[a,a+1{]}^n$. Their intersection is $[a,1{]}^n$, of volume $(1-a{)}^n$. Thereforewhere the inequality is Bernoulli's inequality. ConsequentlyThis also fits the Hellinger distance approach: the two one-sample affinities give $H^2(U_0,U_a)=a$, while equal-height indicator densities imply $V(U_0^n,U_a^n)=H^2(U_0^n,U_a^n)$. Part (a)(ii) thus yields the same bound $V\le na=1/2$. The change of support produces Squared Hellinger distance proportional to $a$, explaining the parameter scale $a\asymp n^{-1}$ and quadratic risk scale $n^{-2}$.

Use the first order statistic and correct its bias:This is a measurable function of the sample. Under $U_{\theta }^n$, write $Z=X_{(1)}-\theta$. It lies in $[0,1]$, and independence givesFor a bounded nonnegative random variable, integrating the identities $Z={\int }_0^1{1}_{\{Z>u\}}du$ and $Z^2={\int }_0^{1}2u{1}_{\{Z>u\}}du$ proves the tail integral formula for moments by Tonelli's theorem. HenceThus $\hat{\theta }$ is an unbiased estimator. Its quadratic risk is the variance of $Z$, independent of $\theta$:Taking the supremum over all real $\theta$ and then the infimum over estimators givesThe final inequality follows from $n^3\le (n+1{)}^2(n+2)$. Together with part (i), this proves that the minimax risk has order $n^{-2}$ for all $n\ge 1$. In the last line of the source, the request for the upper-bound constant calls it $C$; here it is denoted $C^{\prime }$ consistently with the upper-bound inequality.