Pith. sign in

REVIEW 1 major objections 6 minor 14 references

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

T0 review · 1 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that randomized learners achieve the optimal $\tilde{\Theta}(\sqrt{d\eta})$ excess error under instance-targeted poisoning in the agnostic setting, resolving the main open problem left by prior work on targeted data…

desk verdict Right answer to a real open problem, and likely repairable, but the lower-bound proof as written has a false inequality in Lemma 12 that invalidates the stated constant. read the letter →

arxiv 2506.03075 v1 pith:ZILQOVSN submitted 2025-06-03 cs.LG math.PR

Bogdan Chornomaz , Yonatan Koren , Shay Moran , Tom Waknine This is my paper
classification cs.LGmath.PR MSC 68Q3268T05
keywords agnosticlearningtargeteddatapoisoninginstance-targetedattacksrandomizedlearnersVCdimensionexcesserrorpublicrandomnessadversarialrobustness
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper resolves the question of whether randomized learners can learn agnostically when an adversary may corrupt an $\eta$-fraction of the training sample after observing the test point. It establishes that the optimal achievable excess error for a concept class of VC dimension $d$ is $\tilde{\Theta}(\sqrt{d\eta})$, up to logarithmic factors. In the realizable case the optimal error scales as $d\eta$, so the agnostic rate is the square root of that, and randomness is the reason: deterministic learners were previously known to be forced into near-maximal error even for tiny $\eta$. The paper also shows that giving the adversary full visibility of the learner's random seed does not hurt, and that the lower bound holds for a single fixed hard distribution for infinitely many sample sizes.

What carries the argument

The machinery has three load-bearing parts. First, the poisoned coin problem, where the hypothesis class is just two constants over a single point and the adversary shifts the bias within an $\eta$-ball; the lower bound analyzes the learner's expected prediction $F(p)$ and shows $F$ must change by $\Omega(\sqrt{\eta})$ across a critical window, yielding Lemma 12. Second, the $d$-coin direct sum: biases for the $d$ coordinates are drawn independently from a finite-support hard distribution $U$, breaking information leakage, so the expected excess over $U^d$ is at least $\sqrt{d\eta}/16$. Third, on the upper-bound side, the central object is a prediction-stable learner: a randomized rule whose output distribution changes by at most $O(t\eta)$ in total variation under $\eta$-fraction sample perturbations, built from exponential sampling over an $\varepsilon$-cover; stability plus a low clean-excess bound gives the final $\tilde{O}(\sqrt{d\eta})$ guarantee. The public-randomness result uses a monotone coupling between outputs on $\eta$-close samples.

What would settle it

Check Lemma 12's final estimate: the step $t/2 - \eta/(4t) \geq \eta/(4t)$ requires $t^2 \geq \eta$, but the proof only establishes $\sqrt{\eta}/2 \leq t \leq \sqrt{\eta}$. At $t = \sqrt{\eta}/2$, the left side is $-\sqrt{\eta}/4$ while the right side is $\sqrt{\eta}/2$, so the asserted chain fails; a reader can settle the lemma by determining whether a different choice of the hard distribution repairs this step.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: for any concept class with VC dimension $d$ and poisoning budget $\eta$, the optimal excess error under instance-targeted poisoning is $\tilde{\Theta}(\min\{\sqrt{d\eta},1\})$. The upper bound is achieved by a proper randomized learner that draws a random subsample of size $\tilde{\Theta}(\sqrt{d/\eta})$, builds a finite $\varepsilon$-cover of the class on that subsample, and samples a hypothesis with probability proportional to $\exp(-\lambda \cdot \text{empirical loss})$—a rule whose prediction stability is controlled by the coupling of its randomness. The lower bound proceeds through a poisoned coin problem: a one-dimensional bias-shifting scheme forces any learner to suffer $\Omega(\sqrt{\eta})$ excess on a single coin, and a direct-sum argument with independently randomized biases extends this to $d$ coins and hence to any class of VC dimension $d$. A separate theorem shows that a learner whose random bits are fully visible to the adversary can match any private-randomness learner, via a monotone coupling of predictions; another shows that the lower bound is witnessed infinitely often by one fixed distribution.

Load-bearing premise

The lower bound for arbitrary VC classes rests on a one-dimensional coin lower bound (Lemma 12) whose proof's final display contains an invalid inequality chain; the $\sqrt{d\eta}$ lower bound collapses if that lemma cannot be repaired.

Editorial extensions

