VC dimension, growth functions, and classification sample complexity

Let $(\mathcal{X},\mathrm{\Sigma })$ be a nonempty measurable space and let $H$ be a nonempty class of measurable functions $h:\mathcal{X}\to \{0,1\}$. For an integer $m\ge 0$ and an indexed tuple $\mathbf{x}=(x_1,\dots ,x_m)\in {\mathcal{X}}^m$, define its trace by

${\mathrm{tr}}_H(\mathbf{x}):=\{(h(x_1),\dots ,h(x_m)):h\in H\}\subseteq \{0,1{\}}^m\mathrm{.}$

The tuple $\mathbf{x}$ is shattered by $H$ if ${\mathrm{tr}}_H(\mathbf{x})=\{0,1{\}}^m$. Its coordinates are indexed: repeated instance points remain distinct coordinates, although their labels must agree for every $h\in H$. For $m=0$, $\mathbf{x}=()$ and $\{0,1{\}}^0=\{()\}$, so the empty tuple is shattered. The VC dimension of $H$ is

$\mathrm{VCdim}(H):=\sup \{m\in {\mathbb{N}}_0:\text{some }\mathbf{x}\in {\mathcal{X}}^m\text{ is shattered by }H\}\in {\mathbb{N}}_0\cup \{+\mathrm{\infty }\}\mathrm{.}$

Shattering and the Vapnik–Chervonenkis dimension of a set family: its current definition treats a family $\mathcal{F}\subseteq \mathcal{P}([n])$; on an indexed sample, identify each $h$ with the subset $\{i\in [m]:h(x_i)=1\}$, keeping repeated sample points at separate indices.

Mohri et al., Definition 3.10: VC dimension of a hypothesis class.

Bartlett and Mendelson, Theorem 6: sample-restricted VC dimension.

Let $(\mathcal{X},\mathrm{\Sigma })$ be a nonempty measurable space and let $H$ be a nonempty class of measurable binary functions on $\mathcal{X}$. For each integer $m\ge 0$, the growth function of $H$ is

${\mathrm{\Pi }}_H(m):={\sup }_{\mathbf{x}\in {\mathcal{X}}^m}\mathrm{\mid }{\mathrm{tr}}_H(\mathbf{x})\mathrm{\mid }\mathrm{.}$

The supremum is a maximum because each trace size is an integer between $1$ and $2^m$ and ${\mathcal{X}}^m$ is nonempty. In particular, ${\mathrm{\Pi }}_H(0)=1$. A finite indexed tuple is shattered exactly when its trace has size $2^m$, so $\mathrm{VCdim}(H)=\sup \{m\in {\mathbb{N}}_0:{\mathrm{\Pi }}_H(m)=2^m\}$.

Indexed shattering and VC dimension of a binary class: ${\mathrm{tr}}_H(\mathbf{x})$ is the set of binary label vectors on the indexed tuple $\mathbf{x}$, and shattering means that this trace is all of $\{0,1{\}}^m$.

Mohri et al., Definition 3.6 and equation (3.19): the growth function counts distinct dichotomies on a sample.

Bartlett and Mendelson, Theorem 6: restriction of a class to a fixed sample and its empirical VC dimension.

Let $(\mathcal{X},\mathrm{\Sigma })$ be a nonempty measurable space and let $H$ be a nonempty class of measurable binary functions on $\mathcal{X}$ with finite VC dimension $d$. Put $\mathcal{Z}=\mathcal{X}\times \{0,1\}$ with its product sigma-algebra and $G_H=\{g_h:h\in H\}$, where $g_h(x,y)=\mathbf{1}\{h(x)\mathrm{\ne }y\}$. For any integer $m\ge 1$ and any fixed sample $S=(z_1,\dots ,z_m)\in {\mathcal{Z}}^m$, let ${\sigma }_1,\dots ,{\sigma }_m$ be independent uniform signs and define

