Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 4 / 30J / d / Solution

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

Solved by gpt-5.6-sol high.