On Optimal Learning Under Targeted Data Poisoning
Authors: Steve Hanneke
Amin Karbasi
Mohammad Mahmoody
Idan Mehalel
Shay Moran
Venue: NeurIPS 2022 Accept (2022)

Abstract: Consider the task of learning a hypothesis class $\mathcal{H}$ in the presence of an adversary that can replace up to an $\eta$ fraction of the examples in the training set with arbitrary adversarial examples. The adversary aims to fail the learner on a particular target test point $x$ which is \emph{known} to the adversary but not to the learner. In this work we aim to characterize the smallest achievable error $\epsilon=\epsilon(\eta)$ by the learner in the presence of such an adversary in both realizable and agnostic settings. We fully achieve this in the realizable setting, proving that $\epsilon=\Theta(\mathtt{VC}(\mathcal{H})\cdot \eta)$, where $\mathtt{VC}(\mathcal{H})$ is the VC dimension of $\mathcal{H}$. Remarkably, we show that the upper bound can be attained by a deterministic learner. In the agnostic setting we reveal a more elaborate landscape: we devise a deterministic learner with a multiplicative regret guarantee of $\epsilon \leq  C\cdot\mathtt{OPT} + O(\mathtt{VC}(\mathcal{H})\cdot \eta)$, where $C > 1$ is a universal numerical constant. We complement this by showing that for any deterministic learner there is an attack which worsens its error to at least $2\cdot \mathtt{OPT}$. This implies that a multiplicative deterioration in the regret is unavoidable in this case. Finally, the algorithms we develop for achieving the optimal rates are inherently improper. Nevertheless, we show that for a variety of natural concept classes, such as linear classifiers, it is possible to retain the dependence $\epsilon=\Theta_{\mathcal{H}}(\eta)$ by a proper algorithm in the realizable setting. Here $\Theta_{\mathcal{H}}$ conceals a polynomial dependence on $\mathtt{VC}(\mathcal{H})$.

On Optimal Learning Under Targeted Data Poisoning
Steve Hanneke
Amin Karbasi
Purdue University, USA steve. steve. www.hhe@ggaaillccommm com
Yale University, USA and Google Research amin karbasi @yale. edu
Mohammad Mahmoody University of Virginia, USA
Idan Mehalel
Technion, Israel i ddanmehale@@gmail.cooo
mohammad@virginie edu
Shay Moran
Technion, Israel and Google Research shaymoran @gmail..mmmm.m com
Abstract
Consider the task of learning a hypothesis class H. in the presence of an adversary that can replace up an 17 fraction of the examples in the training set with arbitrary adversarial examples. The adversary aims to fail the learner on particular target test point æ which is known the adversary but to the learner. In this work we aim to characterize the smallest achievable error = =(1) by the learner in the presence of such an adversary both realizable and agnostic settings. We fully achieve this in the realizable setting, proving that @(VC(H) 7), where Remarkably, we show that the upper bound reveal a
VC(H) the VC dimension can be attained by deterministic learner. In the agnostic setting more elaborate landscape: we devise a deterministic learner with a multiplicative regret guarantee of и C OPT O(VC(H) n7), where C' > 1 is a universal numerical constant. We complement this by showing that for any deterministic learner there is attack which worsens its error at least 2 OPT. This implies that a multiplicative deterioration in the regret is unavoidable in this case. Finally, the algorithms we develop for achieving the optimal rates inherently improper. Nevertheless, we show that for a variety of natural concept classes, such as linear classifiers, it is possible retain the dependence (x(1) by a proper algorithm in the realizable setting. Here Oμ conceals a polynomial dependence on VC(H).
Introduction
basic goal in machine learning is develop predicting model from labeled examples (i.e., training data) that can reliably generalize to unseen examples (i.e., test data). In its simplest form, namely, binary classification, a learner Lrn is given a training set S { 31).... (In, yn)}. usually assumed to be i.i.d. samples drawn from an unknown distribution D of labeled examples where x; 's are the domain instances (or data points) and yı E {0, 1} are the labels. The aim to produce mapping h = Lrn(S) that predicts the labels of fresh examples (z, 8) ~ D as accurately as possible, ie.. to minimize the population loss (h) been extensively studied in the last half century. This accumulated work resulted in fundamental mathematical characterizations regarding the nature of learnability when the training samples are truly i.i.d without any tampering by adversary [Shalev-Shwarde and Ben-David, 2014]. The goal of this paper is to offer a similar characterization in the presence of an adversary who can tamper with subset of the training data.
Pr(z,,)>~Dl (h(x)) * y). This classical setting has
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

