Generalized Adaptive Boosting and the Geometry of Mistakes
Organizations: Università degli Studi di Milano · Apple Research · Tel Aviv University · Google Research ·
Abstract
Not all mistakes are alike. For example, in medical diagnosis, false positive and false negative mistakes have a different impact and should not be aggregated. By revisiting the classical theory of boosting through this lens, we introduce the notion of -learner, which returns weak hypotheses achieving joint false-positive/false-negative guarantees from some set . This formulation generalizes the standard notion of -weak learning--recovered by taking --and allows for more flexible notions of weak learnability that account for the impact of the distribution on the achievable learning guarantees. This raises a natural question: which sets are boostable? We answer this by giving a complete geometric characterization that unifies, as special cases, both the classical boosting dichotomy and the recent multi-objective extension of Bressan et al. (COLT 2025). We also present an adaptive algorithm for boosting -learners without relying on the prior knowledge of , generalizing AdaBoost's ability to handle unknown margin parameters. Finally, we demonstrate that -learners can achieve confidence amplification. However, the analysis is significantly more involved than in classical boosting and relies on the centerpoint theorem from discrete and computational geometry.
Figures & tables
Statistical Learning Theory
Statistical learning theory studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.
See all 635 papers