Online Agnostic Multiclass Boosting
Authors: Vinod Raman
Ambuj Tewari
Venue: NeurIPS 2022 Accept (2022)
Keywords: Boosting
Online Convex Optimization
Online Learning

Abstract: Boosting is a fundamental approach in machine learning that enjoys both strong theoretical and practical guarantees. At a high-level, boosting algorithms cleverly aggregate weak learners to generate predictions with arbitrarily high accuracy. In this way, boosting algorithms convert weak learners into strong ones. Recently, Brukhim et al. [2020] extended boosting to the online agnostic binary classification setting. A key ingredient in their approach is a clean and simple reduction to online convex optimization, one that efficiently converts an arbitrary online convex optimizer to an agnostic online booster. In this work, we extend this reduction to multiclass problems and give the first boosting algorithm for online agnostic mutliclass classification.  Our reduction also enables the construction of algorithms for statistical agnostic, online realizable, and statistical realizable multiclass boosting. 

Online Agnostic Multiclass Boosting
Vinod Raman
Ambuj Tewari Department Statistics University of Michigan Ann Arbor, MI 48018 tewariaSumico ch. edu
Department of Statistics University of Michigan Ann Arbor, MI 48104 vkraman Sumin ch. edu
Abstract
Boosting is fundamental approach in machine learning that enjoys both strong theoretical and practical guarantees. At a high-level, boosting algorithms cleverly aggregate weak learners generate predictions with arbitrarily high accuracy. In this way, boosting algorithms convert weak learners into strong ones. Recently, Brukhim al. (6] extended boosting the online agnostic binary classification setting. A key ingredient in their approach is a clean and simple reduction to online convex optimization, one that efficiently converts arbitrary online convex optimizer to an agnostic online booster. In this work, we extend this reduction to multiclass problems and give the first boosting algorithm for online agnostic mutli- class classification. Our reduction also enables the construction of algorithms for statistical agnostic, online realizable, and statistical realizable multiclass boosting.
1 Introduction
Boosting is a fundamental technique in machine learning that cleverly aggregates the predictions of weak learners produce strong learner. Originally studied in the batch (realizable) PAC learning set- ting for binary classification, boosting has now been extended to a wide variety of settings, including multiclass classification, online learning, and agnostic learning. Recently, Brukhim et al. [6] extended boosting to online agnostic binary classification, marking the completion of boosting algorithms for all four regimes of statistical/online and agnostic/realizable binary classification. However, less can be said about multiclass classification, where boosting algorithms are only well studied under the assumption of realizability. Designing online agnostic multiclass boosting algorithms is important for several reasons. First, realizability is very strong assumption in real-life: it requires the existence of expert that perfectly labels the data. Second, the vast majority of classification tasks require more than two labels, a prominent example being image classification. Lastly, modern machine learning tasks often require sequential processing of data, making the design and development of online algorithms increasingly relevant. In this work we fill this gap in literature by studying online agnostic boosting for multiclass problems.
1.1
Main Results
We give the first weak learning conditions and algorithms for online agnostic multiclass boosting. A key idea of our algorithms is a reduction from boosting to online convex optimization (OCO), an idea borrowed from Brukhim et al. algorithms for the three other settings of statistical agnostic, online realizable, and statistical realizable multiclass boosting. Finally, we give empirical results showcasing that OCO-based boosting algorithms are fast and competitive with existing state-of-the-art multiclass boosting algorithms.
c As consequence of this reduction,
also able to give
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

