VC Dimension and PAC Learning

VC dimension measures the capacity of a hypothesis class: how many different labeling patterns it can produce on a set of points. A class shatters a set of n points if, for every one of the 2^n possible ways to assign positive or negative labels to those points, some hypothesis in the class reproduces that exact labeling. The VC dimension is the largest n for which some set of n points can be shattered. Linear classifiers in 2D can shatter any 3 points in general position but cannot shatter every configuration of 4 points, so their VC dimension is 3. PAC learning builds on this: it asks how many training examples are needed so that, with probability at least 1-delta, a learned hypothesis has error at most epsilon above the best hypothesis in the class. In an agnostic PAC setting, a representative worst-case sample-complexity bound has a term proportional to VC dimension divided by epsilon squared, along with confidence and sometimes logarithmic terms. Realizable PAC settings have different epsilon dependence, so the formula depends on the learning assumptions. This formalizes the tradeoff between model flexibility and data requirements: a class that can represent almost any labeling needs much more data before its empirical performance reliably predicts its true performance. A common misconception is that VC dimension is just the number of parameters in a model; it is not. Some infinite-parameter classes have finite VC dimension, and some models with few parameters can have surprisingly high VC dimension. VC theory is also a worst-case, distribution-free bound, so real-world performance is often far better than these bounds suggest, especially for modern over-parameterized models like deep neural networks.