With the emergence of sensitive machine learning applications, it is critical to ensure the trustworthy of such predictive models in the non-ideal scenarios. In this paper, we consider robust learnability when the training examples can be altered by an adversary whose goal is to make sure that target test point will be predicted incorrectly. For instance, a language model trained on conversations in shopping forums can be attacked by marketing campaigns, who may want specific product to be associated with a positive experience, instead of a bad one. Another example is an adversary who aims to fool self-driving car to speed up once it observes a stop sign. If such an adversary can somehow influence the training sets used for training the decision rules, she has all the reasons to strategically change them with the specific goal of misleading the self-driving car. As another example, consider a loan applicant who wants to make sure that his loan will be granted. If he can somehow change the training set used by the bank, he might be able to make his application approved. Note that the training set is the lens through which a learning algorithm obtains information about the underlying learning process. Therefore, once allow the training examples be tampered with by an adversary, even slightly, unexpected outcomes may take place. To quantify the robustness of learning algorithms, in this paper, we show how much the outcome of a learning algorithm for particular target test can be trusted once the training set is being altered.
(PAC) learning under instance-targeted poisoning. More formally, we consider an adversary Adv that is allowed to replace an n-fraction of the training sample S, resulting to a tampered training sample S given to the learning algorithm Lrn. Note that even though the training sample S is drawn Li.d. from a distribution D, the tampered training sample S' does not enjoy this property anymore. Such attackers are also called poisoning adversaries [Barreno, Nelson, Sears, Joseph, and Tygar, 2006), and variants of them are previously studied under the name of malicious noise [Valiant, 1985, Kearns and Li, 1993] or nasty noise [Bshouty, Eiron, and Kushilevitz, 2002]. More specifically, study poisoning settings in which the adversarial perturbation of the original sample S can also depend on the final test instance x. Due to the adversary's 's knowledge of the target test point æ, such poisoning attacks are sometimes referred to as instance-targeted poisoning attacks [Barreno, Nelson, Sears, Joseph, and Tygar, 2006]. Even without any manipulation to the training set, it is too much to ask the learning algorithm to predict correctly all the time while given only a finite number of examples to learn from. In the same vein, we can only hope to design a robust learning algorithm that is correct with high probability over the selection of (zz, y) ~ D. especially if the adversary knows the test instance (z. 3) before manipulating the training set S to S' Gao, Karbasi, and Mahmoody [2021], building on ideas from [Levine and Feizi, 2020], proved that PAC learnability under targeede poisoning attacks is achievable only when 1) = o(1). In other words, when the adversary can only change a sublinear o(n) number of n examples, then the optimal learner can achieve error (1) that goes to zero when the number of examples n goes to infinity.
1.1 Our Results
The prior work leaves several key questions open on the exact parameters of learnability under instance-targeted poisoning. Most importantly, the work of Gao. Karbasi, and Mahmoody [2021] does not quantify the error rate when the adversary's 's budget is 1) = 2(11 (e.g., if the adversary can corrupt n/100 of the examples). Secondly, Gao, Karbasi, and Mahmoody [2021] only assume the realizable setting as it is crucial for their results that all the "sub-models" trained using the bagging technique will have error that goes zero. Hence, the question of finding optimal learning rates is left open for both realizable and agnostic settings. Finally, as the developed robust algorithms are all based on "bagging" they are inherently improper learning technique.
In this work, we make progress on all the directions above and achieve optimal error rates (up to constant factors) for general n) both for the realizable and agnostic settings. We further study the proper nature of the obtained algorithms and give the first proper learning methods that are robust against instance-targeter poisoning attacks for natural hypothesis classes such as linear classifiers. More precisely, we give a characterization of the optimal error rate of learning under instance-targeted poisoning attacks with budget 1) as follows.
Realizable setting, We show that the optimal error is O(1 - d) where dl the VC dimension of the hypothesis set H. To prove this, we first present an upper bound, showing that (deterministic) learner can guarantee the error to be at most ((1d) under any instance-targeted poisoning attacks of budget 17n. We then also show a matching lower bound (up to constant factor) as follows. For any

---

nontrivial' hypothesis class of VC dimension d, we show how to design a distribution D over the examples such that no matter how the learning proceeds, there always exists an adversary of budget vn that can increase the error (under the instance-targeted attack) to ((nd). Our lower bound above holds even if the learning algorithm uses private randomness that not known to the adversary*. Our positive result, however, is deterministic, and so can be seen as satisfying the stronger guarantee, in which the adversary's perturbations to the training set is allowed to depend on learner's randomness.
Agnostic setting. We also extend our result above to the agnostic setting in which all hypotheses H have population loss bounded away from zero (even before the attack). In this setting, we devise a deterministic algorithm whose expected error on the test point is O(OPT + d), where OPT is the population loss of the best hypothesis h H.
A natural question that arises is whether one can achieve an additive regret guarantee of OPT + Onn dy? (Note that agnostic learning is usually defined with respect to additive regret). We show that this is in fact not possible, at least for deterministic learners, by presenting a negative result. In particular we show that for any deterministic learner Lrn, there is an extremely simple hypothesis class (just consisting of two functions) and an input distribution such that the learner is forced to have adversarial error 2 2OPT. This negative result uses tools from the computational concentration of products (Talagrand, 1995] and a continuity intermediate-value argument.
Proper learning. The deterministic algorithm witnessing the above upper bound is inherently improper which might be a disadvantage in terms of interpretability or test-time computational complexity. In contrast, in (the non-adversarial) PAC setting proper algorithms near optimal learning rates (up to log factors). We therefore explore the cost of proper learning under iettance-targetee poisoning attacks. We show that in many natural classes, such half spaces, it is indeed possible to obtain proper learning rules that are robust to instance-targeted poisoning attacks, with guarantees which are only polynomially worse than optimal. For example, for the class of half-spaces in I we derive a deterministic proper learning rule whose error rate is at most (d)")). At a technical level, we achieve this result by relying on the projection number of the class [Bousquet, Hanneke, Moran, and Zhivotovskiy, 2020, Kane, Livni, Moran, and Yehudayoff. 2019, Braverman, Kol, Moran, and Saxena, 2019].
known to achieve
1.2 Relation to Certification and Stability
Certification. Robustness to instance-targeted poisoning boils down to the following type of stability: on most of the test instances x; the prediction of the learner y = y(r) remains the same even if at most v) fraction of the examples in the training-set S are replaced. It is natural to require the learning rule to certify this stability. That is, a certifying learning rule provides a bound k: = k(x) along with the prediction label y = y(z). where the meaning of is that the prediction y =y remains the same even if at most k examples in the input sample are replaced. Note that it is always possible to provide the trivial guarantee of O, and therefore the goal is to design robust learners that provide non-trivial certificates. Our algorithm naturally achieves that: for = 1 - E of the test instances x it provides a guarantee of l zs ryn.
Connection to stability. We also present a new perspective on instance-targeted poisoning attacks by showing how they can be seen as natural forms of algorithmic stability [Bousquet and Elisseeff, 2002, Rakhlin, Mukherjee, and Poggio, 2005]. In particular, we show that one can study the adversarial robustness (around the true label) to rostance-targete poisoning by decoupling the (pure) stability aspect (which does not depend on the true labels) from the (non-adversarial) risk. We refer to the former the prediction stability. Roughly speaking, prediction stability requires that the model's prediction on x does not change even if the adversary changes the training set withing its budget mnn Note that here we do not care whether the model's output on x is the correct label or not, and hence is a pure measure of stability of the predictions.
It might be helpful to compare prediction stability with the algorithmic stability of [Bousquet and Elisseeff, 2002, Rakhlin, Mukherjee, and Poggio, 2005]. The later requires that for a typical sample S of size n, and for every fixed i [m]. the prediction of the model trained on S and tested on random
A non- noivirivial class H. is for which there 21, 22 E X and fu, Au H. that hu (2x) hz(21) and ha (wa) A ha (I2). In particular, any class containing at least 3 hypotheses is non-trivial. "This model is referred to as the "weak" learning model (under -asance-ttareted targeted poisoning attacks) in the work of Gao, Karbasi, and Mahmoody [2021].
3

---

