Margin-Independent Online Multiclass Learning via Convex Geometry
Authors: Guru Guruganesh
Allen Liu
Jon Schneider
Joshua Ruizhi Wang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Multiclass Classification
Online Learning

Abstract: We consider the problem of multi-class classification, where a stream of adversarially chosen queries arrive and must be assigned a label online. Unlike traditional bounds which seek to minimize the misclassification rate, we minimize the total distance from each query to the region corresponding to its assigned label. When the true labels are determined via a nearest neighbor partition -- i.e. the label of a point is given by which of $k$ centers it is closest to in Euclidean distance -- we show that one can achieve a loss that is independent of the total number of queries. We complement this result by showing that learning general convex sets requires an almost linear loss per query. Our results build off of regret guarantees for the problem of contextual search. In addition, we develop a novel reduction technique from multiclass classification to binary classification which may be of independent interest. 

Margin-nndependenn Online Multiclass Learning via
Convex Geometry
Guru Guruganesh Google Research gurug0google. com
Allen Liu MIT c1iu5680mit.cm
Jon Schneider Google Research jschnei@google.o com
Joshua Wang Google Research j joshuawang@goolle.com
Abstract
We consider the problem of multi-class classification, where stream of adversari- ally chosen queries arrive and must be assigned label online. Unlike traditional bounds which seek to minimize the misclassification rate, we minimize the total distance from each query the region corresponding its correct label. When the true labels are determined via a nearest neighbor partition - i.e. the label of point is given by which of centers is closest in Euclidean distance we show that one can achieve a loss that is independent of the total number of queries. We complement this result by showing that learning general convex sets requires an almost linear loss per query. Our results build off of regret guarantees for the geometric problem of contextual search. addition, develop novel reduction technique from multiclass classification to binary classification which may be of independent interest.
Introduction
Online multiclass classification is ubiquitous problem in machine learning. In this problem, learning algorithm is presented with a stream of incoming query points and is tasked with assigning each query with label from fixed After choosing label, the algorithm told the true label of the query point. The goal of the algorithm is to learn over time how to label the query points as accurately possible.
Traditionally, theoretical treatments of this problem are built around the notion a margin ry This margin represents the extent to which the imput points are well-separated from the boundaries between different labels. For example, the analysis of the classic Perceptron algorithm [Nov63] guarantees that it makes at most (11/²2) mistakes when performing binary classification, long all query points are distance at least y from a hyperplane separating the two classes. More sophisticated analyses and algorithms (relying on e.g. hinge loss) do not necessarily assume the classes as well separated, but still inherently incorporate a margin 7 (for example, the hinge loss associated with a point is positive unless it is --separated).
In this paper, we present an alternative to the traditional margin approaches. Our approach weights each mistake by how ambiguous the classification task is for that point, rather than penalizing all mistakes equally. More precisely, consider a partition of the space of all possible query points into regions R, where R& contains all query points whose true label is i. In our formulation assigning query point q a label incurs a loss of Egg. R₂), where E(g, R&) should be thought of as the distance needed move q so that it lies in R₃ (i.e., for it to be labelled correctly). For example, in the case of
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

