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: In this paper, the authors introduce an agnostic online learning boosting algorithm for multiclass classification problems extending the prior work [5] for binary classification (N. Brukhim et al., NeurIPS-20). The algorithm is based on a generic reduction of boosting to online convex optimization (OCO) which was proposed in the aforementioned paper. Given access to agnostic weak online learners (AWOLs) satisfying some error bound, the algorithm constructs an online learner with a regret bound. The proposed procedure can be extended to other settings (statistical agnostic, online realizable, and statistical realizable) but does not lead to state-of-the-art regret bounds in these settings. Finally, the authors numerically compare the proposed agnostic and realizable online boosting algorithms with OnlineMBBM and Adaboost.OLM. The experimental results show that the proposed algorithms are competitive with existing multiclass boosting algorithms.
strengths_and_weaknesses: **Strengths**

The problem is well motivated and, in my opinion, is relevant to the NeurIPS community. The paper fills a gap in the literature by providing the multiclass boosting algorithm in the online agnostic setting.

Overall, the paper is well written. The structure of the paper is clear. All the stated claims are supported by proofs.

The generalization of online agnostic boosting from [4] (Brukhim et al., 2020) to multiclass problems looks nontrivial and requires careful analysis. Namely, new complications in the multiclass setting arise in construction of a loss function which is passed by the booster to an OCO algorithm. However, I expect some comment on how the algorithm correspond to that of  [4] in the particular case k=2. Given that it the algorithms have the same regret bounds, are they equivalent in some sense?

The paper provides more intuition behind the proposed algorithms than the original paper [Brukhim et al., 2020]. Additionally, the paper discusses how to construct AWOLs for two types of finite hypothesis classes: the set of discretized weight matrices and the set of discretized multiclass decision trees of depth 1. Although these examples are simple, they were not discussed in [Brukhim et al., 2020]. 

Finally, the authors conduct numerical experiments for the proposed methods.


**Weaknesses**

First of all, I have several questions about the problem setting and the significance of the obtained results (see below). My score depends on the answers.

Second, I would appreciate particular formulations of regret bounds for the adaptive environment as it announced in ll. 167-168. Currently, the main result assumes a strong requirement for weak learners (adaptive env.) and in a weak setting for boosting algorithm (non-adaptive env.). This makes the main result something inapplicable: it does not correspond to any of the two settings.

It is known that the reduction of boosting to OCO leads to suboptimal regret bounds when applied to realizable boosting and statistical agnostic boosting; see [Brukhim et al., 2020]. In Section 4, where other settings are discussed, the authors write that their purpose is “not to achieve state-of-the-art bounds for these settings”. I understand that the reduction to OCO may not lead to the optimal regret bounds but, however, it seems necessary to me to compare the obtained results with the existing ones. I would suggest, for instance, to move some of the proofs to the appendix and add this comparison. 

Experiments. I understand that the main contribution of the paper is the theoretical results. However, in my opinion, experiment section can be improved.
(1) The number of weak learners is set to only 100, and simple decision trees of depth 1 are used as weak learners. In practice, real models are much more complicated. Is it true that the proposed algorithms are so complex that it is hard to apply them in more realistic settings. It would be useful to provide complexity analysis of the proposed algorithms. 
(2) I am confused by the fact that the accuracy may differ by more than 10% within a single dataset. Is it a consequence of (1)?
(3) It is difficult to make any conclusions from experimental results, since more expensive algorithms generally achieve higher accuracy. A “fair” comparison requires to assign equal computational budget to all methods (all of them have hyperparameters, which allow to trade-off accuracy and training time).   
(4) What parameters for Projected OGD are used? Why in OnlineMBBM the advantage parameter was tuned across [0.001, 0.01, 0.05, 0.1, 0.3]? Experimental part needs much more details.
(5) Only seven quite small datasets are used.
(6) It would be useful to have also some average accuracy over all datasets and an alternative measure (e.g., cross-entropy).

At last, formulations are not absolutely perfect:

- In equations for expected regret (l. 69-70) and AWOL condition (ll. 155-156), y_t / l_t should be different in the first and the second term of the differences, because y_t / l_t depend on the expert/algorithm. This is the consequence of the environment adaptivity, and the use of the same notations for different variables indicates, conversely, the non-adaptive case.

- In ll. 67-68, the dimension of the standard simplex is k-1, not k, see https://en.wikipedia.org/wiki/Simplex#The_standard_simplex
Please, respect general mathematics.

