The Many Faces of Optimal Weak-to-Strong Learning

This paper presents an efficient and simple weak-to-strong learner that has optimal in-expectation error. In weak-to-strong learning, we are given a dataset of $m$ points from a distribution, and a $\gamma$-weak learner that returns hypotheses from a class of VC dimension $d$. AdaBoost, which is a textbook weak-to-strong learner, makes $O(\ln(m)/\gamma^2)$ total invokations to the weak learner, and the best-known analysis for it shows that it suffers an in-expectation error $O\left(\frac{d\ln(m/d)\ln(m)}{\gamma^2 m}\right)$. Larsen and Ritzert (2022) constructed a weak-to-strong learner, that has expected error $O(d/\gamma^2 m)$. Furthermore, they showed that this is the optimal error that one can obtain from $m$ training examples and a $\gamma$-weak learner. However, the weak-to-strong learner by Larsen and Ritzert (2022) makes $O(m^{0.8}/\gamma^2)$ invokations to the weak learner --- which is exponentially worse than AdaBoost. Another bagging-based-boosting algorithm due to Larsen (2023), which also achieves the optimal expected error of $O(d/\gamma^2m)$, makes only $O((\ln m)^2/\gamma^2)$ invokations to the weak-learner. This is still a log factor worse than AdaBoost. Could we then hope to obtain a tighter analysis of the error of AdaBoost, and show that it obtains the optimal error with only $O(\ln(m)/\gamma^2)$ invokations to the weak learner? Unfortunately, no. Høgsgaard et al. (2023) showed that AdaBoost necessarily suffers an expected error which is at least $\Omega(d\ln(m)/\gamma^2 m)$.

Can we then at least shoot for a different weak-to-strong learner that attains the optimal expected error of $O(d/\gamma^2m)$, and also invokes the weak learner only $O(\ln(m)/\gamma^2)$ many times (which is the AdaBoost gold standard)? This paper answers the question in the affirmative, with a remarkably simple weak-to-strong learner that they call Majority-of-29. The algorithm is exceedingly simple to describe: Partition the training dataset into 29 disjoint sub-samples of size $m/29$ each. Run AdaBoost on each subsample, and return the majority vote over the AdaBoosts. Since each AdaBoost makes only $O(\ln(m)/\gamma^2)$ calls to the weak learner, and we run a constant (29) many AdaBoosts, the total number of calls to the weak learner is $O(\ln(m)/\gamma^2)$ as required. Further, using an analysis similar to the recent majority-of-3-ERMs algorithm of Aden-Ali et al. (2023), the authors are able to show that the expected error of Majority-of-29 is $O(d/\gamma^2m)$. The analysis from that work does not extend in a trivial manner, and the authors are required to make appropriate technical modifications and enhancements. The number 29 emerges from the analysis --- the authors require showing a new generalization bound for margin-based classifiers (they show a generalization bound of the order $O((d/\gamma^2m)^{\alpha})$), for $\alpha=1/14$, and this lets them obtain the result for Majority-of-$g(\alpha)$, where $g(\alpha)=2/\alpha+1$. The authors conjecture that the analysis of the generalization bound could be improved, and a Majority-of-3 might well suffice for optimal error.

Finally, the authors also do a (somewhat-limited) empirical comparison of the the performances of the three optimal weak-to-strong learners mentioned above (LarsenRitzert, Bagging-based-boosting, Majority-of-29) as well as AdaBoost. The authors find that for large datasets, Majority-of-29 outperforms the other optimal weak-to-strong learners. On the smaller datasets, the authors find that Bagging-based-boosting outperforms Majority-of-29.

This paper introduces a new Boosting algorithm, MAJORITY-OF-29, which achieves provably optimal sample complexity and is remarkably simple to implement. The algorithm partitions the training data into 29 disjoint subsets, applies AdaBoost to each subset, and combines the resulting classifiers through a majority vote. This approach not only matches the asymptotic performance of AdaBoost but also improves upon previous weak-to-strong learners in terms of simplicity and runtime efficiency.

The authors present a new boosting algorithm: partition training data into 29 pieces of equal size, run AdaBoost on each, and output the majority vote over them. The authors prove that the sample complexity of MajorityVote29 is optimal and its running time is the same order as AdaBoost. Experimental results are also attached, which corroborate their theoretical findings.

We would like to thank all reviewers for their thoughtful reviews.

Let us add one general remark that we will leave to the reviewers whether to include in their evaluation of the submission or not. Recently we found a way to improve the result to the majority of 5 instead of majority of 29. The reason why this improvement is possible is due to us becoming aware of a stronger statement of corollary 5 which improves the previous $O((d/(\gamma^2m)^{1/14})$ bound to $O((d/(\gamma^2m)^{1/2})$. For the intuition of why this leads to a majority of 5, we recall from the proof sketch that we needed to combine $2/\alpha+1$ many AdaBoosts where $\alpha$ is the number of the exponent that we obtain in corollary 5 ($O((d/(\gamma^2m))^{\alpha}$), which now can be set equal to $\alpha=1/2$ and thus we get that we only need to combine $2/\alpha+1=5$ many AdaBoosts to get the optimal in expectation sample complexity. Fortunately, out experiments also included Majority-of-5 so no significant changes to the paper are needed. The new proof only changes (and simplifies) the material in the appendix.

Also, as we wish to be assessed as a theory paper, so primarily on the theoretical contribution, and added the experiments merely as a very first pilot study, let us add that if the reviewers all feel the paper would be stronger without the experiments, we would like to remove the experiments.

If there is one thing that boosting teaches us, it is the value of simple and original ideas whose use relies on nice technical tricks. This paper is a good example which deserves to be seen by the NeurIPS audience.

Regarding experiments: those have generated substantial discussion, for a paper which is theoretical in nature. Looking at the paper, one can say that there has been substantial work in polishing the theory while the experiments comparatively look a bit "let down" (it only takes a look at Figs 1 and 2) and their presentation could have been substantially simplified. But the merits of the paper are principally in its theory. I concur with the idea that those experiments could be changed. A suggestion: reduce the 1.5 page to 0.5 page that would take place in a "Discussion" section before conclusion, along with the story around Corollary 5 (below) and the limitations of the work, currently a single section. Put all that is not necessary in Appendix (dataset descriptions, etc.), eventually find a summary plot / table, insist on the fact that the experiments are preliminary / pilot, tone down the narrative. Again, the theory is the message.

Regarding the replacement of Corollary 5, there are two strategies: the first would be to just replace Corollary 5 with its stronger version and change the rest. I do not support this because the change has not been reviewed. Another strategy would be to use the "Discussion" Section (above) to add a subsection on a potential change to Corollary 5, with a new Corollary properly stated and how it changed the 29 -> 5 split. Hopefully both Corollaries have the same backbone. Extensive proof in Appendix required and proofchecked.

With this, make the why "The answer is 29" clear from Section 1.1: write that 29 is an integer that allows for the appropriate convergence of a series handling the algorithm's error, discuss the 29 -> 5, etc. . This allows to install the formal decorum.