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

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.