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

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.