The Many Faces of Optimal Weak-to-Strong Learning
This work addresses the need for efficient and simple boosting algorithms in machine learning, offering a practical solution with potential performance gains on large datasets, though it appears incremental in nature.
The authors tackled the problem of designing a sample-optimal boosting algorithm by introducing a simple method that partitions training data, runs AdaBoost on each part, and combines classifiers via majority vote, achieving provably optimal sample complexity and the fastest runtime among such algorithms.
Boosting is an extremely successful idea, allowing one to combine multiple low accuracy classifiers into a much more accurate voting classifier. In this work, we present a new and surprisingly simple Boosting algorithm that obtains a provably optimal sample complexity. Sample optimal Boosting algorithms have only recently been developed, and our new algorithm has the fastest runtime among all such algorithms and is the simplest to describe: Partition your training data into 5 disjoint pieces of equal size, run AdaBoost on each, and combine the resulting classifiers via a majority vote. In addition to this theoretical contribution, we also perform the first empirical comparison of the proposed sample optimal Boosting algorithms. Our pilot empirical study suggests that our new algorithm might outperform previous algorithms on large data sets.