a linear classifier, l(g. R&) is zero if is correctly classified, and the distance to the classifier if is incorrectly classified. The goal of the algorithm is to minimize the total loss.
This notion of loss not only measures the rate of errors but also the degree of each error; choosing wildly inaccurate label is punished more than selecting label that is "almost" correct. This fine-grained approach to looking at errors has occurred in other areas of machine learning research as well. For example, the technique of knowledge distillation is based on training smaller model on the logits produced by larger model [HVDI5]. Hinton et al. explain, "The relative probabilities of incorrect answers tell us about how the cumbersome model tends to generalize. An image of BMW, for example, may only have a very small chance of being mistaken for garbage truck, but that mistake is still many times more probable than mistaking for carrot." " Rather than leaning on the power of a trained model, our framework differentiates between these different incorrect answers based on the geometry of the problem.
1.1
Our Results
1.1.1
Learning Linear Classifiers
In this case we have a binary classification problem, where the two regions Ri and R2 are separated by an unknown d-dimensional hyperplane (v,x)) = 0 (with ||e||| = 1). Our loss function in this case is the function (gg R2) = Kg. e)] 1(q & Rs). We prove the following result:
Theorem (Restatement of Corollary 3.1). There exists an efficient algorithm for learning a linear classifier that incurs a total loss of at most Od d).
Note that the total loss in Theorem 1 is independent of the time horizon (number of rounds) T. More importantly, note that this is stronger than the naive guarantee implied by the margin bounds for the Perceptron algorithm. Indeed, each mistake at a distance y from the separating hyperplane is assigned loss (()) in our model. Since the Perceptron algorithm can make up to 0(1/7²) such mistakes, this only implies Perceptron incurs total loss of at most O(1/7) (which blows up as 7 + 0).
Indeed, our algorithm in Theorem I is not based off of the Perceptron algorithm or its relatives, but rather off of recently developed algorithms for problem in online learning known contextual search. In contextual search, a learner is similarly faced with a stream of incoming query points qe and wishes to learn hidden vector v. However, instead of trying to predict the sign of (v. qt). in contextual search the goal is to guess the value of (v. q.) After the learner submits a guess, they told whether not their guess was higher lower than the true value of (v. qs) (and pay a loss equal to the distance between their guess and the truth). The best known contextual search algorithms rely on techniques from integral geometry (bounding various intrinsic volumes of the allowable knowledge set), and are inherently different than existing Perceptron/SVMM-sy al algorithms.
While it may seem like contextual search (which must predict the value of (v, 91) instead of just the sign) is strictly harder than our online binary classification problem, they are somewhat incomparable (for example, unlike in contextual search, we have control over what feedback we learn about the hidden vector v). Nonetheless, classification problem contextual search. This allows to recent results of [LLS20] obtain our O d log d) bound in Theorem 1.
Theorem 8 we show a general reduction from our binary
1.1.2 Learning Nearest Neighbor Partitions
One natural way to split query space into multiple classes is via nearest neighbor partition. In this setting, each label class is associated with "center" xy E RRd and each region RG consists of the points which are "nearest" to 2;. To define "nearest", we introduce similarity metric 5(x, v) representing the "distance" between points æ and in RRd, The two major classes of similarity metrics we consider are: a) the inner-produed similarity 8(x, y) = - (x, y) and b) the L similarity 5(r,y) = || vllp- Given fixed similarity metric ö, our loss function in this case is the function E(g, R,) = 8(g. 2z4) min,- 8(g, Zz- ); other words, the difference between the similarity between q and r; with the similarity between y and its most similar center.
Theorem 2 (Restatement of Corollary 3.3). For inner-prodis proerrprduuct similarity, there exists efficient randomized algorithm for learning a nearest neighbors partition that incurs a total expected loss of at most O log d).
2

---

