Bracketing entropy and VC-dimension
Yu. V. Malykhin · Mathematical Notes · 2012
We study the relationship between two characteristics of functional classes, pseudodimension and bracketing entropy. (Pseudodimension is a generalization of VC-dimension to classes of functions. Bracket entropy characterizes the L 1-error of one-sided approximation of a class by finite sets.) It is shown that classes of continuous functions with finite pseudodimension possess a finite bracketing ɛ-entropy for any ɛ > 0. We establish a general result concerning the relationship between the VC-dimension of classes of sets and their bracketing entropy.