Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness

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.

• The reviewer comments that the realizable setting was already addressed in prior work [Hanneke et al. 2022].

We 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.

One 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.

This 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.

• Typos

Fixed. Thanks.

• Q.1. Do results generalize from in-expectation to high-probability?

This 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.

• Q.2. Poisoning budget less than $1/d$, where $d$ is the number of parameters.

We 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.

In 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.

In 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.

[1] A Theory of PAC Learnability of Partial Concept Classes. Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. FOCS 2021

• Q3. Similarities and differences with [Bassily et al. 2019] and [Dagan and Feldman 2020]

Both 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.

The 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.

In 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.

Our 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.

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).

We 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.

However, 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$).

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:

• 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.

• Q.1. Typo in Step 2 of the description of the ``Poisoned coin with Oblivious Adversary.'' - Yes, this was a typo, fixed.

• 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.

• 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.

• 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.

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.

⸻

(1) Concern about the VC dimension in Theorem 1 being too large in practice.

We 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.

In 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.

In 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.

[1] A Theory of PAC Learnability of Partial Concept Classes. Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. FOCS 2021

⸻

(2) Concern that Theorem 2 does not analyze performance on clean data.

Theorem 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.

⸻

(3) Concern about the interpretation and importance of Theorem 3.

The 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].

In 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.

This 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.

[2] A Theory of Universal Learning. Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, and Amir Yehudayoff. STOC 2021

⸻

Responses to Additional Questions:

• Q1: How is the target of attack (cause error on a given point) reflected in Theorem 1?

Theorem 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.

However, 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.

⸻

• Q2: In Theorem 2, if we take the learner to be SGD, what is the corresponding public learner?

To 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.

⸻

• Q3: How to verify Theorem 1 experimentally?

Theorem 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.

Empirical 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.