Like some other algorithms for multiclass classification, our algorithm in Theorem 2 works by running one instance our binary classification algorithm (Theorem 1) for each pair of labels. Unlike some other "alll-s-alll" methods in the multiclass classification literature, however, it does not suffice to run a simple majority vote over these instances. Instead, to prove Theorem 2, we solve a linear program to construct a probability distribution over centers that guarantees that our expected loss is bounded by an expected decrease in total potential of all our (2) sub-algorithms.
Our results for L similarity are follows:
Theorem 3 (Restatement
Theorems 12 and 13). For L similarity, when is a positive even integer, there exists an efficient randomized algorithm for learning nearest neighbors partition that incurs a total expected loss of al most polypoly (p, d)).
For arbitrary p Z 2, if all k centers are A-separated in LP distance, there exists efficient randomized algorithm that incurs a total expected loss of
4-poly(p.d) d)
A
When p is an even integer, it is possible to construct a polynomial kernel that exactly reduces this problem to the problem for inner-pun aener-productee similarity (albeit in the higher dimensional space Rd(++))). When p is not even integer, it is no longer possible to perform an exact reduction to the inner- product similarity problem. Instead, parallel we perform series of approximate reductions to inner-product similarity at multiple different scales (the full algorithm can be found in Appendix! E). Surprisingly, this technique only gives T-independent bounds on the loss when p 2 2. is an interesting open problem to develop algorithms for the case S p < (and more generally, for arbitrary norms).
1.1.3 Learning General Convex Regions
Finally, we consider the case where the regions R& are not defined in relation to hidden centers, but where they can be any convex subsets of Rd. Interestingly, in this case it is impossible achieve total loss independent of T. Indeed, we prove lower bound of ((T2-0(1/4) for the total loss of any algorithm for this setting, even when k: 2.
Theorem 4. Any algorithm for learning general convex regions incurs total loss of at least (T(dd4)/(d22) even when there are only two regions.
1.2 Mistake Bounds and Halving Algorithms
As mentioned in the introduction, classical algorithms for multi-class classification generally try to minimize the mistake bound (the total number of classification errors the algorithm makes) under some margin guarantee y Even though our algorithms are designed to minimize the absolute loss and not -angin-de mistake bound, is natural ask whether our algorithms come with any natural mistake bound guarantees.
We show that algorithms do in fact possess strong mistake bounds, matching the dependence the margin y of the best known halving algorithms. In particular, we show the following.
Theorem 5 (Restatement of Theorem 16). If all query points qu are at least distance 7 away from the separating hyperplane, our algorithm for learning linear classifiers (Theorem 1) makes at most loggogdd/y) mistakes.
Theorem 6 (Restatement Theorem 17). If all query points qe are at least distance 7 away from the boundary between any two regions, algorithm for learning nearest neighbor partitions (Theorem 2) makes at most O log(d/")) mistakes.
In comparison, the best dimension--eependent classical bounds for this problem come from haly- ing algorithms (efficiently implementable via linear programming) which have mistake bounds of (d log(1 log(1/7)) (1/))) and log(l/)) respectively. In the first case, our mistake bound is nearly tight (losing only an additive Od d'). In the second case, our mistake bound is tight up multiplica- tive factor of k; it is an interesting open question whether it is possible to remove this factor of k in our techniques.
All references to the appendix refer the appendices of the Supplementary Material.

---

We additionally introduce a variant on the mistake bound that we call a robust mistake bound that is defined as follows. Normally, when we have a margin constraint of y, we insist that all query points 4: are distance at least away from any separating hyperplane. In our robust model, we remove this constraint, but only count mistakes when the query point qt lies at least y away from the separating hyperplane.
Existing algorithms (both the Perceptron and halving algorithms) do not appear to give any non-trivial mistake bounds in the robust model - it is very important for the analysis of these algorithms that every query point is far from the separating hyperplane. On the other hand, it straightforwardly follows from our notion of loss that if we have an O(R)-loss algorithm for some problem, that algorithm simultaneously achieves an O(R/2) robust mistake bound. In particular, we obtain robust mistake bounds of ((dlog d) and O((A* d lolog d)) for learning linear classifiers and learning nearest neighbor partitions respectively.
Related work The problem of online binary classification (and specifically, of online learning of a linear classifier) is one of the oldest problems in machine learning. The Perceptron algorithm was invented in [Ros58], and the first mistake bound analysis of the Perceptron algorithm appeared in [Nov63]. Since then, there has been a myriad of research on this problem, some of which is well-surveyed in [MR13]. Of note, the first mistake bounds for the non-separable case appear in [FS99]. We are not aware of any work on this problem that investigates the same loss we present in this paper.
Bounds for support vector machines (see [Vap13]) also result in the use of a margin to bound the number of mistakes. Choosing suitable kernel can help create or improve the margin when viewing the data in the "kernel" space. We use a similar technique in proving bounds for generalized L' norms. Our idea is to differently-scale kernels to produce increasingly accurate approximations. To the best of our knowledge, the technique we present is novel. There are other related techniques in the literature, e.g. [SBD06] attempt to learn the best kernel to improve classification error.
Similarly, there is wealth of both theoretical and empirical research on multiclass classification. As far back as 1973, researchers were looking at generalizing binary classification algorithms to this setting (see e.g. Kesler's construction in [DH+73]). One piece of relevant work [CS03), which generalizes online binary classification Perceptron-style algorithms to solve online multiclass classification problems- - in particular, the multiclass hypotheses they consider are same as the nearest neighbor partitions generated by the inner-product similarity metric (although as with the Perceptron, they only analyze the raw classification error). Since then, this work has been extended in many ways to variety of settings (e.g. (CDK+06, CG13, KSST08)).
Another way looking at the problem of multiclass classification is that we are learning how to cluster a sequence of input points into k pre-existing clusters. Indeed, the nearest neighbor partition with 1,2 similarity metric gives rise to exactly the same partitioning as a k-means clustering. There an active area of research on learning how to cluster in an online fashion (e.g. [GLZ14, GLK+11 17, BR20J). Perhaps most relevantly, [LSS16] studies a setting where one must choose cluster labels for incoming points in an online fashion, and then at the end of the algorithm can choose the k centers (the goal being to minimize the total k-means loss of this eventual clustering).
The algorithms we develop in this paper are based off of algorithms for contextual search. Contextual search is problem that originally arose in the online pricing community [CLPL16. LLV17]. The variant of contextual search we reference in this paper (with symmetric, absolute value loss) first appeared in [LS11]]. The algorithms in this paper were later improved in [L.LS20] (and it these improved algorithms that we build off of in this paper).
2 Model
Notation We will write Ba(c, r) to denote the d-dimensional ball in Rd centered at e with radius r. We write Ba in place of (2 1) to indicate the unit ball centered at the origin.
Given an E Rd, we will write ||æ||| p to denote the L" norm of the vector x. In the case of 2, we
will often omit the subscript and write ||x|| in place of ||

---

2.1 Online Multiclass Learning
We will view the problem of online multiclass learning as follows. There are & disjoint regions in some domain, say Ba, labelled Ri through Rg. The region Rg contains the points in Ba that should be assigned the label i. The goal of the learner is to learn these subsets (and thus how to label points in Ba in online manner). Every round f, the learner receives an adversarially chosen query point E Ba. The learner must submit a prediction 4 E [A] for which region Rí, the point qt lies in. The learner then learns which region Rr; the point actually belongs to, and suffers some loss Elg,, Rr,). This loss function should in some way represent how far was from lying in the region Rr, chosen by the learner; for example, in the case where the learner chooses the correct region R1g. E(q, Rı;) should be zero.
In this paper, will consider two specific cases of the above learning problem. In the first case, we wish to learn a nearext-neighhor partition. That is, the k regions are defined by h "centers" 3i, 22.-2..... 3& Ba- Region R2 then consists of all the points which are "nearest" to center ii according to some similarity metric 8(2; y) (where lower values of ((r, y) mean that æ and are more similar; note that (xr y) does not need to be actual metric obeying the triangle-nnequality). Given similarity metric 6(x, y). the loss our algorithm incurs when labelling query with label i is given by E(g, R.) = 5(q, xz) 8(q, x.;)) where R&- is the region containing query q.
We will examine several different possibilities for 8(z, y). including:
o(z,)) y) = -x. 9). We refer to this as the inner-product similarity between x and y. Note that when k = 2, using this similarity metric reduces to the problem of learning linear classifier. For A: > 2, this results in similar partitions to those learned by multiclass perceptrons/ / SVMs [CS03, CDK+06).
6(z, y) = ||I- - yll2: in other words, the Euclidean distance between x and y. When using this loss function, the k regions are given by the Voronoi diagram formed by the & centers Ty.
. For p 2 1, 8(x, v) = || ullp: in other words, the L distance between x and y.
There is a straightforward reduction from the Euclidean distance similarity to the inner-product similarity (see Appendix C), so in Section we will primarily concern ourselves with the inner- product similarity. In Section 4 we will tackle this problem for the case of general L' norms; for some cases (even integer p) is possible perform a similar reduction to the inner product similarity, but in general it is not and we will need to rely on other techniques.
In the second case, we wish learn general convex sets. In particular, there are k disjoint convex sets RI...., Rg S Ba (not necessarily a partition). Each round f, we receive a query point de E - R, guess a region i E [k:). and are penalized against the loss function Eyq, R.) _ minzen, | - x x||2- In other words, we are penalized the minimum distance from ge to the predicted region R, which is zero if our guess was correct. In Section 5 we will show that (even in the case of k = 2), there is no low-loss learning algorithm for learning general convex sets (in contrast to learning nearest neighbors).
Finally, for any > 0 and existing loss function E(g, Rz), we can consider the modified loss function ((1, R₂)) = E(g. R2) Note that this does not change the division of BN into regions, but it can change the total loss incurred by our algorithm (and will be useful for some of our reductions). If in any result we do not specify an a, that means we are taking a = (i.c. the unmodified loss function).
2.2 Contextual Search
One of the main tools will rely on is an existing algorithm for a problem in online learning known as contextual search. For our purposes, the problem of contextual search can be defined as follows. There is hidden point p Ba, unknown to the learner. Every round ł (for T rounds) ad adversary provides the learner with a query vector 2; E B2- The learner must then submit guess Sr for the value of the inner product (2.. p). The learner then learns whether their guess too high or too low. At the end of the game, the learner incurs loss Egg, (I., p)) = 1ge- (I p) for each of their guesses. The learner's goal is minimize their total loss.
Interestingly, there exist algorithms for contextual search with total loss polynomial in the ambient dimension d and independent of the time horizon T.. The first such algorithms were given in [LS
5

---

and used techniques from integral geometry to obtain a total regret of O(d)). More recently, these algorithms were improved in [LLS20] to achieve a regret bound of log d). We will rely on a slightly strengthened variant of the result from [LIS200] to work when the loss function raised to an arbitrary power.
Theorem 7. Let > O. There exists an algorithm for contextual search with loss function Egge. (zt, = 9g: (Te. p)1e that incurs a total loss of at most ( - 'd d).
In particular, Theorem 7 is satisfied by the algorithm from [LLS20]. For completeness, we include a description of the algorithm (along with the proof of Theorem 7) in Appendix A.
3 Learning Nearest Neighbor Partitions
3.1 The Two-Point Case: Learning a Hyperplane
To begin, we will discuss how to solve the k = 2 variant of the problem of learning nearest neighbor partitions for the inner-product similarity function 8(q,
2). Recall that in this setting we have two unknown centers I1 and 22 belonging to Ba. Each round we are given query point q: E Ba. and asked to choose label I [1 of the center that we think is most similar to qu (i.e.. that maximizes 8(g, z)). Letting = 21, and 2; = arg max2, 5(g. I;), our loss in round is zero if we guess correctly (yr- = x;} and is 8(g 2²) } 8(g. yt) if we guess incorrectly (we will also be able to deal with the case when the loss is |ō(g, ax) 8(1, v+) for some or 0). Afterwards, we are told the identity (but not the location) of 27-
Note that the optimal strategy in this game (for an agent who knows the hidden centers 21 and x2) to guess 4, = 1 whenever (g, x1) {q, x2), and to guess 4 otherwise. Rewriting this, we want to guess 4, = 1 exactly when (g, 21 x2) > O. If we let w = I1 I2, we can think of goal as learning the hyperplane (g, w) 0. More specifically, each round we are given a point q and asked which side of the hyperplane lies on. If we guess correctly, we suffer no loss; if we guess incorrectly, we suffer loss equal to the distance from q to this hyperplane. In either case, we learn afterwards which side of the hyperplane lies on.
3.1.1 Reducing to Contextual Search
We will show that we can solve this online learning problem with total loss (ppoy(dd), independent of the number of rounds 7 in the time-horizon. As mentioned earlier, our primary tool will be existing algorithms for problem in online learning known as contextual search.
Recall that in contextual search there is a hidden vector v E Ba, and each round we are given a vector q. E Ba. However, unlike in our problem (where we only care about the sign of the inner product (qt, v)), the goal in contextual search is to submit guess gi for the value of the inner product (qt, v). We then incur loss equal to the absolute distance (gt, va) Sel between our guess and the truth, and are then told whether our guess It was too high or too low.
As mentioned earlier in Section 2.2, there exist algorithms for contextual search with Old d) total loss. Via a simple reduction, we will show that we can apply these algorithms our setting.
Theorem 8. Fix a > O. Assume there exists an algorithm A for contextual search with loss function Egg,. (z) = [g: { p) 1x that incurs regret at most R(d, T). Then there exists an algorithm A' that incurs regret at most R (d, T) for the k = 2 case of learning nearest neighbor partitions with (z. 3) and loss raised to the power a.
similarity metric 6(x, 3)
Corollary 3.1. Fix an a > O. When k = 2, there exists an algorithm for learning nearest neighbor partitions with similarity metric 8(x, y) (xx, 3) and loss raised to the power a that incurs total loss at most O(a-2dlo d).
3.1.2 Potential-Bane Based Algorithms
In order to generalize this to k 2 labels, we will need to open the black box that is our contextual search algorithm slightly. In particular, the argument in the following section requires our algorithm for the k- 2 case to be potential- algorithm.
Before defining exactly what a potential- based algorithm is, it will be useful to define the notion of a knowledge set. For the problem we are considering in this section the lc 2 variant of our problem

---

for inner-produee product similarity we will define the knowledge ser K2 at time t to be the set of possible values for w 21 I2 that are consistent with all known information thus far. Note that since 2 and 22 start as arbitrary points in B2, the knowledge set Ko is simply the set Ba Bd = 2 As the algorithm gets more feedback about w, the knowledge set shrinks; however, since this feedback always of the form of linear constraint (e.g. (qt, w) 2 0), the knowledge set K2 is always a convex subset of R...
Let St be the history of all feedback the algorithm has seen up (but not including) round t; that is S. = (q) J,). (92.15)..... (5),,...((9-11111.. (9--1, Let S, denote the set of possible values for S,, and let S U St. We can think of S, capturing the state of a deterministic algorithm at time l. For now, it is fine to think of St as interchangeable with K2; i.e., the knowledge set K2 captures all relevant details about all feedback the algorithm has observed thus far. (Later, when looking at I. similarity metrics, we will want to keep track of separate knowledge sets at different scales, and thus will want more nuanced notion of potential-ban baase algorithm).
Definition 9. A deterministic algorithm A (for k = 2 and a >> 0) is a potential polential-based algorithm if there exists a potential function & from S to Rzzo and a "loss bound" function L. from S x Ba to Rzo that satisfy:
For all rounds I, ((S++1) S ((:))
Let qu be the query point in round I. Then L(St, q:) is upper bound on the loss incurred by any guess. In other words, L(Se, q6) must satisfy
L(S., 9t) Z
max 21.222
18(9.x1)) - x2))"
comsistent with Sy
Again, let qi be the query point in round t. If A guesses the label incorrectly in round t, then Φ ((S+1) 2 L(S.,q)). q:).
For the case of inner-product similarity, we will set the loss bound function L(S,, ge) equal to the width of the knowledge set K, in the direction gr- Importantly, this choice of L is an efficiently computable (in terms of q and the knowledge set K2) upper-bound on the loss, which will prove important in the following section (in general, we will want both & and L to be efficiently computable in order to efficiently carry out the reduction in Section 3.2).
Note also that such a potential immediately gives way to bound the total loss of an algorithm independently of T; particular, summing the inequality ((S.) ((S,-)) 2 L(Si, q:) over all t gives that the total loss is at most (Su). We call the value ((S)) the initial potential of the algorithm A.
Similar potential-based arguments are used in [LLS20] and [LS18] to give T-independent total loss bounds for the problem of contextual search. Unsurprisingly, these arguments can be extended (via Theorem 8) to apply to the problem of learning nearest neighbors as well.
Theorem 10. Fix an > When k = there exists a potential-based algorithm for learning nearest neighbor partitions under the similarity metric 5(x, y) (x, v) that incurs total loss at most ((a 2d log d) (independent of the time horizon T).
The proof of Theorem 10 can be found in Appendix B.
3.2 From Two to Many Centers
We will now show how to any potential-based algorithm for learning nearest neighbor partitions with two centers to construct an algorithm that can learn nearest neighbor partitions with any number of centers.
Our main result the following:
Theorem 11. Let A be potential-based algorithm for learning nearest neighbor partitions with two centers that has an initial potential (and thus a total loss) of at most R. Then there exists a randomized algorithm A' for learning nearest neighbor partitions for any k > 2 whose total expected loss is at most ( R).
Similar to many existing methods for multiclass classification ("all-to-all" methods), we will accom- plish this by running one instance of our two-center algorithm A for each of the (+) pairs of centers.
7

---

However, instead of using a simple majority voting scheme to choose our eventual label, we will use the potentials of these (-) algorithms to construct a distribution over centers that we will sample from.
More specifically, our algorithm will work as follows. As mentioned, each round, based on the current query dr and the potentials of the (t) sub-algorithms, we will construct a distribution e E A(k)) over the &t centers (we will describe how do this shortly). We then sample label i from this distribution and guess it as the label of q:. If we then learn that the correct label was in fact j. we update the sub-algorithm for the pair (i, with this information. We do not update any of the other aub-algoitthms (in particular, if we guess the label correctly, we do not update any of the sub-algorithms).
To construct our distribution v, we will choose a distribution v that has the property that our expected loss in each round is at most the expected decrease in the total potential over all (t) sub-algorithms. This will guarantee that the total expected loss of our algorithm is bounded above by the total starting potential of all our (+) sub-algorithms. To be more precise, define the following variables:
1. Let Ai denote the two-center sub- sub-algorithm for the labels i and j. Let (((t) be the state of Aij at round and let (
(((())) be the potential of Aij at round t. Define
s (1)) (a,)) D.f to be the total of all the potentials belonging to sub- sub-algorithms Asj-
2. As in Detinition 9, let L L(S 4:) denote upper-bound the loss incurred by the algorithm Aij in round f.
3. Let D denote the reduction in the potential of Auj when i is the correct label. In other words, D " (+++1) when I; i. Note that D is equal to D it is possible for the potential of A., to decrease lot more upon learning that point qe has label than learning it has label j (geometrically, this corresponds to different halves of the knowledge set being maintained by A.y).
4. Finally, define (t) ( 2 I,(0, where here we are treating M and T,(*) as n-by-n matrices. Observe that we can efficiently compute the values L and D and hence the value of M from qe and the knowledge set of Aij at the beginning of round t.
From here on, we will fix a round t and suppress all associated superscripts. Assume that in this round the correct label for the query point is r. Now, if we sample label from distribution e, then note that the expected loss we sustain is E; Lycu; = of Lv. Similarly, the expected decrease in & is E; D,i% = of De. it was guaranteed to the case that ef Du 2 e, Lv, then this would in turn guarantee that our total expected loss is at most the total starting potential.
follows that if we can find distribution e that satisfies Me 2 O, we are in luck. If such distribution exists, we can find it by solving an LP. This is in fact how we find the distribution v, and this concludes the description of the algorithm. To prove correctness of the algorithm, suffices to show that such a distribution always exists.
To do so, note that from the third point in Definition 9, we know that for each pair of labels (i.j),
Dis + Djs 2 Lij
(PI)
(In fact, Definition 9 tells us that max(Dij, Djs)= 2 Lij. since if Ai predicts j. we have that Dij Laj, and likewise if Aij predicts we have that Dji 2 Lij). We can rewrite (P1) in the form M + MT 2 0. The following lemma shows that if M + .TT 2 0, then there must exist distribution v satisfying Mu 2 O, whose proof we defer to the appendix.
Lemma 3.2. Given any matrix M E Ruxn such that M + M 2 0, there exists a point v E An
such that Me 2 0.
With this, it is straightforward to finish off the proof of Theorem 11.
Proof of Theorem 11. By Lemma 3.2, we know that each round we can find a distribution v E ((k)) satisfying Mr 2 0. By the previous discussion, it follows that if we always sample from this
8

---

distribution, the total expected loss will be at most twice the starting total potential, 2g(1), But note that ((1) is just the sum of the starting potentials & of all the sub-algorithms, and is thus at most (*) R. It follows that the total loss of our new algorithm is at most O R).
L
Corollary 3.3. Fix an a > O. There exists a randomized algorithm for learning nearest neighbor partitions with the inner-product similarity metric that incurs total loss at most O -2 log d).
Remark 3.4. Why do simple algorithms (such majority voting scheme) fail work in our setting? In fact, it is possible to get a simple majority vote (breaking ties arbitrarily) to work if we are given additional feedback from the algorithm specifically, the ranking of all k distances 5(4,,23 r.). With this information, it is possible update all (5) sub-instances each round, and charge any regret we sustain to an appropriate sub-instance. But if we only receive the true label of qt. we no longer have the information to update every sub-instance, and instead have to do the more subtle amortization described above.
4 Learning Nearest Neighbor Partitions Under I.P Similarity
In this section, we will discuss generalizations of our previous results for the inner- similarity metric to general L" spaces. We will primarily deal with the case when there are only two unknown points (k = 2) as the general reduction Section 3.2 will allow us to reduce from the k-point case to the 2-point case.
The general approach for the algorithms in this section is to apply some sort of kernel mapping so that inequalities of the form ||.X - =illpp S ||X - z2l1, become linear constraints, Once we linearize the problem, we can apply our earlier algorithms for the inner-product similarity along with tools from [LLS20].
Similar to the previous sections, we will assume that the hidden points Fi, 222 are the L unit ball Bg. This is equivalent to assuming that the hidden points are in the L" unit ball (which may be more natural setting since are working with L distances) up to v factor since we can simply rescale the ball to contain the -alll...
4.1 p-Norms for Even Integers p
When is an even integer, there is a kernel mapping that exactly linearizes the problem. To see this, note that [< - a)}² = (x - a) which is polynomial in x so it suffices to consider the polynomial kernel (1, ....... x²) In d dimensions, we can simply apply this kernel map coordinate-wise. After applying these kernel maps, we will be able to apply Corollary 3.3. Our main theorem for even integer p is stated below.
Theorem 12. For even integer there is an algorithm for learning nearest neighbor partitions under the L similarity metric that incurs expected total loss at most O d d O(k2 poly (gly(p,)) d)).
The details of the proof are deferred to Appendix E.2.
Remark 4.1. For the special case of = 2, the reduction is even more immediate (the kernel map needs only add a single dimension), and obtains a slightly tighter bound of O(K? dloo d). The reduction for this special case is summarized Appendix C.
4.2 General p~Norms
Now we discuss how to deal with general L norms. The main difficulty here is that there is no kernel map that exactly linearizes the problem so instead we will have multiple kernel maps. These kernel maps approximately linearize the problem at different scales, i.e. they have different output dimensions and as the output dimension grows, the problem can be more closely approximated by a linear one. When we are given query point, we choose the scale of approximation that we use based on estimating the maximum possible loss that we can incur. By balancing the dimensionality and the approximation error to be at the same scale as the maximum possible loss, we may ensure that whenever we guess the label incorrectly, a certain potential function must decrease by an amount comparable to the loss that we incur. Our main theorem is stated below.

---

Theorem 13. a > 2. If all l unknown centers are A --searrated in L" distance, there exists an algorithm for learning nearest neighbor partitions under the L" similarity metric that incurs total loss
k poooy(d,,)
A
The full proof is more complicated than the algorithms in previous sections and requires opening the contextual search black-box and redoing parts of the analysis. Note that the above theorem, we need the assumption that the unknown centers are A-separated, an assumption that was not necessary for even integer p. This is due the fact that when the true centers are too close together, the dimensionality of the kernels that need to achieve the necessary approximations are large. Nevertheless, we believe that the separated centers assumption is realistic for classification problems in practice. The details of the proof of Theorem 13 are deferred to Appendix E.3 of the Supplementary Material.
5 Learning General Convex Regions: Lower Bound
In this section, we consider the task of learning general convex regions, and present a construction which shows that any learning algorithm incurs (((r(d44)(dd2))) error over T rounds, even for only k 2 regions. We give the full proof in Appendix F.
Theorem 4, Any algorithm for learning general convex regions incurs a total loss of at least (T(d-4)/(d ())(--))), even when there are only two regions.
References
[BR20] Aditya Bhaskara and Aravinda Kanchana Rwanpathirana. Robust algorithms for online k-means clustering. In Algorithmic Learning Theory, pages 148-173. PMLR, 2020.
[CDK+06] Koby Crammer, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz, and Yoram Singer. Online passive aggressive algorithms. 2006.
[CG13] Koby Crammer and Claudio Gentile. Multiclass classification with bandit feedback using adaptive regularization. Machine learning, 90(3):347-338 2013.
[CLPL16] Maxime C Cohen, Ilan Lobel, and Renato Paes Leme. Feature-based dynamic pricing. Proceedings of the 2016 ACM Conference on Economics and Computation, pages 817-817. ACM, 2016.
[CS03] Koby Crammer and Yoram Singer. Ultraconservative online algorithms for multiclass problems. Journal of Machine Learning Research, 3(Jan):951-99) 2003.
[3}+73] Richard Duda, Peter E Hart, et al. Pattern classification and scene analysis, volume 3. Wiley New York, 1973.
[FS99] Yoav Freund and Robert E Schapire. Large margin classification using the perceptron algorithm. Machine learning, 37(3):277-296, 1999.
[7]K+17] Claudio Gentile, Shuai Li, Purushottam Kar, Alexandros Karatzoglou, Giovanni Zappella, and Evans Etrue. On context-dependent clustering of bandits. In International Conference on Machine Learning, pages 1253-1262. PMLR, 2017.
[GLZ14] Claudio Gentile, Shuai Li, and Giovanni Zappella. Online clustering of bandits. In International Conference on Machine Learning, pages 757-765. PMLR, 2014.
(HVD15) Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge neural network. arXiv preprint arXiv: 1503.0253.. 2015.
[Kle55] VI. Klee. Separation properties of convex cones. Proceedings of the American Mathe- matical Society, 6(2):313-318 1955.
10

---

[KSST08] Sham M Kakade, Shai Shalev-Shware and Ambuj Tewari. Efficient bandit algorithms for online multiclass prediction. In Proceedings of the 25th international conference on Machine learning, pages 140-447, 2008.
[Lil1] Shengqiao Li. Concise formulas for the area and volume of hyperspherical cap. Asian Journal of Mathematics and Statistics, 4(1):66-7)) 70, 2011.
[LLS20] Allen Liu, Renato Paes Leme, and Jon Schneider. Optimal contextual pricing and extensions, 2020.
[LLV17] Ilan Lobel, Renato Paes Leme, and Adrian Vladu. Multidimensional binary search for contextual decision- maaiing. Operations Research, 2017.
[LS18] Renato Paes Leme and Jon Schneider. Contextual search via intrinsic volumes. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 268-282,11 2018.
[LSS16] Edo Liberty, Ram Sriharsha, and Maxim Sviridenko. An algorithm for online k-means clustering. In 2016 Proceedings of the eighteenth workshop algorithm engineering and experiments (ALENEX), pages 81 81-89. SIAM, 2016.
[MG07] Jiri Matousek and Berdd Gärtner. Understanding and using linear programming. Springer Science & Business Media, 2007.
[MR13] Mehryar Mohri and Afshin Rostamizadeh. Perceptron mistake bounds. arXiv preprint arXiv:130.00208, 2013.
[Nov63] Albert B Novikoff. On convergence proofs for perceptrons. Technical report, STAN- FORD RESEARCH INST MENLO PARK CA, 1963.
[Ros58] Frank Rosenblatt. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological review, 65(6):386, 1958.
[SBD06] Nathan Srebro and Shai Ben-David. Learning bounds for support vector machines with learned kernels. In International Conference on Computational Learning Theory, pages 169-183. Springer, 2006.
[Vap13] Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013.
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]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(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]
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 hyperparameters, how they
URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, were chosen)? [N/A]
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [N/A]

