Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness
Authors: Bogdan Chornomaz
Yonatan Koren
Shay Moran
Tom Waknine
Venue: NeurIPS 2025 spotlight ()
Keywords: Learning theorey
Data Poisoning
Primary area: theory
TL;DR: Giving tight bounds for the acess loss in the Agnostic Learning under Targeted Poisoning modle unsing randomized learnes.

Abstract: We study the problem of learning in the presence of an adversary that can corrupt an $\eta$ fraction of the training examples with the goal of causing failure on a specific test point. In the realizable setting, prior work established that the optimal error under such instance-targeted poisoning attacks scales as $\Theta(d\eta)$, where $d$ is the VC dimension of the hypothesis class [Hanneke, Karbasi, Mahmoody, Mehalel, and Moran (NeurIPS 2022)]. In this work, we resolve the corresponding question in the agnostic setting. We show that the optimal excess error is $\widetilde\Theta(\sqrt{d\eta})$, answering one of the main open problems left by Hanneke et al. To achieve this rate, it is necessary to use randomized learners: Hanneke et al.\ showed that deterministic learners can be forced to suffer error close to $1$ even under small amounts of poisoning. Perhaps surprisingly, our upper bound remains valid even when the learner’s random bits are fully visible to the adversary. In the other direction, our lower bound is stronger than standard PAC-style bounds: instead of tailoring a hard distribution separately for each sample size, we exhibit a single fixed distribution under which the adversary can enforce an excess error of $\Omega(\sqrt{d\eta})$ infinitely often.

Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness
Bogdan Chornomaz'
Yonatan Koren
Department of Mathematics
Department of Mathematics
Technion Israel Institute of Technology Haifa, Israel
Technion Israel Institute of Technology
Haifa, Israel
markyz. www.kkkaaaaaaaaaall....m com
yonatankoren&campus technion
Shay Moran
Departments of Mathematics, Computer Science, and Data and Decision Sciences Technion Israel Institute of Technology and Google Research Haifa, Israel
smoran@technion. ac.
Tom Waknine
Department of Mathematics
Technion Israel Institute of Technology
Haifa, Israel
tom. wakninn@camppss..mmmmm.mm techni on ac il
Abstract
We study the problem of learning in the presence of an adversary that can corrupt an yj fraction the training examples with the goal causing failure on specific test point. In the realizable setting, prior work established that the optimal enror under such instance-targeted poisoning attacks scales as (dy)), where is the VC dimension of the hypothesis class [Hanneke, Karbasi, Mahmoody, Mehalel, and Moran (NeurIPS 2022)]. In this work, we resolve the corresponding question the agnostic setting. We show that the optimal excess error is Ô ((yd)), answering of the main open problems left by Hanneke al. To achieve this rate, it is necessary to use randomized learners: Hanneke et al. showed that deterministic learners can be forced suffer error close even under small amounts of poisoning. Perhaps surprisingly, our upper bound remains valid even when the learner's random bits are fully visible the adversary. In the other direction. our lower bound is stronger than standard PAC-style bounds: instead of tailoring a hard distribution separately for each sample size, exhibit single fixed distribution under which the adversary can enforce an excess error of 12( /dr)) infinitely often.
'Bogdan Chornomaz supported by the European Union (ERC, GENERALIZATION 101039692).
Robert J. Shillman Fellow; supported by ISF grant 1225/20, by BSF grant 2018385, by Isracl PBC-VATAT, by the Technion Center for Machine Learning and Intelligent Systems (MLIS). and by the European Union (ERC, GENERALIZATION. 101039692). Views and opinions expressed are however those only and do not necessarily reflect those the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
author(s)
'Tom Waknine is supported by European Union (ERC, GENERALIZATION, 101039692) and by ISF grant.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Introduction
Imagine a social network like Facebook or X (formerly Twitter), where recommendation algorithms curate the content shown users. A business political entity might attempt manipulate the system by injecting carefully crafted fake interactions - likes, shares, and comments - into the training data, aiming subtly boost the visibility of its content for specific target users. The goal is not to disrupt overall system performance, but to force an error on particular instances of interest.
Such scenarios fall outside the scope of classical models of learning, such as PAC learning, which assume that the training data and the test example are independent. When an adversary can modify the training data based knowledge of the test instance, this independence assumption breaks down. This motivates the study of targeted data poisoning attacks, where the adversary corrupts part of the training set in order to cause failure specific test point.
1.1
Main Results
In this subsection, we present the learning model and our main results. The presentation here assumes familiarity with standard concepts from classical learning theory; more self coffcconti exposition will be provided in Section
We focus on the instance-targeted poisoning model (see, e.g., Barreno, Nelson, Sears, Joseph, and Tygar (2006)), parameterized by poisoning budget 1i E (0,1) and sample size 0. The
interaction proceeds as follows:
Learning under Instance- Targetd Poisoning
1. The adversary selects a distribution over labeled examples (x. E X x (0,1}.
2. A training sample n examples and a target example (Ir, y) are drawn independently from DD
3. The adversary observes both S and (r, v). and modifies up to an r7-fraction of the examples in produce poisoned sample S'.
4. The learner receives S' and outputs a hypothesis A(S") :X' - {0, 1).
5. The learner succeeds if (()))(z) y and fails otherwise.
We study this model with respect to fixed hypothesis class S (0, 1 As in classical learning theory, we distinguish between the realizable and agnostic settings:
In the realizable case, there exists a hypothesis h E H. with zero loss on D.
In the agnostic case, assumption is made D, and the learner aims compete with the minimal achievable loss over H.
Previous work by Gao, Karbasi, and Mahmoody 2021a] showed that if the poisoning budget vanishes with the sample size (n7 o(1)
oo), then PAC Icarnability of H. implies learnability
under instance-targett targeted poisoning. both in the realizable and agnostic settings. Their algorithms, however, relies crucially
17 being negligible. Subsequently, Hanneke, Karbasi, Mahmoody Mchalel, and Moran 2022] studied the problem for general values of 77, and provided tight bounds on the achievable error in the realizable setting They showed that an error rate of O(7 VC(H)) ) is achievable, and that this rate is optimal up to constant factors. Remarkably, this optimal rate can already be attained by deterministic learners. In the agnostic setting, however, |Hanneke et al. [2022) revealed strikingly different phenomenon: deterministic learning under instance-targeted poisoning impossible. Specifically, they showed that for any deterministic learner, an adversary can drive the learner's error close to 1, even when is small (c.g.. e.. 17 (l)/)T)). This naturally raises the following question:
function of r and the VC dimension VC(H).
Main Question
Is agnostic learning under instance-targeted poisoning possible using randomized learners? What the optimal achievable excess error?

---

