Why should a model that fits training data also work on new data? Statistical learning theory gives conditions under which that is true, and the VC dimension is one of its central tools.
The generalization gap
The gap between training error and true error is the generalization gap. Theory aims to bound it using the size of the training set and the complexity of the hypothesis class.
Shattering and VC dimension
A set of points is shattered by a hypothesis class if the class can realize every possible labeling of those points. The VC dimension is the size of the largest set that can be shattered. Linear classifiers in the plane have VC dimension 3: they can shatter some sets of three points but no set of four.
What the bound says
For a class with VC dimension d and n training samples, standard bounds show that the generalization gap shrinks roughly like √(d/n), up to logarithmic factors and a confidence term. More complex classes need more data.
Limits of the classical picture
- The bounds are often loose for modern neural networks, which have enormous capacity yet still generalize.
- Other tools, such as Rademacher complexity and norm-based bounds, give sharper explanations in many settings.
Practical lessons
Complexity must be controlled, whether by limiting model size, adding regularization, or collecting more data. Theory also explains why validation sets are necessary: training error alone is an optimistic estimate.
Continue with the book
Explore the full treatment, worked examples, and exercises in Mathematics for AI and Machine Learning.
Adapted from Mathematics for AI and Machine Learning, published by Choral Software. Article text and original examples © 2026 Choral Software. All rights reserved.