test-point z is likely not changed if one substitutes the i-th example in S with a fresh random example. Prediction stability strengthens this condition in two ways: (1) the choice of what coordinate in S to change can adversarially depend on the test instance 2, (2) the adversary is allowed to change more than one examples (i.e., up to r] n).
1.3 Related Work
Poisoning attacks are studied in theoretical learning under various noise models [Valiant, 1985, Kearns and Li, 1993, Sloan, 1995, Bshouty, Eiron, and Kushilevitz, 2002]. However, these works focus on the non- non-taaget setting in which the adversary does not know the target instance.
The computational aspects of efficient learning under (non-targeted) poisoning have been studied in various works, including that of Kalai, Klivans, Mansour, and Servedio [2008], Klivans, Long, and Servedio [2009], Awasthi, Balcan, and Long [2014], with this last work obtaining nearly optimal (up to constants) learning guarantees among polynomial-time algorithms for learning homogeneous linear separators with malicious noise under distribution restrictions. That result was subsequently extended to the nasty noise model by Diakonikolas, Kane, and Stewart [2018), via techniques that also enable them to study other geometric concept classes. In the unsupervised setting, Diakonikolas, Kamath, Kane, Li, Moitra, and Stewart [2016], Lai, Rao, and Vempala [2016) studied the computational aspect of learning under poisoning. In contrast, our work focuses on (supervised) poisoning, and we study the learning rates information theoretically regardless of learner's 's computing power. The work of Steinhardt, Koh, and Liang [2017] further studied the certification of the overall (non-targeted) error. More recently, such (nn-targeeed)) poisoning attacks are combined with test-time attacks and are studied under the name of backdoor attacks [Gu, Dolan-Gavit, and Garg, 2017, Ji, Zhang, and Wang, 2017].
targeted
Besides instance-targeted attacks (which are the focus of this paper), other notions of targeted attacks were studied in the literature: for example, in model-targeted attacks, the adversary's goal is to make the learner predict according a specific model. Recent works on this model include [Farhadkhani, Guerraoui, Hoang, and Villemaud, 2022, Suya, Mahloujifar, Suri, Evans, and Tian, 2021]. Some other works study label-targeted attacks, in which the adversary's s goal is to flip the decision on the test instance to specific label (c.g., see targeted misclassification attacks in [Chakraborty, Alam, Dey, Chattopadhyay, and Mukhopadhyay, 2018]). The work of [Jagielski, Severi, Pousette Harger, and Oprea, 2021] studies a generalization of instance-targeted attacks, called subpopulation attacks, in which the adversary knows the subset of the inputs, from which the test instance will be drawn.
Most relevant to our setting are the recent works of Gao, Karbasi, and Mahmoody [2021], Blum, Hanneke, Qian, and Shao [2021] where the general problem of learning (and more quantitative variant of learning error rate) under instance-turgeted poisoning was formally defined and studied. In particular, Blum, Hanneke, Qian, and Shao [2021] studied learnability under instance-targeter poisoning where the adversary can add an unbounded number of so-called clean-label examples to the training set. A clean-label example (x. y) has the property that y the correct label of æ, while æ could be an arbitrary instance that is not sampled from the same distribution that generates other instances in the training set. Gao, Karbasi, and Mahmoody [2021] also showed that when the adversary's 's corruption is only an o(1) fraction of the training set, PAC learning is possible (if it is possible without the attack). In a concurrent work, Balcan, Blum, Hanneke, and Sharma [2022] study the problem of certifying the correct prediction even under instance-targeted data poisoning. Our methods, however, can be used to obtain certification of the stability of the model around their prediction (even though the prediction might not be true always), while controlling the overall error to be provably small (again under the instance-targeted attack).
Rosenfeld, Winston, Ravikumar, and Kolter [2020] empirically demonstrated that randomized smoothing [Cohen, Rosenfeld, and Kolter, 2019] can provide robustness against label-flipping attacks, in which the adversary is limited to merely flipping the label of a subset of the training set. They also showed that randomized smoothing can be used to handle replacing attacks (the model also studied in this paper), in which the adversary substitutes a part of the training set with new set of same size. Subsequently, Levine and Feizi [2020] used deterministic methods that further allowed attacks that can add examples to or remove them from the training set. Chen, Li, Wu, Sheng, and Li [2020], Weber, Xu, Karlas, Zhang, and Li [2020], Jia, Cao, and Gong [2020] further developed the technique of randomized bagging/subssampling for the goal of resisting instance-targete poisoning attacks.

---

Finally, we comment that other theoretical works have also studied instance-targeted poisoning attacks [Mahloujifar and Mahmoody, 2017, Etesami, Mahloujifar, and Mahmoody, 2020]. These works show how to amplify error for specific test. instances, say from 0.01 error to 0.5, through instance-targeted poisoning. In partieular, these works do not talk about the fraction of the test population that is vulnerable to targeted poisoning. The work of Shafahi, Huang. Najibi, Suciu, Studer, Dumitras, and Goldstein [2018] studied the power of such attacks empirically.
Preliminaries
Notation and basic learning theory definitions. We consider the setting of binary classification.
Let X' denote the input domain and y' = {0, } denote the label-set. A pair (z, E X x y is called an example. A sequence S = (2 ), ....., (In, yn) (X x ))" of n examples is sample of size n. The i'th example in S is denoted by S;.
A function h: X + y is called hypothesis hypothesis class, or a concept class. We denote the VC-dimension of a concept class H by d = d(H).
concept. A set of hypotheses H. ) is called an
For set 7. let 7 7. denote the set of all finite sequences with elements from Z. A learning rule or learning algorithm or learner Lrn: (X' x 3)) -> X is a deterministic" mapping which takes an input sample 5 E (X' 3)" and maps it to hypothesis Lrn(S) = h E X². If it is guaranteed that (Sn E H for all imput samples S then Lmn is said to be proper; otherwise, it is improper.
Let D be a distribution over examples, and let h be an hypothesis. The population loss of with respect to D is defined by Lp(h) Pr(x.g)>D(h(a A y] = [(e,))DD[((((() A y]]. A distribution D is said to be realizable by H if infRcH (h) 0. Similarly, for sample S, let (h)(h) = [ST E (xx.)) # y4] denote the empirical error of h with respect to S, and call a sample realizable by class H. if there exists h E H. such that Ls(h)
O. The expected loss (also called risk) of a learning algorithm Lrn w.r. a distribution D and sample size n is defined by (Lmn D) := Pr [Lrn(S) # v]. The function n + e,, DD is called the learning curve, or learning rate of Lrn w.r.t D.
For real number let [r] denote the nearest integer to In case of ties, when r r= k + 1/2 for some k Z. then define [r] = k + 1. For any finite multiset H' C H. denote by Maj(H(" the
function defined for all x E X' by (a)(H))
[ EMER h((z)
Adversarial risk and prediction stability. Before we introduce the definition of Adversarial risk, define Hamming distance between samples, which is natural way to quantify distance between samples of equal size.
Definition 2.1 (Hamming distance between samples). Fix n E N and let S, S' E (X x y)". We define the Hamming distance between S and 5" by dH(S, Σ 1[s # S:]-
Note that the Hamming distance is defined only for samples of equal sizes. dH(S, S') S 17 n, we say that S, are y--lose. For any sample S. let (S) = (S' dH S nn
Definition 2.2 (ny-adversarial risk). Let E (0, 1) be the adversary's budget, let Lmn be a learning rule, and let / be distribution over examples. The njudveeraaial risk of Lrn w.r. D and sample size n is defined by
Adv n (Lrn) ==
Pr (2.9->
[3 E BS) Lrn(S") # v).
Thus, robust learning with respect to targgnee poisoning with budget 17 boils down to minimizing the adversarial risk. Indeed, given an input sample S and a test example (z. y), an adversary with budget y can force mistake on x if and only if Lrn(") A y for some S' E B,()
Randommess. In Definition 2.2 above we define adversarial risk for the setting in which both the learner Lm and the model h = Lrn(S) are deterministic. When either Lrn or h is allowed to use randomness, then the notion of adversarial risk as defined in Definition 2.2 can be extended in several ways, depending on whether the adversary can see the randomness of the learner or not. Some of these variations are discussed in the work of Gao, Karbasi, and Mahmoody [2021]. We remark
In Appendix B, we extend the definition in way that captures also family of randomized leamers.
5

---

however that our results in the realizable setting apply to all variations. This is simply because our upper bounds are achieved by deterministic learners, whereas our lower bound uses the weakest type of an adversary (which does not depend on the randommess of the learner). In contrast, our lower bound the agnostic setting applies only to deterministic learners.
Explicit bounds. We do not try to optimize the constants hidden in the (()), notation in the derived bounds. The reason is because on the one hand, this way the proofs are simpler and more accessible, and on the other hand, we do not know how to get tight (or nearly tight) lower and upper bounds on the constants. Obtaining tight bounds is natural direction for future research; we elaborate on this in Section 5. Nevertheless, the complete proofs (which are given in the appendix) include explicit numerical bounds on the constants.
Decoupling adversarial risk into stability and risk. is convenient and illustrative to decouple robust learnability two properties: small expected loss and prediction stability. The latter means that the prediction of the learning algorithm on a random test point is stable under replacing a bounded amount of examples from the training set:
Definition 2.3 (Prediction stability). Let n N, o, E (0, 1). Let Lrn be learning rule and D be a distribution over examples. We say that the learning rule Lmn is (ni a, n1) predictionn stable with respect to D if the following holds
Pr (L D, S-D"
ES' E B,(() LL)()) & Lmn(S( aa
where Dr is the marginal distribution induced by D on the domain X.
Of course, prediction stability alone does not guarantee robust learning. Indeed, useless learning rule that always outputs the all 0's classifier has maximal stability. At the very least, the learning rule should learn the class in the classical sense (in the absence of an adversary). The following observation asserts that prediction-stable learning rules with small loss are robust learners:
Observation 2.4 (Prediction stability small error = robust learning). Let Lrn be a learner and D distribution over examples. Then,
max
X,, (Lrm) D, n)} S (L(m))))n)) S (L(n))) D, + D)r
In other words, if Lrn is (n, o, preddiciii stable with respect D whose expected population loss is én. (.rL))))) S e. Then Lrn learns D with an adversarial expected loss a e.. Conversely, if e., (LLL))) D,1) < then Lrn is (n, e, -)-prediccioon stable with respect D and its expected population loss is also En (Lrn) D) < E. We leave the (simple) proof of Observation 2.4 to the reader.
3 Realizable Setting
Theorems 3.1 and 3.3 below characterize the optimal adversarial risk in the realizable setting.
Theorem 3.1 (Realizable case positive result). There exists a constant e1 >> 0 so that the following holds. Let H be a hypothesis class with VC dimension and let Tj E (0,1), 1). Then there exists learner Lrn having T-aaversarial risk
Adv (Lrn) S cind
for any distribution D realizable by H and for any sample size n 2 1/n.
We prove Theorem 3.1 in Appendix A.
Note that the requirement that the sample size is n 1/n is necessary since otherwise 17 < 1, which means that the adversary cannot modify the input sample, and so this case reduces to classical learning without an adversary.
Theorem 3.1 is proven using the STABLE PARTITION AND VOTE (or SPV, for short) algorithm, described in Figure 1. The meta-algorithm is based on the idea of partitioning and then voting used in [Gao, Karbasi, and Mahmoody, 2021], but with a more refined and precise analysis. The partition and vote technique works as follows. First, partition the input sample to subsamples of a carefully chosen size. Then, train a given learner (which is called the input learner SPV) on each subsample, and finally let the trained learners vote determine the output label. The size of each subsample

