Rademacher complexity and uniform generalization

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.

Let $m\ge 1$, let $z_1,\dots ,z_m$ be fixed points in a set $\mathcal{Z}$, and let $\mathcal{H}$ be a nonempty class of functions $h:\mathcal{Z}\to \mathbb{R}$. For each $i$, let ${\mathrm{\Phi }}_i:\mathbb{R}\to \mathbb{R}$ be $L$-Lipschitz for one common $L\ge 0$. Suppose either that $\mathcal{H}$ is finite or countable, or that it has a specified nonempty countable subclass ${\mathcal{H}}_0$ for which, for every sign vector $\sigma \in \{-1,+1{\}}^m$, both displayed suprema equal the corresponding suprema over ${\mathcal{H}}_0$. Assume the suprema are finite. With independent uniform signs ${\sigma }_1,\dots ,{\sigma }_m$ and the one-sided normalization

${\widehat{\mathfrak{R}}}_S(\mathcal{H}):=\frac{1}{m}{\mathbb{E}}_{\sigma }{\sup }_{h\in \mathcal{H}}{\sum }_{i=1}^m{\sigma }_{i}h(z_i),$

one has

$\frac{1}{m}{\mathbb{E}}_{\sigma }{\sup }_{h\in \mathcal{H}}{\sum }_{i=1}^m{\sigma }_i{\mathrm{\Phi }}_i(h(z_i))\le L{\widehat{\mathfrak{R}}}_S(\mathcal{H})\mathrm{.}$

No condition ${\mathrm{\Phi }}_i(0)=0$ is required.

One-sided empirical Rademacher complexity: fixes the nonabsolute sign supremum and $1\mathrm{/}m$ normalization.

One-sided coordinate Rademacher contraction: proves this inequality for finite or countable classes, including the no-zero-at-zero case.

Mohri et al., Lemma 5.7, printed pp. 93–94: states the coordinatewise one-sided factor-$L$ contraction under the same normalization.

Bartlett and Mendelson, Theorem 12(4), printed p. 469: uses a different absolute-value convention, assumes the scalar map vanishes at zero, and has factor $2L$; that convention is not used here.

Let $(\mathcal{Z},\mathcal{A},P)$ be a probability space, let $m\ge 1$, and let $\mathcal{G}$ be a nonempty class of measurable functions $g:\mathcal{Z}\to [0,1]$. Let $S=(Z_1,\dots ,Z_m)$ be IID with law $P$, let $S^{\mathrm{\prime }}=(Z_1^{\mathrm{\prime }},\dots ,Z_m^{\mathrm{\prime }})$ be an independent IID copy on a finite product probability extension, and let ${\sigma }_1,\dots ,{\sigma }_m$ be independent uniform signs independent of both samples. Write $P_{m}g=m^{-1}{\sum }_{i}g(Z_i)$ and $P_m^{\mathrm{\prime }}g=m^{-1}{\sum }_{i}g(Z_i^{\mathrm{\prime }})$. Assume the random suprema ${\sup }_g(Pg-P_{m}g)$, ${\sup }_g(P_m^{\mathrm{\prime }}g-P_{m}g)$, ${\sup }_g{\sum }_i{\sigma }_i(g(Z_i^{\mathrm{\prime }})-g(Z_i))$, and ${\sup }_g{\sum }_i{\sigma }_{i}g(Z_i)$ are measurable on their respective product sigma algebras. Then, with ${\mathfrak{R}}_m(\mathcal{G})$ the expected one-sided Rademacher complexity,

${\mathbb{E}}_S{\sup }_{g\in \mathcal{G}}(Pg-P_{m}g)\le 2{\mathfrak{R}}_m(\mathcal{G})\mathrm{.}$

This is a one-sided expectation inequality; it does not assert a tail bound or an absolute-value deviation bound. No choice axiom is assumed.

One-sided Rademacher complexity: ${\mathfrak{R}}_m(\mathcal{G})$ is the expected empirical one-sided sign supremum with normalization $1\mathrm{/}m$.

