Adversarial Resilience in Sequential Prediction via Abstention
Authors: Surbhi Goel
Steve Hanneke
Shay Moran
Abhishek Shetty
Venue: NeurIPS 2023 poster (2023)
Keywords: Sequential prediction
adversarial examples
abstention
out-of-distribution
VC Classes
TL;DR: We propose a framework for stochastic sequential prediction with a clean-label injection adversary where we achieve stochastic-like guarantees despite adversarial injections.

Abstract: We study the problem of sequential prediction in the stochastic setting with an adversary that is allowed to inject clean-label adversarial (or out-of-distribution) examples. Algorithms designed to handle purely stochastic data tend to fail in the presence of such adversarial examples, often leading to erroneous predictions. This is undesirable in many high-stakes applications such as medical recommendations, where abstaining from predictions on adversarial examples is preferable to misclassification. On the other hand, assuming fully adversarial data leads to very pessimistic bounds that are often vacuous in practice. 
  
  To move away from these pessimistic guarantees, we propose a new model of sequential prediction that sits between the purely stochastic and fully adversarial settings by allowing the learner to abstain from making a prediction at no cost on adversarial examples, thereby asking the learner to make predictions with certainty. Assuming access to the marginal distribution on the non-adversarial examples, we design a learner whose error scales with the VC dimension (mirroring the stochastic setting) of the hypothesis class, as opposed to the Littlestone dimension which characterizes the fully adversarial setting. Furthermore, we design learners for VC dimension~1 classes and the class of axis-aligned rectangles, which work even in the absence of access to the marginal distribution. Our key technical contribution is a novel measure for quantifying uncertainty for learning VC classes, which may be of independent interest.

Adversarial Resilience in Sequential Prediction via Abstention
Surbhi Goel
Steve Hanneke Purdue University
University of Pennsylvania surbhigecis upenn. edu
steve hww.eee@gail.ccom
Shay Moran
Abhishek Shetty
Technion and Google Research, Israel smoran@technion ac.il
University of California, Berkeley shetty@berkeley.co edu
Abstract
We study the problem of sequential prediction in the stochastic setting with an adversary that is allowed inject clean-label adversarial (or out-of-distribution) examples. Algorithms designed to handle purely stochastic data tend to fail in the presence of such adversarial examples, often leading erroneous predictions. This is undesirable in many high-stakes applications such as medical recommendations, where abstaining from predictions adversarial examples is preferable mis- classification. On the other hand, assuming fully adversarial data leads to very pessimistic bounds that are often vacuous practice.
To move away from these pessimistic guarantees, we propose new model sequential prediction that sits between the purely stochastic and fully adversarial settings by allowing the learner to abstain from making a prediction at no cost on adversarial examples, thereby asking the learner make predictions with certainty. Assuming access to the marginal distribution on the non-adversarial examples, we design learner whose error scales with the VC dimension (mirroring the stochastic setting) of the hypothesis class, as opposed to the Littlestone dimension which characterizes the fully adversarial setting. Furthermore, design learners for VC dimension classes and the class of axis-aligned rectangles, which work even in the absence of access the marginal distribution. Our key technical contribution is novel measure for quantifying uncertainty for learning VC classes, which may of independent interest.
Introduction
Consider the problem of sequential prediction in the realizable setting, where labels are generated from an unknown f belonging to hypothesis class F. Sequential prediction is typically studied under two distributional assumptions on the input data: the stochastic setting where the data is assumed to be identically and independently distributed (i.i.d) according to some fixed (perhaps unknown) distribution, and the fully-adversarial setting where we make absolutely no assumptions on the data generation process. A simple empirical risk minimzation (ERM) strategy works for the stochastic setting where the learner predicts according the best hypothesis on the data seen so far. The number of mistakes of this strategy typically scales with the Vapnik-Chervonente dimension of the underlying hypothesis class F.. However, in the fully adversarial setting, this strategy can lead to infinite mistakes even for classes of VC dimension even if the adversary is required to be consistent with labels from f*. The Littlestone dimension, which characterizes the complexity of sequential prediction in fully-adverse adversarall setting, can be very large and often unbounded compared to
(VC)
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the VC dimension Li887] This mismatch has led to the exploration of beyond worst-case analysis for sequential prediction [STTI HRS20 RST3a BCKP20].
In this work, we propose a new framework that sits in between the stochastic and aully-adversarial setting. In particular, we consider sequential prediction with adversary that injects adversarial (or )ot-of-distribution) examples in a stream of i.id. examples, and a learner that is allowed to abstain from predicting on adversarial examples. A natural motivation for our framework arises in medical diagnosis where the goal is to predict patient's illness based on symptoms. In cases where the symptoms are not among the commonly indicative ones for the specific disease, or the symptoms may suggest disease that is outside the scope of the doctor's ' knowledge, it is safer for the doctor to abstain from making prediction rather than risk making an incorrect one. Similarly, for self- delf-driving cars, in cases where the car encounters weather conditions outside of its training, or unknown information signs, it is better for the algorithm to hand over access to the driver instead of making wrong decision which could end up being fatal.
In the proposed framework, the learner's s goal is minimize erroneous predictions on examples that the learner chooses to predict on (i.i.d. or adversarial) while refraining from abstaining on too many i.i.d. examples. If the learner was required to predict on every example, then the adversary could produce a fully-adversarial sequence of examples which would force the learner to make many erroneous predictions. The abstention option allows us to circumvent this challenge and handle any number of adversarial injections without incurring error proportional to the number of injections. In this framework, we can ask the following natural question:
there statistical price for certainty in sequential prediction?
In particular, can we recover stochastic-lid guarantees in the presence of an adversary if we are allowed to abstain from predicting adversarial examples? A priori, it is not clear where the spectrum between the fully- fully-adversarial and stochastic models, the complexity of this problem lies. The main challenges arise from the fact that the adversary fully controls the injection levels and provides no feedback about which examples were adversarial, and the learner has to perform one-sample outlier detection, which is nearly impossible. Despite this, we show that it is possible to guarantee certainty in a statistically efficient manner.
1.1 Main Contributions
We summarize the main contributions of our work:
We formalize a new framework of beyond-worst case learning which captures sequential prediction a stochastic sequence with clean-labe injection-only adversary. With the option of abstention, our framework allows for any number of injections by the adversary without incurring error proportional to the number of injections. Our notion of error simultaneously guarantees few mistakes on classified data while ensuring low abstention rate on non-adversarial data. Our framework naturally connects to uncertainty quantification and testable learning.
In our framework, we design an algorithm that achieves error Odd log T)) for classes with VC dimension for time horizon T. given access the marginal distribution over the i.i.d. examples. This allows us to get (up to a factor of d) the guarantees of the stochastic setting while allowing for any number of adversarial injections.
We further design an algorithm that achieves O( O(VTTo( T) error for the special (but important) case of VC dimension 1 classes without any access to the marginal distribution over the i.i.d. examples. Similar ideas also allow us to design algorithm for the class of axis-aligned rectangles in any dimension with error (dv O(d/Tooog log T))
Our algorithms uses novel measure of uncertainty for VC classes to identify regions of high uncertainty (where the learner abstains) or high information gain (where the learner predicts and learn from their mistakes). The measure uses structural properties of VC classes, in particular, shattered sets of varying sizes. In the known distribution setting, measure is easy to compute, however for the unknown distribution setting, we show how to design a proxy using only the examples we have seen far using leave-one-out type strategy.
1.2 Related Work
Beyond-worst case sequential prediction. Due to pessimistic nature of bounds in adversarial online learning, there are several frameworks designed to address this issue. One approach is to consider

---

mild restrictions on the adversarial instances such as slight perturbation by noise. This has been formalized as the smoothed adversary model (see [RSTI] HRS20 HRS22 HHSY22 BDGR22]
and has been used to get statistical and computationally efficient algorithms. Another approach has been to make the future sequences more predictable given the past instances. Examples of such settings are predictable sequence [RST3b], online learning with hints [BCKP20), and notions of adaptive regret bounds [FRS20).
Abstention-basee learning. Abstention has been considered in several other works in classification, both in the online and offline settings. An early example of this is the Chow reject model Cho70
Various versions of this have been considered in offline learning (see e.g. [HW06, BW08, BZ20 and references therein) and online learning (see e.g. [ZC16] CDG 19 NZ20 and references therein). These results show that abstention can lead to algorithms with desired features, for example fast rates without margins assumptions. Another line of work that is closely related to our setting the KWIK (knows what it knows) framework by [LWO8 which requires the learner to make predictions only when it is absolutely confident, and abstain otherwise. This requirement was relaxed to allow for mistakes by [SZB]O]. The key difference from our work is that they assume fully-adversariaa stream thus the error bounds can be as large as the size of the domain, which is unbounded in the settings we consider. Perhaps, the work that is closest to our setting is the study of adversarial learning with clean-label injections by [GKKM20] KK21]. In their transductive adversarial model, the learnr is given labeled training examples and unlabeled test examples which it must predict, where the test examples may have been injected by an adversary. They show how to abstain with -dvesarraliall examples. However, in many
few test misclassifications and few false abstentions real-world scenarios, it is unrealistic to expect to have the entire test set in advance, which further motivates the fully online setting that we consider.
Adversarially robust learning. Highly related to our setting is the problem of inductive learning in the presence of adversarial corruptions. The literature on this is generally divided into two scenarios: test-time attacks and training-time attacks. the case of test-time attacks, the learning algorithm is trained on (uncorrupted) i.i.d. training set, but its test examples may be corrupted by an adversary whose intention is to change the classification by corrupting the test example SZS 13 BCM 13 GSSI5 FMS18 AKM19 MHS19 MHS20 MHS21 MHS22 MGDS20). Often the goal in this setting is to learn a classifier that predicts correctly on all adversarial test examples, which is a very strong requirement. Empirical work in this space has focused designing methods to make training adversarially robust [MMS+ [W18), and also on detecting adversarial examples (PDDZI8 AHFD22] Detecting adversarial examples is very challenging tasks and proposed solutions often brittle [CWI7). In fact, our framework does not explicitly require detection as long as we can predict correctly on these. On the other hand, in the case of training-time attacks, the training data the learning algorithm trains on is corrupted by an adversary (subject to some constraints on what fraction it may corrupt and what types of corruptions are possible), while the test examples are uncorrupted Val85, KL93, BEKO2 BNLI2 ABLI7 SKL17 SHN 18 [F21] GKM21 HKM 22, BBHS22] In particular, within this literature, most relevant to the present work is the work on clean-label poisoning. where the adversary's 's corrupted examples are still labeled correctly by the target concept [S BHQS2T). Comparing to these works, is interesting to note that the fact that our setting involves sequential prediction (i.e., online), our problem may be viewed simultaneously as both training-times and test-time corruption: that is, because on each round the point we are predicting (or abstaining) may be inserted by an adversary, this could be viewed as test-time attack; on the other hand, since the prefix of labeled examples we use to make this prediction may also contain adversarial examples, this can also be viewed as training-time attack. Thus, our setting requires reasoning accounting for issues arising from both attack scenarios, representing a natural blending of the two types of scenarios.
2 Abstention Framework
In this section, we present the formal framework for sequential prediction with abstentions. For background on sequential prediction and other related concepts, please refer to AppApepdix A
Notation. We will denote the domain with X' and the distribution over X' as D. We let ((Y) denote the set of all distributions over X. We will work in the realizable setting where our label will be according to some function in F Given class F and data set S { })), we will denote
3

