Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper presents a new algorithm that constructs a strong learner from a weak learner with less sample complexity than existing methods by two logarithmic factors. Matching upper and lower bounds for sample complexity shows that the algorithm is optimal up to multiplicative constants. In doing so, the algorithmic analysis uses a new generalization bound for voting classifiers with large margins. This work resolves open issues with respect to the sample complexity of the problem of constructing a strong learner from a weak learner.
strengths_and_weaknesses: The paper provides a theoretical contribution to an important problem in practice. This includes a new algorithm that constructs a strong learner from a weak learner using less training data than previous work, and showing that the algorithm is optimal up to multiplicative constants and resolves the sample complexity of the problem of constructing a strong learner from a weak learner.

The paper does not provide any empirical results that illustrate the theoretical results in practice, but this is not a major concern given the theoretical contribution of the paper. The paper leaves open a few important related theoretical problems, but the theoretical contributions are strong enough on their own.

questions: Is it possible to extend the work in the paper to address the few important related open theoretical problems? Or would a completely new approach be needed to address these open problems? The paper should at least discuss this.

Maybe it is just a formatting issue, but it is somewhat strange to have the first theorem listed as Theorem 3 as a result of the two preceding definitions Definition 1 and Definition 2. Can this be fixed? I do not believe this is a NeurIPS standard.

limitations: Yes
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers the number of training examples to build a strong learner from a weak learning algorithm.
It presents a new algorithm with a bound that is two logarithmic factors lower than the state of the art.
In addition, it includes a lower bound asymptotically matching the upper bound.

The algorithm uses a sub-sampling scheme from Hanneke.  On each of the many subsamples, a boosting algorithm runs a weak learner guaranteeing edge $\gamma/2$ on the given sub-sample (where $\gamma$ is the edge of the weak learning algorithm) to produce an intermediate voted hypothesis.  
These resulting intermediate hypotheses are then thresholded and majority (unweighted) voted to produce the final classifier.

A new theorem (Theorem 6) is applied to show each subsample suffices for the thresholded intermediate hypotheses to have generalization error at most 1/200 (with high probability).   


strengths_and_weaknesses: It is very nice that the upper and lower bounds match asymptotically.

Although only a minor limitation, it seems like Theorem 6 requires that the weak learners be classifiers rather “confidence rated”.

questions: Are there situations where AdaBoost is known to require at least $\Omega$(expression in (1) )  examples for strong learning?
This seems implied by the page 3 line 80 comment, but it is not stated precisely.  

limitations: yes
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper provides a new weak to strong learning algorithm that has less sample complexity compared to the best known algorithms. It also proves that the new algorithm achieves the optimal sample complexity by driving a lower bound. The optimal sample complexity of weak to strong learning algorithms was unknown before this work, but this work settles the sample complexity of the classic problem
of constructing a strong learner from a weak learner.
strengths_and_weaknesses: - The paper solves an important open problem regarding the sample complexity of weak to strong learning algorithms by improving the sample complexity of AdaBoost by two logarithmic factors. For the theoretical analysis of the newly proposed algorithm, they also derive a new generalization bound for voting classifiers that improve the Breiman's result.

- AdaBoost is a voting classifier. They justify that a simple majority vote is not sufficient for obtaining an optimal sample complexity and an algorithm based on a majority of majorities is indeed necessary.

- The paper is well written and easy to follow.

-It is of sufficient interest to the audience of NeurIPS.

- I did not check the proof in the supplementary material but the technical proof seems to be sound.

Weaknesses:
The paper does not have any experimental results. I recommend the authors to incorporate some experiments to compare the sample complexity of their algorithm to other weak to strong learning algorithms such as AdaBoost on real data sets. They can also move some of parts of the proof to the supplementary material and instead incorporate some experimental results.
questions: I have a quick question regarding the definition of weak learning. In Definition 1, the confidence probability, $\delta$, is a fixed constant. However, according to Definition 7.1 of "Foundation of Machine Learning by M. Mohri", the statement must hold for any arbitrary $\delta>0$. Please give an explanation on these two different definitions.
limitations: The paper does not have any negative societal impact.
review_title: null

Meta-review: metareview: The paper makes a nice progress on our understanding of boosting
confidence: Certain
Decision: Accept