Sample Complexity of Neural Networks

When studying a neural network as a binary classifier, it is not enough to ask whether the network classifies one particular dataset correctly. We also want to know how many different classification patterns the entire hypothesis class can express. VC dimension provides a way to describe this expressive capacity. The connection matters because the sample complexity of learning a binary-classifier hypothesis class depends on its VC dimension.

The central idea is to test a hypothesis class on finite sets of input points. If the class can realize every relevant binary labeling of a set, that set is shattered. The largest size of a set that can be shattered determines the VC dimension.

To study a hypothesis class, temporarily choose a finite set C of input points. Each hypothesis in the class assigns binary labels to the points in C. The class may produce only some of the possible labelings, or it may produce many of them. The growth function records the largest number of distinct labelings that the class can produce on any set of m points.

The size of the shattered set is the key quantity. A class with a larger VC dimension can support complete labeling behavior on a larger set, so it has greater capacity in the VC-dimension sense. This is a statement about the entire hypothesis class, not merely about the performance of one selected hypothesis on one selected dataset.

The growth function and VC dimension describe related but different views. The growth function counts how many distinct labelings are available on sets of a chosen size, taking the maximum over those sets. VC dimension asks for the largest set size for which the class can realize every relevant binary labeling.

Now specialize to the hypothesis class H_{V,E,sign}. This class uses the sign activation function, and its network graph has a single neuron in the output layer. For this specified class, the source result states that the VC dimension is O(|E| log(|E|)). Here, |E| is the number of parameters being learned in the network as described by the network graph.

The bound connects the network's learned parameters to its capacity. It is not a statement about every neural-network architecture. It is a theorem for the specified hypothesis class, the sign activation function, and the single-output-neuron setting. The logarithmic factor is part of the stated upper-bound form.

For binary-classifier hypothesis classes, the fundamental learning-theory connection is direct: sample complexity depends on VC dimension. Once the VC dimension of a neural-network hypothesis class is bounded, that bound becomes relevant when reasoning about how many training examples are required to learn the class.

A larger VC dimension means that the class can support complete binary-labeling behavior on a larger set of points. In this capacity sense, the learner is dealing with a richer hypothesis class. Therefore, VC dimension is the capacity measure used when connecting the class's expressive possibilities to the amount of data needed for learning.