Boosting, Voting Classifiers and Randomized Sample Compression Schemes
<|reference_start|>Boosting, Voting Classifiers and Randomized Sample Compression Schemes: In boosting, we aim to leverage multiple weak learners to produce a strong learner. At the center of this paradigm lies the concept of building the strong learner as a voting classifier, which outputs a weighted majority vote of the weak learners. While many successful boosting algorithms, such as the iconic AdaBoost, produce voting classifiers, their theoretical performance has long remained sub-optimal: the best known bounds on the number of training examples necessary for a voting classifier to obtain a given accuracy has so far always contained at least two logarithmic factors above what is known to be achievable by general weak-to-strong learners. In this work, we break this barrier by proposing a randomized boosting algorithm that outputs voting classifiers whose generalization error contains a single logarithmic dependency on the sample size. We obtain this result by building a general framework that extends sample compression methods to support randomized learning algorithms based on sub-sampling.<|reference_end|>
@article{da cunha2024boosting,,
    title={Boosting, Voting Classifiers and Randomized Sample Compression Schemes},
    author={Arthur da Cunha, Kasper Green Larsen, Martin Ritzert},
    journal={arXiv preprint arXiv:2402.02976},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.02976},
    primaryClass={cs.LG stat.ML}
}