# Reducing Adversarially Robust Learning to Non-Robust PAC Learning

arXiv: https://arxiv.org/abs/2010.12039 · HTML: https://mlsanity.com/paper/2010.12039/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Oct 2020.

## Built on by (most cited first, 28 of 28)

- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Calibration and Consistency of Adversarial Surrogate Losses](https://mlsanity.com/paper/2104.09658/) (2021)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [Adversarially Robust Learning with Unknown Perturbation Sets](https://mlsanity.com/paper/2102.02145/) (2021)
- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [Robustly-reliable learners under poisoning attacks](https://mlsanity.com/paper/2203.04160/) (2022)
- [Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization](https://mlsanity.com/paper/2209.07369/) (2022)
- [Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization](https://mlsanity.com/paper/2402.09327/) (2024)
- [A PAC-Bayes Analysis of Adversarial Robustness](https://mlsanity.com/paper/2102.11069/) (2021)
- [A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability](https://mlsanity.com/paper/2202.05420/) (2022)
- [Adversarial Resilience in Sequential Prediction via Abstention](https://mlsanity.com/paper/2306.13119/) (2023)
- [Reliable learning in challenging environments](https://mlsanity.com/paper/2304.03370/) (2023)
- [Adversarially Robust Learning with Tolerance](https://mlsanity.com/paper/2203.00849/) (2022)
- [Adversarially Robust PAC Learnability of Real-Valued Functions](https://mlsanity.com/paper/2206.12977/) (2022)
- [A Multiclass Boosting Framework for Achieving Fast and Provable Adversarial Robustness](https://mlsanity.com/paper/2103.01276/) (2021)
- [PAC Learning with Improvements](https://mlsanity.com/paper/2503.03184/) (2025)
- [Adversarial for Good? How the Adversarial ML Community's Values Impede Socially Beneficial Uses of Attacks](https://mlsanity.com/paper/2107.10302/) (2021)
- [Boosting Barely Robust Learners: A New Perspective on Adversarial Robustness](https://mlsanity.com/paper/2202.05920/) (2022)
- [Modeling Non-Cooperative Dialogue: Theoretical and Empirical Insights](https://mlsanity.com/paper/2207.07255/) (2022)
- [Agnostic Multi-Robust Learning Using ERM](https://mlsanity.com/paper/2303.08944/) (2023)
- [Sample Compression Scheme Reductions](https://mlsanity.com/paper/2410.13012/) (2024)
- [When are Local Queries Useful for Robust Learning?](https://mlsanity.com/paper/2210.06089/) (2022)
- [Distribution-Free Sequential Prediction with Abstentions](https://mlsanity.com/paper/2602.17918/) (2026)
- [Bagging Robustly Learns VC Classes with Linear Sample Complexity](https://mlsanity.com/paper/2608.13514/) (2026)
- [mathscrH-Consistency Estimation Error of Surrogate Loss Minimizers](https://mlsanity.com/paper/2205.08017/) (2022)
- [Adaptive adversarial training method for improving multi-scale GAN based on generalization bound theory](https://mlsanity.com/paper/2211.16791/) (2022)
- [A Model for Combinatorial Dictionary Learning and Inference](https://mlsanity.com/paper/2407.18436/) (2024)
- [Adversarially Robust PAC Learning with Optimal VC Rates](https://mlsanity.com/paper/2609.24260/) (2026)

## Abstract (arXiv)

We study the problem of reducing adversarially robust learning to standard PAC learning, i.e. the complexity of learning adversarially robust predictors using access to only a black-box non-robust learner. We give a reduction that can robustly learn any hypothesis class C using any non-robust learner A for C. The number of calls to A depends logarithmically on the number of allowed adversarial perturbations per example, and we give a lower bound showing this is unavoidable.