Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates how the expressive power of boosted classifiers is influenced by the base learner's structure, quantified by the $\gamma$-VC dimension. The authors establish that this parameter fundamentally governs weak-to-strong learning sample complexity, up to a constant factor. They also refine the connection between the standard VC dimension and the $\gamma$-VC dimension, and provide tighter bounds for decision stumps and axis-parallel rectangles.
The $\gamma$-VC dimension, not just the standard VC dimension, dictates the sample complexity of boosting weak learners into strong predictors.
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 result shows that this parameter characterizes the sample complexity for weak-to-strong learning up to a constant factor scaling in $γ$. We then sharpen the general relationship between the classic VC dimension and the $γ$-VC dimension. Finally, we also give improved upper and lower bounds on the $γ$-VC dimension for the fundamental concept classes of decision stumps and axis-parallel rectangles in $\mathbb{R}^d$.