---

SPV: STABLE PARTITION AND VOTE
Input: Stability parameter 7 E (0, 1), learning algorithm Lrn and an input sample ~ 5 where n 2 1/7.
Output: A classifier h: v.
1. Partition S into [7mm]] consecutive subsamples such that all first t [7mm] subsam- ples are of size at least 7n Denote the i'th subsample by 5
2. For all i [t]. run the learning algorithm Lrn on 8 to obtain hypothesis
h, Lrn(S(()).
3. Return the hypothesis h defined as follows for all x E X
l(x) = Maj (4))
Figure 1: SPV A meta algorithm implementing a stable version of the input learning algorithm Lrn.
trades-off, in a way, expected loss and prediction-stability. perform poorly on each subsample. On the other hand, if it is relatively large then the number of learners that participate
it is too small, the given learner will
the majority vote is small and the adversary can poison large fraction of these learners and flip the overall majority vote. We elaborate on this when proving Theorem 3.1. Notice that the time complexity of SPV is proportional to the time complexity of the learner Lrn.
To state the complementing impossibility result, we need the following definition of non-trivial concept classes [Bshouty, Eiron, and Kushilevitz, 2002].
Definition 3.2 (Non-trivial concept classes). We say that a concept class H over domain X is non-trivial, if there are 2 x2 X and h1, h2 H so that h1 (x1) = h2(x1) and h (x2) # h2(22). impossibility result). There exists constant C2 so that the following holds. Let H be a non-trivial hypothesis class with VC dimension d and let E (0, 1). Then, there exists distribution D realizable by H. that every learner Lrn has nyadversarial risk
Theorem 3.3 (Realizable
Adv (Lrn) D.n) 2 min(c2nd, 1/100]
for any sample size n 2 1/n-
We note that this impossibility result applies also to a variety of randomized learners; we elaborate on this in Appendix B, where we also prove Theorem 3.3.
The above lower bound demonstrates how vulnerability to targaeee attacks depends greatly on the hypothesis class we want to learn, and specifically on its VC-dimension.
3.1 Certification
Besides prediction-stabiiee another useful property our SPV meta-algorithm has is the ability to efficiently calculate and output a certificate for the stability of its predictions. Formally, given an input sample S, certificate is function 1/5 X' [0, 1], outputted by learner in addition to its output hypothesis hi such that the following is satisfied: hs(x) = hs (x) for every point x and for every input sample S' which nss (=(x)) (z)-los S. one ignores computational considerations.
outputting optimal certificates is always possible:
Definition 3.4 (Optimal Certificate). Let Lrn be any learning rule, and let S an input sample. Define the optimal certificate v7 (.) = 17" (-15) of Lrn on input sample S as follows. The optimal certificate 17 (x: .S) is equal to where l is the largest integer for which Lrn(S'((z) = (z) for every sample S' with hamming distance at most from S.
In other words, if S is sample that was corrupted by adversary with budget such that 7) S 17 (x|S) then the output label (rn(S)(x) is equal to the label that would have been outputted if the learner trained with the uncorrupted sample.
The issue with the optimal certificate 17" (xr) that can be impossible to compute as it requires to iterate over the potentially infinite space of all samples S' of hamming distance most 77(z) from
7

---

PSPV: PROPER STABLE PARTITION AND VOTE
Input:
Stability parameter 7 E (0, proper learning algorithm Lrn, and input sample S ~ D where n. 2 1/17.
Output: A classifier h H.
1. Partition S into [5kp consecutive subsamples such that all first t 7
subsamples are of size at least 3kp" Denote the i'th subsample by S
2. For all í [t]. train Lrn, on S to obtain hypothesis h; Lrnn
3. Return h H such that
h(x)) Maj
(x)
holds for all x E Ae
Figure 2: PSPV A meta-algorithm that implements stable version of the input proper learning algorithm Lrnp and maintains properness.
the input sample S. In contrast, our SPV learner can efficiently calculate a non-trivial lower bound on 1y" which therefore also serves as a certificate. The key property which enables this the fact that its output hypothesis is the majority vote of base learners, each trained disjoint subsample. This summarized in the following proposition:
Proposition 3.5. Consider leurner whose oulput hypothesis is given by a majority vole of learners Li,..., La that are trained on l. disjoint subsamples S1, Si,...,,y, St. of the input sample S. Define
n(x|S)= = 1 [Eient
. (1((()) v) - Eieno 1 + -1).
2
where h4 is the outpul hypothesis of Li y is the output label of the majority vote of the L 's, and n is the size of the input sample S. Then, n(z[S) 17" (x|8).
Proof. Notice that n S) + 1 is equal to the minimal number of h1's whose prediction on w must be flipped in order to enforce that Ki h+(2)) = y} S li hz(z) * y)1. Therefore, at least one example in each S; such that h; (z) = must be replaced in order to change the prediction of (rn(S) on z. In particular, if only n n[>[S) (S) examples are replaced than the prediction of Lrn (S) on remains the same. This implies that 77 (x 2 T/(x))) as stated.
In light of Proposition 3.5, our SPV learner can efficiently compute and output certificate n)xx) which is proportional to 7/ (where is the stability parameter given to SPV), with probability proportional
to the expected loss of the input learner given to SPV when executed on sample of size
7n
3.2 A Proper Variant of SPV
We now present a proper version of SPV for classes H. with finite projection number, described in Figure 2. The projection number concept class H. is denoted by kp = (?)) (we present its definition after the statement of Theorem 3.6 below). In particular, for the class of halfspaces it yields a robust learner with the following guarantee:
Theorem 3.6. There exists a constant e >> so that the following holds. Let the class of halfspaccs over Bdd for some d 2 1, and let (0, 1). Then, there exists proper learner Lrn having apadversarial risk
e,, (Lrn) D, n) S enjd for any distribution D realizable by H and for any sample size n. 2 1/n.
The proof of Theorem 3.6 is deferred Appendix C.
To derive Theorem 3.6, we reinforce the SPV algorithm with technique introduced by Kane, Livni, Moran, and Ychudayoff [2019] and further developed by Bousquet, Hanneke, Moran, and