---

by Fls, the class Fls Ff f(z;) - v13. When the data set contains a single point S= (1, })}. J. it will be convenient to denote Fis as F=
Protocol. At the start, the adversary (or nature) picks a distribution D over the domain X' and the labelling function f E F. We will be interested in both the setting where the learner knows the distribution D and the setting where the learner does not know the distribution D. In the traditional sequential prediction framework, the learner sees input za at time and makes prediction yi and observes the true label y/. The main departure of our setting from this is that an adversary also decides before any round whether to inject an arbitrary element of X (without seeing zzt). We denote by & the instance after the adversarial injection (Ø, = 2e or & # z.)). The learner then observes & and makes a prediction y and observes the true label yt, in the traditional sequential prediction framework. We present this formally below.
Protocol 1 Sequential Prediction with Adversarial Injections and Abstentions
Adversary (or nature) initially selects distribution D E (x) and f E F. The learner does not have access to f*. The learner may or may not have access to D. for 1 = I,...," do
Adversary decides whether to inject an adversarial input in this the round (ce 1) or not (c+ 0).
if c = then Adversary selects any &g E X
else Nature selects 2₁ ~ D, and we set 8.- Zt. Learner receives è; and outputs D/ E {0, 1, 1, where L implies that the learner abstains.
Learner receives clean label yt (2,).
Remark. It is important to note we are in the realizable setting, even after the adversarial injections since the labels are always consistent with hypothesis f E F. This model can naturally be extended to the agnostic setting with adversarial labels. It is also possible to allow the adversary to adaptively choose f F, that is, the adversary has make sure the labels are consistent with some f E F at all times but does not have to commit to one fixed f". Another interesting variation would be change the feedback to not include the true label y/+ on rounds that the learner abstains. As we will see, the known distribution case will be able to handle adaptive f* and limited label access.
Objective. In our framework, the goal of the learner is to have low error rate on the rounds it decides predict (that is when ý. E {0, 1)) while also ensuring that does not abstain (je- =1) on too many non-adversaria rounds (ca- = 0). More formally, the learner's 's objective is to minimize the following error (or regret),
T
T
Error: =
Σ
1 = = f (+)) +
Σ [cc = - de =1].
MissdassificationEErrr
AbstentionEErro
It is important to note that we allow the learner to abstain on adversarial examples for free. This allows the learner have arbitrarily many injections without paying linearly for them in the error. Remark. There are many natural generalizations and modification of the model and objective that one could consider. For example, we would consider cost-based version of this objective that would allow us to trade-off these errors.
Connections to testable learning. A further interesting connection can be made by viewing our model as an online version of testable learning framework of [RV22]. In order to see the analogy more direct, will focus on the setting where the learner knows the distribution D. In the setting, learning algorithm is seen as a tester-learner pair. The tester takes the data set as input and outputs whether the data set passes the test. The algorithm then takes as input any data that passes the test and outputs a hypothesis. The soundness guarantee for the pair of algorithms is that the algorithm run on any data set that passes the test must output hypothesis that is good on the distribution. The completeness requires that when the dataset is indeed from the "nice" distribution, then the tester passes with high probability. We can see our framework in this light by noting that the decision of whether to abstain or not serves as test. Thus, in this light, completeness corresponds to the abstention error being small when the data is non-adversarial i.e. from the true distribution, while the soundness corresponds to the misclassification error being small on points the algorithm decides not to abstain. While the testable learning literature primarily focuses on the computational aspects of learning algorithms, our focus is solely the statistical aspects.

---