Minor comments: 
(1) A small overview of OCO algorithms would be helpful for the reader, as OCO is a central part of the proposed algorithms. At the same time, the detailed proof of the main theorem can be moved to Suppl.
(2) Caption for Figure 1: the dot after p_2^* appears at the beginning of the second line.
(3) L187, second line, first term: factor 2 should be inside the bracket
questions: The main setting considered in the paper is fully adversarial, not just agnostic: the environment adapts to the player. This entails a stronger condition on weak learners (see Definition 1) as compared to the same requirement in the non-adaptive case. At the same time, I believe, non-adaptive environment is more realistic for most practical cases. To what extent is the condition in Definition 1 more restrictive than that in the non-adaptive case? For example, are there generic examples for class of experts where the maximum of expected gain is at least positive? (as it required in ll. 518-520 of Supplementary?).

I would consider a much simpler and interpretable condition for AWOL in Definition 1 without auxiliary variables l_t. We can just use 0-1 loss as the gain function instead of strange \sigma_{y_t, l_t}. Such variant of Definition 1 has the following properties:
(1)	It is also a generalization of Definition 1 from [4]
(2)	It is strictly weaker than the current requirement to AWOL in Definition 1.
Does the regret bound work for this version of Definition 1?

“Importantly, we also allow the adversary to pick l_t even after it has observed W(x_t)”. Could you provide some intuition why do you want the environment to controls how much loss the weak learner suffers when it is incorrect?
limitations: I see not potential negative societal impact
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 presents an extension of the results in Brukhim et al 2020 to multiclass problems, with similar extensions to online & batch settings for both adversarial and realizable problems.
strengths_and_weaknesses: Overall the presentation of the material is good, and the topic is interesting.

This paper is rather full, with much of the supplementary material being necessary to understand Section 4, and the paper itself relying strongly on Brukhim et al 2020 for longer explanations of several of the concepts. It might be better as a longer journal paper with all the material in the appropriate order rather than forced into an overly terse 9 pages.

The modification from random relabelling to fractional relabelling is discussed very briefly in the experimental results, but this seems to be quite an important difference which should be covered in more detail. The fractional relabelling approach is approximating passing in the full distribution as a target, and if the weak learner was capable of fitting the full probability distribution (as for example a logistic regression trained under cross entropy would be) then passing in a single example with $y_t$ replaced by $p_t^i[l]$ seems like it would achieve the same goals more efficiently.
questions: The agnostic setting allows the label generating function to be adversarial which is significantly more flexible, but there are several intermediate points between a stationary labelling function in the realizable case and an entirely adversarial labelling function in the agnostic case, which is a non-stationary but not adversarial labelling function (e.g. operating under concept drift). Are the bounds tighter in the non-stationary but not adversarial setting?

Does Algorithm 1 reduce to the algorithm of Brukhim et al 2020 in the binary case?

Why does the agnostic algorithm (agn) outperform the realizable version (ocor), when the datasets should be realizable?
limitations: The experimental study is small, and would have benefited from more complex datasets involving non-stationary or adversarial behaviour to make clear the distinction between the agnostic algorithm and the existing realizable ones.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This work proposes an extension of online agnostic boosting techniques to the multiclass setting, via a reduction to OCO. They further generalize the approach to statistical agnostic, online realizable, and statistical realizable multiclass boosting. They give several WL conditions, and provide corresponding bounds for each condition. Lastly, they give an empirical evaluation of their approach. 

strengths_and_weaknesses: **Strengths**

1. This approach seems to be a natural extension of previous boosting methods to the online multiclass setting. The analysis also seems to be rigorous. 
2. The various weak learning conditions given in this work and their corresponding bounds under the same boosting framework is an interesting contribution. 

**Weaknesses**

1. The novelty looks limited as the techniques are very similar to Brukhim et al. 2020. Moreover, this paper does not discuss the major difficulty of extending that framework to the multiclass setting.
2. The WL assumptions seems to be quite strong (see details below). It would greatly improve the work to either relax these conditions or give a lower bound showing this cannot be done. 



questions: 
1. Figure 1 - is not very clear. Consider adding description of the axis, and further explain how to interpert the plot. Maybe explicitly say that the black,blue,red lines correspond to Delta_k/gamma for the different gammas?

2. Why is “L2 projection is not a natural projection operator for Delta_k”? not clear why it is needed to first project to the line that contains Delta_k, and only then to Delta_k - why not directly project to Delta_k? 

3. Weak learning assumption : regarding Definition 1, the assumption that W performs well w.r.t this sequence of ell_t without ever seeing it seems quite strong. In addpendix D the example given which satisifies this requirement seems to also be irelevant for boosting, i.e., for the setting specified in appendix D applying the boosting procedure only worsen the regret bound, compared to simply running randomized weighted majority ? 

