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

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.