Research map / Adversarial robustness and security / Certified and empirical robustness
Reducing Adversarially Robust Learning to Non-Robust PAC Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Wrap a non-robust PAC learner with boosting and sparsified majority votes | PAC learner A for class C, with explicit perturbation sets · Realizable robust PAC learning | sample complexity dependence on |U|: sample complexity independent of |\mathcal{U}| | Helped |
| Use only a non-robust PAC learner, without stronger oracle assumptions | Robust learning with explicit perturbations · Realizable robust PAC learning | oracle calls as a function of |U|: O((\log{m}+\log|\mathcal{U}|)^2 + \log(1/\delta)); lower bound \Omega(\log |\mathcal{U}|) | Mixed |
| Use an online learner instead of only a non-robust PAC learner | Robust learning with a mistake oracle · Realizable robust PAC learning | dependence of sample and oracle calls on |U|: independent of |\mathcal{U}| | Helped |
| Use a mistake oracle without an online learner, even with an ERM | Robust learning with a mistake oracle · Robust empirical learning | mistake-oracle calls: T\geq \abs{\mathcal{U}} | Hurt |
Closest papers by meaning
- On Proper Learnability between Average- and Worst-case Robustness (NeurIPS 2023 · similarity 0.91)
- Boosting Barely Robust Learners: A New Perspective on Adversarial Robustness (NeurIPS 2022 · similarity 0.91)
- A Characterization of Semi-Supervised Adversarially Robust PAC Learnability (NeurIPS 2022 · similarity 0.91)
- Learning Better Certified Models from Empirically-Robust Teachers (NeurIPS 2026 · similarity 0.87)
- Adversarial Training Can Provably Improve Robustness: Theoretical Analysis of Feature Learning Process Under Structured Data (ICLR 2025 · similarity 0.86)
- Probably Approximately Global Robustness Certification (ICML 2025 · similarity 0.86)
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.