{'fraction_non_alphanumeric': 0.05972318854984594, 'fraction_numerical': 0.013629360898519034, 'mean_word_length': 3.7853151010701547, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Robustly-reliable learners under poisoning attacks

Data poisoning attacks, in which an adversary corrupts a training set with the goal of inducing specific desired mistakes, have raised substantial concern: even just the possibility of such an attack can make a user no longer trust the results of a learning system. In this work, we show how to achieve strong robustness guarantees in the face of such attacks across multiple axes. We provide robustly-reliable predictions, in which the predicted label is guaranteed to be correct so long as the adversary has not exceeded a given corruption budget, even in the presence of instance targeted attacks, where the adversary knows the test example in advance and aims to cause a specific failure on that example. Our guarantees are substantially stronger than those in prior approaches, which were only able to provide certificates that the prediction of the learning algorithm does not change, as opposed to certifying that the prediction is correct, as we are able to achieve in our work. Remarkably, we provide a complete characterization of learnability in this setting, in particular, nearly-tight matching upper and lower bounds on the region that can be certified, as well as efficient algorithms for computing this region given an ERM oracle. Moreover, for the case of linear separators over logconcave distributions, we provide efficient truly polynomial time algorithms (i.e., non-oracle algorithms) for such robustly-reliable predictions. We also extend these results to the active setting where the algorithm adaptively asks for labels of specific informative examples, and the difficulty is that the adversary might even be adaptive to this interaction, as well as to the agnostic learning setting where there is no perfect classifier even over the uncorrupted data.


Introduction
Overview: There has been significant interest in machine learning in recent years in building robust learning systems that are resilient to adversarial attacks, either test time attacks (Goodfellow et al., 2015;Carlini and Wagner, 2017;Madry et al., 2018;Zhang et al., 2019) or training time attacks (Steinhardt et al., 2017;Shafahi et al., 2018) also known as data poisoning. A lot of the effort on providing provable guarantees for such systems has focused on test-time attacks (e.g., Yin et al., 2019;Attias et al., 2019;Montasser et al., 2019Montasser et al., , 2021Goldwasser et al., 2020), and the question of understanding what is fundamentally possible or not under training time attacks or data poisoning is wide open (Barreno et al., 2006;Levine and Feizi, 2021).
In data poisoning attacks, an adversary corrupts a training set used to train a learning algorithm in order to induce some desired behavior. Even just the possibility of such an attack can make a user no longer trust the results of a learning system. Particularly challenging is the prospect of providing formal guarantees for instance targeted attacks, where the adversary has a goal of inducing a mistake on specific instances; the difficulty is that the learner does not know which instance the adversary is targeting, so it must try to guard against attacks for essentially every possible instance. In this work, we devolop a general understanding of what robustness guarantees are possible in such cases while simultaneouly analyzing multiple important axes: • Instance targeted attacks: The adversary can know our test example in advance, applying its full corruption budget with the goal of making the learner fail on this example, and even potentially change its corruptions from one test example to another.
• Robustly-reliable predictions: When our algorithm outputs a prediction y with robustness level η, this is a guarantee that y is correct so long as the target function belongs to the given class and the adversary has corrupted at most an η fraction of the training data. For any value η, we analyze for which points it is possible to provide a prediction with such a strong robustness level; we provide both sample and distribution dependent nearly matching upper and lower bounds on the size of this set, as well as efficient algorithms for constructing it given access to an ERM oracle. We note that our guarantees are substantially stronger than those in prior work, which were only able to provide certificates of stability (meaning that the prediction of the algorithm does not change), rather than correctness. This is much more desirable because it implies that our predictions can truly be trusted.
• Active learning against adaptive adversaries: We also address the challenging active learning setting where the labeled data is expensive to obtain, but the learning algorithm has the power to adaptively ask for labels of select examples from a large pool of unlabaled examples in order to learn accurate classifiers with fewer labeled examples. While this interaction could save labels, it also raises the concern that the adversary could generate a lot of harm by adaptively deciding which points to corrupt based on choices of the algorithm. We provide algorithms that not only learn with fewer labeled examples, but are able to operate against such adaptive adversaries that can make corruptions on the fly.
• Agnostic learning: Providing a reasonable extension to the agnostic case where there is no perfect classifier even over the uncorrupted data.
While prior work has considered some of these aspects separately, we provide the first results that bring these together, in particular combining reliable predictions with instance-targeting poisoning attacks. We also provide nearly-tight upper and lower bounds on guarantees achievable, as well as efficient algorithms.
Our Results: Instance targeted data poisoning attacks have been of growing concern as learned classifiers are increasingly used in society. Classic work on data poisoning attacks (e.g., Valiant (1985); Kearns and Li (1993); Bshouty et al. (2002); Awasthi et al. (2017)) only considers non-instance-targeted attacks, where the goal of the adversary is only to increase the overall error rate, rather than to cause errors on specific test points it wishes to target. Instance targeted poisoning attacks, on the other hand, are more challenging but they are particularly relevant for modern applications like recommendation engines, fake review detectors and spam filters where training data is likely to include user-generated data, and the results of the learning algorithm could have financial consequences. For example, a company depending on a recommendation engine for advertisement of its product has an incentive to cause a positive classification on the product it produces or to harm a specific competitor. To defend against such adversaries, we would like to provide predictions with instance-specific correctness guarantees, even when the adversary can use its entire corruption budget to target those instances. This has been of significant concern and interest in recent years in machine learning.
In this work we consider algorithms that provide robustly-reliable predictions, which are guaranteed to be correct under well-specified assumptions even in the face of targeted attacks. In particular, given a test input x, a robustly-reliable classifier outputs both a prediction y and a robustness level η, with a guarantee that y is correct unless one of two bad events has occurred: (a) the true target function does not belong to its given hypothesis class H or (b) an adversary has corrupted more than an η fraction of the training data. Such a guarantee intrinsically has in it a notion of targeting, because the prediction is guaranteed to be correct even if the adversarial corruptions in (b) were designed specifically to target x. Note that it is possible to produce a trivial (and useless) robustly-reliable classifier that always outputs η < 0 (call this "abstaining" or an "unconfident prediction"). We will want to produce classifiers that, as much as possible, instead output confident predictions, that is, predictions with large values of η. This leads to several kinds of guarantees one might hope for, because while the adversary cannot cause the algorithm to be incorrect with a high confidence, it could potentially cause the classifier to produce low-confidence predictions in a targeted way.
In this work, we demonstrate an optimal robustly-reliable learner L, and precisely identify the guarantees that can be acheived in this setting, with nearly matching upper and lower bounds. Specifically, • We prove guarantees on the set of test points for which the learner will provide confident predictions, for any given adversarial corruption of the training data (Theorem 3.1), or even more strongly, for all bounded instance-targeted corruptions of the training set (Theorem 3.3). Intuitively speaking, we show that the set of points on which our learner should be confident are those that belong to the region of agreement of low error hypotheses. Our learner shows more confidence for points in the agreement regions of larger radii around the target hypothesis. We also show how L may be implemented efficiently given an ERM oracle (Theorem 3.2) by running the oracle on datasets where multiple copies of the test point are added with different possible labels. We further provide empirical estimates on the set of such test points (Theorem 3.4), which could help determine if the learner is ready to be fielded in a highly adversarial environment.
• We provide fundamental lower bounds on which test points a robustly-reliable learner could possibly be confident on (Theorems 3.5 and 3.6). We do this through characterizing the set of points an adversary could successfully attack for any learner, which roughly speaking is the region of disagreement of low error classifiers. Intuitively speaking, ambiguity about which the original dataset is leads to ambiguity about which low error classifier is the target concept so we cannot predict confidently on any point in the region of disagreement among these low error concepts. Our upper bound in Theorem 3.3 and lower bound in Theorem 3.5 exactly match, and imply that our learner L is optimal in its confident set.
• For learning linear separators under logconcave marginal distributions, we show a polynomial time robustlyreliable learning algorithm under instance-targeted attacks produced by a malicious adversary (Valiant, 1985) (see Theorem 4.1). The key idea is to first use the learner from the seminal work of Awasthi et al. (2017) (that was designed for non-targeted attacks) to first find a low error classifier and then to use that and the geoemetry of the underlying data distribution in order to efficiently find a good approximation of the region of agreement of the low error classifiers. We also show that the robust-reliability region for this algorithm is near-optimal for this problem, even ignoring computational efficiency issues (Theorem 4.2).
• We also study active learning, extending the classic disagreement-based active learning techniques, to achieve comparable robust reliability guarantees as above, but with reduced number of labeled examples (Theorems 5.3, 5.1), even when an adversary can choose which points to corrupt in an adaptive manner (Theorem 5.1). This is particularly challenging because the adversary can use its entire corruption budget on only those points whose labels are specifically requested by the learner.
• Finally, we generalize our results to the agnostic case where there is no perfect classifier even over the uncorrupted data (Theorems 6.1, 6.2, 6.3, and 6.5). In this case, the adversary could cause a robustly-reliable learner to make a mistake, but only if every low-error hypothesis in the class would have also made a mistake on that point as well.

Related Work
Non-instance targeted poisoning attacks. The classic malicious noise model introduced in (Valiant, 1985) and subsequently analyzed in (Kearns and Li, 1993;Bshouty et al., 2002;Klivans et al., 2009;Awasthi et al., 2017) provides one approach to modeling poisoning attacks. However the malicious noise model only captures untargeted attacks -formally the adversary's goal is to maximize the learner's overall error rate. Instance targeted poisoning attacks. Instance-targeted poisoning attacks were first considered by Barreno et al. (2006). Shafahi et al. (2018) and  showed empirically that such targeted attacks can be powerful even if the adversary adds only correctly-labeled data to the training set (called "clean-label attacks"). Targeted poisoning attacks have generated significant interest in recent years due to the damage they can cause to the trustworthiness of a learning system (Mozaffari-Kermani et al., 2014;Chen et al., 2017;Geiping et al., 2020). Past theoretical work on defenses against instance-targeted poisoning attacks has generally focused on producing certificates of stability, indicating when an adversary with a limited budget could not have changed the prediction that was made. For example, Levine and Feizi (2021) propose partitioning training data into k portions, training separate classifiers on each portion, and then using the strength of the majority-vote over those classifiers as such a certificate (since any given poisoned point can corrupt at most one portion). Gao et al. (2021) formalize a wide variety of different kinds of adversarial poisoning attacks, and analyze the problem of providing certificates of stability against them in both distribution-independent and distributionspecific settings. In contrast to those results that certify when a budget-limited adversary could not change the learner's prediction, our focus is on certifying that the prediction made is correct. For example, a learner that always outputs the "all-negative" classifier regardless of the training data would be a certifying learner in the sense of Gao et al. (2021) (for an arbitrarily large attack budget) and its correctness region would be the probability mass of true negative examples. In contrast, in our model, outputting a prediction (y, η) means that y is guaranteed to be a correct prediction so long as the adversary corrupted at most an η fraction of the training data and the target belongs to the given class; so, a learner that always outputs (y, η) for y = −1 and η ≥ 0 would not be robustly-reliable in our model (unless the given class only had the all-negative function). We are the first to consider such strong correctness guarantees in the presence of adversarial data poisoning.
Interestingly, for learning linear separators, our results improve over those of Gao et al. (2021) even for producing certificates of stability, in that our algorithms in run polynomial time and apply to a much broader class of data distributions (any isotropic log-concave distribution and not only uniform over the unit ball). Blum et al. (2021) provide a theoretical analysis for the special case of clean-label poisoning attacks (Shafahi et al., 2018;. They analyze the probability mass of attackable instances for various algorithms and hypothesis classes. However, they do not consider any form of certification or reliability guarantees. Reliable useful learners. Our model can be viewed as a broad generalization of the perfect selective classification model of El-Yaniv and Wiener (2012) and the reliable-useful learning model of Rivest and Sloan (1988), which only consider the much simpler setting of learning from noiseless data, to the setting of noisy data and adversarial poisoning attacks.

Formal Setup
Setup. Let D denote a data distribution over X × Y, where X is the instance space and Y = {0, 1} is the label space. Let H ⊂ Y X be the concept space. We will primarily assume the realizable case, that is, for some h * ∈ H, for any (x, y) in the support supp(D) of the data distribution D, we have y = h * (x) (we extend to the non-realizable case in Section 6). We will use D X to denote the marginal distribution over X of unlabeled examples. The learner L has access to a corruption S of a sample S ∼ D m , and is expected to output a hypothesis h L(S ) ∈ Y X (proper with respect to H if h L(S ) ∈ H). We will use the 0-1 loss, For a fixed (possibly corrupted) sample S , let err S (h) denote the average empirical loss for hypothesis h, i.e. err S (h) = 1 . For a sample S, let H η (S) = {h ∈ H | err S (h) ≤ η} be the set of hypotheses in H with at most η error on S. Similarly for any distribution D, let H η (D) = {h ∈ H | err D (h) ≤ η}. We will consider a class of attacks where the adversary can make arbitrary corruptions to up to an η fraction of the training sample S. If the adversary can also choose which examples to attack, it corresponds to the nasty attack model of Bshouty et al. (2002). We formalize the adversary below. Adversary. Let d(S, S ) = 1 − |S∩S | m ∈ [0, 1] denote the normalized Hamming distance between two samples S, S with m = |S| = |S |. Let A(S) denote the sample corrupted by adversary A. For η ∈ [0, 1], let A η be the set of adversaries with corruption budget η and A η (S) = {S | d(S, S ) ≤ η} denotes the possible corrupted training samples under an attack from an adversary in A η . Intuitively, if the given sample is S , we would like to give guarantees for learning when S ∈ A η (S) for some (realizable) uncorrupted sample S. Also we will use the convention that A η (S) = {} for η < 0 to allow the learner to sometimes predict without any guarantees (cf. Definition 1). Note that the adversary can change both x and y in an example (x, y) it chooses to corrupt, and can arbitrarily select which η fraction to corrupt as in Bshouty et al. (2002).
We now define the notion of a robustly-reliable learner in the face of instance-targeted attacks. This learner, for any given test example x, outputs both a prediction y and a robust reliability level η x , such that y is guaranteed to be correct so long as h * ∈ H and the adversary's corruption budget is ≤ η x . This learner then only gets credit for predictions guaranteed to at least a desired value η.
Definition 1 (Robustly-reliable learner). A learner L is robustly-reliable for sample S w.r.t. concept space H if, given S , the learner outputs a function L S : X → Y × R such that for all x ∈ X if L S (x) = (y, η) and if S ∈ A η (S) for some sample S labeled by concept h * ∈ H, then y = h * (x). Note that if η < 0, then A η (S) = {} and the above condition imposes no requirement on the learner's prediction. If L S (x) = (y, η) then let h L(S ) (x) = y.
Given sample S labeled by h * , the η-robustly-reliable region RR L (S, h * , η) for learner L is the set of points x ∈ X for which given any S ∈ A η (S) we have that L S (x) = (y, η ) with η ≥ η. More generally, for a class of adversaries A with budget η, RR L A (S, h * , η) is the set of points x ∈ X for which given any S ∈ A(S) we have that L S (x) = (y, η ) with η ≥ η. We also define the empirical η-robustly-reliable region Remark 1. The requirement of security even to targeted attacks appears in two places in Definition 1. First, if a robustly-reliable learner outputs (y, η) on input x, then y must be correct even if an η fraction of the training data had been corrupted specifically to target x. Second, for a point x to be in the η-robustly-reliable region, it must be the case that for any S ∈ A η (S) (even if S is a targeted attack on x) we have L S (x) = (y, η ) for some η ≥ η. So, points in the η-robustly-reliable region are points an adversary cannot successfully target with a budget of η or less.
Definition 1 describes a robustly-reliable learner for a particular (corrupted) sample. We now extend this to the notion of a learner being robustly reliable with high probability for an adversarially-corrupted sample drawn from a given distribution.
Definition 2. A learner L is a (1 − γ)-probably robustly-reliable learner for concept space H under marginal D X if for any target function h * ∈ H, with probability at least 1 − γ over the draw of S ∼ D m (where D is the distribution over examples labeled by h * with marginal D X ), for all S ∈ A η (S), and for all x ∈ X , if L S (x) = (y, η ) for η ≥ η then y = h * (x). If L is a (1 − γ)-probably robustly-reliable learner with γ = 0 for all marginal distributions D X , then we say L is strongly robustly-reliable for H. Note that a strongly robustly-reliable learner is a robustly-reliable learner in the sense of Definition 1 for every sample S .
The η-robustly-reliable correctness for learner L for sample S labeled by h * is given by the probability mass of the robustly-reliable region, RobC L (D, η, S) = Pr x∼D X [x ∈ RR L (S, h * , η)].
In our analysis we will also need several key quanntities -agreement/disagreement regions and the disagreement coefficient -that have been previously used in the disagreement-based active learning literature (Balcan et al., 2006;Hanneke, 2007;Balcan et al., 2009). The disagreement coefficient, θ , of H with respect to h * over D is given by

Robustly Reliable Learners for Instance-Targeted Adversaries
We now provide a general strongly robustly-reliable learner using the notion of agreement regions (Theorem 3.1) and show how it can be implemented efficiently given access to an ERM oracle for H (Theorem 3.2). We then prove that its robustly reliable region is pointwise optimal (contains the robustly reliable regions of all other such learners), for all values of the adversarial budget η (Theorems 3.3 and 3.5). Recall that a strongly robustly-reliable learner L is given a possibly-corrupted sample S and outputs a function L S such that if L S = (y, η) and S = A η (S) for some (unknown) uncorrupted sample S labeled by some (unknown) target concept h * ∈ H, then y = h * (x).
Theorem 3.1. Let H η (S ) = {h ∈ H | err S (h) ≤ η}. For any hypothesis class H, there exists a strongly robustly-reliable learner L that given S outputs a function L S such that RR L (S , η) ⊇ Agree(H η (S )).
Proof. Given sample S , the learner L outputs the function L S (x) = (y, η) where η is the largest value such that x ∈ Agree(H η (S )), and y is the common prediction in that agreement region; if x ∈ Agree(H η (S )) for all η ≥ 0, then L S (x) = (⊥, −1). This is a strongly robustly-reliable learner because if L S (x) = (y, η) and S ∈ A η (S), then h * ∈ H η (S ), so y = h * (x). Also, by design, all points in Agree(H η (S )) are given a robust reliability level at least η.
We now show how the strongly robustly-reliable learner L from Theorem 3.1 can be implemented efficiently given access to an ERM oracle for class H.
Theorem 3.2. Learner L from Theorem 3.1 can be implemented efficiently given an ERM oracle for H.
Proof. Given sample S and test point x, for each possible label y ∈ Y the learner first computes the minimum value y of the empirical error on S achievable using h ∈ H subject to h(x) = y; that is, This can be computed efficiently using an ERM oracle by simply running the oracle on a training set consisting of S and m + 1 copies of the labeled example (x, y) where m = |S |; this will force ERM to produce a hypothesis h such that h(x) = y. Now if 0 = 1 , then this means that x ∈ Agree(H η (S )) for any value η for which H η (S ) is nonempty, so the algorithm can output (⊥, −1). Otherwise, the algorithm can output the label y = argmin y { y } and η = max{ 0 , 1 } − 1/m. Specifically, by definition of y , this is the largest value of η such that x ∈ Agree(H η (S )).
We now analyze the η-robustly-reliable region for the algorithm above (Theorems 3.3 and 3.4) and prove that it is optimal over all strongly robustly-reliable learners (Theorem 3.5). Specifically, Theorem 3.3 provides a guarantee on the size of the η-robustly-reliable region in terms of properties of h * and S, and then Theorem 3.4 gives an empirically-computable bound. Thus, these indicate when such an algorithm can be fielded with confidence even in the presence of adversaries that control an η fraction of the training data and can modify them at will. Theorem 3.3. For any hypothesis class H, the strongly robustly-reliable learner L from Theorem 3.1 satisfies the property that for all S and for all η ≥ 0, Moreover, if S ∼ D m then with probability 1 − δ, Agree(B H S (h * , 2η)) ⊇ Agree(B H D (h * , 2η + )) for m = O( 1 2 (d + ln 1 δ )). So, whp, RR L (S, h * , η) ⊇ Agree(B H D (h * , 2η + )). Here d = VCdim(H).
The set RR L (S, h * , η) = ∩ S ∈Aη(S) RR L (S , η) therefore contains S ∈Aη(S) where the above equality holds because if h ∈ B H S (h * , 2η) then there exists S ∈ A η (S) such that h ∈ H η (S ), and if h ∈ H η (S ) for some S ∈ A η (S) then h ∈ B H S (h * , 2η). Finally, by uniform convergence (Anthony and Bartlett (2009) Remark 2 (Linear separators for uniform distribution over the unit ball). The above agreement region can be fairly large for the well-studied setting of learning linear separators under the uniform distribution D over the unit ball in R d , or more generally when the disagreement coefficient (Hanneke (2007)) is bounded.
Since the disagreement coefficient is known to be at most π √ d in this setting (Hanneke (2007)), we have that . For example, if 1% of our data is poisoned and our dataset is large enough so that = 0.1%, even for d = 9 we are confident on over 80% of the points. We illustrate the relevant agreement region for linear separators in Figure 1. We can also obtain (slightly weaker) empirical estimates for the size of the robustly-reliable region for the learner L from Theorem 3.1. Such estimates could help determine when the algorithm can be safely fielded in an adversarial environment. For example, in federated learning, if an adversary controls processors that together hold an η fraction of the training data, and can also cause the learning algorithm to re-run itself at any time, then this would allow one to decide if a low abstention rate can be guaranteed or if additional steps need to be taken (like collecting more training data, or adding more security to processors).
Theorem 3.4. For any hypothesis class H, the strongly robustly-reliable learner L from Theorem 3.1 satisfies the property that for all S, for all η ≥ 0 and for all S ∈ A η (S), , which together with Theorem 3.3 implies the first claim. Indeed h ∈ B H S (h * , 2η) implies that err S (h) ≤ 2η and therefore err S (h) ≤ 3η. Also, if err S (h) ≤ 3η, then h ∈ B H S (ĥ, 4η) since err S (ĥ) ≤ η again using the triangle inequality, which implies the second claim.
It turns out that the bound on the robustly-reliable region from Theorem 3.3 is essentially optimal. We can show the following lower bound on the ability of any robustly-reliable learner for any hypothesis class H to be confident on any point in Agree(B H S (h * , 2η)). Our upper and lower bounds extend the results of Gao et al. (2021) for learning halfspaces over the uniform distribution to general hypothesis classes and any distribution with bounded region of disagreement.
Theorem 3.5. Let L be a strongly robustly-reliable learner for hypothesis class H. Then for any h * ∈ H and any sample S, any point in the η-robustly-reliable region must lie in the agreement region of Next, let S X be the points in S with labels removed, and let S A denote a labeling of S X such that exactly half the points in ∆ S = {x ∈ S X | h (x) = h * (x)} are labeled according to h * (the remaining half using h , for convenience assume |∆ S | is even). Notice that sample . Thus, L is not a strongly robustly-reliable learner and we have a contradiction. Finally We can also extend the above result to (1 − γ)-probably robustly-reliable learners, as follows.
Theorem 3.6. Let L be a (1 − γ)-probably robustly-reliable learner for hypothesis class H under marginal D X . For any h * ∈ H, given a large enough sample size m = |S| ≥ c 2 ln 1 δ , we have where c is an absolute constant and D is the distribution with marginal D X consistent with h * .
where D is a data distribution with the same marginal as D but consistent with h . We now consider three bad events of total probability at most 2γ + δ: Indeed events (A) and (B) occur with probability at most γ each since L is given to be a (1 − γ)-probably robustly-reliable learner. Since , event (C)) occurs with probability at most δ. We claim that if none of these bad events occur, then x ∈ RR L (S, h * , η). To prove this, assume for contradiction that none of the bad events occur and x ∈ RR L (S, h * , η). LetS h ,h * denote a relabeling of S such that exactly half the points in ∆ S = {x | (x, y) ∈ S, h (x) = h * (x)} are labeled according to h * (the remaining half using h , for convenience assume |∆ S | is even). Note that since bad event (C) did not occur, We can strengthen Theorem 3.6 for learners that satisfy a somewhat stronger condition that with probability at least 1 − γ over the draw of the unlabeled sample S X , for all targets h * ∈ H, the sample S produced by labeling S X by h * should be a good sample. See Theorem A.1 in Appendix A.

Robustly-Reliable Learners for Instance-Targeted Malicious Noise
So far, our noise model has allowed the adversary to corrupt an arbitrary η fraction of the training examples. We now turn to the classic malicious noise model (Valiant, 1985;Kearns and Li, 1993) in which the points an adversary may corrupt are selected at random: each point independently with probability 1 − η is drawn from D and with probability η is chosen adversarially. Roughly, the malicious adversary model corresponds to a data poisoner that can add poisoned points to the training set (because the "clean" points are a true random sample from D) whereas the A η noise model corresponds to an adversary that can both add and remove points from the training set.
Traditionally, the malicious noise model has been examined in a non-instance-targeted setting. That is, the concern has been on the overall error-rate of classifiers learned in this model. Here, we consider instance-targeted malicious noise, and provide efficient robustly-reliable learners building on the seminal work of Awasthi et al. (2017). To discuss the set of possible adversarial corruptions in the malicious noise model with respect to particular random draws, for training set S and indicator vector v ∈ {0, 1} |S| , let A mal (S, v) denote the set of all possible S achievable by replacing the points in S indicated by v with arbitrary points in X × Y. We will be especially interested in Definition 4. Given sample S and indicator vector v ∈ {0, 1} |S| , let A mal (S, v) denote the collection of corrupted samples S achievable by replacing the points in S indicated by v with arbitrary points in X × Y.
We now define the notion of probably robustly-reliable learners and their robustly-reliable region for the malicious adversary model.
In Appendix B we show how this model relates to the A η adversary from Section 3, and to other forms of the malicious noise model of Kearns and Li (1993).

Efficient algorithm for linear separators with malicious noise
For learning linear separators, the above approaches and prior work Gao et al. (2021) provide inefficient upper bounds, since we do not generically have an efficient ERM oracle for that class. In the following we show how we can build on an algorithm of Awasthi et al. (2017) for noise-tolerant learning over log-concave distributions to give strong per-point reliability guarantees that scale well with adversarial budget η. The algorithm of Awasthi et al. (2017) operates by solving an adaptive series of convex optimization problems, focusing on data within a narrow band around its current classifier and using an inner optimization to perform a soft outlier-removal within that band. We will need to modify the algorithm to fit our setting, and then build on it to produce per-point reliability guarantees.
Theorem 4.1. Let D X be isotropic log-concave over R d and H be the class of linear separators. There is a polynomial-time (1 − δ)-probably robustly-reliable learner L against A mal η for class H under D X based on Algorithm 2 of Awasthi et al. (2017), which uses a sample of size m = poly(d, 1 η , log(1/δ)). Furthermore, for any h * ∈ H, with probability at least 1 − δ over S ∼ D m and v ∼ Bernoulli(η) m , we have TheÕ-notation suppresses dependence on logarithmic factors and distribution-specific constants.
Proof. We will run a deterministic version of Algorithm 2 of Awasthi et al. (2017) (see Appendix C) and let h = h(S ) be the halfspace output by this procedure. By Theorem C.9 (an analog of Theorem 4.1 of Awasthi et al. (2017) for the A mal η noise model), there is a constant C 0 such that err D (h) ≤ C 0 η with probability at least 1 − δ over the draw of S ∼ D m and v ∼ Bernoulli(η) m . 1 In the following, we will assume the occurrence of this 1 − δ probability event where the learner outputs a low-error hypothesis for any S ∈ A mal (S, v). We now show how we extend this result to robustly-reliable learning.
We will first show we can in principle output a robust-reliability value η on all points in Agree(B H D (h, C 0 η)). (Algorithmically, we will do something slightly different because we do not have an ERM oracle and so cannot efficiently test membership in the agreement region). Indeed by Theorem C.9, h * is guaranteed can be confidently classified with robust reliability level η.
Since we cannot efficiently determine if a point lies in Agree(B H D (h, C 0 η)), algorithmically we instead do the following. First, for any halfspace h , let w h denote the unit-length vector such that h (x) = sign( w h , x ). Next, following the argument in the proof of Theorem 14 of Balcan and Long (2013), we show that for some constant C 1 , for all values α, we have: Algorithmically, we will provide robustness level η for all points satisfying the right-hand-side above (which we can do efficiently), and the containment above implies this is legal. To complete the proof of the theorem, we must (a) give the proof of containment (1) and (b) prove that the intersection of the right-hand-sides of (1) over all h = h(S ) for S ∈ A mal (S, v) has probability mass 1 −Õ( √ dη). We begin with (a) giving the proof of the containment in formula (1). First, by Lemma C.2 (due to Balcan and Long (2013) , completing the proof of containment (1). Now we prove (b) that the intersection of the right-hand-sides of (1) over all h = h(S ) for S ∈ A mal (S, v) has probability mass 1−Õ( √ dη). To do this, we first show that for all h such that err D (h) ≤ C 0 η we have: This follows from the same argument used to prove (a) above. Specifically, by Lemma C.2, B H D (h * , C 0 η) consists of hypotheses having angle at most C 1 η to w h * for the same constant C 1 as above.
To complete the proof of (b), we now just need to show that the probability mass of the right-hand-side of (2) is at least 1 −Õ( √ dη). This follows using the argument in the proof of Theorem 14 in Balcan and Long (2013). First we use the fact that for an isotropic log-concave distribution over R d , we have . This means we can choose α = ln(1/( √ dη)) and ensure that at most an O( √ dη) probability mass of points x fail to satisfy the first term in the right-hand-side of (2). For the second term, using the fact that marginals of isotropic log-concave distributions are also isotropic log-concave (in particular, the 1-dimensional marginal given by taking inner-product with w h * ) and that the density of a 1-dimensional isotropic log-concave distribution is at most 1 (Lemma C.1), at most an O(αη √ d) probability mass of points x fail to satisfy the second term in the right-hand-side of (2). Putting these together yields the theorem.
Remark. Note that the above result improves over a related distribution-specific result of Gao et al. (2021) in three ways. First, we are able to certify that the prediction of our algorithm is correct rather than only certifying that the prediction would not change due to the adversary intervention. Second, we are able to handle much more general distribution -any isotropic logconcave distribution, as opposed to just the uniform distribution. We essentially achieve the sameÕ( √ dη) upper bound on the uncertified region but for a much larger class of distributions. Finally, unlike Gao et al. (2021), our algorithm is polynomial time. Lower bounds. We also have a near-matching lower bound on robust reliability in the A mal η model. This lower bound states that points given robust-reliability level η must be in Agree(B H D (h * , η 1−η − )) with a high probability, which differs from our upper bound above by a constant factor in the agreement radius.
Theorem 4.2. Let L be a (1 − γ)-probably robustly-reliable learner against A mal η for hypothesis class H under marginal D X . For any h * ∈ H, given a large enough sample size m = |S| ≥ c 2 ln 1 δ and any η ≤ 1 2 , we have where c is an absolute constant and D is the distribution with marginal D X consistent with h * .
Proof. Let L be a (1 − γ)-probably robustly-reliable learner for H under marginal D X and let h * ∈ H. Let ; such an h exists by definition of the disagreement region. Let S ∼ D m and define S = {(x, h (x)) | (x, h * (x)) ∈ S}. Note that S ∼ D m , where D is a data distribution with the same marginal as D but consistent with h . Let be the points with indicator v set to 1 which the malicious adversary gets to corrupt.
We now consider four bad events of total probability at most 2γ + 2δ: (A) L is not robustly-reliable for all Indeed events (A) and (B) occur with probability at most γ each since L is given to be a (1 − γ)-probably robustly-reliable learner. An application of Hoeffding's inequality implies (C) occurs with probability at most δ for sufficiently large m ≥ c 2 ln 1 δ for some absolute constant c since v ∼ Bernoulli(η) m . Finally, observe that the event (x, y) ∈ ∆ S \ S v for any (x, y) in the sample S is a Bernoulli event with probability of occurrence at most η 1−η − (1 − η) = η − (1 − η) ≤ η − 2 , since the events (x, y) ∈ ∆ S and (x, y) / ∈ S v are independent and η ≤ 1 2 . Another application of Hoeffding's inequality implies a δ-probability bound on (D).
We claim that if none of these bad events occur, then x ∈ RR L mal (S, h * , η, v). Assume for contradiction that none of the bad events occur and x ∈ RR L mal (S, h * , η, v). We will now proceed to describe an adversarial corruptionS v h ,h * of S which guarantees at least one of the bad event occurs if x is in the stipulated η-robustlyreliable region. We select a uniformly random sequence of |∆ S \ S v | corruptible points from S v and replace them (x, 1 − y) for each (x, y) ∈ ∆ S \ S v . We substitute the remaining points in S v by (x, h * (x)) for some fixed x ∈ Agree(B H D (h * , η 1−η − )). We specify this substitution to ensure that all remaining points in the disagreement region occur in pairs with opposite labels, and we do not reveal the corruptible points. The first claim follows by noting that |∆ S \ S v | ≤ |S|(η − 3 ) ≤ |S v | since bad events (C) and (D) did not occur. So, x cannot be in RR L (S, h * , η, v) as desired.

Active Robustly Reliable Learners
Instance-targeted attacks may also occur in situations where the labeled data is expensive to obtain and one would typically use active learners to learn accurate classifiers with fewer labeled examples. For example, consider translation to a rare language for which an expert can be expensive to obtain. We might have access to proprietary labeled data, but may be charged per label and would like to minimize the cost of obtaining the labels. It is possible that an attacker with access to the data corrupts it in an instance-targeted way.
We consider a pool-based active learning setting (Settles (2009)), where the learner draws (labeled and unlabeled) examples from a large pool of examples which may have been corrupted by an instance-targeted adversary. That is, a dataset S is drawn according to some true distribution D and the instance-targeted adversary may corrupt an η fraction of the dataset arbitrarily (change both data points and labels). The learner has access to unlabeled examples from the corrupted dataset S , and is allowed to make label queries for examples in the dataset. The goal of the learner is to produce a robustly-reliable predictor for the marginal distribution D X , and using as few labels as possible. Our (passive) robustly-reliable learner in Theorem 3.3 needsÕ( d 2 ) examples; in this section we explore if we can actively robustly-reliably learn with fewer labeled examples.
To formalize our results on active learning, we have the following definition.
Definition 6 (Active Robustly-Reliable Learner). A learner L is said to be an active robustly-reliable learner w.r.t. concept space H if for any training sample S , the learner has access to unlabeled examples from S and the ability to request labels, and must output a function L S : X → Y × R. The label complexity of L is the number of labels the learner requests before outputting L S . An active robustly-reliable learner L is said to be strongly robustly-reliable against A η for class H if for any target function h * ∈ H, for any dataset S consistent with h * , for all S ∈ A η (S), for all x ∈ X , if L S (x) = (y, η ) for η ≥ η then y = h * (x). The robustly-reliable correctness and robustly-reliable region, for this value η, are defined the same as for passive learning above.
An active robustly-reliable learner L is said to be (1 − δ)-strongly robustly-reliable against A η for class H if for any target function h * ∈ H, for any dataset S consistent with h * , for all S ∈ A η (S), with probability at least 1 − δ over the internal randomness of the learner, for all x ∈ X , if L S (x) = (y, η ) for η ≥ η then y = h * (x). The empirical η-robustly-reliable region is defined as for passive learning above.
We will now show two results indicating that it is possible for the learner to query the labels intelligently to obtain a robustly-reliable algorithm, first in the stronger sense of strongly robustly-reliable learning, and second in the weaker sense of (1 − δ)-strongly robustly-reliable learning (i.e., with high probability over the randomness of the learner). In both cases, we are also able to obtain a bound on the number of queries made by the active learner, holding with high probability over the draw of the uncorrupted dataset S (and in the (1 − δ)-strongly robustly-reliable case, also the randomness of the learner).
First, let us consider the case of strongly robustly-reliable active learning. Note that this case is quite challenging, since the adversary effectively knows what queries the learner will make. For instance, the adversary may choose to set it up so that the learner's first ηm queries are all corrupted, so that the learner cannot even find an uncorrupted point until it has made at least ηm queries. In particular, this intuitively means that nontrivial reductions in label complexity compared to passive learning are only possible in the case of small η.
Our result (Theorem 5.1 below) proposes an active learning method that, for any given η, produces an optimal η-robustly-reliable region (i.e., matching the upper and lower bounds of Theorems 3.3 and 3.5), while making a number of label queries that, for small η, is significantly smaller than the number m of examples in S (the corrupted sample), when the disagreement coefficient θ is small: specifically, it makes a number of queriesÕ(θηm + θd). The algorithm we propose is actually quite simple: we process the corrupted data S in sequence, and for each new point x i we query its label y i iff x i is in the region of disagreement of the set of all h ∈ H that make at most ηm mistakes among all previously-queried points. In the end, after processing all m examples in S , we use the region of agreement of this same set of classifiers as the empirical η-robustly-reliable region, predicting using their agreed-upon label for any test point x in this region. The result is stated formally as follows.
Theorem 5.1. For any hypothesis class H and η ≥ 0, there is an active learner L that is strongly robustlyreliable against A η which, for any data set S consistent with some h * ∈ H, Moreover, if D is a realizable distribution with some h * ∈ H as target concept, then for any δ ∈ (0, 1), if m = Ω η+ . , x m , the algorithm, processes the data in sequence: for each t ≤ m, the algorithm queries for the label y t iff x t ∈ DIS(V t−1 ); if it queries, then Q t = Q t−1 ∪ {(x t , y t )}, and otherwise Q t = Q t−1 ; in either case, V t = {h ∈ H : (x,y)∈Qt 1[h(x) = y] ≤ ηm}. To define the predictions of the learner in the end, for any x ∈ Agree(V m ), define L S (x) = (y, η) for the label y agreed upon for x by every h ∈ V t ; for any x / ∈ Agree(V m ), we can define L S (x) = (⊥, −1). Note that if S ∈ A η (S) for a data set S = {(x 1 , y 1 ), . . . , (x m , y m )} consistent with some h * ∈ H, then (since Q t is a subsequence of S , and h * makes at most ηm mistakes on S ), we maintain the invariant that h * ∈ V t for all t. In particular, this implies L S (x) is well-defined since V m is non-empty. Moreover, this implies that for any x, any label y agreed-upon by all h ∈ V m is necessarily h * (x). Thus, L satisfies the definition of a strongly robustly-reliable learner. Additionally, for any h ∈ V m , since we also have h * ∈ V m , the algorithm would have queried for the label y t of every x t ∈ DIS({h, h * }). Since h remains in V m , it must be that h(x t ) = y t on at most ηm of these points. Since any h ∈ H not in B H S (h * , 2η) has strictly greater than 2ηm points in S on which it disagrees with h * and is incorrect, and the number of such points in S can be smaller by at most ηm, 2η)). To address the remaining claims, let D be a realizable distribution with some h * ∈ H as target concept, and fix , δ ∈ (0, 1) and η ≥ 0, and suppose m = Ω η+ 2 d log 1 + log 1 δ with an appropriate numerical constant factor. Let S ∼ D m . By classic relative uniform convergence guarantees Vapnik and Chervonenkis (1974) (see Theorem 4.4 of Vapnik (1998)), with probability at least 1 − δ, every h ∈ H satisfies so that, for an appropriate numerical constant, if m = Ω η+ 2 d log 1 + log 1 δ , every h ∈ H with err D (h) > 2η + has err S (h) > 2η. Thus, on this event, B H S (h * , 2η) ⊆ B H D (h * , 2η + ). In particular, by the above analysis of the algorithm under any fixed S, we have V m ⊆ B H S (h * , 2η). Together, we have that with probability at least 1 − δ, V m ⊆ B H D (h * , 2η + ), which immediately implies that RR L (S, h * , η) ⊇ Agree(B H D (h * , 2η + )). Finally, we turn to bounding the number of label queries. For every t ∈ {1, . . . , m}, define S t = {(x 1 , y 1 ), . . . , (x t , y t )} and S t = {(x 1 , y 1 ), . . . , (x t , y t )}. Note that the number of queries equals Following a similar argument to the analysis of RR L above, for any t ≤ m, since any h ∈ H not in B H St h * , 2ηm t has strictly greater than 2ηm points in S t on which it disagrees with h * and is incorrect, and the number of such points in S t can be smaller by at most ηm, every h ∈ V t is necessarily in t . Together with (3), this implies the total number of queries is at most By Bernstein's inequality for martingale difference sequences, with probability at least 1 − δ/2, the right hand side above is at most Let α t = c t d log t d + log 1 δ , for a numerical constant c > 0. Again by relative uniform convergence guarantees, together with a union bound (over all values of t), for an appropriate numerical constant c > 0, with probability at least 1 − δ/2, for every t ≤ m and h ∈ H,

Thus, on this event, for every
Plugging into (4), by a union bound, with probability at least 1 − δ, the total number of queries is at most where the inequality on the second-to-last line is by the definition of the disagreement coefficient, and the final expression results from summing the harmonic series: b Next, we consider the weaker case of (1 − δ)-strongly robustly-reliable active learning. Note that in this case, the adversary only corrupts the data pool, but is not directly involved with the learner's queries. That is, the corruption may depend on the dataset S and the target test instance x, but it does not depend on the randomness in the algorithm used by the learner to query labels and output a hypothesis.
In this case, our result (Theorem 5.3 below) provides a method that yields an empirical robustly-reliable region of comparable size to the results for passive learning above (up to constant factors), using a number of queries that is significantly smaller than the sample complexity of passive learning, when η and the disagreement coefficient are small. However, we note that unlike Theorem 5.1 above, in this case the number of queries is bounded, in that it does not depend on the size m of the data set S: that is, it can be expressed purely as a function of η, ,δ,d, and θ. However, it is also worth noting that the number of queries in Theorem 5.1 is actually of the same order as in Theorem 5.3 (up to log factors) in the case that m = Θ η+ 2 d log 1 + log 1 δ , so that for the minimal sample size sufficient for the result on RR L (S, h * , η) in Theorem 5.1, we essentially lose nothing compared to the guarantee achievable by the weaker (1 − δ)strongly robustly-reliable learner in Theorem 5.3.
Our (1 − δ)-strongly robustly-reliable active learner in Theorem 5.3 will use an agnostic active learning algorithm (in the usual learning setting, without robust-reliability requirements). We will use the algorithm proposed by Dasgupta et al. (2007). The algorithm partitions points seen so far into sets T (labels explicitly queried) and U (labels not queried). For a new point x, ERMs h y on T consistent with U ∪ (x, y) for y ∈ {0, 1} are learned and the label for x is requested only if the difference in errors of h 0 , h 1 is small. The algorithm has the following guarantee.
Theorem 5.2 (Dasgupta et al. (2007)). Let H denote the hypothesis space. Let D be a distribution such that h * = argmin h∈H err D (h) and err D (h * ) = η. If θ η+ is the disagreement coefficient of H w.r.t. h * over D, then given S ∼ D m with m ≥ c η+ In Theorem 5.3 we define an (1 − δ)-strongly robustly-reliable active learner which requires fewer labels than the passive learner.
Theorem 5.3. Let H be a hypothesis class, and S be a sample consistent with h * ∈ H. Ifθ η+ is the disagreement coefficient of H with respect to h * over the uniform distribution U (S) over S (see Definition 3), there exists a (1 − δ)-strongly robustly-reliable active learner L based on the agnostic active learning algorithm of Dasgupta et al. (2007), which for some constant c, given any S ∈ A η (S), for sample size m ≥ c η+ 2 d log 1 + log 1 δ , with probability 1 − δ the learner queries O θ η+ (η+ ) 2 2 d log 1 + log 1 δ log 1 labeled examples and returns L S which satisfies, with probability at least 1 − δ, Proof. The learner samples points uniformly randomly from the (corrupted) data pool S and applies the agnostic active learning algorithm of Dasgupta et al. (2007), i.e. the agnostic active learning algorithm receives unlabeled points drawn uniformly from the data pool S and labels are revealed for points requested by the algorithm. Letĥ denote the hypothesis output by the algorithm. The learner provides test point x with the largest η such that x ∈ Agree(B H S (ĥ, 2η + )) and outputs the common y in the agreement region, and outputs (⊥, −1) if x / ∈ Agree(B H S (ĥ, 2η + )) for any η ≥ 0. Note that this computation does not need the knowledge of labels and can be performed over the unlabeled pool which the learner has access to.
By Theorem 5.2, we have an upper bound on the number of labels requested by the agnostic active learner given by O θ η+ (η+ ) 2 2 d log 1 + log 1 δ log 1 with probability at least 1 − δ over the algorithm's internal randomness, where θ η+ is the disagreement coefficient of H w.r.t. h * over D , with D being the distribution corresponding to uniform draws from S . We will show that θ η+ = O(θ η+ ), which implies the desired bound. LetD denote U (S). Observe that The agnostic active learning algorithm returns a hypothesisĥ with error at most err D (ĥ) ≤ err D (h * ) + ≤ η + on S with failure probability δ. Since err S (ĥ) ≤ η + (if the failure event does not occur) and err S (h * ) ≤ η, using the triangle inequality h * ∈ B H S (ĥ, 2η + ) and we can provide robust-reliability η to x if x ∈ Agree(B H S (ĥ, 2η + )). Notice B H S (ĥ, 2η + ) ⊆ B H S (h * , 4η + 2 ) ⊆ B H S (h * , 5η + 2 ). Therefore the empirical η-robustly-reliable region of the learner contains Agree(B H S (h * , 5η + 2 )) with probability 1 − δ over the learner's randomness.
To establish the distributional results, we need to relate θ η+ withθ η+ and the robustly-reliable agreement region over the sample to one over the distribution, both using uniform convergence bounds. By uniform convergence (Anthony and Bartlett (2009) Theorem 4.10), with probability at least 1 − δ, r + )). Moreover, note that the family {DIS(B H D (h * , r)) : r ≥ 0} has VC dimension 1, and therefore by uniform convergence, with probability at least 1 − δ, we have PrD r))] + for all r ≥ 0. Supposing both of these events, we haveθ By a union bound, the above 3 events occur simultaneously, with probability at least 1 − 3δ. This implies the desired label complexity bound. The bound on the trusted region follows from another application of the uniform convergence bound which implies B H S (h * , 5η + 2 ) ⊆ B H D (h * , 5η + 3 ) with probability 1 − δ, from which the stated result follows by a union bound.
Remark 3. Our above result is essentially a reduction of finding a (1 − δ)-strongly robustly-reliable active learner to a general agnostic active learner. We have used the algorithm from Dasgupta et al. (2007) in Theorem 5.3, but we can substitute any other agnostic active learning algorithm to get the corresponding label complexity guarantees.
We demonstrate an application of the above theorem to the well-studied setting of learning a linear separator, with the data distributed according to the uniform distribution over the unit ball.
Remark 4 (Linear separators for uniform distribution over the unit ball). It was shown by Hanneke (2007) that θ η+ = O( √ d) for this setting. Theorem 5.3 now implies an exponential gain in the label complexity for ≈ η and a gain by a factor ofÕ( 1 √ dη ) for η.

