Empirical-Process Complexity

Let $(\mathcal{X},\mathcal{A},P)$ be a probability space, let $n\ge 1$ be an integer, and let $Z_1,\dots ,Z_n$ be IID random elements with law $P$. For a class $\mathcal{F}$ of measurable, integrable real-valued functions on $\mathcal{X}$, write

$Pf:=\int fdP,P_{n}f:=\frac{1}{n}{\sum }_{i=1}^{n}f(Z_i),{\mathbb{G}}_n(f):=\sqrt{n}(P_{n}f-Pf)\mathrm{.}$

The map $f\mapsto P_{n}f-Pf$ is the centered empirical process, and ${\mathbb{G}}_n$ is its $\sqrt{n}$-scaled version. More generally, for independent processes $X_1(t),\dots ,X_n(t)$ whose marginal expectations are finite for each index $t\in T$, the centered process sum is

$S_n(t):={\sum }_{i=1}^n(X_i(t)-\mathbb{E}{X}_i(t)),t\in T\mathrm{.}$

On an auxiliary probability-space extension, let ${\sigma }_1,\dots ,{\sigma }_n$ be independent signs, each taking $+1$ and $-1$ with probability $1\mathrm{/}2$, independent of the observations. The empirical Rademacher process is

$R_n(f):={\sum }_{i=1}^n{\sigma }_{i}f(Z_i),f\in \mathcal{F}\mathrm{.}$

The centered Rademacher process ${\sum }_i{\sigma }_i(f(Z_i)-Pf)$ is a distinct process; no equality between it and $R_n$ is part of this definition.

For a countable class of measurable functions, each displayed supremum of measurable sample paths is measurable. For an uncountable class, ordinary probability or expectation is used only when a specified countable subclass has the same supremum almost surely for the process in question; this is the separable-version convention used here. Otherwise state results using outer probability

$P^{\ast }(A):=\inf \{P(B):A\subseteq B,B\in \mathcal{A}\}$

and, for a nonnegative possibly nonmeasurable random quantity $Y$, outer expectation

${\mathbb{E}}^{\ast }Y:=\inf \{\mathbb{E}U:U\text{ is measurable, nonnegative, and }U\ge Y\}\mathrm{.}$

In particular, measurability of every $f$ separately does not by itself make an uncountable supremum measurable.

Let $\mathcal{C}\subseteq \mathcal{P}(X)$ be a family of subsets of an arbitrary set $X$. For a finite $T\subseteq X$, its trace is

$\mathcal{C}{\mathrm{\mid }}_T:=\{C\cap T:C\in \mathcal{C}\}\mathrm{.}$

The family $\mathcal{C}$ shatters $T$ when $\mathcal{C}{\mathrm{\mid }}_T=\mathcal{P}(T)$. This extends the finite-ground-set trace convention of Shattering and the Vapnik–Chervonenkis dimension of a set family: any finite $T$ can be relabeled by $[\mathrm{\mid }T\mathrm{\mid }]$, and relabeling preserves all traces and their cardinalities.

For a nonempty class, its VC dimension $d(\mathcal{C})$ is the greatest size of a finite shattered set if those sizes are bounded, is $0$ if no singleton is shattered, and is $+\mathrm{\infty }$ if finite shattered sets have unbounded size. When the dimension is finite, its VC index is

$V(\mathcal{C}):=d(\mathcal{C})+1,$

equivalently the least positive integer $V$ such that no $V$-point subset is shattered. The empty class is assigned $V=0$ by convention and is treated separately in the entropy theorem.

Let $Y$ be a measurable real random variable on a probability space with $0\le Y\le 1$ almost surely. Then, for every $\lambda \in \mathbb{R}$,

$\mathbb{E}\exp \{\lambda (Y-\mathbb{E}Y)\}\le \exp ({\lambda }^2\mathrm{/}8)\mathrm{.}$

This proof uses only finite product and scalar integral arguments; it does not assume the Axiom of Choice.

Let $J\ge 1$ be an integer, put $u_j=-1+2j\mathrm{/}J$ for $j=0,\dots ,J$, and give the finite set $U_J=\{u_0,\dots ,u_J\}$ the probability weights

${\nu }_J(\{u_0\})={\nu }_J(\{u_J\})=\frac{1}{2J},{\nu }_J(\{u_j\})=\frac{1}{J}(1\le j<J)\mathrm{.}$

For all $-1\le a\le b\le 1$,

$\mid {\nu }_J([a,b))-\frac{b-a}{2}\mid \le \frac{1}{J}\mathrm{.}$

Let $r>0$. The map $t\mapsto t^r$ is strictly increasing on $[0,\mathrm{\infty })$. Consequently, if $(X,\mathcal{A})$ is a measurable space and $h:X\to [0,\mathrm{\infty })$ is measurable, then $h^r$ is measurable.