${\widehat{\mathfrak{R}}}_S(G_H):={\mathbb{E}}_{\sigma }{\sup }_{h\in H}\frac{1}{m}{\sum }_{i=1}^m{\sigma }_i{g}_h(z_i)\mathrm{.}$

Set $K_0:=3e^2\mathrm{/}(e-1)$, $K:=4K_0$, $A:=12eK+2$, and

$C_{\mathrm{V}\mathrm{C}}:=3\sqrt{8A}(\sqrt{\log A}+2\sqrt{\log 2})\mathrm{.}$

Then, for every such finite sample,

${\widehat{\mathfrak{R}}}_S(G_H)\le C_{\mathrm{V}\mathrm{C}}\sqrt{\frac{d+1}{m}}\mathrm{.}$

No countability or Axiom of Choice premise is used; the supremum over classifiers reduces to the finite set of loss traces on $S$.

Mohri et al., Theorems 3.3 and 3.7, Corollary 3.8, and the proof of Corollary 3.19: finite-sample Rademacher complexity and Massart's finite maximum bound.

Bartlett and Mendelson, Theorem 6: qualitative empirical VC-entropy control.

Let $(\mathcal{X},\mathrm{\Sigma })$ be a nonempty measurable space and let $H$ be a nonempty class of measurable functions $h:\mathcal{X}\to \{0,1\}$ with finite VC dimension $d$. For every integer $m\ge 0$,

${\mathrm{\Pi }}_H(m)\le {\sum }_{j=0}^d\left(\genfrac{}{}{0px}{}{m}{j}\right),$

where $\left(\genfrac{}{}{0px}{}{m}{j}\right)=0$ for $j>m$. Consequently, ${\mathrm{\Pi }}_H(m)=1$ when $d=0$; and when $1\le d\le m$,

${\mathrm{\Pi }}_H(m)\le {\left(\frac{em}{d}\right)}^d,$

where $e:=\exp (1)$.

Indexed shattering and VC dimension of a binary class: shattering uses indexed tuples and $\mathrm{VCdim}(H)$ is the largest shattered length.

Growth function of a binary hypothesis class: ${\mathrm{\Pi }}_H(m)$ is the largest number of distinct binary traces on an indexed $m$-tuple.

Sauer–Shelah: a family on $[n]$ of VC dimension at most $d$ has at most ${\sum }_{i=0}^d\left(\genfrac{}{}{0px}{}{n}{i}\right)$ members: a family in $\mathcal{P}([m])$ with VC dimension at most $d$ has at most ${\sum }_{j=0}^d\left(\genfrac{}{}{0px}{}{m}{j}\right)$ members.

Mohri et al., Theorem 3.17 and Corollary 3.18: Sauer’s trace bound and its $(em\mathrm{/}d{)}^d$ estimate.

Bartlett and Mendelson, Theorems 5–6: empirical VC dimension enters the classification complexity bound.

Let $(\mathcal{X},\mathrm{\Sigma })$ be a nonempty measurable space, let $H$ be a nonempty class of measurable functions $h:\mathcal{X}\to \{0,1\}$, put $\mathcal{Z}=\mathcal{X}\times \{0,1\}$ with its product sigma-algebra, and let $P$ be a probability law on $\mathcal{Z}$. For a fixed sample size $m\ge 1$, a risk-measurable learning rule under $P$ is a map $A:{\mathcal{Z}}^m\to H$ for which the real-valued maps $S\mapsto R_P(A(S))$ and $S\mapsto {\widehat{R}}_S(A(S))$ are measurable; if the class infimum is used, also require $S\mapsto {\inf }_{h\in H}{\widehat{R}}_S(h)$ to be measurable. The realizable condition is that some $h^{\ast }\in H$ has $R_P(h^{\ast })=0$. The rule is consistent on a sample when ${\widehat{R}}_S(A(S))=0$, an exact ERM when it attains ${\inf }_{h\in H}{\widehat{R}}_S(h)$, and an $\eta$-approximate ERM for finite $\eta \ge 0$ when ${\widehat{R}}_S(A(S))\le {\inf }_{h\in H}{\widehat{R}}_S(h)+\eta$.

