Overview of Statistical Learning Theory Part 1
summary
Survey of classical statistical learning theory that pins down learnability: VC dimension and Sauer's Lemma give tight sample complexity and explain the sharp phase transition; empirical risk minimization and minimum description length (short programs ≈ 100 lines → log-size ≈ 60k → samples ~ a few 100k) provide practical templates; computation is the real bottleneck; structured risk minimization becomes a bicriteria / Pareto frontier view (regularization path, early stopping, optimistic 1/ε vs 1/ε^2 rates) that matches how models are chosen in practice.
AI-written summary · about
chapters (13)
- 0:00Statistical learning theory intro
- 1:48Machine learning history
- 10:21Machine learning paradigm
- 13:58Supervised learning error
- 16:28No free lunch theorem
- 23:35Error decomposition model selection
- 27:52Statistical learning trivial?
- 31:05Beyond VC dimension
- 36:46PAC learning theorem
- 42:31Beyond flat bias
- 58:25Complexity measures SRM
- 1:08:29Structured risk minimization in practice
- 1:16:16Closing remarks
related talks
59mTutorial: Statistical Learning Theory and Neural Networks I
33mLearning and Testing Structured Distributions
01h 21mTutorial: Implicit Bias I
11mLinear Predictors in Reinforcement Learning: ...
23mComparative Learning: A Sample Complexity Theory for Two Hypothesis Classes
01h 04mStatistical Physics and Computation in High Dimension
01h 02mTheory and Big Data
48mPredicting from Noisy and Incomplete Data: Some Perspectives from Computational Learning Theory