Research map / Learning theory and algorithms / Sample complexity
Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that agnostic learning under instance-targeted poisoning achieves optimal excess error Θ̃(√(dη)) using randomized (exponential-mechanism-style) learners, resolving an open problem from Hanneke et al.
Problem
Determining the optimal excess error for agnostic PAC learning under instance-targeted data poisoning with poisoning budget η, where deterministic learners are known to fail.
Approach
A proper randomized learner that samples hypotheses from a finite epsilon-cover with probability proportional to exp(-t·empirical loss) (exponential mechanism / multiplicative weights), analyzed via prediction stability and group privacy; the lower bound uses a randomized-bias d-coin construction on a single fixed distribution, plus a generic private-to-public randomness transformation.
Key results
- Upper bound: a randomized proper learner achieves excess error Õ(√(dη)) for n ≥ 1/η (quantitative bound 36√(ηd) log(e/(ηd)))
- Lower bound: for any learner there is a distribution and adversary forcing excess error Ω̃(min{√(dη),1}), and Ω(√(dη)) infinitely often on a single fixed distribution
- Upper bound remains valid even when the learner's random bits are visible to the adversary (public randomness), via a private-to-public transformation
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a randomized learner instead of a deterministic learner | Agnostic learning under instance-targeted poisoning · Agnostic instance-targeted poisoning | excess error | Helped |
| Use subsampling, a finite cover, and exponential sampling | Proposed randomized learner · Agnostic instance-targeted poisoning (n ≥ 1/η) | excess error: 36\sqrt{\eta d}\log \frac{e}{\eta d} | Helped |
| Give the learner public access to its random seed, using the constructed public-randomness learner | Private-randomness learner · Agnostic instance-targeted poisoning | excess error | No clear effect |
Surprising findings
- Upper bound holds even when the adversary sees the learner's random seed
- Lower bound holds for a single fixed distribution infinitely often, stronger than standard PAC-style per-sample-size bounds
Limitations
- Results are information-theoretic; the learner is not computationally efficient in general
- Upper bound holds up to logarithmic factors
- Analysis restricted to binary classification with VC classes
Experimental setup
Metrics: excess error
Baselines: deterministic learners (Hanneke et al. 2022)
Builds on: Hanneke et al. 2022 instance-targeted poisoning exponential mechanism multiplicative weights group privacy
Closest papers by meaning
- On Optimal Learning Under Targeted Data Poisoning (NeurIPS 2022 · similarity 0.94)
- What Distributions are Robust to Indiscriminate Poisoning Attacks for Linear Learners? (NeurIPS 2023 · similarity 0.89)
- Poisoning Attacks on LLMs Require a Near-constant Number of Poison Samples (NeurIPS 2026 · similarity 0.85)
- On Agnostic PAC Learning in the Small Error Regime (NeurIPS 2025 · similarity 0.85)
- Generalization Bound and New Algorithm for Clean-Label Backdoor Attack (ICML 2024 · similarity 0.84)
- Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.