Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper “Multiclass Boosting and the Cost of Weak Learning”  studies boosting in the multiclass regime, especially by focusing on the how number of classes k affects the resources required for boosting.

The contribution that I found most interesting is the demonstrated gap between the sample complexity dependence on the number of classes needed for boosting versus weak learning. (log(k) versus k^2). 

The other contribution of this paper is a modified boosting algorithm for the framework above.
main_review: I think the paper's contributions are interesting and worthwhile.  They are not groundbreaking contributions to the theory of multiclass boosting, but they elucidate some important aspects.  I would recommend acceptance subject to the following comments being addressed.

main comments

1. How is your Algorithm 1 distinguished from the multiclass boosting algorithm of Mukherjee and Schapire (2011)?  (As in, what does section 3 add on its own?)  Or is section 3 meant as a tool and inspiration to the tradeoff later shown?
2. It seems to me that Theorem 7 / Corollary 8 depend on a (justified) assumption where the weak learning oracle is used as a black box.  Otherwise, one could presumably use the upper bounds of [9] to find a linear combination of weak learners without the k^2 dependence.  I think this should be pointed out to avoid confusion. (Or please correct me if I am mistaken.)
3. Are lower bounds from Daniely et al. (2015) on multiclass learnability pertinent to your results? (You cite only their upper bounds.)

minor

l. 74 “which they proved to be necessary and sufficient” (who is “they”? You should state the authors’ names.)

Do these results point to any general principles for designing multiclass weak learners? (c.f. Reyzin (AAAI 2014) for such a discussion for the binary case.)

limitations_and_societal_impact: no concerns
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper presents an analysis of multiclass boosting, showing that the boosting problem itself is simpler to learn (in terms of the sample complexity wrt the number of classes), than the problem of producing acceptable weak learners which can be boosted.
main_review: It would be helpful to contrast the boosting algorithm in algorithm 1 against the other algorithms described in reference 13, especially Adaboost.MM, and to unify the notation a little (as this paper refers to sigma-gains, which are the cost matrices in ref 13).

The text after Theorem 6 is confusing. If any ERM learner can learn a gamma-realizable hypothesis with O(log(k)) sample complexity, then it would be helpful to clearly explain what restrictions force the weak learner to have a sample complexity of O(k^2).

Update: thank you for the responses, I think some of the clarifications for the other reviewers and I should be included in the final text.
limitations_and_societal_impact: The theoretical work is hard to place in the literature of boosting as there is little analysis of what the results imply for extant multiclass boosting algorithms, or the relative complexity of large multiclass problems. It's also unclear at what level the number of classes starts to be the dominant complexity issue for boosting weak learners. Much of the text says k > 2, but some sections require k >> 2, and I'm unclear as to the boundary between the two, or appropriate inferences to draw from the theory when applied to smaller problems.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper analyzes theoretically the resources required by multiclass boosting to guarantee convergence. Namely, the authors propose an AdaBoost algorithm variant tailored to solve multiclass tasks. The algorithm uses the standard classification loss function, as opposed to state-of-the-art multiclass AdaBoost algorithms that use tailored loss functions. The convergence of the proposed algorithm is guaranteed if the boosting sample complexity has a logarithmic dependency on the number of classes k in the training dataset and if the number of samples used by the weak learner at each boosting iteration has a k^2 complexity. The paper also shows that the weak learner must be best in class when the number of classes is very large, making each call to the weak learner oracle very costly / challenging.
main_review: In terms of originality, the paper proposes a novel theoretical analysis of multiclass boosting by using a multiclass variant of the AdaBoost algorithm. In contrast to state-of-the-art algorithms, the proposed method uses the standard classification loss function and does not convert the learning of the multiclass problem into multiple binary problems. 

In terms of significance, the paper provides a set of interesting theoretical findings regarding the resources required by multiclass boosting to guarantee convergence especially in the case of a large number of classes. It would be good to understand how these findings could be applied (if possible) to other boosting schemes, such as gradient boosting. In other words, how general are the theoretical findings for all the multiclass boosting schemes? Also, how can these findings be used in practice. 

In terms of clarity and quality, the paper could be improved as suggested in the next paragraphs:

- What is the definition of an "easy-to-learn" base class, and what would be an example of such a class, a tree stump? Are decision trees of max_depth N > 1 an easy-to-learn base class?
- It would be good to mention the boosting resources under study also in the abstract.
- A very popular boosting framework nowadays is gradient boosting. A discussion would be appreciated if the authors could explain how the findings could be applied to gradient boosting. If they do not apply, would the challenges of multiclass boosting described in the paper apply to gradient boosting as well? 
- One of the main contribution of the paper is that the proposed algorithm and theoretical analysis use the standard classification loss as opposed to tailored loss functions. Could the authors explain why using a tailored loss function as proposed in [13] is a disadvantage compared to their proposed algorithm? What are the challenges with using tailored loss functions?
- It would be good if the authors would explain the statement in lines 197-198 about the logarithmic dependence of the algorithm on k.
- Would it be possible for the authors to design a set of experiments in which their proposed method is applied to a real dataset, where the base class is the decision tree? As base learners need to be "easy-to-learn", probably tree stumps could be used as a base class. Could such experiments validate the theoretical findings and show that if k is large and the sample complexity / number of calls to the weak learner oracle is not of the complexity suggested by the theoretical analysis, then the model does not converge even for a large number of iterations?
- AdaBoost is known to be sensitive to noisy datasets. How is this taken into account by the theoretical analysis proposed in this paper?
limitations_and_societal_impact: The authors do not discuss the potential negative societal impact of their work, but that looks reasonable to me. I do not see any negative impact of their proposed work.

In terms of limitations, the authors describe the cost using the standard classification loss on the lower bound of the excess error.
review_title: null

Meta-review: This paper studies the problem of multiclass boosting and proves a few different results. 1) proving that the number of samples required by a 
weak learner is exponentially more than the number of samples needed by the booster; 2) proving that the weak learner's accuracy parameter must be smaller than an inverse polynomial; and 3) giving a trade-off between number of oracle calls and the
resources required of the weak learner.  This is a nice set of interesting and even surprising set of results about multiclass boosting and would add to the conference.
Decision: Accept (Poster)