Overfitting and Underfitting

Consider a learning algorithm that selects a hypothesis $h$ from a hypothesis space $\mathcal{H}$ by minimizing empirical (training) error on a finite dataset $D = \{(x_i, y_i)\}_{i=1}^n$. Underfitting occurs when $\mathcal{H}$ is too restrictive to represent the true underlying relationship between $x$ and $y$, so even the best $h \in \mathcal{H}$ has high error on both the training set and unseen data. The training error itself is a high number, and this is the tell: the model cannot even fit the data it was shown.

Overfitting occurs when $\mathcal{H}$ is expressive enough (or the optimization is run long enough) that the selected $h$ fits not only the true signal but also the sampling noise specific to $D$. Training error becomes very low, sometimes zero, while error on a fresh sample drawn from the same distribution remains high or even increases. The hypothesis has effectively partly memorized the training set rather than learning the generating process. Formally, if $R(h)$ denotes true (population) risk and $\hat{R}(h)$ denotes empirical risk on $D$, overfitting is the situation where $\hat{R}(h)$ is small but $R(h) - \hat{R}(h)$ is large — the generalization gap is large. The unifying quantity is model capacity: informally, how large and flexible $\mathcal{H}$ is. Capacity can be measured formally via VC dimension, Rademacher complexity, or number of effective parameters, but the intuition is simpler: a hypothesis space with more capacity can fit more datasets exactly, including datasets that are pure noise. As capacity increases from very low to very high, training error decreases monotonically (a richer space can always fit the training data at least as well), while test error traces a U-shape — first decreasing as real signal is captured, then increasing as the model starts absorbing noise. The minimum of that U is the sweet spot; underfitting lives to its left, overfitting to its right. This single picture is the qualitative core of the The Bias-Variance Tradeoff, where the same phenomenon is decomposed quantitatively into bias and variance terms.

The mechanism is best understood by tracing exactly what happens as one sweeps a complexity knob — polynomial degree, tree depth, number of hidden units, number of training epochs, or inverse regularization strength — while holding the training set fixed.

Step 1 — Fit at low complexity. The hypothesis space contains only very simple functions (e.g., degree-1 polynomials, a decision stump, a linear model). The best fit in this space cannot bend enough to track the true signal. Both training error and held-out error are high and close to each other, because the model's limitation, not the particular sample, is the bottleneck. This is the underfitting regime.

Step 2 — Increase complexity toward the right amount. As more flexible hypotheses become available (higher-degree polynomials, deeper trees, more hidden units), the model starts capturing genuine structure — curvature, interactions, nonlinearities that really exist in the data-generating process. Training error drops. Crucially, held-out error also drops, because the newly captured structure generalizes: it reflects the true relationship, not sampling noise. This is the productive middle regime, where more capacity is good.

Step 3 — Overshoot into excess complexity. Beyond some point, additional capacity no longer buys genuine structure — there is none left to capture — so the model starts fitting the specific noise realized in this particular training sample. Training error continues to fall, potentially to zero, because a sufficiently flexible model can literally interpolate every training point exactly. But held-out error stops falling and begins to rise, because the noise pattern memorized from the training set does not recur in new data; the model's predictions on new inputs are driven partly by artifacts that have zero correlation with the true target. This is overfitting.