---

Zhivotovskiy [2020]. This technique allows in certain cases to project majority vote of hypotheses from the class H back to H. Its applicability hinges on a combinatorial parameter called the projection number. The PSPV learner explicitly uses the projection number, so for completeness we give its definition below. The interested may see the work of Bousquet, Hanneke, Moran, and Zhivotovskiy [2020] for an insightful discussion on the role of the projection number in proper learning.
Definition 3.7 (Projection Number). Let H. be a concept class. For any l 2 and for any multiset H'' H define the set Azy. to be the of all x X, for which the number of hypotheses in H' that disagree with Maj(H") is less than [7(1 |HL'/e.. The Projection Number of the class H. denoted kpp (H), is defined to be the smallest E so that for any finite multiset H' H. there exist h H such that h(x) = Maj(?l) (x) for all x E Xze, .. If no such & exists then kg = 0C.
4 Agnostic Setting
In this section, extend the results robust learnability to the agnostic case. First, by simple generalization of the positive result for the realizable case, we provide a robust semi-agnostic learner. That is, our learner has adversarial risk depending linearly on OPT OPT(H, D) minNEH (h). While semi-agnostic learning is considered not ideal in many cases, we complement our positive result by showing that aanisagnottcc learning unavoidable when the goal is to design a robust and deterministic (as ours) learner for the agnostic setting.
4.1 A Semi-agnostic Learner
Formally, a semi agnostic learner is defined follows. Let E R. A learning rule Lrn is semi agnostic learner if the following holds. Let H be a concept class and let D be a distribution examples. Then there exists excess ervor rate Aen N [0, 1] such that c.,(Lm) D) I cOPT + e (n)) where OPT = infRCи (h).
Before stating our positive result in this setting, we first discuss how achieving adversarial risk Odd(PPT - 1) is possible by reduction to the realizable setting.
Reduction to the realizable setting. Suppose learner is given training set S" of size n that comes with ym replacements made by the adversary on the original set S. Moreover, suppose that S is sampled from distribution D such that the best roughly OPT fraction of S does not match to h. Therefore, one can see S' as first sampled from D (without noise) followed by x (1) + OPT) y replacement corruptions. This way, one employ learner that can tolerate v/ = 1 + OPT fraction of adversarial corruptions in the realizable setting and obtain total adversarial risk (d(OPT + 17).
76 has OPT eтror on D. This means that,
The above discussion raises a natural question: can learner achieve adversarial risk O + dn) or even (ideally) OPT + (dn)) The latter is the typical type of risk bound in agnostic settings, where there is no multiplicative dependence on OPT in the risk.
The following theorem, which we prove in Appendix D states the positive result.
Theorem 4.1 (Positive result for the agnostic case). There exist constants C1,C2 so that the following holds. Let H be hypothesis class with VC dimension d and let n) E (0, 1). Then, there exists learner Lrn having 7-adversarial risk
Adh (Lmn) n) S c2 OPT c1 d d.1)
for any distribution D over examples and for any sample size n 2 1/n.
As in the realizable case upper bound, the above upper bound is proved by using the SPV meta-learner. The main difference is that to prove this result we use a different input learner Lrn given to SPV than the
in the realizable case.
4.2 Ruling Out Agnostic Learning
Note that Theorem 4.1 only proves the existence a semi-agnostic learner under instance-targeted poisoning. A more desirable goal would be to obtain (standard) agnostic learners whose error under the attack OPT + d where / a vanishing (additive) error term when v) -> O. Here we will prove that at least when it comes deterministic learners, such goal is out of reach, and the best we can

---

