One Parameter, Infinite Capacity

Here is a classifier. It takes a real number $x$, has one real parameter $\theta$, and predicts

$$h_\theta(x) = \operatorname{sign}\left(\sin(\theta x)\right).$$

One parameter. Fewer than a straight line through the origin has in two dimensions, which is usually where people put the cheap end of the scale.

Put twenty points at $x_i = 2^{-i}$ for $i = 1, \dots, 20$ and hand it any labelling you like of those twenty points. There are $2^{20} = 1{,}048{,}576$ of them. A single value of $\theta$ realises every one, checked exhaustively.

A. How it does it

The trick is that $\theta$ is not being used as a knob. It is being used as a tape.

Take the labels $y_1, \dots, y_m$, each $\pm 1$, and set

$$\theta = \pi\left(1 + \sum_{i=1}^{m} \frac{1 - y_i}{2}\, 2^{i}\right).$$

Then $\theta x_i = \theta 2^{-i}$ picks out the binary expansion of $\theta/\pi$ from digit $i$ onward, and the sign of the sine reads off the bit that was written there. Each label occupies its own binary place, and nothing collides, because the points were chosen an octave apart.

A real number holds infinitely many bits. There is no $m$ at which this stops working, so the class $\{h_\theta\}$ shatters sets of every finite size and its VC dimension is infinite.

B. It learns nothing

Fit the twenty points with random labels, then ask about a twenty-first point at $x_{21} = 2^{-21}$, also labelled at random. Over 20,000 trials: training accuracy 100% every time, held-out accuracy 0.5038.

That is exactly what "infinite VC dimension" means operationally. The twenty labels fix the first twenty bits of $\theta/\pi$ and say nothing whatsoever about the twenty-first, so the prediction on a new point is a coin flip. The model has perfect memory and no generalisation at all, and the distribution-free bounds correctly refuse to say anything about it.

So far this is a curiosity. The part worth keeping is what it does to parameter counting.

C. Parameter count is not an upper bound

The natural reading of "one parameter" is "this class cannot express much". The sine classifier says that reading is simply wrong. Capacity is about how many distinct labellings a class can produce on a finite sample, and the number of parameters constrains that only when the parameters are used the way we expect them to be: continuously, locally, one direction of variation each.

Linear separators in $\mathbb{R}^d$ have VC dimension $d + 1$, so the intuition survives there and generalises badly beyond it. A single real number can carry a whole training set.

For contrast, the figure shows a class with two parameters whose capacity really is finite: with one interval on three points it reaches 7 of the 8 labellings and cannot produce (1, 0, 1).

D. And it is not a lower bound either

The reverse direction fails too, and this is the one that matters in practice.

Add a margin requirement to linear separators: classify correctly with all points at distance at least $\gamma$ from the boundary, with the data inside a ball of radius $R$. The capacity of that restricted class is bounded by $R^2 / \gamma^2$ regardless of the dimension. Push $d$ to infinity, which is what a kernel does, and that bound does not move at all: the constraint has removed almost every function the parameters could otherwise express, and what is left is governed by a scale rather than by a count.

Modern networks are the same phenomenon at a larger scale. They have more parameters than training examples, so parameter counting places their capacity above $n$ and every classical bound built on it is vacuous. They generalise anyway. The parameters are not free to take arbitrary values: they are reached by a particular optimiser, from a particular initialisation, under weight decay and early stopping and data augmentation, and the set of functions actually reachable that way is far smaller than the set the architecture could express.

E. What to measure instead

If the count does not bound capacity in either direction, the honest options are empirical.

• Try to fit random labels. If a model can achieve zero training error on the same inputs with the labels shuffled, its effective capacity on that sample is at least $n$, and any explanation of its real performance has to come from somewhere other than the size of the hypothesis class.
• Measure the margin, and the norm. For the classes where a bound does exist, the quantity in it is a scale, not a count: $R^2/\gamma^2$ for separators, weight norms for networks. Those are things you can compute after training.
• Hold something out, and hold it out properly. A validation estimate is a direct measurement of what the bounds are trying to bound, and it remains the only capacity measure that is always available.
• Be suspicious of any capacity claim made before training. The sine classifier is one line of code away from looking like the simplest model in the world.

Capacity is a property of what a procedure can actually reach, not of how many numbers it happens to store.