Skip to content
AI360XpertBeta

Statistical Learning Theory

A generalization bound caps how far true error can exceed training error — and the honest catch is that cap is usually far too loose to use as a real number.

A PAC bound with VC dimension 10 falls from 0.2395 at 1,000 samples to 0.0112 at 1,000,000, so the shape shows data shrinking the gap even when the number itself is too loose
A PAC bound with VC dimension 10 falls from 0.2395 at 1,000 samples to 0.0112 at 1,000,000, so the shape shows data shrinking the gap even when the number itself is too loose

Why Does This Exist?

Overfitting and underfitting shows the symptom: training error low, validation error high. It does not say how far apart they could be before you measure. Statistical learning theory asks for a guarantee that holds whatever sample you drew.

The honest headline comes first. The numbers these bounds output are usually too loose to act on. A bound that allows true error to sit 24 points above training error is true and useless as a promise. What survives is the shape: more data tightens the gap, more capacity widens it, and no training score replaces unseen data.

One idea underneath it. True error means performance on the whole distribution. Training error means performance on your sample. A bound caps the distance between them with high probability over samples, using sample size and model capacity only.

This page covers the guarantee, the capacity measure, and what to keep. The symptom and its plots live in overfitting and underfitting. The capacity tradeoff from another angle lives in bias-variance-tradeoff.

Think of It Like This

A worst case weather range that still teaches

A forecaster says rain chance sits between 0 and 100 percent. True, useless as a forecast. Then stations report in and the provable range shrinks to 30 to 70, then 45 to 55. The specific range was never the point. The pattern was: more stations narrow it, and simpler weather narrows it faster.

Bounds work the same way. The number rarely tells you what accuracy to promise. The relationships tell you why to collect data, why to control capacity, and why a held out test stays non negotiable no matter how good training looks.

Where it stops: you would never plan a picnic from the worst case range. Do not promise accuracy from a bound either. Use held out measurement for promises and theory for why that measurement is required.

How It Actually Works

PAC frames the question with two tolerances. Probably means the guarantee may fail on an unlucky sample with small probability δ\delta, often 0.050.05. Approximately means we bound being close, within margin ϵ\epsilon, not exact. That modesty is what makes a proof possible without assuming the true distribution.

Capacity is measured by VC dimension, named for Vapnik and Chervonenkis. It is the largest number of points the model class can label every way. Higher means more flexibility to fit training data, which is exactly more room to fit noise. That is why capacity appears as a cost in the bound.

The bound and its shape

A representative gap bound looks like this:

true≤train+d(log⁡(2n/d)+1)+log⁡(4/δ)ntrue \leq train + \sqrt{\frac{d (\log(2n/d) + 1) + \log(4/\delta)}{n}}

Here dd is VC dimension, nn sample count, δ\delta failure probability, log⁡\log natural log. True is true error, train is training error. The square root term is the gap. It shrinks as nn grows and grows as dd grows. It must hold for every distribution at once, which is why it is valid everywhere and tight almost nowhere.

Worked example with VC 10

Fix d=10d = 10 and δ=0.05\delta = 0.05. Then log⁡(4/δ)=log⁡(80)≈4.38\log(4/\delta) = \log(80) \approx 4.38.

At n=1000n = 1000: numerator is 10×log⁡(200)+4.38=10×5.30+4.38=57.3610 \times \log(200) + 4.38 = 10 \times 5.30 + 4.38 = 57.36. Divide by 10001000 gives 0.057360.05736. Square root gives 0.23950.2395, or 24.024.0 points.

At n=10000n = 10000: numerator is 10×log⁡(2000)+4.38=10×7.60+4.38=80.3910 \times \log(2000) + 4.38 = 10 \times 7.60 + 4.38 = 80.39. Divide by 1000010000 gives 0.008040.00804. Square root gives 0.08970.0897, or 9.09.0 points.

At n=100000n = 100000 the same steps give 0.03220.0322. At n=1000000n = 1000000 they give 0.01120.0112. Ten times the data shrinks the gap by about square root of ten, not ten. That rate is the diagram headline: a steep early fall that flattens, from 0.23950.2395 down to 0.01120.0112.

Code

Compute the representative gap across sample sizes with plain Python. No library beyond standard math.

import math
def pac_bound(vc_dim: int, n: int, delta: float = 0.05) -> float:    term = (vc_dim * math.log(2 * n / vc_dim) + math.log(4 / delta)) / n    return math.sqrt(term)
for n in (1000, 10000, 100000, 1000000):    b = pac_bound(10, n)    print(f"n={n}: {b:.4f}")# -> n=1000: 0.2395# -> n=10000: 0.0897# -> n=100000: 0.0322# -> n=1000000: 0.0112

Even at a million samples the bound still allows 1.11.1 points of gap for a tiny capacity of 1010. For large nets the number is far looser. What the printout proves is the rate: each tenfold data multiplies the gap by about 0.360.36, the square root law in numbers.

Watch Out For

Quoting a bound as an accuracy promise

A report says true error is at most training plus 9.09.0 points because n=10000n = 10000 gave 0.08970.0897. A stakeholder hears a guarantee of single digit gap. The bound is valid for every distribution, so on your distribution it is far from tight.

Symptom: a loose number presented beside measured accuracy as if both were measurements. Fix: promise only what held out data measured. Cite the bound for why held out data is required, never as the number itself.

Reading VC dimension as a real world overfitting forecast

VC dimension measures worst case shattering power on adversarial point arrangements. Real data is rarely adversarial, and large nets often generalize despite huge VC values.

Symptom: a high VC number blocks a model that validates well, or a low VC number excuses skipping validation. Fix: treat VC as one input to intuition about capacity alongside bias-variance-tradeoff. Always confirm on unseen data. Theory guides the tradeoff, measurement decides.

The Quick Version

  • PAC learning bounds true error by training error plus a gap that holds with high probability over samples.
  • VC dimension measures raw capacity to fit arbitrary labelings, and higher capacity widens the bound.
  • Our VC 10 example falls from 0.2395 at 1,000 samples to 0.0112 at 1,000,000, a square root rate with diminishing returns.
  • The numeric bound is usually too loose to promise, since it must cover every distribution at once.
  • What survives: more data narrows the gap, more capacity widens it, and held out testing stays required.