On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities I: The Growth Function DichotomyResearch Paper
Statistical learning theory asks when the empirical frequencies of a whole class of events converge to their probabilities uniformly over the class. Vapnik and Chervonenkis answered this question in 1971 (Theory Probab. Appl. 16 (1971) 264–280) by attaching to every class of sets a single combinatorial quantity, the growth function, and bounding the…