---

(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)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
Funding Transparency Statement
Allen Liu is supported by a NSF Graduate Fellowship and Hertz fellowship. None of the other authors received third carr-pprtt funding or support during the preparation of this paper.
12


Reviews:
[{"review_id": "GKr2nciftsj", "reviewer": "Reviewer_CoFX", "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.", "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": "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???\nSome comments:\nLine 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.\nLine 91 -  “poly(p , d)” should be explicitly written.\nLine 211 - around here you drop the subscript t on many qs", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The algorithm is not robust to noise at all - give the algorithm one incorrect label and it completely breaks.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "BLYbgTq3Bu", "reviewer": "Reviewer_5eTA", "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.\n", "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": "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.\n\nI 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.\n\nLine 52: what is a time horizon T?\n\nLine 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?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations: Yes\nNegative Societal Impact: N/A, this is a theory paper", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "8TRfH7rv5Rc", "reviewer": "Reviewer_vqdM", "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.", "questions": "", "limitations": "", "rating": 7, "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": "**Strengths**\n1. 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.\n2. The proposed learning algorithms are backed up with strong theoretical analysis.\n3. The theoretical results presented in the paper are interesting.\n4. The authors provide a thorough theoretical analysis of the learning setting and the proposed algorithms.\n\n**Weaknesses, Concerns, and Questions**\n1. The paper contains a lot of new concepts and theoretical analyses. However, the presentation makes it hard to understand. \n2. 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. \n3. 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. \n4. 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.\n\nIn 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.\n\n", "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": "4"}, "extra_text": {}}, {"review_id": "1_daGm1Wa0", "reviewer": "Reviewer_cefD", "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.\n", "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": "TLDR: I think this is a good contribution. I believe it could be written in a better way, see below.\n\nOriginality: 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.\n\nQuality: I did not check the proofs. I would *expect* the quality to be ok based on how the manuscript is written.\n\nClarity: 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?\n\nSignificance: 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.\n\nSPECIFIC COMMENTS:\n\nL48: should you require v to be a unit vector?\n1.1: I think that a picture of v,q, and the R_i would help\nL68: 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?\nTheorem 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?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are discussed adequately. There are no foreseeable societal consequences.\n", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

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)