定理を述べるために、まず関数族に対して、growth functionとVC次元を定義する。 $X$を集合、$\mathcal{H}$を$X$から${ -1, 1 }$への写像の部分集合とする。 $X$の有限部分集合の$S \subset X$, $|S| = m$に対して、$\mathcal{H}$の$S$への制限 $\mathcal{H}\mid_{S}$を次の様に定義する。

$$\begin{align*} \mathcal{H}\left|_{S}\right. = \{(f(x))_{x\in S} \mid f \in \mathcal{H}\} \end{align*}$$

さらに、$\mathcal{H}$のgrowth function $g_{\mathcal{H}} : \mathbb{N}\to \mathbb{N}$を次で定義する。

$$\begin{align*} g_{\mathcal{H}}(m) = \max_{S\subset X, |S|=m} \left|\mathcal{H}\left|_{S}\right.\right| \end{align*}$$

すると、自明な不等式として、$g_{\mathcal{H}}(m) \leq 2^{m}$が成立する。 また、ある$m$で等号が成立していたら、任意の$m’ \leq m$でも等号は成立している （等号を達成する$m$点集合$S$に対して、$S$の$m’$点部分集合を取れば良い）。

この不等式で等式が成立する最大の$m$を$\mathcal{H}$のVC次元と定義する （任意の$m$で等号が成立する場合には、VC次元は無限大と定義する）。

$$\begin{align*} \text{VC-}\mathrm{dim}(\mathcal{H}) = \max \{ m \mid g_{\mathcal{H}}(m) = 2^{m}\} \end{align*}$$

以上を準備として、Sauerの定理は次の通り

$$\begin{align*} g_{\mathcal{H}}(m) \leq \sum_{i=0}^{\text{VC-}\mathrm{dim}(\mathcal{H})} \binom{m}{i} \end{align*}$$

出典

• Understanding Machine Learning, Shai Shalev-Shwartzの6.5.1章

会社では著者名を取ってSSS本と呼んでいる。