Revisiting Agnostic Boosting
Arthur da Cunha, Mikael Møller Høgsgaard, Andrea Paudice, Yuxin Sun
Boosting is a key method in statistical learning, allowing for converting weak learners into strong ones.While well studied in the realizable case, the statistical properties of weak-to-strong learning remain less understood in the agnostic setting, where there are no assumptions on the distribution of the labels.In this work, we propose a new agnostic boosting algorithm with substantially improved sample complexity compared to prior works under very general assumptions.Our approach is based on a reduction to the realizable case, followed by a margin-based filtering step to select high-quality hypotheses.Furthermore, we show a lower bound on the sample complexity of agnostic boosting, which matches our upper bound up to logarithmic factors.