Sample Complexity
How many training examples are needed to learn a concept to accuracy ε with confidence 1−δ? Explore how VC dimension, error tolerance, and confidence interact.
Agnostic PAC bound: m ≥ O((d + log(1/δ)) / ε²)
Realizable PAC bound: m ≥ O((d·log(1/ε) + log(1/δ)) / ε)
Lower bound: Ω(d/ε + log(1/δ)/ε) examples are always necessary — this is tight up to log factors.
The gap between realizable and agnostic cases is a factor of 1/ε, reflecting the difficulty of handling noise.