The Overfitting Problem

Imagine you're a student preparing for an exam. You have access to last year's test, complete with answers. You study those specific questions until you can answer each one perfectly. On exam day, you feel confident—until you realize the new test has entirely different questions. Your perfect preparation becomes worthless.

This is precisely what happens when machine learning models overfit.

A model that achieves 99% accuracy on training data but only 60% on new data hasn't learned the underlying patterns—it has memorized the specific examples. Understanding this distinction, quantifying it, and learning to prevent it forms the very heart of practical machine learning.

Before we can understand overfitting, we need precise definitions. Machine learning fundamentally involves learning a function $f: \mathcal{X} \rightarrow \mathcal{Y}$ from examples. Our goal is to find a hypothesis $h$ that approximates the true function $f$ (or the conditional distribution $P(Y|X)$).

The Training Set and Training Error

We observe a finite sample of data:

$$\mathcal{D}_{train} = {(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)}$$

The training error (also called empirical error or in-sample error) measures how well our hypothesis $h$ performs on this observed data:

$$\text{Err}{train} = \frac{1}{n} \sum{i=1}^{n} L(y_i, h(x_i))$$

where $L(y, \hat{y})$ is a loss function (e.g., squared error $(y - \hat{y})^2$ for regression, or 0-1 loss $\mathbf{1}[y eq \hat{y}]$ for classification).

The Test Set and Test Error

The test error (also called generalization error or out-of-sample error) measures performance on new, unseen data drawn from the same distribution:

$$\text{Err}{test} = \mathbb{E}{(x,y) \sim P}[L(y, h(x))]$$

In practice, we estimate this expectation using a held-out test set $\mathcal{D}_{test}$ that was never used during training:

$$\widehat{\text{Err}}{test} = \frac{1}{m} \sum{j=1}^{m} L(y_j^{test}, h(x_j^{test}))$$

The test set serves as a proxy for all possible future data. It must remain completely untouched during model development—using it for any decision (hyperparameter tuning, model selection) contaminates it and invalidates the error estimate.

The generalization gap is the difference between test error and training error:

$$\text{Generalization Gap} = \text{Err}{test} - \text{Err}{train}$$

This gap is perhaps the single most important diagnostic in machine learning. It tells us exactly how much our model has overfit to the training data.

Why the Gap Exists

The gap arises because the model sees the training data during optimization. Any noise, outliers, or idiosyncratic patterns in the training set get incorporated into the hypothesis. These patterns don't generalize to new data because they were specific to the training sample, not the underlying distribution.

Interpreting the Gap

The generalization gap reveals the model's behavior:

The sweet spot is a small gap with low training error—the model has learned the true patterns without memorizing noise.

Mathematical Decomposition

We can decompose the expected test error of our learning algorithm into components that illuminate the gap:

$$\mathbb{E}[\text{Err}_{test}] = \text{Irreducible Error} + \text{Bias}^2 + \text{Variance}$$

where:

• Irreducible Error: Noise inherent in the problem; cannot be reduced by any model
• Bias²: Error from incorrect assumptions in the model (underfitting)
• Variance: Error from sensitivity to training data fluctuations (overfitting)

The generalization gap is primarily driven by the variance term. High variance means the model's predictions change significantly with different training sets—a hallmark of overfitting.

Learning curves are the primary diagnostic tool for understanding model behavior. They plot training and test error against either:

1. Training set size (more data)
2. Model complexity (more parameters)
3. Training iterations (more optimization)

Each perspective reveals different aspects of the training/test relationship.

Learning Curves vs Training Set Size

As training data increases:

For training error:

• Starts very low (with few examples, any model can fit perfectly)
• Increases gradually as more data makes perfect fitting harder
• Converges to the irreducible error plus bias

For test error:

• Starts very high (model hasn't learned from enough examples)
• Decreases as more data reveals true patterns
• Converges toward training error (gap shrinks)

$$\lim_{n \to \infty} (\text{Err}{test} - \text{Err}{train}) = 0$$

With infinite data, the training set would contain all possible patterns, and the distinction between training and test would vanish.

Learning Curves vs Model Complexity

As model complexity increases (more parameters, higher-degree polynomials, deeper networks):

For training error:

• Monotonically decreases
• More complex models can fit training data better (or perfectly)
• Eventually reaches zero for sufficiently complex models

For test error:

• Initially decreases (reduced bias)
• Reaches a minimum at optimal complexity
• Increases beyond that point (increased variance)

This U-shaped test error curve is characteristic of the bias-variance tradeoff. The optimal complexity minimizes test error, not training error.

Knowing the theory is essential, but recognizing overfitting in real-world scenarios requires pattern recognition across multiple symptoms.

A Concrete Example: Polynomial Regression

Consider fitting polynomials to noisy data generated from $y = \sin(2\pi x) + \epsilon$ where $\epsilon \sim N(0, 0.3)$:

The degree-15 polynomial achieves essentially zero training error—it passes exactly through every training point. But its test error is catastrophic because it has learned the noise, not the signal.

Correctly measuring the generalization gap requires disciplined data handling. Violations of proper protocol lead to data leakage—where information from the test set inappropriately influences training, yielding optimistic but invalid error estimates.

The Three-Way Split

For proper evaluation, data should be divided into three disjoint sets:

1. Training Set (~60-70%): Used to fit model parameters
2. Validation Set (~15-20%): Used for hyperparameter tuning and model selection
3. Test Set (~15-20%): Used ONCE at the end to estimate generalization

$$\mathcal{D} = \mathcal{D}{train} \cup \mathcal{D}{val} \cup \mathcal{D}{test}$$ $$\mathcal{D}{train} \cap \mathcal{D}{val} = \mathcal{D}{train} \cap \mathcal{D}{test} = \mathcal{D}{val} \cap \mathcal{D}_{test} = \emptyset$$

Cross-Validation for Small Datasets

When data is limited, k-fold cross-validation provides a more robust estimate:

1. Split data into k folds
2. For each fold i:
   • Train on all folds except i
   • Evaluate on fold i
3. Average the k error estimates

$$\widehat{\text{Err}}{CV} = \frac{1}{k} \sum{i=1}^{k} \text{Err}^{(i)}$$

This uses all data for both training and validation (never simultaneously), yielding lower-variance estimates than a single train-test split.

It's tempting to evaluate models by training error alone—after all, it's always available and requires no data splitting. But training error is fundamentally misleading, especially for complex models.

The Mathematical Problem

Training error is computed on the same data used for optimization. The model parameters $\theta$ are chosen to minimize:

$$\hat{\theta} = \arg\min_\theta \frac{1}{n} \sum_{i=1}^{n} L(y_i, f_\theta(x_i))$$

By definition, $\hat{\theta}$ makes the training error as small as possible. This means training error is optimistically biased:

$$\mathbb{E}[\text{Err}{train}] < \mathbb{E}[\text{Err}{test}]$$

The more flexible the model, the more it can overfit, and the more optimistic the training error becomes.

The Extreme Case: Interpolation

Consider a model complex enough to perfectly interpolate all training points (zero training error). Examples include:

• High-degree polynomials with degree ≥ n-1
• Decision trees grown to full depth
• 1-Nearest Neighbor
• Kernel machines with sufficient capacity

For such models: $$\text{Err}_{train} = 0$$

But test error can be arbitrarily bad! The model has memorized the training set but learned nothing about the underlying pattern. Training error gives no indication of this failure.

The training/test distinction connects to deep results in statistical learning theory that provide theoretical bounds on the generalization gap.

Empirical Risk Minimization (ERM)

Most learning algorithms minimize empirical risk (training error):

$$\hat{h} = \arg\min_{h \in \mathcal{H}} \frac{1}{n} \sum_{i=1}^{n} L(y_i, h(x_i))$$

The fundamental question is: when does minimizing empirical risk also minimize true risk (test error)? The answer depends on:

1. Sample size n: More data → better guarantees
2. Hypothesis class complexity: Simpler $\mathcal{H}$ → tighter bounds
3. Data distribution: Some distributions are easier to learn

Generalization Bounds

Statistical learning theory provides bounds of the form:

$$\text{Err}{test}(\hat{h}) \leq \text{Err}{train}(\hat{h}) + \text{Complexity}(\mathcal{H}, n, \delta)$$

with probability at least $1 - \delta$. The complexity term depends on measures like:

• VC Dimension: For binary classifiers, $\text{Gap} = O\left(\sqrt{\frac{d_{VC}}{n}}\right)$
• Rademacher Complexity: More general measure of hypothesis class richness
• PAC-Bayes Bounds: Incorporate prior beliefs about good hypotheses

These bounds formalize the intuition that:

• More training data shrinks the gap
• Restricting model complexity shrinks the gap
• Regularization effectively reduces complexity, improving bounds

Practical Implications

While theoretical bounds are often loose, they provide crucial guidance:

We've established the foundational distinction that underlies all of regularization theory. Let's consolidate the key insights:

What's Next?

Now that we understand the generalization gap, we need to understand why it grows uncontrollably in certain settings. The next page explores high-dimensional settings—where the number of features approaches or exceeds the number of samples, creating the perfect conditions for catastrophic overfitting.