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": "cHGDx3vo5ei", "reviewer": "Reviewer_u4LL", "summary": "This study deals with (adversarial) online multiclass classification problem with partial feedback about the true label.\nThe feedback is characterized by a directed graph on the label space,\nthrough which the model includes the full-information setting, the bandit feedback setting, the spam-filtering problem setting,\nand so on.\nFor this general problem setting,\nan algorithm called GAPPLETRON is developed.\nThe performance is measured in terms of the surrogate regret,\nthe difference between the number of mistake and cumulative loss for an optimal model.\nThe proposed GAPPLETRON algorithm achieves nearly optimal surrogate-regret bounds both for non-separable and for separable cases.", "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": "Originality:\n\nTo the best of my knowledge,\nthis is the first study that deals with the online multiclass classification with feedback graph.\nHowever,\nas mentioned in the paper,\neach of online multiclass classification and the model of feedback graph is not new.\nSince it is a natural idea to combine these elements, the problem setting itself is not very original.\nThe proposed algorithm is based on unbiased estimator for loss functions and online convex optimization,\nwhich is a standard approach for bandit optimization problems.\nThe surrogate-regret analysis for the proposed algorithm appears to contain new ideas,\nwhich relay on the regularity of the surrogate losses.\n\nQuality: \n\nAs far as I can see, no technical errors have been found.\nI think the authors are careful and honest about evaluating both the strengths and weaknesses of their work.\n\nClarity:\n\nThe main part of the paper is clearly written.\nOne question I had was whether the proposed algorithm could be compared with BANDITRON by Kakade et al.(2008),\nwhich has been analyzed for the hinge loss (with $\\kappa = 0$).\nIn my understandint,\nas the hinge loss does not suffice the assumptions of (2) and (3),\nGappletron has not yet been proven to be superior to BANDITRON.\nIn my understanding is correct,\nthe description in lines 84--98 may be misleading.\nI think it is important to emphasize that BANDITRON employs hinge loss and that the analysis for Gappletron does not directly apply.\n\nSignificance:\n\nThis work considers a new problem setting, which will be of interest to the research community of online learning.\nThe proposed algorithm is simple and works well for various situations including non-separable cases.\nI think that this work has a certain impact on the research community online learning.\nIt would be better if \nthe dependence of regret bounds on graph-structure parameters (e.g., the parameter $\\rho$)\ncould be analyzed more precisely,\nas in the literature by Alon et al.(2015) and by Alon et al.(2017).\nI'm also interested in cases where the regularity assumptions are relaxed.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "A more detailed explanation of the limitations resulting from the regularity assumption (Eq. (2), (3)) would be appreciated.\nFor example, it would be good to have information on which existing studies meet this assumption and which do not.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "bPZJSCF5mJi", "reviewer": "Reviewer_p3fb", "summary": "This paper studies the problem of active online multiclass classification. As opposed to previous works, this paper introduces the additional complexity of gathering data via a feedback graph, as opposed to past works that consider either bandit feedback or the full information case. The authors present an algorithm referred to as Gappletron. The algorithm begins with a max margin prediction of the labels and then breaks into cases. If the action is `revealing’- meaning that its feedback leads to the full information case due to the structure of the feedback graph, then a distribution is computed, and arms appear to be pulled in proportion to an estimated gap. Otherwise, more uniformity enters into the distribution. Following drawing the sample, the algorithm updates loss estimates via IPS. Finally, the algorithm updates a set of weights using the loss estimates and calls out to a generic online convex optimization routine. The feedback graph affects the guarantees that the authors are able to show. The algorithm suffers regret O(B\\sqrt(\\rho * K * T)) where K is the number of classes and \\rho is the domination number of the graph. It should probably be noted that since, as the authors note, finding the smallest dominating subgraph is NP complete, a greedy approximation algorithm must be used and one would instead expect a dependence on \\rho * \\log(\\rho). The authors prove via a lower bound that this complexity is not significantly improvable. They show a lower bound of max(B^2*K , \\sqrt(T)). In order to prove their theoretical results, the authors follow the same approach is van der Hoeven 2020 whereby they assume a surrogate loss for the 0/1 loss and control the surrogate regret. The paper concludes with several experiments demonstrating the power of their approach. ", "questions": "", "limitations": "", "rating": 6, "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": "Strengths: The setting of a feedback graph is very natural and covers many problems of practical interest. The guarantees in this setting seem natural. The lower bound is a good step towards understanding the complexity of this problem, though they seem to be independent of \\rho which is a key parameter for the upper bounds. I also appreciate that the authors provide results both in expectation and with high probability for their regret guarantees. Interestingly, they seem to not be achieved by simply taking \\delta = 1/T as has been done in other works. Additionally, the results cover both the separable and non-separable settings, in contrast to prior work. Finally, the algorithm shows strong empirical promise versus the chosen baselines. \n\nWeaknesses: My most major issue is that while the idea is novel, the paper borrows heavily from the techniques of van der Hoeven, 2020- leading to the paper feeling like more of an extension of that work than an independent work. Furthermore, the clarity of the writing could be improved throughout. Especially given the number of assumptions made in this paper, it would have been nice to have a clear, worked out example of all of these assumptions and the guarantees. While I appreciate the level of generality this paper is going for, it would be nice for example to have a quick subsection like one of the subsections of section 4 or 5 in van der Hoeven showing the result in a specific case. Additionally, when the algorithm is presented, smaller theoretical guarantees are interspersed with the description of the functioning of the algorithm, and this is to the detriment of the transparency of both the theory and the algorithm. \n\nComments:\n-\tIn the intro, the authors note a difference in the order of T in the regret of T^0.5 vs T^2/3. This seems like a major difference, but this is not addressed after the introduction. \n\nMinor comments:\n-\tLine 131: typo, “equivalent to saying” rather than “equivalent to say”\n-\tThe quantity h(U) is referenced before assignment\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Neither are really covered. As the neurips website notes, https://neurips.cc/Conferences/2021/PaperInformation/PaperChecklist, a paper being theoretical is not grounds for the authors ignore the societal impacts of the work. I mention this as a note for future work and not as a contributing factor to my score. \n\n", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}, {"review_id": "Tm9Qb0DjfUf", "reviewer": "Reviewer_Qt6c", "summary": "This paper considers the problem of online multi-class classification, in which the learner sequentially predicts an output among K classes after observing an input vector. Following the work of van der Hoeven (2020), the authors consider a surrogate regret in which the cumulative number of mistakes incurred by the learner (with zero-one loss) is compared to the cumulative surrogate loss of the best parameter in a ball. The surrogate loss can be the multi-class Hinge loss or the multi-class logistic loss. \n\nThis paper generalizes the results and the algorithm of van der Hoeven from bandit and full-information feedback to feedback graphs, proving a new surrogate regret bound that depends on the domination number. Furthermore, they prove the first high-probability regret bound for the problem. Similar to van der Hoeven, they provide improved bound for the separable case and prove a lower-bound.", "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": "The paper is generally well written. The main contributions are the following:\n- New algorithm (Gappletron) for online multi-class classification. Compared to previous algorithms, the algorithm can deal with general surrogate losses and general feedback graphs, which was not the case for previous analysis.\n- New upper-bounds on the surrogate regret. The main novelties are: \n    - the bounds hold in high-probability while previous bound were in expectation only;\n    - extension of the analysis to feedback graphs: the number of actions from the bandit setting is replaced with the domination number which can be significantly smaller. \n- New matching lower-bound that show that sqrt{T} is not improvable with general feedback graphs (which was not the case for full-information). I was a bit disappointed with the fact that the lower-bound only holds for the worst feedback graph. It would have been much stronger if it could depend on the domination number.\n- Gappletron seems to significantly outperform the proposed baselines on the synthetic experiments proposed in the paper. \nIn general, I find the contributions are interesting but not so much surprising. The generalization from bandit feedback to feedback graphs, with bounds that depend on the domination number, is already well studied in the bandit literature. Furthermore, the improvement of the bounds by using the gap between the surrogate loss and the zero-one loss was already present in van der Hoeven (2020). Yet, having a matching lower-bound and having the results in high-probability is an interesting technical contribution.\n\nComments: \n- About the h.p. upper-bound (Thm 2): I unfortunately not had time to go through the proof in details, but I was a bit surprised by its length. Since the bound is of order sqrt{T}, why isn't it possible to just use the bound in expectation together with an Azuma-Hoeffding type inequality (or your Lemma 4) and directly use it together with Thm. 1?\n- In your experiments, Gaptron is not used as a baseline in the bandit setting. Does Gappletron in this case coincides with Gaptron?\n\nTypos:\n- What is 1_S in Alg 1?\n- domain R^{Kxd} as input in Alg 1\n- Initialize W_t in Alg 1\n- What is delta' in Thm 5?\n- I would define hat g_t with hat ell_t in line 208. And then say that for the full info setting \\hat \\ell_t = \\ell_t", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "7eCH3ZPUDVc", "reviewer": "Reviewer_TAuC", "summary": "The authors study the problem of multiclass classification where the feedback is determined by an arbitrary directed graph, where each node corresponds to an action by the learner and has at least one incoming edge, and if there is an edge from node a to b, then the learner, on performing action a, observes the loss of action b. This model is a generalization of the bandit feedback case, and has applications in other problems. They present GAPPLETRON, an online multiclass algorithm for arbitrary feedback graphs, and prove surrogate regret bounds. They also present experimental results that show competitive performance of GAPPLETRON against various baselines. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "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": "The problem is well motivated and the results seem novel. While the result is well presented and appears to be correct, I am unable to accurately review the paper in the context of originality and significance because I feel like I lack the domain knowledge to accurately assess the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "While not limitations, the authors do discuss potential improvements to the result, and have mentioned that since their result is mainly theoretical there is no foreseeable societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4-5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies a new problem setting of online multiclass linear classification with graph-structured feedback. The reviewers agree that it is of interest to the online   learning research community. In summary, the paper: 
- proposes the Gappletron algorithm that can establish regret guarantees against a wide range of surrogate loss functions; 
- proves high probability regret bounds that are new
- gives a new \sqrt{T} regret lower bound
- gives improved experimental results against prior art

The reviewers also pointed out that studying: (1) the regret's fundamental dependence on the graph independence number \rho (e.g. by showing lower bounds in term of \rho); (2) whether the results can be extended to the commonly-used hinge losses, are important future directions. The reviewers would also like the authors to incorporate their rebuttal on comparison with prior art into the final version.
Decision: Accept (Poster)