Generalization III
summary
Uses Rademacher symmetrization to reduce uniform deviations to analyzable averages and gives classification bounds like sup deviation = O(sqrt(d log n / n)) when VC dimension d is finite. Shows surrogate ramp loss (1/γ-Lipschitz) lets Rademacher control real-valued predictors with an extra 1/γ factor, explaining why test error can drop after in-sample zero. Gives compression bounds ~O(sqrt(k log n / n)) and links kernel ridge to uniform stability β = O(1/(λ n)) via strong convexity.
AI-written summary · about
chapters (12)
- 0:00Start
- 3:28Recap
- 6:57Classification and Rademacher Complexity
- 8:46Controlling Rademacher Complexity: Growth Function
- 14:41Vapnik-Chervonenkis Dimension: "Sauer's Lemma"
- 22:58VC-Dimension of Neural Networks
- 37:08Recall
- 40:24Rademacher Complexity for Lipschitz Loss
- 43:41Example: Linear Classifiers
- 48:20Risk versus surrogate risk
- 51:21Generalization: Margins and Size of Parameters
- 54:55Compression Set
related talks
01h 30mHigh-Dimensional Statistics I
01h 01mRobustness, Stochastics, Uncertainty 2
44mActive Regression via Linear-Sample Sparsification
01h 03mOverview of Statistical Learning Theory Part 2
41mGeneralization Bounds for Uniformly Stable Algorithms
01h 01mRobustness, Stochastics, Uncertainty 1
01h 02mPrediction, Generalization, Complexity: Revisiting the Classical View from Statistics Part 2
59mTutorial: Statistical Learning Theory and Neural Networks I