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.

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