Past exam of the algorithmic foundations of learning course of the University of Oxford / 2025 (SC10, A16556H1)

Solutions to all three questions. Source: Oxford examination paper, parent PDF pages 17–22; paper pages 1–6.

Write $\psi (s)=\log \mathbb{E}{e}^{sX}$ for the cumulant-generating function, and let $D_{+}=\{s>0:\psi (s)<\infty \}$. This set is nonempty. In fact, finiteness of the moment-generating function at some $\eta >0$ and $-\eta$ givesso $X$ is an integrable random variable. Put $m=\mathbb{E}X$.

For the upper tail, use the following one-sided convex conjugate and its strict generalized inverse of a nondecreasing function:Here $\psi (0)=0$, and $I$ is nondecreasing because every slope in its defining supremum is nonnegative. For $x\ge m$, negative $s$ cannot increase the conjugate: $\psi (s)\ge sm$ gives $sx-\psi (s)\le s(x-m)\le 0$, and $s=0$ already gives zero. Thus $I$ agrees with the full Legendre transform of a cumulant-generating function on its upper-tail branch. Using a strict generalized inverse of a nondecreasing function handles constant random variables and bounded supports without assuming a strictly increasing, everywhere finite conjugate. Directly from the definition,This threshold is finite: any fixed $s\in D_{+}$ gives a finite upper bound, while $e^u\ge 1+u$ gives $\mathbb{E}{e}^{s(X-m)}\ge 1$ and hence $\psi (s)\ge sm$, providing the lower bound $m$.

We now derive the needed Chernoff bound. For $s\in D_{+}$ and any real $x$, the pointwise inequality $e^{sX}\ge e^{sx}{1}_{\{X>x\}}$ impliesLet $q={\psi }_X^{\ast -1}(t)$. For every $\epsilon >0$, the infimum formula supplies an $s\in D_{+}$ such that $(t+\psi (s))/s<q+\epsilon$. Thus $\mathbb{P}(X>q+\epsilon )\le e^{-t}$. As $\epsilon \downarrow 0$, these events increase to $\{X>q\}$; continuity from below of a measure provesThe strict event and the strict generalized inverse of a nondecreasing function avoid any assumption that the optimizing $s$ exists. For example, if $X=m$ almost surely, the threshold is $m$ for every $t>0$, and the probability is zero.

Let $M_n={\max }_{1\le i\le n}{X}_i$. For $0<s<1/c$, the exponential of a maximum is bounded by a sum, givingApplying Jensen's inequality to the logarithm yieldsFor $n>1$, put $a=\sqrt{2\log n/\nu }$ and choose $s=a/(1+ca)$. This gives $1-cs=1/(1+ca)$ and thereforeFor $n=1$, let $s\downarrow 0$ in the preceding upper bound, obtaining $\mathbb{E}{X}_1\le 0$. ConsequentlyThe proof uses only the individual moment-generating function bounds for Sub-Gamma random variables in the right tail; it requires no independence. Under the paper's literal one-sided definition, the negative part need not be integrable. The positive part of $M_n$ is integrable by the displayed exponential bound; if $\mathbb{E}{M}_n=-\infty$, the conclusion holds in the extended sense. Otherwise the application of Jensen's inequality is ordinary. Equivalently, truncate $M_n$ below and pass to the limit.

Use closed balls with centres belonging to the space being covered. The covering number iswith value $\infty$ if there is no finite metric net, and value zero for the empty space.

With this intrinsic-centre convention, the proposed monotonicity under subsets is false. Give $R=\{-1,0,1\}$ the usual distance, take $S=\{-1,1\}$, and set $\epsilon =3/2$. A ball centred at $0$ covers $R$, so $N(3/2;R,\rho )=1$. The two points of $S$ are distance $2$ apart, so a ball centred in $S$ contains only its centre, and $N(3/2;S,\rho )=2$. These values are also valid with open balls.

The obstruction is that the useful centre $0$ disappears on passing to the subspace. If centres were allowed anywhere in a fixed ambient space, monotonicity would hold. With intrinsic centres, one instead hasIndeed, discard covering balls missing $S$ and choose one point of $S$ from each remaining ball. The triangle inequality shows that every point of its intersection with $S$ is within $2\epsilon$ of the chosen point. This proves the replacement bound whenever the right side is finite; otherwise it is automatic.

We give a finite chaining argument, keeping the constants explicit. If $\delta =0$, the metric space has just the point $t_0$ and both sides vanish. Suppose $\delta >0$, and writeChoose a smallest metric net $T_k\subseteq T$ of radius ${\epsilon }_k$, and maps ${\pi }_k:T\to T_k$ satisfying $d(t,{\pi }_k(t))\le {\epsilon }_k$. Set $T_0=\{t_0\}$ and ${\pi }_0(t)=t_0$. Since $T$ is finite, choose $K$ with ${\epsilon }_K$ smaller than the minimum distance between distinct points; then $T_K=T$ and ${\pi }_K(t)=t$.

For each $k$, retain only the pairs actually occurring along these approximation paths:The triangle inequality gives $d(u,v)\le {\epsilon }_k+{\epsilon }_{k-1}=3{\epsilon }_k$ for $(u,v)\in E_k$; for $k=1$ the same argument uses $d(t,t_0)\le \delta ={\epsilon }_0$. AlsoHere only monotonicity in the radius for the same space $T$ is used. No monotonicity under subsets is assumed.

