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

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}$.