If this is right

  • Agnostic learning under instance-targeted poisoning is possible at all, and the optimal excess error is $\tilde{\Theta}(\sqrt{d\eta})$: randomized learners suffice and are necessary.
  • Deterministic learners are not merely suboptimal but catastrophically vulnerable; any successful agnostic learner in this model must randomize.
  • Public randomness is as good as private randomness: the adversary's knowledge of the random seed does not increase the achievable excess error.
  • The lower bound is not an artifact of distribution tailoring per sample size: one fixed distribution forces $\Omega(\sqrt{d\eta})$ excess for infinitely many sample sizes.
  • When the sample size is below the poisoning threshold ($n < 1/\eta$), the problem degrades to standard PAC learning with rate $\Theta(\sqrt{d/n})$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the lower-bound proof is repaired, the $\sqrt{d\eta}$ rate suggests a general square-root law for agnostic robustness: the adversary's budget enters quadratically less severely than in the realizable case, because the learner's uncertainty about the Bayes-optimal label already contributes error at the $\sqrt{d/n}$ scale.
  • The monotone-coupling argument for public randomness is a general recipe: any learner whose predictions can be coupled monotonically across adjacent samples inherits public-randomness robustness, a property that may transfer to other data-dependent attack models.
  • The finite-support hard distribution over biases in Lemma 12 could be converted into concrete attacks: one only needs to locate the critical bias window for a given learner's prediction function.
  • A natural testable extension is to multiclass or non-binary loss settings; the coin and $d$-coin constructions suggest the rate may depend on a metric or combinatorial dimension of the loss rather than merely the VC dimension.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 6 minor

Summary. The paper studies agnostic learning under instance-targeted poisoning, where an adversary corrupts an η-fraction of the training sample after seeing the test point. The main claim is that the optimal excess error for a class of VC dimension d is eΘ(√(dη)): an upper bound via a randomized learner based on exponential loss weighting over a random subsample, and a matching lower bound via a poisoned-coin hard distribution that is universal in a strong sense (a single fixed distribution works infinitely often). The paper also proves that public randomness is equivalent to private randomness (Theorem 2) and that the lower bound holds along learning curves (Theorem 3). The upper-bound proof is constructive and largely self-contained; the lower-bound proof rests on a one-dimensional coin lemma (Lemma 12) whose final displayed inequality is invalid. Since the subsequent direct-sum lemmas (Lemmas 13 and 14) invoke Lemma 12, the lower bound is currently unproven as written, although the defect appears repairable.

Significance. If the result stands, it resolves a main open problem from Hanneke et al. (2022), showing that randomized learners are necessary and sufficient for agnostic learning under instance-targeted poisoning, and that the optimal rate is eΘ(√(dη)). The paper's strengths include: an explicit randomized learner with a clean stability analysis; a nice use of ε-covers of size Õ(d/ε) for VC classes; a black-box reduction from private to public randomness (Theorem 2) via a monotone coupling; and a lower-bound construction that randomizes biases to prevent information leakage, a potentially reusable idea. The main weakness is technical: the one-dimensional lower-bound lemma contains an algebraic error, and because the multi-dimensional lower bound and the learning-curves theorem build directly on it, the paper's central lower bound is not yet established. For these reasons, the contribution is significant and the approach is promising, but the proof currently does not justify the stated result.

