Overfitting and Regularization Strategies

Overfitting occurs when a learning algorithm fits patterns in the training data that do not generalize — including sampling noise, mislabeled points, and idiosyncrasies of the specific finite sample — rather than the underlying data-generating process. Its mirror image is underfitting, where the model is too simple to capture even the true signal. Both are failures of generalization: the gap between performance on data the model has seen and performance on data drawn from the same distribution but never observed during training. The precise mathematical lens is the bias-variance decomposition. Consider a regression problem where the true relationship is

and we train an estimator $\hat f_D(x)$ on a random training set $D$. For a fixed test point $x$, the expected squared error over the randomness of both $D$ and $\epsilon$ decomposes as

Bias measures how far the average model (over hypothetical resamplings of the training set) is from the truth — it is large when the hypothesis class is too restrictive. Variance measures how much the fitted model would change if trained on a different sample from the same distribution — it is large when the model is complex enough to chase sampling noise. Model capacity — informally, the richness of the function class a model can represent — is the dial that trades one against the other: increasing capacity (more layers, more parameters, less constraint) tends to lower bias but raise variance, and vice versa. Overfitting is precisely the high-variance regime; underfitting is the high-bias regime.

Regularization is any modification to a learning algorithm that is intended to reduce generalization error, typically by reducing variance at some acceptable cost in bias. This is deliberately a broad definition — it does not require an explicit penalty term. It is convenient to organize regularizers into four families: 1. Parameter-norm penalties — add a term to the loss that discourages large or complex parameter values (e.g., $L_2$ weight decay, $L_1$ sparsity). 2. Structural / capacity constraints — shrink the hypothesis space directly, e.g., weight sharing, smaller architectures, or randomly disabling units (dropout). 3. Noise injection — perturb inputs, weights, or activations during training so the model cannot rely on any single fragile feature. 4. Data-side interventions — increase effective sample size or coverage via more data, data augmentation, or early stopping (which limits how long the optimizer is allowed to fit noise). Every technique later in this course — dropout, early stopping, data augmentation, batch normalization's incidental regularizing effect — is best understood as attacking variance from one of these four angles, using $L_2$ weight decay as the reference point you already know.

Diagnosing and treating overfitting is a loop: measure the generalization gap, identify whether the problem is bias or variance, and apply the family of regularizer that targets it. The following procedure is the standard workflow used in practice (and mirrors how automated hyperparameter search / early-stopping logic is implemented). ``` ALGORITHM: Diagnose-and-Regularize(model_family, train_set, val_set, budget)

# Phase 1: baseline capacity sweep to locate the bias/variance regime for capacity in increasing_sequence(model_family): model <- fit(capacity, train_set) # optimize until convergence train_err[capacity] <- error(model, train_set) val_err[capacity] <- error(model, val_set) k <- argmin_capacity( val_err ) # sweet spot on the U-curve gap <- val_err[k] - train_err[k] if train_err[k] is large (both errors high, gap small): diagnosis <- "underfitting (high bias)" action <- "increase capacity, reduce regularization, engineer better features" else if gap is large (train_err small, val_err much larger): diagnosis <- "overfitting (high variance)" action <- "apply regularization family (see below), or gather more data" else: diagnosis <- "well balanced" action <- "ship it, monitor on held-out / production data"

# Phase 2: apply targeted regularization, then re-validate for lambda in candidate_strengths: model_reg <- fit(capacity = k, train_set, penalty = lambda R(theta)) val_err_reg[lambda] <- error(model_reg, val_set) lambda <- argmin_lambda( val_err_reg ) return fit(capacity = k, train_set, penalty = lambda R(theta)) ``` Two subroutines deserve elaboration because they are the mechanisms that actually change what the optimizer converges to.

Weight decay ($L_2$ penalty), the reference mechanism. The training objective becomes

and gradient descent on $J$ gives the update

The factor $(1-\eta\lambda)$ shrinks every weight multiplicatively at each step, independent of the gradient signal — hence the name weight decay. This directly reduces the effective capacity of the model: weights are pulled toward zero unless the data provides a persistent gradient signal to counteract the pull, so only genuinely useful, well-supported directions in weight space survive with large magnitude.

Model-selection loop. The outer sweep over `capacity` and the inner sweep over `lambda` are both instances of the same idea: trace out the U-shaped validation-error curve as a function of a single complexity-controlling knob, and pick the minimum. This is why $L_2$ regularization strength, network width/depth, polynomial degree, and (as you will see next) dropout probability and early-stopping patience are all "the same kind of hyperparameter" from a bias-variance standpoint — they all slide the model along the capacity axis.

``` +-----------------------------------------------------------+ | Regularization taxonomy (4 families) | +-----------------------------------------------------------+ | 1. Parameter-norm penalties : L2 weight decay, L1 (Lasso) | | 2. Structural constraints : smaller nets, weight | | sharing, dropout (foreshadowed) | | 3. Noise injection : input noise, dropout, | | label smoothing | | 4. Data-side interventions : more data, data | | augmentation, early stopping (both foreshadowed) | +-----------------------------------------------------------+ ```