Step 4 — Select complexity using a held-out signal. Because training error is monotonically deceptive (it always prefers more capacity), model selection must use a signal the model did not fit on: a validation set, cross-validation, or a penalized criterion (AIC/BIC) that explicitly charges for capacity. The complexity level minimizing validation error is chosen, and only then is test error — from data touched exactly once — reported as the final, honest estimate of generalization performance. ```text ALGORITHM: DiagnoseAndSelectComplexity INPUT: training set D_train, validation set D_val, a family of hypothesis spaces H_1 ⊂ H_2 ⊂ ... ⊂ H_K of increasing capacity (e.g., polynomial degrees 1..K, or tree depths 1..K) for k = 1 .. K: h_k = argmin_{h in H_k} EmpiricalRisk(h, D_train) # fit on training data only train_err[k] = EmpiricalRisk(h_k, D_train) val_err[k] = EmpiricalRisk(h_k, D_val) # never used to fit h_k

# Diagnostic pass (informational, does not change selection) for k = 1 .. K: gap[k] = val_err[k] - train_err[k] if train_err[k] is high and gap[k] is small: label[k] = "underfitting region" elif train_err[k] is low and gap[k] is large: label[k] = "overfitting region" else: label[k] = "reasonable fit" k_star = argmin_k val_err[k] # model selection uses ONLY validation error h_star = h_{k_star}

# Final, one-time evaluation on data untouched by both fitting and selection test_err = EmpiricalRisk(h_star, D_test) return h_star, test_err, label ``` The subtlety worth emphasizing: `val_err` is used to choose $k$, so it is no longer an unbiased estimate of the generalization error of $h_\star$ once selection has happened (a small amount of overfitting to the validation set itself occurs). The final, honest number must come from a third, untouched test set — this is why practitioners maintain a strict train / validation / test split, or use nested cross-validation when data is scarce.

Complexity, computationally. The `DiagnoseAndSelectComplexity` procedure fits $K$ models, one per complexity level. If a single fit at complexity level $k$ costs $T(k)$ time (e.g., $O(n \cdot d_k)$ for a degree-$d_k$ polynomial regression via least squares, or $O(n \log n \cdot d_k)$ for tree induction of depth $d_k$), the total procedure costs

which is dominated by the largest, most complex model in the sweep — typically $O(K \cdot T(K))$. Space is $O(n)$ per fit plus $O(K)$ to store the error curves, or $O(K \cdot p_K)$ if all $K$ fitted models are retained ($p_K$ the parameter count of the richest model). This is the honest cost of any principled complexity search: there is no way to know the right complexity without trying several and checking held-out performance, short of using a capacity-penalizing criterion (AIC, BIC, minimum description length) that estimates the U-curve analytically from a single fit at each complexity, trading search cost for a bias toward the specific penalty's assumptions.

Why training error is monotonically misleading. For nested hypothesis spaces $\mathcal{H}_1 \subset \mathcal{H}_2 \subset \cdots$, since $\mathcal{H}_k \subset \mathcal{H}_{k+1}$, the minimizer of empirical risk over the larger space can always at least match the smaller space's minimum (it contains it as a candidate), so

Training error is therefore non-increasing in $k$ — a mathematical certainty, not an empirical trend — which is exactly why it cannot be used alone to pick $k$: it would always select the richest available space, including one so rich it interpolates noise.

Why validation/test error is U-shaped — the bias-variance argument. Decompose expected test error (for squared loss, on a point $x$) as

where $f$ is the true regression function and $\sigma^2$ is irreducible noise. Low-capacity models have high bias (they cannot represent $f$ even with infinite data) but low variance (they barely change from one training sample to another, since there is little freedom to change). High-capacity models have low bias but high variance (small perturbations of the training sample — different noise draws — produce very different fitted functions, especially where the model is free to chase individual points). Test error is the sum of these two decreasing/increasing quantities plus a constant, and a sum of a decreasing and an increasing function is minimized at an interior point — this is the mathematical reason the U-shape is not a coincidence but a theorem-level consequence of the decomposition, made fully precise in The Bias-Variance Tradeoff.

Tradeoffs to be honest about. Reducing capacity to fight overfitting introduces bias — you may now systematically miss real structure. Adding regularization to fight overfitting (previewed in Regularization) shrinks variance at the cost of a controlled, small bias increase, and is usually preferable to hard-capping capacity because it degrades gracefully with a tunable knob rather than a discrete choice. Gathering more data reduces variance without adding bias, but is often the most expensive fix in practice. There is no complexity level that is universally correct — the U-curve's minimum depends on sample size (more data shifts it rightward, tolerating more capacity), noise level (more noise shifts it leftward), and true underlying complexity of $f$ itself.

