Learning Theory

Learning Theory

1. Question

How many examples guarantee low test error? Answer links error gap to hypothesis complexity and $n$.

2. Core Bound (intuition)

With probability $1 - δ$:

Complexity = VC-dimension / Rademacher (roughly, parameters / margin). More data $n$ → smaller gap; simpler class → smaller gap.

3. VC Dimension (one line)

Largest $m$ such that $H$ shatters $m$ points (realizes all $2^{m}$ labellings). Lines in $R²$: VC $=3$. Higher VC → needs proportionally more data.

4. Takeaways

• Regularization / margin reduces effective complexity (why SVM generalizes).
• Structural risk minimization: minimize train error + complexity penalty jointly.
• Theory is loose — use CV in practice, bounds for insight.

5. Exam Points

• State test ≤ train + complexity/$\\sqrt{n}$ form — 5 marks, very frequent.
• Define VC dimension + shattering — 3-5 marks, frequent.
• Why margin / regularization helps generalization — 3 marks.