One-sided Rademacher complexity

Let $(\mathcal{Z},\mathcal{A},P)$ be a probability space and let $\mathcal{G}$ be a nonempty class of $\mathcal{A}$-measurable functions $g:\mathcal{Z}\to [0,1]$. For a fixed sample $S=(z_1,\dots ,z_m)\in {\mathcal{Z}}^m$, where $m\ge 1$, let ${\sigma }_1,\dots ,{\sigma }_m$ be independent uniform signs in $\{-1,+1\}$. Define

$P_{m}g:=\frac{1}{m}{\sum }_{i=1}^{m}g(z_i),Pg:=\int gdP,$

and define the empirical Rademacher complexity by

${\widehat{\mathfrak{R}}}_S(\mathcal{G}):={\mathbb{E}}_{\sigma }[{\sup }_{g\in \mathcal{G}}\frac{1}{m}{\sum }_{i=1}^m{\sigma }_{i}g(z_i)]\mathrm{.}$

Here ${\mathbb{E}}_{\sigma }$ is the uniform average over the $2^m$ sign vectors. If $S=(Z_1,\dots ,Z_m)$ is an IID sample with common law $P$, and the displayed supremum is measurable as a function of $S$, the expected Rademacher complexity is

${\mathfrak{R}}_m(\mathcal{G}):={\mathbb{E}}_{S\sim P^m}{\widehat{\mathfrak{R}}}_S(\mathcal{G})\mathrm{.}$

The class may be finite, countable, or uncountable when the indicated supremum is measurable; a specified countable subclass giving the same supremum for every sign vector for almost every sample suffices. This is the one-sided convention: the definition contains no absolute value, and zero need not belong to $\mathcal{G}$. Both complexities lie in $[0,1]$: every signed average lies in $[-1,1]$, and for any fixed $g_0\in \mathcal{G}$ the sign-average supremum is at least the sign-average for $g_0$, which is zero.

Probability measures and probability spaces: $P$ is a measure of total mass one on $(\mathcal{Z},\mathcal{A})$.

Empirical, centered, and Rademacher processes: defines the notation $Pg=\int gdP$, $P_{m}g=m^{-1}{\sum }_{i}g(Z_i)$ and the one-sided Rademacher process.

One-sided empirical Rademacher complexity: uses the same nonabsolute sign supremum normalization for fixed samples and finite or countable classes.

Identical distribution and IID families: IID means mutually independent random elements with the same law.

Independent random elements have product joint law: identifies the joint law of a finite independent tuple with the product of its marginals, so an IID tuple with common law $P$ has law $P^m$.

Mohri et al., Definitions 3.1–3.2, printed pp. 30–31: the adopted $1\mathrm{/}m$ one-sided empirical and expected normalization.

Bartlett and Mendelson, Definition 2, printed p. 464: an independent treatment using an absolute supremum and a $2\mathrm{/}m$ normalization, recorded for comparison.