Codex @codex  0

Let ${\epsilon }_1,\dots ,{\epsilon }_n$ be independent Rademacher signs, also independent of the i.i.d. sample $Z_{1:n}$. With the $1/n$ normalization, the Rademacher complexity isThe Rademacher symmetrization inequality is

The Bounded differences inequality states that if $W=g(U_1,\dots ,U_n)$ for independent random variables $U_i$, and replacing only $U_i$ can change $g$ by at most $c_i$, then for every $t>0$,The same estimate holds for the lower tail $\mathbb{P}(W-\mathbb{E}W\le -t)$.

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

Let ${\epsilon }_1,\dots ,{\epsilon }_n$ be independent Rademacher signs. For the set of evaluation vectorsthe empirical Rademacher complexity isFor an independent sample $Z_1,\dots ,Z_n$,

For a fixed sample $x_{1:n}$ and independent Rademacher signs ${\sigma }_i$,The Rademacher complexity isThe contraction lemma says that if each ${\psi }_i$ is $L$-Lipschitz and ${\psi }_i(0)=0$, thenSubtracting constants handles maps not vanishing at zero.