Learning Theory

The "why" behind every practical ML decision: why we hold out test sets, why we regularize, what "learning" formally means.

Table of contents

1. The learning problem
2. Generalization and train/val/test split
3. Bias-variance decomposition
4. Overfitting and underfitting
5. Regularization: theory and methods
6. Cross-validation
7. VC theory and PAC learning (overview)
8. Model complexity and the no-free-lunch theorem
9. Data splits and common mistakes

1. The learning problem

1.1 Setup

• Input space $\mathcal{X} = \mathbb{R}^p$ (features).
• Output space $\mathcal{Y}$ (regression: $\mathbb{R}$; classification: $\{1,\ldots,C\}$).
• Unknown distribution $P(\mathbf{x},y)$ that generates the data.
• Training set $\mathcal{D} = \{(\mathbf{x}_i, y_i)\}_{i=1}^n$ sampled i.i.d. from $P$.
• Hypothesis class $\mathcal{H}$: set of candidate functions $h: \mathcal{X} \to \mathcal{Y}$ the algorithm searches over.
• Loss function $\ell(h(\mathbf{x}), y)$: penalty for a prediction.

1.2 Expected and empirical risk

Expected (true) risk:

This is what we ultimately care about: performance on *new* unseen data.

Empirical risk (training loss):

This is observable. Empirical risk minimization (ERM): find $\hat{h} = \arg\min_{h\in\mathcal{H}} \hat{R}(h)$.

The fundamental problem: $\hat{R}(\hat{h})$ underestimates $R(\hat{h})$ because we optimized on the same data we are evaluating on. The gap $R(\hat{h}) - \hat{R}(\hat{h})$ is the generalization gap.

2. Generalization and train/val/test split

2.1 Why three splits?

Using the test set to make *any* decision (including "I'll keep this model because it worked on test") inflates your estimate of generalization. This is called test set contamination.

2.2 Typical splits

• 60/20/20 (train/val/test) or 70/15/15 — common for moderate datasets.
• k-fold CV — when data is small, no permanent val set (see §6).
• Temporal splits for time series — future data never used to predict past (see note 10).

3. Bias-variance decomposition

3.1 Derivation (regression)

Fix a test point $\mathbf{x}$ and assume $y = f(\mathbf{x}) + \varepsilon$, $\mathbb{E}[\varepsilon]=0$, $\text{Var}(\varepsilon)=\sigma^2$.

For a learning algorithm $\mathcal{A}$ trained on dataset $\mathcal{D}$, let $\hat{f}_\mathcal{D}(\mathbf{x})$ be its prediction. Expected MSE over random training sets:

Derivation sketch: add and subtract $\bar{f} := \mathbb{E}_\mathcal{D}[\hat{f}_\mathcal{D}(\mathbf{x})]$:

Expand and take expectations; cross terms vanish.

3.2 Bias-variance tradeoff

As model complexity increases:

Bias:        ████████░░░░░░░░  (decreases)
Variance:    ░░░░░░░░████████  (increases)
Total error: ╲__________/      (U-shaped curve)

• High bias (underfitting): model too simple (e.g., fitting a line to curved data). Both train and test error are high.
• High variance (overfitting): model too complex (e.g., degree-100 polynomial on 20 points). Train error low, test error high.
• Sweet spot: right model complexity minimizes sum of bias² + variance.

3.3 What affects each term?

Bias is increased by:

• Small hypothesis class (e.g., only linear functions when truth is nonlinear).
• Heavy regularization (shrinks model toward a biased baseline).
• Wrong model assumptions.

Variance is increased by:

• Large model class (many free parameters).
• Small training set.
• Little regularization.

Practical rules:

• If train error ≈ test error and both are high → high bias → more model complexity, less regularization, more features.
• If train error ≪ test error → high variance → more data, regularization, fewer features.

4. Overfitting and underfitting

4.1 Overfitting

