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

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.