VC Bounds on the Cardinality of Nearly Orthogonal Function Classes

We bound the number of nearly orthogonal vectors with fixed VC-dimension over {−1,1}n. Our bounds are of interest in machine learning and empirical process theory and improve previous bounds by Haussler. The bounds are based on a simple projection argument and they generalize to other product spaces. Along the way we derive tight bounds on the sum of binomial coefficients in terms of the entropy function.