Model memorizes training data, including noise. Signs:

• Loss on training set continues to decrease but validation loss plateaus or increases.
• Large train/validation loss gap.

Causes:

• Too many parameters relative to data.
• Training too long (in iterative methods).
• Noisy features, irrelevant features.

4.2 Underfitting

Model too simple to capture the true pattern. Signs:

• Both train and validation loss are high.
• Adding more training data does not significantly improve either.

Causes:

• Too few parameters.
• Heavily constrained model class.
• Excessive regularization.

4.3 Learning curves

Plot train and validation loss vs. training set size $n$:

Loss
│
│ train ────────────────────
│                       \
│                        \________  validation
│
└──────────────────────────────── n

• If both curves are high and converging: high bias (add complexity).
• If large gap between them: high variance (add data or regularize).

5. Regularization: theory and methods

5.1 The regularization idea

Add a penalty term to the training loss to control complexity:

Higher $\lambda$ → stronger regularization → smaller model → higher bias, lower variance.

5.2 L2 regularization (Ridge / weight decay)

$\Omega(\mathbf{w}) = \|\mathbf{w}\|_2^2 = \sum w_j^2$.

Effect: shrinks all weights uniformly toward zero. Does not produce exact zeros (smooth penalty). Closed form for linear models. Probabilistic interpretation: Gaussian prior on weights.

Ridge regression: $\min_\mathbf{w} \|\mathbf{y}-\mathbf{X}\mathbf{w}\|^2 + \lambda\|\mathbf{w}\|^2$, solution: $\mathbf{w}^\star = (\mathbf{X}^\top\mathbf{X}+\lambda\mathbf{I})^{-1}\mathbf{X}^\top\mathbf{y}$.

Adding $\lambda\mathbf{I}$ makes the matrix strictly positive definite → always invertible → solves the ill-conditioned / collinear case.

Effective degrees of freedom: $\operatorname{tr}(\mathbf{X}(\mathbf{X}^\top\mathbf{X}+\lambda\mathbf{I})^{-1}\mathbf{X}^\top)$ — decreases as $\lambda$ increases.

5.3 L1 regularization (Lasso)

$\Omega(\mathbf{w}) = \|\mathbf{w}\|_1 = \sum |w_j|$.

Effect: promotes sparsity — many weights become exactly zero → automatic feature selection.

Why sparsity? Geometric argument: L1 ball has corners on axes; optimization tends to land on a corner where some coordinates are exactly zero.

Proximal operator (soft thresholding): the 1D Lasso proximal update for coordinate $j$:

where $z_j$ is the unconstrained coordinate update. This is used in coordinate descent for Lasso.

When to use Lasso: you believe few features are truly relevant (sparse signal).

5.4 Elastic Net

Combines both:

Advantages over pure Lasso: handles correlated features better (Lasso arbitrarily picks one from a correlated group; ElasticNet can keep all), always selects at most $n$ features.

5.5 Regularization via early stopping

In gradient descent, stopping before convergence implicitly regularizes. The number of iterations controls model complexity. Equivalent to a form of L2 regularization for some models (gradient flow argument).

5.6 Dropout (preview of DL)

During training, randomly zero out each neuron with probability $p$. Prevents co-adaptation. Equivalently trains an ensemble of $2^N$ sub-networks.

5.7 Data augmentation as regularization

Expanding the training set with label-preserving transformations (flips, crops, noise) reduces effective variance without adding parameters.

6. Cross-validation

6.1 Purpose

