Online Selective Classification with Limited Feedback
Authors: Aditya Gangrade
Anil Kag
Ashok Cutkosky
Venkatesh Saligrama
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Selective Classification
Online Learning

Abstract: Motivated by applications to resource-limited and safety-critical domains, we study selective classification in the online learning model, wherein a predictor may abstain from classifying an instance. For example, this may model an adaptive decision to invoke more resources on this instance. Two salient aspects of the setting we consider are that the data may be non-realisable, due to which abstention may be a valid long-term action, and that feedback is only received when the learner abstains, which models the fact that reliable labels are only available when the resource intensive processing is invoked.
Within this framework, we explore strategies that make few mistakes, while not abstaining too many times more than the best-in-hindsight error-free classifier from a given class. That is, the one that makes no mistakes, while abstaining the fewest number of times. We construct simple versioning-based schemes for any $\mu \in (0,1],$ that make most $T^\mu$ mistakes while incurring $\tilde{O}(T^{1-\mu})$ excess abstention against adaptive adversaries. We further show that this dependence on $T$ is tight, and provide illustrative experiments on realistic datasets.

Online Selective Classification with Limited Feedback
Aditya Gangrade Boston University gangrade@bu. edu
Anil Kag Boston University ani lkag@bu. edu
Ashok Cutkosky Boston University
Venkatesh Saligrama
Boston University srvêbu. edu
ashokecutkosky.co com
Abstract
Motivated by applications to resource-limited and safety-critical domains, we study selective classification in the online learning model, wherein predictor may abstain from classifying an instance. For example, this may model an adaptive decision to invoke more resources setting we consider are that the data may be non-realisable, due to which abstention may be valid long-term action, and that feedback is only received when the learner abstains, which models the fact that reliable labels are only available when the resource intensive processing is invoked.
this instance. Two salient aspects of the
Within this framework, we explore strategies that make few mistakes, while not abstaining many times more than the best-in-hindsight error-free classifier from a given class. That is, the one that makes no mistakes, while abstaining the fewest number of times. We construct simple versioning based schemes for any p (0, 1]. that make most T mistakes while incurring ~ excess abstention against adaptive adversaries. We further show that this dependence on T is tight, and provide illustrative experiments on realistic datasets.
1 Introduction
Consider low-power or battery-limited edge device, such as sensor or a smart-speaker that receives a stream classification requests. Due to the resource limitations, such device cannot implement modern models that are needed for accurate decisions. Instead the device has access (e.g. via an internet connection) to an accurate but resource-intensive model implemented on a cloud server, and may send queries to the cloud server in order to retain accuracy. Of course, this incurs costs such as latency and battery drain due to communication. The ideal operation of such device should thus be to learn a rule that classifies 'casy' instances locally, while sending harder ones to the cloud, thus maintaining accuracy whilst minimising the net resource consumption XXu+14; NS17].
Selective classification [Cho57; Cho70] is classical paradigm of relevance to such settings. The setup allows predictor to abstain from classifying some instances (without incurring a mistake). This abstention models adaptive decisions to invoke more resource-intensive methods on subtle cases, like the above example. The solution concept relevant widely for instance, it is relevant to adaptively recommending further (and costly) tests rather than offering diagnosis in medical scenario, or to recommending a human review instead an alarm-or-not decision security contexts. Two aspects of such settings are of particular interest to us. Firstly, the cheaper methods are typically not sufficient to realise the true labels, due to which abstention may be a long-term necessity. Secondly, a-priori reliable labels can only be obtained by invoking the resource intensive option, and thus feedback on whether a non-abstaining decision was correct is unavailable.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

