Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 4 / 30J (Mathematics of Machine Learning)

The AdaBoost algorithm starts with weights $w_i^{(1)}=1/n$. For $m=1,\dots ,M$:

Because $h\in B$ implies $-h\in B$, the selected classifier can always have weighted error at most $1/2$, so ${\hat{\beta }}_m\ge 0$. The output score is

The convex hull of $S\subseteq {\mathbb{R}}^d$ isThus $v$ is a convex combination of $v_1,\dots ,v_m$ when it has precisely this form. Equivalently, $\mathrm{conv}S$ is the smallest convex set containing $S$. The Caratheodory theorem sharpens the finite-combination description in ${\mathbb{R}}^d$: every point of $\mathrm{conv}S$ is a convex combination of at most $d+1$ points of $S$.

The exponential loss is $\varphi (z)=e^{-z}$. For a score $f:\mathcal{X}\to \mathbb{R}$, its exponential classification risk and empirical risk areFor the set of evaluation vectorsits empirical Rademacher complexity iswhere the ${\sigma }_i$ are independent uniform random signs.

The stopping rule ensures that the returned function belongs toIndeed, when adding the next coefficient would make the sum exceed one, the algorithm returns the preceding sum, and at the first step it returns zero.

Since each $h_m$ takes values in $\{-1,1\}$, every $f\in \mathcal{H}$ satisfies $|f(x)|\le 1$. On $[-1,1]$, the map $z\mapsto e^{-z}$ is $\exp (1)$-Lipschitz. The expected Rademacher complexity generalization inequality followed by the Rademacher contraction lemma givesA linear functional attains the same supremum over a set and its convex hull. Since $B=-B$, adjoining zero and allowing total coefficient at most one does not increase the supremum, so the Rademacher complexity of a convex hull givesCombining the two bounds proves