Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The author proposed an online learning setting where the true label is determined by which of k centers is the closest from the query point for a distance function.  The goal of the learner is to minimize the total distance from each query to the region corresponding to the correct label. The authors then propose learning algorithms for these settings and provide a theoretical analysis of the proposed algorithms. The authors also show interesting properties of this learning setting that could not be achieved in the traditional multiclass learning setting.
main_review: **Strengths**
1. The new learning setting that proposed by the author is interesting. The framework allows the learner to quantify how wrong the prediction is based on the geometry of the data.
2. The proposed learning algorithms are backed up with strong theoretical analysis.
3. The theoretical results presented in the paper are interesting.
4. The authors provide a thorough theoretical analysis of the learning setting and the proposed algorithms.

**Weaknesses, Concerns, and Questions**
1. The paper contains a lot of new concepts and theoretical analyses. However, the presentation makes it hard to understand. 
2. The author presented a new learning setting. Although the learning setting is theoretically interesting, I suggest the author explain more about the motivation of the setting, for example, by providing a concrete example of applications where the learning setting may be useful. 
3. Since it contains many new concepts, I suggest the authors explain more the connection of the new concepts with the well knows terminologies in the traditional multiclass setting. 
4. Additionally, some illustrations will be useful to help the reader understand the concept and the proposed algorithm, particularly since it is promoted as a geometrically-based method.

In conclusion, I think the proposed learning setting and algorithms are in the interest of the machine learning community. The results and analyses are also interesting. However, I would suggest the author to make the presentation easier to understand by the reader as I mentioned above.


limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes an online multiclass classifier that minimizes the distance between a point and the correct class partition for that point’s label. They argue that this loss function punishes more harshly points that are classified as extremely wrong versus almost correct. They propose an algorithm where in every round, their classifier predicts a point and suffers the distance based loss between their predicted point and the correct class region.

main_review: The paper seems well defined and theoretically sound although I do not think NeurIPS is the correct venue. The paper seems to prove the existence of algorithms with certain properties, but does not elaborate on what the algorithm they are proposing is explicitly. Such a theoretical paper may be better served in a venue such as COLT. It also is clear that there is not nearly enough space in the page limits for this paper.

I do not recommend putting the results section at the beginning of the paper. There is no context for what is discussed there and is extremely confusing until you read the rest of the paper. It also is a waste of space as it is a restatement of theorems that are presented later in the paper. Especially as this paper is already packed with material and space is scarce.

Line 52: what is a time horizon T?

Line 148/149: It is not clear why learning the subsets directly corresponds to being able to label points in an online manner. It is also not clear why the learner is given an adversarially chosen query point in round t; is this point adversarial because it is simply hard to label or the predicted label was wrong in the previous round?
limitations_and_societal_impact: Limitations: Yes
Negative Societal Impact: N/A, this is a theory paper
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers the problem of online prediction of which region of a k-centred nearest-neighbour partition (where “nearest” is defined via a “distance” function) a point is in. The feedback on each trial is which region the point is in - as in standard online learning. However, instead of bounding the number of mistakes, this paper seeks to bound the total loss, where the loss on a trial is the “distance” of the point to the region predicted (see the main review for a confusion I have here). The paper considers two types of “distance” - the (negative of the) inner product and the p-norm. The paper gives loss bounds that are independent of the total number of trials and don’t have a “margin” term.
main_review: I am surprised that nobody has studied this problem before, especially in the k=2 (separating hyperplane) case - perhaps nobody was able to get anywhere with it until now. If this is truly original then it is an important result and should be accepted. There is one major confusion that I have though - in line 161 what does delta(q,R_i) mean? Surely to be consistent with the abstract it should mean the distance from q to the nearest point in R_i but to be consistent with line 212 it should be the distance from q to the centre of R_i???
Some comments:
Line 77 - you should state here that by “metric” you don’t necessarily mean a metric space (inner product isn’t) and can even be negative.
Line 91 -  “poly(p , d)” should be explicitly written.
Line 211 - around here you drop the subscript t on many qs
limitations_and_societal_impact: The algorithm is not robust to noise at all - give the algorithm one incorrect label and it completely breaks.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The work addresses an online learning problem, where the algorithm receives a sequence of points q_1,q_2,... in the d-dimensional unit ball, and must guess the label of each point among k possible labels {1,...,k}. The correct label corresponds to a nearest-neighbor partition of the ball, R_1,...,R_k determined by k unknown "centers" x_1,...,x_k. If the algorithm predicts that a point q has label i, it incurs a loss equal to the distance between q and the subset R_i of the points labelled as i. The goal is to minimize the total loss. The main result is a set of upper bounds on the loss in the form poly(d), or similar, but in any case independent of the length T of the sequence. The work considers also the special case k=2, the case of general convex classes (for which it gives lower bounds), as well as some other implications of the upper bounds.

main_review: TLDR: I think this is a good contribution. I believe it could be written in a better way, see below.

Originality: good. The main results are obtained starting from a technique introduced recently, but they are not just a corollary of it. Moreover, different results are obtained through proofs, and some of them require substantial work and a good understanding of the mechanisms behind.

Quality: I did not check the proofs. I would *expect* the quality to be ok based on how the manuscript is written.

Clarity: good. However, I think it that the Introduction can be improved. I would for example pin down the notation more explicitly, since you are studying several variants of the same problem and thus definitions "in words" alone tend to be difficult to follow (the notation is very light and therefore there's room for this). Similarly, I would make the theorem statements more exhaustive, and in particular I would specify the loss under examination (in Theorem 2 the loss is not specified). More in general, I think the results could be structured in a better way; there are many of them, of different kinds, and it's not easy to get the big picture. Otherwise said: what is the main message of this paper?

Significance: fair. The results are significant, as the problem seems basic and the bounds are interesting. I must also say, however, that I find a slight dissonance between the declared goal (margin-independent multiclass learning, see the title) and what the paper actually achieves. First, the "margin independence" can be obtained for any algorithm by simply incorporating the distance into the loss. It is true however that the algorithm presented here subsume the margin-based algorithms in some sense (Thm 5 and Thm 6), so it's not too incorrect to claim "margin independence". Second, the multiclass setting boils down to a very specific scenario: classifiers that are induced by a Voronoi partition. This somewhat clashes with the generality of the first part of the paper.

SPECIFIC COMMENTS:

L48: should you require v to be a unit vector?
1.1: I think that a picture of v,q, and the R_i would help
L68: What do you mean by "we have no control over what feedback we learn about the hidden vector"? In both problems (and in most problems I have seen) the algorithm does not decide what feedback it gets, right?
Theorem 2: you have not specified the loss here. What is it? The same as in 1.1.1 but with the inner product replaces by \delta I guess?

limitations_and_societal_impact: The limitations are discussed adequately. There are no foreseeable societal consequences.
review_title: null

Meta-review: The reviewers are in consensus after discussion that this paper should be accepted even if the score of one reviewer does not reflect this. It is strongly suggested that the presentation around the Introduction be updated (see reviews) and also to make sure that terms with technical meanings such as adversarial are defined for the general reader.
Decision: Accept (Poster)