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.

通过提出一种随机增强算法，我们构建了一个通用框架，将样本压缩方法扩展到支持基于子采样的随机学习算法，并输出具有单对数依赖性的投票分类器的泛化误差，相比于已知可实现的一般的弱到强学习器，我们的算法在训练样本数量方面具有更好的表现。

提升、投票分类器与随机样本压缩方案