Estimate generalization performance when data is limited (can't afford a large held-out set) and to select hyperparameters.

6.2 k-fold CV

1. Partition data into $k$ roughly equal folds.
2. For $i = 1, \ldots, k$: train on all folds except fold $i$, evaluate on fold $i$.
3. Average the $k$ evaluation scores.

Bias-variance of CV: large $k$ → low bias (trains on nearly all data), high variance (each fold's test set is small). Small $k$ → faster, more biased. $k=5$ or $k=10$ is standard.

Leave-one-out CV (LOOCV): $k = n$. Unbiased but expensive and high variance.

6.3 Stratified k-fold

Preserve class proportions in each fold. Essential for imbalanced classification.

6.4 Nested CV (for hyperparameter tuning)

Inner loop: select hyperparameters (CV over train data). Outer loop: estimate test performance (CV over full data).

Without the outer loop, selecting hyperparameters via CV and reporting that CV score as your performance estimate is optimistic (you've peeked at which parameters "work").

6.5 Common CV mistakes

Rule: every step of the pipeline that "learns" from data (scaling, encoding, feature selection) must be fit only on training folds and applied to validation/test folds.

7. VC theory and PAC learning (overview)

7.1 PAC learning

Probably Approximately Correct (PAC) framework: algorithm $\mathcal{A}$ PAC-learns $\mathcal{H}$ if for any distribution $P$ and any $\varepsilon, \delta > 0$, using at most polynomially many samples:

"$\varepsilon$-close to the best in class, with probability at least $1-\delta$."

Sample complexity: how many samples are needed? For finite $|\mathcal{H}|$:

Grows logarithmically in $|\mathcal{H}|$ — even huge but finite classes are learnable.

7.2 VC dimension

For infinite hypothesis classes, VC dimension measures effective complexity.

Shattering: a set of $m$ points is shattered by $\mathcal{H}$ if for every labeling of those points, some $h\in\mathcal{H}$ correctly classifies them.

VC dimension $d_{VC}(\mathcal{H})$: largest set size that $\mathcal{H}$ can shatter.

Examples:

• Threshold classifiers on $\mathbb{R}$: $d_{VC} = 1$.
• Linear classifiers in $\mathbb{R}^n$: $d_{VC} = n + 1$.
• Neural networks: $d_{VC} = O(W \log W)$ where $W$ = number of weights.

Fundamental theorem of PAC learning (VC bound):

Takeaways:

• More data $n$ → smaller generalization gap.
• Higher VC dimension → larger gap (more complex model needs more data).
• Tighter for models with lower VC dimension.

8. Model complexity and the no-free-lunch theorem

8.1 Inductive bias

Every learning algorithm makes assumptions about the structure of solutions. This is its inductive bias. Without inductive bias, a model cannot generalize beyond the training set.

Examples: linear models assume linearity; SVMs with RBF kernel assume smoothness; Naive Bayes assumes conditional independence.

8.2 No-free-lunch (NFL) theorem

Statement: Averaged over all possible data distributions, every learning algorithm performs exactly the same (as random guessing on unseen data).

Implication: there is no universally best algorithm. Every algorithm makes assumptions. The right model requires domain knowledge. This is why practitioners choose models with inductive biases that match their data.

Do not misuse: NFL does not say "all models are equally good in practice." Real problems are not uniform over all distributions — real data has structure, and some algorithms exploit it better.

9. Data splits and common mistakes

9.1 Temporal data

• Always split by time: train on past, evaluate on future.
• Never use future information to construct features for past samples (temporal leakage).

9.2 Group-based data

• If samples within a group are correlated (e.g., multiple readings from one patient), do group k-fold: keep all samples from a group in the same fold.

9.3 Label leakage

• A feature is derived from or correlated with the label after the fact (e.g., using a column that was computed using the answer). Classic cause of "too good to be true" results.

9.4 Preprocessing leakage (the most common mistake)

WRONG:
  1. StandardScaler.fit_transform(all_data)
  2. train_test_split(...)
  3. Train model on train, evaluate on test

CORRECT:
  1. train_test_split(...)
  2. StandardScaler.fit(train), transform(train) and transform(test)
  3. Train model on train, evaluate on test

Any fit call must only see training data.

*File: notes/02_learning_theory.md — next: notes/03_linear_models.md*