On the complexity of constrained VC-classes

AbstractSauer's lemma is extended to classes HN of binary-valued functions h on [n]={1,…,n} which have a margin less than or equal to N on all x∈[n] with h(x)=1, where the margin μh(x) of h at x∈[n] is defined as the largest non-negative integer a such that h is constant on the interval Ia(x)=[x-a,x+a]⊆[n]. Estimates are obtained for the cardinality of classes of binary-valued functions with a margin of at least N on a positive sample S⊆[n]