4. Missing citations: the paper does not discuss their approach in comparison to other online boosting framworks, apart from Brukhim et al. 2020. It would be helpful to compare your result to e.g., “Online Gradient Boosting” by Beygelzimer, Hazan, Kale, Luo, 2015, and “Online Boosting with Bandit Feedback” by Brukhim, Hazan, 2021.  Both of these works are not restricted to binary labels or realizability assumptions. Also consider discussing the works “Optimal and adaptive algorithms for online boosting” Beygelzimer, Kale, Luo 2015, and and “Online Multiclass Boosting” by Jung, Goetz, Tewari, 2017. - and why they do not easily extend to the multiclass agnostic setting? 

5. Regarding the alternative definitions in appendix C: Def. 5 is too strong as well, as th authors pointed out. Def. 6 is unclear to me - does the learner W get to observe the label \ell ? it seems like it doesn’t, and that also seems to be a strong assumpution. If we consider extending a learnable class H to also contain all k fixed-label functions (this does not change the complexity of H), then the average correlation of the learner per label is at least gamma, for all labels simoultanously.  


6. Regarding appendix C in general, no one of the results mentioned there are proved. I understand this is derived similarly to the previous results, consider adding a formal proof for clarity as it is not entirely trivial. 


7. Mukherjee an Schapire 2013 discuss various WL conditions for multiclass boosting in the batch setting. It would be beneficial to at least include some discussion on the various conditions given in the paper and their relative strengths and weaknesses, as this seems to be a main contribution of this work. 


8. Regarding appendix D,  what is the expectation taking with respect to? in the statemnt of Def.1 you say that \ell_t may depend on W(x_t), so it is randomized and cannot be fixed beforehand (though the inequalities still holds regardless). 
    - (also a minor comment - please refer to a specific source for the REWA algorithm and a regret bound guarantee or include it in the writeup, since there are many variations and naming conventions so it is not clear to less familiar readers to which one you are refrring to). 

 9. Lemma 14 seems to be a critical component of the overall proof, which is given via a case-by-case analysis. It would be interesting to also have a high-level intuitive explanation for why this works? 

limitations: There is no potential negative societal impact of the work.
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 main contribution of the paper is to introduce the first algorithm
for online agnostic multiclass boosting. In addition, it also presents
algorithms for multiclass boosting in the offline setting and the online
realizable setting, for which algorithms were already available.

strengths_and_weaknesses: This is a well written paper, which is the first to address the important issue of online agnostic multiclass boosting.

Proofs are clean and elegant.


Remarks:
* A strange aspect of the proof of Theorem 1 is that the definition of
  ell_t^i in line 185 is arbitrary in the second case. I have carefully
  checked the proof, though, and it seems fully correct.
* In line 172, the paper suggests to use online gradient descent as a
  learning algorithm over the probability simplex, but using
  Hedge would improve the dependence on k from O(sqrt{k}) to
  O(sqrt{ln(k)}).
* Experiments: it seems difficult to draw any conclusions from the
  reported accuracies in Table 1, which seem to vary greatly between
  data sets. In particular, the claim that "Compared to OnlineMBBM, our
  OCO-based boosting algorithms achieve comparable if not better
  performance" does not seem sufficiently supported, because it is only
  true if we compare the best of the two new algorithms to OnlineMBBM.

Minor comments:

* I found the choice of identifying integers ell in [k] with basis
  vectors e_ell, with the meaning depending on context, to be quite
  inconvenient. It works if the reader only wants to scan for global
  meaning, but for checking proofs it is an extra hurdle.
* I would suggest to change the notation for the predictions of the weak
  learners from cal{W}_i to cal{W}_t^i, for consistency with e.g. p_t^i.
* The most difficult parameter of Algorithm 1 is gamma, so it should be
  listed as an input.
* Line 176: O(k sqrt{T}) should be O(k sqrt{T}/gamma)
* Definition 2: Define cal{W}_{S'}, and "independent sample OF size m_0"

questions: * Could you give some intuition why the definition of ell_t^i can have an
  arbitrary part? Isn't there some choice that is somehow best?
* The definition of weak learners depends on ell_t^i, but how is it
  chosen? Shouldn't it be passed from Algorithm 1?

limitations: * Although the theory is solid, and sufficient to support the paper, the
  empirical performance of the new algorithms in the experiments is not
  entirely convincing. (I do not consider this a mayor issue, but it
  suggests there may be room for fine-tuning or further investigation in
  future work.)
review_title: null

Meta-review: metareview: The reviewers agree that this is a solid contribution. Please do revise the paper according to the reviewers comments and the discussion.
confidence: Certain
Decision: Accept