In each PAC criterion below, require $A$ to be risk-measurable under every law $P$ quantified over in that criterion. For $0<ϵ,\delta <1$, $A$ is realizable $(ϵ,\delta )$-PAC on $H$ if for every law $P$ satisfying the realizable condition, ${\mathbb{P}}_{S\sim P^m}\{R_P(A(S))\le ϵ\}\ge 1-\delta$. It is agnostic $(ϵ,\delta )$-PAC if for every law $P$ on $\mathcal{Z}$, ${\mathbb{P}}_{S\sim P^m}\{R_P(A(S))-{\inf }_{h\in H}{R}_P(h)\le ϵ\}\ge 1-\delta$. These are probability criteria only; no existence, attainment, measurability of a selector beyond the stated risk maps, or computational-efficiency claim is implicit. When $H$ is finite and $A$ is measurable into the discrete space $H$, these probability formulas are the criteria in the finite-class definition.

Realizable and agnostic PAC learning: gives the same realizable and agnostic probability criteria when $H$ is finite and the learner takes values in that finite class.

Population and empirical risk: population risk is the expected nonnegative loss and empirical risk is its sample average; here the loss is binary zero-one loss.

Mohri et al., Chapter 2: finite-class PAC criteria and risk notation.

Shalev-Shwartz and Ben-David, Chapters 2–4: PAC learning and VC-dimension framework.

Let $(\mathcal{X},\mathrm{\Sigma })$ be a nonempty measurable space, let $H$ be a nonempty class of measurable binary functions on $\mathcal{X}$ with finite VC dimension $d$, put $\mathcal{Z}=\mathcal{X}\times \{0,1\}$ with its product sigma-algebra, and let $P$ be a probability law on $\mathcal{Z}$. For $h\in H$, define $R_P(h):=P\{(x,y):h(x)\mathrm{\ne }y\}$ and ${\widehat{R}}_S(h):=m^{-1}{\sum }_{i=1}^m\mathbf{1}\{h(X_i)\mathrm{\ne }{Y}_i\}$ for an IID sample $S=((X_i,Y_i){)}_{i=1}^m$ of size $m\ge 1$ with law $P$. Assume every displayed supremum over $H$ and its binary loss class that appears below is measurable. For $0<\delta <1$, the following separate branches hold.

1. If $H$ is finite, then without an Axiom of Choice premise, with probability at least $1-\delta$, ${\sup }_{h\in H}\mathrm{\mid }{R}_P(h)-{\widehat{R}}_S(h)\mathrm{\mid }\le \sqrt{\frac{\log \mathrm{\mid }H\mathrm{\mid }+\log (2\mathrm{/}\delta )}{2m}}\mathrm{.}$ In particular, if $d=0$, then $H$ is a singleton and this gives ${\sup }_{h\in H}\mathrm{\mid }{R}_P(h)-{\widehat{R}}_S(h)\mathrm{\mid }\le \sqrt{\log (2\mathrm{/}\delta )\mathrm{/}(2m)}$.

2. If $1\le d\le m$ and the Axiom of Choice (AC) is assumed, then with probability at least $1-\delta$, simultaneously for every $h\in H$, $R_P(h)\le {\widehat{R}}_S(h)+\sqrt{\frac{2d\log (em\mathrm{/}d)}{m}}+\sqrt{\frac{\log (1\mathrm{/}\delta )}{2m}}\mathrm{.}$

Here $\log$ is the natural logarithm and $e=\exp (1)$.

Mohri et al., Theorem 3.3, Theorem 3.5, Theorem 3.7, Corollary 3.8, and Corollary 3.19: one-sided Rademacher generalization, the finite-sample maximum bound, and the stated VC display.

Bartlett and Mendelson, Theorem 5 and Appendix B: an independent classification-risk bound in their $2\mathrm{/}m$ absolute-supremum normalization.

