Sample Complexity Bounds: Finite and Infinite Hypothesis Classes

The double-descent lesson showed a case where naive parameter-counting misleads. This note supplies the actual formal machinery — building from two elementary probability lemmas up to Vapnik's VC-dimension theorem — that answers the deeper question underlying this entire topic: under precisely what conditions, and after how much data, can we prove that a learning algorithm's training-set performance will transfer to new data? This is, in the CS229 notes' own words, "many would argue, the most important theorem in all of learning theory."