Boosting and the Expressive Power of Simple Weak Learners via the $\gamma$-VC Dimension

Arthur da Cunha, Kasper Green Larsen, Liang-Yu Zou

Boosting converts weak hypotheses with a small edge over random guessing into highly accurate predictors, but the expressive power of the resulting classifier can depend strongly o…