Let $(\mathcal{X},\mathrm{\Sigma })$ be a nonempty measurable space, let $H$ be a nonempty class of measurable binary classifiers with finite VC dimension $d$, and put $\mathcal{Z}:=\mathcal{X}\times \{0,1\}$ with sigma-algebra ${\mathrm{\Sigma }}_{\mathcal{Z}}:=\mathrm{\Sigma }\otimes \mathcal{P}(\{0,1\})$. Let $P$ be a probability law on $\mathcal{Z}$, and let $S=(Z_1,\dots ,Z_m)$ consist of $m\ge 1$ IID observations with law $P$. For $h\in H$, put $g_h(x,y):=\mathbf{1}\{h(x)\mathrm{\ne }y\}$, ${\mathcal{G}}_H:=\{g_h:h\in H\}$, and ${\bar{\mathcal{G}}}_H:=\{1-g:g\in {\mathcal{G}}_H\}$. Define $R_P(h):=P\{h(X)\mathrm{\ne }Y\}$ and ${\widehat{R}}_S(h):=m^{-1}{\sum }_{i=1}^m{g}_h(Z_i)$. For measurable $g:\mathcal{Z}\to [0,1]$, write $Pg:=\int gdP$ and $P_{m}g(S):=m^{-1}{\sum }_{i=1}^{m}g(Z_i)$. Let $S^{\mathrm{\prime }}=(Z_1^{\mathrm{\prime }},\dots ,Z_m^{\mathrm{\prime }})$ be an independent sample with law $P^m$, and write $P_m^{\mathrm{\prime }}g:=P_{m}g(S^{\mathrm{\prime }})$.

Assume the following maps are measurable:

1. $S\mapsto {\sup }_{g\in {\mathcal{G}}_H}(Pg-P_{m}g(S))$ and $S\mapsto {\sup }_{\bar{g}\in {\bar{\mathcal{G}}}_H}(P\bar{g}-P_m\bar{g}(S))$ on $({\mathcal{Z}}^m,{\mathrm{\Sigma }}_{\mathcal{Z}}^{\otimes m})$;
2. $(S,S^{\mathrm{\prime }})\mapsto {\sup }_{g\in {\mathcal{G}}_H}(P_m^{\mathrm{\prime }}g-P_{m}g(S))$ and $(S,S^{\mathrm{\prime }})\mapsto {\sup }_{\bar{g}\in {\bar{\mathcal{G}}}_H}(P_m^{\mathrm{\prime }}\bar{g}-P_m\bar{g}(S))$ on $({\mathcal{Z}}^m\times {\mathcal{Z}}^m,{\mathrm{\Sigma }}_{\mathcal{Z}}^{\otimes m}\otimes {\mathrm{\Sigma }}_{\mathcal{Z}}^{\otimes m})$;
3. for every fixed $\sigma \in \{-1,+1{\}}^m$, the maps $(S,S^{\mathrm{\prime }})\mapsto {\sup }_{g\in {\mathcal{G}}_H}{m}^{-1}{\sum }_{i=1}^m{\sigma }_i(g(Z_i^{\mathrm{\prime }})-g(Z_i))$ and $(S,S^{\mathrm{\prime }})\mapsto {\sup }_{\bar{g}\in {\bar{\mathcal{G}}}_H}{m}^{-1}{\sum }_{i=1}^m{\sigma }_i(\bar{g}(Z_i^{\mathrm{\prime }})-\bar{g}(Z_i))$ on $({\mathcal{Z}}^m\times {\mathcal{Z}}^m,{\mathrm{\Sigma }}_{\mathcal{Z}}^{\otimes m}\otimes {\mathrm{\Sigma }}_{\mathcal{Z}}^{\otimes m})$;
4. for every fixed $\sigma \in \{-1,+1{\}}^m$, the maps $S\mapsto {\sup }_{g\in {\mathcal{G}}_H}{m}^{-1}{\sum }_{i=1}^m{\sigma }_{i}g(Z_i)$ and $S\mapsto {\sup }_{\bar{g}\in {\bar{\mathcal{G}}}_H}{m}^{-1}{\sum }_{i=1}^m{\sigma }_i\bar{g}(Z_i)$ on $({\mathcal{Z}}^m,{\mathrm{\Sigma }}_{\mathcal{Z}}^{\otimes m})$.

