Rademacher complexity and generalization bounds
Measure a class by how well it can fit pure noise on the data you actually have. That one idea gives data-dependent bounds, dimension-free margin and norm bounds, and — via PAC-Bayes — non-vacuous bounds for deep (stochastic) networks. It also explains precisely why most classical bounds say nothing about them.
50 min
After this lesson you can
- Define the empirical Rademacher complexity and compute it for simple classes
- State the Rademacher generalization bound for binary classification and read each term
- Derive the dimension-free bound for norm-bounded linear predictors
- State the PAC-Bayes bound and explain the roles of the prior and the posterior
- Explain why capacity-based bounds are vacuous for networks that fit random labels, and what Dziugaite and Roy did about it
In this lesson
- Fitting noise, formally
- The bound
- Norms, not counts: the linear case
- PAC-Bayes: a prior over hypotheses
- Why the classical bounds say nothing about deep networks
- In code
- What to take from all this
This lesson is part of Descent Pro
Descent Pro unlocks every lesson on the route, from base camp to the summit. Every plan starts with a free trial.