cs.LGNov 9, 2026

Generalized Adaptive Boosting and the Geometry of Mistakes

Authors: Marco Bressan, Nataly Brukhim, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, Maximilian Thiessen

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 ZZ-learner, which returns weak hypotheses achieving joint false-positive/false-negative guarantees (FP,FN)(\mathrm{FP},\mathrm{FN}) from some set Z⊆[0,1]2Z \subseteq [0,1]^2. This formulation generalizes the standard notion of γγ-weak learning--recovered by taking Z={(z1,z2):z1+z2<1/2−γ}Z=\{(z_1,z_2): z_1+z_2<1/2-γ\}--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 ZZ 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 ZZ-learners without relying on the prior knowledge of ZZ, generalizing AdaBoost's ability to handle unknown margin parameters. Finally, we demonstrate that ZZ-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

Explore similar work

CardsList
  1. Tight Generalization Bound for AdaBoost

    Jul 29, 2026Mikael Møller HøgsgaardEnsemble LearningGeneralization Bounds