Sample Complexity of Neural Networks

From Correct Predictions to Expressive Capacity

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.

Counting Labelings with the Growth Function

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.

Shattering and VC Dimension

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.

The Neural-Network Capacity Bound

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.

Why Capacity Changes Sample Needs

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.

Common Reasoning Errors

• Treating good performance on one dataset as a measurement of VC dimension.

  VC dimension concerns how many binary labeling patterns the entire hypothesis class can realize across sets of points, not just one dataset's observed accuracy.

  Fix: Ask about the class's ability to shatter finite sets and realize their relevant binary labelings.

• Defining the growth function using only one fixed point set.

  The growth function records the maximum number of distinct labelings over sets containing the chosen number of points.

  Fix: Count the distinct labelings for candidate sets of m points and take the maximum.

• Applying the stated neural-network bound without its conditions.

  The source result is for the sign-activation class with a single neuron in the output layer.

  Fix: State the activation function, output-layer condition, and meaning of |E| before using the bound.

• Confusing VC dimension with the exact number of training examples in every learning problem.

  The source establishes that sample complexity depends on VC dimension, but does not state one exact sample count for every setting.

  Fix: Use VC dimension as the capacity quantity that informs sample-complexity reasoning for binary-classifier hypothesis classes.

Check Your Understanding