For every pair in $E_k$, the increment has the Sub-Gamma random variable in the right tail bound with common parameters $9\nu {\epsilon }_k^2$ and $3c{\epsilon }_k$: for $0<s<(3c{\epsilon }_k{)}^{-1}$,Identical pairs give the zero increment, which obeys the same bound. Both orientations have finite exponential moments, so all increments are integrable random variables. Differentiating their two upper bounds at zero also gives $\mathbb{E}(X_u-X_v)=0$. Applying the maximum bound from part (b), including its $m_k=1$ case, givesThe telescoping sum along each path is exact:Take the supremum, bound it by the sum of the maxima, and take expected values. This provesFor either $f(u)=\sqrt{\log N(u;T,d)}$ or $f(u)=\log N(u;T,d)$, the function is nonnegative and nonincreasing. ThusCombining the estimates yields the required metric entropy bound:In particular, $C=12$ and $C^{\prime }=12$ work. The square-root and linear metric entropy terms arise respectively from the two terms in the sub-Gamma maximum bound. Because the chain ends exactly at $T$, no limiting sample-path regularity assumption is needed.

Work for an arbitrary realization of the sequence, and set $u_t=X_t^T{V}_{t-1}^{-1}{X}_t$. In the Loewner order,By the spectral theorem for real symmetric matrices, every eigenvalue of $V_{t-1}$ is at least $\lambda$. The matrix inverse therefore has eigenvalues at most ${\lambda }^{-1}$, andFor $0\le u\le 1$, put $g(u)=2\log (1+u)-u$. Since $g(0)=0$ and $g^{\prime }(u)=(1-u)/(1+u)\ge 0$, we have $u\le 2\log (1+u)$. The matrix determinant lemma now givesTaking logarithms and using a telescoping sum,This elliptical potential bound holds for every realization and every $n$, without a probabilistic exceptional event. The condition $\lambda \ge 1$ is what ensures $u_t\le 1$.

Let $a_1,\dots ,a_d>0$ be the eigenvalues of the positive-definite matrix $V_n$. Its trace satisfiesThe arithmetic-geometric mean inequality givesSince $\det V_0={\lambda }^d$, taking the logarithm provesThe determinant is largest, for a fixed trace, when the eigenvalues are equal; this is the geometric content of the estimate.

Use the single eventFix a realization in $\mathcal{E}$. The action space is nonempty and compact, since it is a closed subset of the finite-dimensional unit ball. The Lipschitz continuous reward function is continuous, so there is an optimal action $x_{\star }\in {\mathrm{argmax}}_{x\in \mathcal{X}}\mu (⟨x,{\theta }_{\star }⟩)$. Because the same reward function is used at every time, the pseudoregret is $R_n={\sum }_{t=1}^n{r}_t$, whereThe pair $(x_{\star },{\theta }_{\star })$ is feasible in the optimization defining $(X_t,{\theta }_t)$. This optimism in the face of uncertainty givesFor any positive-definite matrix $V$, the ordinary Cauchy-Schwarz inequality applied to $V^{-1/2}x$ and $V^{1/2}z$ provesBoth ${\theta }_t$ and ${\theta }_{\star }$ belong to the same confidence ellipsoid ${\Theta }_{t-1}$. The triangle inequality for the norm associated with this weighted Euclidean inner product therefore givesand hence $r_t\le 2L{\beta }_{t-1}(\delta )|X_t{|}_{V_{t-1}^{-1}}$. Monotonicity of ${\beta }_t(\delta )$ and another Cauchy-Schwarz inequality now yieldThis reasoning holds on $\mathcal{E}$ for every $n$ simultaneously, proving the asserted probability. In combination with part (a), it also givesOnly the supplied simultaneous confidence set coverage and the optimistic choice are needed here. No claim that the displayed linear estimator is automatically a suitable estimator for a nonlinear link is required: its coverage was an explicit hypothesis.

Let ${\mathcal{G}}_t=\sigma (X_1,\dots ,X_t)$. Under $P_{{\theta }_{\star }}$, the true probability density function is positive and finite at every observation almost surely. Define the sequential likelihood ratioA zero numerator sets the product to zero thereafter. Thus $M_t$ is a well-defined nonnegative process, and $L_t({\theta }_{\star })=\log M_t$, with $\log 0=-\infty$.

The next observation is independent of ${\mathcal{G}}_{s-1}$, while ${\hat{\theta }}_{s-1}$ is measurable with respect to that sigma-algebra. Its conditional expectation is thereforeConsequently $\mathbb{E}(M_s\mid {\mathcal{G}}_{s-1})\le M_{s-1}$; induction also gives $\mathbb{E}{M}_s\le 1$. Thus $(M_t)$ is a nonnegative supermartingale for the filtration $({\mathcal{G}}_t)$. It need not be a martingale: an alternative distribution can put mass outside the support of the true distribution.

The maximal inequality for a nonnegative supermartingale, the corresponding form of the Ville inequality, givesThe strict inequality in the definition of the confidence set correctly becomes a non-strict crossing event.

There is a minor definitional omission in the source: for false candidates $\theta$, the printed sum of log-likelihood ratios can involve $0/0$ or both infinite signs. To define the entire confidence set without a positivity assumption, use the logarithm of the ratio of the two full products, ${\prod }_s{p}_{{\hat{\theta }}_{s-1}}(X_s)$ and ${\prod }_s{p}_{\theta }(X_s)$, taking $0/a=0$ for $a>0$, $a/0=+\infty$ for $a>0$, and, for example, $0/0=1$. This is a measurable extension of the printed formula wherever that formula is defined. The choice at $0/0$ cannot affect coverage of the truth, since its full denominator is positive almost surely. Alternatively, strict positivity of every density on the common support removes the omission.

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.