We show that randomness indeed circumvents the impossibility result established by Hanneke al. 2022] for deterministic learners. Furthermore, we obtain nearly tight bounds on the optimal achievable excess error, matching up to logarithmic factors.
Theorem 1 (Main Result). Let be concept class with VC dimension d, and let n (0, be the poisoning budget. Then, the following hold:
(Upper Bound) There exists a randomized learning rule such that for any distribution and against any adversary with poisoning budget 9,, and sample size of at least 2 1 n'' the excess error is at most Ô (vdn)
(Lower Bound) For every learning rule, and n > O, there exist a distribution DD and an adversary with poisoning budget yI such that the excess error is least Q (min {ydn, }))-
In particular, for every sufficiently large sample size n, the optimal achievable excess error under instance-targeted poisoning is
+ mind V vdn,
'Note that if n < y. then the adversary's 's budget is too small to corrupt any examples. In this case, the problem reduces standard PAC learning, for which the optimal rate is O(/d/)).
The upper bound in Theorem | and its quantitative version, Theorem 4 are achieved by a proper randomized learner, which selects its output hypothesis with probability proportional the expo- nential of (minus) its empirical loss in the spirit of multiplicative weights algorithms and the exponential mechanism from differential privacy. The connection between data poisoning and differ- ential privacy [Dwork, McSherry, Nissim, and Smith 2006] is intuitive: differential privacy requires that an algorithm's 's output be stable under adversarial changes to a single training example. This guarantee extends- with some quantitative degradation-to group privacy, which ensures stability under changes to multiple examples. This notion is closely related to the goal in our setting, where the adversary may corrupt n--raction of the training data.
The lower bound established by first analyzing simpler setting, the poisoned coin guessing problem, and then using kind of direct-sum argument extend the bound to arbitrary VC classes. Further details and intuition behind these constructions are provided in the technical overview below.
1.1. Private vs. Public Randomness
Following Gao et al. (202 la and Hanneke et al. 2022 we distinguish between two natural types of adversaries, according to their access to the learner's randomness: and publicsrandomness adversaries. In the private randomness setting, the adversary does not observe the learner's internal random bits when constructing its poisoning attack. In the public randomness setting, by contrast, the adversary has full knowledge of the learner's random seed before designing the poisoned dataset.
adversaries
At first glance, one might expect public randomness to reduce to the deterministic case: indeed, once the random seed fixed, the learner becomes a deterministic function its (poisoned) input, seemingly vulnerable to the same attacks as any deterministic algorithm. Perhaps surprisingly, this intuition proves false: although the adversary sees the learner's random seed when crafting the poisoned dataset, the underlying distribution this randomness. This asymmetry allows, with appropriate design, the construction learners whose guarantees under public randomness match those achievable under private randomness:
examples is fixed in advance and independently of
Theorem 2 (Private vs. Public Randomness F).
For every learning rule Apriv, there exists learning rule Apab such that for any distribution D, sample size n,, and poisoning budget E 10,
max adversary soes internal randonness
ExcessLoss(Apub D, n,
S
max
ExcessLoss(Apriv. D, n, 7).
adversary does not see internal randomness
3

---

Psee Section for formal version.
Thus, the theorem implies that whatever guarantees can be achieved against adversaries that do not observe the learner's ' internal randomness can also be achieved against adversaries who do. Specifically, given any learning rule Apriv that achieves certain excess against weak adversaries (private randomness), we can efficiently construct a learning rule Apub that achieves the same guarantees against strong adversaries (public randomness). In partieular, applying the theorem an optimal learner Apriv for the private randomness model yields a learner Apub that matches its performance even when the adversary is fully aware of the learner's random bits.
The proof of Theorem rrllics on carefully coupling the predictions of Apriv across all possible input samples. Specifically, we construct Apub to satisfy monotonicity property: whenever Apriv is more likely to make an error on a test point æ given training sample S1 than given training sample S2, the learner Apub will err for S1 whenever it additional advantage from observing the learner's 's internal randomness.
for S2. This ensures that adversaries gain
1.1.2 Poisoned Learning Curves
The lower bound in Theorem Tholds in the standard distribution-free PAC setting: for every learner and every sample size n, there exists a distribution tailored the sample size n and the learner that forces large excess error. This is typical for PAC-style lower bounds, where the hard distribution is allowed to depend on the training set size.
However, in many practical learning scenarios, we think of the underlying distribution as fixed and study the learner's behavior the sample size n increases naturally raises the question: is it possible that for any fixed distribution, under tasreede poisoning eventually falls below daj? other words, can better asymptotic behavior be achieved in the universal learning setting [Bouquuet Hanneke, Moran, van Handel, and Yehudayoff 2021] The following result shows that the answer is unfortunately negative.
the so-called learning curve. This
grows, the excess eπrr
Theorem 3 (Poisoned Learning Curves) ). Let H be concept class with VC dimension d, and let 17 (0, 1) be the poisoning budget. Then, for every learning rule A, there exists distribution D and an adversary that forces excess error of at least Q (min {Vdn. }) for infinitely many sample sizes n.
Theorem 3 follows by exploiting the proof of Theorem 1 In that proof, we construct a finite set of distributions with the property that, for every learner and every sample size n, there exists distribution in the set witnessing the lower bound of Theorem [ aat sample size n. Since the set is finite, by simple pigeonhole principle argument, of these distributions must witness the lower bound for infinitely many values n, thus establishing Theorem
Organization
The remainder of the manuscript is organized as follows. In Section 2 we provide a technical overview of our approach. focusing on the key ideas behind the proofs. Section work and places our contributions in context. In Section 4 we formalize the learning model and introduce the adversarial losses studied this work. In Section we formally state and prove our main results.
related
2 Technical Overview
In this section, we provide a high-level overview of the proof of our main result, Theorem | and not included this overview, as their proofs are shorter and structurally simpler than that of the main result; they are deferred to the supplementary material.

---

2.1 Lower Bound
natural starting point for understanding the lower bound is the coin problem, introduced by Hanneke et al. [2022] In this setting, the learner is shown a training set consisting of coin tosses, and must predict the outcome of partieular test toss. The adversary is allowed observe both the training set and the target toss, and can corrupt small fraction of the training data before the learner sees it. The learner's goal is to guess the target toss correctly despite this targeted poisoning. Formally, the coin problem is equivalent to learning hypothesis class H. ho, hı over single point A' {x), where h, (x) i.
The Poisoned Coin Problem
1. The adversary selects bias parameter p E [0,
2. A training sample S' of n examples is drawn i.i.d. from Bernoulli distribution of bias
p. A target label y is drawn independently from the same distribution.
After observing both S and y/, the adversary modifies at most an r--raccion of to obtain a poisoned sample S'.
4. The learner receives 5' and outputs a prediction A(S') E {0,
The learner succeeds if A(S") = y. and fails otherwise.
In the absence of poisoning, the optimal strategy for the learner is simple: if 2. the learner should always predict resulting in eπror rate of p; if p 1. the learner should predict O, with an error rate of p. Thus, while the learner does not observe the bias p directly, can estimate it from the sample. In the absence of poisoning, this allows the learner to achieve error arbitrarily close to min - p) as the sample size increases.
When poisoning is allowed, the learner instead observes corrupted sample S', and we measure its performance relative to the clean optimum. We define the excess error as
excess P(A(S") + y) min(p, 1- p).
Our goal is to show that against any learner, there exists an adversary that forces an excess error of 0( ((v)). Toward this end, we consider the function F(p) = E[A(S)], where S is a clean (unpoisoned) training sample drawn from Bernoulli distribution with bias p. That is, Fp) represents the expected then convenient to consider
prediction the learner when trained on clean samples with bias the oblivious setting, which can be summarized follows
The Poisoned Coin Problem with Oblivious Adversary
1. The adversary selects a bias parameter E [0, 1].
A target label y is drawn from Bernoulli distribution of bias p.
After observing y. the adversary modifies p into p' which is close d(p. S 17.
4. The learner receives training sample S' of i.i.d. examples drawn from Bernoulli distribution of bias p', and outputs a prediction A(S') {0, 1}.
The learner succeeds if A(S") = y, and fails otherwise.
One can change a sample drawn from a distribution with bias p to a sample S' which is indistin- guishable from one drawn from distribution with bias p', Thus it is suffice to find lower bounds for the oblivious setup. The advantage this model that the excess error can be defined terms the function F, hence the lower bound can be derived purely by analyzing properties of such functions.
Fix any learner A. We can assume that its excess eтrоr in the absence of poisoning is at most /n- since otherwise the lower bound immediate. In particular, this implies that when = + /7, the
*We note that in Hanneke here we are dealing with a nondeterministic one. Despite a seeming resemblance, these end up being very different problems with very different answers. In particular, for the deterministic learner, non-trivial adversary always force excess error of 1/2, provided the sample size is big enough (compare it with Theorem
2022
coin problem was considered for a deterministic learner, while
5

---

learner's expected prediction F(p) must be close to 1, and when p = VT, F(p) must be close to O. Thus, p varies from _ V to _ेz + vīj the function F(p) must change by constant amount (independent of 1 and n).
By averaging argument, this implies that over an interval of length O()), the function F(p) must change by at least 12( v7) on average. In particular, there exists a critical point p E E VT. 2 + vil such that
FF(p" n) Flp + n)) = 2(v
This critical bias p" will correspond to a hard instance for the learner, enabling the adversary to enforce the desired lower bound on the excess error.
The preceding argument establishes the desired lower bound for classes of VC dimension 1. Recall that class H. has VC dimension 1 if and only if there exists point x that is shattered by H-mmaning that for every label y E {0, 13. there exists a hypothesis E H. such that h(z) = y. Thus, learning H distributions supported æ; reduces to distinguishing between two competing hypotheses single point, corresponding exactly to the coin problem described above.
The case of VC dimension d corresponds naturally to generalization that we call the d-coin problem. In the d-coin problem, there are distinct coins ..,.... . Ldd each associated with its own unknown bias ps E (0, 1]. The data generation process proceeds as follows:
The d-Coin Problem
Consider the following sampling process:
The adversary selects bias vector Pı..... Pi.....PP Pa E [0, 1ja.
A coin x = x; is selected uniformly at random from (x1,..., ma)-
The label y is drawn according to Bernoulli distribution with bias pa (that is, y = 1 with probability p.).
The rest is as before. the sampling process, independently of the target example (a,, v)- After observing both the training set and the target example, the adversary may modify up to an 17-faccionn of the training examples produce poisoned sample. The learner receives the poisoned sample and attempts to predict the label of the target coin x. The learner succeeds if its prediction matches and fails otherwise.
The training set of n i.i.d. examples (z,, y/)) is generated according to
We further note that, similalrly to how it was in the one coin case, the lower bound is proven using d-coin problem with oblivious advrsary, defined by analogy.
This d-coin problem mirrors the setting of learning a class H with VC dimension d. Indeed, (3i.....,4d)] ].,] is set shattered by H. then the label of each point xy behave independently of the others. Assigning biases to the labels of each x; corresponds to constructing a distribution over labeled examples consistent with H. Thus, the problem of predicting the label of a randomly chosen target point (under potential data poisoning) mirrors the challenge faced by the learner in the d-coin setting.
The Naive Extension Coins. first glance, may seem that the lower bound for a single coin should extend directly to the d-coin problem. Since each coin x; has its own independent bias pi. one might expect that the learner's 's prediction for x; depends only on the outcomes of examples corresponding to x; in the training sample, and not examples involving other coins.
Under this assumption, the adversary's 's strategy would be simple: conditioned on the target coin being r;, the adversary would focus its poisoning efforts solely on the training examples involving zq. Since the meta- distriibitiittonn is uniform over the coins, the expected number of appearances of a;; in the training sample is about n//d. The adversary's global budget allows corrupting an f-fraction of the n examples, and thus roughly a vjd-fraction of the x; examples. Thus, for the target coin, the setting effectively reduces to the single-coin case with sample size about n//d and poisoning budget about rjd. Applying the single-coin lower bound then suggests that the excess error should be least Q (Vdr). matching the desired bound.

---

Unfortunately, the above reasoning overlooks an important subtlety. In the d-coin problem, the adversary must commit the biases PI,.... Pa before the training sample and target example are drawn. Because of this, the learner's prediction for a target coin I; could, in principle, depend on the outcomes of other coins xy (j * i), whose biases are correlated with pt through the adversary's global choice of parameters.
In partieular, if the biases across different coins are not carefully chosen, the learner may be able to infer information about the bias of z; by examining patterns across the entire sample, not just the examples involving 24. This possibility of information leakage where the behavior of non-target coins reveals something about the target coin - breaks the reduction to the single-coin case. Thus, more careful argument needed establish the desired lower bound.
Randomizing the Biases. To overcome this difficulty, we modify the adversary's 's strategy: rather than fixing the biases Pi..... Pa deterministically, the adversary draws each bias independently at random from a carefully designed distribution over [0, 1]. This randomization breaks potential correlations between different coins, ensuring that the behavior of non-target coins carries no useful information about the target coin.
The Fix:
Constructing such a hard distribution requires strengthening the lower bound for the single-coin case (d = 1): instead of selecting a hard bias p tailored to a specific learner, we design distribution over biases that is universally hard- - meaning that for any learner, the expected excess error (over the choice of the bias) remains (ī))). Sampling the biases pı..... Pa independently from this hard distribution ensures that, for any fixed learner, the expected excess error remains large, and prevents information leakage between coins. With this setup, the adversary effectively reduces the d-coin problem back to independent copies of the single-coin case, yielding the desired 92( (2)dd) lower bound.
2.2 Upper Bound
Coin Problem. To build intuition for the upper bound, we begin with the coin problem. One natural way to exploit randomness in the learner's strategy via sub-sampling. Specifically, the learner can randomly select a small sub-sample of size k ~ from the training set and predict the label of the test coin by majority vote over this sub-sample.
This simple strategy has key advantages. First, by standard concentration bounds, small sub-sample already suffices to estimate the bias of the coin up to small additive error. Second, and crucially, by anti-concentration, the adversary cannot easily flip the prediction: changing the majority outcome typically requires modifying roughly vk entries. As long as the poisoned fraction rj is small, the adversary is unlikely to control enough points in the sub-sample to alter the majority. In total, this approach yields an excess error of (V))) the coin problem.
Finite Classes. A natural next step is to generalize this idea to arbitrary finite hypothesis classes. One might try the same strategy: draw small random sub-sample of size k and train an optimal PAC learner on it. This technique was used by Gao et al. (2021a], who showed it suffices for learning under instance-targeted poisoning when the poisoned fraction 7) vanishes with n. However, this method fails to provide our desired bounds when v) is not negligible.
What fails here is robustness. In the coin problem, majority vote has a useful anti-concentration property: to flip the output, the adversary must corrupt roughly vk points. But for general hypothesis classes, it unclear whether any natural learning rule exhibits similar resilience to perturbations. In particular, standard PAC learners might change their output significantly in response to few targeted changes, especially when trained on a small sub-sample. This instability limits the effectiveness of naive sub-sampling in the general case.
Sampling via Loss Exponentiation. To move beyond naive sub-sampling it is helpful to ask: what probability distribution over hypotheses does the sub-sampling strategy induce?
In the coin problem, majority voting over random sub-sample can be interpreted assigning higher selection probability to the constant label h = 0 or h = 1) that achieves lower empirical loss. More guantitatively, one can show that the induced selection probability is roughly proportional to
7

---

the exponential of the negative squared loss on the sub-sample: P(h) x exp ( -- Ls(h))). for some À > This reflects the conceenonnntrninn property of the majority vote: flipping the output requires altering many points in the sub-sample (although we note that due to the abovementioned problems, we end up not using the anti-concentration inequalitis per se).
This motivates the use of learners that explicitly reweight hypotheses according to exponentiated losses. In our final algorithm for finite classes, we simplify the squared loss standard loss and sample from the exponential of its negative: P(h) oc exp A- [s)h) This distribution, known from the exponential mechanism in differential privacy and multiplicative weights in online learning. preserves both stability and performance. Small perturbations to the dataset (such as an 1)- 77-fraction of poisonings) have limited impact on the output, while hypotheses with lower empirical error remain more likely to be selected. Working out the details of this approach yields an excess error bound of ( v log m) for finite hypothesis classes of size m.
From Finite to VC Classes, All that remains to extend the result from finite classes to hypothesis classes of bounded VC dimension. In the case of finite class H of size m. the exponential sampling strategy achieves excess error On Our goal is replace the dependence on log m with VC(H), the VC dimension of the class.
A direct application of the multiplicative weights sampling method to an infinite class fails to yield tight bounds, as the performance of the learner would then scale with the (possibly infinite) size of the class, rather than with its VC dimension.
To overcome this, we use a classical reduction based on E-covers: we construct finite cover H' S H such that the minimal loss over '2' approximates that over H. up to an additive e. This allows us to reduce to the finite case without significantly increasing the error.
A standard uniform convergence argument shows that an é-cover can be constructed from a random sample of size roughly VC(H))/².. Unfortunately, using such sample leads suboptimal overall bound on the excess error. Instead, we apply a more refined analysis based on the VC dimension of the symmetric difference class hāh': h, h' H. which shows that it suffices to construct the E-cover from a much smaller subsample of size O(VC(H)/E). This enables us to keep the size of the subsample below the poisoning threshold with high probability, ensuring that the cover is not corrupted.
similar approach- - involving subsampling and refined covering arguments has been used the context of differential privacy and algorithmic stability, for example in Basssly et al. [2019] Dagan and Feldman 2020)).
Putting everything together, our final algorithm proceeds as follows:
Given sample S, draw a random sub-sample T of size Ö(VVC(H))m)
2. Use T to construct a finite e-cover Hr S H. where & = VVC(H)
3. Run exponential sampling over Hy: select h E Mr with probability proportional to exp(-> (h))..
This completes the proof sketch of the upper bound.
3 Related Work
Learning under poisoning attacks has been studied in several settings. Earlier research (Valiant) 1985 Kearns and Li. 1993, Sloan 1995 Bshouty, Eiron, and Kushilevitz (2022) focused on non- targeted poisoning. where the adversary does not know the test point. Computational aspects of efficient learning under poisoning have been studied under various distributional and algorithmic assumptions (Kalai, Klivans, Mansour, and Servedio, 2008 Klivans, Long, and Servedio, 2009 Awasthi, Balcan, and Long 20144] Diakoniklas, Kane, and Stewart [2088] In particular, Awasthhi Balcan, and Long [2014] achieved nearly optimal learning guarantees (up to constant factors) for polynomial-time algorithms learning homogeneous linear separators under distributional assumptions in the malicious noise model. These results were later extended to the nasty noise model by
Diakonikolas, Kane, and Stewart 2018), along with techniques that also apply to other geometric
8