3 Warm-up: Disagreement-based Learners
As a first example to understand the framework, we consider the most natural learner for the problem. Given the data S of the examples seen thus far, the learner predicts on examples & whose labels it is cer- tain of. That is, if there is unique label for å consistent with Flth Fls. the learner predicts that label. Else, it abstains from making a prediction. This region of uncertainty is known the disagreement region.
Example: thresholds in one dimension. Consider learning a single-dimensional threshold in [0. 1] (that is, concepts x + 1[2 2 f] for any t E [0, 1).. While it is well known that ERM achieves log T misclassification error for i.i.d. data sequences, in the case of an adversarially chosen sequence, it is also well known that the adversary can select inputs in the disagreement region each time (closer and closer to the decision boundary) and thereby force any non-abstaining learner to make a linear number of mistakes (recall that the Littlestone dimension of thresholds is infinite (Li887). Indeed, it is known that the function classes F for which non-abstaining predictors can be forced to have MisclasifficationEroo unbounded size Lit87 7 She
S2(T)) are precisely those with embedded threshold problems of Hod97 ALMMI9). Let us now consider the learner that abstains in the disagreement region and predicts based on the consistent hypothesis outside of this region.
Proposition 3.1. Disugreement- bused learner for one dimensional thresholds has
MisclassiciationEErro 0 and AbstentionError S 2 log
To see this note that our learner only predicts when the input is not in the disagreement region and thus it never predicts incorrectly (MisclasiiciationErroo exchangeability, argument shows that when there are n i..d. examples in the sequence, the probability of the new non-adversarial example being in the disagreement region 1/n. Summing this over the time horizon gives us the above proposition.
0). As for the abstentions, a simple
Perfect selective classification and active learning. The learner for the above thresholds problem is a well-known strategy from the areas of perfect selective classification and active learning known as disagreementtbuuee learning [RS88 EYWIO CAL94 [BL.09 DHM07 HY15). In the perfect selective classification setting [RS88 EY EYWIO, the learner observes the examples sequentially, as in our framework, and may predict or abstain on each, and must satisfy the requirement that whenever it predicts its prediction is always correct. From this fact, it immediately follows that applying any perfect selective classification strategy in our setting, we always have MisclassiciationErro = so that its performance is judged purely on its abstention rate on the iid examples. It was argued by (EYWIO) that the optimal abstention rate among perfect selective classification strategies is obtained by the strategy that makes a prediction on the next example if and only if all classifiers in the hypothesis class that are correct on all examples observed so far, agree on the example. Note that this is precisely the same learner used above. This same strategy has also been studied in the related active learning [CAL94] BBL.09, Han09 Han 14 DHM07 HY21. The
setting of stream-buase
abstention rate achievable by this strategy for general hypothesis classes is thoroughly understood [Han07, [aan I Han09) [Han 12, Han 14, Han 16, EYWTO, EYW12 WHETS HY15). In particular,
complete characterization of the optimal distribution free abstention rate of perfect selective classification is given by the star number of the hypothesis class [HY15) [6n]6]) The star number s is the size of the largest number such that there are examples {x1,.... .......... .r,) } and hypotheses hp. .i.....AA h2 such that h; and by disagree exactly on z;. For instance, 5 = 2 for threshold classifiers abstention rate for perfect
[HY15). It was shown by [6 that the optimal distribution- selective classification is sublinear if and only if the star number is finite (in which case it is always at most log T). One can show that s is always lower bounded by the VC dimension of the class. Unfortunately, the star number is infinite for most hypothesis classes of interest, even including simple VC classes such as interval classifiers H5
Beyond disagreement- based learning. The learner that abstains whenever it sees an example that it is not certain of may be too conservative. Furthermore, it does not exploit the possibility of learning from mistakes. Let us consider another example to elucidate this failure. Consider the
In this setting, instead of observing a sequence of labelled examples, the learner only observes the examples without their target labels, and at each time may query to observe the target label. The disagreement based strategy chooses to query precisely on the points for which the classifiers in the hypothesis class correct on the observed labels so far do not all agree on the label [CAL94]. The rate of querying for this strategy is precisely the same the abstention rate in the perfect selection classification setting [Han] I Han 14 EYW12
5

---

class of d intervals in one dimension where the positive examples form union of intervals. That F = =E 1 [a,,6] : 01 S b1 ...... as S by E [0. =1} over the domain X' = [0, 1]. This class has VC dimension 2d but infinite star number. Suppose that d 2 but examples in the second interval are very rarely selected by i.i.d. examples. Then the disagreement-based learner would suggest to abstain on all examples to protect against the possibility that our new example is in the second interval. However, consider the following simple strategy: if the new example lies between two positives (resp. negatives), we predict positive (resp. negative), else we abstain.
Proposition 3.2. The proposed strategy for the class of d-intervals in one dimension has
MisclassiciationError S d and AbstentionError S 2dlog
To see this, note that whenever predict, either are correct we have identified the location of a new interval, hence reducing the VC dimension of the version space by 1. Since there are at most d intervals, we will therefore make at most 2d errors when we predict, implying MisclassiciationErroe S 2d. As for abstaining on i.i.d. examples, the same argument for thresholds can be applied here by treating the intervals as at most d thresholds.
Higher-order Disagreement-basee learner with Known marginals
We will first focus on the setting when the marginal distribution of the ii.d. distribution D is known to the learner. Suppose F has VC dimension d. In this setting, the algorithm that naturally suggests itself is to take cover for the class under D of accuracy poly(T-1) and use an adversarial algorithm for prediction. Since there are covers of size ( and Littlestone dimension of any finite class is bounded by the logarithm of the size, this seems to indicate that this algorithm will achieve our goal with misclassication error (d log 7') and zero abstention error. But unfortunately note that this algorithm competes only with the best classifier on the cover. The cover is a good approximation only on the marginal distribution D and not on the adversarial examples. In fact, when we restrict to the hypothesis class being the cover, the data may no longer even be realizable by the cover. Therefore, we need to use the access to the distribution is completely different way.
The inspiration for our approach comes from the work of [Han09) 12 on active learning strategies that go beyond disagreementtbasee learning by making use of higher-order notions of disagreement based on shattering. We note, however, that while the work of [Han09 [2 only yields asymptotic and distribution -ebbuddenn-deendentt guarantees (and necessarily so, in light of the minimax characterization of
[HY15) based on the star number), our analysis differs significantly in order to yield distribution-ffee finite-sample bounds on the misclassification error and abstention rate.
As we saw earlier. just looking at the disagreement region does not lead to good algorithm for general VC classes (whenever the star number is large compared to the VC dimension). The main algorithmic insight of this section is that certain higher-order versions of disagreement sets do indeed lead to good notions of uncertainty for VC classes. Our measure uses the probability of shattering h examples (see definition below) for different values of ls freshly drawn from the underlying distribution, under the two restrictions of the class corresponding to the two labels for the current test example, to make the abstention decision. One can think of the probability of shattering as a proxy for the complexity of the version space. This serves both as method to quantify our uncertainty about whether the current example is from the distribution or not, since we can understand the behavior of this quantity in the i..d. case, and also as potential function which keeps track of the number of mistakes. In order to formally state this, we will need some definitions.
Definition 4.1 (Shattering and VC Dimension). Let X' be domain and F be binary function class . C X' is said to be shattered by F if for all y E 1), 1)*
on X i... F C (0. 1) A set (#1...., there exists a function f E F such that of (xx) = y/- The VC dimension of F is defined as the maximum l such that there is a set of size l that is shattered.
Definition 4.2 (Shattered k-tpless). Let be a positive integer. The set of shattered k-tuples, denoted by Sp, for hypothesis class F over domain X is defined as
(F) = { (Z1,...... ..... ....:)::: f } is shattered by F}.

---

Additionally, given a distribution D on the domain, we will refer to as the & shattering probability of FF with respect D. denoted by Pk (F,D). as
8k (S%: (F)) Pke (F, 2) D
Pr 21 Re-
[[ Fx is shattered by Fl
Let us now describe the algorithm (see Algorithm D. The algorithm maintains state variable k which we will refer to the level the algorithm is currently in. The level can be thought of as the complexity of the current version space. At level k, we will work with shattered sets of size k. At each round, the algorithm, upon receiving the example St, computes the probabilities of shattering k examples (drawn i.idd from D) for each of the classes corresponding to sending 4 to 0 and respectively. The algorithm abstains both these probabilities are large, else predicts according to whichever one is larger. At the end of the round, after receiving the true label yr, the algorithm checks whether the probability of shattering & examples is below a threshold ag,, in which case it changes the level, that is, updates & to be k 1.
Algorithm 1: Lavel-based learning for Prediction with Abstension
Set k = d and Fi F
for f 1...., T.AAK k >
do
Receive 82
pk (J(H PN (IR: } 0.6px (Fe) then predict D. T
if min
( (H
else predict bs Jr(1) Pk
Upon receiving label yr, update Fi+1 f- F( ti if Ph: (Fi+1) S Oge then Set ls
if k = 1 2. S then U =
if k = A f & S then Predict with the consistent label for ft.
Below, we state the main error bound of the algorithm and give an overview of the analysis. We defer the detailed proofs to Appppedxi BJ Our theorem shows that both the misclassication error and the abstension error are bounded in terms of the VC dimension.
Theorem 4.1. In the adversarial injection model with abstentions with time horizon T, Algorithm 1 with ag T gives the following.
E E|MisclassffiaaiionErrot < dl log T and E[AbstentionErro]] 6d.
We will now present the main technical idea that we will use to analyze the theorem. Let & be positive integer and x be any example X. The following lemma upper bounds the probability for a random example the shattering probability of the two restrictions of the class are both large compared to the original shattering probability of the class. That is to say for most examples, one of the two restrictions of the class will have smaller shattering probability compared to the original class.
Lemma 4.2. For any & E N and any > 1/2, we have
Pk: (F=-1)) + Pk (Fr-O) > 2npx (F)
Ph++ (F) 2n Pk (F)
1
Pr BND
S
With this in hand, we will first look at the abstention eтror. The intuition is that when the algorithm level kt, an abstention occurs only if the condition from (1) satisfied and Lemma 4.2 bounds the probability of this event. It remains to note that when the algorithm is at level k we both have an upper bound on Pk+1 (since this is the condition to move down to level k from level k + 1) and lower bound on the Pk. (since this is the condition to stay at level k).
Lemma 4.3 (Abstention error). For any d, let [Lg, eg] denote the interval of time when Algo- rithm is at level k. Then, the expected number of non-adversarial rounds at level k on which the algorithm abstains satisfies
E
Σ 1=
I[q = OA v2 = _1
< 5T
(2)
0k
7

---

Next, we bound the misclassification error. The main idea here is to note that every time misclassi- cation occurs at level k, the k-th disagreement coefficient reduces by constant factor. Since we have a lower bound on the disagreement coefficient at a fixed level, this leads to logarithmic bound on the number of misclassifications at any given level.
Lemma 4.4 (Misclassffication error). For any l < ler [ex. ek] denote the interval of time when Algorithm 7 is at level k. For any threshold in Algorithm 7
E
I Live =1 f
S 2. log
Ork
Putting together Lemma and Lemma 4.3 along with a setting of 0g = T-*, gives us Theorem 4.1 Remark. Closer inspection the algorithm and the analysis reveals that the algorithm gives the same guarantees even the setting where the learner does not receive the label y/ during rounds that it abstains (hinted at in Section 2). To see this note that during the rounds that we abstain, we only use the fact that Pk (Fe) does not increase which would remain true when if we did not update the class.
5 Structure-based Algorithm for Unknown Distribution
We move to the case of unknown distributions. In this setting, the example x are drawn from distribution D that is unknown the learner. As saw earlier, is challenging to decide whether single point is out of distribution or not, even when the distribution is known. This current setting is significantly more challenging since the learner needs abstain on examples that are of distribution for a distribution that it doesn" 't know. A natural idea would be to use the historical data to build model for the distribution. The main difficulty that, since do not get feedback about what examples are corrupted, our historical data has both in-distribution and out-of-distribution examples. The only information we have about what examples are of distribution is the prediction our algorithm has made on them. Such issues are major barrier in moving from the known distribution case to the unknown distribution case. In this section, we will design algorithms for two commonly studied hypothesis classes: VC dimension I classes, and axis-aligned rectangles. Though, VC dimension 1 seems restrictive, there are classes with VC dimension with large Littlestone dimension and large star number, which capture the complexity of sequential prediction and active learning respectively. Thus, our results separate the complexity of those models from our model of abstention.
5.1 Structure-based Algorithm for VC Dimension Classes
A key quantity that we will use in our algorithm will be version of the probability of the disagreement region but computed on the historical data. The most natural version of this would be the leave-one- out disagreement. That is, consider the set of examples which are in the disagreement region when the class restricted using the data set with the point under consideration removed. This estimate would have been an unbiased estimator for the disagreement probability (referred to earlier as P1 in Definition 4.2). As mentioned carlier, unfortunately, in the presence of adversarial injections, this need not be good estimate for the disagreement probability.
In order to remedy this, we consider a modified version of the leave-one-out disagreement estimate which considers examples z in the disagreement region for the class Fls, (a.y) where Sy is the subset of the datapoints which disagrees with a fixed reference function f. important note that this function f is fixed independent of the true labelling function f*. Though this seems bit artificial at first, but this turns out to be a natural quantity to consider given the structure theorem for VC dimension one classes (see Appendix C.I for more details).
Definition 5.1. Let F be class of functions and let f E F be reference function. Let S = ((.,))) {1}} be a realizable data set. Define
F(S.F,f) - x: By (I,z) E SEEEEAEES (Fls (Flss)tea))
where Sy w) E S fxx w). Further, we will denote the size of this set by (S,F)
[IS, f)]. We will suppress the dependence on F when it is clear from context.
8

---

Let us now present the main algorithm (see Algorithm 2) The main idea of the algorithm is similar to Algorithm in the known distribution case. We will make a prediction in the case when the difference between I' for the two classes corresponding to the two labels for the point is large. The idea is that when a prediction is made and mistake happens, the size of T goes down similar to Pk in the known distribution case. In the case when the difference is small, we will abstain.
Algorithm 2: Structure- based learning for Prediction with Abstention for Unknown Distribution
Let F be reference function and be the abstention threshold. Set Fo = F and S = 9
for 1 ,...., do
Receive Zt
Let ug = [ [S [) and ai - ( if â. & S (Fi) then Predict with the consistent label for it.
else if max {ao, a1} 2 then d argmax, as
else V/ =
Upon receiving label ye. update S. S U (8e, }o) and Fe F
Though the algorithm is simple and can be made fairly general, our analysis is restricted to the case of VC dimension one. The main reason for this restriction is that our analysis relies on structure theorem for VC dimension one classes which has no direct analogy for higher VC dimension. But since the algorithm has natural interpretation independent of this representation, we expect similar algorithms to work for higher VC dimension classes as well.
Theorem 5.1. Let F be a hypothesis class with VC dimension 1. Then, in the corruption model with abstentions with time horizon T, Algorithm 2 with parameter a V gives the following guarantee
E E|MiisclassficationEEroo < log and IE AbbtentionEError] S /T /Tlog T.
We will now present the main technical ideas that we use to analyze the algorithm. We will keep track of the mistakes using the size of the disagreement region, which we denote by 7/- 7 (St, F). The main idea for the proof is to note that when we decide to predict the label with the larger value of r is bigger by an additive a. Thus, when a mistake occurs the value of decreases by at least a. Summing the errors over all time steps gives the following bound.
Lemma 5.2. Algorithm 2 has [E|MisclassfiiationEEroo < 2T/a.
Next, we move on to the number of abstentions. In fact, we will prove stronger structural results that shows that the number of examples such that there is any set of adversarial injections that would make the algorithm abstain is small. We refer to examples on which algorithm can be made to abstain as attackable examples (formally defined in Definition C.2 The main idea is to prove that in any set of iid examples, there are only a few attackable ones. This is formally stated and proved as Lemma C.3 Using this claim, we can bound the number of abstentions using exchangeability argument.
Lemma 5.3. Algorithm 2 has [[AbbstentooEError]] S a log
The proof of Theorem 5.1 follows from Lemma 5.2 and Lemma 5.3 by setting a = vT/ log
5.2 Structure-based Algorithm for Axis-aligned Rectangles
We can extend the idea from above to design an algorithm for the class of axis-aligned rectangles in dimension p (VC dimension is 2p) that achieves abstention and misclassification error bounded by OppyTT log T'. This exhibits class of VC dimension > 1 for which we can attain the desired guarantees without access to the distribution.
Theorem 5.4. Let F be the class of axis aligned rectangles in RP. Then, Algorithm 3 with /T/ log T satisfies
MisclasiificttinnErrrr S PV TT/Tlog?
AbstentionError - 2p T Tlog T + 2p log T.
For details of the algorithm and analysis, we refer the reader to Appendix C.3.]

---

6 Discussion and Future Directions
In this paper, we introduce a framework for beyond- heyond-worst worst case adversarial sequential predictions by using abstention. Our proposed framework falls at the intersection of several learning paradigms such as active learning, uncertainty quantification, and distribution testing. In this framework we show two main positive results, validating the beyond-wors. case nature of our framework. However, our work has only scratched the surface of understanding learnability for VC classes in this new framework. Here we discuss several exciting future directions:
General VC classes with unknown distribution. Extending the structure- algorithms for general VC classes is wide open. Even characterizing the complexity of learning in the unknown distribution open. One could attempt to convert the algorithm from [Section 4 that for any class F with VC dimension d, achieves abstention error and misclassificatiin error bounded only as a function of d. Recall that Algorithm I computed the probabilities of shattering k points using the knowledge of the distribution and made a prediction yi depending on the relative magnitudes of the probabilities corresponding to the two restricted classes. The main challenge in the unknown distribution case is that it is not immediately obvious how to compute these quantities.
One natural approach is to use the historical data as proxy for the distribution. That is, given the data set St of size n, compute the leave-k-out estimator for the probability as follows (a. = 1/(x) Ercs.IT
T shattered by Flsvr] There are a few things to observe about this estimator. First, in the case when the data is generated i..d., this estimator is unbiased. Further, though each of the summands is not independent, one can show concentration for estimators of this form using the theory of U-statistics. Additionally, recall that in Algorithm I required the thresholds ar to be set to O(k) (we use T but it is straightforward to extend this to T' for c < 1). This appears to be high precision but note that the "number of samples" one has for a data set of size n is n O(k) Thus, is conceivable that such an estimator can give the necessary bounds. Unfortunately, the challenge with analyzing this in our setting is that we do no know which of the examples are adversarial. Thus, the adversary could inject examples to make our estimates arbitrarily inaccurate. Thus, as in the case of the VC dimension classes and rectangles, our analysis would need to not rely on the accuracy of the estimates but rather use these estimates to maintain progress or construct other versions of estimators that are unaffected by the adversarial injections.
Tight bounds for known distribution. In the known distribution case, remains to find the optimal error bound. It would be interesting to improve the upper bound or perhaps even more interesting to show separation between stochastic sequential prediction and our model. We conjecture that the correct dependence on VC dimemsion d should be linear and not quadratic, and our analysis is potentially lose in this aspect. A potential strategy to obtain an improved bound would be to choose the level A at each iteration in an adaptive manner.
Beyond realizability. Our techniques rely strongly on the realizability (no label noise), however our framework can naturally be extended to settings with label noise. Immediate questions here would be to extend our results to simple noise models such as random classification noise and Massart noise or more ambitiously the agnostic noise model.
Beyond binary classification. Our framework can naturally be extended to more general forms of prediction such as multiclass classification, partial concept classes, and regression. It would be interesting to characterize the complexity of learning in these settings.
Connections conformal prediction and uncertainty quantification. The unknown distribution case can be seen as form of distribution-free uncertainty quantification. It would be interesting to understand connections to other forms such as conformal prediction. On a technical level, our work exploits exchangeability of the i.i.d. sequence which is the foundation of conformal prediction, though the main challenge in our setting is the presence of adversarial inputs. It would be interesting to build on this connections and understand whether techniques can be ported over in either direction.
Computationally efficient algorithms. Our focus for this paper has been entirely on the statistical benefits of abstention. Understanding the computational complexity in this setting is an exciting avenue for research. Concretely, for halfspaces in d dimensions, is there a polynomial time algorithm for learning with abstentions, even for well-behaved distributions such as Gaussians. On a related note, showing computationall gaps this specialized setting would be interesting, albeit disappointing.
10

---

Acknowledgements
S. Goel would like sincerely thank Thodoris Lykouris and Adam Tauman Kalai for working with her on designing the model of adversarial learning with abstention. Several ideas presented in the Section and are based on discussions with T. Lykouris and A. Kalai. We would also like to thank our anonymous NeurIPS reviewer for helping us improve the clarity and accessibility of our paper.
References
[ABL17] Pranjal Awasthi, Maria Florina Balcan, and Philip M Long. The power of localization for efficiently learning linear separators with noise. Journal of the ACM (JACM), 63(6):1-27, 2017.
[AHFD222] Ahmed Aldahdooh, Wassim Hamidouche, Sid Ahmed Fezza, and Olivier Déforges. Adversarial example detection for dnn models: A review and experimental comparison. Artificial Intelligence Review, 55(6))4403-4465 2022.
[AKM19] Idan Attias, Aryeh Kontorovich, and Yishay Mansour. Improved generalization bounds for robust learning. In Proceedings of the 30th International Conference on Algorithmic Learning Theory, 2019.
[ALMM19] Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite littlestone dimension. In Proceedings of the 51st Anmual ACM Symposium on Theory of Computing (STOC), page 852-860, 2019.
[BBHS22] M.-F. Balcan, A. Blum, S. Hanneke, and D. Sharma. Robustly-reliable learners under poisoning attacks. In Proceedings of the 35th Annual Conference Learning Theory, 2022.
[BBL09] M.-F. Balcan, A. Beygelzimer, and J. Langford. Agnostic active learning. Journal of Computer and System Sciences, 75(1):78 89, 2009.
[BCKP20] Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Online learning with imperfect hints. In Proceedings of the International Conference on Machine Learning (ICML), pages 822-831. PMLR, 2020.
[BCM+ 13] Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Srndić, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Joint European conference on machine learning and knowledge discovery databases, pages 387-402, Springer, 2013.
[BD15] Shai Ben-David. notes on classes with vapnik-chervonenkis dimension 1, 2015.
[BDGR22] Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy as statistical learning. In Proceedings of the Conference on Learning Theory (COLT), pages 1716-1786. PMLR, 2022.
[BEK02] Nader H Bshouty, Nadav Eiron, and Eyal Kushilevitz. PAC learning with nasty noise. Theoretical Computer Science, 288(2):255-22) -255, 2002.
[BHQS21] Avrim Blum, Steve Hanneke, Jian Qian, and Han Shao. Robust learning under clean- label attack. In Conference on Learning Theory (COLT), 2021.
[BNL12] Battista Biggio, B Nelson, and P Laskov. Poisoning attacks against support vector machines. In 29th International Conference on Machine Learning, pages 1807-1814, ArXiv e-prints, 2012.
[BW08] Peter L. Bartlett and Marten H. Wegkamp. Classification with a reject option using a hinge loss. Journal of Machine Learning Research, 1893 2008.
[BZ20] Olivier Bousquet and Nikita Zhivotovskiy. Fast classification rates without standard margin assumptions, 2020.
11

---

[CAL94] David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine Learning, 15:201-221, 1994.
[CDG+19 19] Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, and Scott Yang. Online learning with abstention, 2019.
[Cho70] C. Chow. On optimum recognition error and reject tradcoff. IEEE Transactions on Information Theory, 16(1):41-46, 1970.
[CW17] Nicholas Carlini and David Wagner. Adversarial examples are not easily detected: Bypassing ten detection methods. Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 3-14. ACM, 2017.
[DHM07] S. Dasgupta, D. Hsu, and C. Monteleoni. A general agnostic active learning algorithm. Advances in Neural Information Processing Systems 20, 2007.
[ЕУW10] Ran El- Yaniv and Yair Wiener. On the foundations of noise-free selective classification. Journal of Machine Learning Research, 11(5), 2010.
[EYW12] R. El-Yaniv and Y. Wiener. Active learning via perfect selective classification. Journal of Machine Learning Research, 13(2):255-25) 279, 2012.
[FMS18] Uriel Feige, Yishay Mansour, and Robert Schapire. Robust inference for multiclass classification. In Firdaus Janoos, Mehryar Mohri, and Karthik Sridharan, editors, Algorithmic Learning Theory, ALT 2018, 7-9 April 2018, Lanzarote, Canary Islands, Spain, volume 83 of Proceedings of Machine Learning Research, pages 368-386 PMLR, 2018.
[FRS20] Dylan J. Foster, Alexander Rakhlin, and Karthik Sridharan. Adaptive online learning, 2020.
[GKKM20] Shafi Goldwasser, Adam Tauman Kalai, Yael Tauman Kalai, and Omar Montasser. Selective classification algorithms provably robust to arbitrary adversarial examples. In Advances in Neural Information Processing Systems, 2020.
[GKM21] Ji Gao, Amin Karbasi, and Mohammad Mahmoody. Learning and certification under instance-targeted poisoning. The Conference on Uncertainty in Artificial Intelligence (UAI), 2021.
[GSSI5] lan J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In Proceedings of the 3rd International Conference Learning Representations, ICLR, 2015.
[Han07] S. Hanneke, A bound on the label complexity of agnostic active learning. In Proceedings of the hh International Conference on Machine Learning. 2007.
[Han09] Hanneke. Theoretical Foundations of Active Learning. PhD thesis, Machine Learning Department, School of Computer Science, Carnegie Mellon University, 2009.
[Hanl1] S. Hanneke. Rates of convergence in active learning. The Annals of Statistics, 39(:)3333-
20
[Han12] S. Hanneke. Activized learning: Transforming passive to active with improved label complexity. Journal of Machine Learning Research, 13(5):1469- 15877, 2012.
[Han14] 14] Hanneke. Theory of disagreement- based active learning. Foundations and Trends in Machine Learning, 7(2-3):131 13:3:)1113099 10910,,91110 2014.
[6 Hanneke. Refined error bounds for several learning algorithms. Journal of Machine Learning Research, 17(135):1-55, 2016.
[HHSY22) Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang. Oracle-efficient online learning for beyond worst-case adversaries. Advances in Neural Information Processing Systems (NeurIPS), 2022. to appear.
12

---

[HKM* 22] S. Hanneke, A. Karbasi, M. Mahmoody, I. Mehalel, and S. Moran. On optimal learning under targeted data poisoning. In Advances in Neural Information Processing Systems 36, 2022.
[Hod97] Wilfrid Hodges. A Shorter Model Theory. Cambridge University Press, 1997.
[HRS20] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis of online and differentially private learning. Advances in Neural Information Processing Systems, 33:9203-9215, 2020.
[HRS22] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis with adaptive adversaries. In Proceedings of the Annual Symposium Foundations of Computer Science (FOCS), pages 942-953, 2022.
[HW06] Radu Herbei and Marten H. Wegkamp. Classification with reject option. The Canadian Journal of Statistics / La Revue Canadienne de Statistique, 34(4):709-721, 2006.
[HY15] Steve Hanneke and Liu Yang. Minimax analysis of active learning. Journal of Machine Learning Research, 161109)3447-36002 2015.
[HY21] S. Hanneke and L. Yang. Toward general theory of online selective sampling: Trading off mistakes and queries. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021.
[KK21] Adam Tauman Kalai and Varun Kanade. Towards optimally abstaining from prediction with ood test examples, 2021.
[L93] Michael Kearns and Ming Li. Learning in the presence of malicious errors. SIAM Journal on Computing, 22(4):807-837, 1993.
[LF21] Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defense against general poisoning attacks. International Conference on Learning Representations (ICLR), 2021.
[Lit87] Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear- threshold algorithm. In 28th Annual Symposium on Foundations of Computer Science (sfes 1987), pages 68 68-77, 1987.
[LLWW88] Lihong Li, Michael Littman, and Thomas J Walsh. Knows what it knows: framework for self-aware learning. In Proceedings of the 25th international conference on Machine learning, pages 368-575, 2008
[MGDS20] Omar Montasser, Surbhi Goel, Ilias Diakonikolas, and Nathan Srebro. Efficiently learn- ing adversarially robust halfspaces with noise. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 7010-7021. PMLR, 2020.
[MHS19] Omar Montasser, Steve Hanneke, and Nathan Srebro. Vc classes are adversarially robustly learnable, but only improperly. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirly-Second Conference on Learning Theory, volume 99 of Pro- ceedings of Machine Learning Research, pages 2512-2530, Phoenix, USA, 25-28 Jun 2019, PMLR.
[MHS20] Omar Montasser, Steve Hanneke, and Nati Srebro. Reducing adversarially robust learn ing to non-robust PAC learning. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Infor- mation Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6-12 12, 2020, virtual, 2020.
[MHS21] Omar Montasser, Steve Hanneke, and Nathan Srebro. Adversarially robust learning with unknown perturbation sets. CoRR, abs/2102.02145, 2021.
[MHS22] O. Montasser, S. Hanneke, and N. Srebro. Adversarially robust learning: A generic minimax optimal learner and characterization. In Advances in Neural Information Processing Systems 36, 2022.
13

---

[MMS 17] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu, Towards deep learning models resistant to adversarial attacks. arXiv preprint 17Xiv:/706.00000 2017.
[NZ20] Gergely Neu and Nikita Zhivotovskiy. Fast rates for online prediction with abstention, 2020.
[PDDZ18] Tianyu Pang, Chao Du Yinpeng Dong, and Jun Zhu. Towards robust detection of adversarial examples. In Advances in Neural Information Processing Systems, pages 4579-4589, 2018.
[RS88] Ronald L. Rivest and Robert H. Sloan. Learning complicated concepts reliably and usefully (extended abstract). In Tom Mitchell and Reid Smith, editors, Proceedings AAAI-88, pages 635-666--660 640.6 AAAI, 1988.
[RS13a] Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. Proceedings of the Conference on Learning Theory (COLT), pages 993-1019. PMLR, 2013.
[RS13b] Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with pre- dictable sequences. Advances in Neural Information Processing Systems, 26, 2013.
[RST1I] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Stochastic and constrained adversaries. arXiv preprint arXiv: 104.5000 2011.
[RV22] Ronitt Rubinfeld and Arsen Vasilyan. Testing distributional assumptions of learning algorithms. arXiv preprint arXiv:2204.07196 2022.
[She78] Saharon Shelah. Classification Theory and the Number of Non-isomorphic Models. North Holland, 1978.
[SHN+ 18] Ali Shafahi, W Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer. Tudor Dumitras, and Tom Goldstein. Poison frogs! targeted clean-label poisoning attacks on neural networks. In Advances in Neural Information Processing Systems, pages 6103-66 6013, 2018.
[SKL11]] Jacob Steinhardt, Pang Wei Koh, and Percy Liang. Certified defenses for data poisoning attacks. Advances in Neural Information Processing Systems, 30, 2017.
[SZB10] Amin Sayedi, Morteza Zadimoghaddam, and Avrim Blum. Trading off mistakes and don't-know predictions. In Advances in Neural Information Processing Systems, pages 2092-2100, 2010.
[SZS+ 13] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013.
[Va185] Leslie G Valiant. Learning disjunctions of conjunctions. In Proceedings of the 9th International Joint Conference on Artificial intelligence, pages 560-566, 1985.
[WHE15] Y. Wiener, S. Hanneke, and R. El-Yaniv. A compression technique for analyzing disagreement-basse bbseee active learning. Journal of Machine Learning Research, 16(4):713- 745, 2015.
[WK18] Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International conference on machine learning. pages 5286-5295. PMLR, 2018.
[ZC16] Chicheng Zhang and Kamalika Chaudhuri. The extended littlestone's dimension for learning with mistakes and abstentions. Conference on Learning Theory, pages 1584-1616. PMLR, 2016.
14

---

A Preliminaries
We introduce the framework of sequential binary prediction. We focus on the realizable case for direct comparison to the model that we will subsequently introduce. In sequential binary prediction, the
time step an adversary picks 3e E X (potentially from a distribution Dt) and presents learner. The learner then picks Vi E {0, 1) and then receives as label = (zz) where f E F is the unknown function that the learner is trying to learn. The objective of the learner is to minimize the number of mistakes it makes. This is measured using the regret (also known as the mistake bound the realizable case), defined as
Regrety Σ
1 life + Hyl.
The stochastic case of sequential binary prediction corresponds to the setting when the input z; is sampled from fixed D, = independently across time. This the sequential analogue of the classical i.i.d. batch model of learning. We now introduce fundamental notion of complexity for hypothesis classes, the VC dimension which captures the regret in this setting. The VC dimension measures how expressive hypothesis class is by measuring the number of functions that can be realized by the class on a set of points
Definition A.1 (Shattering and VC Dimension). Let X' be domain and F be binary function class on X i.e. C 10, 1)x set (æ1,.... } S X is said to be shattered by JF if for all y E {0. 1)* there exists function f E F such that (z;) = ys. The VC dimension of F is defined as the maximum k such that there a set size that shattered and denoted by VCDim (F).
The VC dimension originally introduced in the context of binary classification in the batch setting but minor modifications the argument show that even the sequential prediction setting, the VC dimension characterizes the regret in stochastic sequential prediction.
Continuing the discussion about shattering, we will introduce a notion that corresponding to the probability of shattering a set of points. Though this notion does feature in usual analysis of sequential prediction, it will be a key to the design and analysis of algorithms in our setting. See /Section 4 for further discussion.
Definition A.2 (Shattered k-tuples). Let & be a positive integer. The set of shattered k-tuples, denoted by Sg, for hypothesis class F over domain X' is defined
S (F) = (z1,..., xx)) { 36 is shattered by F}.
Additionally, given a distribution on the domain, we will refer to as the k shattering probability of F with respect to D, denoted by Pk (F, D), as
Pk (F,2) D ck (Sx (F))=
Pr NDON
[[ ... .xk is shattered by F].
case of particular interest in the above definition k = 1. This notion closely studied in active learning under the name of disagreement region.
Definition A.3 (Disagreement Region). Let F be hypothesis class on domain X. The disagreement region of F is defined as
S (F) f e X: 3f.9 F such that f(x) # g(x))
Analogously, we will the disagreement probability as
P1 (F,2) D (8i (F)) = Pr |f.g such that f(x) + g(x))
=~D
Going back to sequential prediction, in seminal result [Lit87] showed that the mistake bound is characterized by a combinatorial property of the hypothesis class known as the Littlestone dimension. Though the definition would not be central to work, we include it here for comparison to our results.
Definition A.4 (Littlestone Dimension). Let J hypothesis class on domain X. A mistake tree full binary decision of depth i tree whose internal nodes are labelled by elements of X. Every root
15

---

to leaf path in the mistake tree corresponds to a sequence (z,, Be) by associating label to node depending on whether it the left or right child its parent on the path. A mistake tree of depth & said to be shattered by a class F if for any root to leaf path (zi, Vi)i=1> there a function E FF such that f(x;) Ys for all i S f. The Littlestone dimension of the class F denoted by LDim (F) is the largest depth of a mistake tree shattered by the class F.
The Littlestone dimension completely characterizes the mistake bound of the class F in the sense that any algorithm can be forced have mistake a bound of Q (LDim (F)) and there exists an algorithm known as the standard optimal algorithm (SOA) with a mistake bound of (LDim (F)). Though this characterization is elegant, it is usually interpreted simple classes the Littlestone dimension infinite. This is exemplified by the class of thresholds
negative result since even
i.c. F { |a,1] a E [0.1]] } over the domain X' [0, 1J. for which the VC dimension is 1 but the Littlestone dimension is infinite. As noted earlier, the VC dimension captures the number of mistakes when the inputs are i..dd while Littlestone captures the number of mistakes for the worst case, dealing to disparity between achievable mistake bounds in the two settings. This discrepancy is the main motivation for the study sequential prediction beyond worst-case settings.
B Proofs from Section
B.1 Properties of Higher-Order Disagreement: Proof of Lemma 4.2
We first begin by relating the probabilities of shattering & points for the classes gotten by restricting to evaluating to 0 and at x respectively, for an arbitrary point x. The proof of the following lemma uses simple inclusion exclusion argument.
Lemma B.1. For all x E and any hypothesis class F, we have
D 00 Sh (5
+ Don (Sx (F2-H)) < 8h (Sx (F)) + D 80 (Sx (Fa-I) n So (FR-MO)
Equivalently,
Pk (Fe+1)+ +px (Fe-O) & Pk (F)+ Pr TI
Ii...., Ia is shattered by both F=+1 and F2
Proof. For II X, consider the four indicator random variables given by
A 1 31,-..; Tn is shattered by f
A2 1
[1r... In is shattered by f=)
4g $1,..., Fy is shattered by F and F
A4 1 (Ii,..., Fn is shattered by F)
Note that A₁ + A2 < Ag + A4. Taking expectations gives the desired result.
In order to prove the main lemma, we then take expectations with respect to the point x drawn independently from D. The key observation is to relate the probability of & point being shattered by both classes that evaluate to and at x, for a random point æ, to the probability of shattering + points.
Proof of Lemma 4.2 The proof follows by using Lemma B. to get (3) and Markov's inequality
to get The final line follows by noting that since 21,..., T'k and x are drawn from D and are
16

---

shattered, (4)
computes the probability that l + 1 points are shattered.
Pk ( + pk (Fe-L))
Pr
2np (F)
Pr rwD
Pk (F) +
Pr TIann
; Ty shattered by both J= and f==+ 2 20pR (F) (3)
Pr
Pr BI
21 Bhr..,, Tb shattered by both J and _= 2 (2n) - 1) pa (F)
DnD
EE
Pr Pres
T1...., 2h is shattered by both F= and F=
(4)
(2 1) Pkb (F)
Pk+1 (F)
21j
Pk (F)
B.2 Proof of Lemma 4.3
Proof. Let & [ex, my). Recall that F, denotes the class consistent with the data seen till time t.
Recall that H, denotes the history of the interaction till time t.
E 1 [a
OA (a.) 1] H1]
E
1 (e 0A De (xx) 11 He)
(5)
E
1 [U (Ire) -] Hi]
min Ph (f pk (F. ( 2 0.6ps (Fi)
Pr
HRG)
p (FR:-1)) + ph (J 2 1.2ps (Fi) He
Pr
(7)
5 Ph++ (Fr)
(8)
Pk (Fi)
5 06+11
(9)
Olk
The equality in (5) follows from the fact that in the uncorrupted rounds, ât zz. The inequality in (6) follows from the condition for abstention in Algorithm and the fact that 2, ~ D. [7) from the fact that the min of two numbers
most their average. The key step is (8) which follows
from Lemma 4.2
(9) follows from the fact that at level k in Algorithm [ p (Fx) < 09 and
Pk (Jt)
1- Summing this bound and noting that ex lg is at most 7, get the required
bound.
B.3 Proof Lmmma
Proof. Note that from definition of Algorithm
I we have that when D
Ps (F(r=1) Ps (F ( & 0.6pp (Fi). Thus, since we predict with the label corre- sponding to max
min
pk (IRLL)) Pk (F. (F) ) } if we make a mistake, we have
Pk (F++1) S 0.6 Pk (Fi).
Also, note once end of the phase corresponding to k, ck. is reached when Pk (Fi) S ag. This leads the required bound.
B.4 Proof of Theorem 4.1
Proof. First, us look at the misclassication error. Note that Algorithm will not misclassify when & 1. To see this, recall from Definition 4.2 that o; Sn implies that there is unique label
17

---

consistent with the history. For the remaining levels, we sum the errors from Lemma 4.4 and recall that ar = which gives us
MisclassifiattionErro
1 1- (x+)]
t=1
log
ack
k=2
d
2
k log T
k=2
d log Ti
For the abstention error, again begin with the case of k 1. Note that for t l1, we have
[ E St (Fi) an. 2nD
Pr
Thus, have bound of Tai on the expected error in this case. For the remaining levels, sum the error from (2) over all k which gives us the bound
AbstentionError
1|c = 0 =T]
6k
1 [e 0A
t=4
0j+1
= 1 + 57
O%
k=2
1
= 1+ 57
T
2=
< 5d + 1
< 6d.
This gives us the desired bounds.
C Proofs from Section 5
C.1 Structure for VC Dimension One Classes
Definition C.1. Consider domain A' and a partial order < on X. We say that set 7 is an initial segment of if for all x E and y E X such that y < x, we have y We say that a partial order is a tree ordering if every initial segment I is a linear order i.e. for all E I, either x x or x x.
Theorem C.1 (BDI5). Let F. be hypothesis class over the domain X. Then, the following are equivalent:
a. has VC dimension 1.
b. There is a tree ordering - on X and a hypothesis f such that every element of the set = t he :
is initial segment of 2.
The result above was initially observed in BD15
18

---

C.2 Proof of Lemma 5.2
Lemma C.2. For any we have that
7+1 72 1 Misclassification Miissaiiiiislastttttttiin time 1.
(10)
Proof. First, note that in any round that a mistake was not made, we have that 7++1 S 7h. 1. This is because at most one point added to the data set in each round.
Note that (S F(++1)
(5
<|r ( Further, we have/r [), S
I 1, From the condition for predicting, have that
( | (S).
max
When we make misclassication, we go the smaller value for I, therefore we get the desired bound.
Proof of Lemma 3.2 Note that MisclasiiiicttionError = T [Misllsssification at time t]. Rear-
ranging 10 and summing gives
MisclasificationErroo <
(7t 7++1 1)
Note that for all we have that % S which gives us the desired bound.
C.3 Proof of Lemma 5.3
Definition C.2 (Attackable Point). Let F be a hypothesis class and let f E FF be representative function. Let S be realizable dataset. We say that a point æ attackable with respect a data set S if there exists is sequence of adversarial examples A, such that algorithm abstains on example when the history is As) (z). In other words, attackable if there set of adversarial examples A₂ such that Si (FlsuAA(a)) and
max Fr (SSUA I (oSUAMMO)) | Ssa
The key lemma for analysis is that the number of attackable examples is bounded. Lemma C.3. Let F be hypothesis and f F be any reference function. Let S be any set of examples. Then, the number of attackable examples is at most a.
The proof uses a structure theorem for classes with VC dimension which states that they be represented as initial segements a tree order.
Proof. Let ʃ be the representative function from the characterization Theorem C.I Futher, let I be the tree corresponding to the tree order on X. Since is fixed function that does not depend on the algorithm or the history of interaction with adversary, we can preprocess all points and labels tranform the class be such that f is the all
to be xored with the labels of f. In other words, zeros function. In this setting, the true hypothesis f* corresponds to a path and threshold x" on I such that (x) = 1 if and only if æ E p and x < x². For this proof, it is important to consider only adversaries that do not get to chose the true hypothesis f* adaptively. Thus the path is fixed throughout the history of the interaction.
Let be the data set under consideration. First note that by definition, we only need to consider the points v in the disagreement region. The labels of all points that are not in the subtree of the deepest 1 labeled point are fixed and thus cannot be in the disagreement region. Thus, we only need to consider the points in the subtree of the deepest 1 labeled point in S.
19

---

First note that points that have more than a points in descendant subtree cannot be attacked. This is because if the point is labelled 0 then all its descendants are in the disagreement region. This remains true even for any points that are added to the data set. Thus, [ (SUAA) {z), FT
This is because in the definition of y we remove all points labelled O.
For any node ut denote by pos(v) the closest ancestor on the path corresponding to the positíve points, We claim that u has fewer than a points its descendant subtree, then is attackable only if
{o E S :os(u) 3 pos(c) is not a descendant of u] S a
(11)
First note that adding any 0 labelled points to S as A. does change the number of points in r. Further note that for u such that pos(u) N pos(v), adding a labelled point must be on the path between pos(u) and po)(v). But, this would remove u from the disagreement region. Thus, all point e would be counted in I' and if these are greater than a then u is not attackable.
Consider the point that is minimal amongst pos(u) (u) for satisfying (T) and be node such that pos(u) = w. First note that all points that satisfy (11) are in the subtree of w. Second, note that this subtree has at most points. This is because if there were more than a points, would not satisfy (II) which is a contradiction.
Proof of Lemma 5.3] Let iT be the number of i.i.d. points in the data set time T. Note that the only i..d. points that we abstain on are the attackable points. But, since the i.i.d. points are exchangeable if i i.i.d. points are seen so far, the probability of abstain is given by 4. Thus, the expected total number of abstentions is at most
f
a log T
as required.
C.3.1 Structure-based Algorithm for Axis-aligned rectangles
Recall that the class of axis-aligned rectangles consists of functions f parameterized by (a1, .i...., ap. bp) such that
{
if [p), S 24 s
Mor (1))))
otherwise.
Now consider the following algorithm:
Algorithm 3: Structure- based learning for Axis-aligned Rectangles
Set .1...... 00 = 00 and Ph.....bb 00
for t = T do
Receive d;
if VT < 1,9r = 0 then 11 = 0
else if á, & S1 then ői f(x.) for any f E Fi-1
else if Es,...., Sa < t and _i....., la E such that Leydd E [ ai,) U (bi,, &t,ū,l then
0t = else 1i Receiving label
Update S. + S U { (ă,, wt)} and F, +- -
Update a1,..., a and bi.... by such that [a1, b1] x x...(ap. bp] is the smallest rectangle containing the points labelled positive so far. i.e. a; min(x; (xr, 1) S.)
we have only seen labels so far, the algorithm predicts Otherwise, let [ar, bi) x (az, by) x ... X (Ups bp] be the minimal rectangle enclosing the positive examples so far (i.e., the Closure hypothesis). For the next point dt, isn't in the region of disagreement, we predict the agreed-upon label. Otherwise, we check whether there exist at least examples L., < t, for each of which there exists
20

---

a coordinate with Ses E [ a:) U (b,, Rrs] (at most one of these sides is non-empty or sometimes both sides will be empty for some coordinates i). If so, we predict O. Otherwise, we abstain. (The algorithm never predicts in the region of disagreement, similar to the Closure algorithm).
Proof of Theorem 5.4] For any example with target label 1, the algorithm predicts O, there are at least examples Is which each have some coordinate Ra,s that was not in [a;, b.] before the update, but which will have f. in [a,, bi] after the update. For each example f., this can happen at most p times (corresponding to each coordinate) before it will never again be included in future set of examples that convince us to predict O. So we make at most pT' a misclassification on adversarially injected examples. Since the algorithm never predicts 1 unless the true label is 1, we never misclassify a negative example. So it remains only to bound the number of abstentions on the i.ddd examples.
For any n, suppose 2, is the n-th i.i.d. example, and let æi....,ff, 3. be these i..d. examples (so in = ..). & is "attackable" (same to Defiiiitoo C.2 meaning that there some set of examples the adversary could add, knowing &t, to make us abstain) then it must be that either 2; is positive example the region disagreement
the version space induced by the other n points, or else it is negative example such that there are < points T..
for which there exists with Te, E ( a.) U (b,, f...). In particular, in the latter case, it must be that each coordinate has < a examples T, with Fe.s [Fr.a az) ) U (6ī ft,a). where the target concept is [aī, b7] x X (a 67]- This is because the current estimated rectangle will be inside the true rectangle.
We will use exchangeability to bound the probability that S, is attackable by times the number of S.. 8 I n, which would be attackable if they were swapped with é, Among .1..... &, there are at most 2p positive examples in the region of disagreement of the version space induced by the others (namely, the minimum spanning set the positive examples), For each coordinate i, there are at most 2a examples ã., S n, with < other examples Ts in [Ta.i, az) U (b, T..i. (namely, the < a examples with smallest T. such that ã.,i > bi. and the S a examples with largest T.,i such that T,, a.). So there are at most 2ap negative examples I. which would be attackable if they were swapped with Zn.
Altogether there are at most 2p(a + 1) examples ā, which would be attackable if they were swapped with e.. Thus, the probability i.i.d. example ④, is attackable at most 2p(a + 1)/n where n is the number of i.i.d. points seen so far including 2, Summing, the expected number of abstentions
on i.i.d. examples is at most 2p(a + 1) log T. Now setting result.
vT/ log T, gives us the desired
21


Reviews:
[{"review_id": "H8MEkjs91I", "reviewer": "Reviewer_7wBe", "summary": "This paper proposes a pipeline and algorithms for machine learning prediction with abstention. The authors first propose the optimization framework to learn a model which allows abstention. They then consider different distributions and propose different algorithms for the learning process. Their theoretical analysis shows that the algorithms can achieve low error rate for misclassification and abstention.", "questions": "* What will be the practical use case for the abstention framework under the adversarial setting?\n\n* Can the algorithm also be applied to get an abstention model for a non-sequential dataset?", "limitations": "The authors discuss their limitation in their broader impact setup. The paper does not contain potential negative societal impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The paper studies a variety of different contributions. The authors start with one-dimensional threshold scenario and shows the application of the abstention model. Then they provide algorithms for both known distribution and unknown distribution. The latter one is a more difficult setting and the authors provide a generalized algorithm for it based on the former one.\n\n* The paper provides comprehensive error bound for the algorithms. I am not an expert in theoretical ML analysis, but as far as I can tell, the theory part does not contain significant mistakes.", "weaknesses": "* I do not see significant real-world application of the proposed abstention framework with adversarial resilience. The authors mention the case of predicting patient's illness, in which case I understand why the abstention would be necessary. However, I do not see the necessity of caring about the adversarial resilience in such case - is it a (serious) threat that an adversary may launch a clean-label attack when people are training an illness classification task?\n\n* The authors also emphasize the \"sequential prediction\" in addition to the abstention framework and adversarial resilience in the context. I am not fully clear why this is also an important point to consider - can we also apply the proposed pipeline on a static dataset that does not contain a sequential order but also benefits from the abstention pipeline?\n\n* The paper does not contain empirical evaluation of the proposed algorithm, nor does it contain comparison with other works to show how good their bound is.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful review. Here we address the major concerns raised by the reviewer.\n\n\n**Significance of the model in the real-world**:  The key benefit of our model and algorithms is the fact that they produce 'certain' predictions. In particular, the model is correct whenever it predicts despite out-of-distribution or adversarial data. Creating predictors equipped with this guarantee is very desirable in high-stakes applications where incorrect predictions are costly, and we need high-levels of reliability from our models. As for the medical scenario, the out-of-distribution setting is more natural to think about. For example, if our model has seen data mostly from a particular population (say the majority population), then our model is likely to make incorrect predictions on patients not from this population. In such scenarios, it is better for the predictor to abstain than make an incorrect prediction on the minority population. Similar out-of-distribution interactions can occur in other settings such as self-driving cars, chatbots, etc. \n\nFurther, we propose a loss corresponding to our setting given abstention and misclassification. But, our setting is not merely a new loss minimization setting. Since we do not have access to whether the examples the learner has seen are adversarially injected or i.i.d. ($c_t$ is unknown), the algorithm cannot compute its own loss (in particular, the learner cannot compute the abstention error). So the algorithm needs to work without directly knowing its own total loss. This highlights another major challenge of our setting. We believe this more realistically captures OOD and adversarial examples in the real world.\n\n\n**Importance of considering sequential prediction**: Most real-world settings involve interactions with the model, and dynamic decision making, where the environment can change over time. Therefore, it is natural to consider prediction in the sequential setting. On the technical side, this setting is also much more challenging than the offline setting. In our case, the sequential part introduces several challenges: \n- we need to decide to predict or abstain based on only one example \n- the adversary can change their strategy over time adaptively based on our decisions. \n\nThat said, our techniques can be directly applied to a static dataset to achieve similar guarantees. But due to the relative simplicity of the static setting, more direct approaches have been previously studied as described in our related work section under the title “abstension-based learning”. \n\n\n**Comparison to other bounds**: In this work we have proposed a new model, therefore a direct comparison to existing bounds is not possible. As described in the paper, the algorithms designed for the stochastic or worst-case settings do not get non-trivial guarantees in our model. In particular, prior to our work, it was not even clear if we could get any rates better than the Littlestone dimension (which can be infinite even when the VC dimension is finite) in the non-stochastic setting with arbitrarily many adversarial injections. We refer the reviewer to our extensive related work section that compares our results to closely related other work. \n\n\n**Empirical evaluation**: The main focus of our work is mainly theoretical and we believe empirical evaluation distracts from the main message of the paper. Our goal in this paper was to propose a model under which sets a realistic goal on handling adversarial/OOD data and showing the existence of efficient algorithms in this setting. We hope that our work will inspire practitioners to develop practical algorithms using the algorithmic ideas proposed in this work. One particular direction that would be great to explore, would be to use our uncertainty estimation measures based on shattered sets to create heuristics that work for more complex classes such as neural networks.\n\n\n**Practical use of abstention**:  Currently the proposed algorithms are not efficient, however there is hope to create heuristics based on our approaches that could measure the model's uncertainty which would have great practical usage. Even in the setting of adversarial examples (as in vision), equipping the model with abstention would allow us to prevent adversarial attacks which are outside of the perturbation sets we have trained for. Our related work highlights some ways in which this has been used in practice in the static setting."}, {"review_id": "WjNCTeGyB8", "reviewer": "Reviewer_KALR", "summary": "The paper presents a new protocol for beyond-worst-case sequential prediction, incorporating the option of abstention. It introduces two main algorithms: the first achieves an error rate of $O(d^2 \\log T)$ for classes with VC dimension $d$, while the second realizes an error of $O(\\sqrt{T})$ for a specific instance of classes with VC dimension $1$.", "questions": "See Weaknesses.", "limitations": "The authors adequately addressed the limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. An extensive literature search and insightful discussion of prior work spanning a variety of areas. This includes nuanced connection to topics such as beyond-worst-case sequential prediction, abstention-based learning, adversarially robust learning, adversarial examples, testable learning, etc.\n\n2. A new protocol of beyond-worst case sequential prediction with the option of abstention.", "weaknesses": "1. Although the authors propose a new protocol, I struggle to identify novelty, as the primary difference appears to be the relatively straightforward inclusion of an additional abstention option.\n\n2. While new algorithms have been introduced, they are specifically tailored to special classes, thereby limiting the significance of the paper. Why that special case of VC dimension 1 classes is important?\n\n3. The proof techniques presented appear to lack significant novelty. What, then, is the underlying challenge?\n\n4. The phrase \"naturally be extended\" has been referenced multiple times throughout the paper, such as on lines 147-148, 366-367, and 370-371. Firstly, these extensions are not immediately evident, and as such, a more detailed discussion would be beneficial. Secondly, if these extensions are indeed straightforward, including them in the paper could greatly augment its significance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful review. Here we address the major concerns raised by the reviewer.\n\n\n**Novelty of the model**: The inclusion of abstention itself is not sufficient to get any guarantees in this setting. We need the correct notion of regret to accompany this. For instance, an algorithm could just abstain on the entire sequence, but such an algorithm would not be useful. On the other hand, from classical results we know that asking the algorithm to predict always would lead to very pessimistic bounds (could lead to infinite errors even when the VC dimension is 1). Our model balances these two settings to get a beyond-worst case guarantee where the algorithm is required to predict correctly on the i.i.d. examples while allowing free abstention on adversarial/ood examples. This allows us to design algorithms that get similar error bounds to the setting with only i.i.d. examples and non-adversarial examples. Previous models like KWIK could not get such guarantees because they didn't account for an underlying i.i.d. distribution which is natural in several real-world applications.\n\nFurther, we propose a loss corresponding to our setting given abstention and misclassification. But, our setting is not merely a new loss minimization setting. Since we do not have access to whether the examples the learner has seen are adversarially injected or i.i.d. ($c_t$ is unknown), the algorithm cannot compute its own loss (in particular, the learner cannot compute the abstention error). So the algorithm needs to work without directly knowing its own total loss. This highlights another major challenge of our setting. We believe this  more realistically captures OOD and adversarial examples in the real world.\n\n**Focus on particular classes**: Our known distribution algorithm is not tailored to special classes and works for all function classes as long as they have bounded VC dimension (which is a necessary condition for learning even for iid data). Note that the unknown distribution case is significantly more challenging than this as we only have the examples in the past (which may be corrupted) to make the decision for the example at each time, and we do not have any information about what the actual distribution could look like. As noted in the paper, even for the simple class of thresholds, designing an algorithm that works is already non-trivial. Currently, we do not know if this is even possible for general VC classes. Therefore, towards addressing the general question of VC classes, we naturally considered the class of VC dimension 1 (for example, also considered in closely related work by Blum et. al. \"Robust learning under clean-label attack.\" COLT 2021). Note that we also extend the results to axis-aligned rectangles which can have much higher VC dimension. \n\n\n**Novelty of proof technique**: To our knowledge, the proof techniques in the paper are novel. We consider both the algorithm design (keeping track of the higher order shattering) and the analysis (the potential argument analyzing the tradeoff between abstentions and mistakes) as contributions of the paper. We do not know any other paper that uses these. Our algorithm in the known distribution setting is inspired by Hanneke's algorithm for active learning, however, the setting and our analysis differs significantly from theirs. The main challenge in our setting is to identify at each time step whether the example we see is in-distribution or adversarial/OOD. This is an extremely challenging problem given that our sequence so far could also have adversarial corruptions. It is not clear at all if this is even possible. Our algorithms create uncertainty measures by exploiting the structure of the underlying function class and the distribution in a highly non-trivial way, which we believe could have broader impact as a technique for uncertainty quantification for learning. **_Could the reviewer expand on the lack of novelty by pointing us to other works that use similar techniques?_**\n\n\n**Use of \"naturally be extended to\"\"**: We apologize for using this phrase lightly, and will add details of the extensions for each case. Most of the usage of this phrase refers to the model we propose and not the algorithms/proofs. Here we explain these briefly:\n- naturally be extended to the agnostic setting with adversarial/noisy labels\n  - To extend the model to the agnostic setting, we would need to modify the regret to include an additional error term to compare with the best possible error any predictor in the function class could get for the sequence.\n  - To extend to adversarial labels, we just allow the adversary to output any $y_t$\n- naturally be extended to more general forms of prediction such as multiclass classification, partial concept classes, and regression\n  - To extend the model to multiclass classification, we would need to modify the prediction to allow for predicting from a set of $k$-labels and the misclassification loss would need to be modified to penalize error if the predicted label is not the true label\n  - Similarly for regression, we would need to allow prediction to be real-valued and the misclassification loss to be squared loss or the absolute loss. \n  - To extend to partial concept classes, we can keep the model essentially the same with the constraint that the adversary can only inject examples that are consistent with a hidden partial concept, that is, cannot provide an example where the partial concept does not have a label. With this definition, the model allows for more general concepts such as halfspaces with margin while allowing for similar analysis and algorithms.\n"}, {"review_id": "r860yR8Ceu", "reviewer": "Reviewer_cSg3", "summary": "This paper proposes a sequential prediction setting in which an adversary injects adversarial examples with clean labels, and the algorithm is allowed to abstain from predicting. This setting lies between the stochastic and the fully adversarial settings, which are known to be characterized by the VC and Littlestone dimensions of the hypothesis class.\n\nThe paper mainly proves the following two learning performance guarantees stated in terms of the VC dimension. (The algorithm incurs a unit loss whenever it outputs an incorrect label, or it abstains on a clean data poiunt.)\n- An $O(d^2\\log T)$ upper bound on the number of mistakes, where $d$ is the VC dimension and $T$ is the time horizon. This result requires the access to the marginal data distribution.\n- An $O(\\sqrt{T})$ error bound for the $d = 1$ case, without access to marginal distributions.", "questions": "Following up on the second point in the weakness part: To run Algorithm 1 using unlabeled examples from $\\mathcal{D}$, it seems that we need an estimation of $\\rho_k$ up to an $O(\\alpha_k) = O(T^{-k})$ additive error, which in turn requires $T^{\\Omega(d)}$ samples when $k = d$. Is there a more efficient way of using unlabeled examples, or would you conjecture that such a dependence is likely to be necessary?", "limitations": "This work is purely theoretical and the limitations are the assumptions that underlie the problem setting as well as the theoretical results. These were addressed in the \"Broader Impact\" section in the paper.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper defines a new setting of sequential prediction that models the power of abstention against clean-label attacks (e.g., adversarial examples). I found the setting well-motivated and the technical material beautifully presented. The authors identified various future directions of work on this model as well as potential connection to the learning theory literature.\n\nDespite the weaknesses discussed below, I (weakly) lean towards accepting this submission.", "weaknesses": "- The error bounds are likely to be rather loose in terms of both $d$ and $T$.\n- The assumption on having *perfect* access to the marginal data distribution is arguably too strong. While the approach should still work if the access to $\\mathcal{D}$ is replaced with (unlabeled) samples from $\\mathcal{D}$, the sample complexity would likely be $T^{\\Omega(d)}$; see questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful review. Here we address the questions/weaknesses pointed out by the reviewer.\n\n\n**Looseness of the bounds**: For the known distribution setting, this is only loose by a factor of $d$ compared to the fully stochastic setting with no adversarial/OOD data. Since our algorithm needs to also handle adversarial/OOD data, it is not clear if this can be matched. For the unknown marginal setting, we do not yet know if it is possible for general VC classes. Hence, we do not know what the regret is likely to be in these settings\n\n\n**Knowledge of distribution**: Yes, we agree that this assumption is very strong. However, even under this assumption, it is not obvious how to solve the problem since the algorithm needs to decide \"in-sample\" vs \"out of sample\" using only a single sample at test time and corrupted training samples. The only setting where we can remove the assumptions are the special cases of VC dimension 1 classes, and axis-aligned rectangles. Furthermore, our work follows a long tradition of work in the TCS and learning theory literature that construct learning algorithms under known marginal distribution. In fact, a considerable fraction of the literature on computational learning theory focuses on narrower assumptions such as the marginal known to be Gaussian or uniform on the Hypercube.\n\n\n**Efficient use of unlabelled samples**: The reviewer correctly points out that the current algorithm would require a very large number of samples $T^{O(d)}$ to be able to get accurate enough estimates for the algorithm to work. We do not yet know of a way to make use of the unlabelled samples more efficiently. Recall that given $n$ i.i.d. samples, we can construct ${n \\choose k} = O(n^k)$, $k$-tuples, so there is some hope that we do not necessarily need $T^{O(d)}$ samples if we can show stronger concentration using dependent sampling. However, it is not clear to us if this is possible in general. Perhaps, at the cost of a worse dependence on $T$ (like in our unknown distribution setting) we could get away with less accurate approximations of the shattering probabilities."}, {"review_id": "kNB9DHXpzQ", "reviewer": "Reviewer_mVCw", "summary": "The authors study online learning under clean-label attacks. Since it is online learning, such attacks can be seen both as poisoning as well as evasion (adversarial examples). In this direction the authors propose the use of abstention when the classifier is not confident for a prediction and along these lines the main contribution is the introduction of a new loss function that penalizes abstention on non-adversarial examples but not on adversarial examples. The authors give an error (regret) bound of $O(d^2\\log T)$ ) for classes with VC dimension d for time horizon T, assuming access to the marginal distribution over the iid examples. This bound is off by a factor of $d$ from the situation where it is known that data are coming iid from some fixed distribution but at the same time the authors allow clean-label attacks which essentially alter the distribution. Finally, the authors also give a $O(\\sqrt{T})$ bound for concept classes of VC dimension 1 but without any access to the marginal distribution over the iid examples.\n\nAfter the rebuttal:\n\nWe had an interesting discussion during the rebuttal period and I am happy to see the authors will be integrating the feedback from the reviewers and improve the final version of the paper. Therefore I am increasing the score on soundness and presentation from 2 to 3 and the overall rating of the paper from 3 (reject) to 6 (weak accept). Thank you for a very interesting paper!", "questions": "Q1. What is the relevance of adversarial examples and poisoning attacks to medical applications? How is this line of work motivated for both kinds of attacks?\n\nQ2. Going one step further, what is the motivation for studying such methods as the ones you analyze in the paper?\n\nQ3. Can the functions in $F$ be randomized?\n\nQ4. What is the difference between the functions 1{$\\ldots$} (line 152) and I{$\\ldots$} in lines 295 and 301?\n\nQ5. Is there an updated version of the loss function that you propose?\n\nQ6. Line 317: \"... the class is restricted ...\". What class? \n\nQ7. How tight are the bounds with respect to some actual datasets that motivate this line of work (e.g., from the medical domain that is mentioned)?", "limitations": "I would prefer to see a clearly separated paragraph somewhere near the end of the paper indicating clearly what the limitations of the proposed approach are as well as to see some experiments with real data that show how close the bounds are to reality in situations that have motivated this line of research.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is studying sequential prediction while the training examples can be poisoned in the sense that they are not drawn iid from some underlying distribution but otherwise respect the ground truth. This model of learning is somewhere between traditional machine learning where the learner has access to iid examples and online learning where the learners are studied under worst-case sequences of examples that are presented to the learners. The authors study the situation of sequential prediction, which is a term hardly found anywhere online and they never define in the text, but apparently has to do with the fact of studying machine learning algorithms that make predictions as they still learn from data (e.g., perceptron); the catch is to what extent the sequence of data can be adversarial and in this sense the authors allow perhaps the most adversarial of sequences. I believe this is an interesting problem though it is unclear how important this problem is, if it arises in the actual world, and where the motivation is coming from. The paper is sometimes well-written and sometimes not. Hence, there are issues both with the significance of the results and with the clarity.\n\nI like and appreciate the concluding section with ideas for future work and a clearly-separated paragraph on broader impact. However, the authors do not have a similarly marked paragraph listing the limitations of their work.", "weaknesses": "I think the paper has good potential, but it is not quite polished yet.\n\nSeveral definitions are missing or are confusing in the paper. Examples follow:\n\n- Sequential prediction is never defined as a concept.\n\n- Learning in the realizable case vs proper learning: in line 28 you define the hypothesis class $F$ and in lines 133-134 you indicate that labeling occurs according to some function in $F$. This is actually proper learning, which is a special case of learning in the realizable case.\n\n- In line 135 you forget to mention that you define what a version space is (and cite Mitchell) but you go ahead and use this notion in lines 255 and 269 (and perhaps elsewhere).\n\n- Littlestone dimension is mentioned but is never defined (not even in the appendix) and no example is actually given.\n\n- In lines 186-190: What is the relationship between $n$ and $T$? Does $n$ refer to unique examples, or does it allow potential repetitions and is thus the full number of draws from the (potentially adversarial) distribution?\n\n- One of the main contributions of the paper is the new loss function that penalizes the learning algorithm when when it abstains on non-adversarial data but does not penalize the learner on adversarial data. This is captured with the equation on display in line 152 where we see that the total error that the learner suffers over the sequence of the first T examples is decomposed to misclassification error and abstention error. Since the characteristic function (I assume that is what 1{$\\ldots$} is) is never defined, I understand from the misclassification error that the learning algorithm should receive a penalty of 1 every time it abstains since $\\hat{y}_t \\neq 1 - f^*(x_t)$. However, in Proposition 3.1 the learning algorithm abstains to predict in the disagreement region and the claim is that it has misclassification error equal to 0. However, I have no idea how this follows from the equation that is put on display in line 152.\n\n- In Protocol 1, two lines before the end you claim that the learner receives $x_t$ but earlier, in lines 143-144 it is clear that the learner receives $\\hat{x}_t$. \n\nNear the end the paper becomes more dense and while I appreciate that the authors are attempting to enhance the presentation by leaving the proofs in the appendix (thank you) there are still situations where there is ambiguity (e.g., in Theorem 5.1, is the \"corruption model with abstentions\" something new?)\n\nIn line 248 \"As we saw earlier...\" -> Perhaps explicitly number the particular example and refer to that with a number?\n\nAs a last remark, I am not sure if NeurIPS is the appropriate venue for this line of work. I do not believe it is.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review. We will promptly fix typographical errors in a revision. Here we address the major concerns/questions from the reviewer.\n\n**Proper versus realizable**: Realizability and properness are somewhat orthogonal desiderata in learning theory. Realizability is a requirement on _learning instances_ and implies that there is a function in the class that exactly fits the labels from the training set (potentially presented in a sequential manner). Properness is required from the _learning algorithm_ and implies that the algorithm uses a function from the class to make its predictions. These two requirements do not enforce each other in any way. For example, optimal learning algorithms even in the realizable setting may need to be improper and there are settings, such as learning in games, where the instance is not realizable yet a proper algorithm is desired.\n\n**Definitions and notation**: We apologize for this omission of definition of some terms such as sequential prediction and version space that we believe are standard nomenclature in learning theory. We will include formal definitions to improve readability. \n\n**Relationship between $n$ and $T$**: In that paragraph, $n$ is used to refer to the number of samples that are not corrupted while $T$ is used to refer to the total number of samples. In general, $n \\leq T$ (could take any value in $\\lbrace 0, 1, \\ldots, T\\rbrace$) but the algorithm does not have access to $n$ and we can only use it in the analysis. We also comment that the i.i.d. samples could in fact have repetitions. \n\n**Notion of error**: We recall that we use the characteristic function in the standard way i.e. to be the function that outputs one when the condition in the input is satisfied and zero when the condition is not satisfied. Note that the notion of misclassification error is $\\sum_i 1( \\hat{y_t} = 1 - f(x_t) )$. This means that the algorithm suffers an error of one exactly when it does **not** abstain and predict the opposite label. For example, when $\\hat{y_t} = \\bot$ the algorithm does not suffer a misclassification error as $\\hat{y_t} \\neq 1 - f(x_t)$. In particular, when the algorithm abstains in the disagreement region, it does not make a prediction and does not suffer a misclassification error.\n\n**Limitations**: Thank you for your suggestion, we will add a clearly marked paragraph highlighting the limitations of our current model and approaches.\n\n**Appropriateness for Neurips**: We strongly disagree with this. Just as evidence for this, related paper working on similar setups (generally on beyond worst case analysis of sequential prediction) have appears in previous editions of NeurIPS: \n- Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples NeurIPS 2020 (oral) \n- On optimal learning under targeted data poisoning NeurIPS 2022 \n- Oracle-eﬃcient online learning for beyond worst-case adversaries NeurIPS 2022 (oral)\n- Towards optimally abstaining from prediction with OOD test examples NeurIPS 2020 \n\n**Responses to Questions**:\n\nQ1&2. As we mentioned in the introduction, our model captures both data poisoning and OOD example. The key benefit of our model and algorithms is the fact that they produce 'certain' predictions. In particular, the model is mostly correct whenever it predicts despite out-of-distribution or adversarial data. Creating predictors equipped with this guarantee is very desirable in high-stakes applications where incorrect predictions are costly, and we need high-levels of reliability from our models. As for the medical scenario, the OOD setting is more natural. For example, if our model has seen data mostly from a particular population (say the majority population), then our model is likely to make incorrect predictions on patients not from this population. In such scenarios, it is better for the predictor to abstain than make an incorrect prediction on the minority population. Similar OOD interactions can occur in other settings such as self-driving cars, chatbots, etc.\n\nQ3. We assume that the functions in $F$ are deterministic functions. But since the learning occurs in a sequential manner, the adversary can pick functions (in potentially a randomized manner) as long as they are consistent with the data (that is, the function matches the labels seen so far). One can also incorporate functions such that the label is random given the input but this is usually studied in the agnostic setting (not realizable). Most results in learning theory are first proven for the realizable case and the general agnostic case is solved via reduction to the realizable one. Our paper can be seen as putting forth the first step.\n\nQ4. We use both $1$ and $I$ to both mean the indicator function. We will fix this in the revision. \n\nQ5. We propose a loss corresponding to our setting given by the equation in line 152. But, we believe that thinking of our setting directly in terms of loss minimization is not fruitful. Since we do not have access to whether the examples the learner has seen are adversarially injected or i.i.d. ($c_t$ is unknown), the algorithm cannot compute its own loss (in particular, the learner cannot compute the abstention error). This highlights another major challenge of our setting. \n\nQ6. Here by the class, we mean the class with respect which we are learning, referred to as $\\mathcal{F}$ in the paper\n\nQ7. The focus of our work is mainly theoretical. Our goal in this paper was to propose a model under which sets a realistic goal on handling adversarial/OOD data and showing the existence of efficient algorithms in this setting. We hope that our work will inspire practitioners to develop practical algorithms using the algorithmic ideas proposed in this work. For example, our uncertainty estimation measures based on shattered sets can be used to create heuristics that work for classes such as neural networks."}]

Author rebuttal:

Meta-review: The paper presents a sequential prediction problem that allows the option of abstention, where an attacker can inject clean-label adversarial examples. It introduces two algorithms with associated error bounds; in one the error scales with the VC dimension of the hypothesis class. The reviews are all on the positive side, if not all strongly, after a very healthy amount of discussion and response. 
.
Decision: Accept (poster)