Mohri et al., Theorem 3.3 proof, printed pp. 31–33: the complete ghost-sample and sign-symmetrization argument for the one-sided bound.

Bartlett and Mendelson, Theorem 8 proof, printed pp. 466–467: an independent ghost-sample proof in their different $2\mathrm{/}m$ absolute-value convention.

Assume the Axiom of Choice (AC). Let $(\mathcal{Z},\mathcal{A},P)$ be a probability space, let $m\ge 1$, and let $\mathcal{G}$ be a nonempty class of measurable functions $g:\mathcal{Z}\to [0,1]$. Take $S=(Z_1,\dots ,Z_m)$ to be the coordinate sample with law $P^m$. Put $P_{m}g=m^{-1}{\sum }_{i}g(Z_i)$ and $\bar{\mathcal{G}}:=\{1-g:g\in \mathcal{G}\}$. Assume the sample, independent-copy and sign suprema over $\mathcal{G}$ and $\bar{\mathcal{G}}$ used in the displayed claims and the symmetrization argument are measurable. Let ${\sigma }_1,\dots ,{\sigma }_m$ be independent uniform signs, and let

${\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),{\mathfrak{R}}_m(\mathcal{G}):={\mathbb{E}}_{S\sim P^m}{\widehat{\mathfrak{R}}}_S(\mathcal{G}),$

where the ${\sigma }_i$ are independent uniform signs, and let $\delta \in (0,1)$. Each of the following four guarantees holds with probability at least $1-\delta$ over $S$:

$\mathrm{\forall }g\in \mathcal{G},Pg\le P_{m}g+2{\mathfrak{R}}_m(\mathcal{G})+\sqrt{\frac{\log (1\mathrm{/}\delta )}{2m}},$

$\mathrm{\forall }g\in \mathcal{G},Pg\le P_{m}g+2{\widehat{\mathfrak{R}}}_S(\mathcal{G})+3\sqrt{\frac{\log (2\mathrm{/}\delta )}{2m}},$

${\sup }_{g\in \mathcal{G}}\mathrm{\mid }Pg-P_{m}g\mathrm{\mid }\le 2{\mathfrak{R}}_m(\mathcal{G})+\sqrt{\frac{\log (2\mathrm{/}\delta )}{2m}},$

${\sup }_{g\in \mathcal{G}}\mathrm{\mid }Pg-P_{m}g\mathrm{\mid }\le 2{\widehat{\mathfrak{R}}}_S(\mathcal{G})+3\sqrt{\frac{\log (4\mathrm{/}\delta )}{2m}}\mathrm{.}$

The four guarantees are separate probability statements. The choice axiom is used through the bounded-differences theorem.

One-sided Rademacher complexity: fixes the one-sided empirical and expected complexities and their $1\mathrm{/}m$ normalization.

One-sided Rademacher symmetrization bound: bounds the expected one-sided deviation by twice the expected complexity.

McDiarmid bounded-differences inequality: supplies bounded-differences concentration under AC.

The Axiom of Choice: AC is the stated set-theoretic axiom carried by the concentration theorem.

The natural logarithm as the inverse of the exponential function: defines $\log$ as the inverse of the exponential on positive inputs.

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: gives the reciprocal law $\log (1\mathrm{/}x)=-\log x$ and monotonicity of $\log$.

Basic identities for a probability measure: gives finite subadditivity for the union bounds.

Mohri et al., Theorem 3.3 and complete proof, printed pp. 31–33: proves both one-sided bounds with the stated constants in the adopted normalization.

Bartlett and Mendelson, Theorems 5 and 8 with proofs, printed pp. 464–467 and 479–480: gives independent risk-bound proofs in its separate absolute/$2\mathrm{/}m$ convention.

