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

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.