We propose online selective classification, with an emphasis on ensuring very few mistakes, to account for the need for very accurate decisions. Concretely, an adversary sequentially produces contexts and labels (X,, Yt), and the learner uses the X,s to produce a decision Y, that may either be one of K classes, or abstention, which we represent L. Feedback in the form of Y, is provided if and only if V, = +, and the learner incurs mistake if V; was non-abstaining and did not equal Y,.
With the emphasis on controlling the total number of mistakes, we study regrets achievable when compared to the behaviour of the best-in-hindsigg error-free selective classifier from given class- that is, one that makes no mistakes, while abstaining the fewest number of times. Notice that our situation is non-realisable, and therefore this competitor may abstain in the long-run. The two metrics of importance here are the number of mistakes the learner makes, and its excess abstention over this competitor. An effective learner must control both abstention and mistakes, and it is not enough to make one small, e.g. a learner that makes a lot of mistakes but incurs a very negative excess abstention is no good. This simultaneous control of two regrets raises particular challenges.
We construct a simple scheme that, when competing against finite classes, simultaneously guarantees O(T*) mistakes and O(T excess abstentions against adaptive adversaries (for any μ [0, I),, and show that these rates are Pareto-tight [OR94]. We further show that against stochastic adversaries, the same rates can be attained with improved dependence of the regret bounds on the size of the class, and we also describe schemes that enjoy similar improvements against adaptive adversaries, but at the cost of the T --dependence of the regret bounds. The main schemes randomly abstain at a given rate in order to gain information, and otherwise play Y, consistent with the 'version space' of classifiers that have not been observed to make mistakes. For the adversarial case, the analysis of the scheme relies on a new 'adversarial uniform law of large numbers' (ALLN) to argue that such methods cannot incur too many mistakes. This ALLN uses self-normalised martingale concentration bound, and further yields an adaptive continuous approximation guarantee for the Bernoulli-samplig sketch in the sense of Ben-Eliezer & Yogev Y20; Alo+21], The theoretical exploration is complemented by illustrative experiments that implement our scheme on two benchmark datasets.
1.1 Related Work
Selective classification has been well studied in the batch setting, and many theoretical and method- ological results have appeared [e.g. HW06; BW08; EW10; WF11; KKM12; CDM16; Leil4; GE19; GKS21J. These batch results do not have strong implications for the online setting.
Cortes et al. have studied selective classification in the online setting [Cor+18], but with two differ- ences from our setting. Firstly, rather than individually controlling mistakes and abstentions, the regret is defined according to the Chow loss, which adds up the number of mistakes and e times the number of abstentions, where is fixed cost parameter. Secondly (and more importantly) it is assumed that feedback is provided only when the learner does not abstain, rather than only when does. This difference arises from the underlying situations being modelled Cortes et al. view the abstention as a decision given to a user in which case no feedback is forthcoming, while we view it as decision to invoke further processing. Both of the scenarios are reasonable, and so both of these explorations are valid, however is unclear what implications one set of results have for the other.
A similar decision and feedback model as ours was proposed by Li et al. in the 'knows what it knows' (KWIK) framework [LLWSII]. The KWIK model, however, fundamentally views abstentions as a short term action, typically arguing that only finite number of these are made. This is viable since Li et al. study this model in an essentially realisable setting, wherein the optimal labels are known to be essentially realised by given class- notice that in such case, a single abstention at instance x determines what value should be played there in the long run. Our interest however lies in the situation where this data cannot be represented in such a way, and such strategies are not viable since the labels may be noisy. Our work thus generalises the KWIK setting to non non-realisable data, and to situations wherein abstention is valid long-term action, as motivated in the introduction, by studying behaviour against competitors that may abstain.'
While Szita and Szepesvári have extended the KWIK formulation to the agnostic case in a regression setting [SS11], this work also focuses of limiting the number of abstentions to be finite rather than
'The KWIK model also bears other significant differences. It posits an input parameter e, and requires that the learner either abstains, or produces an e-accurate response. A notion of competitor is not invoked, and rather than studying regret, the number of abstentions needed to achieve this e-accuracy is studied.

---

long-run abstentions. Concretely it is assumed that Y =(x,) x+ + noise, for some function and the learner knows class H. and bound A such some H is A-close to g (in an appropriate norm). Using the knowledge of A, they describe schemes that have limited abstention, but at the cost of mistakes, by producing responses Y, that are up to (2 + o ((1)) separated from Y, In contrast, in our formulation, contexts X; for which no function in H can represent the ground truth g well would always be abstained upon. In addition to this work, trade-off's between mistakes and abstentions in a relaxed version of the KWIK framework have been considered [ZC16; SZB 10; DZ13], and in particular the agnostic case has been explored by Zhang and Chaudhuri [ZC16], but unlike our situation this relaxed KWIK model requires full-feedback to be available whether or not the learner abstains. Neu and Zhivotovskiy [NZ20] also work in this relaxed model, and show that when comparing the standard loss of a non-abstaining classifier against the Chow loss of an abstaining learner, regrets independent of time can be obtained.
Due to the limited feedback, our setting is related to partial-monitrring [LS20, Ch. 37J. Viewing actions as choices over functions, our setting has feedback graphs [MS11] I] that connect abstaining actions to every other action and themselves. The novelty with respect to partial-monitoring arises from the fact that we individually control two notions of losses, rather than single one. It's unclear setup to this situation indeed, naively, our game is
how to apply the generic partial-monitone only weakly observable in the sense of Alon et al. al.[ACDK15], and one would expect ((T2/33 regrets, while we can control both mistakes and excess abstention to Ö(VT). A limited feedback setting where two 'losses' are individually controlled is label-efficient prediction [CLS05], where a learner must query in order to get feedback. However, in our setting, abstentions are both a way to gather feedback, and also necessary to prevent mistakes. That is, our competitor may abstain regularly, but makes few mistakes, while in this prior work the competitor does not abstain, but may make many mistakes. The resulting scenario is both qualitatively and quantitatively distinct, e.g. in label-efficient prediction, the smallest symmetric rate of number of queries and excess mistakes is again ((T2/3),
2 Setting, and Problem Formulation
Setup Let X be a feature space, y a finite set of labels, and F a finite class of selective classifiers, which are )' } valued. For simplicity, we assume that F contains the all abstaining classifier (i.e. the function fl such that Vz, fa (z) = -). We will denote [F]= = N. The setting may be described as game between learner and an adversary (or more prosaically, a data generating mechanism) proceeding in T rounds. Also for simplicity, we will assume that T is known to both the learner and the adversary in advance. The objects in this game are the context process, X₂ E X, the label process Y E y, the action process V, E y U {L) and the feedback process Z, E ) U {*), where * E ) is a trivial symbol. The information sets of the adversary and learner up to the tth round are respectively HE = (X,,,,,, Y.): : < f}. and XEE == [X.,, Y,, Z.) : < <}.
The Game For each round E [1 T", the adversary produces a context and a label (X., Yr) on the ba- sis its history " The learner observes only the context, X,, and on the basis of this and its history Xe produces action Y, We will say that this action is abstention if Y. = L, and that it is prediction otherwise. If the action was an abstention, set Z,- = Y,, and otherwise to *. The learner then observes Ze, and the round concludes. Notice that since Z, is deterministic function of Y, and Y, and since the adversary observes both, H. can be determinstically generated from H, Due to the same reason, Y, and Y, are conditionally independent given (X,,
Adversaries are characterised by sequence of conditional laws on (X,, Y;) given HA (and T,F). In the following we will explicitly consider two classes of such laws: Stochastic Adversary: (X,, Y.) are drawn according to a fixed law, P, unknown to the learner,
independently of X Adaptive Adversary: (X,, Y.) are arbitrary random variables with x measurable laws. We will denote generie class of adversaries as C.
Performance Metrics The two principal quantities of interest are the number of mistakes made by the learner, and the number of times it has abstained. We will denote these as
My = Σ 1 & (L.YH). and Ar = Σ Eum8= 1T.
1
1ST
3

---

As previously discussed, the performance of a learner is measured in terms of regret with respect to the best-in- best-in-hindsigee hinniddsight abstaining classifier from FF that makes no mistakes, that is
f E arg min JEF
E1((()) = + s.t. 1ST
E(((x,) & (L,,))) IST
Note that such an f" is always realised, since the class is finite, and since it contains the all abstaining classifier. Let A7 : ΣiSt (X, - denote the value of the minimum above. The principal metrics of interest to us are the abstention regret Ar - A and the total mistakes Mr- Solution Concept The two performance metrics naturally involve tradeoff for instance, making some mistakes may allow a learner to drastically reduce its abstention regret to the point that it is negative. We pursue the trade-off between the worst possible behaviour of either regret.
Definition (Regret Achievability) For functions i,, th N2 - R. say that expected regret bounds of (qp 2 are achievable against a class of adversaries '6' if there exists a learner such that for every adversary in '6, E[AT Ai S (TT,NN and M[ (T,
As is common, we are interested in the growth rates of achievable bounds with T. We thus define
Definition (Achievable rates) we say that asymptotic expected-regret rates of (a,,1) E [0, 1J2 are achievable against a class of adversaries '6 if an expected regret bound of (4, 1)) can be achieved against for functiins sp,b, said to be witnesses for the rate, such that
log (T,,
log (T,
sim T-000
S a and lim sup T-000
S
logT
log T
Notice that if (or, ()) is an achievable rate, so is (a',8') for a' 2 a, 8 2 5. As result, the lower boundary of the set of achievable rates well defined, and we will refer to this as the Pareto frontier of achievable rates. This is equivalently characterised by the function a(p) == inf(a (a, p)) is an achievable rate]. This is well defined since Vj, (1, (1) is achievable by always abstaining.
3 The Adversarial Case
We begin with the adversarial case. The scheme, called the 'versioned uniform explorer' (VUE) is described below, and we discuss both the motivation of the scheme, and its analysis. The main idea underlying VUE is that any function f
Algorithm 1 VUE
that is observed to make a mistake on an instance X,
(due to the learner abstaining on this instance) can
1: Inputs: F, Exploration rate p.
be removed from future consideration, since we are
2: Initialise: V1= < F.
3: for / E [1 7] do
only trying to match the behaviour of the competitor
f", and clearly f + f as it has made a mistake. This motivates setting up 'version space,"
4:
De (f(X)) V.).
5:
if [5 = then
6:
Y, + f(X)) for any f E Va.
n f:
& (1,Y,)) =
V++1 + Vr.
8:
else
the set of functions that are consistent with the ob- servations made up to time L. Notice that f* E V. for all L. Given V. we can restrict to playing an action in the set Di- := (x,, : f E V1- (X,, lies in this set, and thus any action outside of it can be climinated. Of course, if }, is a singleton, then it contains f* (X,), and we can just play it.
9:
Sample C. Bern(p). if C, = 1 then
10:
11:
Set Y, = 1, observe Y.
12:
Ur + f(x,) E (1,
13:
V++1 = -1
14:
else
15:
Pick Y, E 51 {LL.. Vi+1 + V2.
Next, since we are incentivised to minimise the total number of abstentions. it behooves us to play aon-aaitann actions whenever possible. However, this puts us in a bind, since feedback is produced only when we play an abstaining action. Taking inspiration from [CLS05), we abstain at a rate p by tossing a biased 'exploratory coin'. Cr. abstaining when C. 1, and otherwise playing any non-abstaining action in Pt. Clearly, such strategy can incur at most pT excess abstention regret in expectation. Mistakes made by this strategy are controlled via the following 'adversarial law of large numbers' (ALLN).
16:
)2 be (F:)-udapted binary processes, such that B. Bern(p), p < 1/2 is jointly independent of F (-11 for each t. Let W, Eose U.,
Lemma I. Let { be any filratiion, and [U. {

---

and Wi = EEss U.B. For any ò E (0,1/V),
IP 3t: W. W,W, > 8log(1/0) S 6.
P
The above is argued in SA using a self-normalised martingale tail inequality [HRMS20J. We note that this seff-normalisation is critical, and without this techniques such as Freedman's 's inequality yield an extraneous /T factor in the bounds that is untenable for our purposes. The same argument, along with the shaping technique of Howard et al. [HRMS18) yields a Bernstein-type law of iterated logarithms that controls W W at a level Ó + / W./p log log t), which should be useful more broadly. This full version (presented in ŞA) further shows that the 'Bemoulli Alo+21] offers a continuous approximation in the sense of Ben Ben-Eliezer & Yogev [B (22)), but with the error for sets of low incidence flattened as expected due to Bernstein's inequality.
[B YB;
For our purposes, the point of Lemma is to allow us to argue that no matter what the adversary does, if we uniformly abstain at rate p. then we will 'catch' any mistake- prone function before it makes (1/p) mistakes. Exploiting a union bound, this in turn means that with high probability, any such function will fall out of the version space V. before it has incurred much more than log N/p mistakes. Since the label produced by Algorithm I must equal fX;) for some f in the version space, we can infer that the number of mistakes the learner makes is at most the number of times any function in the version space is wrong. Using the Lemma yields a bound of Õ on the number of mistakes that any functions in the version space can have ever made, and since there are only N possible functions, in total the number of mistakes the learner can make is bounded as ((N/p). More formally, the argument, presented in $B, argues this for a single function f F by instantiating the lemma with F. = ofF = (HH,)), B = Ct, and U.- == ({,, & (L,Y)))- The resulting W is the number of mistakes / is observed to have made, and f E V. if and only if W = O2. Along with a use of Bernstein's 's incquality to control Ar this yields the result below.
pestake-prone
Theorem 2. Algorithm instantiated with < 1/2, and run against an adaptive adversary, attains the following with probability at least å over the randomness of the learner and the adversary:
9N 1og(2N/8)
Mr S
AT - AT pf + () + 2 log
In particular, taking p /N/T yields the symmetric regret bound
max(Mr, Ar AT) S NT (N)).
We conclude with a few remarks. Achievable rates: Taking 1/z, and varying p in TosT//, 1] gives the rates attainable by VUE Corollary 3. All rates (a, μ1) such that
0, 0, t are achievable against adaptive adversaries. These rates are tight- as expressed in Corollary 6, rates such that a + μ < 1 are not achievable even against stochastic adversaries. The Pareto frontier is therefore the line a + μ
Dependence on N: should be noted that the dependence on the number of functions, N, in Thm. 2 is polynomial, as opposed to the more typical logarithmic dependence the same in online classification. The problem of characterising this dependence appears to be subtle, and we do not resolve the same. In the following section, we explore schemes that improve this aspect, but at cost $4 yields logarithmic dependence against stochastic adversaries, while $5 gives a scheme that has a logarithmic dependence against adaptive adversaries, but worse dependence with T.
It is worth stating that the analysis above is tight for Algorithm 1 consider the domain X'= [1 N). and the class F= (fa= & E [0: N] such that fa(x)) = 1 if S and = if x >> f. Now consider an adversary that chooses a in advance, and presents the contexts T/N times, 2 T/N times and so on, labelling contexts smaller than t* as O, and contexts larger than t* as 1. Notice that in each case, there is exactly one function in V; that does not abstain. The scheme above incurs 2(pT(1 - t" /N) excess abstention, and 22(t) /p) mistakes, and linearly large !* form tight example. Of course, this is not a lower bound on this problem, and the question of the optimal dependence on N remains open.
This argument only needs control for the case W 0. The & in Lemmal is exploited in $5.2.
5

---

Hedge-Type Schemes The natural approach of proceeding by weighing the cost of abstention versus mistake, and running a hedge-type scheme on an auportance-sstminnn of the resulting loss does not lead to tight rates- the scheme MIXED-LLOSS- POOD--RDD of $5 pursues precisely this strategy, and the worse case symmetric regret bounds that standard analyses lead to scale as 72/3 instead of as 7 as for VUE (Cor. 8). This may be due to the fact certain-error prone classifiers in J may have very low abstention rates, and thus overall large weight, and it is unclear how to eliminate this behaviour.
4 The Stochastic Case
This section argues that the regret bounds of Thm. can be improved behave logarithmically in N in the stochastic setting. There are a couple of issues with Algorithm that impede better analysis in the stochastic case. The first, and obvious, one is that how Y; is chosen is not specified. More subtly. the fact that the scheme insists on playing non- non-abstaining actions whenever possible makes it difficult to control the number of mistakes without a polynomial dependence on N.
We sidestep these issues in Algorithm 2 by maintaining a law ग. on functions in V4 that only depends on X/= and predicting by setting Y, f(X,) for ft ~ nr Notice that playing this way it is possible that we abstain on X, even if the exploratory coin comes up tails. We control mistakes by arguing that very error-prone functions are all quickly eliminated (due to the stochasticity). and using the property that ne does not depend on X₁ to limit the mistakes incurred up to such a time. Abstention control follows by choosing т according to strategy that favours s's with small overall abstention rate over the history. Algorithm 2, we use a version of the PROD scheme of [CMS07] to set weights, analysed with shrinking decision sets. The following is shown along these lines in $C.
Theorem 4. Algorithm 2, run against stochastic adversaries with 1) = p: altains the regret bounds
B[MT] < <8- log JogTlope log(TT)
log N
and IB[AT A7 S pf
P
P
We note that VUE-PROD also enjoys favourable bounds in the adversarial case mistakes are bounded as ((N/p), and abstention regret as in the above result.
Algorithm 2 VUE-PROD
Inputs: F.p. Learning rate v).
2: Initialise: V/2 5- F-F,V, wf + 1.
This is in contrast to simpler wollow-thh-versioned--eee type schemes that also satisfy similar bounds as Thm. in the stochastic case. Also note that the above cannot attain rates such that a S 1/2, an inefficiency introduced due to the conditional independence of म. and X,
3: for E [1 T] do
wf wfEl
4: Sample fo Te EYEV,
5: Toss C. ~ Bern(p).
I
G==
Finally, we show lower bound. The statement equates stochastic adversaries with their laws.
6:
P. +
(((x))
==
7:
Ve+1 + V/.
Theorem 5. If F contains two fanctions fi, f2 such that there exists a point for which fi(x) = 1 + fz(x). then for every y E [0, 1/4,, there exists pair of laws
8:
if 1 then
9:
Ur + if: f(x,) E {1, Y.))
10:
Ve+1 = V.
PT. P` such that any learner that attains Ep7 [Ar
11:
for ff V4+1 do
A7] = K must incur pp [MT] 2 7( -2-KT K).
12:
of + ((((x)) = }}
13:
w/41 +- w/ (1 maa )-
Thus, if a (p, v) regret bound with sup & < achievable, then up. ((TT). Indeed, using the above with 1/T( N),, gives Ep, [Ar A - 1. This proves the following.
1 is
2
K S (TT N). and NT) 2 Ery 2 ((T.N) ((
T e-
( 2K///((T.N)
Corollary 6. If (a, 1) E [0, 1)2 is such that a + t < 1, then an (a, 14 regret rate is not achievable against stochastic udversariex, and, a fortiori, against adaptive adversaries.
5 Reducing the dependence of regret bounds on N in the adversarial case
This section concentrates on improving the N -edependence of regret bounds in the adversarial case via two avenues. The first improves this dependence to log( (N) by running PROD with a weighted loss, but at the cost of increasing T dependence. This holds greatest relevance when T is bounded as a polynomial of N, which is of interest because N can be quite large even in reasonable settings e.g., discrctisation of d' d-dimensional hyperplanes induces N exp (Cd). The second approach

---

considers the case when the set of possible contexts, i.c. X' is not too large. While in this case, N can be as large as (1>/) + 1) we show bounds depending only linearly on (
5.1 Weighted PROD
Algorithm MIXED-LOSS-PROD
We continue the uniform exploration, but play according to the PROD method, with the loss
1: Inputs: F, Exploration rate p, Learn-
ing rate 7). Initialise: vff E F, wf 1.
= (J((()) & (1, + -I(
3: for E [1: '" do
where À both trades-off the relative costs of mistakes
4: Sample ft ~ Tt w/ / m!!
and abstentions, in the vein of the fixed cost Chow loss, and accounts for the sub-sampling of the mistake loss.
Toss C. ~ Bern(p).
6:
if C. then
The analysis of this scheme, presented in $D exploits 7:
Y, + 1
the quadratic bound of PROD due to [CMS07] to control
else
the sum ElpMT + A(Ar pf') by min, log N/1 + n)()), where the expectation is only over the coins Ct and the -p7 term is due to the extra abstentions due to the exploratory coin. The key observation is that since I" makes no mistakes, E(er )²- = X² Ar, and so taking 9 = I", and exploiting the weight allows us separately control the regrets in terms of AT.
9:
V, < fe(X,)
Af E F, evaluate Ef
10:
w/ + w (1 np
11:
Theorem 7. Algorithm 3, when run against adaptive adversaries with = -1/2, X S p. attains
E[MT] <
logg N
22
E[AT],
2 log N and B[AT A7] S pT +
P
x
5.1.1 Rates
Theorems 4 and 7 show regret bounds with logarithmic dependence in N. The following concept separates rates attainable with this advantageous property from those with worse N-dependence.
Definition (Logarithmically Achievable Rates) We say that rates (a, are logarithmically achiev- able against adversaries from class & if there exists learner that attains a (v, rrerrtt against such adversaries for sb. yp that witness the rate (a, P), and satisfy that for every fixed T, max (T, N)) = O ((polylog(N)) as N 30.
Since A7 < T, choosing p T A T (w++)) in MIXED-LOSS PROD for any (u, v) E [0, 1J2, u v S 1 allows us to attain rates of the form (a. (1) = (max(1 - u, u + v), - v). Notice that for any fixed v. the smallest a attainable is L+1/2. This shows
Corollary 8. Any rate (or, u)) such that + p > is logarithmically achievable against adaptive adversaries.
The following figure illustrates the worst case achievable rate regions in the three cases considered.
Unkuownj
Unknown
Achievable
Achievable
Achievable
P
Impossible
Impossible
Impossible
Figure 1: Left shows rates achievable against adaptive adversaries. Middle and right show logarithmi- cally achievable rates against stochastic and adaptive adversaries respectively.
Adaptive Rates Observe that if Aj. x 7 for some a" < 1, then nominally, the achievable rates can be improved. Indeed, with the parametrisation p --= À = - we may attain rates of the form (a, n1) (max(1 u, + v), max(u, a* - v)). Further, given mistake rate μ can be attained by setting u = μ. and x S μ. With these constraints, the smallest abstention rate attainable is (((uaa.) max (1 n. (1 + (a" #)+)/2),
7

---

achieved by setting v (a. - p)+. u = min(1 (a* attained adaptively, without prior knowledge of The main bottleneck here is that the quantity A7 is not observable. However, every function g that is never observed to make a mistake satisfies = = Σ (x(x,) 1}, and such functions are identifiable given Hr" Let
2p)/2. Such rates can in fact be
B min Σ (x(X))) = = S.L. (C.)(((x)) & (1, =.
Note that B, grows monotonically, and is always smaller than ( show the following in $D.1 via a scheme that adaptively sets p, À according B
1.. We
Theorem 9. For any a", J4, (0, 1]. Algorithm 4 attains, without prior knowledge of any rate of the form (ālu, a²) + μl +) against adaptive adversaries that induce A S T almost surely.
The rates ā essentially interpolate between the second and third panels of Fig. 1. Concretely the region achieved consists of the intersection of the regions {a 1/23, {a p > 1} and {2a p > l+a"), with the last set being active only when a' 2 1/2.
5.2 A X -dependentt analysis of VUE
We give an alternate mistake analyse for VUE over finite domains. The analysis is slightly stronger: y ([1 KJ {1}}(=] be indexed by elements of F. with the 'fth' entry y, reprsents value that f might take. Consider the resulting partition of (Ky (())))((: where each part Xy X E contains points that have the same pattern of function values, that is Xy = {ar E f()) yy) The following argument can be run unchanged by replacing single æs in the following by all æs in one Ky. That is, we may replace | in the following Theorem 10 with [( } For simplicity, we present the argument for |X| only.
Denote D {f(x): f E V.J Notice that after the first time t such that X, Y. -. will remove from the version space all classifiers that did not abstain or output the correct classification at time t. Thus if we define y" E [1 K] to be Y,, then for all subsequent times, 578 c {L,v"), As result, if we observe two mistakes at any given æ, then we cannot make any more mistakes at subsequent time l' with X₃ I, because the only remaining decision in Diz must 1.
We may now proceed in much the same way as $3 instantiate U/ = 1(X, = 2, P (L,YH)
B, = Ct, and union bound over the 2s. Then [5'] 2 2 if and only if W. < 1, and, invoking Lemma 1, up such a time at most W = Olog 1xpp mistakes may be made on instances such that X, x. But then totting up, make at most O( log (plpp) mistakes, encapsulated below
Theorem 10. Algorithm I instantiated with S 1/2 and run against an adaptive adversary, attains the following with probability at least 5 over the randomness of the learner and the adversary:
9/ log (2g(2)
Mr <
Ar 17 PT 2p(1 T)T log (2/8) + 2 2lg(22/8).
Along with the bound itself, the above result makes couple of points regarding the characterisation of N --dependence of the regrets in online selective classification. Firstly, it suggests that efficient analyses, and possibly schemes, must incorporate the structure of X; and secondly shows that constructions that attempt to show superlogarithmic in N lower bounds must have both N and X large, and thus typical strategies placing very rich class on a small domain will not be effective.
6 Experiments
We evaluate the performance of Algorithm 2 on two tasks CIFAR 10 [KH09], and GAS [Ver+12] see SE for details of implementation, and here for the relevant code. The former represents setting where an expert can be adaptively invoked, which we treat by providing the true labels of the classes upon abstention. The second case is more explicitly an adaptive feature selection task the GAS dataset has features from 16 sensors, and we train one model, g. on all of this data, while the selective classification task operates on data from the first 8 sensors only, and receives the output of g when abstaining. The standard accuracies of the model classes implement are 90% on CIFAR- 10.
8

---

and ~ 77% on GAS. In both cases, a training set is used to learn parameterized family of selective classifiers, fn.t. The hyperparameters (p,t) provide control over various levels of accuracy and abstention. For training, we leverage recent method [GKS21] that yields such a parameterisation, which is discretised to get N = 600 of these functions to form our class F. We then sequentially classify the test datasets of each of the tasks.
One subdlty with the setting is that none of the selective classifiers in F actually make no mistakes. To avoid the trivialities emerging from this, we relax the versioning condition to only drop classifiers that are seen to make mistakes on least eN₂- + /2eN, mistakes at time t, where N₂ is the number of times feedback was received up to time t. and the second term handles noise. Additionally, if it turns out that all functions in V42 are wrong on a particular observed instance, we igmore this feedback (since such an error is unavoidable). Such variations of 'relaxed versioning" are natural ideas when extending the present problem to the one where the competitor may be allowed to make non-zero mistakes, although its analysis is beyond the scope of this paper. The scheme's 's viablility in this extended setting with only simple modifications indicates the practicality of such strategies.
Below, we take the competitor to be the function that makes the fewest mistakes, denoted as M7. If there is more than one such function, we take the one that makes the fewest abstention to get A We measure excess mistakes Mr- - Mj and excess abstentions Ar- - Aj with respect to this competitor.
Behaviour of regrets with the length of the game Fig. 2 presents the excess mistakes as a fraction of T for the two datasets, i.c. Mr-Mi/I, as T, is varied. The learners are all instantiated with the exploration rate p 1/VT. We observe that the excess abstentions this range (see Fig. 4 in $E). Therefore we do not plot these below (the orange line is MMEA, see below). We note that the relative mistakes stay below /2log N/T, bearing out the theory.
negative (or near-zero) over
Achievable Operating Points of Mistakes and Abstentions Fig. 3 shows the mistake and abstention rates attainable by varying p and E, while holding fixed at 500 (which is large enough to show long- run structure, but small enough allow fast experimentation). Concretely, we vary these linearly for 20 values of p E [0.015, 0.285]. and 10 values of æ E [0.001, 0.046]. The resulting values represent operating points that can be attained by choice of p, E. The same plot includes lines that represent the operating points when the scheme is run with E = 0.001, the smallest value we take. Note that in practice, the best choices of E, p may be data dependent, and choosing them in online way is an interesting open problem (also see $E.6).
The Price of Being Online We characterise this in two ways beyond the excess mistakes.
In Fig. 2, we also plot the imistake-matehee excess abstention' (MMEA). This is defined as follows if the scheme concludes with having made My mistakes, minimises the number of abstentions, subject to making at most My mistakes. The MMEA is the excess abstention of the learner over those of this relaxed competitor, and represents how many fewer abstentions a batch learner would make if allowed to make as many mistakes as the online learner. Notice that this MMEA remains well controlled in Fig. 2, and appears to scale as O(VT).
find, in hindsight, the classifier that
In Fig. 3, we also plot the post-hoc operating points of the classifiers in F as black triangles. This amounts to plotting the optimal abstentions amongst classifiers that make at most m mistakes, varying m. We note that the red operating points of the scheme get close to the black frontier, illustrating that the inefficiency due to being online is limited. As the time-behaviour of MMEA in Fig.2 illustrates, the inefficiency is expected to grow sublinearly with T, and to thus vanish under amortisation.
7 Discussion
Online selective classification offers primitive that has relevance to both safety-critical and resource- limited settings. In the paper, we highlighted the role of long-term abstentions in such situations, and studied this problem under the feedback limitation that labels are only provided when the system abstains, which is the only time high-complexity evaluation would be invoked in a selective classification system. When working with finite class of model, we identified simple scheme that provides a tight (in terms of 7) trade-off between mistakes and excess abstentions against adaptive adversaries. We further discussed two schemes that improve upon the dependence of the same on the size of the model class- tightly against stochastic adversaries, and at the cost of some rate
'Observe that the MMEA corresponds to the horizontal distance between a red- red-point with m mistakes, and the left-most black point with y-corrdinate under m.

---

AGloghi7
Villoggo7
Valies fnccieer
0.35
0.30
805
860
0.00
-0.3
500
1000
1030
2000
2200
2000
2000
4000
500
1000
1500
2000
2500
3000
4020
Figure 2: Mr M7. and MMEA as fractions of T, the number of rounds T is varied for CIFAR- 10 (left)
and GAS (right). The plots averaged 100 runs, and one-staandardddevittoon
regions drawn.
8.87
0.2
0.50
0.05
0.05
0.01
0.82
0.02
0.1
sperating
sparating
0.00
0.00
0.7 0.0
Figure 3: Operating points for our scheme as and p are varied are represented as red dots (for CIFAR-10 the left, and GAS in the right). The black triangles represent operating points obtained by batch learning with the benefit of full feedback. The blue lines interpolate points obtained by varying p for g 0.001 Points are averaged over 200 runs. Note that the values
mistakes and abstentions, and not regrets.
performance against adaptive adversaries. Together, these schemes and analyses provide some basic foundations for the problem when competing against no-mistake models. Additionally, carried out empirical studies that validate the scheme in the stochastic case, and demonstrate that with minor modifications, the scheme is resilient to the situation where selective classifier in the model class mistake-free. A number of interesting questions remain open, and we discuss a few of these below.
Perhaps the most basic question left open by the above study is how the minimax regrets against adaptive adversaries depend on N. Along with being basic scientific question, this issue has implications for whether the results can be extended to infinite classes. Indeed, under assumptions of bounded combinatorial dimensions, the VUR-PROD and MIXED-I.OSS-PRE to infinite model classes, but the basic technique to do so yields trivial bounds for VUE due to the linear dependence on N. If this dependence could be improved to logarithmic, the extension to model classes with finite (multiclass versions of) Littlestone dimension would be immediate.
schemes can be extended
practically relevant and theoretically interesting direction is online SC but where the competitor can make non-zero mistakes. This can be set up in at least two ways either an eтror parameter is given the learner, which must ensure that both notions of regret are small against competitors that make at most ET' mistakes; no explicit eтror parameter is specified, and the learner is required to compete against the least mistake-pret prone model in a given set (similarly to $6). Both settings raise new challenges, since one must relax the notion of versioning used in the above work for related schema to be viable. The latter setting raises further issue of how one can adapt to the mistake rate of the competitor. Also of practical relevance is the case where abstentions but have some variable cost. Here too, one can study variants signalling regarding whether the cost of abstention is available before only after abstaining decision is made.
not equally penalised,
Finally, we observe that while tight, the random exploration technique is somewhat unsatisfying and practically context-adapted abstention strategy is likely to offer meaningful advantages over it. In analogy with the exploration in label-efficient prediction, one direction towards exploring context-aware methods is to study more concrete structured situations, such as linear models with noisy feedback that are popular in the investigation of online selective sampling.
10

---

Acknowledgements Our thanks to Tianrui Chen for helpful discussions.
Funding Disclosure This research was supported by the Army Research Office Grant W911NF21 10246, the National Science Foundation grants CCF-2007350 and CCF-1955981, ARM Research Inc, and the Hariri Data Science Faculty Fellowship Grants. Additional revenues related to this work: AC was a visiting researcher at Google when this work was completed.
References
[ACDK15]
Noga Alon, Nicolo Cesa-Bianchi, Ofer Dekel, and Tomer Koren. "Online learning with feedback graphs: Beyond bandits". In: Conference on Learning Theory. PMLR. 2015, pp. 23-35.
[Alo+21]
Noga Alon, Omri Ben- Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev. "Adversarial Laws of Large Numbers and Optimal Regret Online Classification" In: arXiv preprint STfi::2011.00055. (2021).
[BLM13]
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: nonasymptotic theory of inlependence. Oxford university press, 2013.
[BW08]
Peter L Bartlett and Marten Wegkamp. "Classification with reject option using a hinge loss". In: Journal of Machine Learning Research 9.Aug (2008), pp. 1823-1844
[BY20]
Omri Ben-Eliczer Eliezer and Eylon Yogev. "The adversarial robustness of sampling". In: Proceedings the 39th ACM SIGMOD-SIGACT-SICA Symposium Principles of Database Systems. 2020, pp. 49-62.
[CDM16]
Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. "Learning with rejection". In: International Conference on Algorithmic Learning Theory. Springer, 2016, pp. 67-82.
[Cho57]
C Chow. " An optimum character recognition system using decision functions". In: IRE Transactions on Electronic Computers EC-6.4 (1957), pp. 247-254.
[Cho70]
C Chow. "On optimum recognition error and reject tradeoff". In: IEEE Transactions Information Theory 16.1 (1970), pp. 41-46.
[CLS05]
Nicolo Cesa- assa-Biacchi, Gábor Lugosi, and Gilles Stoltz. "Minimizing regret with la- bel efficient prediction". In: JEEE Transactions on Information Theory 51.6 (2005), pp. 2152-2162.
(CMS07)
Yishay Mansour, and Gilles Stoltz. "Improved second-order bounds for prediction with expert advice". In: Machine Learning 66.2 (2007), pp. 321- 352.
Nicolo
[Cor+18]
Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mchryar Mohri, and Scott Yang. "Online learning with abstention". In: international conference on machine learning.
PMLR. 2018, pp. 1059-1067.
[DZ13]
Erik Demaine and Morteza Zadinoghaddam. "Learning Disjunctions: Near-Optimal Trade-off between Mistakes and "I Don't Knows"" In: Proceedings of the Twenty- Fourth Anmual ACM-SIAM Symposium on Discrete Algorithms. SIAM. 2013, pp. 1369 1379.
[EW10]
Ran El-Yaniv and Yair Wiener. "On the foundations of noise-free selective classifica- tion". In: Journal of Machine Learning Research 1 11.May (2010), pp. 1605-1664
[GE19]
Yonatan Geifman and Ran El-Yaniv. "SelectiveNet: A Deep Neural Network with an Integrated Reject Option". In: International Conference on Machine Learning. 2019, pp. 2151-2159.
[GKS21] Aditya Gangrade, Anil Kag, and Venkatesh Saligrama. "Selective Classification via One-Sided Prediction".. In: International Conference on Artificial Intelligence and Statistics. PMLR. 2021, pp. 2179-2187.
[HRMS18] Steven Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. "Time- uniform, nonparametric, nonasymptotic confidence sequences". In: arXiv preprint 1OXiv:1810.085 (2018).
[HRMS20]
Steven Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon, "Time-uniform Chernoff bounds via nonnegative supermartingales" In: Probability Surveys 17 (2020), pp. 257-317.

---

[HW06]
Radu Herbei and Marten Wegkamp. "Classification with reject option". . In: The Cana- dian Journal of Statistics/La Revue Canadienne de Statistique (2006). pp. 709-721.
[HZRS16]
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. "Deep residual learning for image recognition". In: Proceedings of the IEEE conference computer vision and pattern recognition. 2016, pp. 770-778.
[Ide19]
Yerlan Idelbayev. Proper ResNet Implementation for CIFARIO/CIFARIO00 in pytorch. Accessed on 2020-2-28. 2019. URL: https: /ttp:////gttbt.gg/ com/ wwt.///aaaatttetttttttrr..a resnet_cifarll
[KH09]
Alex Krizhevsky and Geoffrey Hinton. "Learning multiple layers of features from tiny images". In: (2009).
[KKM12]
Adam Tauman Kalai, Varun Kanade, and Yishay Mansour. "Reliable agnostic learning.. In: Journal of Computer and System Sciences 78.5 (2012), pp. 1481-1495.
[Lei14]
Jing Lei. "Classification with confidence". In: Biometrika 101.4 (Oct. 2014), pp. 755- 769. ISSN: 0006-3444 DOI: 10. wtw9///imee//aaaaeeeeeeeeaeeee/e
[LLWS11] Lihong Li, Michael L Littman, Thomas Walsh, and Alexander L Strehl. "Knows what it knows: a framework for self-aware learning". In: Machine learning 82.3 (2011),
pp. 399-443.
[LS20]
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[MS11]
Shie Mannor and Ohad Shamir. "From Bandits to Experts: On the Value of Side- Observations". In: Advances in Neural Information Processing Systems. Ed. by J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger. Vol. 24. Curran Associates, Inc., 2011. URL: https pptp///eooceeen...eeoepppoo wwwrips.cc/eepeeee cttpccerpppp111111111//pppp1
Paper Pdfer.pdf.
[NS17]
Feng Nan and Venkatesh Saligrama. " "Adaptive classification for prediction under budget". In: Advances in Neural Information Processing Systems. 2017, pp. 4727-4731 Gergely Neu and Nikita Zhivotovskiy. "Fast rates for online prediction with abstention". In: Conference on Learning Theory. PMLR. 2020, pp. 3030-3048.
[NZ20]
[OR94]
Martin J Osborne and Ariel Rubinstein. A course in game theory. MIT press, 1994.
[RST15a]
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. "Online learning via sequen- tial complexities." " In: J. Mach. Learn. Res. 16.1 (2015), pp. 155-186.
[RST15b]
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. "Sequential complexities and uniform martingale laws of large numbers". In: Probability Theory and Related Fields 161.1-2 (2015), pp. 111-153.
[SS11]
István Szita and Csaba Szepesvári. "Agnostic KWIK learning and efficient approximate reinforcement learning". : In: Pruceedings of the 24th Annual Conference on Learning Theory. JMLR Workshop and Conference Proceedings. 2011, pp. 739-772.
[SZB10]
Amin Sayedi, Morteza Zadimoghaddam, and Avrim Blum. "Trading off mistakes and don't don't-knowe t-know predictions". In: (2010).
[Ver+12]
Alexander Vergara, Shankar Vembu, Tuba Ayhan, Margaret A Ryan, Margie L Homer, and Ramón Huerta. "Chemical gas sensor drift compensation using classifier ensem- bles". In: Sensors and Actuators B: Chemical 166 (2012), pp. 320-329. Yair Wiener and Ran Elniv..v. "Agnostic selective classification". In: Advances in neural information processing systems. 201 1, pp. 1665-1673.
[WE11]
[Xu+14]
Zhixiang (Eddie) Xu, Matt J. Kusner, Kilian Q. Weinberger, Minmin Chen, and Olivier Chapelle. "Classifier Cascades and Trees for Minimizing Feature Evaluation Cost". In: Journal of Machine Learning Research 15 (2014), pp. 2113-2144. URL: http:
//jmlr. /tjpllloog/aapeeeeeeeeeeeeeeeeee wwtg/aaprrs/viie hatorr///v//////aaa html.
[ZC16]
Chicheng Zhang and Kamalika Chaudhuri. "The extended littlestone's dimension for learning with mistakes and abstentions". In: Conference on Learning Theory. PMLR. 2016, pp. 1584-1616.
Checklist
1. For all authors...
12

---

(a) Do the main claims made in the abstract and introduction accurately reflect the paper's 's contributions and scope? [Yes] The main contributions of this paper are the setting and formulation, and the schema and their analysis. These are all accurately described in the abstract and introduction.
(b) Did you describe the limitations of your work? [Yes] See $3
(c) Did you discuss any potential negative societal impacts of your work? [No] As primarily theoretical paper concerned with efficiency, our work does have any meaningful negative impacts on society beyond the larger issues of how it is employed. (d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We have considered the potential societal impacts, and conformed to the ethical conduct guidelines
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 or a URL)? [Yes] Main experimen- tal details are discussed in $6 and şE, and code to reproduce the same is made available watee-llssssiaaaiioooooo (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See &6 and $E
at https: : //t/ ///gtttubb... com/ ani kaaak2/
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See $6
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes] See $E
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? [Yes)
(b) Did you mention the license of the assets? [N/A] We used publicly available datasets and libraries.
(c) Did you include any new assets either in the supplemental material or as URL? [No] (d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A] The datasets are made publicly available, and do not contain human data The CIFAR-10 dataset contains low-resolution images of inanimate objects, while the GAS dataset consists of chemical sensor readings.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] See above.
5. If you used crowdsourcing or 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 to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "xcvkb1rIL-", "reviewer": "Reviewer_54E7", "summary": "The authors propose online selective classification and explore strategies with a goal to make the least number of mistakes and abstain the fewest number of times. Concretely, they explore the adversarial case and the stochastic case. They argue that the regret bounds in the ‘versioned uniform explorer’ (VUE) scheme in the adversarial case can be improved logarithmically in N in the stochastic setting by using the VUE-PROD scheme.", "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": "Pros of this work:\n- The introduction and related work sections are well written and easy to understand. \n- The authors have described the main differences with other closely related work in a neat and concise manner.\n- The authors provide strong theoretical bounds for the presented algorithms, VUE, VUE-PROD and MIXED-LOSS-PROD.\n\n\n Cons of this work:\n- The experimental section in the main paper is very limited and has less details for reproducibility and is hard to understand.\n- It seems that the error bars on the GAS dataset are very high for both the measures, excess mistakes and MMEA. It would be great to explain such large standard deviation error regions.\n\nMinor typo:\n\nL111. basis *of its history\n\nPost Rebuttal Update: I will maintain my score of accepting this paper. I would encourage the authors to carefully go through the reviewers concerns and update their paper for the next version.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have not discussed the limitations and societal impact of this work in as much detail.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3-4 hours"}, "extra_text": {}}, {"review_id": "cRKAO8g9dA7", "reviewer": "Reviewer_DiTU", "summary": "This manuscript proposes a framework for selective classification in an online fashion. In particular, it proposes strategies that make few mistakes while not abstaining too many times. A tight regret analysis is well established and experiments on real datasets demonstrate the power of the approach. ", "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 framework appears to be novel and the proposed strategies are impressive, supported by a tight regret analysis.\n\nThe experiments on real datasets also support the usefulness of the framework. \n\nThe paper is well written and is easy to follow. I personally enjoy reading this manuscript. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some practical guidelines on the choice of epsilon and p should be provided. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "JLzQ9ohWryB", "reviewer": "Reviewer_BK84", "summary": "The paper introduces a new setting for online classification with abstention and provide algorithms with provable guarantees for both the stochastic and adversarial setting. The bounds obtained are tight and very well exposed in the paper. The paper overall is of high quality, however, the setting studied makes multiple simplifying assumptions. Most importantly, the cost to abstention is constant, which may not be the case in real world settings. How changing this assumption affects the methods proposed is unclear. Empirical evidence serves mainly as a sanity check of the the theoretical guarantees. ", "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": "Originality: While online learning with abstention has been studied previously, the particulars of the observability and metrics has not been studied previously.  The algorithms provided combines different pieces from the online learning literature. The theoretical analysis is very detailed and novel on it is own. Prior work is compared to adequately. \n\nQuality: The technical details of the paper are clearly argued for and the appendix provides full proofs for al the claims made in the paper. Empirical results do not much to the paper beyond a sanity check of the theoretical results. \n\nClarity: The paper is very well written and details are carefully explained. The proofs are non-trivial but are well explained to understand the technique. However, I will suggest reducing the amount of technical language in the text favor of some more basic explanations of the algorithms and what exactly do the theorems imply.\n\nSignificance: I think this paper makes a nice theoretical contribution to the study of online prediction with abstention. However, I am unsure of how their methods can be generalized to more practical scenarios. Mainly, what if there is a variable cost to abstention that depends on the context, the  setting for this is when the high capacity model may still make mistakes. Furthermore, the methods rely on the finite class assumption, I think an extension to VC classes is possible.\n\n--------------\n\nPost response: I have read the authors responses, although we uncovered that generalization to VC classes is harder than previously thought, the paper still remains interesting in it's own right", "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": "7eeCnDEglyg", "reviewer": "Reviewer_Ja1o", "summary": "This paper focuses on selective classification models in the online setting where the true label is revealed to the learner only when the abstention option is picked. Both adversarial and stochastic cases are studied in this paper, and algorithms are provided for these cases, respectively. ", "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": "Different from the existing paper [Cor+18], this paper is focused on the setting where the true label is revealed to the learner only when the abstention option is picked, which the authors have provided real-world scenarios. Different algorithms are proposed for adversarial and stochastic cases, and detailed regret analysis are also provided for them. This paper looks quite interesting to me. But I have a few questions below. I would really appreciate it if the authors could further clarify them.\n- The goal is to design an online algorithm that doesn’t abstain more times than the best-in-hindsight error-free classifier f*. However, the regret bound from Theorem 4 and 7 has a linear dependence on T, i.e., the term pT if p is a constant. Normally we would hope to get a sublinear dependence on T for the purpose of convergence. Therefore, we need to have varying p. It would be more clear if the authors could explicitly provide the formula for p in the theorems.\n- It would be great if the authors could provide more explanations about the implication of Lemma 1 for regret analysis, especially in the context of Algorithm 1. In this way, it's easier to understand the rationality of how Theorem 2 is derived.\n- It looks like there is no Conclusion section at the end of this paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are discussed in Section 3.\nThis is primarily a theoretical paper. There is no negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers an online learning setting in which the true label is revealed only when the algorithm abstains from making a prediction. Algorithms are proposed for several variants of this setting, and strong theoretical guarantees provide a trade-off between the number of mistakes and the number of abstentions. Some experiments demonstrate that these procedures can also be applied in practice. The work advances the theoretical understanding of selective classification, and as such could be of interest to many in the NeurIPS community.
Decision: Accept (Spotlight)