Boosting and the Expressive Power of Simple Weak Learners via the gamma-VC Dimension
Boosting turns simple weak learners into highly accurate predictors, but their expressive power depends on how complex the base class is. The paper introduces the $\gamma$-VC dimension to measure this complexity for weak-to-strong learning. It establishes relationships between classic VC dimension and $\gamma$-VC dimension and provides bounds for specific classes like decision stumps and axis-parallel rectangles.