Time complexity. Adding an $L_2$ penalty $\frac{\lambda}{2}\|\theta\|_2^2$ changes the per-step cost negligibly: computing $\nabla_\theta \|\theta\|_2^2 = 2\theta$ is $O(P)$ where $P$ is the number of parameters, strictly dominated by the $O(P)$-to-$O(P \cdot n)$ cost of a forward/backward pass over a batch of $n$ examples. So weight decay is asymptotically free — it does not change the order of per-iteration cost, only the constant. The outer model-selection loop (sweeping capacity and $\lambda$) multiplies total training cost by the number of grid points tried, which is the real practical cost of regularization tuning, not the penalty itself.

Space complexity. No extra parameters are introduced; at most one extra scalar accumulator per weight is needed if decay is fused into an optimizer's update rule (e.g., AdamW), so space remains $O(P)$, unchanged in order.

Why weight decay reduces variance — a correctness argument. Consider linear regression with design matrix $X\in\mathbb{R}^{n\times d}$ and targets $y$. Ordinary least squares minimizes $\|y - X\theta\|_2^2$, giving $\hat\theta_{\text{OLS}} = (X^\top X)^{-1}X^\top y$. Ridge regression (the linear case of $L_2$-penalized training) minimizes $\|y-X\theta\|_2^2 + \lambda\|\theta\|_2^2$, giving

Two facts follow directly from this closed form: 1. Bias increases with $\lambda$. Since $\hat\theta_\lambda \to 0$ as $\lambda \to \infty$, and $\mathbb{E}[\hat\theta_\lambda] \ne \theta^\star$ for $\lambda > 0$ in general, ridge estimates are biased toward zero — the penalty deliberately introduces bias. 2. Variance decreases with $\lambda$. The covariance of the ridge estimator is

and one can show this matrix decreases (in the Loewner / positive-semidefinite order) as $\lambda$ increases, because adding $\lambda I$ before inverting shrinks every eigenvalue-direction's sensitivity to noise in $y$. In particular, when $X^\top X$ is ill-conditioned (near-singular, as happens with correlated or high-dimensional features), $(X^\top X)^{-1}$ has huge eigenvalues and OLS variance explodes; adding $\lambda I$ caps those eigenvalues at $1/\lambda$ at most, directly bounding variance. This is the exact mechanism that generalizes qualitatively to deep networks: penalizing $\|\theta\|_2^2$ damps the model's sensitivity to small perturbations of the training sample, which is variance, at the cost of pulling the fit away from the unconstrained optimum, which is bias. The bias-variance decomposition guarantees that as long as the variance reduction outweighs the bias increase, expected test error strictly decreases — this is why an intermediate $\lambda^\star > 0$ (found by the sweep in the pseudocode) typically beats both $\lambda=0$ (unregularized, high variance) and $\lambda \to \infty$ (all-bias, model collapses to zero).

Honest tradeoffs. Regularization strength is itself a hyperparameter that must be tuned on a validation set, so its use adds an outer loop and computational cost; too much regularization silently converts an overfitting problem into an underfitting one; and the bias-variance framework, while exact for squared loss, is only a useful heuristic (not an exact decomposition) for other losses such as cross-entropy or 0/1 classification error, where bias and variance interact multiplicatively rather than additively.

Consider fitting polynomials of increasing degree to $n=15$ noisy samples of $y = \sin(2\pi x) + \epsilon$, $\epsilon \sim \mathcal N(0, 0.1^2)$, and evaluating on a held-out set of 200 points from the same distribution. Degree plays the role of "capacity."

Now fix the capacity at degree 14 (deliberately over-parameterized) and sweep the $L_2$ penalty $\lambda$ on the polynomial coefficients, exactly mirroring the ridge-regression argument above:

Two things are worth noticing. First, degree-14 with $\lambda = 10^{-1}$ achieves validation error (0.022) essentially matching the "correctly sized" degree-5 unregularized model (0.021) — this is the practical payoff of regularization: you do not need to know the right capacity in advance if you can instead over-parameterize and regularize. Second, both sweeps produce the same U-shape in validation error, confirming that "capacity" and "regularization strength" are two different knobs turning the same bias-variance dial.

The bias-variance tradeoff and its regularization remedies emerged from statistics decades before deep learning existed, then were re-discovered and re-purposed as neural networks grew large enough for overfitting to become the dominant practical concern.

Every production machine learning system fights overfitting continuously, because real-world data distributions shift and finite training sets can never fully specify the desired function. Search-ranking and recommendation systems apply $L_2$ and $L_1$ penalties (and later, dropout-style techniques) to prevent overfitting to popular items or historically dominant behaviors, ensuring the model still ranks novel or cold-start items sensibly. Computer vision pipelines routinely combine weight decay with the data-side techniques foreshadowed here — early stopping and augmentation — because image models are typically over-parameterized relative to any single dataset. Large language model pretraining uses weight decay (often bundled into optimizers like AdamW) as one of only a handful of regularizers applied at trillion-parameter scale, alongside architectural and data-side choices, because it is essentially free computationally yet measurably improves downstream generalization. Financial risk and medical diagnosis models are held to strict validation protocols precisely because the bias-variance framework predicts, and regulators now require evidence, that a model performing well only on its training cohort is unsafe to deploy. Autonomous vehicle perception stacks must generalize to weather, lighting, and geography never seen during training, making variance reduction — not just training accuracy — the primary engineering metric tracked in continuous integration.

Ask the tutor: How does implicit regularization from stochastic gradient descent interact with explicit techniques like weight decay in modern over-parameterized networks?