major comments (1)
  1. [Section 5.1.2, Lemma 12] The final displayed chain in the proof of Lemma 12 is invalid. The authors derive E ≥ t/2 + (F(t)-F(-t))(η-2t²)/(4t), then lower-bound this by t/2 - |2t²-η|/(4t), and then write '≥ t/2 - η/(4t) ≥ η/(4t) ≥ √η/4'. The step t/2 - η/(4t) ≥ η/(4t) is equivalent to t² ≥ η, which contradicts the stated choice t ≤ √η. For the admissible value t=(2m+1)η=√η/2, the left-hand side equals -√η/4, which is not ≥ √η/4. The claimed bound E ≥ √η/4 (and hence the lemma's stated √η/16) is therefore not established. Since Lemma 13 invokes Lemma 12 directly (with budget dη), and Lemma 14 invokes Lemma 13, the lower bound in Theorem 4 and Theorem 1 is currently unsupported. The defect seems repairable—for instance, by choosing the grid so that t is sufficiently close to √η, the same argument can yield a positive constant times √η—but as written the proof of the lower bound fails.
minor comments (6)
  1. [Section 5.1.1, Lemma 9] In the bound on P_J[T(J)≠T'(J)], the inequality '≤ E_J |J∩I| ≤ kη' ignores the factor n/n1 ≈ 2. Specifically, |I|≤ηn and n1=⌊n/2⌋ give E|J∩I| = k|I|/n1 ≤ 2kη. The displayed constant 4 in λ_n ≤ 4√(ηd log(e/(ηd))) should be adjusted; the overall eΘ rate is unaffected.
  2. [Section 5.1.2, Lemma 14] The statement of Lemma 14 contains 'excessH,D,η(A,n) ≥ inf_h L_{D_u}(h) + √(dη)/(16√2) - e^{-ηn/6}', but the proof directly establishes the lower bound without the additive 'inf_h L_{D_u}(h)' term. This is a typographical error in the statement, not in the proof itself.
  3. [Section 5.1.2, Lemma 12] In the definition of the poisoning scheme, 'ξ_0(x)=ξ_1(x)=x' should presumably read 'ξ_{-1}(x)=ξ_1(x)=x' for x not in the grid, since the scheme components are ξ_{-1} and ξ_1; this is a minor notation slip.
  4. [Section 1.1, Theorem 1 discussion] The text states that the upper bound is achieved by a 'proper' randomized learner, but the learner used in the proof (learner B in Proposition 6) can output hypotheses outside H. The first-stage learner A is proper but does not satisfy the stability bound as proved. The wording should be corrected to avoid claiming properness, or the construction should be adjusted to produce a proper learner.
  5. [Section 5.2, Theorem 3 proof] The expression 'exp(log(-64√(dη)))' should read 'exp(-log(64√(dη)))'; in addition, the displayed lower bound uses √(dη)/16 while the preceding line has √(dη)/(16√2), which should be reconciled.
  6. [Throughout] There are several minor typographical issues, including 'tistribution' in the proof of Lemma 12, 'exits' in Theorem 4, and occasional missing articles. These do not affect the mathematics.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found; the central lower-bound defect is a correctness gap, not a circular derivation.

full rationale

The paper's derivation is essentially self-contained and does not reduce its central claims to its own inputs. The upper bound is proved directly via an exponential-mechanism learner (Proposition 6) and a subsampling/covering argument (Lemma 9); the cited cover lemma from Bassily et al. is an independent published structural bound on VC classes, and although one of the present authors is a co-author there, it is used as a standard external tool rather than as a premise that assumes the target result. The lower bound constructs a fixed finite-support distribution over biases and a shifting poisoning scheme before seeing the learner, so no parameter is fitted to the learner and the claimed lower bound is not a renamed version of an input. The only serious defect is in Lemma 12's final display: the paper claims t/2 - eta/(4t) >= eta/(4t), which would require t^2 >= eta, contradicting the choice t=(2m+1)eta <= sqrt(eta). This makes the proof of the one-dimensional lower bound invalid as written and therefore puts the direct-sum extension in question, but that is a mathematical correctness gap, not circularity: Lemma 12 is supposed to establish the lower bound rather than presuppose it, and no equation in the paper defines the target result in terms of itself. Accordingly, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The proof relies on standard learning-theory results and concentration inequalities. There are no data-fitted free parameters: the algorithm's temperature and subsample size are explicit functions of eta and d chosen for the analysis. No new particles, forces, or mediators are introduced. The only non-elementary black box is the Bassily-Moran-Alon cover lemma and the Blanc-Valiant adversarial equivalence, both external results with published proofs.

assumptions (6)
  • standard math Sauer-Shelah lemma bounding the number of distinct labelings induced by a VC class on a finite set.
    Used in Lemma 4 and Lemma 9 to bound |H_T| as (e k / d)^d. This is a classical result in learning theory, independent of the paper's claims.
  • standard math Hoeffding's and Chernoff's concentration inequalities.
    Used in Claim 2 of Proposition 6 and in Proposition 11 to control uniform convergence and the failure probability under sample corruption. Standard tools, not assumptions tailored to the target result.
  • standard math Cover lemma of Bassily, Moran, and Alon (2019), Lemma 3.3, bounding the expected epsilon-cover size of a VC class from a random sample.
    Used in Lemma 8 to show that a subsample of size O(d/epsilon log(d/epsilon)) is a good cover. Although one co-author overlaps with the present paper, this is a published, peer-reviewed structural result that does not encode the target theorem.
  • standard math Blanc and Valiant (2024) equivalence between adaptive and oblivious statistical adversaries, as formalized in Proposition 11.
    Used to convert the oblivious-adversary lower bound into the original adaptive-poisoning lower bound. The equivalence is cited as an external theorem and is not the paper's main contribution.
  • domain assumption Instance-targeted poisoning model assumptions: the adversary observes the clean sample and target point, corrupts at most an eta fraction, and the underlying distribution is fixed in advance.
    This is the model under study, inherited from Gao et al. and Hanneke et al. It is a domain assumption that defines the problem rather than a hidden premise.
  • domain assumption In the lower bound, it suffices to consider distributions with uniform marginal over a shattered set and independent label biases; this is without loss of generality for a VC class of dimension d.
    Introduced in Section 5.1.2 before Lemma 13 and 14. It is standard for VC-dimension lower bounds because a shattered set allows arbitrary independent label behavior.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness." pith.science (2026). https://pith.science/paper/ZILQOVSN

@misc{pith2026250603075,
  author       = {Pith},
  title        = {Pith review of: Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZILQOVSN}},
  note         = {Machine review of arXiv:2506.03075}
}
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 arXiv:2210.02713. In this work, we resolve the corresponding question in the agnostic setting. We show that the optimal excess error is $\tilde{\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.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

14 extracted references · 9 canonical work pages

  1. [10]

    Steve Hanneke, Amin Karbasi, Mohammad Mahmoody, Idan Mehalel, and Shay Moran

    URLhttp://papers.nips.cc/paper_files/paper/2023/ hash/1967f962c7c2083618236d80eeb9d1ac-Abstract-Conference.html. Steve Hanneke, Amin Karbasi, Mohammad Mahmoody, Idan Mehalel, and Shay Moran. On optimal learning under targeted data poisoning,

    work page 2023

  2. [11]

    Matthew Jagielski, Giorgio Severi, Niklas Pousette Harger, and Alina Oprea

    URLhttps://arxiv.org/abs/2210.02713. Matthew Jagielski, Giorgio Severi, Niklas Pousette Harger, and Alina Oprea. Subpopulation data poisoning attacks. InProceedings of the 2021 ACM SIGSAC Conference on Computer and Com- munications Security, pages 3104–3122,

    arXiv 2021

  3. [12]

    Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks

    Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Intrinsic certified robustness of bagging against data poisoning attacks.arXiv preprint arXiv:2008.04495,

    work page Pith review arXiv 2008

  4. [1985]

    Rab: Provable robustness against backdoor attacks.arXiv preprint arXiv:2003.08904,

    Maurice Weber, Xiaojun Xu, Bojan Karlas, Ce Zhang, and Bo Li. Rab: Provable robustness against backdoor attacks.arXiv preprint arXiv:2003.08904,

    arXiv 2003

  5. [2002]

    Adversarial attacks and defences: A survey.arXiv preprint arXiv:1810.00069,

    Anirban Chakraborty, Manaar Alam, Vishal Dey, Anupam Chattopadhyay, and Debdeep Mukhopad- hyay. Adversarial attacks and defences: A survey.arXiv preprint arXiv:1810.00069,

    arXiv

  6. [2006]

    ISBN 1595932720

    Association for Computing Machinery. ISBN 1595932720. doi: 10.1145/1128817.1128824. URLhttps://doi.org/ 10.1145/1128817.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´ e-Buc, Emily B. Fox, and Roman Garnett, editors,Advances i...

    work page arXiv

  7. [2009]

    Agnostic estimation of mean and covariance

    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,

    work page 2016

  8. [2014]

    Robustly-reliable learn- ers under poisoning attacks

    Maria-Florina Balcan, Avrim Blum, Steve Hanneke, and Dravyansh Sharma. Robustly-reliable learn- ers under poisoning attacks. In Po-Ling Loh and Maxim Raginsky, editors,Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 ofProceedings of Machine Learning Research, pages 4498–4534. PMLR,

    work page 2022

Show all 14 references
  1. [2018]

    Robust estimators in high dimensions without the computational intractability

    Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high dimensions without the computational intractability. InFoundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 655–664. IEEE,

    2016

  2. [2019]

    Guy Blanc and Gregory Valiant

    URLhttps://proceedings.neurips.cc/paper/ 2019/hash/9a6a1aaafe73c572b7374828b03a1881-Abstract.html. Guy Blanc and Gregory Valiant. Adaptive and oblivious statistical adversaries are equivalent,

    2019

  3. [2021]

    URLhttps://doi.org/10

    doi: 10.1145/3406325.3451087. URLhttps://doi.org/10. 1145/3406325.3451087. 24 Nader H Bshouty, Nadav Eiron, and Eyal Kushilevitz. Pac learning with nasty noise.Theoretical Computer Science, 288(2):255–275,

  4. [2022]

    Learning and certification under instance-targeted poisoning, 2021a

    Ji Gao, Amin Karbasi, and Mohammad Mahmoody. Learning and certification under instance-targeted poisoning, 2021a. URLhttps://arxiv.org/abs/2105.08709. Ji Gao, Amin Karbasi, and Mohammad Mahmoody. Learning and certification under instance-targeted poisoning. InUncertainty in Ar...

    2023 arXiv

  5. [2023]

    Marco Barreno, Blaine Nelson, Russell Sears, Anthony D

    URLhttps://proceedings.neurips.cc/paper_files/ paper/2023/file/96189e90e599ccc43f00434ff3ed0312-Paper-Conference.pdf. Marco Barreno, Blaine Nelson, Russell Sears, Anthony D. Joseph, and J. D. Tygar. Can machine learning be secure? InProceedings of the 2006 ACM Symposium on Inf...

    2023

  6. [2024]

    Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, and Amir Yehudayoff

    URLhttps://arxiv.org/abs/2410.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 Computin...

    arXiv

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.