The first pair of maps gives the two one-sided deviation suprema and makes the absolute-deviation supremum in the conclusion measurable. Set $K_0:=3e^2\mathrm{/}(e-1)$, $K:=4K_0$, $A:=12eK+2$, and $C_{\mathrm{V}\mathrm{C}}:=3\sqrt{8A}(\sqrt{\log A}+2\sqrt{\log 2})$, where $e:=\exp (1)$ and $\log$ is the natural logarithm. If the Axiom of Choice (AC) is assumed, then for every $0<\delta <1$, with probability at least $1-\delta$,

${\sup }_{h\in H}\mathrm{\mid }{R}_P(h)-{\widehat{R}}_S(h)\mathrm{\mid }\le 2C_{\mathrm{V}\mathrm{C}}\sqrt{\frac{d+1}{m}}+\sqrt{\frac{\log (2\mathrm{/}\delta )}{2m}}\mathrm{.}$

This is a uniform absolute-deviation bound; it claims neither ERM existence nor a distribution-free lower bound.

Mohri et al., Theorem 3.3 and proof: one-sided generalization through ghost-sample symmetrization and bounded differences.

Bartlett and Mendelson, Theorem 5 and Appendix B: an independent Rademacher generalization proof in a different normalization.

Let $(\mathcal{X},\mathrm{\Sigma })$ be a nonempty measurable space, let $H$ be a nonempty class of measurable binary functions with finite VC dimension $d$, put $\mathcal{Z}=\mathcal{X}\times \{0,1\}$, and let $P$ be a probability law on $\mathcal{Z}$. Fix an integer $m\ge 1$ and a map $A:{\mathcal{Z}}^m\to H$ for which $S\mapsto R_P(A(S))$ and $S\mapsto {\widehat{R}}_S(A(S))$ are measurable, where $R_P(h):=P\{(x,y):h(x)\mathrm{\ne }y\},{\widehat{R}}_S(h):=\frac{1}{m}{\sum }_{i=1}^m\mathbf{1}\{h(X_i)\mathrm{\ne }{Y}_i\}\mathrm{.}$ Suppose $P$ is realizable by $H$ and $A$ is consistent $P^m$-almost surely. For $0<ϵ<1$, assume the events $E_{m,ϵ}:=\{S\in {\mathcal{Z}}^m:\mathrm{\exists }h\in H,R_P(h)>ϵ,{\widehat{R}}_S(h)=0\}$ and $B_{m,ϵ}:=\{(S,S^{\mathrm{\prime }})\in {\mathcal{Z}}^m\times {\mathcal{Z}}^m:\mathrm{\exists }h\in H,R_P(h)>ϵ,{\widehat{R}}_S(h)=0,{\widehat{R}}_{S^{\mathrm{\prime }}}(h)\ge ϵ\mathrm{/}2\}$ are measurable in their respective product sigma-algebras; this holds when $H$ is countable. For $0<ϵ,\delta <1$ and $S\sim P^m$, if $d=0$ then $R_P(A(S))=0$ almost surely for every such rule. If $d\ge 1$ and $m\ge \frac{64}{ϵ}[d\log \text{\hspace{0.17em}⁣}\left(\frac{64e}{ϵ}\right)+\log \text{\hspace{0.17em}⁣}\left(\frac{4}{\delta }\right)],$ where $\log$ is natural and $e=\exp (1)$, then $\mathbb{P}\{R_P(A(S))\le ϵ\}\ge 1-\delta$. This is a conditional upper bound for consistent risk-measurable learners; it asserts no existence or computational-efficiency result.