Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
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.

Clarity: 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.

Significance: 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.

Feedback: 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.
limitations_and_societal_impact: Yes. This is a theoretical paper whose societal impact is hard to asses and the authors acknowledge as much
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

This 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.

In 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.

However, 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.

Minor:
- Line 60: “we prefer the former former”: Repeated word.
- 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.

-----
I've read the author's response, thanks.
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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

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. 

I 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.
limitations_and_societal_impact: NA
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

The 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.

This 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.
limitations_and_societal_impact: -
review_title: null

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)