Statistical Learning Theory

Statistical Learning Theory

1. Goal

Explain why minimizing train error works (or fails) and how much data is needed. Core: decompose error into bias + variance + noise.

2. Bias-Variance Tradeoff

For target $y = f(x) + noise$ with noise variance $σ²$:

• Bias: error from wrong assumptions (too simple → underfit).
• Variance: error from sensitivity to sample (too complex → overfit).
• Noise: irreducible.

simple model: high bias, low variance → underfit
complex model: low bias, high variance → overfit
best: middle (validation U-curve)

3. Overfitting vs Underfitting

	Train error	Test error	Fix
Underfit	high	high	bigger model, more features
Good fit	low	low	—
Overfit	very low	high	regularize, more data, simpler model

4. PAC Idea (how much data?)

With probability $1 - δ$, true error ≤ train error + complexity penalty that shrinks as $1 / \sqrt{n}$. More data $n$ → tighter gap; richer hypothesis class → needs more data.

5. Exam Points

• Bias-variance formula + diagram — 7 marks, most frequent theory question.
• Underfit vs overfit table + fixes — 5 marks, frequent.
• State PAC intuition (more data → smaller gap) — 3 marks.