Robustly reliable agnostic learners
So far we have assumed throughout that the uncorrupted samples S are realizable under our concept class H.
We will now show that our results can be extended to the non-realizable setting, i.e. min h∈H err S (h) > 0, with weaker but still interesting guarantees. Specifically, our algorithm might now produce an incorrect prediction (y, η) with η greater than the adversary's power, but only if every hypothesis in H with low error on the uncorrupted S would also be incorrect on that example. We can define a ν-tolerably robustly-reliable learner in the non-realizable setting as the learner whose reliable predictions agree with every low error hypothesis (error at most ν) on the uncorrupted sample.
Definition 7. A learner L is ν-tolerably robustly-reliable for sample S w.r.t. concept space H if, given S , the learner outputs a function L S : X → Y × R such that for all x ∈ X if L S (x) = (y, η) then for all h * ∈ H such that err S (h * ) ≤ ν for some S with S ∈ A η (S), we have y = h * (x).
Definition 7 describes the notion of a robustly-reliable learner for a particular (corrupted) sample. Notice that if there are multiple h ∈ H satisfying err S (h) ≤ ν and they disagree on x then it must be the case that the algorithm outputs η < 0. Notice also that setting ν = 0 in the above definition yields the usual robustlyreliable learner. Similarly to Definition 2, we now extend this to robustly-reliable with high probability for an adversarially-corrupted sample drawn from a given distribution.
Definition 8. A learner L is a (1 − γ)-probably ν-tolerably robustly-reliable learner for concept space H under marginal D X (where D is the distribution over examples with marginal D X ) if with probability at least 1 − γ over the draw of S ∼ D m , for any concept h * ∈ H such that err D (h * ) ≤ ν, for all S ∈ A η (S), and for all x ∈ X , if L S (x) = (y, η ) for η ≥ η then y = h * (x). If L is a (1 − γ)-probably ν-tolerably robustly-reliable learner with γ = 0 for all marginal distributions D X , then we say L is νtolerably strongly robustly-reliable for H. Note that a ν-tolerably strongly robustly-reliable learner is a ν-tolerably robustly-reliable learner in the sense of Definition 7 for every sample S . Given distribution D, the (ν, η)-robustly-reliable correctness for learner L for sample S is given by the probability mass of the robustly-reliable region, RobC L (D, ν, η, S) = Pr x∼D X [x ∈ RR L (S, ν, η)].
We now provide a general ν-tolerably strongly robustly-reliable learner using the notion of agreement regions (Theorem 6.1). Our results here generalize corresponding results from Section 3. We first present our learner and a guarantee on the learner's empirical (ν, η)-robustly-reliable region given any (possibly corrupted) dataset. Our algorithm assumes ν is given.
Proof. Given sample S , the learner L outputs the function L S (x) = (y, η) where η is the largest value such that x ∈ Agree(H η+ν (S )), and y is the common prediction in that agreement region; if x ∈ Agree(H η+ν (S )) for all η ≥ 0, then L S (x) = (⊥, −1). This is a strongly robustly-reliable learner because if L S (x) = (y, η) and S ∈ A η (S) and err S (h * ) ≤ ν, then h * ∈ H η+ν (S ), so y = h * (x). Also, notice that by design of the algorithm, all points in Agree(H η+ν (S )) will be given robust-reliability level at least η. The learner may be implemented using an ERM oracle using knowledge of ν and the construction in Theorem 3.2.
We now analyze the (ν, η)-robustly-reliable region for the algorithm above which we will prove is pointwise optimal over all ν-tolerably strongly robustly-reliable learners.
Theorem 6.2. For any hypothesis class H, the ν-tolerably strongly robustly-reliable learner L from Theorem 6.1 satisfies the property that for all S and for all η ≥ 0 and for any h * with err S (h * ) ≤ ν, where H α (T ) = {h ∈ H | err T (h) ≤ α} for any α ≥ 0, where T may be a sample or a distribution. Moreover, if S ∼ D m for m = O( 1 2 (d + ln 1 δ )) then with probability at least 1 − δ, RR L (S, ν, η) ⊇ Agree(H 2η+ν+ (D)). Here d denotes the VC dimension of H.
We will now show a matching lower bound for Theorem 6.2. In contrast to the realizable case, our matching bounds here are in terms of agreement regions of hypotheses with low error on the sample (more precisely Agree (H 2η+ν (S))), instead of balls around a fixed hypothesis in H. In Theorems 3.3 and 3.5, the size of the robustly-reliable region is Agree B H S (h * , 2η) , which in the realizable case is the same as Agree (H 2η (S)). This also implies we do not lose too much of the robustly-reliable region in the agnostic case.
Theorem 6.3. Let L be a ν-tolerably strongly robustly-reliable learner for hypothesis class H. Then for any sample S, any point in the (ν, η)-robustly-reliable region must lie in the agreement region of H 2η+ν (S) = {h ∈ H | err S (h) ≤ 2η + ν}. That is, Proof. Let x ∈ Agree(H 2η+ν (S)). We will show that x cannot be in the (ν, η)-robustly-reliable region. First, since x ∈ Agree(H 2η+ν (S)), there must exist some h 1 , h 2 ∈ H 2η+ν (S) such that h 1 (x) = h 2 (x). Since we are interested in the (ν, η)-robustly-reliable region, suppose we have hypothesis h * ∈ H such that } denote the points in the uncorrupted sample where h * is incorrect. Further let S e = {(x, y) ∈ S | h 1 (x) = y} be the points where h 1 is incorrect on S. Finally letS be a fixed subset of S e \ S * e of size min{2ηm, |S e \ S * e |} and let S ⊂S with |S | = |S|/2. We will now construct two sets S 1 and S A . S 1 will be such that err S 1 (h 1 ) ≤ ν and S A will satisfy S A ∈ A η (S) as well as S A ∈ A η (S 1 ). For any U ⊆ T , let FLIP(T , U ) = {(x, 1 − y) | (x, y) ∈ U } ∪ T \ U denote a sample T with flipped labels for subset U . We define S 1 = FLIP(S,S) and S A = FLIP(S, S ). To show err S 1 (h 1 ) ≤ ν, note that we have one of two cases. Either |S e \ S * e | ≤ 2ηm, in which casẽ S = S e \ S * e and h 1 will we correct on these in S 1 . So h 1 is incorrect on at most |S * e | points on S 1 and err S 1 (h 1 ) ≤ ν. The other case is |S e \ S * e | > 2η, which impliesS ≥ 2ηm. SinceS ⊆ S e , we have that err S 1 (h 1 ) ≤ err S (h 1 ) − 2η ≤ ν. Finally since |S| ≤ 2ηm and |S | = |S|/2, we have d(S, S 1 ) ≤ 2η and d(S, S A ) ≤ η. Also, S 1 and S A differ on points corresponding toS \ S with |S \ S | = |S|/2 ≤ ηm. Thus, S A ∈ A η (S) as well as S A ∈ A η (S 1 ). Now notice that sample S has err S (h * ) ≤ ν and S A ∈ A η (S). Also S has err S 1 (h 1 ) ≤ ν and S A ∈ A η (S 1 ). Now, assume for contradiction that x ∈ RR L (S, ν, η). This means that L S A (x) = (y, η ) for some η ≥ η. However, if y = h * (x), the learner is incorrectly confident for (true) dataset S since S A ∈ A η (S). Similarly, if y = h * (x), the learner is incorrectly confident for sample S 1 since h 1 (x) = h * (x). Thus, L is not a ν-tolerably strongly robustly-reliable learner and we have a contradiction.
We can show that any 2ν-tolerably strongly robustly-reliable learner for the concept space can be used to give a (1 − γ)-probably ν-tolerably robustly-reliable learner over a distribution D where the best hypothesis h * in H has error err D (h * ) = ν.
Theorem 6.4. Let H be the concept space, and D be a distribution such that min h∈H err D (h) = ν * , and let L be a 2ν * -tolerably robustly-reliable learner for H for any sample S . If m ≥ c ν * 2 (d + ln 1 γ ), then L is also (1 − γ)-probably ν * -tolerably robustly-reliable learner for H under marginal D X .
Proof. Let D be a distribution with the same marginal D X as D. Let S ∼ D m . By uniform convergence (Anthony and Bartlett (2009) Theorem 4.10), for each h ∈ H ν * (D ) = {h ∈ H | err D (h) ≤ ν * }, we have that err S (h ) ≤ 2ν * with probability at least 1 − γ over the draw of S. For each such S, for all S ∈ A η (S), and for all x ∈ X , if L S (x) = (y, η ) for η ≥ η then y = h(x) for any h ∈ H with err S (h) ≤ 2ν * since L is 2ν * -tolerably robustly-reliable for any sample S . In particular, the prediction agrees with each h ∈ H ν * (D ). Therefore L is a (1 − γ)-probably ν * -tolerably robustly-reliable learner for H under marginal D X .
We can use the above reduction, together with our ν-tolerably strongly robustly-reliable learner, to give a probably tolerably robustly-reliable learner for any distribution D along with guarantees about its distribution-averaged robust reliability region.
Theorem 6.5. Let H be the concept space, and D be a distribution such that min h∈H err D (h) = ν * . If m ≥ c ν * 2 (d + ln 1 γ ), then there is a (1 − γ)-probably ν * -tolerably robustly-reliable learner for H under marginal D X , with (2ν * , η)-robustly-reliable correctness that satisfies where d is the VC-dimension of H, and c is an absolute constant.
Finally, let's consider the η-robustly-reliable correctness of L. By another application of uniform convergence, with probability at least 1 − γ, Agree (H 2η+2ν * (S)) ⊇ Agree (H 2η+3ν * (D)). As shown above, with probability 1 − γ, we also have RR L (S, 2ν * , η) ⊇ Agree (H 2η+2ν * (S)). By a union bound over the failure probabilities, with probability at least 1 − 2γ over the draw of S, we have RR L (S, 2ν * , η) ⊇ Agree (H 2η+3ν * (D)). Finally, by the definition of (ν, η)-robustly-reliable correctness, we have that Finally we have the following lower bound on the robustly-reliable correctness for any (1 − γ)-probably ν-tolerably robustly-reliable learner. The key idea in establishing this lower bound is the creation of two distributions with the same marginal but nearly-consistent with two hypotheses which are close in error.
Theorem 6.6. Let L be a (1 − γ)-probably ν-tolerably robustly-reliable learner for hypothesis class H under marginal D X . Given a large enough sample size m = |S| ≥ c 2 d + ln 1 δ , we have where c is an absolute constant and D is the distribution with marginal D X consistent with h * .
Proof. Let L be a (1 − γ)-probably ν-tolerably robustly-reliable learner for H under marginal D X and let h * ∈ H such that err D (h * ) ≤ ν. Let x ∈ Agree(H 2η+ν− (D)). To prove the theorem, it suffices to prove that Pr S∼D m [x ∈ RR L (S, ν + , η)] ≤ 2γ + 3δ. By definition of the disagreement region, we can select some Let D be a distribution which modifies D by re-assigning a probability mass of p = min{2η − , Pr D [E 1 \ E * ]} from points (x, y) ∈ E 1 \ E * to corresponding points with flipped labels (x, 1 − y). Formally, using Corollary D.2, there are distributions D 1 and D 2 such that D = pD 1 + (1 − p)D 2 with supp(D 1 ) ⊆ E 1 \ E * , and we define D = pD 1 + (1 − p)D 2 where D 1 is the distribution corresponding to drawing from D 1 but with flipped labels. Notice that D has the same marginal D X distribution as D. Moreover, Drawing from D is equivalent to first flipping a random biased coin, with probability p drawing according to D 1 (call these points 'red'), and otherwise drawing from D 2 . Let S ∼ D m and S be the dataset obtained by flipping labels of all the 'red' points in S. Notice that S ∼ D m . We now consider three bad events of total probability at most 2γ + 3δ: (A) L is not (ν + )-tolerably robustly-reliable for all datasets in A η (S), (B) L is not (ν + )-tolerably robustly-reliable for all datasets in A η (S ), and (C) d(S, S ) > 2η. Indeed events (A) and (B) occur with probability at most γ + δ each since L is given to be a (1 − γ)-probably ν-tolerably robustly-reliable learner for H under D X , and by uniform convergence (Anthony and Bartlett (2009) Theorem 4.10) for each h with err D (h) ≤ ν we have err S (h) ≤ ν + with probability at least 1 − δ. Finally, a point drawn according to D is red with probability p ≤ 2η − . By an application of the Hoeffding's inequality, there are at most 2η red points in S with probability at least 1 − δ, i.e. (C) occurs with probability at most δ.
We claim that if none of these bad events occur, then x ∈ RR L (S, ν + , η). To prove this, assume for contradiction that none of the bad events occur and x ∈ RR L (S, ν + , η). LetS h 1 ,h * denote a relabeling of S such that exactly half the red points are labeled according to h * (the remaining half using h 1 ). Note that since bad event (C) did not occur, this means thatS h 1 ,h * ∈ A η (S) andS h 1 ,h * ∈ A η (S ), Now, since x ∈ RR L (S, ν + , η) andS h 1 ,h * ∈ A η (S), it must be the case that LS h 1 ,h * (x) = (y, η ) for some η ≥ η. But, if y = h * (x) then this implies bad event (A), and if y = h (x) then this implies bad event (B). So, x cannot be in RR L (S, ν + , η) as desired.

