# VC dimension

> Source: https://aiwiki.ai/wiki/vc_dimension
> Updated: 2026-07-24
> Fact-checked: 2026-07-24
> Categories: Machine Learning, Mathematics, Statistics
> License: CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) - attribute to "AI Wiki (aiwiki.ai)"
> Cite as: AI Wiki. "VC dimension." aiwiki.ai, 24 Jul 2026. https://aiwiki.ai/wiki/vc_dimension
> From AI Wiki (https://aiwiki.ai), the free encyclopedia of artificial intelligence. Reuse freely with attribution.

The Vapnik-Chervonenkis dimension, almost always shortened to VC dimension, measures the capacity of a class of [binary classifiers](https://aiwiki.ai/wiki/binary_classification) by asking how many points the class can label in every possible way. A finite set of points is said to be shattered by a hypothesis class if, for each of the 2^k ways of assigning labels to those k points, some hypothesis in the class produces exactly that assignment. The VC dimension is the size of the largest shattered set, and it is infinite when sets of arbitrary size can be shattered [3]. Vladimir Vapnik and Alexey Chervonenkis introduced the quantity in a 1971 paper on the uniform convergence of relative frequencies of events to their probabilities, which remains the founding reference for [statistical learning theory](https://aiwiki.ai/wiki/statistical_learning_theory) [1].

What makes the definition more than a combinatorial curiosity is that it settles exactly which classes can be learned from finitely many examples. A class of binary classifiers is learnable in the probably approximately correct (PAC) framework introduced by Leslie Valiant in 1984 [5] if and only if its VC dimension is finite, and the number of labeled examples required grows linearly in that dimension [2][3]. The result, usually called the fundamental theorem of statistical learning, ties together four ideas that look unrelated at first: uniform convergence of empirical error to true error, the success of [empirical risk minimization](https://aiwiki.ai/wiki/empirical_risk_minimization), PAC learnability, and a purely combinatorial count of labelings.

The theory was built for hypothesis classes of modest size, and it strains badly on modern [deep learning](https://aiwiki.ai/wiki/deep_learning). The VC dimension of a [ReLU](https://aiwiki.ai/wiki/relu) network scales with its parameter count [6], so the classical bound demands roughly as many training examples as the network has weights. Networks with far fewer examples than parameters still generalize, and the same networks will happily memorize randomly assigned labels, which means their capacity is more than enough to shatter the training set [7]. Explaining why they generalize anyway is an open problem, and VC dimension is the measure that most clearly fails to answer it.

## Shattering and the formal definition

Let H be a class of functions from a domain X to {0,1}. The restriction of H to a finite set C = {c1, ..., cm} is the set of label vectors that hypotheses in H induce on C. H shatters C when that restriction is all of {0,1}^m, that is, when every one of the 2^m labelings is achievable. The VC dimension of H, written VCdim(H), is the largest size of a set that H shatters [3].

Proving that VCdim(H) = d therefore takes two separate arguments: exhibit one set of d points that H shatters, and show that no set of d+1 points can be shattered. The asymmetry matters. Only one d-point set has to work, but every (d+1)-point set has to fail.

A closely related quantity is the growth function, sometimes called the shatter function. For a sample size m it counts the maximum number of distinct labelings H can induce on any m points. For sample sizes up to the VC dimension the growth function equals 2^m, since any subset of a shattered set is itself shattered. What Vapnik and Chervonenkis proved, and what makes the theory work, is that above the VC dimension it collapses to a polynomial [1][3].

Shalev-Shwartz and Ben-David give the intuition for why a large shattered set is bad news for a learner in one line: "If someone can explain every phenomenon, his explanations are worthless" [3]. If a class can produce any labeling of the training points, seeing their labels tells the learner nothing about the rest of the domain.

## Worked examples

The classic examples are worked out in most learning theory texts, and several of them are small enough to verify by hand.

| Hypothesis class | Domain | VC dimension |
| --- | --- | --- |
| Threshold functions, indicator of x < a | R | 1 |
| Intervals, indicator of x in (a,b) | R | 2 |
| Axis-aligned rectangles | R^2 | 4 |
| Axis-aligned rectangles | R^d | 2d |
| Halfspaces with a bias term, sign of (w.x + b) | R^d | d + 1 |
| Any finite class H | any | at most log2 of the size of H |
| Ceiling of sin(theta x), one real parameter | R | infinite |

The rectangle case is a good illustration of the two-sided proof. Four points arranged in a diamond can be labeled arbitrarily by axis-aligned rectangles, but for any five points one can pick a leftmost, a rightmost, a lowest and a highest point, and no rectangle containing those four can exclude the fifth [3].

The halfspace entry is what most people mean by "linear classifiers in R^d have VC dimension d+1". It covers the [perceptron](https://aiwiki.ai/wiki/perceptron) and any other classifier that splits the input space with a single [hyperplane](https://aiwiki.ai/wiki/hyperplane) [3]. An affine function in R^d can be rewritten as a homogeneous linear function in R^(d+1) by appending a constant 1 to every input vector [3], so restricting to hyperplanes through the origin costs exactly one dimension of capacity.

The last row is the important counterexample to the folk belief that VC dimension equals parameter count. The class of functions x mapped to the ceiling of sin(theta x), parameterized by a single real number theta, has infinite VC dimension and is therefore not PAC learnable at all [3]. Parameter counting is a decent heuristic for the classes people usually write down, but it is not a theorem.

## The Sauer-Shelah lemma

The bridge from the combinatorial definition to a statistical guarantee is the Sauer-Shelah lemma, also called the Sauer-Shelah-Perles lemma. If VCdim(H) is at most d, then for every sample size m the growth function is bounded by the sum of the binomial coefficients (m choose i) for i from 0 to d, and once m exceeds d+1 this is at most (em/d)^d [3].

That is the whole trick. A class with finite VC dimension may contain infinitely many hypotheses, but on any m sample points it behaves like a finite class of polynomial size in m. A union bound over that effectively finite set, combined with a concentration inequality, gives uniform convergence of empirical error to true error, and uniform convergence is what makes empirical risk minimization safe [1][3].

The lemma was proved several times independently, which is why it carries several names. Norbert Sauer published it in 1972 in response to a problem posed by Paul Erdos. Saharon Shelah, working with Micha Perles, proved it the same year as a lemma for Shelah's theory of stable models. Perles, by a story that Gil Kalai relates, later proved it a second time in an ergodic theory context, having forgotten that he had already done so. Vapnik and Chervonenkis proved it in the statistical setting [3].

## Generalization bounds and sample complexity

The fundamental theorem of statistical learning states that for binary classification under 0-1 loss, six conditions on a hypothesis class H are equivalent: H has the uniform convergence property, any empirical risk minimizer is a successful agnostic PAC learner, H is agnostic PAC learnable, H is PAC learnable, any empirical risk minimizer is a successful PAC learner, and H has finite VC dimension [3]. The equivalence is what licenses treating VC dimension as the definition of capacity rather than one measure among many.

The quantitative version pins down sample complexity. Writing d for the VC dimension, epsilon for the target error and delta for the failure probability, there are absolute constants C1 and C2 such that the number of examples m needed satisfies [3]:

| Setting | Lower bound | Upper bound |
| --- | --- | --- |
| Uniform convergence | C1 (d + log(1/delta)) / epsilon^2 | C2 (d + log(1/delta)) / epsilon^2 |
| Agnostic PAC learning | C1 (d + log(1/delta)) / epsilon^2 | C2 (d + log(1/delta)) / epsilon^2 |
| Realizable PAC learning | C1 (d + log(1/delta)) / epsilon | C2 (d log(1/epsilon) + log(1/delta)) / epsilon |

The gap in the realizable row is a logarithmic factor in 1/epsilon, and it stayed open for decades. The classical upper bound with the extra log factor is due to Vapnik and to Blumer, Ehrenfeucht, Haussler and Warmuth, who also proved that any algorithm returning a hypothesis consistent with the sample achieves it [4]. The matching linear-in-d lower bound came from Ehrenfeucht, Haussler, Kearns and Valiant [4]. Steve Hanneke closed the gap in 2016 with a learner that takes a majority vote over classifiers trained on recursively constructed overlapping subsets of the data, giving an upper bound that matches the lower bound up to constants [4].

None of this is a statement about a particular trained model. The bounds are distribution free and hold uniformly over every hypothesis in the class, which is exactly why they are both powerful and, for large classes, weak.

## Structural risk minimization

VC dimension gives a principled way to trade fit against complexity. Vapnik and Chervonenkis set this out as structural risk minimization (SRM) in their 1974 book Theory of Pattern Recognition, published in Russian by Nauka in Moscow [3]. The class H is written as a countable union of nested subclasses H1, H2, ..., each with its own uniform convergence rate, and a weight function assigns each subclass a prior preference with weights summing to at most one. The SRM rule then returns the hypothesis minimizing the sum of empirical risk and the confidence term for the subclass it belongs to, rather than empirical risk alone [3].

The practical effect is automatic model selection. Fitting polynomials to a small data set, plain empirical risk minimization over degree-10 polynomials will [overfit](https://aiwiki.ai/wiki/overfitting), and restricting to degree 2 will underfit. SRM over the union of all polynomial classes picks the degree whose combined empirical risk and complexity penalty is smallest [3]. The same bound-minimization idea, with description length in place of VC dimension, yields the minimum description length principle and a formal version of Occam's razor [3]. Norm based [regularization](https://aiwiki.ai/wiki/regularization) can be read the same way: penalizing the squared norm of a weight vector amounts to an approximate SRM over the nested classes of vectors whose squared norm is at most 1, 2, 3 and so on [3].

[Support vector machines](https://aiwiki.ai/wiki/support_vector_machine_svm), introduced by Boser, Guyon and Vapnik in 1992 and by Corinna Cortes and Vapnik in 1995 [16][3], came out of the same research program. The sample complexity of the hard margin SVM depends on the ratio between the radius of the data and the margin, and not on the dimension of the space, so capacity is controlled without counting parameters [3].

Outside of learning, VC dimension turns up in computational geometry through epsilon-nets. Haussler and Welzl showed in 1987 that a range space of bounded VC dimension admits a small random sample hitting every sufficiently heavy range, which underpins a family of geometric approximation algorithms [15].

## VC dimension of neural networks

Bounds for [neural networks](https://aiwiki.ai/wiki/neural_network) depend sharply on the [activation function](https://aiwiki.ai/wiki/activation_function). Writing W for the number of parameters, L for the number of layers and U for the number of nonlinear units, the tightest known results are summarized by Bartlett, Harvey, Liaw and Mehrabian [6]:

| Activation type | VC dimension | Attribution |
| --- | --- | --- |
| Piecewise constant (threshold units) | Theta(W log W) | Upper bound from Cover (1968) and Baum and Haussler (1989); lower bound from Maass (1994) |
| Piecewise linear (ReLU) | between c W L log(W/L) and C W L log W | Bartlett, Harvey, Liaw and Mehrabian (2019) |
| Piecewise polynomial | O(W L^2 + W L log W), also O(W U) | Bartlett et al. (1998) and the 2019 paper |

Two things follow. Depth genuinely increases capacity for ReLU networks, and the dependence is linear in L, whereas for threshold networks depth does not enter the bound at all [6]. And because the bounds scale with W, the classical guarantee for a network with hundreds of millions of weights only starts to say something once the training set is of comparable size. The ImageNet training set used in the experiments described below holds roughly a million images [7], two orders of magnitude below that.

## Why it under-explains deep learning

The clearest demonstration came from Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht and [Oriol Vinyals](https://aiwiki.ai/wiki/oriol_vinyals) at [ICLR](https://aiwiki.ai/wiki/iclr) 2017 [7], later revised for Communications of the ACM [8]. They replaced the true labels in [CIFAR-10](https://aiwiki.ai/wiki/cifar_10) with uniformly random ones and retrained standard architectures without changing hyperparameters. The networks fit the noise.

| Model on CIFAR-10 | Parameters | Train accuracy on random labels | Test accuracy |
| --- | --- | --- | --- |
| Inception (small) | 1,649,402 | 100.0% | 9.78% |
| AlexNet (small) | 1,387,786 | 99.82% | 9.86% |
| MLP, 3 hidden layers of 512 | 1,735,178 | 100.0% | 10.48% |
| MLP, 1 hidden layer of 512 | 1,209,866 | 99.34% | 10.61% |

Test accuracy sits at chance, which is 10% on a ten-class problem, exactly as it must when labels carry no signal. On [ImageNet](https://aiwiki.ai/wiki/imagenet) the same treatment reached 95.20% top-1 accuracy on the randomly labeled training set, a million labels drawn from 1,000 categories, short of a perfect fit but not by much [7]. The networks also fit images whose pixels had been replaced by Gaussian noise.

Explicit regularization did not stop any of this. The methods examined were [data augmentation](https://aiwiki.ai/wiki/data_augmentation), [weight decay](https://aiwiki.ai/wiki/weight_decay) and [dropout](https://aiwiki.ai/wiki/dropout_regularization). On CIFAR-10, switching off random cropping and weight decay cost the Inception model about three points of test accuracy on true labels, from 89.05% to 85.75%, and with weight decay left on both Inception and the MLPs still fit the random training set perfectly, though AlexNet with weight decay failed to converge on random labels. The authors concluded that explicit regularization is "neither necessary nor by itself sufficient for controlling generalization error" [7].

The consequence for capacity measures is direct. If a class shatters the training sample, its empirical Rademacher complexity is essentially 1, and the corresponding bound is vacuous. Zhang and colleagues state that the same reasoning applies to VC dimension and to its continuous analog the fat-shattering dimension, unless the network is further restricted [7].

The structural reason is that VC dimension is a property of the hypothesis class alone. It says nothing about which hypothesis the optimizer actually returns, nothing about the data distribution, and nothing about the [inductive bias](https://aiwiki.ai/wiki/inductive_bias) that stochastic gradient descent brings. Any bound that holds uniformly over a class rich enough to memorize the training set has to be weak. Vaishnavh Nagarajan and Zico Kolter pushed this further in 2019, exhibiting settings where uniform convergence bounds actually increase with training set size and arguing that uniform convergence may be unable to explain generalization in overparameterized models even when restricted to the classifiers the algorithm produces [9].

Related lines of work reached the same conclusion from the statistical side. Mikhail Belkin, Daniel Hsu, Siyuan Ma and Soumik Mandal described the [double descent](https://aiwiki.ai/wiki/double_descent) curve, in which test error falls again once capacity passes the interpolation threshold, extending the classical [bias-variance tradeoff](https://aiwiki.ai/wiki/bias_variance_tradeoff) rather than obeying it [10]. Peter Bartlett, Philip Long, Gabor Lugosi and Alexander Tsigler characterized when a perfect fit to noisy data is compatible with accurate prediction in linear regression, the phenomenon known as benign overfitting, and showed that overparameterization is essential for it rather than an obstacle: the number of directions in parameter space that do not matter for prediction has to greatly exceed the sample size [11].

The upshot is not that VC dimension is wrong. Its theorems are still true, and its bounds are tight in the worst case over distributions. It is that the worst case is the wrong regime for describing what a trained network does on natural data.

## Current research

VC dimension remains an active subject in learning theory and combinatorics, and it has been extended to architectures that did not exist when the theory was written.

Chenxiao Yang, Nathan Srebro and Zhiyuan Li characterized the VC dimension of [transformers](https://aiwiki.ai/wiki/transformers) in 2026, proving an upper bound of O(L W log(T W)) and a nearly matching lower bound of Omega(L W log(T W / L)) for a depth-L transformer with W parameters mapping an input sequence of length T to a single output. They also derived sample complexity for [chain-of-thought](https://aiwiki.ai/wiki/chain_of_thought) learning: teacher forcing, meaning selecting a predictor consistent with the entire chain on the training data, learns with O(L W log((T + T') W)) examples, while any learning rule that uses chain-of-thought data needs at least Omega(L W log((T + T') W / L)) examples, where T' is the number of autoregressive steps [12].

Two 2026 results tightened the classical theory itself. Jiahua Liu and Benchong Li resolved a longstanding open question by proving that the no-clash teaching dimension, a complexity measure for collusion-free teaching, is bounded above by VC dimension for any finite concept class [13]. Steve Hanneke, Qinglin Meng, Shay Moran and Amirreza Shaeiri established a sharp Sauer inequality for multiclass and list prediction over k-ary alphabets, replacing the Natarajan-dimension-based bound with one stated in terms of the Daniely-Shalev-Shwartz dimension that is tight for every alphabet size and list size [14].

## Origins and naming

The name entered the computational learning theory literature through the 1980s work that connected the 1971 results to Valiant's PAC model, most visibly the 1989 Journal of the ACM paper by Anselm Blumer, Andrzej Ehrenfeucht, David Haussler and Manfred Warmuth whose title carries the term [2]. Chervonenkis worked simultaneously for the Russian Academy of Sciences and for Royal Holloway, University of London. He got lost in Losiny Ostrov National Park on 22 September 2014 and was found dead of hypothermia near Mytishchi, a suburb of Moscow [17].

## See also

- [Statistical learning theory](https://aiwiki.ai/wiki/statistical_learning_theory)
- [Structural risk minimization](https://aiwiki.ai/wiki/structural_risk_minimization_srm)
- [Empirical risk minimization](https://aiwiki.ai/wiki/empirical_risk_minimization)
- [Generalization](https://aiwiki.ai/wiki/generalization)
- [Overfitting](https://aiwiki.ai/wiki/overfitting)
- [Model capacity](https://aiwiki.ai/wiki/model_capacity)

## References

1. Vapnik, V. N.; Chervonenkis, A. Ya. "On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities." Theory of Probability and Its Applications 16(2):264-280, 1971. https://epubs.siam.org/doi/10.1137/1116025
2. Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, M. K. "Learnability and the Vapnik-Chervonenkis Dimension." Journal of the ACM 36(4):929-965, 1989. https://doi.org/10.1145/76359.76371
3. Shalev-Shwartz, S.; Ben-David, S. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. Chapters 6, 7, 9, 13 and 15. https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf
4. Hanneke, S. "The Optimal Sample Complexity of PAC Learning." Journal of Machine Learning Research 17(38):1-15, 2016. https://www.jmlr.org/papers/volume17/15-389/15-389.pdf
5. Valiant, L. G. "A theory of the learnable." Communications of the ACM 27(11):1134-1142, 1984. https://doi.org/10.1145/1968.1972
6. Bartlett, P. L.; Harvey, N.; Liaw, C.; Mehrabian, A. "Nearly-tight VC-dimension and Pseudodimension Bounds for Piecewise Linear Neural Networks." Journal of Machine Learning Research 20(63):1-17, 2019. https://www.jmlr.org/papers/v20/17-612.html
7. Zhang, C.; Bengio, S.; Hardt, M.; Recht, B.; Vinyals, O. "Understanding deep learning requires rethinking generalization." ICLR 2017. arXiv:1611.03530. https://arxiv.org/abs/1611.03530
8. Zhang, C.; Bengio, S.; Hardt, M.; Recht, B.; Vinyals, O. "Understanding deep learning (still) requires rethinking generalization." Communications of the ACM 64(3):107-115, 2021. https://doi.org/10.1145/3446776
9. Nagarajan, V.; Kolter, J. Z. "Uniform convergence may be unable to explain generalization in deep learning." arXiv:1902.04742, 2019. https://arxiv.org/abs/1902.04742
10. Belkin, M.; Hsu, D.; Ma, S.; Mandal, S. "Reconciling modern machine learning practice and the bias-variance trade-off." Proceedings of the National Academy of Sciences 116, 2019. arXiv:1812.11118. https://arxiv.org/abs/1812.11118
11. Bartlett, P. L.; Long, P. M.; Lugosi, G.; Tsigler, A. "Benign overfitting in linear regression." Proceedings of the National Academy of Sciences 117, 2020. arXiv:1906.11300. https://arxiv.org/abs/1906.11300
12. Yang, C.; Srebro, N.; Li, Z. "Tight Sample Complexity of Transformers." arXiv:2606.09731, 2026. https://arxiv.org/abs/2606.09731
13. Liu, J.; Li, B. "The No-Clash Teaching Dimension is Bounded by VC Dimension." arXiv:2603.23561, 2026. https://arxiv.org/abs/2603.23561
14. Hanneke, S.; Meng, Q.; Moran, S.; Shaeiri, A. "An Optimal Sauer Lemma Over k-ary Alphabets." arXiv:2604.12952, 2026. https://arxiv.org/abs/2604.12952
15. Haussler, D.; Welzl, E. "Epsilon-nets and simplex range queries." Discrete and Computational Geometry 2:127-151, 1987. https://doi.org/10.1007/BF02187876
16. Cortes, C.; Vapnik, V. "Support-vector networks." Machine Learning 20(3):273-297, 1995. https://doi.org/10.1007/BF00994018
17. "Alexey Chervonenkis." Wikipedia. https://en.wikipedia.org/wiki/Alexey_Chervonenkis