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

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.