= Solution
The stopping rule ensures that the returned function belongs to
$$
\mathcal H
=\left\{\sum_{m=1}^M\beta_mh_m:
\beta_m\geq0,\ \sum_m\beta_m\leq1,\ h_m\in B\right\}.
$$
Indeed, 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)|\leq1$. 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> gives
$$
\mathbb ER_\phi(\widehat f)
\leq\mathbb E\widehat R_\phi(\widehat f)
+2e\,\mathbb E\widehat R(\mathcal H(X_{1:n})).
$$
A 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> gives
$$
\widehat R(\mathcal H(x_{1:n}))
\leq\widehat R(B(x_{1:n}))
\leq r_B.
$$
Combining the two bounds proves
$$
\boxed{
\mathbb ER_\phi(\widehat f)
\leq\mathbb E\widehat R_\phi(\widehat f)+2\exp(1)r_B}.
$$
Back to article page