---

concept classes. In the imsupervised setting the computational challenges of learning under poisoning attacks have been investigated by Diakonikolas, Kamath, Kane, Li, Moitra, and Stewart 2016], Lai Rao, and Vempala [016].
In contrast, our work focuses instance-targeted poisoning, and investigates the fundamental tradeoffs in error and sample complexity, independent of computational constraints. A related but more demanding task-certifying the correctness of individual predictions under instance-targeted poisoning-was studied by |Balcan Blum, Hanneke, and Sharma [2022] The instance-targeted model we study was formalized in Gao, Karbasi, and Mahmoody [2021b], who showed that when the poisoning budget vanishes with the sample size. PAC learnability is preserved. Hanneke, Karbasi, Mahmoody, Mchalel, and Moran (2022) extended this line of work to general (non-vanishing) poisoning rates, and characterized the optimal error in the realizable setting. In particular, they showed that deterministic learners suffice in the realizable case, but fail in the agnostic case, where they can suffer near-maximal error even under minimal poisoning. They left open the question of whether randomized learners could succeed in the agnostic case. Our work resolves this open problem, establishing that randomized learners can indeed achieve meaningful guarantees in the agnostic setting, and characterizing the optimal excess error @(vrr), where d is the VC dimension.
Other types of targeted attacks have also been studied, In -tareeeed attacks, the adversary aims to force the learner to mimic a particular model [Farhadkhani, Guerraoui, Hoang, and Villemaud 2022 Suya, Mahloujifar, Suri, Evans, and Tian 2021]. Label-targeted attacks aim to flip the learner's prediction on a specific test example (Chakraborty. Alam, Dey, Chattopadhyay, and Mukhopadhyay 2018). Jagielski, Severi, Pousette Harger, and Oprea] [2021] introduced subpopulation poisoning, where the adversary knows that the test point comes from a specific subset of the population.
More broadly, recent works have explored robustness to adversarial test test-time manipulation. |alcaan Hanneke, Pukdee, and Sharma [023) study reliable prediction under adversarial rest-time attacks and distribution shifts. While their work focuses on modifying the test point rather than poisoning the training set, it shares our motivation of provable robustness in challenging environments. Like- wise, Goel, Hanneke, Moran, and Shetty] (023) analyze a sequential learning model with clean-label adversaries, allowing abstention on uncertain inputs.
Empirical and algorithmic defenses against instance-targeted and clean-label poisoning have been widely studied. |Rosenteld. Winston, Ravikumar, and Kolter (2020) show that randomized smooth- ing [Cohen, Rosenfeld, and Kolter 2019] can mitigate fabelffiippng attacks, and can extend to replacing attacks such as ours. Follow-up up work has explored deterministic defenses (Levine and
Feizi (2200) as well as randomized sub-sumpll sampling and bagging [Chen, Li, Wu, Sheng, and Li 2020
Weber. Xu, Karlas, Zhang, and Li, 2020 Jia. Cao, and Gong 2020].
Other theoretical works have studied error amplification under targeted poisoning (Mahloujifar and Mahmoody] 2017 Etesami, Mahloujifar, and Mahmoody| [2020], often with a focus on specific test examples. The empirical study of poisoning attacks in SSaaahii, Huang, Najibi, Suciu, Studer Dumitras, and Goldstein (0088) further illustrates the practical relevance of instance-targeted threats.
4 Preliminaries
As it is usual in learning theory, we consider concept class H over domain X' with label space 0/ = (0, 1): that is, H is set of functions (also called concepts) from X' to V. We define the set of labeled examples
Z = X' x y and sample of size is - = U n= za. A learning rule is a map A Z + + that assigns to each sample S a function A(S), called hypothesis. We also often consider randomized learners that output a distribution over hypotheses.
sequence S E Z"; the space of samples
The sample loss of a hypothesis h: X + Y on sample 5 E Z" is
Ls(h) = - [h(x)) Vol-
Similarly, we define the population loss of h with respect to a distribution D over Z as
(hD(h) P [M(x)) # v) (2
[h(x)= yl-
(a.0)~
9

---

The expected loss of learner A with sample size with respect to D is (D(()))
LD(A,n)
E
E [A(S) yl-
S-D"
S-DD
(w.y)~D
The above formula is also applicable to randomized learners, in which case the expectation is also over the internal randomness of A.
Define the normalized Hamming distance between two samples S, S E z" by
dæ (S, = 1 Hi [m] S, #
For any sample S E z" and 17 E (0, 1). define the 17-ball centered S by B,( 18' z" (s 8*) S /n)
Definition (n--adversarial loss). Let n E (0,1) 1) be the adversary's budget, be a (possibly randomized) learning rule, and let DD be distribution over examples. The n-adversarial loss of A with sample size n with respect to DD is defined as
sup E ((A)(S))() - -u] S'EB,(8)
(D.(A,
SND" (2.g)m<
where is the internal randomness of A, and Er can be omitted case the learner A is deterministic.
Note that in this definition the data is corrupted before the randomness of A. which corresponds to private randomness. Alternatively, we may consider the public randomness model in which we define
pub (A,
E
E
sup (S),
(Ar()" vl
S-D"
[a.y)~D
Finally, in the spirit of agnostic learning and the poisoned coin problem, the effectiveness of the learner in the presence of poisoning is measured with respect to excess error:
Definition 2 (Excess error). For a concept class H. adversary budget E (0, 1), learning rule A. sample size n, and distribution over examples DD we define the excess error of A with sample size against an adversary with budget y on 'D as
D.,es,,,D,,(A,... = L.D,, (A, inf (D).).
hEH
The definition excess similarly adapted to the case of public randomness, and, as usual, we drop some of the parameters H. D, n,A, A, in the notation for loss/excess if they clear from the context.
Definition (VC dimension). We say that a concept class H shatters set X for any any function f: + {0,1) 1} there exists h E H such that f(x) = h(x))_p for all x E X. The VC dimension of H. denoted VC(H), the largest d for which there exist a set X X of size d that is shaltered by H. sets of arbitrary size can be shattered we define VC H) = 3C.
Lemma Sauer-Shelale lemma see Lemma 6.10 be a concept class of VC dimension d = VC(H), and ler X C X be a finite set of unlabeled examples of size = X). Define an equivalence relation on H by h ~xx h h((x) = l((x) for x E X, and let Hx be arbitrary set of representatives with respect to this relation. Then have
and Ben- BeviD 2014]). D. Let H
d
Σ 1=0
71
In particular, if >> d d+1 we have
6 Bndd Hxx S
d
References
P. Awasthi, M. F. 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.
10

---

Maria-Florina Balcan, Avrim Blum, Steve Hanneke, and Dravyansh Sharma. Robustly-reliabl learners under poisoning attacks. In Po-Ling Loh and Maxim Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 4498 4534, PMLR, 2022. URL https: htt.hhttp:::p/oettte //ppee/edpocccnngss. mlr wwl.mmrrrreeee p.t..presss/11..
balcan22a.htan html
Maria-Florina F Balcan, Steve Hanneke, Rattana Pukdee. and Dravyansh Sharma. Re- liable learning in challenging environments. In A. Oh, T. Naumann, A. Glober- son, K. Saenko, M. Hardt, and Levine, editors, Advances in Neural Informa- tion Processing Systems, volume 36, pages 48035 48050. Curran Associates, Inc., 2023. URL
sacaperrffles__eeeeeeeeeeeeeeeee www.fflleeppppee pttps///ppp//////11eeeel/ pdf
961 oat.a//0eeeoocoooooooooooaaaaaae
Marco Barreno, Blaine Nelson, Russell Sears, Anthony D. Joseph, and D. Tygar. Can machine learning be secure? In Proceedings of the 2006 ACM Symposium on Information, Computer and Communicaation Security, ASIACCS '06, page 16-25, New York, NY, USA, 2006. Association for Computing Machinery. ISBN 1595932720. doi: 10.1 145/1 288 17. 128824. URL https
//doi //doi.org/10.1111
httrg/1..1145/// 11t....111111111111 1128824
Raef Bassily, Shay Moran, and Noga Alon. Limits of private learning with access to public data. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Bue, Emily Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019. December 8-14, 2019, Vancouver, BC, Canada, pages 10342-10352, 2019. URL https: / http:///poceedeeeeeee/ee www.inngn.n..uuppeeee meurips cc/ 0aapperr/219//ahh///aaee httpp//0002a//e/aaaaaaa/////7/70 Abbssstrtt.................aa...
Abstract. html
Guy Blanc and Gregory Valiant. Adaptive and oblivious statistical adversaries are equivalent, 2024.
URL pistps://arxier http://wxxvvi.oaeeeee// htwgg//bb/1/...// 13548
Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, and Amir Yehudayoff. A theory of universal learning. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 532-541. ACM, 2021. doi: 10.1 1..1145/3440325.45518888.. URL (RLttttps://doi org/ 10. 11.114533406225 34418777
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 18xiv 1.0000069, 2018
Ruoxin Chen, Jie Li, Chentao Wu, Bin Sheng, and Ping Li. A framework of randomized selection based certified defenses against data poisoning attacks, 2020.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pages 1310-1320. PMLR, 2019.
Yuval Dagan and Vitaly Feldman. Pac learning with stable and private predictions. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 1389-1410. PMIR, 09-12 Jul 2020. URL httpps://proceeednngg mlr. press/v125/// dwg./////aaa.aa... html
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.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, pages 265-284. Springer, 2006.

---

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 Algorithms, 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. In International Conference on Machine Learning, pages 6284 6323. PMLR, 2022.
Ji Gao, Amin Karbasi, and Mohammad Mahmoody, Learning and certification under instance-targeted poisoning, 2021a. URL httpshts::/// //axxiv org/ aba/ .07090079999
Ji Gao, Amin Karbasi, and Mohammad Mahmoody. Learning and certification under instance-targeted poisoning. In Uncertainty in Artificial Intelligence, pages 2135 2145. PMLR, 2021b.
Surbhi Goel, Steve Hanneke, Shay Moran, and Abhishek Shetry. Adversarial resilience in sequential prediction via abstention. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA. USA, December 10 16, 2023, 2023, URL http::/papers.. mipppprrrr..ippppp.p.ppp.p ww/pwpcrpppppppetee (tt.::22222222211622222222222280
Conferenet-ooooeeceeec html
Steve Hanneke, Amin Karbasi, Mohammad Mahmoody, Idan Mehalel, and Shay Moran. On optimal learning under targeted data poisoning, 2022. /ttpt:tts://aaxiiiv. wbargg/abs/22110 02713
Matthew Jagielski, Giorgio Severi, Niklas Pousette Harger, and Alina Oprea. Subpopulation data poisoning attacks. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pages 3 10223122, 2021.
Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Intrinsic certified robustness of bagging against data poisoning attacks. arXiv preprint arXiv:2008. 04495, 2020.
A. T. Kalai, A. R. Klivans, Y. Mansour, and R. A. Servedio. Agnostically learning halfspaces. SIAM Journal on Computing, 3776 2008
Michael Kearns and Ming Li. Learning in the presence of malicious errors. SIAM Journal on Computing, 22(4):807-837, 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 B Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 665-674. IEEE, 2016.
Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defenses against general poisoning attacks. In International Conference Learning Representations, 2020.
Saeed Mahloujifar and Mohammad Mahmoody. Blockwise p-tampering attacks on cryptographic primitives, extractors, and learners. In Theory of Cryptography Conference, pages 245-277 Springer, 2017.
Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and Zico Kolter. Certified robustness to label- flipping attacks via randomized smoothing. In International Conference on Machine Learning, pages -2411 PMLR, 2020.
Ali Shafahi, W Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Dumitras, and Tom Goldstein. Poison frogs! targeted clean-labe 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 Sloan. Four Types of Noise in Data for PAC Learning. Information Processing Letters, 54 13):157-162, 1995.
12

---

Fnu Suya, Saeed Mahloujifar, Anshuman Suri, David Evans, and Yuan Tian. Model-targette poisoning attacks with provable convergence. International Conference on Machine Learning. pages 10000-10010. PMLR, 2021.
Leslie G Valiant. Learning disjunction of conjunctions. In IJCAI, pages 560-566, 1985.
Maurice Weber, Xiaojun Xu, Bojan Karlas, Ce Zhang, and Bo Li. Rab: Provable robustness against backdoor attacks. arXiv preprint 2xXiv:2003.0800 2020.
13

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the abstract we briefly introduce the main question, and in the paper we formally prove it.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [NA]
Justification: The paper deals with theoretical filed, in which the definitions are well established and the questions a well defined. states those problems and prove them formally.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: Everything is formally defined and proved in the paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments requiring code
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /otee//guudddeeeeoSuuubbmiibii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
16

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with NeurlPS Code of Ethics https: /tttps://neurips..c http://wwwwr..ooo///////ssssssaa
Answer: [Yes]
Justification: There no human subjects nor are there any data-related concerns. And the paper dose not seem to have any potential harmful consequences
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: While the paper deal with foundational research, the practical motivation is well stated and backed by examples. being theoretical paper lesson its potential impact, yet the positive advantage it can yield are clear from the motivating examples.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
17

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The paper poses no such risks since it contains no models or private data.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
18

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
19

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy buctps://neure wwwparippps..coooeeeeeeeee for what should or should be described.
20

---

Proofs
5.1 Proof of Theorem 1
We prove Theorem announced it.
I [n form of Theorem bellow, which gives quantitative version of the bounds
Theorem (Main result - quantitative version). Let be a concept class with VC dimension d' Z 1 and suppose zn. Then there exits randomized learner A such that for any distribution DD on X y and all 2 we have:
excessw.p.,(A.) S 36 /nd nd
This bound also tight up log factors; that is, for every randomized learner A, n zo and n1 Z log 61 there exists a distribution D such that /dai
Vdn 36
Dx >
There will be no separate proof of Theorem 4 Instead, the entire Section 5.1 is treated as such proof. particular, the upper bound on the excess established in Lemma and the lower bound in Lemma 14 We also remark that Theorem direct consequence of Theorem 4 Indeed the bounds in Theorem are quantitative versions the ones in Theorem so we just need to justifies the assumptions of Theorem
For the upper bound the assumption 17 < 4d is safe since otherwise bound of Ó(vdn) O(1) is trivial, while the assumption < was already assumed in Theorem where remarked that without it the adversary unable to poison even a single point.
For the lower bound, we may assume < 4. since otherwise ddy- = 2(1) and the result is clear. The assumption 2 6 log 64 is valid since without it, standard PAC learning arguments shows that the yay desired lower bounds can be forced even without poisoning. Indeed, by 28.2.22 in (Shalev-Shwartz
7
and Ben-David 2014), excess loss of 52 V 4) can always be forced, even without poisoning. In the case of n S log Van this becomes the desired (Vvd)).
5.1.1 Upper bound
We address loss of learners with poisoning via prediction stable learners:
Definition& 5 (Prediction stability). The n--reddctionn stability of a random learner A with sample size n with respect to distribution D
An (A),,n) =
E SWD" (x.))~
sup P ([A,(S)(z) + (x)) (S)
E -14((5)(())444(1))))) A.()))))
E
sup (s)
S-D" (
Note that, trivially,
max (A., To(A, & (A.,(A.)) (AID, (.D.A,n),
where the second inequality be trivially rewritten
excessH.p,, (A) n) + (AA)
(1)
where excessH, LD(AA, inf (h)).
So minimizing the loss of a learner with poisoning is equivalent to finding an efficient learner that prediction stable.
21

---

Proposition 6. Let H. S y be a finite concept class of size [H]] = and let > 0 be the poisoning budget. Then there exists a randomized learner Au such that for every distribution over Z and every n. > 0, it holds
Xn(Au[D,n) S 4 log m
log 2m
ExcessH. S lo V m + 4
n1
Proof. We define the learner AH in two stages. First, we define the learner A. that samples according the exponential mechanism with multiplicative weights. That is, outputs each h H with probability
P (A(()) h) E (L)
where W = e (h) and t
V |og m We then prove that A satisfies the bound on the loss from the statement of the proposition, that that (D n) S infRcH Lp ( +5 log 2m.
As our second stage, we define another learner B, which will be our target learner, as follows: B samples ~ (0, 1). Then, for sample S and X, B returns 1 if r S Pr- (z) 11. and O otherwise. is easy to see that is a different learner than A; in particular, B can output hypotheses outside of the class H. However, by construction, for all S and x, holds
()= (A,(S(()) 1].
In particular, this easily implies that LD(B, = (D, n), and so B also satisfies the required bound on the loss. Notice, however, that, unlike with A, for B there is an explicit dependence the output on the internal randomness Thus, the outputs of B on any samples S and S' are naturally coupled. We will then utilize this coupling to prove the required bound on the prediction stability of B.
Let us now start with the proof of the bound LD LD (A, The proof proceeds by several claims.
Claim I. For any sample S, holds:
E Ls (Ls((S)) I inf Ls(h) + log m WEW
Indeed,
L. Ls (A)) < [by Jensen's] < Eexp (I- Ls (Ar(S)))
exp
W Σ e m
1
W
W (h) 2 sup tL)(h)
Sm. sup e -tba(h)) NeW
S exx (t inf Ls Ls(h)). bEH
KEH
Taking the log of both sides we get
log m
E ELs
I inf Ls(h) + MEW
as needed.
Claim 2.
E sup [hD(h) Ls(1)) < 22 log 2m D~ REM
n
Indeed, for any h H and
by Hoeffding's 's inequality have
P (lLs(h) - Lp(h)l 2) s 2c o'n
SwDn
22

---

And, by union bound, this gives
P SwDD
sup hEW
(h)) LD(h)] > E) S 2me -
Let us define 6n =
=6n 2 = 1, and compute the value for which 2me
Ls(h)) ("' T (sup [h)(h) T.D(h)) > t)dt [D(hh)
R sup S-Da NE7l
SND"
hE7f
1+
2me I'n dl S f=== vn. E +
2m pc
e=²
dx
Vn.
0
c0
=ovā
EO
Vlog 2m
1, so estimate
-x²
S xe-*
80
2m
roc
36
x²
dr =0 +
2m
2-
1 =x² 20
vn
Vn
cov
2m
exp(-cōn)
log 2m
mcxp(- log 2m
log 2m
$ Eo
vn
2
n
vn
n
This finishes the proof of Claim 2.
Putting Claims and 2 together and recalling that t LD(A,n):
logm
we get the required bound on n
log 2m
LD(A,n)= = E (D(A(S)) S
E (s(A((()) + +21 S.DD
S.DD
< inf Ls (h) + log m heH
log 2m
< inf LD(h) + Vn log m + +4V log 2m NEH
+ 2
Let us now prove the prediction stability bound for B. Recall that B returns if S Pr (S) = 1]. and 0 otherwise, for < u(0, 1). Again, we start with an intermediate claim, which, somewhat unexpectedly, is still be about A, not B.
Claim 3. Let S, S' E z" two samples with d (S, S') S 17. Then, for any h E H. we have
2tn (().(S)) h] s P(A,(S) h] < 2t (S', = h).
Indeed, by the definition of dh, Ls(h) S L (h) + 17, so
e < c (tis(N)) < 10 e (h)
where the second inequality is by symmetry. So.
W Σ e (h)()) en Σ e -t)) - W',
NER
hER
and so
e (tgggr())
(Lg(()
P[A,(S") = -|]
< 26n
26n, (S') = h)..
W
W
And the second inequality is by symmetry. This finishes the proof of Claim 3.
23

---

Now, let S and S' be ylcoosee samples and let z E A. Then
PlB,(SMa)) + B.
= =P(B,(()(x) - and (S)) - o] + [3)())()) (B) and (x) =
p ((A(())(z) -P (4.)))
(()(())()) = h) E [()((s)(z) -n]
h: h(x)=1
((A)(S)()) = (P(A = =n]
[y Claim 3/ $ Σ max P [()(())())) h). (z) -1l) e1---21)
h
$ 2 - c 2 I 4tn- 4v m.
2
where in the last inequality extends to (B) n) I 4 log m, as needed. Because, as argued in the beginning, B satisfies the same guarantee LD. it thus satisfies both bounds in the statement of the proposition, finishing the proof.
used the estimate 1 1 S for x: E (0. 1). The last bound clearly
Definition (E-cover). Let H. be a concept class over domain X. let E and D be a distribution over X. Then H C H is called an E-cover of H with respect to 'D for any h E H there is h' e H such that PIND [h(x)) # W/ (x)) S s. Let &D(H) H) be the minimal > 0 for which an E-cover of H. that is
ED = sup inf P. [Mxx) + hxx)].
NEH NEH rND
We also the above definition with distributions D over examples X x V, rather than just over X. This is done in a natural way, by letting (H( E (H), where Dx is the marginal of D.
For set of unlabeled examples X C X' recall we defined an equivalence relation on H by h ~x h h(x)) n (x) for all x E X, and denoted Hx an arbitrary set of representatives with respect to this relation. Extend this definition labeled samples S ((z1, y1), (I2, 82). ..... (In, Bn)) by letting Hss Hx for X {-1,-- f )
The following lemma is based on Lemma 3.3 in Bassily et al. (201
Lemma 8 (Covers for VC classes), For any concept class with VC dimension d, for any distribution
D and any n 2 d, we have:
13d n
2en log
E
8(Hs) <
d
Proof. The proof relies on Lemma 3.3 in Bassily et al. 2019 specifically, we use claim (1) in this result which gives
P (E())) e] s 2 2en 2d exp( S~Da
en
Hence for any > 0 we have
2en 2d exp(
671
E [(H))) < 2( S~n
d
4
Taking
12d x
log
Zem get
2en 2d exp( -3d
2em d
12d
2en
2en -d <
13d
2en
E S
[E(H))] S 2(
log
+ 2(
log
n
d
Where in the last inequality used 2 d to deduce 2( 2e2)
12d log
2nn
24

---

For any sample S = ((11, (12, U2), ................................ (In, Ba)) and an index set J S ..2...... n). define the subsample Sn ((x) Moi (1 1b2).... (I Mi.)), where J -ii are the elements of J ordered as j1 < J2 << jk.
Lemma 9 (Upper bound of Theorem 4. Let H be concept class with VC dimension d 2 1 and 4d' Then there exits a randomized learner A 2 - [0, 1] such that for any
suppose 7) < 1
distribution 'D on X x y and all 2 1/n we have:
(n n) S 4v I/d (nnddogg log nd
excessH.D(A, n) - 32 nd and nd
e
excessH.D., 2 36 nd log nd
Proof. Let 7 E (0.1) and let H be a class of VC dimension d. The learner A is defined as follows: For distribution D over Z, 2 2, and n-sample S ~ D", let S be concatenation of samples S1 and S2 of sizes n |n/2] and n22 [n/2] respectively, and let k [vd/An) note that by an easy computation, the condition
1/n implies k I A1, n2, while the condition vj S 1 implies k 2 1. A samples a k-set J C [n:]. uniformly at random. Then on the subsample T Si.J it runs the learner Azr from Proposition using the concept class Hr C H and the subsample S2. That is, A(5)= = AHr(s)) (52).
It is easy to see that, by construction, T DK Hence, by Proposition we can estimate the (clean) loss of A as
(,inf inf LD(h) + vn log [rr] + 4/ WeHt
log 2|Hr
[D(Ann)=
E TwDD
LD(AHr:
n2) S E T~DA
12
S
E TNDi
inf LD(h) + 9V n log 2
AEEHT
Note that the last bound follows from the assumption the two terms in the above. The first term is bounded using Lemma
[n/2]
We now separately bound
E
inf (h(h)= < [by the definition of e-cover] < inf (h) heH
+
E
{D(T)
TwDk heHr
TwDk
S inf (h) + 13d
2ek:
e2
log
inf [D(hh / Vnd
inf ID(h) + 13 nd log beh
NEH
NEH
nd
For the second term, we apply the Sheer- lemma 4 to conclude that (Hrl S (0%) jd. the above bounds requires & >> d + 1, which is enforced by the condition 17 < 4d Then
Note that
2ek S 5v ngd
E 5V 17 log 2|7r| S 5 prd yd log d TNDA
Vnd S 3 33 nnd log dij
Finally, combining these two estimates, we get:
e² Lo(A,n) inf Lo(h)) log rdd 33 qd log dn
e²
inf hER
Lo(h) + 32 nd
nd log nnd
NEW
yielding
excessH.p(A.n) S 32 ndllg
nd
as needed.
Now let us show the stability bound. Let S' E n be samples such that S' E BS(,), let E X and, above, let C [nI]. be k-set, for k LVd/4nj [n]4 chosen uniformly random. Let T=)(J) = Si,J and 7" = (J) = S Recall that the rendomness of AA is composed of picking and the internal randomness r of Axy. We have
P. (())() # A(5)) p. [A (52) + An (52)
S (p(T(J) (T()) + TJ] TP Anr (S2)(z) Ah,, (8)(2) T T s...
25

---

Let us estimate the first probability as follows: Let / fi [mi] this implies
SI * 81,13. As S' E By(s),
||| S 1 n, and so
p [
= [ + [ s kn.
Thus
S km P [(J) - 1P AHAA (S2) + AH (5) T= T"
...
km + (()) -
1p ( (S) + Au, (82)2) T= T
S km + P.P Jrr An, (S2)(() # Anr (S))
Notice that the only difference between the first and the second expression is that AHp becomes AHz- Now, taking expectation over S Dr and (I, v) ~ 'D in the above, we get
Nn (A(D.))) S knj +
E SwD (z,y)>
sup Bs) J.r
P.
Au, (52) + An (52)
S kn +
E
sup
P Aur & Aur (2))
Snp"
()),
(2,g)~D
< k0) + E
sup
PP Auu (52)(x) # Ave (2)
TwDk S2nDa2 (S,) r (a.
S kn + E
Ana (Aur [D. 21)
TWDA
< by Proposition
6
S km +
E TaDe
4 4 17 log |Hrl
c d
ek < kn + 4v nd d
S by |Htl S
d
< vnd
+
Auduloo
e
Vnd
2 + 2 ndd log
e² 4nd
2
VAnd
< 4/ndlog
e
nd
Finally, we estimate excessw.D. (A, by 1
excessx. n) S {A,(A(D)m) 7) + Axcesss,,(A,,))
pd S 4v <4Vnd log nd= + 32 nog S 3 pu log nd
5.1.2 Lower hound
When it comes to lower bounds on the excess error rate, is convenient to consider oblivious adversary, which only changes the distribution, not the sample itself, and can be considered a relaxation of the regular sample-changing adversary. This setup can be informally summarized as follows:
1. The adversary selects a distribution D.
2. A labeled example x = (x. y) is drawn from D and is shown to the adversary.
3. The adversary corrupts the distribution D by changing it into D' which is rycclose to D.
4. The learner draws an n-sample S from the corrupted distribution D' and uses to predict the label y.
26

---

The formal definition follows Blanc and Valiant 2024). Recall that for distributions μf over X1 and N2 over X2. coupling of μa and #2 a distribution P12 over X1 X2, whose marginals on X1 and X2 coincide with jal and 2l2 respectively. For distributions DD, and D2 over 2, we define the distance betwen them as
d(D,, D2) inf
[Z] + 22), Dia 21,22~D12
where the infimum is over all couplings D12 of 'Di and D2. We note that thus defined, d(Di, D2) coincides with the total variation distance between DD and '2, that is:
a(Di, D2) sup -
E
where the supremum is over all measurable events, Definition in Blanc and Valiant (2024) Finally, for a distribution 2 we define (D) to be the set of all distributions D' such that d(D, D)) S
y)-
Definition 10 (11ooblivious adversarial loss). Let r) (0,1) be the adversary's 's budget, let A be (possibly randomized) learning rule, and let D be a distribution over examples. The n-oblivious adversarial loss of A with sample size and with respect D is defined by
L LB,, (A. (x.g)~ (DE S'DD
E E (S)x)) m1
sup
The following proposition substantiates the claim that the oblivious adversary can be considered relaxation of the regular one.
Proposition 11. For any O, 17 (0, 1). s > O, learner A, and distribution be we have
LD,2((A, + (A,
Proof.
Recall that we want to upper-bound
Lobl L., (A,
E
sup
E E ((),()) vI]
(2.9)~D
(D) S'wpr
with
E sup E (z) L., (x. SND (')
We will now bound the part after Ery of the first expression in terms the similar part of the second. For brevity, denote Er (S") vl by L(S",, keeping in mind that also depends x; y- and A.
sup E L(S")
= sup
P
Ss
B2n(
E
L(S")
(D)
S'ND
3'~D' .SD
SND
S'E
+
p S'~D"
S & Bzn (2n
E
L(S') s...
S' D' S-D
Here assume that D and DD coupled with coupling witnessing a(D,D) D') 1). Now, in the expression [1] + [2) in brackets, let us estimate [1] and [2] separately, starting from [2]:
[2]
P D
S & B2n
E L(S')
S'DD'SS SDD ('g
S-D
P S'
S (S) < Bin (n. n) 2 2nm) ) S 4
S
Here in the second inequality we use the fact that D and D' are coupled in such way that F Pr-Da # z'| < n, and hence the event S' & (S) is equivalent to making at least
27

---

20yr mistakes in trials, where the probability of an individual mistake is at most 7). The final bound by multiplicative Chernoff bound inequality. Now, for [1]]
[
S E B2n
L(S")
S'DD 8ND
S' 8' (2,
p (S' E (2n((S)
E
sup
I(8")
S' SwD
S' SnD S"E S'eB2((5)
sup S' SDD (8)
E
L(S") = E sup SwD s (2.
I(S").
Note that here we fold back the expectation with conditionals, the way opposite to how we did in the beginning, but after changing the function under the expectation. Notably, the estimates for both [1] and [2] no longer depend on D', so
E sup SDD ('E
L(S") + 3
yielding the desired bound.
Throughout the section, {=1} instead of the usual {0, 1}. Let 7l _ {=1]* be a concept class of VC dimension d, and let X x= (z:) fixed dlset shattered by X. We will only consider distributions that have uniform marginals over {a:] that distributions DD such that for S S d we have
going to assume the following setup. Our label space will be
x 24 d'
(r.a))~
For 1d, let define distribution D,,
1 (1r, v/ (xi, v)] d (1/2 2 yuu)
1 + uz) a wi)
1,
IP (..
Note that the function + Da gives one to one correspondence between distributions with uniform marginals and [-2 2 which metric on 7d as 1 nnorm rescaled by 1 1/d, that is,
going to denote by 1d | 2: 2 Moreover, if we define the
d Σ 1=1
d(u, v/) = a Ilu 2/112 =
u//b
then d(u, u') = a(Du. D',).
For fixed n and a learner A: 8" -+ 10, us define a function F= n)A 1d - Id as
F((u)
((S)
S-DD
Now, for an arbitrary function F: Id eexxess of F with respect to u 1d as
Id, let us define the n-oblivious adversarial loss of F and
(F) = d
Σ im l. DE(il)
sup (1/2+ (1/2)2((((('))) and
u,n
a'E (u)
oxcessob]FF) 1bb1( (F)
Σ
min(1/2 ui, 1/2 + uz).
i=I....
28

---

In particular, for F = F(A,1) n.), we have:
(x) 1/
D'... (A,
sup
E
('EB(()) (x
S'-D.'
[A,(5))
d
Σ
(1/2 + yu))
(') S'ND
sup
E
E
2
i
>E(=1}
Σ
sup ('E
(1/2+ + yu:) (1/2 - y. 11/2-y.11 1/2.
E E (.s)
g'nD.r
1=1..
(-(=1)
Σ
(1/2 + yu.) yF((u')) Lob1 [ (FA,
sup (a)
i=
xE(=1)
and, similarly,
obl S..e (..,((,A))) (A,n)
excess (F,A,
(2)
Note that the 1/2 factor in the first equality for the loss comes from changing the label space from {0, 1) (=1}.
A poisoning scheme is collection [ of functions from Id to Id The scheme
S for all E [d. y E [=1}. and u E Id. Poisoning schemes are used to explicate the choice of E (.),). and so we define 2 and excess (F) by tweaking, in obvious way, the respective definitions of
g is said to have a poisoning budget ry (4), u) = 1/d- (M)) - w||
(E))(()) and excess (F)) Trivially, for all F: Id + Id and u E Id, we have excess = sup excess (F),
where the infimum is over all poisoning schemes with budget r)- We thus want prove that for every such there is u E 7d and poisoning scheme & with budget such that
(. 22 (2(dd)))
Lemma 12 (Ome-dimensional lower bound). For any v (0,1), there exist a (one dimensional) poisoning scheme& & = (5-1,51 with poisoning budgel and a distribution U over such that for any F: I I we have
VT
E excess obl (P) 2 w-ll
u.
16
Proof. We going to prove that such & and U exist for 17 S 1/16, and that they guarantee E, = Easu excess ebl
u.5 (F) 2 v Note that in this case, for v 2 1/16 (but still y S 1), we can thus enforce an excess of E1/16 V1/16/4 1/16, yielding the statement of the lemma for all v E (0,
So let nj S 1/16 and let m be a natural number such that vT/2 S (2m + 1)y S VQ S 1/2; easy to see that the condition on 1/ guarantees that such exists. Let U = {2in -m S i m).
Define the poisoning scheme (5-1.E1) E1) as
(2in) = +
(2in) (2i 1)n,
for ...... m and Cu(x) = (x)) = x for I, x # 2in. Clearly. the poisoning budget of { (5o. {1) is n. Let us now estimate the excess error for this poisoning scheme first at points 2in, for -m,- m, and then, in a different way, at points -(2m 1)n and (2m + 1)n. So, for
0 < i < m, and 26q;
excess o.
obl (F) = Σ (1/2 + yn) y (F()((1)) (1/2-M)
wE(11)
= -1/2 + u) (1/2-F((i(u))) + (1/2 u) (1/2+ F(E-1(u))) (1/2 - u)
F(u+ - F(uu 7))
+ u(( F(u n) - F(u F(u+n))
2
29

---

By similar computation, for -m I 0 and u 2i1;:
sxce (F) F(u + 11) - F(u -1) u(1 Flu 17) + F(u 1)).
2
In either case, for 2in and i= - m, have:
F(u 17) F(u 11)
excess obl (F)
(3)
At the same time, for (2m + 1)7, 5-1(0) - [i(u) = u, and so
abl (F) = Σ y1/2 yF(u)) - (1/2 u)
excess
u.t
yE{+1}
(1/2 + u1/1 - F(u))+ + (1/2 w) (1/2+ F(u)) - (1/2 - u)
= -1122 + F(u) = - (1/2-F(w))
-11/2 (1/2 (4))==((22)) -1/2-1111 F(u))
aa(1 - 2F())
Similarly, for (2m 1)m.
obl excess u.E (F) = - 2F())).
All in all, for (2m 1)7, we get
excess obl (F) = =lu((1 2sign(u)F(u))
(4)
Let us now define the tistribution U as follows: let U1 be a uniform distribution over U f2in m < i S m)
, let U2 be uniform distribution over {= + 1)m), and let U be U1 or Uz with probability 1/2 each. Trivially,
1
E excess oh uoll
(F)
abl E excess
u.f ( (F) + E
excessunn abl (F).
2 undl
2 u-lls
Let us estimate the two terms in the above using and 4 Below, we denote (2m + 1)m by t:
F(u + 11) F(u-u)
E excess
Ubl une
(F) by
E w-ld
uith
2
F(2km + 17) F(2k7 n)
F(t) - F(-t)
F(t) - F(-t)
2m
2
4m +
2
k=
and
1 +11 2F(-t))
E excess obl obl (F) [by
2 t(1 -2F()) +
unill
-t-1(F(1) F(-t))-
Combining, we get
1 1( t ((((t) F(-t))
F(t) F(-t)
E excess
obl (F)
+1
uoll
2
2t
212
1
212
+ (F(() - -(((()
2
2
4t
2
4t
2 12 t2 V
11
11
1
2
2
>
2
2
4f
44
4
30

---

Lemma 13 (Lower bound for F: Ist - 1²). Let be poisoning budget with < 1/d. There exists distribution U over and poisoning scheme with budget such that for any function F Td T we have
vdn
excess 1 (F)
16
Proof. By Lemmaa 12 there exists distribution U over I and poisoning scheme { (Eu.Li) with poisoning budget dn such that for any function F - I we have
vdn
E
excess
ebl u
16
Note that here we need dn < which is enforced by our condition on 1). Let us define a d-dimensional poisoning strategy {(Er,, {x.1)
(u) = (ui.... un (ui), us+1.-... ud)
Note that since the budget of & is dnj, the poisoning budget of & is 17. Now, for a given G Id - 1 let us define F F(G): + I as
d
F(t) =
wolled Σ
G. U4-1, u441.......... ud) = E((t,
where Fi(1) = En- Gi(ui,.... Uj 1, 1, 0/4 1i+l....,,d. Ud).
In words, F(t) is an expected value of G.(. .., ....... ) where is of the dimensions picked at random, plugged into the z coordinate, and the rest of coordinates a picked at random according to U. Moreover, by design, the expected excess error of F with is the same as of with ç, but let us nevertheless explicate it. In what follows, let mill,, =- min(1/2 ui, 1/2 + uz).
E excess andd
abl (G) = E
Σ i=l....d
Σ (1/2+ vu.) yGi(Er,, - minu.
w-l d
(+
drag
E aydll
for j o i, inside, all the way down to Gi
Σ
E Wirild
Σ vE(L1)
(1/2+
yw:)
1/2 1/2-
E
G.(Sip(u))
-inn
t=
jE(d--
rename u; and rewrite using
E
(w) (.)
uolf"
Σ
Σ
(1/2+ + yt) (1/2 1 y (EE((,(()))
min;
brlld
(=1)+
1 Σ Fi(()
now drag the average over all the way down to F,, and use F(t) d
E b-ld
Σ (1/2+ vt) (1/2- y. F(ÉU(())) min,
excess (F).
ball
2,6
0E(=1)
In particular, this implies
Vdy
E. excess obl (GT >
and
16
needed.
31

---

Lemma 14 (Lower bound of Theorem For any concept class '.. of VC dimension d 2 1, any randomized learner A (X x V) [0. 1]x, poisoning budget df 1/d and sample size 2 log
64 there exists distribution D such that vdn
Vdn
excessH, Dx (,
inf LD. (h) bER
16v2
In particular, for n > log
64 we have vān
excess D.n, 2 inf LD., (h) + Vdn
hCH
36
Proof. Recall that Lemma
13 applied to F = F(A, 1d + 1d, for an arbitrary sample size
implies that there a distribution D = Du. realizable by H and corresponding to u E 1 and poisoning scheme with budget 2 such that
excess ob1 u, (P 2 excess (F(A,))) > vdn
obl excess D,n/2 2 (A,
16
Here, the first equality is by (2 the second inequality is by the definition of poisoning scheme with budget, and the last one is by Lemma 13 where change probabilistic statement into existential one. Note that here we use the condition 17 < for compliance with the lemma.
Finally, exchanging the oblivious poisoning with regular one by Proposition we get:
ddn
(A, exceas p.ceas/p./22A11) 22.
16
Which gives the first assertion of the Lemma. For the second simple computation shows that for 64 have
log
din 16v2
ddn
dij
exp(log
= dnj
16v2
Vān
16v2
64
36
5.2 Proofs of Theorems2ane and
Theorem 2, For every learning rule Aprivr there exists a learning rule Apub such that for any distribution D, sample size n, and poisoning budget 1) E (0,1).
L. (Apub: n.) S LLD. [ n.)
Moreover, Apub can be constructed efficiently given black-box access to Apriv.
Note that originally Theorem 2 was stated in terms excess error; its equivalence with the present statement in terms of loss is straightforward.
Proof. In the proof, without losing generality, we identify the probability space of Apriv and Apub with [0, 1]. Let us define function A : 2 - [0, 1]x induced by Apriv. as
(())(x) = E (r).
And let Apab, if < A(S) and otherwise. Let 1 E (0, 1), and let D be some distribution. For each x E A' let us define functions Ex.0, En.1 2 + Z" by
(x, = max
A(S')(z), (')
(S) = arg min ('E
(z))
32

---

Note that, trivially, for y E {0, (x,g(S) E (S) and
(5) = arg max E Apriv, (5)) - y/- (S)
We claim that Apab, (Ex,)(S)x)) implies (z) y for all S' (S) Indeed
Apub.r (5x,1 = = [VS' E (, r r A(S)) = [VS' E BB, (S) 1],
Apub. (5x,0 =0 = (VS' E (,) r >> A(S")
= (VS' E B2( Apub, (S) = -).
Hence have
LD, LDD (ppivvn) n)
sup E Aprii,r - y/] S'EB(())
E
E (E.y =1 x
SwDn
S-D"
(EN))aD
(a,y)~D)
= E S-DA (2.9)~~
[IA(Ez.)()) vI]
E E sup ('),,
(S)) -yl] = =I. (Apub; n.)
S-D" (a.0)~D
Theorem (Poisoned Learning Curves). Let H. be a concept class with VC dimension d and ler n E (0, 1) be the poisoning budget. Then, for every learning rule A, there exists a distribution and an adversary that forces an excess error of at least O (min (dnn, 13) for infinitely many sample sizes n.
Proof.
The proof is by careful examination of the proof of Theorem 4 more precisely, of Lemmas For the rest the proof assume that 17 < d' otherwise the result is obvious.
13 and
14
First, we note that in Lemma 13 the parameter u E Id of the target distribution P.. demonstrating the high excess of F, F(A, n) is picked from distribution V on 1d, which has finite support and whose construction is independent on Thus, by pigeonhole principle, there is E 1 such that for D D,, and for infinitely many n
Vān
obl (A, n) = excess obl excess
u,u ( (F(A, n)) 2 16
Which by Proposition limplies
ddn
excessp,
(,, (A, 2 excess abl 22, -
no/2
16v2
And since 16
dan
<
v 36
for only finitely many n's, we deduce that for infinitely many n
excessD,,(A,)) 2 dd
33


Reviews:
[{"review_id": "uXqfnSUTu2", "reviewer": "Reviewer_Yaf2", "summary": "This paper follows with the Hanneke et al. (NeurIPS 2022), study the problem of learning with an adversary that can corrupt $\\eta$ fraction of the training examples in order to cause error on a given point.Author gives an upper and a lower bound about $O(\\sqrt{d\\eta})$ for excess error for random algorithm. Then, for the Private and Public poison problem, author shows that under public, we can guarantee the robustness as good as private.  In Technical Overview, author shows how to use coin problem to solve their theorem.", "questions": "Question:\n\n1:How is the target of attack (cause error on a given point) reflected in the theorem 1? The author mainly analysis the excess error.\n\n2: In th2, if we take $A_{priv}$ as SGD, what is $A_{pub}$?\n\n3: How to verify th1 in experiment?", "limitations": "no.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strong:\n(1): This paper is easy to read.The theory is novel.\n\nWeakness:\nI am not particularly familiar with this field, but some parts of the theorem do confuse me.(If author can well answer, I will improve my score)\n\n(1)\t:The boundaries given in the Th1 seem too loose in the real world, because VC-dim d is always much large than poison rate $1/\\eta$, such as poison $1\\%$ for ResNet trained on CIFAR-10. \n\n(2):Theorem 2 only compared the robustness of two algorithms(Private and Public) in poisoning, but did not analyze their accuracy on clean data. As is well known, improving robustness may lead to a decrease in generalization, but the author did not discuss this point\n\n\n(3): In Theorem 3, the author states that for an infinite number of n samples, the excess-error will be $O(\\sqrt{d\\eta})$, but does not mention the probability of sampling such n samples, which should be mentioned. On the other hand, designing distributions and attack methods based on training set size $n$ seems to be impractical in the real world, what is the importance of th3?", "was_revised": true, "final_justification": "The author has solved most of my questions.", "rebuttal": "We thank the reviewer for taking the time to read our paper, reflect on its contributions, and share constructive comments. As detailed below, we will take these suggestions into account in the next revision of the manuscript.\n\n⸻\n\n**(1) Concern about the VC dimension in Theorem 1 being too large in practice.**\n\nWe agree that for real-world models such as ResNet trained on CIFAR-10, the VC dimension can be extremely large. However, this reflects a well-known limitation of the classical PAC framework, which provides distribution-free guarantees and quantifies over all possible data distributions.\n\nIn many practical settings, it is more appropriate to adopt data-dependent assumptions that make the learning problem more tractable and effectively decouple the VC dimension from the number of parameters. A canonical example is the analysis of support vector machines and kernel methods in infinite-dimensional spaces, where generalization depends not on the parameter count but on properties like the margin of the data. Such assumptions are conveniently formalized within the framework of PAC learnability of partial concept classes [1], which extends the classical PAC model to incorporate structure or distributional constraints.\n\nIn this work, we focus on the basic PAC model to establish general upper and lower bounds. That said, our lower bound in Theorem 1 applies to partial concept classes as well, while the upper bound does not directly extend, as it relies on covering arguments. We will include this observation and suggest the extension of our results to partial concept classes as a direction for future work in the next draft.\n\n[1] A Theory of PAC Learnability of Partial Concept Classes. Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. FOCS 2021\n\n⸻\n\n**(2) Concern that Theorem 2 does not analyze performance on clean data.**\n\nTheorem 2 applies for any poisoning rate η, including η = 0, which corresponds to clean data. In this case, the result becomes somewhat trivial since the adversary has no influence over the training data. Still, the guarantee holds: the algorithm with public randomness performs no worse (in terms of excess loss) than the one using private randomness.\n\n⸻\n\n**(3) Concern about the interpretation and importance of Theorem 3.**\n\nThe goal of Theorem 3 is to investigate whether stronger guarantees on excess loss can be achieved by moving from the worst-case, distribution-free PAC framework to the more fine-grained, distribution-dependent setting of universal learning [2].\n\nIn the absence of data poisoning (i.e., η = 0), it is well known that PAC learning rates scale as VC/n in the realizable case and as √(VC/n) in the agnostic case. In contrast, in the universal learning framework—where performance is measured pointwise over distributions—many hypothesis classes (including every online learnable class) enjoy significantly faster rates, often with exponentially fast decay of the learning curve.\n\nThis raises the natural question: can one beat the √(dη) bound from Theorem 1 by moving to the universal setting? Theorem 3 shows that the answer is negative—despite the extra granularity of universal learning, the same asymptotic √(dη) limitation persists. We will clarify this motivation in the revised text.\n\n[2] A Theory of Universal Learning. Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, and Amir Yehudayoff. STOC 2021\n\n⸻\n\n**Responses to Additional Questions:**\n\n- Q1: How is the target of attack (cause error on a given point) reflected in Theorem 1?\n\nTheorem 1 guarantees that for any learning algorithm, the adversary we construct can force an excess loss of at least roughly √(dη), where d is the VC dimension and η is the poisoning rate. This excess loss is uniform across all algorithms.\n\nHowever, the absolute error rate on the target point (i.e., the total loss) depends on the specific distribution chosen by the adversary, which in turn may depend on the algorithm being attacked. For some algorithms, the total loss on the target point may approach 0.5; for others, it may be significantly lower. We will clarify this point in the revised version.\n\n⸻\n\n- Q2: In Theorem 2, if we take the learner to be SGD, what is the corresponding public learner?\n\nTo implement the public learner, it suffices to estimate the probability P that the private learner predicts label 1 on the given test point x. Once P is estimated, the public learner draws a random number R uniformly from [0,1]; if R < P, it outputs label 1, and otherwise it outputs 0. This simulates the private learner’s behavior using only public randomness.\n\n⸻\n\n- Q3: How to verify Theorem 1 experimentally?\n\nTheorem 1 is an information-theoretic result that quantifies over all distributions, all adversaries (in the upper bound), and all learning algorithms (in the lower bound). As such, it is not meant to be verified empirically—doing so would require checking infinitely many cases, even for simple hypothesis classes. That said, the mathematical proof certifies the validity and tightness of the bounds.\n\nEmpirical exploration might still be meaningful for fixed distributions and concrete attack strategies relevant to real-world applications, but such experiments lie beyond the scope of this theoretical work."}, {"review_id": "ZvpXcjIEQV", "reviewer": "Reviewer_EBae", "summary": "This paper addresses the *instance-targeted* poisoning problem, in which a Learner must effectively predict a test point in the presence of an adversary that can corrupt a fraction of the training examples. It specifically addresses a problem left open by Hanneke, Karbasi, Mahmoody, Mehalel, and Moran 2022: if there exists an (optimal) *randomized* learner that can learn in this instance-targeted poisoning setting in the general agnostic model of learning. The aforementioned paper of Hanneke, Karbasi, Mahmoody, Mehalel, and Moran 2022 address this problem in the *realizable* setting (proving optimal rates) and show the impossibility of a *deterministic* learner of achieving this in the agnostic case. This current paper's main result shows that, in fact, a *randomized* (proper) learner can achieve an optimal rate of $\\Theta(\\sqrt{d \\eta})$ in the agnostic case of instance-targeted poisoning. The main results of the paper exhibit a lower bound $\\Omega(\\sqrt{d \\eta})$ by reducing to what the authors call the \"poisoned coin problem\" and an upper bound by way of simply running exponential sampling over the hypothesis class $\\mathcal{H}$.", "questions": "There are a couple of minor questions I have with some of the notation of the paper to address clarity:\n\n1. On page 5: Step 2 of the \"Poisoned Coin Problem with Oblivious Adversary\" description is somewhat unclear to me. Why are you repeating the draw of the target label twice? Maybe this is just a typo.\n2. On page 5: As a minor detail, in the description of the \"$d$-Coin Problem,\" it would be helpful to explicitly include the adversary's choice of $p_1, \\dots, p_d$ especially because this plays a key role in the \"fix\" of the construction. Also, I was wondering -- for the lifting to the VC dimension case, is it still the case that the lower bound is proven for an oblivious adversary? In the box for the \"$d$-Coin Problem,\" it says that the adversary does indeed observe the training set and target example. So I was wondering if the formal reduction is to the oblivious case as well when we deal with $d$ coins?\n3. If space permits in Section 2.2 for the Upper Bound, it might be helpful to formally state the anti-concentration property as a lemma as it is key to the argument.\n\nAs a general question:\n\n4. It seems that the definitions of excess error in this setting given in Section 4 address in-expectation quantities. Do these same results port over to high probability? Or are there additional tools needed besides standard concentration arguments?", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths \n\nThis paper's main results present a lower bound and upper bound for learning under instance-targeted poisoning in the agnostic setting, where an adversary has a general $\\eta \\in (0, 1)$ poisoning budget. It is generally well-written and clear, and it does address an existing open problem in the literature.\n\n**Originality:** The paper seems, to my knowledge, original in the tools it uses to address an existing open problem. Although the authors note that the aforementioned Hanneke et al. paper in 2022 introduced the reduction to the poisoned coin problem, the authors adapt the lower bound to their setting and, interestingly, also show that the \"hard distribution\" is stronger than traditional PAC-style bounds in that the adversary has a single fixed distribution instead of a distribution tailored to $n$ (the sample size). They do this by essentially allowing the adversary to construct the hard distribution (which is a set of biases $p_1, \\dots, p_d$ for $d$ coins) not by fixing these biases deterministically, but, rather, letting the adversary *draw* the biases (in a somewhat \"Bayesian prior\" way) over a fixed distribution over $[0, 1]$. For the upper bound, the author's techniques must be original because the prior work in this subfield established that it is impossible to achieve an upper bound for this setting with a deterministic learner. Indeed, the authors show that, with a specific exponential sampling mechanism, they can achieve the upper bound as well.\n\n**Quality:** The paper's claims seem to be technically correct, at least when judging the proof sketches. One issue that I had was further intuition and discussion towards how the constructions the authors introduce might be relevant in a defense to a real-world adversarial poisoning attack, but, because this is a theory paper, that would just be a nice cosmetic addition. \n\n**Clarity:** The authors provide clear proof sketches and lay out the paper's results in an intuitive and organized way. In particular, the main theorems were nicely outlined and it was mostly clear in the lower bound exposition what the \"hard\" problem was and what the main steps to developing the algorithm was in the upper bound section. There are a couple of small confusing possible typos that I found in some notation, which is outlined in the **Questions** section.\n\n**Significance:** The work fills in an existing gap in our understanding of the instance-targeted poisoning problem, particularly in the agnostic case. With that, it does round out the entire basic understanding of this setting, as sharp results for the realizable case have also been shown. I am not entirely familiar with this line of literature (and the broader poisoning attack literature in general), so I cannot be a judge to whether this particular *subfield* is significant in the broader research agenda in adversarial ML. However, as a specific learning theory paper addressing a specific problem, it does address and close an open question.\n\n## Weaknesses\nOne might point that the main possible weaknesses of the paper might be that the problem's solutions don't introduce any new technical techniques. The lower bound appeals to an existing hard problem (the poisoned coin problem) but it wasn't entirely clear to me what the new technical additions were needed to address the agnostic case. It would be helpful to include a sentence or two about this in the lower bound section to make clear how this hard distribution differs from the realizable construction. For the upper bound, the algorithm itself is not terribly complex, though I don't think that's necessarily a knock on the paper -- if a simple algorithm suffices, then a simple algorithm suffices. This all being said, the paper clearly sets out to address a known open problem and rounds out our understanding of a learning-theoretic setting, so I believe how \"technical\" the means to those ends are secondary to the fact that these results are sharp.", "was_revised": true, "final_justification": "I maintain my original positive score but emphasize that my confidence is not as high as reviewers that are more familiar with the subfield.", "rebuttal": "We thank the reviewer for a thorough elaboration on the paper and for his or her constructive remarks. Here's our address of the points raised: \t\n\n- Weakness: How does the coin problem get adapted to the setting of the paper? - While the coin problem was indeed introduced in Hanneke et.al., and even in the context of an agnostic setting, the learner there was assumed to be deterministic. Allowing it to be randomized changes the problem quite substantially, both in terms of the result and the technique needed to obtain it. We added a note pointing this out in the paper.  \n\n- Q.1. Typo in Step 2 of the description of the ``Poisoned coin with Oblivious Adversary.'' - Yes, this was a typo, fixed.\n\n- Q.2. Description of the $d$-Coin Problem. - First of all, as suggested, we've emphasized the adversarial choice of $p_1, \\dots, p_d$. Then, you are right - the lower bound in the general case is indeed proven via oblivious adversary, and we added the respective note to the paper text.\n\n- Q.3. Anti-concentration bounds. - Sorry for the confusion. While anti-concentration bounds can indeed be used to prove the upper bound for the toy 1-coin problem, we failed to adapt this approach to the real problem, and used instead the exponential mechanism from differential privacy. Thus, the anti-concentration is not used, and is mentioned only as an analogy. We clarified this in the text, and, because of that, and also due to space restrictions, we are not adding their exact formulation. On a private note, for 1-coin, one can use, for example, Khintchine's for $p=1$, that is, that the sum of $n$ Bernoullis is w.h.p. at distance ~ $O(\\sqrt{n})$ from their expected value.\n\n- Q.4. Do results generalize from in-expectation to high-probability? - This is an interesting question, and our gut feeling is that essentially the same bounds should hold also w.h.p., essentially because the exponential mechanism used in the learner that witnesses the upper bound is ``rather smooth''. However, exploring this direction, even formulating the relevant definitions, requires a fair amount of technical work. Thus, we will not address it in the present paper."}, {"review_id": "9xdYSigh2W", "reviewer": "Reviewer_fdBF", "summary": "The paper studies the instance-targeted poisoning attack where the adversary can observe the target instance and the corrupt $\\eta$ fraction of the training sample, with the goal of forcing the learner to make a mistake on the test instance. This problem has previously been studied under the realizable case and this paper extends it to the agnostic setting. A main result of the paper is the optimal excess error, i.e., the difference in error with the approximation error of the class for clean datasets, is $\\Theta (\\sqrt{\\eta d})$, where $d$ is the VC dimension. The second interesting result is showing that private randomness does not help and the above excess rate error holds even when the randomness of the learner is public to the adversary. Moreover, the construction of the hard distribution for lower bound is not specific to the sample size as opposed to usual constructions in PAC learning. It is based on finding a finite set of hard distributions which proves that there is a fixed one that is hard for infinitely many samples sizes.", "questions": "It seems that the learner needs the knowledge of the poisoning budget. Is it clear (maybe from prior work) what happens if we want to relax such an assumption? Does the problem become significantly harder or are there straightforward techniques that can remove such a dependence with slight blowups in error rate?\n\nIs it possible to consider a setting where the target is a test set rather than a single instance? The adversary then has the goal of making the learner to error on as many test instances as possible. I think we should know that the error rate in this case is still bounded by $O(\\sqrt{\\eta d})$. Is it possible to get better error rates? I am not much familiar with the setting of prior work and I am not sure how useful such a setting would be.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I think generalizing this problem to the agnostic setting is a reasonable next step in this line of research and the result of the paper kind of answer the relevant questions under this setting in the agnostic case. I also think showing that private randomness cannot protect against such attacks is an interesting result of the paper. I still think the authors could have added more detail for other parts, e.g., the private vs. public randomness in the main paper. Maybe this is something that the authors can try for the camera-ready version. This is just a suggestion.", "was_revised": true, "final_justification": "My initial assessment of the paper was positive. After reading rebuttals, I still keep my score. The authors explained well my questions and I agree that some of the questions are for future work. I raised them because the paper provokes them, which makes me believe the problem studied is an interesting research direction.", "rebuttal": "We thank the reviewer for his or her excellent questions. Those are, to our view, some nice and interesting research directions, and we consider adding them as open questions (and acknowledge the anonymous reviewer for proposing them). \n\nWe can hardly say anything on top of that regarding Question 1: How will the setup change if the learner does not know the poisoning budget? - It is indeed quite natural, but we have no idea of how to approach it at the moment.\n\nHowever, something can be said about Question 2: Is it possible to consider a setting where the target is a test set? - Standard uniform convergence arguments imply that any ERM on the (possibly poisoned) training sample will, on average, have test error at most $\\sqrt{\\frac{d}{m}} + \\eta$ on a random test set of size $m$. Hence, when $m > \\frac{1}{\\eta}$, this bound becomes better than the worst-case bound we provide. More generally, it seems possible to interpolate between the case of a single test point (where the optimal error scales as $\\sqrt{d\\eta}$) and the case of a large test set (where the optimal value should approach $\\eta$)."}, {"review_id": "Gj71kL4iMi", "reviewer": "Reviewer_yng4", "summary": "The setting\n\nThe paper studies PAC learning in the targeted poisoning model, building on [Hanake et al 2022] and preceding work. This setting is defined as follows: \n- As in standard PAC learning, there is some hypothesis class $\\mathcal{H}$.\n- The adversary receives a collection $S$ of i.i.d. labeled samples from a distribution $D$, and has the power to corrupt $\\eta$ fraction of elements in $S$. \n- As in standard PAC learning, in the **realizable setting**, the original dataset $S$ is labeled by a function in $\\mathcal{H}$. In the **agnostic setting** this is not the case, and the best error in $\\mathcal{H}$ is used as a benchmark.\n- The goal of the adversary is to force the learning algorithm to misclassify some specific point $x_0$, which is **drawn in the very beginning** from the sample distribution $D$ and given to the adversary.\n\nFor a specific choice of learning algorithm $\\mathcal{A}$ and an adversary, the **adversarial loss** in this model is defined to be the probability (over all random variables including $x_0$) that the learning algorithm indeed misclassifies $x_0$ (and thus the adversary succeeds). Overall, this setting models the situation when the adversary wants the learning algorithm to misclassify some specific input $x_0$. \n\nThere are two distinctions that are important to keep in mind:\n- As mentioned earlier, the setting can be **realizable** and **agnostic**.\n- The learning algorithm $\\mathcal{A}$ can be **deterministic** or it can be **randomized**. A deterministic learner outputs a classifier based only on the training dataset,  whereas a randomized learner can utilize additional random bits in addition to the training dataset.\n\nIt is slightly subtle how the goal of the learning algorithm is defined in the agnostic setting: the goal is to bound the **excess loss**, which is defined as the difference between (a) the **adversarial loss** defined above and (b) the minimum prediction error OPT in the class $\\mathcal{H}$ on the distribution of $D$ from which data is drawn prior to being poisoned by the adversary.\n\nResults\n\nThe paper focuses on the **agnostic** setting and allows the learning algorithm to be **randomized**. \nIf $d$ denotes the VC dimension of the class $\\mathcal{H}$, the paper gives upper and lower bounds of $\\tilde{\\Theta}(\\sqrt{d\\eta})$ for the excess loss in this setting. In other words, the paper shows that there is a learning algorithm that achieves excess loss of  $\\tilde{O}(\\sqrt{d\\eta})$, and this amount of loss is provably unavoidable.\nPrevious work [Hanake et al 2022] gave a bound of $\\Theta(d\\eta)$ for the realizable setting.\nThis fully characterizes the realizable setting, leaving open only the agnostic setting, in which:\n- The work of [Hanake et al 2022] gave a bound on the adversarial loss of $C\\cdot OPT+\\Theta(d\\eta)$ where $C$ is an absolute constant. [Hanake et al 2022] show that a multiplicative constant $C$ is necessary here, as long as a **deterministic** learner is used.\n- As explained earlier, this work gives an algorithm with adversarial loss by $OPT+\\Theta(\\sqrt{d\\eta})$. The impossibility result of [Hanake et al 2022] is side-stepped by using a randomized learning algorithm.\n\nAdditionally,  the upper bound given in this work is shown to work even if the adversary knows in advance the random bits utilized by the learning algorithm.\nThe work also gives lower bound instances that force excess error $\\tilde{\\Omega}(\\sqrt{d\\eta})$ for infinitely many dataset sizes $n$ (as opposed to having a different instance for each $n$).\n\nTechnical summary\n\nThe algorithm given in this work samples a classifier randomly from via a procedure inspired by the exponential mechanism. To handle continuous hypothesis classes, the paper uses a covering argument in order to go from a continuous hypothesis class to a discrete collection of functions.\n\nThe hardness result is conceptually based around a reduction to the poisoning coin problem from [Hanake et al 2022]. The main technical challenge is connected to handling information leakage: in a naive construction the behavior of non-target coins may reveal information about the target coin. This technical challenge is handled via sampling the biases of different coins independently from a certain distribution.", "questions": "- Suppose we want to establish high-probability bounds on the excess adversarial loss, rather than bounds on the expected adversarial loss. Does your work give such bounds?\n- Are you aware of any work in ML security for which the poisoning budget is less than the inverse of the number of model parameters? \n- Could you elaborate on similarities and differences of your work and [Bassily et al. 2019] and [Dagan and Feldman 2020]?", "limitations": "My understanding is that requiring the poisoning budget to be at most the inverse of the VC dimension could be a large limitation from the point of view of potential future impact on ML security. I think the work would benefit from discussing in more detail potential limitations due to this. Other than this, I think that the limitations are addressed.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The problem is fairly natural, and was studied in the previous work.\n- The loss bounds are quite tight, because the work gives matching upper and lower bounds on excess risk up to logarithmic factors. \n- The algorithmic approach based on exponential sampling could provide useful tools for future work. However, the paper does note that a similar approach was used in [Bassily et al. 2019] and [Dagan and Feldman 2020].\n\nWeaknesses\n- Arguably the more natural realizable setting was already solved in [Hanake et al 2022].\n- I am not sure how much interest there within ML security community in methods for which the poisoning budget has to be less than $1/d$. This could potentially limit future impact of this work.\n\nSome minor typos:\n- Line 137 “as follow” should be “as follows”\n- Between lines 137 and 138: “A target label y os drawn” -> “A target label y is drawn”", "was_revised": true, "final_justification": "Good paper, but has some weaknesses potentially undermining the relevance of the paper. Authors note that the weaknesses could potentially be addressed, but leaves this for future work.", "rebuttal": "We thank the reviewer for the detailed review and constructive suggestions. The questions raised are quite profound, or at least require substantial technical elaboration, so, unfortunately, we are not able to properly address them in the revision; however, we will flag them for future directions. Below, we give a detailed elaboration on them.\n\n- The reviewer comments that the realizable setting was already addressed in prior work [Hanneke et al. 2022].\n\nWe note that the realizable and agnostic settings are complementary: each captures a different aspect of the learning landscape. While the realizable setting assumes the existence of a perfect concept that classifies all points correctly, the agnostic setting allows for arbitrary noise and aims to compete with the best possible hypothesis in a class of models. Both frameworks are well-established and widely studied in learning theory.\n\nOne advantage of the agnostic setting is that it offers robustness to small deviations from ideal assumptions. In many practical scenarios, even when highly accurate classifiers exist, they may still incur some small but nonzero error—i.e., a nearly realizable setting that lies between the strict realizable and fully agnostic regimes. The agnostic framework captures this more realistic scenario and provides more resilient guarantees.\n\nThis actually motivates further investigation into intermediate regimes such as near-realizability, which better reflect practical learning settings and offer a more nuanced understanding of robustness in the presence of noise.\n\n- Typos\n\nFixed. Thanks.\n\n- Q.1. Do results generalize from in-expectation to high-probability? \n\nThis is certainly a valid line of inquiry, and our gut feeling is that essentially the same bounds should hold also w.h.p., essentially because the exponential mechanism used in the learner that witnesses the upper bound is ``rather smooth''. However, exploring this direction, even formulating the relevant definitions, requires a fair amount of technical work. Thus, we do not address it in the present paper. \n\n- Q.2. Poisoning budget less than $1/d$, where $d$ is the number of parameters.\n\nWe agree that for real-world models, the VC dimension can be extremely large. However, this reflects a well-known limitation of the classical PAC framework, which provides distribution-free guarantees and quantifies over all possible data distributions.\n\nIn many practical settings, it is more appropriate to adopt data-dependent assumptions that make the learning problem more tractable and effectively decouple the VC dimension from the number of parameters. A canonical example is the analysis of support vector machines and kernel methods in infinite-dimensional spaces, where generalization depends not on the parameter count but on properties like the margin of the data. Such assumptions are conveniently formalized within the framework of PAC learnability of partial concept classes [1], which extends the classical PAC model to incorporate structure or distributional constraints.\n\nIn this work, we focus on the basic PAC model to establish general upper and lower bounds. That said, our lower bound in Theorem 1 applies to partial concept classes as well, while the upper bound does not directly extend, as it relies on covering arguments. We will include this observation and suggest the extension of our results to partial concept classes as a direction for future work in the next draft.\n\n[1] A Theory of PAC Learnability of Partial Concept Classes. Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. FOCS 2021\n\n- Q3. Similarities and differences with [Bassily et al. 2019] and [Dagan and Feldman 2020]\n\nBoth mentioned papers study a different setup—namely, differentially private (DP) learning—but a parallel arises when designing learners that are resistant to poisoning attacks. Since a poisoner’s budget is limited, one strategy for achieving robustness is to ensure that the learner behaves similarly on similar datasets. This idea aligns with the stability guarantees required by DP, and so techniques from DP learning become relevant.\n\nThe general approach of first constructing a finite $\\varepsilon$-cover of the hypothesis class and then using it to learn is classical in statistical learning theory. In our setting, we use this approach in combination with the exponential mechanism to select a hypothesis. This template also appears in [Dagan and Feldman 2020] and [Bassily et al. 2019] in the context of differentially private (DP) learning, and we apply it here in the context of poisoning robustness. While the high-level structure is similar, there are several technical differences.\n\nIn particular, our setting requires robustness not just to individual data point changes (as in standard DP), but to adversarial modifications of an entire $\\eta$ fraction of the training set. This corresponds to what is known in the DP literature as group privacy, but in our case the group size is substantial. These strong stability requirements necessitate a different approach compared to [Dagan and Feldman 2020] and [Bassily et al. 2019]. Most notably, the proof and analysis of our algorithm are substantially different and also the parameters of the exponential mechanism are tuned differently due to our different stability requirement.\n\nOur analysis critically requires an $\\varepsilon$-cover constructed using only $\\tilde{O}(1/\\varepsilon)$ examples—a realizability-type bound obtained by considering the class of symmetric differences of concepts—which is essential for achieving our excess error guarantees. In contrast, the more standard agnostic-type bound of $\\tilde{O}(1/\\varepsilon^2)$ (which follows directly from uniform convergence) would not suffice for our purposes. A similar reliance on the faster $\\tilde{O}(1/\\varepsilon)$ rate appears in [Bassily et al. 2019], where it is used to minimize the number of public data points required in their semi-private learning framework. Although the same covering property is used, our proof differs substantially due to the distinct objectives and stability requirements in our setting. We note that Dagan and Feldman [2020] also rely on the linear-in-$1/\\varepsilon$ bound when constructing their cover; however, in their case, this yields only a quantitative improvement in privacy guarantees. In contrast, our analysis fundamentally hinges on this tighter bound—resorting to the more naïve quadratic $\\tilde{O}(1/\\varepsilon^2)$ rate would cause the argument to fail entirely."}]

Author rebuttal:

Meta-review: This paper delivers ​exceptional theoretical contributions: resolving an open problem with tight bounds, introducing algorithmic innovations, and redefining assumptions about randomness in adversarial settings. While practical deployment faces inherent PAC limitations (e.g., large d), the work provides foundational insights that will influence multiple ML subfields. The authors’ rigorous engagement with reviewers solidified unanimous support. I endorse ​acceptance​.
Decision: Accept (spotlight)