Suppose the true relationship is $y = \sin(1.5\pi x) + \varepsilon$, $\varepsilon \sim \mathcal{N}(0, 0.09)$, with $x \in [0,1]$, and we have $n=12$ training points. We fit polynomial regression $h(x) = \sum_{j=0}^{d} w_j x^j$ for degrees $d \in \{1, 3, 9\}$ and record training MSE and held-out MSE on a fresh 200-point validation set drawn from the same distribution.

Walking through why degree 9 fails: with 10 free coefficients and only 12 training points, the polynomial has almost enough freedom to pass through every training point exactly (interpolation), including the specific noise draws $\varepsilon_i$ at each of the 12 $x_i$'s. Between training points, the fitted curve is forced to oscillate wildly to hit each noisy target exactly (a manifestation of Runge's phenomenon for high-degree interpolation). Those oscillations are a function purely of this sample's noise realization; a different draw of 12 points from the same true process would force wildly different oscillations. On the validation set, the oscillations are essentially uncorrelated with the true signal, so they contribute pure error — hence validation MSE of 0.61, worse than the underfit line's 0.46, even though training MSE for degree 9 is nearly perfect. Degree 3 sits near the true model's effective complexity (the population signal has a dominant single oscillation over $[0,1]$ under this frequency, well-approximated by a cubic), so nearly all the reduction in training error going from degree 1 to degree 3 reflects genuine captured signal, and validation error drops correspondingly. Going from degree 3 to degree 9, training error keeps falling (guaranteed, by the nesting argument above) but validation error rises sharply — the signature of crossing from the productive regime into the overfitting regime, exactly the right half of the U-curve in the figure. A second, smaller trace makes the underfitting side concrete with real numbers. Suppose we instead fix degree at 1 but vary sample size $n \in \{5, 50, 500\}$:

Notice training and validation error converge toward the same nonzero floor (around 0.41–0.43) as $n$ grows, and neither approaches zero. More data does not fix underfitting — the gap between train and validation shrinks, but both stay stubbornly high, because the bottleneck is model bias (a line cannot represent a sine curve), not sample noise. This is the diagnostic contrast with overfitting: overfitting's gap shrinks with more data (variance falls), while underfitting's gap is already small and adding data does not move either curve toward zero.

The formal study of the tension between model flexibility and generalization emerged from statistics and learning theory across the 20th century, long before "overfitting" became standard machine-learning vocabulary.

Every production machine learning pipeline is architected around this tension. Search ranking and recommendation systems (used by web search engines and streaming platforms) hold out validation data specifically to catch models that have overfit to historical click patterns rather than learning genuinely predictive user preferences. Autonomous driving perception systems must generalize to weather, lighting, and road conditions never seen in training, so validation on deliberately distribution-shifted held-out sets is standard to catch overfitting to the training distribution's idiosyncrasies. Medical diagnostic models trained on data from one hospital system are routinely evaluated on external hospitals precisely to detect overfitting to site-specific artifacts (scanner type, patient demographics) rather than the actual disease signal. Large language model training uses validation loss curves over the course of training to decide when additional training epochs stop helping and start memorizing, informing decisions about dataset size, model size, and stopping point (related to the "compute-optimal scaling" tradeoffs that are themselves a large-scale instance of the bias-variance tradeoff). Regularization techniques such as weight decay, dropout, and data augmentation — the practical machinery introduced in Regularization — exist entirely because engineers need a tunable knob to move along the complexity axis without discretely changing the hypothesis space, and cross-validation and the train/validation/test protocol described here remain the universal diagnostic tool for locating where on that axis a given model sits.

Ask the tutor: How does the bias-variance decomposition mathematically prove that the U-shaped validation error curve must have an interior minimum?