Discussion
In this work, for the first time we provide correctness (specifically robust reliability) guarantees for instancetargeted training time attacks, along with guarantees about the size of the robustly-reliable region. One implication of our results is a combined robustness against test-time attacks as well, where an adversary makes imperceptible or irrelevant perturbations to the test examples in order to induce errors. Specifically, even without being given any knowledge of the kinds of perturbations such an adversary could make, our algorithms in the worst case will simply abstain (output η < 0) or produce an η less than the perturbation budget of the adversary if the adversary is performing both kinds of attacks together. In the agnostic case, the adversary could cause us to make a mistake, but only if every low-error hypothesis in the class would have also made a mistake. An interesting open question is to provide usefulness guarantees for test time attacks, for reliable predictors: that is, nontrivial bounds on the probability that an adversary's perturbation of the test point can cause the predictor to abstain.

A Additional lower bounds in the realizable setting
We show how we can strengthen the lower bound of Theorem 3.6 for learners that satisfy the somewhat stronger condition of being a (1 − γ)-uniformly robustly-reliable learner (defined below). This condition requires that with probability at least 1 − γ over the draw of the unlabeled sample S X , for all targets h * ∈ H, the sample S produced by labeling S X by h * should be a good sample. In contrast, Theorem 3.6 requires only that for any h * , with probability at least 1 − γ over the draw of S, S is a good sample (different samples may be good for different target functions).
Definition 9. L is a (1 − γ)-uniformly robustly-reliable learner for class H under marginal distribution D X if with probability at least 1 − γ over the draw of an unlabeled sample S X ∼ D m X , for all h * ∈ H, for all Theorem A.1. Let L be a (1 − γ)-uniformly robustly-reliable learner for hypothesis class H under marginal D X . Then, for any h * ∈ H, for S ∼ D m (where D is the distribution over examples labeled by h * with marginal D X ), with probability 1 − γ over the draw of S we must have where c is an absolute constant and d is the VC-dimension of H, then with probability 1 − δ, The proof is similar to the proof for Theorem 3.5. We are given that L is a (1 − γ)-uniformly robustly-reliable learner. This means that with probability 1 − γ, the unlabeled sample S X has the property that the learner would be robustly-reliable for any target function in H. Assume this event occurs, and consider any x ∈ Agree(B H S (h * , 2η)). We will show that x cannot be in the η-robustly-reliable region. First, since x ∈ Agree(B H S (h * , 2η)), there must exist some h ∈ B H S (h * , 2η) such that h (x) = h * (x). Next, let S A denote a labeling of S X such that exactly half the points in ∆ S = {x ∈ S X | h (x) = h * (x)} are labeled according to h * (the remaining half using h , for convenience assume |∆ S | is even). Notice that S satisfies S A ∈ A η (S) since h ∈ B S (h * , 2η). Also for S = {(x i , h (x i ) | x i ∈ S X } labeled by h , we have S A ∈ A η (S ). Now, assume for contradiction that x ∈ RR L (S, h * , η). This means that L S A (x) = (y, η ) for some η ≥ η. However, if y = h * (x), the learner is incorrectly confident for (true) dataset S since S A ∈ A η (S). Similarly, if y = h * (x), the learner is incorrectly confidnet for sample S since h (x) = h * (x). This contradicts our assumption about S X .
The second part of the theorem statement follows directly from standard uniform convergence bounds.
B Relating A mal η to other models In this section we provide some observations that relate our instance-targeted malicious noise adversarial model from Section 4 to models from prior and current work. We begin by noting that learnability against the sample-based attacks defined above implies learnability under attacks which directly corrupt the distribution D with malicious noise.
Lemma B.1. Suppose D is a distribution over X × Y. Under the malicious noise model of Kearns and Li (1993), the learner has access to samples from D η (A ) = (1 − η)D + ηA , where A is an arbitrary adversarial distribution over X × Y. Let S ∼ D m and S ∼ D η (A ) m . Then there exists adversary A 1 ∈ A mal η such that A 1 (S) is distributed identically as S . Input: allowed error rate , probability of failure δ, sequences of sample sizes n k > 0, k = 1, 2, 3, ..., a sequence of cut-off values b k > 0, a sequence of hypothesis space radii r k > 0, a sequence of removal rates ξ k , a sequence of variance bounds σ 2 k , precision value κ; weight vector w 0 . Note that compared to Awasthi et al. (2017), we have replaced the random sampling inside W with just directly using loss with respect to weighting p.
1. Place the first n 1 examples in S into a working set W .
b. Find v k ∈ B(w k−1 , r k ), v k 2 ≤ 1, to approximately minimize hinge loss in W weighted by p: Scan S until n k+1 data points x have been found such that |w k · x| < b k , and put them into W . (If S is exhausted before this step is completed, then output failure.) Output: weight vector w s of error at most with probability 1 − δ.
noisy point and q * (x) = 1 for each clean point. This analysis makes the worst-case assumption that every adversarial point is placed inside the band |w k · x| < b k . Moreover, since q * (x) = 0 for each noisy point, there is no dependence on its location or label, so this q * remains feasible in our setting. Also, the analysis uses the fact that the non-noisy points are a true random sample from D (which is true in the A mal η model but not the A η model used in Section 3). For completeness, we present the theorem and summarize its analysis.
First, let η denote the value η divided by the probability mass under D of the band |w k−1 · x| < b k−1 . This is an upper bound on the probability a random example in the band is noisy even if the adversary places all of its points inside the band. By Chernoff bounds, n k ≥ poly(1/η , 1/δ) suffices so that with probability at least 1 − δ, at most a 2η fraction of the points in W are controlled by the adversary. Assume this is indeed the case. Also, let D w k−1 ,b k−1 denote the distribution D restricted to the band |w k−1 · x| < b k−1 .
Theorem C.4 (Analog of Theorem 4.2 of Awasthi et al. (2017) for the A mal η noise model). For any C > 0, there is a constant c and a polynomial p such that, for all ξ > 2η and all 0 < γ < C, if n k+1 ≥ p(1/η , d, 1/ξ, 1/δ, 1/γ, 1/r), then, with probability 1 − δ, the output q of Algorithm 3 satisfies the following: • For all unit length w such that w − u 2 ≤ r, Furthermore, the algorithm can be implemented in polynomial time.
Proof Sketch. The theorem is proven by analyzing the clean data points, namely those that are not under the adversary's control, using a pseudodimension-based uniform convergence analysis and properties of a. for all x ∈ W , 0 ≤ q(x) ≤ 1 b. 1 |W | (x,y)∈W q(x) ≥ 1 − ξ c. for all w ∈ B(u, r) ∩ B(0, 1), 1 |W | x∈W q(x)(w · x) 2 ≤ σ 2 .
log-concave distributions. This uses the fact that the non-noisy points are a true random sample from the underlying distribution, so this does not apply to the A η model used in Section 3.
Specifically, the proof uses the following two properties of isotropic log-concave distributions.
The two lemmas above, along with the fact that the non-noisy points in the A mal η model are indeed distributed according to D, imply that for all w ∈ B(u, r), 1 |W | x∈W q * (x)(a · x) 2 ≤ 2E[(a · x) 2 ] ≤ c(r 2 + γ 2 ), for an appropriate constant c, where q * (x) = 0 for each noisy point and q * (x) = 1 for each non-noisy point as defined above. Finally, an efficient separation oracle for the convex program yields the theorem. The next step is a further analysis of the working set W in each round k of Algorithm 2. The analysis partitions W into the "clean" set W C drawn from the true distribution D w k−1 ,b k−1 of points from D subject to lying inside the previous band, and the "dirty" set W D controlled by the adversary. Lemma 4.5 in Awasthi et al. (2017) upper-bounds the size of W D , and its analysis makes the worst-case assumption that every adversarial point lies inside the band. Since our setting is identical in terms of the probabilistic selection of which points are controlled by the adversary (differing only in allowing the adversary to make its choice after all of S is drawn), this argument also goes through directly. Specifically, Lemma 4.5, adapted to our setting, is as follows: Lemma C.7 (Analog of Lemma 4.5 of Awasthi et al. (2017) for the A mal η noise model). There is an absolute positive constant c such that, with probability 1 − δ 6(k+k 2 ) , Proof Sketch. Since the underlying distribution of non-noisy points is isotropic log-concave, the probability that a random example from D falls in the band is Ω(M −k ). By Chernoff bounds, this implies that O(n k M k ) examples from D are sufficient so that with probability at least (1 − δ 12(k+k 2 ) ), n k examples fall inside the band. In the A mal η model, the probability that each example drawn is noisy is η, and in the worst case, the adversary can place each noisy example inside the band. Since with probability at least (1 − δ 12(k+k 2 ) ) the total number of examples drawn is O(n k M k ), Chernoff bounds imply that for some constant c, with probability at least 1 − δ 12(k+k 2 ) we have |W D | ≤ cηn k M k . The second inequality follows from the fact that k ≤ log M (1/ ) . The bound of Lemma C.7 above is then used in Lemma 4.7 of Awasthi et al. (2017), which relates the average hinge loss of examples in W when weighted according to the solution q found by Algorithm 3 (scaled to sum to 1 over W ) to the average hinge loss of the clean examples W C weighted uniformly. In particular, it shows that the soft outlier-removal performed by Algorithm 3 is comparable to correctly identifying and removing the adversarial data with respect to the loss of any w ∈ B(w k−1 , r k ). Lemma C.7 is used in equation (11) of the proof of Lemma 4.7 (see below), and is the only property of W D used in the proof.
Specifically, let p denote the weighting q over W produced by Algorithm 3, scaled to sum to 1. Constraints a and b in the definition of q ensure that the total variation distance between p and the uniform distribution over W is at most ξ. Now, let (w, p) be the average hinge-loss of points in W weighted by p, and let (w, W C ) denote the average hinge loss of the clean examples W C weighted uniformly. Lemma 4.7 of Awasthi et al. (2017) relates these as follows: Lemma C.8 (Analog of Lemma 4.7 of Awasthi et al. (2017) for the A mal η noise model). There are absolute constants C 1 , C 2 and C 3 such that, with probability 1 − δ 2(k+k 2 ) , if we define z k = r 2 k + b 2 k−1 , then for any w ∈ B(w k−1 , r k ), we have (w, W C ) ≤ (w, p) + C 1 η 1 + z k τ k + κ/32 (8) and (w, p) ≤ 2 (w, W C ) + κ/32 + C 2 η + C 3 η × z k τ k .
Proof Sketch. Given the lemmas shown above, the proof now follows exactly as in Awasthi et al. (2017). In particular, the key properties of the data used are the size of the set W D , which comes from Lemma C.7 analyzed above and is used inequation (11) below, and the fact that the clean data is distributed according to D (which is true in the A mal η model). Specifically, from the lemmas above, with probability at least 1 − δ 2(k+k 2 ) , there are constants K 1 , K 2 and K 3 such that Assume these indeed hold. Equation (10) and the fact that x∈W q(x) ≥ (1 − ξ k )|W | ≥ |W |/2 imply x∈W p(x)(w · x) 2 ≤ 2K 1 z 2 k . Combining this with equation (11) and that fact that the total variation Using the fact that z k = O(τ k ), an Ω( ) bound on η is sufficient so that err D w k−1 ,b k−1 (w k ) ≤ κ with probability (1 − δ k+k 2 ). Finally, the theorem follows from an inductive argument showing that after k iterations, with high probability we have err D (w k ) ≤ M −k . In particular, since err D (w k−1 ) ≤ M −(k−1) by induction, the angle between w k−1 and w * is O(M k−1 ). Also, r k is chosen to be proportional to M −(k−1) so the angle between v k and w k−1 is also O(M k−1 ). M is chosen a sufficiently large constant so that by properties of isotropic log-concave distributions (Theorem 4 of Balcan and Long (2013)), w k has error at most M −k /4 with respect to w k−1 outside the band |w k−1 · x| ≤ b k−1 , and w k−1 has error at most M −k /4 with respect to w * outside the band. So, w k has error at most M −k /2 with respect to w * outside the band. From above, we have that err D w k−1 ,b k−1 (w k ) ≤ κ. Combining this with a bound on the probability mass in the band gives error at most M −k /2 inside the band. So, err D (w k ) ≤ M −k as desired, proving the theorem. D Supporting results for Section 6 Lemma D.1. Let (Ω, F, P ) be a probability space. Let A ∈ F and α ≤ P (A). Then we have probability spaces (A, 2 A ∩ F, P 1 ) and (Ω, F, P 2 ) such that for any S ∈ F, P (S) = αP 1 (A ∩ S) + (1 − α)P 2 (S).
Proof. If P (A) = 0, we have α = 0 and the result holds for P 2 = P and any P 1 . Also, if α = 1, we have P (A) = 1 (or, P (Ω \ A) = 0) and P 1 (T ) = P (T ) for any T ∈ 2 A ∩ F defines a probability space over A. Further, for any S ∈ F, P 1 (A ∩ S) = P (A ∩ S) = P (S) − P ((Ω \ A) ∩ S) = P (S) and the desired result holds for any P 2 .