Advanced Topics · Machine Learning

Learning Theory

Watch lectures

Learning Theory

1. Question

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

2. Core Bound (intuition)

With probability 1−δ1 - δ:

test error≤train error+complexity+log(1/δ)n\text{test error} ≤ \text{train error} + \sqrt{\frac{\text{complexity} + log(1/δ)}{n}}

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

3. VC Dimension (one line)

Largest mm such that HH shatters mm points (realizes all 2m2^{m} labellings). Lines in R2R²: VC =3=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/sqrtn\\sqrt{n} form — 5 marks, very frequent.
  • Define VC dimension + shattering — 3-5 marks, frequent.
  • Why margin / regularization helps generalization — 3 marks.
Budget AppAndroid App

Pocketly on Android

Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.

← All Machine Learning modules