1.2 Related Works
Boosting was first studied for binary classification under the realizable PAC learning setting
33
16
I8 32] and then later extended to the agnostic PAC learning setting [5 21
27
26
25
28
2. The
success of boosting for binary classification led sigmificant interest designing boosting algorithms for multiclass problems. As result, several multiclass boosting algorithms were proposed for the realizable batch setting 19 14 22 20), culminating in the work by Mukherjee and Schapire (D)) who unified the previous approaches under a cost matrix framework. Beyond the batch setting, online boosting algorithms for binary [1 A and multiclass classification TC 24 have been designed assuming realizability bound) More recently, Brukhim et al.
K give the first
online agnostic begrett boosting algorithm for binary classification, marking complete all four regimes of statistical/online and agnostic/realizable boosting for binary classification.
Moving to agnostic multiclass boosting, Brukhim et al. study the resources required for boosting in the statistical/batch setting as the number of labels k grows. However, they consider an alternative model of boosting where the weak learner a strong agnostic PAC learner for a simple "easy-to-learn base hypothesis class, and the goal is to learn target concepts outside the base class. Specifically, they assume the target concept can be represented by weighted plurality votes over the base class. this way, the weakness of a weak learner is manifested in the base hypothesis class. Instead, in our work, we consider the standard boosting model of fixing the base hypothesis class, and ask whether a weak learner's ' performance can be improved relative to the best fixed hypothesis in that class.
Beyond classification, several other works have studied online agnostic boosting for real-valued loss functions under both full full-infornation and bandit feedback settings [3] M 5. In particular, the work by Brukhim and Hazan [5] reduce online boosting for regression tasks under bandit feedback to online linear optimization. A key difference between these works and ours is in the weak learning assumption: these works consider a weak learner that is a strong learner for a small base class of regression functions. The goal of boosting then is to produce a strong online learner for larger class which contains linear spans of the base class. This is in contrast to this work, where again, we fix the base hypothesis class, and boost the regret bound.
2 Preliminaries and Notation
We first describe the basic setup for online agnostic multiclass boosting. There are k possible labels B: := {1...., }} and & is known to the booster and the weak learners. The booster maintains N copies of a weak learner, W, which themselves are (randomized) online learning algorithms that sequentially process examples from instance space X' and output predictions in Bx, which we denote as the set of basis vectors of length k. At each iteration 1 == 1, ...,T, T, an adversary picks a labeled example (It,, (c) E X' x B₁ and reveals x; to the booster. Once the booster observes the unlabeled data Zt, it gathers the weak learners' predictions and makes a final (possibly randomized) prediction de E Bg. After observing the booster's 's final decision, the adversary reveals the true label yr. and the booster suffers the loss 1 (it # y/ or equivalently, gains the reward 21 ( = yr - 1. Finally, the booster, after observing the true label yt, updates each weak learner. Note that the loss/gain of the booster in round can be written as 1 De- Bt and 2t/-- Y/ - 1 respectively. We also let AR represent the (k- 1)-dimensional probability simplex and A represent the -
-scaled (A- --ddimensional
probability simplex for 7 E (0, 1). Finally, we let 1 denote the k-dimensional ones vector.
Evaluation. Unlike the realizable setting, in the agnostic setting, place restrictions on how the stream of examples Ø1, .... Iy are labelled. Thus, for a fixed hypothesis class H. C B the goal of the booster is to output predictions di such that the expected regret,
T
E max NEW
Σ (2h(z)) - y1 - Σ (2 (20 91 - -1)
minimized, where the expectation over the randomness of the booster and that of the possibly adaptive adversary. Note, this is in contrast to the realizable setting where the stream is labelled by E H. and we wish the booster to minimize the (expected) number of mistakes mnistake-boundh
Agnostic Boosting. A key technique in agnostic boosting, first appearing in the work by Kanade and Kalai (27, is to update weak learners by feeding randomly relabelled examples. This is in contrast to the realizable setting where typically update weak learners by passing reweighted examples.
2

---

Accordingly, in order to design a good boosting algorithm, we need to design the booster's strategy for random relabelling while also quantifying the weak learner's ability maximize cumulative gain, even under relabelled data. The first task will be resolved by allowing the booster to use an Online Convex Optimization (OCO) oracle. In this way, we reduce boosting to OCO, an idea borrowed from Brukhim et al. G For the second task, we give different possible weak learning conditions for the same algorithm, all of which capture the ability of a weak learner to maximize cumulative gain with respect to the best fixed competitor in hindsight.
Online Convex Optimization. Our booster will use an OCO oracle to update its weak learners. The OCO setting is sequential game between an online player and adversary over N rounds (see [23] for an in-depth introduction). In each round, the player plays a point z; a compact convex set K. R the ad adversary reveals loss function fi chosen from family of bounded convex functions over K. and the player suffers the loss [x(z)). The goal of player is to also minimize regret, defined as
N R(N) = ((0))
min EEK
f1()).
We will denote an algorithm in this setting as OCO(K, N). If A is a OCO(K,NN) then we will denote its regret by RA(N). For many OCO algorithms, like Online Gradient Descent (OGD), the regret (N) is sub-linear function of the time-horizon N.
3 Online Agnostic Boosting
In this section, we present an online agnostic boosting algorithm and analyze its performance. We begin in Subsection by formally describing our algorithm which reduces boosting to OCO. Then, in Subsection 3.2 we state a weak learning condition and subsequently prove a regret bound for our proposed algorithm.
3.1 Algorithm
Pseudocode for our online agnostic boosting algorithm is provided in Algorithm I The booster maintains oracle access to N copies of weak learner W1...., WN well OCO Ak. N) algorithm A. Each weak learner is characterized by some advantage parameter y E (0, 1] (directly proportional to its strength), and we will be precise about what exactly quantifies in Subsection 3.2 In round f, the booster uses the weak learners to make a prediction ft, observes the true label yt. and finally simulates game with the OCO algorithm A update each weak learner W,. Specifically, the booster uses the outputs of AA to feed relabelled examples (I,, v') to W.. A critical component of our algorithm is the La projection operator onto the probability simplex Ag. which we denote by II- This is used by the booster in line 4 to make randomized predictions it-
We now highlight some desirable properties of Algorithm I First, it is casy to implement and efficient assuming access to an efficient weak learner. In particular, for each round f, if the running time of the weak Iearner is Q, then the rumning time of our booster is O(NQ + Nk log(k)). This is in contrast to the OnlineMBBM algorithm proposed by Jung et al. (24) for the realizable setting which is not efficient even assuming access an efficient weak learner. Second, when k 2. algorithm reduces down to the online agnostic boosting algorithm proposed by Brukhim et al. [6] in the binary case. Indeed, one verify that when & 2, the La projection operator reduces to the same projection used by Brukhim et al. 6 and the distribution over labels y induced by the outputs of OCO algorithm are equal for each weak learner in every round
While the framework in Algorithm| iss inspired from Brukhim et al. 6 in the binary setting, several new complications arise in the multiclass setting, Most notably, when l: >> 2, must figure out how the booster should make predictions, what loss functions the booster should construct and pass to A, and lastly, how the booster should use the output of A to update each weak learner. The interplay behind these three algorithmic pieces is delicate and they have been carefully designed in Algorithm to enable the analysis in Subsection 3.2 Below, provide some intuition behind these algorithmic decisions.
Randomized Prediction. At the start of each round, the booster averages the weak learners votes, scales the average by the parameter 7, projects the sealed vector back into the simplex, and finally samples random label. When the Le projection operator is selected, this approach for randomized
3

---

Algorithm 1: Online Agnostic Multiclass Boosting via OCO
Weak Learners Ww..WNv. OCO(A,, N) algorithm A, Advantage parameter ? for / 1,..., do
Input:
Receive example 24
Accumulate weak predictions h4 = =EEI (((xs)
Set D: II( 7N
Predict Ve ~ Dr Receive true label for 1..,, N do
If 1, obtain P A(l,..... ). Else, initialize p! Lt. Reveal loss function: 14()) - p. (2 (2 1x,)
Sample random label yi ~ pi. and pass (I vt) to W/
10
Reset
1.
PL
P1
0.8
Pz
p4 P2
0.75
0.50
Figure I: The red, blue, and black lines correspond to A for 0.50, 0.75, and, 1.0 respectively. and P2 are 7-scaled votes and pi and pa are their corresponding L2 projection onto A2. Pí and pa denote the orthogonal projections onto the plane containing Ag.
prediction achieves a polarization effect: as 7 gets smaller, the projection concentrates mass on fewer number of labels, specifically those labels that have achieved the majority the votes from the weak learners. When 7 nears 0, the Le projection eventually places all mass on the label with the votes.
One might think that the L2 projection not natural projection operator for A (as KL or L1 projections might seem better suited to the geometry of the probability simplex). However, in the case where we project from A to As, we find that is a natural choice from geometric perspective. Figure provides visualization of the L2 projection operator from A 4 A for k = 2. Because the spaces A and A₁ are parallel, given any point p E Ag, one can think its L2 projection the following procedural manner:
1. Compute the orthogonal projection, P. onto the plane containing Ag-
2. If ğ Ag, output p" p.
3. Else, output p" arg minpe |pp
p112-
From this procedural perspective, Figure [lends a geometric intuition behind the polarization effect of the La projection. As shrinks, the number of points in A that lie orthogonally above A shrinks. Thus, the orthogonal projection of the vast majority of points in Ag will lie outside Ar.

---

leading to greater number of sparse projections that lie on the boundary of A From the booster's s viewpoint, this property of the L2 projection is desirable. If the weak learners are very weak (small y) but somehow concentrate votes on a few labels, then it may be likely that the true response is amongst these few labels. In this sense, 7 controls how many weak learners need agree on a particular label to convince the booster to deterministically predict that label.
Updating Weak Learners. Once the true label yt is revealed in each round, the booster must update each weak learner. As mentioned in Section 2 one strategy for updating weak learners in the agnostic setting is via random relabelling. Indeed, line 10, the booster passes back to the weak learner the example with random label vf př. Together. the specified loss function in line 9 and random relabelling strategy in line 10 achieve the following effect: if more weak learners make mistakes. the distribution over labels output by the OCO algorithm A in line 8 concentrates on the true label yt, increasing the likelihood that y/ passed to subsequent weak learners. This is desirable as the outputs of the OCO guide each weak learner to correct for the mistakes of preceding learners.
3.2 Regret Analysis
Before we give the regret bound of Algorithm we need specify the capacity to which the weak learners can make predictions, even under potentially relabelled data. Unfortunately, in the agnostic setting, there is no canonical weak learning condition for multiclass problems. this paper, we give several possible definitions of an Agnostic Weak Online Learner (AWOL) for the multiclass setting, all of which enable a regret analysis of Algorithm[]] We emphasize that we can derive different regret bounds for Algorithm | based on what condition we assume our weak learners to satisfy. For this section, we present weak learning condition based loosely on a one-vs-one approach to multiclass classification. In Appendix C
[
we provide alternative weak learning conditions.
Define the gain function for input 2 E By.
(vee(z) = 11= -1= -
For some y Bg and é E Bg Ku), (-) can be thought of the binary classification task between labels y and l. Definition [ requires that for any such sequence of binary classification tasks, an online agnostic weak learner must be able to eventually distinguish between every pair of labels to some non-trivial, but far from optimal, degree.
Definition 1 (Agnostic Weak Online Learning). Let H C BE be a class of experts and let 0 < <> S 1 denote the "advantage". An online learning algorithm W a (7, yaggoosiic weak online learner (AWOL) for H if for any adaptively chosen sequence of tuples (Ir,Vr, Uts le) E X x Bg x BB where l A yt the algorithm outputs W(x+)= E B& every iteration t [T] such that,
Σ Eome (W(..))))) < (T,(T
Y mmx E NEW
E
where the expectation is taken w.r.f. the randomness of the weak learner W and that of the possibly adaptive adversary, and Rw: N x IN- + R4 is the additive regret: non-decreasing, sub-linear function T.
The precise dependence of Rw (T, k) on ls is explored in more detail in Appendix D where we explicitly construet learners satisfying AWOL. We make few remarks about Definition First, the strength of the weak learner varies directly with y. Second, for & = 2, Definition [ reduces to the weak learning condition by Brukhim et al. [6] in the binary setting. Finally, we emphasize that Definition I holds under adaptive adversary, and its own internal random bits. Importantly, we also allow the adversary to pick & even after has observed Wxx,) as this only controls how much loss the weak learner suffers when it is incorrect.
that can choose (yt, 62) based
{W
Under the assumption that weak learners satisfy Definition I Theorem I bounds the regret of Algorithm | under an oblivious adversary. Using a standard reduction, our results can then be generalized to an adaptive adversary (see Chapter in ()) In particular, key requirement allowing an oblivious regret bound to generalize to an adaptive regret bound is that the learner's predictions on round should not depend on any of its past predictions from previous rounds. This is indeed true for our Booster.
5

---

Theorem (Regret Bound), Assuming weak learners satisfy Definition 7 of Algorithm
the expected regret bound
1
T Σ t=1
(2) Y1 1)
Rw((Tk)
RA(N)
E
max
(2h(zz)) yt - 1))
T
BEH
I
N
where the expectation is over the randomness of the algorithm and weak learners, and Rw(TT k), (N( are the regrel terms of the AWOL, OCO algorithms respectively.
If one picks A to be Online Gradient Descent (OGD), then Ra(N) O(GDVN), where D is the diameter of DS and G is the upper-bound on [pl(p))l In our setting, D v2 and G (
(using Lemma 19 and hence the average regret further simplifies to:
T
Rw +0
max (2h(x;) y1 - 1) Σ
(20: y/ 1) S
T
KEH
7/
TVN
To exemplify the role N, consider a scenario where Rw Rw OlvVT) (see Appendix D for examples). By setting N 1/2 the overall regret of the booster becomes O ( In the next subsection, give the proof of Theorem
7
3.2.1 Proof of Theorem 1
We follow similar procedure Brukhim et al. 6 by lower and upper bounding the expected sum of losses passed to A in terms of the regret of the weak learner and the regret of AA respectively. These bounds rely several lemmas that have been abstracted out and provided in Appendix E As mentioned previously, we also assume an oblivious adversary.
Let 1I V1), .... (IT, yr) be any sequence of example-label pairs. We start by giving lower bound on the expected sum of losses passed to A using Definition Define h* arg max ΣT (2h
1) as the optimal competitor in hindsight and let
4 = (i(())) le B& (ut).
WF + vl otherwise
Note that the precise choice of é in the second case is not important. The proof below only uses the fact that & E B& {ui} in that case. We then have,
(2W(()))) - 1s (2y, 1sa)
E
E
7
(2M:(22))))) - 1s)]
Σ
Σ
[p] (2yr 1x)]
1=1
N
T
22:( oi -1] Σ
E ppj (2yr 1x)
(Lemma 15
1=1
t=
oo (Ma(
E Ipt (2y: 11)]
1=1
t=1
Using the weak learning condition in Definition

---

N
T
T
NB k)
E
mon (Wi(ze))
2
max HER
E
(Definition D
7
(T,((T,))
E (ov.a((1(()))))
?
(T,(T,K)
22h (21) .0/ -1]-
N T
NRw (T, (T,(T,k)
[p (2h"(x)) 100-111 -1a]
(Lemma [5
Putting things together, we find,
N
E 1ph. (x1) 2y0)] NRw(TTk)
E
7
N
E 12 (xx) y1 - 1)1 NRw(TTA)
(Lemma 16
2(h y1 -1 NRw(T, N
7
Now, we compute an upper bound. For any E [T] and arbitrary p" E A&:
1
Σ
1
E
min
Σ
N
(:C))
+
(a(NN
(OCO Regret)
N
PER
N
N
RA(N)
E
kP')))
N
N
22M( - 1s (2y: -1se))
11m) )] Ra(N)
E
N
7
N
E2(V3 1n]) -p" (22. 11) + (N(
NN
N
(2W,(x²) - 1nl - -p- -(2yt - 1xx + RA(N)
N
Ei=1 N
Wi(ar)) 1s (2y) - 113) 111)] + RA(N)
E
N
N ma(xr)
yt -m- (1-11 )
+ Ra(N)
< E
2
(Lemma 17
NN
N
(N)
= 2 (E [0r) 3/4 1) +
(Law of total expectation)
N
Summing over T,
T
2 [ V1- - 1) TRA(N)
(oi)
<
Σ
N
7

---

Combining lower and upper bounds for EE
NT Σi= e((o))
we get
1
(20r 31 - 1) S
Rw((,k)
RA(N)
E T
max
(2h(z)) -1-
hEH
N
which completes the proof. Since 2/(xz) 1 1 = - 21l (1(r)) # ych. we can also write the average regret terms of the number of mistakes,
(T((Tk)
Ra(N)
E T
Σ 1 # ve)
-min bEH
11(h(a)) # 41
2-T
2N
4 Beyond Online Agnostic Boosting
In this section, we present results of extending our reduction to the three other boosting settings, namely statistical agnostic, online realizable, and statistical realizable learning. The purpose of this section is to showcase the generality of the OCO-based boosting framework and not to achieve state-of-the-art bounds for these settings. Boosting algorithms and all associated proof' can found in AppendixAI and B Throughout this section will let W's denote the hypothesis output by weak learner trained on sample S.
4.1 Statistical Agnostic Boosting
the statistical setting, our objective of interest the correlation, which we define below. Let be distribution over X' x B& and let h X - BR be hypothesis. Define the multiclass correlation of with respect to D as
cor (a.a)~
E [h(x) (2y - 1x)].
Like the online agnostic setting, the boosting algorithm for this setting (provided in Appendix can be analyzed under several candidate weak learning conditions. To showcase the dependence on k, we provide weak learning condition based loosely on one-vs-all approach to multiclass classification.
Definition 2 (Empirical Agnostic Weak Learning). Let H. C B be hypothesis class and let O < < denote the "advantage". Let x = (Z1...., xm.....mm E X denote an unlabeled sample. A learning algorithm W (y, co, ma) weak learner (AWL) for H with respect x if for any labels y = (V1, ..., -....lmmmll Um) E BE, and every reference label E B
Σ (s:) (2y; 1x) PANA
Σ M(x.) (2ys 1x) mcg.
Y
max KEH R:U
where S' is an independent sample size mi drawn the distribution which uniformly assigns to each example (Ii, Ms) probability 1/m.
Under the assumption that weak learners satisfy Definition Corollary bounds the expected correlation statistical agnostic boosting algorithm.
Corollary (Empirical Agnostic Correlation Bound), There exists a boosting algorithm whose output after T rounds, denoted by h, satisfies:
RA(T) T
keo ?
E [cor [h)] 2 max E [h))s(h)] hEH
where S is the distribution which uniformly assigns to each example (æ,, y:) probability 1/m.
1 for any gives an error rate of kea + c. Although, Letting A be OGD, and setting T = 0 .,22))
to our best knowledge, there are no existing multiclass boosting algorithms in the agnostic setting, we point out that there is evidence to suggest that a sub-optimal dependence of the error rate on might be unavoidable (see 77).

---

4.2 Online Realizable Boosting
In the online realizable setting, we are guaranteed that the stream of examples (21, yı), ..., (xr, yr perfectly labelled by some hypothesis h E H. Definition then gives an appropriate online realizable weak learning condition.
Definition (Realizable Weak Online Learning). Let H C Bi be a class of experts and let 0 < S 1 denote the "advantage". An online learning algorithm W is a (r, reallzzbl weak online learner (RWOL) for H. for any sequence (x1.31), (TT. E X' x By that is realizable by H. at every iteration t [T), the algorithm outputs W(x1) Bk such that,
T Σ (2W())))
I
- -1 2 - Pw((Tk)
where the expectation is taken w.r.t the randomness of the weak learner W and Rw :N::NN X - R+ is the additive regret: non-decreasing, sub- nub-linear function of
Under Definition g Corollary
B bounds the expected gain of an online boosting algorithm.
Corollary (Mistake Bound). There exists a boosting algorithm whose outputs ÿ1.-.., fr satisfy:
1
T
RA(N)
(w,(T,)
22
[
21 - 91
T
N
7T
where (T, 2B Ö(VT).
we consider scenario where (T OKvV), taking A be OGD, to be O (,7ZZz and
T to be O(+z)), gives mistake-bound at most ekT. We point out that cannot readily compare this bound with the existing bounds for online realizable boosting by Jung et al. [24] because the dependence of Ry(T,k on k depends on the weak learner choice.
4.3 Statistical Realizable Boosting
In the statistical realizable setting, our metric of interest is again the multiclass correlation. However, under the realizability assumption, max, EH corp (h") = Accordingly, Definition gives appropriate realizable weak learning condition.
Definition 4 (Empirical Realizable Weak Learning). Let H. S Bx be a hypothesis class and let 0 < < 1 denote the "advantage". Let S = {(I1, 31 (i,,,,,,..,, (Fm, vm)) E x By be sample. A learning algorithm W is (7, (7, realizable weak learner (RWL) for H with respect to S if for any distribution (pi...., Pm) over the examples,
E [[corp 2
where S' is independent sample of size mo drawn from p.
Under Definition 4 Corollary bounds the expected correlation of a statistical realizable boosting algorithm.
Corollary 4 (Empirical Correlation Bound). There exists boosting algorithm whose output after T rounds, denoted h, satisfies,
E [cors(F)) 2 RA(T)
T
where S is the distribution which uniformly assigns to each example (x1, y:) probability 1 1/m.
Note that the cost of weak learning manifests in the regret term of the OCO algorithm. Precisely, one picks OGD to be the OCO algorithm, then the bound on correlation can be expressed as
) which exhibits a decreasing lower bound as y shrinks. Setting 00 for any e > ensures that at most error is obtained. is difficult to compare our error rates to that achieved by existing multiclass boosting algorithm in the realizable setting because weak learning condition is different and potentially stronger. Nevertheless,
(h)] 2
bounds sub-optimal to those in Mukherjee and Schapire 30 which only require setting T = O log( ))) to achieve error.

---

Table I: Average accuracy and runtime of algorithms on 7 UCI datasets.
Dataset
k
Accuracy(% )
Runtime(s)
Agn
Opt
Ada
OCOR
Agn
Opt
Ada
OCOR
Balance
3
84.4
79.5
75.2
78.8
11.5
57.6
7.1
4.5
Cars
4
80.6
69.9
75.8
69.6
42.5
104.1
20.4
12.1
Landsat
6
67.0
80.8
56.9
79.6
1255.6
1814.3
81.8
440.4
Segment
7
75.0
78.9
68.6
79.3
647.2
2448.3
51.8
154.7
Mice
8
86.0
77.6
71.3
79.6
1025.8
1811.6
90.1
258.2
Yeast
10
42.3
39.8
41.7
47.6
348.3
1468.8
25.2
56.6
Abalone
28
22.1
24.9
19.2
22.0
4036.7
9775.3
108.0
248.2
Experiments
We performed experiments with Algorithm Ion seven UCI datasets 16 Since, our knowledge, there are no known online agnostic boosting algorithmss for multiclass problems, we benchmark performance against three online realizable multiclass boosting algorithms: the state-of E--hhe-an art optimal (OnlineMBBMI and adaptíve (Adaboost.Oll online boosting algorithms by Jung et al. 24 and the OCO-based online boosting algorithm alluded in Section (see Appendix [ For weak learners, we used the implementation of the VeryFastDecision Tree from the River package
2y and restricted the maximum depth of the tree 1. We used Projected OGD 355 for the OCO algorithm and set the number of weak learners, N, to 100 for each boosting algorithm.
Our experiments using Algorithm D are performed using, fractional relabeling, technique borrowed from Kanade and Kalai (27]. That is, instead of passing just a single example-labe pair (æ,, vi) where y ~ Pi, we pass all possible weighted example-label tuples {(1,, e, P. [)]]) to weak learner in round f. Experiments with random relabeling showed that random relabeling runs faster but performs worse than fractional relabeling.
Table D summarizes the average accuracy and runtime over five independent shuffles of each dataset for each boosting algorithm. "Agn" " refers to Algorithm [ "Opt" to OnlineMBBB, "Ada" to Adaboost.OLM, and "OCOR" the OCO-based online realizable algorithm. Standard errors for accuracies are provided Appendix F All algorithms except AdaBoost. OLLM are parameterized by an advantage parameter
(0, 1). Thus, was tuned separately for each respective cell of Table | for more experimental details. All code is available at htttps://githii com/
II. See Appendix vinodkraman/Onn htwp:o/iii...ooottto.cccca..eaaa
Despite having the fastest overall runtime, Adaboost.C OL.M had the poorest performance. Compared to OnlineMBBM, our OCO-based boosting algorithms achieve comparable performance a fraction of the runtime. Specifically, for three of our datasets, our online agnostic boosting algorithm achieves the highest accuracy. For the remaining datasets, OCO-based realizable boosting algorithm achieves comparable accuracy to OnlineMBBM with shorter runtimes.
Discussion
We give the first weak learning conditions and algorithm for online agnostic multiclass boosting. Our algorithm relies on clean and simple reduction from boosting to online convex optimization. This fruitful connection allows to go beyond the online agnostic setting and design multiclass boosting algorithms for all four regimes of statistical/online and agnostic/realizable learning. As future work, we leave open identify the correct weak learning condition, construct adaptive versions of our boosting algorithms, improve regret upper bounds/prove lower bounds, design agnostic boosting algorithms under bandit feedback. and study the impact of the choice of weak learner and OCO algorithm on the empirical performance of our OCO-based boosting algorithms.
Acknowledgements. AT acknowledges the support NSF via grant IIS- 2007055
10

---

References
[1] N. Agarwal, N. Brukhim, E. Hazan, and Z. Lu. Boosting for control of dynamical systems. In International Conference Machine Learning, pages 96-103. PMLR, 2020.
[2] S. Ben-David, P. M. Long, and Y. Mansour. Agnostic boosting. In International Conference Computational Learning Theory, pages 507-516. Springer, 2001.
[3] A. Beygelzimer, E. Hazan, S. Kale, and H. Luo. Online gradient boosting. Advances in neural information processing systems, 28, 2015.
[4] A. Beygelzimer, S. Kale, and H. Luo. Optimal and adaptive algorithms for online boosting. In International Conference on Machine Learning, pages 2323-2331 PMLR, 2015.
[5] N. Brukhim and E., Hazan. Online boosting with bandit feedback. Algorithmic Learning Theory, pages 397-420. PMLR, 2021.
[6] N. Brukhim, X. Chen, E. Hazan, and S. Moran. Online agnostic boosting via regret minimization. Advances in Neural Information Processing Systems, 33:644-654, 2020.
[7] N. Brukhim, E. Hazan, S. Moran, I. Mukherjee, and R. E. Schapire. Multiclass boosting and the cost of weak learning. Advances in Neural Information Processing Systems, 34, 2021.
[8] N. Cesa- Desa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, USA, 2006. ISBN 0521841089 841089.
[9] S.-T. Chen, H.-T. Lin, and C.-J. Lu. An online boosting algorithm with theoretical justifications. arXiv preprint arXiv: / /206 6462, 2012.
[10] S.-T. Chen, H.-T. Lin, and C.-J. Lu. Boosting with online binary learners for the multiclass bandit problem. In International Conference on Machine Learning, pages 342-350. PMLR, 2014.
[11] Y. Chen and X. Ye. Projection onto simplex. arXiv preprint arXiv: 2011.
[12] A. Daniely, Sabato, Ben-David, and S. Shalev-Shward Multiclass learnability and the erm principle. J. Mach. Learn. Res., 16(1):2377-24000 2015.
[13] C. L. DuBois.
UCI network data repository, 2008. URL http::/hettworidata..iss uci
eddul
[14] G. Eibl and K.-P. Pfeiffer. Multiclass boosting for weak classifiers. Journal of Machine Learning Research, 6(2), 2005.
[15] V. Feldman. Distributionnsseecffcc agnostic boosting. arXiv preprint arXiv:0909.2992; 2009..
[16] Y. Freund. Boosting weak learning algorithm by majority. Information and computation, 121 (2):256-285, 1995.
[17] Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learning and an application boosting. Journal of computer and system sciences, 55(1):119-133) 1997.
[18] Y. Freund and E. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-133, 1999.
[19] Y. Freund, R. E. Schapire, et al. Experiments with new boosting algorithm. In icml, volume 96, pages 148-156. Citeseer, 1996.
[20] Y. Freund, Schapire, and N. Abe. A short introduction boosting. Journal-lapanese Society For Artificial Intelligence, 14(77 1110) 1999.
[21] D. Gavinsky. Optimally-smooth adaptive boosting and application to agnostic learning. Journal of Machine Learning Research, 4(May):101-111, 2003.
[22] Hastie, Rosset, Zhu, and H. Zou. Multi-class adaboost. Statistics and Interface, 2(3): 349-360, 2009.

---

[23] E. Hazan et al. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3-4):15-3325, 2016.
[24] Y. H. Jung, J. Goetz, and A. Tewari. Online multiclass boosting. Advances neural information processing systems, 30, 2017.
[25] A. T. Kalai and R. Servedio. Boosting in the presence of noise. Journal of Computer and System Sciences, 71(3):266-290, 2005.
[26] A. T. Kalai, Y. Mansour, and E. Verbin. On agnostic boosting and parity learning. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 629-638, 2008.
[27] V. Kanade and A. Kalai. Potential-base agnostic boosting. Advances in neural information processing systems, 22, 2009.
[28] Y. Mansour and D. McAllester. Boosting using branching programs. Journal of Computer and System Sciences, 64(1):
2002.
[29] J. Montiel, M. Halford, S. M. Mastelini, G. Bolmier, R. Sourty, R. Vaysse, A. Zouitine, H. M. Gomes, J. Read, T. Abdessalem, and A. Bifet. River: machine learning for streaming data in python, 2020.
[30] I. Mukherjee and R. E. Schapire. A theory of multiclass boosting. Journal of Machine Learning Research, 2013.
[31] N. C. Oza and S. J. Russell. Online bagging and boosting. In International Workshop on Artificial Intelligence and Statistics, pages 229-2366 PMLR, 2001.
[32] R. Schapire. The strength of weak learnability. Machine learning, 5(2):197-227, 1990.
[33] R. E. Schapire and Y. Freund. Boosting: Foundations and algorithms. Kybernetes, 2013.
[34] M. Sion. On general minimax theorems. Pacific Journal of mathematics, 8(1):171-176, 1958.
[35] M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928-936, 2003.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section future work.
g where we identify
(c) Did you discuss any potential negative societal impacts of your work? [No] Due to the theoretical/general nature of the work, do not foresee any major/direct ethical or socictal consequences of the research we presented.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
3.2 Section 4
Appendix A Appendix B and Appendix C
(b) Did you include complete proofs of all theoretical results? [Yes] See Section 3.2.
Appendix A Appendix Appendix D and Appendix
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either the supplemental material or as a URL)? [Yes] order to preserve anonymity, we will include URL github repository if accepted
12

---

(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they
were chosen)? [Yes] See Section D and Appendix [
(c) Did you report error bars (e.g., with respect to the random seed after running experi-
ments multiple times)? [Yes] See Appendix F
(d) Did you include the total amount of compute and the type of resources used (e.g., type
of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix F
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes) See Section
(b) Did you mention the license of the assets? [Yes] See Appendix F
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're ree using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable
information or offensive content? [N/A] None of the datasets we are using contain information about people.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "shnlQj-T8m", "reviewer": "Reviewer_d9wh", "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.", "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?).\n\nI 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:\n(1)\tIt is also a generalization of Definition 1 from [4]\n(2)\tIt is strictly weaker than the current requirement to AWOL in Definition 1.\nDoes the regret bound work for this version of Definition 1?\n\n“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", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nThe 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.\n\nOverall, the paper is well written. The structure of the paper is clear. All the stated claims are supported by proofs.\n\nThe 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?\n\nThe 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]. \n\nFinally, the authors conduct numerical experiments for the proposed methods.\n\n\n**Weaknesses**\n\nFirst 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.\n\nSecond, 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.\n\nIt 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. \n\nExperiments. I understand that the main contribution of the paper is the theoretical results. However, in my opinion, experiment section can be improved.\n(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. \n(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)?\n(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).   \n(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.\n(5) Only seven quite small datasets are used.\n(6) It would be useful to have also some average accuracy over all datasets and an alternative measure (e.g., cross-entropy).\n\nAt last, formulations are not absolutely perfect:\n\n- 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.\n\n- 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\nPlease, respect general mathematics.\n\nMinor comments: \n(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.\n(2) Caption for Figure 1: the dot after p_2^* appears at the beginning of the second line.\n(3) L187, second line, first term: factor 2 should be inside the bracket", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "bNpUZpGdx8y", "reviewer": "Reviewer_8xyp", "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.", "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?\n\nDoes Algorithm 1 reduce to the algorithm of Brukhim et al 2020 in the binary case?\n\nWhy 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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall the presentation of the material is good, and the topic is interesting.\n\nThis 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.\n\nThe 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "b-rZocpcoQW", "reviewer": "Reviewer_AAXr", "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. \n", "questions": "\n1. 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?\n\n2. 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? \n\n3. 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 ? \n\n4. 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? \n\n5. 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.  \n\n\n6. 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. \n\n\n7. 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. \n\n\n8. 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). \n    - (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). \n\n 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? \n", "limitations": "There is no potential negative societal impact of the work. ", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1. This approach seems to be a natural extension of previous boosting methods to the online multiclass setting. The analysis also seems to be rigorous. \n2. The various weak learning conditions given in this work and their corresponding bounds under the same boosting framework is an interesting contribution. \n\n**Weaknesses**\n\n1. 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.\n2. 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. \n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CT7u1TjJs5Z", "reviewer": "Reviewer_Xr8z", "summary": "The main contribution of the paper is to introduce the first algorithm\nfor online agnostic multiclass boosting. In addition, it also presents\nalgorithms for multiclass boosting in the offline setting and the online\nrealizable setting, for which algorithms were already available.\n", "questions": "* Could you give some intuition why the definition of ell_t^i can have an\n  arbitrary part? Isn't there some choice that is somehow best?\n* The definition of weak learners depends on ell_t^i, but how is it\n  chosen? Shouldn't it be passed from Algorithm 1?\n", "limitations": "* Although the theory is solid, and sufficient to support the paper, the\n  empirical performance of the new algorithms in the experiments is not\n  entirely convincing. (I do not consider this a mayor issue, but it\n  suggests there may be room for fine-tuning or further investigation in\n  future work.)\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a well written paper, which is the first to address the important issue of online agnostic multiclass boosting.\n\nProofs are clean and elegant.\n\n\nRemarks:\n* A strange aspect of the proof of Theorem 1 is that the definition of\n  ell_t^i in line 185 is arbitrary in the second case. I have carefully\n  checked the proof, though, and it seems fully correct.\n* In line 172, the paper suggests to use online gradient descent as a\n  learning algorithm over the probability simplex, but using\n  Hedge would improve the dependence on k from O(sqrt{k}) to\n  O(sqrt{ln(k)}).\n* Experiments: it seems difficult to draw any conclusions from the\n  reported accuracies in Table 1, which seem to vary greatly between\n  data sets. In particular, the claim that \"Compared to OnlineMBBM, our\n  OCO-based boosting algorithms achieve comparable if not better\n  performance\" does not seem sufficiently supported, because it is only\n  true if we compare the best of the two new algorithms to OnlineMBBM.\n\nMinor comments:\n\n* I found the choice of identifying integers ell in [k] with basis\n  vectors e_ell, with the meaning depending on context, to be quite\n  inconvenient. It works if the reader only wants to scan for global\n  meaning, but for checking proofs it is an extra hurdle.\n* I would suggest to change the notation for the predictions of the weak\n  learners from cal{W}_i to cal{W}_t^i, for consistency with e.g. p_t^i.\n* The most difficult parameter of Algorithm 1 is gamma, so it should be\n  listed as an input.\n* Line 176: O(k sqrt{T}) should be O(k sqrt{T}/gamma)\n* Definition 2: Define cal{W}_{S'}, and \"independent sample OF size m_0\"\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept