Beyond Bandit Feedback in Online Multiclass Classification
Authors: Dirk van der Hoeven
Federico Fusco
Nicolò Cesa-Bianchi
Venue: NeurIPS 2021 Poster (2021)
Keywords: Online learning
multiclass classification
bandit algorithms
surrogate losses
feedback graphs

Abstract: We study the problem of online multiclass classification in a setting where the learner's feedback is determined by an arbitrary directed graph. While including bandit feedback as a special case, feedback graphs allow a much richer set of applications, including filtering and label efficient classification.
We introduce \textproc{Gappletron}, the first online multiclass algorithm that works with arbitrary feedback graphs. For this new algorithm,
we prove surrogate regret bounds that hold, both in expectation and with high probability, for a large class of surrogate losses. Our bounds are of order $B\sqrt{\rho KT}$, where $B$ is the diameter of the prediction space, $K$ is the number of classes, $T$ is the time horizon, and $\rho$ is the domination number (a graph-theoretic parameter affecting the amount of exploration). In the full information case, we show that \textproc{Gappletron} achieves a constant surrogate regret of order $B^2K$. We also prove a general lower bound of order $\max\big\{B^2K,\sqrt{T}\big\}$ showing that our upper bounds are not significantly improvable. Experiments on synthetic data show that for various feedback graphs our algorithm is competitive against known baselines.

Beyond Bandit Feedback in Online Multiclass Classification
Dirk van der Hoeven dirk @ dedrkvanderhoeeen.ccmm
Federico Fusco
fuscof diag.um www.numiima...
Dept. of Computer Science
Dept. of Computer, Control and Management Engineering Sapienza Università di Roma, Italy
Università degli Studi di Milano, Italy
Nicolò Cesa-Bianchi ccoolo.esa-bbanchii @unimi.it DSRC & Dept. of Computer Science Università degli Studi di Milano, Italy
Abstract
We study the problem of online multiclass classification in setting where the learner's feedback determined by an arbitrary directed graph. While including bandit feedback as special case, feedback graphs allow much richer set of ap- plications, including filtering and label efficient classification. We introduce GAP- PLETRON, the first online multiclass algorithm that works with arbitrary feedback graphs. For this new algorithm, we prove surrogate regret bounds that hold, both expectation and with high probability, for large class of surrogate losses. Our bounds are of order B ByKTT, where is the number of classes, T is the time horizon, and is the domination number (a graph-theoretic parameter affecting the amount of exploration). In the full in- formation case, show that GAPPLETRON achieves constant surrogate regret of order B2 K. We also prove general lower bound of order max { K, vT) showing that our upper bounds are not significantly improvable. Experiments on synthetic data show that for various feedback graphs our algorithm is competitive against known baselines.
the diameter the prediction space, K
Introduction
In online multiclass classification a learner interacts with an unknown environment in a sequence of rounds. each round 1, the learner observes feature vector æ; E Rd and outputs a prediction o/ for the label E [1.....A, K} associated with xt. If y * yt, then the learner is charged with a mistake. Kakade et al. (2008) introduced the bandit version of online multiclass classification, where the only feedback received by the learner after each prediction is the loss 1// + st]. Hence, a mistake is made at time (and based on the feedback information.
2), the learner cannot uniquely identify the true label y/.
Although bandits are canonical example of partial feedback, they fail capture number of important practical scenarios of online classification. Consider for example spam filtering, where an online learner is classify emails spam or non-spam based on their content. Whenever the learner classifies an email as legitimate, the recipient gets to see it, and can inform the learner whether the email was correctly classified of not. However, when the email is classified as spam, the learner does not get any feedback because the email is not checked by the recipient. Another example is label efficient multiclass classification. Here, instead of making prediction, the learner can ask a human
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

expert for the true label. At the steps when predictions are made, however, the learner does not receive any feedback information (not even their own loss). further example disease prevention: if we predict an outburst of disease in certain area, we can preemptively stop it by vaccinating the local population. This intervention would prevent us from observing whether our prediction was correct, but would still allow us to observe an outburst occurring in a different area.
Unlike bandits, the amount of feedback obtained by the learner in these examples depends on the predicted class, and can vary from full information to no feedback at all. This scenario has been pre- viously considered in the framework of online learning with feedback graphs (Mannor and Shamir, 2011: Alon et al., 2015, 2017). A feedback graph is a directed graph G = (V. E) where each node in V receives at least one edge from some other node in V (possibly from itself). The nodes in V correspond to actions, and a directed edge (a. b) E E' indicates that by playing action a the learner observes the loss of action This generalizes the well-known online learning settings of experts (where G is the complete graph, including self-loops) and bandits (where 9 has only self-loops). Note that it is easy to model spam filtering and label efficient prediction using feedback graphs. For spam filtering, G contains only two actions and n (corresponding, respectively, to the learner's predictions for spam and non-spam), and the edge set is & = { n)), (n, })}. For label efficient multiclass prediction, G contains node for each class, plus an extra node corresponding to issuing a label request. It is important to observe that all previous analyses of feedback graphs only apply to the abstract setting of prediction with experts, where any dependence of the loss feature vectors is ignored. This hampers the application of those results to online multiclass classification. In this work we build on previous results online learning and classification with bandit feedback to design and analyze the first algorithm for online multiclass classification with arbitrary feedback graphs. In doing so, we also improve the analyses of the previously studied special cases (full information and bandit feedback) of multiclass classification.
In the online multiclass classification setting, the goal is bound the number of mistakes made by the learner. The mistake bounds take the following form:
T I
T
1 +
+v1= :n Σ ((UU)+ + RT,
(1)
where l, is a surrogate loss, U E W C Rd is the matrix of reference predictors, and Rr is called the surrogate regret. In this work we provide two types of bounds on the surrogate regret: bounds that hold in expectation and bounds that hold with high probability. Note that equation (1) could
also be written as Σ (1(vl * yr] - 4, (U)) = Rr. However, we prefer the former former since Rr is not a proper regret: because the zero-one loss is non-convex we compare it with surrogate loss.
Our results build on recent work by Van der Hoeven (2020), who showed that one can exploit the gap between the surrogate loss and the zero-one loss to derive improved surrogate regret bounds in the full information and bandit settings of online multiclass classification. We modify the GAP- TRON algorithm ( (Van der Hoeven, 2020) to make it applicable to the feedback graph setting. In the analysis of the resulting algorithm, called GAPPLETRON! that it has O(BvpKT) surrogate regret in expectation and (V/KTT(B2 + (n(1))))) surrogate regret with probability at least for any feedback graph with domination number² p. and for any [vec(U)] < B for some norm |-||| (if ||-] is the Euclidean norm, then [ev] is the Frobenius norm of U). For example, in both spam filtering and label efficient classification we have p = 1. So in the label efficient setting, where each label request counts as a mistake, with high probability GAPPLETRON makes at most order of BVTT KT mistakes while requesting at most order of B KTT labels. Note that we are not aware of previously known high- probability bounds on the surrogate regret. Furthermore, whereas the results of Van der Hoeven (2020) only hold for a limited number of surrogate loss functions, our results hold for the larger class of regular surrogate losses.
several new insights to show
Interestingly, with feedback graphs the surrogate regret for online multiclass classification has, in general, better dependence on T than the regret for online learning. Indeed, Alon et al. (2015) show that the best possible online learning regret is 2(T2/33 for certain feedback graphs that are
Our algorithm is called after the apple tasting feedback model, which the original name of the spam filtering graph.
The domination number is the cardinality of the smallest dominating set.
2

---

Upper bounds
Partial
Full
Algorithm Banditoo Gapoletron
PNeetron
SOBAdiag
Non-separable
BvμKT
KB²
Separable
BVpT
B²
Gare rabe
Lower bounds
Non-separable
K KB²
Separable
VT
B
Table 1: Overview of the surrogate regret bounds in the separable and non-separable case. The up- per bounds hold with high probability. while the lower bounds apply to any randomized prediction algorithm. All bounds are novel except for the lower bound in the full information separable case (Beygelzimer et al., 2019, Theorem 11).
Error in non-separable synthetic bandit experiments showcasing GAPPLETRON against known baselines. The points are the means and the whiskers are minimum and maximum error rate over ten repetitions (details in Section 6).
Figure 1:
called weakly observable (e.g., the graphs for label efficient classification), In contrast, we prove O(T!/2) upper bound on the surrogate regret for any feedback graph, including weakly observable ones.
Our results cannot be significantly improved in general: we prove a 22 QBB2K + VT) lower bound on the surrogate regret. Due to the new insights required by their proofs, we believe the high-probability bounds and the lower bounds are our strongest technical contributions.
We provide several other results. In the separable case, when there exists U for which Ein,/ ((U) O, GAPPLETRON has O(BVpT) surrogate regret in expectation. Even though O(B*K) mistake bounds are possible in the separable setting (Beygelzimer al., 2019), ours is the first algorithm that has satisfactory surrogate regret in the non-separable case and has an improved surrogate regret in the separable case. Note that although BANDITRON (Kakade al., 2008) also makes (BV)T) mistakes in the separable case, suffers ((K)/3(BB)2/3)) surrogate regret in the non-separable case. Our results for the separable case in the full information setting improve re- sults of Van der Hoeven (2020) by factor of K: GAPPLETRON suffers ( surrogate regret both in expectation and with high probability, thus matching the bounds of the classical PERCEPTRON algorithm (Rosenblatt, 1958; Novikov, 1962) see Table for a summary of our theoretical results. Finally, we also evaluated the performance of GAPPLETRON in several experiments, showing that GAPPLETRON is competitive against known baselines in the full information, bandit, and multiclass spam filtering setting. in which predicting a certain class provides full information feedback and all other predictions do not provide any information (see Figure 1 for an experimental result in the bandit setting).
Additional related work. The full information and bandit versions of the online multiclass clas- sification setting have been extensively studied. Here we provide the most relevant references and defer the reader to Van der Hoeven (2020) for a more extensive literature review. Algorithms for the full information setting include: the PERCEPTRON, its multiclass versions (Rosenblatt, 1958; Crammer and Singer, 2003; Fink et al., 2006) and many variations thereof, second-order algorithms such as AROW (Crammer et al., 2009) and the second-order PErcEPTRON (Cesa-Bianchi 2005), and various algorithms for online logistic regression see Foster et al. (2018) and refer- ences therein. In the bandit setting, we mention the algorithms BANDITRON (Kakade et al., 2008), NEWTRON (Hazan and Kale, 2011), SOBA (Beygelzimer et al., 2017), and OBAMA (Foster et al., 2018).
al.,
Online learning with feedback graphs has been investigated both in the adversarial and stochastic regimes. In the adversarial setting, variants where the graph changes over time and partially known or stochastic have been studied by Cohen et al. (2016); Kocák et al. (2016). Regret bounds that scale with the loss of the best action have been obtained by Lykouris et al. (2018). Other variants include sleeping experts (Cortes et al., 2019), switching experts (Arora et al., 2019), and adaptive adversaries (Feng and Loh, 2018). Some works use feedback graphs bound the regret in auctions (Cesa-Bianchi et al., 2017: Feng et al., 2018; Han al., 2020). In the stochastic setting, regret
3

---

bounds for Thompson sampling and UCB have been analyzed by Tossou et al. (2017); Liu et al. (2018); Lykouris et al. (2020). Finally, feedbacks graphs can also be viewed as special case of the partial monitoring framework for sequential decisions, see (Lattimore and Szepesvári, 2020) for an introduction to the area.
Helmbold et al. (2000) introduced online filtering as "apple tasting". However, their analysis applies to a restricted version of online learning in which instances 2i belong to a finite domain, and the labels are such that y/+ = f(x)) for all t and for some fixed f in a known class of functions. Practical applications of online learning to spam filtering have been investigated by Desa-Bianchi et al. (2003); Sculley (2008).
Notation. Let and denote, respectively, the all-one and all-zero vectors, and let e be the basis vector in direction k. Let [K] = {1..... }} and let R+ be the non non-negative real numbers. We use (g. w) to denote the inner product between vectors g, w E Rdd The rows of matrix W E Kxd denoted by W ..... WK Whenever possible, we use the same symbol W to denote both K x d matrix and a column vector vec(W) = (W ...,, W in Kdd We use ||æ|| to denote the Euclidean norm of vector æ and |x|| denote an arbitrary norm. The Kronecker product between matrices W and U is denoted by W ② U. We assume W E W for some convex W R Rxxd This is equivalent to say that vec(W) belongs to a convex subset of RRdd, for example a p-norm ball. As in previous works, we assume instance-label pairs (at,, yt) are generated by an adversary who is oblivious to the algorithm's internal randomization. Finally, for any round t, P...] and Ee[] denote the conditional probability and expectation, given the randomized predictions ví: 1/2 -....-...00 V/-1 and the corresponding feedback.
A feedback graph is any directed graph G = (V,E), with edges & and nodes V. such that for any y E V there exists some y' E V such that (v'.v) E E, where we allow y' = y. In online multiclass classification, V [K] and & specifies which predictions observe which outcomes. Let out(y') = {y E V: : (v', y) E E} be the out-neighbourhood of y'. If the learner predicts v/1 at time t, then the feedback received by the learner the set of pairs (y. 1 y * vel) for all y E out(y'). Due to the structure of the zero-one loss, if node has K - 1 outgoing edges, we always add the missing edge to & as this does not change the information available to the learner. We say that an outcome y' is revealing if predicting that outcome provides the learner with full information feedback, i.e., out(y') = [ and we denote the set of revealing outcomes by Q. For example, in label efficient classification, querying the true label y/2 corresponds to playing a revealing outcome. We say that set of nodes S is a dominating set if for each y E V there is a node y/ E S such that y E out(y'). The number of nodes in a smallest dominating set is called the domination number, and we denote it by p. Note that GAPPLETRON is run using the minimum dominating set S, which is known to be hard recover in general. However, if the algorithm is fed with any other dominating set S' of bigger cardinality p', our results continue to hold with p replaced by p' (recall that a dominating set of size at most (In p + 2)p can be efficiently found via a greedy approximation algorithm).
Regular surrogate losses. Fix convex domain W. Let W x Rd x [K] + R.+ be any function convex on W such that, for all W E W. E Rd, and y [K] (with y = arg max, (W x)) we have
K-1 K
1 K
e(W, 2. + ((W a. x.y')
(2)
Then l El(,,,,,, Vt) is regular surrogate loss if
( 2244(W)
WEW
(3)
for some norm || ||. When || || is the Euclidean norm, the condition on the gradient is satisfied by all L-smooth surrogate loss functions (see, for example, (Zhou, 2018, Lemma 4)).
Examples of regular surrogate losses are the smooth hinge loss (Rennie and Srebro, 2005) and the logistic loss with base K, defined by E, (W,) function. Even though the hinge loss is not a regular surrogate loss, in Appendix A we show that a particular version of the hinge loss satisfies all the relevant properties of regular surrogate losses. Also, note that the feedback graph setting, this particular version of the hinge loss we use random whenever the learner's 's predictions are randomized.
log (W,, 2t, Vt), where is the softmax

---

2 Gappletron
Algorithm I: GAPPLETRON
Input: Set revealing actions 2 [ [K], minimum dominating set S, OCO algorithm A with domain W [ R 2 O, and gap map a : IR xxd x Rd + [0.
1: for = 1...TTd do
2:
Obtain 2i
3:
Let y arg m (Wr xz,)
max- max-margin prediction
4:
if v E Q then
5:
Set ? =
6:
else
Set 7/ min { 12.7 V (8 t: vs & x0H}
7:
exploration rate
8:
Set G. = 1/1 S a.
9:
pi = (1- (11--al G,(W,, - (1- et) + GaW xx) # +1+ (1 1s
10:
Predict with label 1/6 ~ p.
1lye E out(y/)]
11:
Compute U2 = Pr(ye E out(v())
P Y/t is observed only when y: out(y()
12:
Set (WG) (Wi)
compute loss estimates
Send & A and get W4+1 in return
In this section we introduce GAPPLETRON, whose pseudocode is presented in Algorithm 1. As input, the algorithm takes information about the graph G in the form of minimum dominating set S and
a (possibly empty) set of revealing actions Q. GAPPLETRON maintains a parameter W E W S
R and uses some full information Online Convex Optimization (OCO) algorithm A to update the vector form of W. Our results hold whenever satisfies the condition that Σ (W,,
(())) be most of order h(U)) ET &W.)) where &, are the estimated losses computed line 12 of Algorithm 1 and h W - IR., is any upper bound the norm of U E W. Since practically any OCO algorithm can be tuned to have such guarantee - see (Orabona and Pál, 2018) this is mild requirement. Whereas GAPTRON is only able use Online Gradient Descent (OGD) with fixed learning rate, GAPPLETRON allows for more flexibility, which in turn may lead different guarantees on the surrogate regret. For example, if the learner runs OCO algorithm with good dynamic regret bound (Zinkevich, 2003), then GAPPLETRON enjoys a good dynamic surrogate regret bound. Furthermore, the guarantee A allows us to derive stronger results in the separable setting while maintaining similar guarantee as GAPTRON in the non-separable setting, which is not possible when using OGD with fixed learning rate. Additional inputs to GAPPLETRON are >> O, which is used to control the exploration rate of the algorithm in the partial information setting, and the gap map a, whose role we explain below.
The predictions of Algorithm I are sampled from pi defined in line 9, where ey; is the basis vector in the direction of the margin-based linear prediction yi = arg max, (W?, (#), The gap map a kxxd x gd + [0, 1] controls the mixture between εy; and the uniform exploration term * 1. For brevity, we sometimes write at instead a ((W, zx). The single most important property of GAPPLETRON is presented in the following Lemma.
Lemma 1. Fix any feedback graph G and suppose that, for all i, le is a regular surrogate loss with respect to Then GAPPLETRON, run on G with a such that al ( w.) = E(W,, Ze, Ve satisfies
K K-12 ((W.) + +
Σ pl(y)) vv DE|K]
K-1 Proof. First, observe that ΣyE (1) # vdl (1- + yul + a; K +h since Ç, (1 (). and the cost of exploration are at most 1. To conclude the proof we claim that the first two terms in the rinht-hand side are upper bounded by K K (W,,) We show that by considering two cases. In the first case yi Y/ and the inequality simply follows by substituting at = L(W De, vi)
5

---

2 (W,). In the second case yi * yt and we have that
(1 (1-wr)) 1 + ve] + at K
x (Wr, Be,
1 we,
=
K
1 K (W,, Ft, vi)
K- ((W,, K-1 4(W)) -
K-1 (WWe), K
=1
K
K
where the inequality is due to equation (2) in the definition of regular surrogate losses.
Although the GAPTRON algorithm uses similar predictions, it is not clear how to choose a such that property similar to the one deseribed in Lemma 1 holds. Rather, Van der Hoeven (2020) derives a different gap map for the hinge loss, the smooth hinge loss, and the logistic loss, and analyses the surrogate regret separately for each loss. With Lemma I in hand, we simplify the analysis and at the same time - also generalize the results of Van der Hoeven (2020) to other surrogate losses. Furthermore, Lemma also allows derive surrogate regret bounds that hold with high probability.
What Lemma states is that with regular surrogate losses and a W1, w+) = <(WW. De. Vt) the expected zero-one loss of GAPPLETRON can be upper bounded by K exploration. While at first this may seem of little interest note that we want to bound the zero-one loss in terms of & rather than K--f,
R (WW,) plus the cost of
K 4. Compared to standard algorithms, this gains us a * (W,)
term in each round, which we can use to derive our results. To see how, observe that GAPPLETRON
uses an OCO algorithm A to update vec (e, each round. Suppose that, for some h W + IR
and U E W, Algorithm satisfies
Σ (E(w.)- & SI(U)
Σ
9 13
(4)
where 9t ve (W,.. For simplicity, now assume are in the full information setting (e.g..
it = 1 for all 1). Since &, is regular surrogate loss, we can use [V)[(1]] < 22 and
Vab 1/ inf {a/n n + nb} to show that
T EteWS & M(U) 1=1
T Σ (W.) - Σ (( < KLh(U)² 1=1
I
M(U)
Σ 1
2
This means that in the full information setting the surrogate regret of GAPPLETRON is independent of the number of rounds. In the partial information setting some additional steps are required. but the idea remains essentially the same. We formalize the aforementioned ideas in the following Lemma, whose proof is deferred to Appendix B.
Lemma 2. Fix any feedback graph G and suppose that, for all 1, le is a regular surrogate loss with respect to f. If A satisfies equation (4) then, for any realization of the randomized predictions Vi,...,,h Vy GAPPLETRON, run on G with gap map a such that a (We, xx.) = E(W,, Dt Ve ), satisfies
T
T
T
ΣΣ [
p((1) ( Fvd S
Σ ((
+ Σ 7
t=1
t=1
inf 920
h(UU)2 2n
T
K
l ((W.)) - velc(W)) (m,
VUEW.
K
t=1
3 Bounds that Hold in Expectation
In this section we present bounds on the surrogate regret that hold in expectation. For brevity we use My Σt= 1 [v%. * yt]. We now state simplified version of Theorem 4, whose full statement and proof can found Appendix C.
Theorem 1. Let G be any feedback graph with dominating number and revealing action set Q. Suppose that, for all t, Ee is regular surrogate loss with respect If A satisfies equation (4) then GAPPLETRON, run on G and A with gap map a such that al W,W ax)) = E(W,, Rt, VE ) satisfies
K2 L2)
(1.x(1,10)) M(U) PKL (t: vs & @011 0111)
E [Rr] =
mAX
VU E W.

---

Furthermore, for all E W such that Et= 4U)) = 0, GAPPLETRON satisfies: (1: (L] vt & 2) (1, }1
(1 B [MT] = =0 =01B 1E max h(U) pL.
L
EEE
Σ l
T
((wi))
K
In the full information setting we clearly have that Q = [K]. Hence, using OGD as A with an appropriated learning rate, the second statement in Theorem reduces to E' [Mr] S 4
-i=1 & (W.,), which improves the results of GAPTRON in the separable case by at least factor K. Interestingly, compared to standard bounds for the separable case, such as the PERCEPTRON bound, there is a negative term which seems to further lower the cost of learning how to separate the data. Similarly, in the partial information setting, the bound for the separable case in Theorem has reduced dependency on K compared to the non-separable case, obtaining similar improvements over GAPTRON as in the full information setting.
For the non separabe case, Theorem 1 generalizes GAPTRON in two directions. The most prominent direction the extension is to feedback graphs, where our analysis reveals surprising phenomenon: Theorem 1 in fact shows that the surrogate regret in the label efficient setting (and in any setting where p < K) is actually smaller than in the bandit setting, where p = K. Intuitively, this due to the fact that our algorithm only updates when Y/ is known. In the bandit setting, we need to explore all labels to find yt, while in label efficient classification we can just play whichever action the revealing action, and find Vr- This implies that exploration in label efficient classification is easier than in the bandit setting. Note that in the bandit setting, playing v A Y/ also provides the learner with information. Perhaps by using this information effectively, one is able to improve our surrogate regret bounds, but as of yet is not clear how to use knowledge of the wrong label. The second extension is that the bounds in Theorem hold for all regular surrogate loss functions with the same gap map defined by the surrogate loss, rather than only for a limited number of loss functions and ad-hoc gap maps it was the case with GAPTRON.
4 Bounds that Hold with High Probability
We now present bounds on the surrogate regret that hold with high probability. After proving a general surrogate regret bound, we derive a corresponding bound, with improved guarantees, for the full information setting. The bound for the partial information setting can be found in Theorem in Appendix D, which implies Theorem 2 below. Let the maximum loss over all rounds be Lax max, (W).
Theorem 2. With probubility at least - 8, GAPPLETRON safisfies:
R₂ Ry= = - + Emax In(1/6)) KPT YU EW
Furthermore, for all U E W such that ET-re O, with probability at least 1 8 GAP- PLETRON satisfies:
Mr =r= (V(LLUU) + Kluna In(1/5)) pT)
Theorem 2 shows that Algorithm I has O(h(U)) ((N(U)VKTT) PpTT) surrogate regret in the worst case, with high probability. As far as the authors are aware, this is the first high-probability surrogate regret bound for margin-based classifier in the partial information setting. Similarly to the bounds in expectation, the worst-case surrogate regret is the largest the bandit setting (p- = K) and the smallest in label efficient classification (p 1). Unlike the bounds in expectation, where the surrogate regret was at least factor / K smaller in the separable case, the improvement in Theorem 2 is less apparent, but the surrogate regret still has a better dependence on in the separable case. In particular, all the terms with h(U) have better dependence on K.
In the full information setting the dependence on lmax can be removed. This cannot be achieved in the partial information setting, due to the necessity of estimating the surrogate loss. If W has a bounded radius B and E, has gradients bounded by G. then fmax < + BG by convexity. The bound for the full information setting can be found in Theorem 3. In the separable case of the full information setting, the bound does not depend on K, which is not the case for Theorem due to the need to control the surrogate loss estimates.
7

---

Theorem 3. Under the conditions of Lemma 2, with probability at least 1-6, GAPPLETRON satisfies
T MT S
+ 3K In(1/0)
VUEW.
1=1
Furthermore, for all U E W such that Σ 4(U) = 0, then with probability at least 1 GAPPLETRON satisfies MT S 4Lh(U)² In
We provide proof sketch of the full information versions of Theorem 3. The proof for the partial information setting is essentially the same, with some extra steps to control the estimates of the sur-
rogate losses. Let 2; [l + ye] Eve(k P vil) The proof relies on (Beygelzimer et al., 2011, Theorem 1) see Lemma 4 in this paper, which, when translated to our setting, states that with probability at least 6, for 1) E [0, 1).
T
Σ
In
Er
22
Since the variance is bounded by the second moment, E, [>]]] I E,
[ S (W
where the last inequality is due to Lemma 1, By applying Lemma 2, we find that, for some E [0, [],
T
400)+ + A(U) - In +
T
K -
Mr S
Σ E1
L+
((W.),
K
K
1=
with probability least 1 - 6. After choosing appropriate 7). this gives 0 (Kh(U)?? surrogate regret bound with high probability.
Lower Bounds
Corollary below here shows that the bound of Theorem cannot be significantly improved.
Corollary 1. Let A be possibly randomized algorithm for the online multiclass classification
setting with feedback graphs. Then, for any = (t)1,, the surrogate regret of A with respect to the smooth hinge loss must satisfy
E [MT] = min Uew
((U) + + VT)
where K is the number of classes, the feature vectors æ, satisfy ||ae||2 ④(1) for all t, and W {W: : [|]] & B).
Corollary is implied by Theorems 6 and 7 in Appendix E. The proof of Theorem 6 builds the lower bound of Daniely et al. (2015) for strongly-adaptive regret. The feedback graph considered in the proof is filtering with two classes: blind class (no outgoing edges) and revealing class. In the proof, we show that the algorithm either explores too much, which case the lower bound trivially holds, the algorithm explores too little, in which case the environment trick the algorithm into playing the wrong action by exploiting the blind class.
Experiments
We empirically evaluated the performance GAPPLETRON on synthetic data in the bandit, mul- ticlass filtering, and full information settings. Similarly to the SynSep and NonSynSyp datasets described (Kakade et al., 2008), we generated synthetic datasets with d E {80, 120, 160). K E {6, 9, 12), and the label noise rate in {0, 0.05, 0.1}. Due to space constraints, we only re- port part the experiments for the bandit setting in the main text, see Figure In the bandit setting we used worst case tuning for the algorithms with the parameters suggested by theory, or set all pa- rameters 1, except for T. Initially we only used theoretical tuning for all algorithms, but we found that two algorithms we compared with did not have satisfactory results. A more detailed description

---

80
120
0.4
0.2
Algorithm
0.0
rate
Banditron
0.4
GapHin
GapLog
0.2
Gap5 mH
0.0
00
PNewtron
50BAdiag
0.00
0.05
0.10
0.00
0.05
0.10
0.00
0.05
0.10
noise
Figure 2: Results of the synthetic experiments the bandit setting. The plot shows the best results of algorithms with parameters suggested by theory, tuned with all parameters set to 1, except for T. The rows indicate different values for and the columns different values for Whiskers show the minimum and the maximum error rate over ten repetitions.
of the results, including how we generated data and tuned the algorithms, can be found in Appendix F.
In the bandit setting, we compared GAPPLETRON with the following baselines: PNewtron (the diagonal version of Newtron, by Hazan and Kale (2011)), SOBAdiag (the diagonal version of SOBA. by Beygelzimer et (2017)), and the importance weighted version of Banditron (Kakade et al., 2008). We opted to use the diagonal versions of Newtron and SOBA for computational rea- sons. We chose the importance weighted version of Banditron because the standard version did not produce satisfactory results. We used three surrogate losses for GAPPLETRON: the logistic loss (W,) = log (W,,, Ti;; Vr) where g is the softmax, the hinge loss defined in (5), and the smooth hinge loss (Rennie and Srebro, 2005), denoted by GapLog, GapHin, and GapSmH re- spectively, The OCO algorithm used with all losses Online Gradient Descent, with learning rate
-1/2 and projections.
77 E VV, (WO1lB)
As shown in Figure 2, on average versions of GAPPLETRON outperform the baselines in the bandit setting. GapHin appears be more unstable than the other versions of GAPPLETRON. We suspect this is due to the fact that GapHin explores less than its counterparts. In multiclass spam filtering (Figure 8 in Appendix F),
that GapLog makes more mistakes than its counterparts for > 6. We suspect this is due to the fact that with logistic loss, the gap map is never zero, which implies that GapLog picks outcome uniformly at random more often than GapHin and GapSmH, while not gaining any information. Due to this behaviour GapLog makes more mistakes than nec- essary, which also observe in the full information setting. In the bandit setting, the additional exploration leads to additional stability for GapLog, as indicated by the small range of performance of GapLog. In all cases, increasing the exploration rate increased the stability of GAPPLETRON, which is very much in agreement with Theorem 5. Additionally, in Appendix we also compare GAPPLETRON with GAPTRON and in these experiments GAPPLETRON makes less mistakes than GAPTRON.
7
Future work
There are several intriguing research directions left open to pursue. While our lower bound holds for general feedback graphs, it is not clear whether our bounds tight for the bandit setting. Either pro- viding a lower bound or an improved algorithm for the bandit setting remains thus open. Our results show that is possible obtain improved bounds for the separable
while maintaining satisfac-
'This is a version different from the one described by Kakade et al. (2008), in particular, we replaced U in their Algorithm I with the gradient of the importance weighted hinge loss.

---

tory results for the non-separable case. However, as Beygelzimer et al. (2019) show. it is possible to obtain even better guarantees in the separable case of the bandit setting. An algorithm guaranteeing O I2) mistakes in the separable case and O surrogate regret in the non-separable case, without prior knowledge of the separability, would therefore be an interesting contribution.
Acknowledgments and Disclosure of Funding
Federico Fusco and Dirk van der Hoeven gratefully acknowledge partial sup- port by the MIUR PRIN grant Algorithms, Games, and Digital Markets (ALGADIMAR) Nicolò Cesa-Bianchi was also supported by the EU Horizon 2020 ICT-48 research and innovation action under grant agreement 951844 951847, project ELISE. Federico Fusco also supported by the ERC Advanced Grant 788893 AMDROMA "Algorithmic and Mechanism Design Research in Online Markets".
Nicolò
References
Alon, N., Cesa-Bianchi, N., Dekel, O., and Koren, T. (2015). Online learning with feedback graphs: Beyond bandits. In Conference on Learning Theory, volume 40, pages 23-35.
Alon, N., Cesa-Bianchi, N., Gentile, C., Mamnor, S., Mansour, Y., and Shamir, O. (2017). Non- stochastic multi-armed bandits with graph-structured feedback. SIAM Journal on Computing, 46(6):1785-188
Arora, R., Marinov, T. V., and Mohri, M. (2019). Bandits with feedback graphs and switching costs. In Advances in Neural Information Processing Systems, pages 10397-10407.
Beygelzimer, A., Langford, J., Li, I.., Reyzin, L.., and Schapire, R. 1). Contextual bandit algo- rithms with supervised learning guarantees. In International Conference on Artificial Intelligence and Statistics, pages 19-26.
Beygelzimer, A., Orabona. F., and Zhang, C. (2017). Efficient online bandit multiclass learning with o(VT) regret. In International Conference on Machine Learning, pages 488-497.
Beygelzimer, A., Pal, D., Szorenyi, B., Thiruvenkatachari, D., Wei, C.-Y., and Zhang, C. (2019). Bandit multiclass linear classification: Efficient algorithms for the separable case. In International Conference on Machine Learning, pages 624-633.
Cesa-Bianchi, N., Conconi, A., and Gentile, C. (2003). Margin-based algorithms for information filtering. Advances in Neural Information Processing Systems, pages 487-494.
Cesa-Bianchi, N., Conconi, A., and Gentile, C. (2005). A second-order perceptron algorithm. SIAM Journal on Computing, 34(3):640-668.
Dasa-Bianchi, N., Gaillard, P., Gentile, C., and Gerchinovitz. S. (2017). Algorithmic chaining and the role of partial feedback in online nonparametric learning. In Conference on Learning Theory, pages 465-481.
Cesa-Bianchi, N., Gentile, C., Zaniboni, I.., and Warmuth, M. (2006). Worst-case analysis of selec- tive sampling for linear classification. Journal of Machine Learning Research, 7:1205-1230.
Cohen, A.. Hazan, T., and Koren, T. (2016). Online learning with feedback graphs without the graphs. In International Conference on Machine Learning, pages 811-819.
Cortes, C., DeSalvo, G., Gentile, C., Mohri, M., and Yang, S. (2019). Online learning with sleeping experts and feedback graphs. International Conference on Machine Learning, pages 1370- 1378.
Crammer, K., Dekel, O., Keshet, J., Shalev-Shwartz, S., and Singer, Y. (2006). Online passive- aggressive algorithms. Journal of Machine Learning Research, 7:551-585.
Crammer, K., Kulesza, A., and Dredze, M. (2009). Adaptive regularization of weight vectors. In Advances in Neural Information Processing Systems, pages 414-422.
10

---

Crammer, K. and Singer, Y. (2003). Ultraconservative online algorithms for multiclass problems. Journal of Machine Learning Research, 3:951-991.
Daniely, A., Gonen, A., and Shalev-Shwartz, (2015). Strongly adaptive online learning. In International Conference Machine Learning, pages 1405-1411.
Feng, Z. and Loh, P.-L. (2018), Online learning with graph-structrred feedback against adaptive adversaries. In IEEE International Symposium on Information Theory, pages 931-935.
Feng, Z., Podimata, C., and Syrgkanis. V. (2018). Learning to bid without knowing your value. In ACM Conference on Economics and Computation, pages 505-522.
Fink, M., Shalev-Shwarz, S., Singer, Y., and Ullman, S. (2006). Online multiclass learning by interclass hypothesis sharing. In International Conference on Machine Learning, pages 313-320.
Foster, D. J., Kale, S., Luo, H., Mohri, M., and Sridharan, K. (2018). Logistic regression: The importance of being improper. In Conference On Learning Theory, pages 167-208.
Han, Y., Zhou, Z.,, Flores, A., Ordentlich, E., and Weissman, T. (2020). Learning to bid optimally and efficiently in adversarial first-price auctions. arXiv preprint Mxiiv:0007.05566
Hazan, E. and Kale, (2011). Newtron: an efficient bandit algorithm for online multiclass predic- tion. In Advances in Neural Information Processing Systems, pages 891-899.
Helmbold, D. P., Littlestone, N., and Long, P. M. (2000). Apple tasting. Information and Compula- tion, (61(2)85--339
Van der Hoeven, D. (2020). Exploiting the surrogate gap in online multiclass classification. Ad- vances Neural Information Processing Systems, 33.
Kakade, S. M., Shalev-Shwartz, S., and Tewari, A. (2008). Efficient bandit algorithms for online multiclass prediction. In International Conference on Machine Learning, pages 440-447.
Kocák, T., Neu, G., and Valko, M. (2016). Online learning with noisy side observations. In Artificial Intelligence and Statistics, pages 1186-1194.
Lattimore, T. and Szepesvári, (2020). Bandit algorithms. Cambridge University Press.
Liu, F., Zheng, Z., and Shroff, N. B. (2018). Analysis of thompson sampling for graphical bandits without the graphs. In Conference on Uncertainty in Artificial Intelligence, pages 13-22.
Lykouris, T., Sridharan, K., and Tardos, f.. (2018). Small-loss bounds for online learning with partial information. In Conference on Learning Theory, pages 979-986.
Lykouris, T., Tardos, E.,, and Wali, D. (2020). Feedback graph regret bounds for Thompson sampling and UCB. In Algorithmic Learning Theory, pages 592-614.
Mannor, and Shamir, O. (2011). From bandits to experts: On the value of side-observations. In Advances in Neurul Information Processing Systems, pages 684-692.
Novikov, A. (1962). On the convergence proofs for perceptrons. Proc. of the Symposium on the Mathematical Theory of Automata, vol XII, pages 615 6222.
Orabona, F. and Pál. D. (2018). Scale-free online learning. Theoretical Computer Science, 716:50- 69.
Rennie, J. D. and Srebro, N. (2005). Loss functions for preference levels: Regression with discrete ordered labels. Proceedings of the IJCAI multidisciplinary workshop on advances in preference handling, volume 1, pages 180-186.
Rosenblatt, F. (1958). The perceptron: probabilistic model for information storage and organiza- tion in the brain. Psychological review, 65(6))386.
Sculley, D. (2008). Advances in online staming-based spam filtering. PhD thesis, Tufts University.

---

Tossou, A., Dimitrakakis, C.. and Dubhashi, D. (2017). Thompson sampling for stochastic bandits with graph feedback. In AAAI Conference on Artificial Intelligence, volume 31.
Zhou, X. (2018), On the fenchel duality between strong convexity and lipschitz continuous gradient. arXiv preprint arXiv:1803.0653 1803.06573.
Zinkevich, M. (2003). Online convex programming and generalized infinitesimal gradient ascent.
In International Conference on Machine Learning, pages 928-936.
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] Our contributions are primarily theoretical and we clearly state the assumptions under which our theoretical results hold.
(c) Did you discuss any potential negative societal impacts your work? [No] Our contri- bution is primarily theoretical. Therefore, this work does not present any foreseeable socictal consequence.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Although some proofs have been deferred to the appendix due to space constraints.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] In our reporting of the experiments we include the best and worst performance of each algorithm.
(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
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either in the supplemental material or URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/eurating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifi-
able information or offensive content? [No] The data synthetic
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links 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]
12


Reviews:
[{"review_id": "vWyqBh3lrmp", "reviewer": "Reviewer_V4xK", "summary": "This work presents Gappletron, an algorithm for online multiclass classification with a feedback graph (which can be viewed as a generalization of bandit feedback). The closest point of comparison is perhaps its predecessor, Gaptron, which also solved the online multiclass classification problem, but with bandit feedback rather than a general feedback graph. The paper provides guarantees on the surrogate regret both in expectation and with high probability. The paper also provides some supporting synthetic experiments showcasing Gappletron outperforming other algorithms for online multiclass classification.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "In the online multiclass classification problem, the learner gets to observe a sequence of feature vectors x_t and make a series of class predictions y’_t. Under classic bandit feedback restrictions, the learning algorithm only learns whether the prediction it made is correct or not, but what the correct class label was. This paper considers the more complex case of feedback graphs, where a directed graph (with a vertex for every class) indicates which classes are revealed to be wrong/correct when a particular class is predicted (edges run from the latter to the former). This can capture a variety of realistic cases, such as spam classification, where the user only evaluates whether an email is spam or not when the algorithm has guessed it is not spam.\n\nThis paper provides an algorithm, Grappletron, that achieves O(B sqrt(rho K T)) expected surrogate regret, where B is a bound on the reference predictors, rho is the size of the smallest dominating set in the feedback graph, K is the number of classes, and T is the number of rounds. The paper gives a similar bound that holds with high probability rather than in expectation. To complement this positive result, the paper also proves an Omega(B^2 K + sqrt(T)) lower bound. Applying the standard a^2 + b^2 >= 2ab trick, this can imply a Omega(B sqrt(K) T^¼) lower bound, leaving only a slack factor of sqrt(rho) T^¼ between upper and lower bounds.\n\nIn contrast, the experimental section of this paper is a little on the weaker side. The test data is synthetic and the parameters are set by theory rather than hand-tuned. I do wish the paper had slightly more space to dedicate to its experimental figures; some of the whiskers are so small in Figure 2 that they clip into the symbol for the averages.\n\nHowever, compared with prior work, I think the experimental efforts are a step in the right direction. To contrast, the Gaptron paper has no experimental section. Overall, I lean towards acceptance of this paper at NeurIPS.\n\nMinor:\n- Line 60: “we prefer the former former”: Repeated word.\n- Line 144: “For example, in label efficient classification, querying the true label y_t corresponds to playing a revealing outcome.” Based on the description of this problem in the introduction, the only revealing outcome is the special node where the learner asks a “human expert for the true label”; even guessing the true label itself reveals no information. I think it would be more clear if this distinction was better emphasized here.\n\n-----\nI've read the author's response, thanks.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I agree with the paper that the main limitation is that the scope of contributions is largely restricted to theory, with much weaker experimental / practical evidence to back it. That being said, I do feel that the core problem is of interest to the community and I could imagine that exposure at NeurIPS might help lead to more practical work on the problem.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "ZFgjGtystC", "reviewer": "Reviewer_SLin", "summary": "This work is interested in designing an algorithm for online multiclass classification with partial feedback determined by a graph. The measure of performance is the surrogate regret i.e. 0/1 loss for the learner and a surrogate loss for the comparative class.  The authors defined an algorithm called Gappletron and abound on its statistical performance is proved. In the special case of full information, Gappletron achieves constant regret. Otherwise the latter is bound by O(\\srqt{T}) with multiplicative constant depending on some quantities of the feedback graph. The authors also show a high probability upper bound, a lower bound and some experiments.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This work mainly relies on tools developed in (van der Hoeven 2020) exploiting the gap between the zero-one loss and surrogate losses. While (van der Hoeven 2020) have only considered full information and the bandit setting, the authors considered a more general setting where the feedback is determined by a graph. Moreover, they have a bit simplified the original proof thanks to Lemma 1 and allowed to use other OCO algorithm than OGD.\n\nThe quality of the writing is good. The theorems and assumptions are clearly stated. The proofs in the appendices are easy to follow. I have only checked the proof of Theorem 1 and associated lemmas which seem correct. I appreciate the effort provided to show a high probability bound and a lower bound. Ideally, it would have been great to have a lower bound depending on \\rho and Q like in the upper bound but it may be complicated.\n\nThis work is a follow up of a recent work which address new cases of interest (spam filtering, label efficient classification...). Its impact should be moderate.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "VRz6NsqlrlW", "reviewer": "Reviewer_fiNV", "summary": "The authors propose a new setting for online multi-classification where the feedback is an arbitrary graph. They provide both upper and lower bound for the separable and the non-separable cases. In synthetic experiments, the authors show that their algorithm performs better than or comparable to previous work.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Originality: the authors show a new setting that generalizes online multi class classification. The bandit setting is a version of their setting. They improve upon the GAPTRON algorithm to the feedback graph setting and derive upper and lower bounds in the full information setting.\n\nClarity: the paper is mostly clear. My one feedback here is that the authors have introduced notation that they later define (dominating set for example) but it makes the reader have to skip back and forth. The main concepts could be defined earlier instead of waiting to introduce them in the notation section.\n\nSignificance: the general lower bounds and the synthetic experiments are interesting but the upper bounds are only for a specific case limiting the potential scope of the work.\n\nFeedback: the bounds seem to apply for the full information setting but the novelty of an arbitrary graph is that it can represent more general functions. While this is an interesting extension, the bounds are limited to a specific setting. They have a general lower bound but the statement that they are close to the upper bound only applies for the specific case of full information. The general graphs are motivated by practical examples like spam filtering, online multi class labeling. It would make the paper stronger to then take some existing datasets to compare the performance of the algorithms on actual data instead of just synthetic data.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. This is a theoretical paper whose societal impact is hard to asses and the authors acknowledge as much", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "7Ebr2fjRmVX", "reviewer": "Reviewer_CwtQ", "summary": "The paper explores alternative feedback models for online multiclass classification problems. More precisely the authors assume a graph feedback model where taking an action reveals outcomes for several other actions. Under this model the authors provide an algorithm called GAPPLETRON and analyze the regret guarantees of this algorithm. Experimental results are provided for some synthetic settings.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "I do not have many comments, but what was not clear to me is what is the use of the gap map and if there are good ways to construct the gap map. \n\nI would suggest running experiments on real multi-class problems with an appropriately designed feedback. Such an experiment would be more useful than experiments on synthetic datasets.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies an online multiclass classification problem with feedback graphs, which interpolate between the bandit and full information setting. The algorithmic technique generalizes the surrogate gap observations of van der Hoeven (2020), the main theoretical results provide a fairly complete picture of achievable regret bounds, and some experiments are conducted. 

The main concern raised by the reviewers is that the paper is fairly incremental relative to van der Hoeven (2020). Indeed, it seems like the paper applies the same techniques to a well-established setting of online learning with feedback graphs. While this is a reasonable contribution, we think it is not sufficiently innovative for the conference and so we are recommending rejection. 
Decision: Accept (Poster)