On the Complexity of Constrained VC-Classes

Sauer’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]