hope for is 2OPT plus additive terms that depend on 77 and the VC dimension. This explains why we can only achieve semi-agnostic learner.
The following theorem, which we prove in Appendix shows that in Theorem 4,1, 1, the constant Ci needs to be at least and the standard way agnostic learners bound their regret is not possible for instance-targeted poisoning.
Theorem 4.2 (Impossibility of agnostic learning). Let E (0. 1),n n N. For any hypothesis class H. that has at least two hypotheses and for any deterministic learner, there is distribution D over (two) examples and 1) = n/ + O(1/v1)) such that Lrn has n-adversarial risk
Adv (Lrn) 2 2OPT + 2(6') (11/m).
Conclusion and Open Questions
In this work, we studied the optimal rate of learning for binary classification problems under instance- targeted poisoning. We showed that in the realizable setting the error rate can be characterized up to constant factor and proportional both adversary's budget and the VC dimension of the class. In the agnostic setting, we proved a perhaps surprising lower bound that standard agnostic learning (with additive regret compared the optimal error in the no-attack setting) impossible for deterministic learners, and also complemented this with positive result using semi-agnostic learner. We also showed how make our learners proper in variety of interesting settings.
Our work leaves a few interesting directions for future research.
Finding the exact constant in the realizable case. Our results in the realizable case characterize the optimal adversarial risk up to a constant multiplicative factor the sense that there exist constants C1, C2 that achieving 7-adversarial risk of ci pll is possible for any hypothesis class with VC-dimension d, whereas obtaining 7-adversarial risk of c2nd can't 'tn't be achieved for any hypothesis class with VC-dimension d. However, there is large gap between C1, C2. Can we close or shrink this gap?
Finding the correct multiplicative factor in the agnostic case. Our results show that in the agnostic case, there must be a constant C so that the best adversarial risk attainable is C' OPT. What is the value of C?
Characterizing proper robust learning. In the proper and realizable case, our stable learner for linear classifiers depends on d3 while our lower bound depends linearly on d, as in the general improper case. remains open to identify the correct dependence on d.
Characterizing the role of randomness. Our impossibility result for the agnostic learning (Theorem 4.2) only applies deterministic learners. It remains open either effectively use randomness during the learning (known or unknown to the adversary) and obtain an agnostic learner, or to extend the negative result cover such randomized learners as well.
Acknowledgments
Amin Karbasi acknowledges funding in direct support of this work from NSF (185-1845032, ONR (N00014- 19-1-2406), and the AI Institute for Learning-Enabee Enabled Optimization Scale (TILOS). Mohammad Mahmoody is supported by NSF grants CCF-191061 and CNS 19369967 Shay Moran is Robert J. Shillman Fellow; he acknowledges support by ISF grant 1225/20, by BSF grant 2018385, by an Azrieli Faculty Fellowship. by Israel PBC-VAIAT, by the Technion Center for Machine Learning and Intelligent Systems (MLIS), and by the the European Union (ERC, GENERALIZATION. 101039692). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. We thank anonymous NeurIPS 2022 reviewers for helping us to improve this paper, and for pointing out good motivating examples.
10

---

References
Awasthi, M. Balcan, and P. M. Long. The power of localization for efficiently learning linear separators with noise. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 449-458, 2014.
Maria-Florins Balcan, Avrim Blum, Steve Hanneke, and Dravyansh Sharma. Robustly-reliable learners under poisoning attacks. arXiv preprint arXiv:2203.044 2022.
Marco Barreno, Blaine Nelson, Russell Sears, Anthony D Joseph, and Doug Tygar. Can machine learning be secure? In Proceedings of the 2006 ACM Symposium on Information, computer and communications security, pages 16-25. ACM, 2006.
Avrim Blum, Steve Hanneke, Jian Qian, and Han Shao. obust learning under clean-label attack. In Conference Learning Theory, 2021.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-5266 026,,-262220000 2002.
Olivier Bousquet, Steve Hanneke, Shay Moran, and Nikita Zhivotovskiy. Proper learning, helly number, and an optimal sym bound. In Conference on Learning Theory, pages 382-609. PMLR, 2020.
Mark Braverman, Gillat Kol, Shay Moran, and Raghuvansh Saxena. Convex set disjointness, distributed learning of halfspaces, and ip feasibility. arXiv preprint arXiv: 2019.
Nader H Bshouty, Nadav Eiron, and Eyal Kushilevitz. Pac learning with nasty noise. Theoretical Computer Science, 288(2):255-275. 2002.
Anirban Chakraborty, Manaar Alam, Vishal Dey, Anupam Chattopadhyay, and Debdeep Mukhopad- hyay. Adversarial attacks and defences: A survey. arXiv preprint arXiv: 111118000000. 2018.
Ruoxin Chen, Jie Li, Chentao Wu, Bin Sheng, and Ping Li. A framework randomized selection based certified defenses against data poisoning attacks, 2020.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. International Conference on Machine Learning, pages 1310-1320. PMLR, 2019.
I. Diakonikolas, D. M. Kane, and A. Stewart. Learning geometric concepts with nasty noise. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1061- 1073, 2018
Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high dimensions without the computational intractability. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 655-664. IEEE, 2016.
Omid Etesami, Saeed Mahloujifar, and Mohammad Mahmoody. Computational concentration of measure: Optimal bounds, reductions, and more. Proceedings of the Fourteenth Annual ACM-SIAM Symposium Discrete Algorithmss, pages 345-363. SIAM, 2020.
Sadegh Farhadkhani, Rachid Guerraoui, Lê- Lê-Nguyên Hoang, and Oscar Villemaud. An equivalence between data poisoning and byzantine gradient attacks. International Conference on Machine Learning, pages 0284-6323 PMLR, 2022.
Ji Gao, Amin Karbasi, and Mohammad Mahmoody. Learning and certification under instance-targeted poisoning. In Uncertainty in Artificial Intelligence, pages 2135-2145. PMLR, 2021.
Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg. Badnets: Identifying vulnerabilities in the machine learning model supply chain. arXiv preprini arXiv: /00v::/77.0066 06733, 2017.
David Haussler, Nick Littlestone, and Manfred K Warmuth. Predicting {0, ffunctios on randomly drawn points. Information and Computation, 115(2):248 292, 1994.
Matthew Jagielski, Giorgio Severi, Niklas Pousette Harger, and Alina Oprea. Subpopulation data poisoning attacks. Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pages 3 3104-3122 2021.

---

Yujie Ji, Xinyang Zhang, and Ting Wang. Backdoor attacks against learning systems. In 2017 IEEE Conference on Communications and Network Security (CNS), pages 1-9. IEEE, 2017.
Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Intrinsic certified robustness of bagging against data poisoning attacks. arXiv preprint arXiv:2008.0444 2020.
A. T. Kalai, A. R. Klivans, Y. Mansour, and R. A. Servedio. Agnostically learning halfspaces. SIAM
Journal on Computing, 3776):177--1855, 2008
Daniel Kane, Roi Livni, Shay Moran, and Amir Yehudayoff. On communication complexity of classification problems. In Conference on Learning Theory, pages 1903-1943, PMLR, 2019.
Michael Kearns and Ming Li. Learning in the presence of malicious errors. SIAM Journal on Computing, 22(4):807-885 1993.
A. R. Klivans, P. M. Long, and R. A. Servedio. Learning halfspaces with malicious noise. Journal of Machine Learning Research, 10(12), 2009.
Kevin A Lai, Anup Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium pages 665-674 IEEE, 2016.
Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defenses against general poisoning attacks. In International Conference on Learning Representations, 2020.
Philip M Long. The complexity of learning according to two models of a drifting environment. Machine Learning, 37(3):337-354, 1999.
Saeed Mahloujifar and Mohammad Mahmoody, Blockwise p-tampering attacks on cryptographic primitives, extractors, and learners. In Theory of Cryptogruphy Conference, pages 245-279, Springer, 2017.
Alexander Rakhlin, Sayan Mukherjee, and Tomaso Poggio. Stability results in learning theory. Analysis and Applications, (04)):997444 2005.
Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and Zico Kolter. Certified robustness to label- flipping attacks via randomized smoothing. In International Conference Machine Learning, pages 8230-8241. PMLR, 2020.
Ali Shafahi, W Ronny Huang. Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Dumitras, and Tom Goldstein. Poison frogs! targeted clean-label poisoning attacks neural networks. Advances in neural information processing systems, 31, 2018
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Robert H. Sloan. Four Types of Noise in Data for PAC Learning. Information Processing Letters, 54 (3):157-162, 1995.
Jacob Steinhardt, Pang Wei Koh, and Percy Liang. Certified defenses for data poisoning attacks. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 3520-3532. 2017.
Fnu Suya, Saeed Mahloujifar, Anshuman Suri, David Evans, and Yuan Tian. Model-targeted poisoning attacks with provable convergence. In International Conference on Machine Learning. pages 10000. PMLR, 2021.
Michel Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Publications Mathématiques de l'Institut des Hautes Etudes Scientifiques, 81(1):33-255 1995.
Leslie G Valiant. Learning disjunction of conjunctions. In IJCAI, pages 560-566, 1985.
Vladimir Vapnik and Alexey Chervonenkis. Theory pattern recognition. 1974.
Maurice Weber, Xiaojun Xu, Bojan Karlas, Ce Zhang, and Li. Rab: Provable robustness against backdoor attacks. arXiv preprint 2889944,00. 2020.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "zcerpN-aPxk", "reviewer": "Reviewer_qCAz", "summary": "This work studies learnability under a targeted poisoning attack.  Specifically, they consider the best achievable error in both the realizable and agnostic settings.  Their method focuses on $\\ell_0$ attacks and is fundamentally based on the ensemble-based robustness proposed by Levine and Feizi [2020].", "questions": "Section 2: Can you clarify what you mean when you wrote \"observe that when both the learner and the output model can be randomized, and if the learner is improper, then the whole process of training and testing can be delegated to 'testing time'\"?\n\nIt is not obvious to me why your method is strictly limited to only the binary classification case.  It seems it should extend to multiclass classification where the difference is w.r.t. to the two most popular classes.  \n* Can you comment on this multiclass case and why it seems not to apply?  Was it simply a simplification for the analysis or a technical limitation?\n\nThis paper focuses on a single target instance $x$.  Increasingly the focus is shifting to subpopulation attacks [Jagielski et al. 2022] and defenses, where the attacker targets multiple (test instances) and the defender provides certification bounds on multiple instances simultaneously.\n* Have you considered how your bounds change under such scenarios?  I understand this question is not the focus of this particular work so \"No\" is a perfectly acceptable answer.", "limitations": "The authors do not include a \"Limitations\" section nor did I expect one for this type of theory paper. \n\nI would have preferred some intuition in the main paper regarding the origin of the \"carefully chosen\" subset sizes in Figures 1 and 2.\n\nWhile the writing overall was clear, the number of typos was a problem, and if this paper is accepted, it needs thorough proofreading.  Some errors are more egregious than others.\n* Lines 153 & 155 \"Gao et al. Gao et al.\" as well as \"Balcan et al. Balcan et al.\"\n* Line 284: \"Besides of Prediction\" -- two issues\n* Line 32: \"ensure the trustworthy of such\" \n* Line 339 & 346 regret bound\nLine 39: \"can can\"", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This work follows in a long tradition of learnability under \"noise\" (defined broadly).   In particular, the authors address several open questions from previous work.  For example, Gao et al. prove a general bound of $o(1)$ but do not consider specific poisoning fractions, e.g., ${\\eta = \\frac{1}{100}}$.\n\nOverall, I enjoyed reading this paper.  Its organizational structure was clear.  The ordering of the arguments allowed me to easily follow along without having to go back and re-read previous sections. I thought it was well done.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "i0XR07Pnoxa", "reviewer": "Reviewer_t9Qw", "summary": "This paper studied developing robust algorithms in presence of an attacker who can corrupt a portion of the training set in the classical version space learning scenario. In the realizable scenario, the paper provided impossibility result that shows if the attacker can perturb eta fraction of training samples, then the test accuracy cannot be lower than eta*d with high probability, where d is the VC dimension of the hypothesis class. To complement this result, the paper then proposed robust PAC learning algorithms that provably achieve this upper bound, which perfectly closes the robust learning problem in the realizable case. In the agnostic scenario, the paper showed that no algorithms can achieve 2*OPT test accuracy, where OPT is the optimal error rate without poisoning. Then the paper proposed a robust algorithm that achieves O(OPT)+delta error, where delta depends on the VC dimension.", "questions": "(1). Whether the threat model considered in this paper is targeted or untargeted poisoning attack?\n\n(2). How tight is the error upper bound in the agnostic scenario?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n(1). The paper provided a very comprehensive study of PAC learning under data poisoning attacks. When the attacker can corrupt eta fraction of the training set, the paper showed impossibility result and proposed robust PAC learning algorithms that achieve the error lower bound. This result is fundamental as it extends PAC analysis from traditional machine learning to the robust machine learning domain.\n\n(2). The theoretical results developed in this paper is important. The proof techniques are novel and can be used to study related topics in future research. The topic is extremely fundamental in the machine learning community, which help researchers builds deep understanding of data poisoning attacks.\n\n(3). The paper is well-written and the structure is articulated in a very clear way. The annotation goes from realizable scenario to the agnostic scenario, which makes the paper easier to read and understand.\n\nWeaknesses:\n\n(1). I think the threat model studied in this paper is \"untargeted data poisoning attack\" instead of \"targeted poisoning attack\". In typical targeted poisoning attack, the goal of the attacker is to change the prediction on a test example to a pre-specified target label. However this paper considered poisoning attacks that aim at reducing the test-time accuracy overall, which is often consider as untargeted poisoning attacks. I suggest the authors check if the terminology is aligned with the SOTA literature.\n\n(2). In the agnostic scenario, while the paper proved that no learners can achieve 2OPT error rate under data poisoning attacks. It's not very clear how the upper bound O(OPT)+delta compares to the lower bound. That said, I am not sure if the upper bound achieved by the proposed robust PAC learner is tight or not. I hope that the authors could elaborate more on this point.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZrGzdLGDIS", "reviewer": "Reviewer_nSt5", "summary": "This work studies the optimal rate of learning for binary settings under a fraction of $\\eta$ poisoning data under targeted data poisoning attack. Under realizable setting, the error rate is proportional to $\\eta$ and the VC dimension of the hypothesis set, which can be attained by a deterministic learner. Under agnostic setting, for any deterministic learner, a lower bound is present to show an inevitable multiplicative deterioration in the regret.", "questions": "1. I’m wondering whether the bound would change if we switch the poisoning attack to non-targeted poisoning attacks. Also, whether there’s any concrete algorithm for the targeted poisoning attack. \n\n2. For the agnostic cases lower bound, I’m wondering whether considering certain noise settings (i.e. Massart noise, Tsybakov noise) will eliminate the additional multiplicator on OPT.\n\n3. For sec 3.2, I’m wondering whether there’s a lower bound when considering proper learner. \n\n4. The author has a discussion on the potential role of randomness on page 5, but I think it should be more clear if first put more work into describing deterministic vs randomness in terms of learning rules and models by either giving examples or giving formal definitions. In the middle of the discussion, the author then mixed randomness and improper learning together. I understand the author may express the idea of improper learners like majority vote involves randomness in the model or learning rule, but it’s unclear currently from the text what’s the take-home message.  Moreover, if the learning rule introduces any randomness,  I’m wondering whether there’s any literature studying the scenario where the attacker can also get access to the random seed.\n\n5. For the discussion of prediction stability, I think the author is trying to make a difference between robustness and astuteness, which I suppose has been clarified in [1] before. Though here the context is under data poisoning attack, since the idea is the same, it might be good to make a comparison.\n\n6. In section 4, it'd be helpful to give a formal definition of semi-agnostic learning.\n\n7. In figure 2 PSPV, what’s the definition of $X_{\\{h_1,\\ldots,h_t\\},2k_p}$. Moreover, does PSPV only limited to linear classifiers or there are no constraints on the hypothesis set. Since the only difference between SPV and PSPV is the latter output $h\\in\\mathcal{H}$, yet both of $h$ are computed via $Maj$, then how can you guarantee the hypothesis computed in PSPV belongs to $\\mathcal{H}$?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This work shows that under the realizable case the adversarial risk bound is tight in terms of corruption fraction and VC dimension of the hypothesis set.\n2. This work provides a lower bound on the adversarial error for agnostic setting.\n\n\nWeaknesses:\n1. I find the poisoning scenario that is described a bit confusing. Notice that targeted poisoning can also be regarded as selecting a targeted label $y_t$, and adding poisoning data to make the test sample misclassify as the targeted label $y_t$. But here to my understanding, the targeted poisoning is the adversary can see the test sample ahead of time so that the adversary can add poisoning data to make the test sample misclassify. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "P9-GZvtafFB", "reviewer": "Reviewer_dWRe", "summary": "The paper information-theoretically studies the possibility and impossibility of learning from poisoned data, in a supervised learning setting with deterministic model predictions, against a relatively powerful attacker who knows the data $x$ on which the model will be tested (or deployed). Remarkably, in the realizable setting, they prove matching upper and lower bounds, up to a multiplicative constant. Namely, this error is $\\Theta(\\eta d)$, where $\\eta$ is the fraction of poisoned data and $d$ is the VC dimension of the class of hypotheses.\n\nIn the agnostic setting, the paper also provides interesting lower and upper bounds, though the gap is then arguably larger. Namely, they prove that the error is at least (roughly) $2 OPT + \\Omega(\\eta) - o(1)$, for a large number of training data, while their upper bound only guarantees $\\mathcal O(OPT + d \\eta)$.\n\nThe authors also note that their solution in the realizable setting is not proper (the learned hypothesis aggregates the predictions of several hypotheses). In the specific case of halfspace learning, they propose a construction of a proper hypothesis, but the guarantee is significantly worse ($\\mathcal O(\\eta d^3)$).", "questions": "It would also be helpful if the authors could provide actual values for the constants, so that the readers can better understand the gap between the positive and negative results. I have seen that most of these constants are available in the Supplementary Material. I would suggest to add them to the main paper. In particular, could the authors provide the value of $c_2$ in Theorem 4.1? This constant seems especially important, as it is non-vanshing even when $\\eta \\rightarrow 0$.\n\nAs far as I understand, SPV, which has provable guarantees, is also very practical. In particular, it seems to have the same time-complexity as the oracle Lrn which it leverages. Is this the case? If so, I would encourage the authors to mention it in the paper (I fully appreciate the information-theoretical impossibility theorems, but it is even better if the positive theorems are computationally tractable).\n\nIt is frustrating that the algorithm used to provide the guarantee of Theorem 4.1 is not described, even informally. Would it be possible to at least provide an intuition of this algorithm?\n\nAdditionally, the time complexity of this algorithm is not discussed. Can the authors say a few words about it?\n\nFinally, there have been lower bounds proved for Byzantine heterogeneous learning. How do these relate with the authors' lower bounds?\n- https://proceedings.neurips.cc/paper/2021/hash/d2cd33e9c0236a8c2d8bd3fa91ad3acf-Abstract.html\n- https://openreview.net/forum?id=jXKKDEi5vJt\n- https://arxiv.org/pdf/2202.08578.pdf", "limitations": "It is a shame that the introduction examples that motivate the paper are unconvincing. It is indeed unclear how and why an adversary would fool autonomous cars into accelerating when shown a stop sign. It is also unclear how a loan applicant could poison a bank’s training set.\n\nI strongly urge the authors to provide much more compelling examples, which I think are numerous. For instance, in content moderation, a troll farm employed by an authoritarian regime or a multinational firm could flag dissents’ and critics’ content on social medias to fool the moderation algorithm into considering that all such critical content should be taken down. As another example, a language model trained on “social media conversations” (like PaLM https://arxiv.org/abs/2204.02311) could be hacked by propaganda and marketing campaigns, who may want the word “meat” to be systematically associated with “delicious” rather than “not environmental-friendly”. Today, the training datasets of such algorithms are arguably full of poisonous attacks (Facebook reports removing 15 billion fake accounts every two years: https://www.techdigest.tv/2021/09/facebook-removes-15-billion-fake-accounts-in-two-years.html).\n\nIn particular, the attacker’s knowledge of $x$ can be justified in practice by the fact that, in may use cases where the model is trained on user-generated data, attackers are also users who will interact with the trained algorithm, and provide the values of $x$ that the model will process. This use case belongs to the family of backdoor attacks, which the paper would gain by mentioning.\n\nI believe that the authors should also discuss the role of $d$. Their lower bounds essentially prove that larger models are more vulnerable to adversarial attacks. This is a very important discovery, as it strongly suggests that the race for ever larger models is also leading to significantly more vulnerable models (if we are to believe the paper).\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I believe that this paper is an exciting important step towards understanding the possibility and impossibility of learning. So far the literature has only provided guarantees in the case of a vanishing fraction of poisoned data. However, especially in applications like online content moderation, this assumption is very unrealistic. Arguably, as a model gains more users, while it gains more data, it also attracts more malicious users, which may thus represent an increasing fraction of the provided data. Given this, I believe that the paper provides an original and very significant contribution to the important literature on adversarial machine learning.\n\nThe paper is well-organized, but there are many typos which make the reading challenging at times. Below is a list of such typos (the list is not exhaustive):\n- Line 53: “Due to adversary” => “Due to the adversary”\n- Line 58: “even if the adversary knows” => “especially if the adversary knows”\n- Line 66: “the Gao et al. [2021]” => “Gao et al. [2021]”\n- Line 153: “Gao et al. Gao et al. [2021]” => “Gao et al. [2021]”\n- Line 155: “Balcan et al. Balcan et al. [2022]” => “Balcan et al. [2022]”\n- Line 156: “under instance targeted” => “under instance targeted attacks”\n- Line 161: “Rosenfeld et al. Rosenfeld et al. [2020]” => “Rosenfeld et al. [2020]”\n- Line 209: “depend its changes” => “make its changes depend”\n- Line 212: “based on adversary’s power” => “based on the adversary’s power”\n- Line 216: “In Definition B.1 present” => “In Definition B.1, we present”\nAlso, the word “semi-agnostic” is not defined in the paper.\n\nFinally, the paper should clarify the difference between what they regard as “targeted attacks”, and what is sometimes known as “model-targeted attacks”, where attackers want a specific target hypothesis to be learned.\n- https://proceedings.mlr.press/v139/suya21a.html \n- https://arxiv.org/pdf/2202.08578.pdf (to appear in ICML’22)\n\nEDIT after reading the authors' responses:\nThe authors' responses were satisfactory to me, which motivated me to increase my rating.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept