A Constrained Version of Sauer’s Lemma
Joel Ratsaby · Birkhäuser Basel eBooks · 2004
We generalize Sauer’s Lemma to finite VC-dimension classesx of binary-valued functions on $$ \left[ n \right] = \left\{ {1, \ldots,n} \right\} $$ which have a margin of at least N on every element in a sample $$S \subseteq \left[ n \right] $$ of cardinality l, where the margin μh(x) of $$ h \in \mathcal{H} $$ on a point x ∈ [n] is defined as the largest non-negative integer a such that h is constant on the interval $$ I_a \left( x \right) = \left[ {x - a,x + a} \right]. $$