A pseudometric $d$ on a set $T$ is a nonnegative symmetric function $d:T\times T\to [0,\mathrm{\infty })$ with $d(t,t)=0$ and $d(s,t)\le d(s,u)+d(u,t)$; distinct points may have distance zero. For a nonempty subset $\mathcal{F}\subseteq T$ and $ϵ>0$, the covering number $N(ϵ,\mathcal{F},d)$ is the least finite $k$ for which there are centers $f_1,\dots ,f_k\in \mathcal{F}$ such that every $f\in \mathcal{F}$ satisfies $d(f,f_j)\le ϵ$ for some $j$. It is $+\mathrm{\infty }$ if no finite cover exists. Set $N(ϵ,\mathrm{\varnothing },d)=1$.

The packing number $D(ϵ,\mathcal{F},d)$ is the largest size of a finite subset $\{f_1,\dots ,f_k\}\subseteq \mathcal{F}$ whose distinct members have pairwise distance strictly greater than $ϵ$. If the sizes of such finite subsets are unbounded, put $D=+\mathrm{\infty }$; put $D(ϵ,\mathrm{\varnothing },d)=0$. These conventions give the radius comparison proved in Packing and covering numbers with explicit radius conventions ↗. The metric entropy is $H(ϵ,\mathcal{F},d):=\log N(ϵ,\mathcal{F},d)$ for nonempty classes, with $\log (+\mathrm{\infty })=+\mathrm{\infty }$.

For a probability measure $Q$ on $(\mathcal{X},\mathcal{A})$ and a measurable real function $g$, set $\mathrm{\parallel }g{\mathrm{\parallel }}_{Q,r}:=(\int \mathrm{\mid }g{\mathrm{\mid }}^{r}dQ{)}^{1\mathrm{/}r}$ for $1\le r<\mathrm{\infty }$ when the integral is finite, using the real-power convention, including $0^{1\mathrm{/}r}=0$, of Real powers for positive bases, with the zero-base positive-exponent convention. If the integral is $+\mathrm{\infty }$, define $\mathrm{\parallel }g{\mathrm{\parallel }}_{Q,r}:=+\mathrm{\infty }$ directly. The function $\mathrm{\mid }g\mathrm{\mid }$ is measurable by Arithmetic and lattice operations preserve measurability whenever they are defined, and Positive real powers preserve measurability makes $\mathrm{\mid }g{\mathrm{\mid }}^r$ measurable, so this nonnegative extended integral is well-defined. On a class of functions with finite such norms, $d_{Q,r}(f,g):=\mathrm{\parallel }f-g{\mathrm{\parallel }}_{Q,r}$ is a pseudometric: nonnegativity, symmetry, and zero diagonal follow from the absolute value, and the triangle inequality is Minkowski's inequality for integrals, including $p=\mathrm{\infty }$. Functions that agree $Q$-almost everywhere have distance zero. We write $N(ϵ,\mathcal{F},L^r(Q))$ for this covering number.

For measurable real endpoints $\mathrm{\ell }\le u$ $Q$-almost everywhere, the bracket $[\mathrm{\ell },u]$ is the set of measurable functions $f$ satisfying $\mathrm{\ell }\le f\le u$ $Q$-almost everywhere. Its $L^r(Q)$ width is $\mathrm{\parallel }u-\mathrm{\ell }{\mathrm{\parallel }}_{Q,r}$. The bracketing number $N_{[]}(ϵ,\mathcal{F},L^r(Q))$ is the least number of such brackets of width at most $ϵ$ that cover $\mathcal{F}$, or $+\mathrm{\infty }$ if no finite cover exists; for the empty class set it equal to $1$. Centers of metric covers are in $\mathcal{F}$; bracket endpoints need not be.

Let $m\ge 1$, let $S=(z_1,\dots ,z_m)$ be a fixed sample in a measurable space $\mathcal{X}$, and let $\mathcal{F}$ be a nonempty finite or countable class of measurable real functions such that the displayed supremum is finite and measurable on the finite sign space. Let ${\sigma }_1,\dots ,{\sigma }_m$ be independent uniform signs. The one-sided empirical Rademacher complexity is

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

There is no absolute value in this definition and $0$ need not belong to $\mathcal{F}$. It differs from the absolute-value complexity $m^{-1}{\mathbb{E}}_{\sigma }{\sup }_{f\in \mathcal{F}}\mathrm{\mid }{\sum }_i{\sigma }_{i}f(z_i)\mathrm{\mid }$.

This convention is the one used in One-sided coordinate Rademacher contraction.

Let $(\mathcal{X},\mathcal{A})$ be a measurable space and let $\mathcal{F}$ be a class of measurable real-valued functions on it. The subgraph of $f\in \mathcal{F}$ is

$C_f:=\{(x,t)\in \mathcal{X}\times \mathbb{R}:t<f(x)\}\mathrm{.}$

It is measurable in $\mathcal{A}\otimes \mathcal{B}(\mathbb{R})$: the coordinate lifts are measurable by The product sigma-algebra and its finite iterates, their difference is measurable by Arithmetic and lattice operations preserve measurability whenever they are defined, and its strict negative set is measurable by Threshold characterisations of real-valued and extended-real-valued measurability. The class $\mathcal{F}$ is a VC-subgraph class when the set family ${\mathcal{C}}_{\mathcal{F}}:=\{C_f:f\in \mathcal{F}\}$ has finite VC index as defined in Shattering, VC dimension, and first-unshattered index for set classes. For nonempty $\mathcal{F}$, write $d(\mathcal{F})$ for the greatest size of a finite shattered set (zero if none is shattered) and

