Preprint Open access
Boosting and the Expressive Power of Simple Weak Learners via the $γ$-VC Dimension
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 on the structure of the base class. We study this phenomenon through the $γ$-VC dimension introduced by Alon et al. (STOC 2021). Our first re …