Statistical Learning Theory
A training score describes a model on the examples used to fit it. Learning theory asks when that score also constrains its error on new examples, even though the model was chosen after seeing the training data. We will build a finite-class guarantee, extend the idea to infinite classes, and use an independent validation set to select among fitted models. These are statements about sampling uncertainty; their usefulness depends on what they bound and how large that bound is.
The setup is binary classification with independent, identically distributed examples \((X_i,Y_i)\) from one distribution \(D\). The loss is 1 for a wrong prediction and 0 for a correct one. For a classifier \(f\), its population risk is \(R(f)=\Pr_D(f(X)\ne Y)\); its empirical risk is \(\hat R_S(f)=n^{-1}\sum_{i=1}^n\mathbf1\{f(X_i)\ne Y_i\}\). Thus 12 mistakes in 100 training examples give \(\hat R_S(f)=0.12\). The earlier Empirical Risk Minimization and Generalization article introduces these quantities. Here the difficulty is that \(f\) itself depends on the sample.
A guarantee that survives choosing a model
For a classifier fixed independently of the sample, Hoeffding’s inequality gives \(\Pr(|\hat R_S(f)-R(f)|>b)\le 2e^{-2nb^2}\). Suppose a class \(\mathcal F\) of \(M\) classifiers is specified before observing that sample. The probability that any of their deviations exceeds \(b\) is at most the sum of the \(M\) probabilities, \(2M e^{-2nb^2}\). This union bound does not require the classifiers’ errors to be independent of one another.
Setting that upper bound to a failure probability \(0<\delta<1\) and solving for \(b\) gives \[b(M,n,\delta)=\sqrt{\frac{\log(2M/\delta)}{2n}},\qquad \Pr\!\left(\forall f\in\mathcal F:\ |\hat R_S(f)-R(f)|\le b\right)\ge1-\delta.\] Logs are natural. With \(M=100\), \(n=1000\), and \(\delta=0.05\), the radius is about 0.0644, or 6.44 percentage points. On the event in the formula, all 100 errors are covered together, including the classifier selected for having the lowest training error. The 5% is an upper limit on the chance, over new training samples, that this simultaneous guarantee fails.
The next experiment uses a distribution whose population errors are known exactly. Each input contains independent fair bits, the label is another independent fair bit, and classifier \(f_j\) predicts input bit \(j\). Every classifier therefore has risk 0.5. Conditional on either label, its mistakes and the other classifiers’ mistakes are independent fair bits, so the training mistake counts are independent \(\operatorname{Binomial}(n,0.5)\) variables. We can sample those counts directly without creating a large input matrix or estimating risk on a second test sample.
import numpy as np
from scipy.stats import binom
rng = np.random.default_rng(52)
delta = 0.05
def finite_radius(M, n, delta=0.05):
return np.sqrt(np.log(2 * M / delta) / (2 * n))
print("M n mean max 95% quantile bound exact failure")
for M in (10, 100, 1000):
for n in (100, 1000):
errors = rng.binomial(n, 0.5, size=(2000, M)) / n
max_gaps = np.max(np.abs(errors - 0.5), axis=1)
radius = finite_radius(M, n, delta)
k = np.arange(n + 1)
outside = np.abs(k / n - 0.5) > radius
one_failure = binom.pmf(k[outside], n, 0.5).sum()
failure = -np.expm1(M * np.log1p(-one_failure))
print(f"{M:4d} {n:5d} {max_gaps.mean():11.4f}"
f" {np.quantile(max_gaps, 0.95):15.4f}"
f" {radius:8.4f} {failure:16.6f}")
# M n mean max 95% quantile bound exact failure
# 10 100 0.0947 0.1400 0.1731 0.004080
# 10 1000 0.0297 0.0440 0.0547 0.005591
# 100 100 0.1369 0.1700 0.2036 0.003211
# 100 1000 0.0435 0.0550 0.0644 0.004404
# 1000 100 0.1704 0.2000 0.2302 0.001666
# 1000 1000 0.0543 0.0640 0.0728 0.004359Each row compares the same quantity: the largest absolute empirical-to-population error gap across the class. The mean and 95th percentile are estimates from 2,000 samples. The last column is computed from the binomial distribution: if one classifier exceeds the radius with probability \(q\), independence in this experiment gives failure probability \(1-(1-q)^M\). Those probabilities are below 0.05. Each row has its own 95% guarantee; we have not assigned a joint 95% guarantee to the entire six-row experiment.
A 95% upper bound is not an estimate of the mean maximum gap. Dividing it by that mean would mix two different summaries and would not establish that the bound is tight. The bound decreases as \(1/\sqrt n\) for fixed \(M,\delta\), and increases with \(\sqrt{\log(2M/\delta)}\) for fixed \(n\). These are properties of the guarantee. An observed gap need not follow either rate for every distribution or family.
From uniform convergence to PAC learning
A bound that holds for all models in a class at once is called a uniform convergence bound. It connects empirical risk minimization (ERM) to population performance. Let \(\hat f\) minimize training error over \(\mathcal F\), and let \(f^*\) minimize population error there. On the simultaneous event above, \[R(\hat f)\le\hat R_S(\hat f)+b\le\hat R_S(f^*)+b\le R(f^*)+2b.\] The first and last steps use the deviation bound. The middle step uses ERM. For example, if \(b=0.03\) and the best model in the class has risk 0.10, this argument guarantees at most 0.16 for ERM. It does not say ERM’s error will equal 0.16.
PAC means “probably approximately correct”: with probability at least \(1-\delta\), a learner achieves an error tolerance \(\epsilon\). In the agnostic setting, the tolerance is excess risk above the best in the class, since even that model may make mistakes. For this finite class, \(n\ge2\log(2M/\delta)/\epsilon^2\) makes \(2b\le\epsilon\). This is a sufficient sample size, not a claim that every problem needs that many examples. If the minimum is not attained, the comparison uses the infimum; an optimization error of \(\eta\) in training risk adds \(\eta\) to the conclusion.
The realizable setting makes the stronger assumption that some classifier in the class has zero population risk. For a finite class, a bad classifier with risk greater than \(\epsilon\) has probability at most \((1-\epsilon)^n\le e^{-n\epsilon}\) of making no training mistakes. A union bound then shows that \(n\ge\log(M/\delta)/\epsilon\) is sufficient for any zero-training-error choice to have risk at most \(\epsilon\), with confidence \(1-\delta\). The faster dependence on \(\epsilon\) relies on realizability. Uniform convergence also cannot remove approximation error: if the class cannot express a useful predictor, learning its best member is not enough.
How an infinite class can have finite capacity
Linear classifiers allow infinitely many coefficient vectors, so counting parameter settings is unhelpful. VC dimension instead counts how many inputs a binary classifier class can shatter: on those inputs, every possible assignment of binary labels must be expressible. The dimension is the largest size of a shattered set, or infinity if there is no finite maximum.
For the one-dimensional rules \(f_t(x)=\mathbf1\{x\ge t\}\), one point can receive either label by moving the threshold. Two ordered points \(x_1<x_2\) cannot receive labels \((1,0)\), so this class has VC dimension 1 despite infinitely many thresholds. Affine linear classifiers in \(d\) dimensions have VC dimension \(d+1\). Fitting one random labeling of a sample is much weaker than expressing all \(2^n\) labelings of it.
The growth function \(\Pi_{\mathcal F}(m)\) is the largest number of distinct label patterns the class produces on \(m\) inputs. For VC dimension \(v\) and \(1\le v\le m\), Sauer’s lemma gives \(\Pi_{\mathcal F}(m)\le(em/v)^v\). A conservative uniform deviation radius is \[b_{\rm VC}=\sqrt{\frac{8}{n}\left[v\log\!\left(\frac{2en}{v}\right)+\log\!\left(\frac{2}{\delta}\right)\right]},\quad 1\le v\le2n.\] This combines the growth-function uniform convergence theorem and Sauer’s lemma in Blum, Hopcroft, and Kannan, Foundations of Data Science, Theorems 5.15–5.16. If the radius exceeds 1, the trivial error-gap bound of 1 is better. That is a vacuous guarantee: every pair of error rates already differs by at most 1. For a fixed finite \(v\), the radius tends to zero as \(n\) grows, so the uniform-convergence argument can also establish learning guarantees for an infinite class.
Here a fixed generator supplies independent examples from the same distribution at every sample size. Twenty Gaussian features produce a label probability through a nonlinear score. The training sets are nested prefixes; the independent test set stays fixed. A logistic classifier’s 0.5-threshold prediction belongs to the affine class, even though its training objective is log loss rather than 0–1 ERM. The uniform deviation guarantee still covers it; the ERM excess-risk argument above would need an additional optimization comparison.
from scipy.special import expit
from sklearn.linear_model import LogisticRegression
def draw_data(n, seed):
g = np.random.default_rng(seed)
X = g.normal(size=(n, 20))
probability = expit(2.5 * X[:, 0] * X[:, 1] + 1.5 * X[:, 2])
y = (g.random(n) < probability).astype(int)
return X, y
Xall, yall = draw_data(100000, 10)
Xtest, ytest = draw_data(20000, 11)
print("n train error test error signed gap VC radius")
for n in (100, 1000, 10000, 100000):
model = LogisticRegression(max_iter=3000).fit(Xall[:n], yall[:n])
train_error = 1 - model.score(Xall[:n], yall[:n])
test_error = 1 - model.score(Xtest, ytest)
v = 21
radius = np.sqrt(8 * (v * np.log(2 * np.e * n / v)
+ np.log(2 / 0.05)) / n)
print(f"{n:6d} {train_error:13.4f} {test_error:12.4f}"
f" {test_error - train_error:+12.4f} {min(1.0, radius):11.4f}")
print("test radius per fixed fitted model:",
round(np.sqrt(np.log(2 / 0.05) / (2 * len(ytest))), 4))
# n train error test error signed gap VC radius
# 100 0.2600 0.3895 +0.1295 1.0000
# 1000 0.3090 0.3362 +0.0272 0.9813
# 10000 0.3248 0.3276 +0.0028 0.3674
# 100000 0.3277 0.3244 -0.0033 0.1318
# test radius per fixed fitted model: 0.0096The signed gap is test error minus training error. The theorem bounds the absolute gap to population risk, whereas the printed test error has its own sampling noise. Its separate Hoeffding radius is about 0.0096 per fitted model; sharing a test set does not automatically give simultaneous 95% coverage for all four estimates. Near-zero test gaps therefore make “bound divided by gap” ratios unstable and hard to interpret.
This conservative VC radius becomes smaller with more data but is much larger than the observed test gaps. It covers every affine classifier, including choices the fitting algorithm would not make. One fitted classifier lying below the radius is not a proof of the theorem, and these four rows cannot establish that better constants or a different analysis would fail. When comparing several classes by training error plus a justified class-specific penalty, structural risk minimization makes this tradeoff explicit; simultaneous coverage must include the classes being compared.
Measuring agreement with random labels
Empirical Rademacher complexity measures a class on the observed inputs. Write predictions as \(-1\) or \(+1\), and let each \(\sigma_i\) be an independent fair sign. Conditional on inputs \(x_1,\ldots,x_n\), define \[\hat{\mathfrak R}_S(\mathcal F)=\mathbb E_\sigma\!\left[\sup_{f\in\mathcal F}\frac1n\sum_{i=1}^n\sigma_i f(x_i)\right].\] Each matching sign contributes +1 and each mismatch contributes −1. If the best classifier matches 70 of 100 random signs, the maximized correlation is \((70-30)/100=0.4\). Repeating the random signs and averaging estimates the expectation.
The supremum means the best agreement achievable anywhere in the class. A fitting algorithm’s result can fall short of it. Rademacher bounds turn this complexity, applied to the relevant loss class, into uniform guarantees with a confidence term. The prediction-sign definition above should not be substituted unchanged into a theorem about differently scaled losses. Data dependence can make an analysis more informative, but does not guarantee a smaller useful bound. Shalev-Shwartz and Ben-David, Understanding Machine Learning, Chapter 26 develops these bounds.
For a finite list we can maximize exactly instead of relying on a training optimizer. The matrix below holds the predictions of 100 fixed coordinate classifiers on 200 inputs: rows are inputs and columns are classifiers. Each row of signs is one independent random labeling. We also duplicate the first ten classifiers to show why counting listed models alone can lose information.
g = np.random.default_rng(7)
n = 200
predictions = g.choice([-1.0, 1.0], size=(n, 100))
signs = g.choice([-1.0, 1.0], size=(2000, n))
def noise_agreement(P):
best_correlations = (signs @ P / n).max(axis=1)
return best_correlations.mean(), ((1 + best_correlations) / 2).mean()
print("class Rademacher estimate best noise accuracy")
for name, P in (("10 distinct", predictions[:, :10]),
("100 distinct", predictions),
("10 repeated 10x", np.tile(predictions[:, :10], (1, 10)))):
complexity, accuracy = noise_agreement(P)
print(f"{name:20s} {complexity:19.4f} {accuracy:21.4f}")
# class Rademacher estimate best noise accuracy
# 10 distinct 0.1066 0.5533
# 100 distinct 0.1767 0.5884
# 10 repeated 10x 0.1066 0.5533The duplicated columns give exactly the same maximum for every random labeling, so both reported quantities stay unchanged. Treating all 100 entries as separate terms in a union bound would still be valid, but unnecessarily loose: there are only ten distinct classifiers in that list. For the genuinely larger nested class the maximum cannot decrease. Neither observation says that a larger class must have worse prediction error on real labels.
A model that fits noise can also learn signal
from sklearn.ensemble import RandomForestClassifier
Xtr, ytr = draw_data(2000, 20)
Xte, yte = draw_data(2000, 21)
g = np.random.default_rng(22)
random_train = g.integers(0, 2, len(ytr))
random_test = g.integers(0, 2, len(yte))
for name, make in (("logistic", lambda: LogisticRegression(max_iter=3000)),
("forest", lambda: RandomForestClassifier(100, random_state=0))):
real = make().fit(Xtr, ytr)
fake = make().fit(Xtr, random_train)
print(f"{name:8s} real train/test {real.score(Xtr, ytr):.4f}/{real.score(Xte, yte):.4f}"
f" random train/test {fake.score(Xtr, random_train):.4f}/"
f"{fake.score(Xte, random_test):.4f}")
# logistic real train/test 0.6850/0.6705 random train/test 0.5535/0.5025
# forest real train/test 1.0000/0.7075 random train/test 1.0000/0.5015The random-label test uses fresh independent fair labels, matching its training-label mechanism. Its population accuracy is exactly 0.5 for any fitted classifier; the finite test score fluctuates around that value. The real-label test evaluates the nonlinear signal generator. A forest can memorize the random training labels and still predict real labels better than chance. This run establishes neither shattering nor a numerical VC dimension, and it does not show that every capacity-based bound must be vacuous.
The class describes available functions; the fitting procedure determines which one is selected. Regularization can change that selection, explicit constraints can restrict the class, and early stopping can limit reachable solutions. Algorithmic stability, compression, and PAC-Bayes analyses provide other ways to study generalization, beyond the worst-case VC calculation shown here. The choice of analysis requires assumptions about the particular learner; a noise-fitting experiment alone cannot supply those assumptions.
References
- Blum, Hopcroft, and Kannan. Foundations of Data Science, Theorems 5.15–5.16
- Shalev-Shwartz and Ben-David (2014). Understanding Machine Learning: From Theory to Algorithms, Chapter 26
Discover more from Insightful Data Lab
Subscribe to get the latest posts sent to your email.