Assume AC. Let $(\mathcal{X},{\mathrm{\Sigma }}_X)$, $(\mathcal{Y},{\mathrm{\Sigma }}_Y)$, and $(\mathcal{A},{\mathrm{\Sigma }}_A)$ be nonempty measurable spaces, let $P$ be a probability measure on $\mathcal{X}\times \mathcal{Y}$, let $\mathcal{H}$ be a nonempty class of measurable predictors $h:\mathcal{X}\to \mathcal{A}$, and let $\mathrm{\ell }:\mathcal{A}\times \mathcal{Y}\to [0,1]$ be measurable. For $h\in \mathcal{H}$, define $g_h(x,y):=\mathrm{\ell }(h(x),y)$, $\mathcal{G}:=\{g_h:h\in \mathcal{H}\}$, and $\bar{\mathcal{G}}:=\{1-g:g\in \mathcal{G}\}$. Assume the sample, independent-copy, and sign suprema over $\mathcal{G}$ and $\bar{\mathcal{G}}$ required by the uniform generalization theorem are measurable in their respective product sigma algebras. Let $Z_i=(X_i,Y_i)$ be mutually independent with common law $P$, with $m\ge 1$, and write

$R_P(h):=P{g}_h,{\widehat{R}}_S(h):=P_m{g}_h\mathrm{.}$

Suppose a measurable prediction rule ${\widehat{h}}_{\eta }$ exists such that ${\widehat{h}}_{\eta }(S)\in \mathcal{H}$ for every sample $S$ and each samplewise output is an $\eta$-approximate empirical risk minimizer, meaning ${\widehat{R}}_S({\widehat{h}}_{\eta }(S))\le {\inf }_{h\in \mathcal{H}}{\widehat{R}}_S(h)+\eta$ for a fixed finite $\eta \ge 0$. Assume $S\mapsto R_P({\widehat{h}}_{\eta }(S))$ is measurable. For $\delta \in (0,1)$, with independent uniform signs ${\sigma }_i$, ${\widehat{\mathfrak{R}}}_S(\mathcal{G})={\mathbb{E}}_{\sigma }{\sup }_{g\in \mathcal{G}}{m}^{-1}{\sum }_i{\sigma }_{i}g(Z_i)$ and ${\mathfrak{R}}_m(\mathcal{G})={\mathbb{E}}_S{\widehat{\mathfrak{R}}}_S(\mathcal{G})$, each of the following excess-risk bounds holds with probability at least $1-\delta$:

$R_P({\widehat{h}}_{\eta }(S))-{\inf }_{h\in \mathcal{H}}{R}_P(h)\le 4{\mathfrak{R}}_m(\mathcal{G})+2\sqrt{\frac{\log (2\mathrm{/}\delta )}{2m}}+\eta ,$

$R_P({\widehat{h}}_{\eta }(S))-{\inf }_{h\in \mathcal{H}}{R}_P(h)\le 4{\widehat{\mathfrak{R}}}_S(\mathcal{G})+6\sqrt{\frac{\log (4\mathrm{/}\delta )}{2m}}+\eta \mathrm{.}$

The two displayed bounds are separate probability guarantees. This corollary asserts no existence of an empirical-risk-minimizing measurable rule for a general class.

Supervised prediction problems: supplies measurable observation, prediction, and loss spaces with a joint law.

Identical distribution and IID families: IID means the sample coordinates are mutually independent and have the common law $P$.

Population and empirical risk: defines population risk as expected loss and empirical risk as its sample average.

Empirical risk minimizers: defines exact and $\eta$-approximate ERM rules and does not assert a selector exists for every class.

Population and empirical risks are measurable: proves measurability of induced losses and fixed-predictor risks.

Rademacher uniform generalization bounds: supplies the two separate two-sided uniform deviation bounds under AC.

One-sided Rademacher complexity: defines the one-sided empirical and expected complexities used in the conclusion.

The Axiom of Choice: AC is carried because the concentration-based supplier assumes it.

The natural logarithm as the inverse of the exponential function: defines the logarithm appearing in the confidence terms.

Mohri et al., Theorem 3.3 and complete proof, Chapter 3 §3.1: supplies the uniform Rademacher deviations; the two-deviation ERM comparison is proved locally.

Bartlett and Mendelson, Theorem 8 and complete proof, printed pp. 466–467: gives an independent uniform risk-bound argument in a different normalization.