$V(\mathcal{F}):=d(\mathcal{F})+1,$

equivalently the least positive integer $V$ for which no $V$-point set is shattered. If no finite such integer exists, set $V=+\mathrm{\infty }$. The empty class is treated separately and assigned index $V=0$ by convention. Thus for every nonempty finite-index class, the VC dimension is exactly $V-1$.

A measurable envelope of $\mathcal{F}$ is a nonnegative measurable function $F$ on $\mathcal{X}$ such that $\mathrm{\mid }f(x)\mathrm{\mid }\le F(x)$ for every $f\in \mathcal{F}$ and $x\in \mathcal{X}$. In an $L^r(Q)$ assertion, changing $F$ on a $Q$-null set does not change its norm or the distances in that assertion.

Let $n\ge 1$, let $Z_1,\dots ,Z_n$ be IID observations with law $P$, and let $\mathcal{F}$ be a finite nonempty class of measurable functions $f:\mathcal{X}\to [0,1]$. For every $ϵ>0$,

$P({\sup }_{f\in \mathcal{F}}\mathrm{\mid }{P}_{n}f-Pf\mathrm{\mid }\ge ϵ)\le 2\mathrm{\mid }\mathcal{F}\mathrm{\mid }{e}^{-2n{ϵ}^2}\mathrm{.}$

Here $P_{n}f=n^{-1}{\sum }_{i}f(Z_i)$ and $Pf=\int fdP$. The proof uses only scalar exponential moments and finite independence; it does not assume the Axiom of Choice.

Let $n\ge 1$, let $Z_1,\dots ,Z_n$ be IID observations with law $P$, and let $Z_1^{\mathrm{\prime }},\dots ,Z_n^{\mathrm{\prime }}$ be an independent IID copy. Let ${\sigma }_1,\dots ,{\sigma }_n$ be independent uniform signs, independent of both samples. Let $\mathcal{F}$ be a nonempty countable class of measurable $P$-integrable real functions. Assume the two suprema below are finite almost surely. If $\mathrm{\Phi }:[0,\mathrm{\infty })\to [0,\mathrm{\infty })$ is finite, convex, and nondecreasing, then

$\mathbb{E}\mathrm{\Phi }\text{\hspace{0.17em}⁣}\left({\sup }_{f\in \mathcal{F}}\mid {\sum }_{i=1}^n(f(Z_i)-Pf)\mid \right)\le \mathbb{E}\mathrm{\Phi }\text{\hspace{0.17em}⁣}\left(2{\sup }_{f\in \mathcal{F}}\mid {\sum }_{i=1}^n{\sigma }_{i}f(Z_i)\mid \right)\mathrm{.}$

The same statement holds for an uncountable class when a specified countable subclass gives the same three displayed suprema almost surely for the data, copy, and signs. This is an expectation inequality only; a tail form requires separate assumptions.

Let $\mathcal{F}$ be a nonempty subset of a pseudometric space $(T,d)$, with covering and packing numbers as in Covering, packing, bracketing numbers, and metric entropy. For every $ϵ>0$,

$N(ϵ,\mathcal{F},d)\le D(ϵ,\mathcal{F},d)\le N(ϵ\mathrm{/}2,\mathcal{F},d)\mathrm{.}$

The packing convention is strict separation $d(f,g)>ϵ$; covers use closed balls of radius at most $ϵ$ centered in $\mathcal{F}$.

Let $m\ge 1$, let $z_1,\dots ,z_m$ be fixed, and let $\mathcal{F}$ be a nonempty finite class of real-valued functions on their domain. For each $i$, let ${\mathrm{\Phi }}_i:\mathbb{R}\to \mathbb{R}$ satisfy $\mathrm{\mid }{\mathrm{\Phi }}_i(x)-{\mathrm{\Phi }}_i(y)\mathrm{\mid }\le L\mathrm{\mid }x-y\mathrm{\mid }$ for all $x,y\in \mathbb{R}$, with a common $L\ge 0$. Then

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

Here $S=(z_1,\dots ,z_m)$ and ${\widehat{\mathfrak{R}}}_S(\mathcal{F}):=m^{-1}{2}^{-m}{\sum }_{\sigma \in \{-1,1{\}}^m}{\sup }_{f\in \mathcal{F}}{\sum }_i{\sigma }_{i}f(z_i)$. Expectations over signs mean this uniform finite average; no measurability on the functions' domain is needed. For measurable classes on a measurable space this agrees with One-sided empirical Rademacher complexity. Equivalently, the unnormalized left expectation is at most $L$ times the unnormalized one-sided supremum on the right.

The same holds for a countable class when both suprema are finite for every sign vector. No condition ${\mathrm{\Phi }}_i(0)=0$ is required; additive constants cancel because the proof compares coordinate differences.