Vapnik-Chervonenkis dimension

The Vapnik-Chervonenkis (VC) dimension is a measure of the capacity of a statistical classification algorithm, defined as the cardinality of the largest set of points that the algorithm can shatter. Introduced by Vladimir Vapnik and Alexey Chervonenkis in 1971, the VC dimension provides a fundamental bound on the generalization performance of learning models: a finite VC dimension is necessary and sufficient for PAC learnability. The concept reveals that learning is not merely about fitting data but about controlling the richness of the hypothesis class — a bridge between computational learning theory and statistical learning theory that shows generalization is a property of model architecture, not just training procedure.

The VC dimension of simple hypothesis classes can be surprisingly large. A single linear classifier in d dimensions has VC dimension d+1, while a neural network with sufficient depth can have VC dimension exponential in the number of parameters. This explosive capacity explains why overparameterized models can memorize training data yet still generalize: the effective VC dimension is not the same as the nominal one, and understanding this gap requires tools from Rademacher complexity and uniform convergence theory that go beyond the classical VC framework.