mlsanityData to 14 Oct 2026

Reducing Adversarially Robust Learning to Non-Robust PAC Learning

arXiv 2010.12039 ↗First posted 22 Oct 2020cs.LGcited by 28

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 6; 2022: 10; 2023: 5; 2024: 3; 2025: 1; 2026: 3.

28 papers.

Sort:

By area:

  1. 2023Cross-Entropy Loss Functions: Theoretical Analysis and Applicationscited by 210
  2. 2021Calibration and Consistency of Adversarial Surrogate Lossescited by 47
  3. 2021Realizable Learning is All You Needcited by 25
  4. 2021Adversarially Robust Learning with Unknown Perturbation Setscited by 24
  5. 2023Optimal Learners for Realizable Regression: PAC Learning and Online Learningcited by 23
  6. 2022Robustly-reliable learners under poisoning attackscited by 20
  7. 2022Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterizationcited by 17
  8. 2024Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorizationcited by 14
  9. 2021A PAC-Bayes Analysis of Adversarial Robustnesscited by 13
  10. 2022A Characterization of Semi-Supervised Adversarially-Robust PAC Learnabilitycited by 13
  11. 2023Adversarial Resilience in Sequential Prediction via Abstentioncited by 11
  12. 2023Reliable learning in challenging environmentscited by 10
16 more
  1. 2022Adversarially Robust Learning with Tolerancecited by 9
  2. 2022Adversarially Robust PAC Learnability of Real-Valued Functionscited by 8
  3. 2021A Multiclass Boosting Framework for Achieving Fast and Provable Adversarial Robustnesscited by 6
  4. 2025PAC Learning with Improvementscited by 6
  5. 2021Adversarial for Good? How the Adversarial ML Community's Values Impede Socially Beneficial Uses of Attackscited by 5
  6. 2022Boosting Barely Robust Learners: A New Perspective on Adversarial Robustnesscited by 3
  7. 2022Modeling Non-Cooperative Dialogue: Theoretical and Empirical Insightscited by 2
  8. 2023Agnostic Multi-Robust Learning Using ERMcited by 2
  9. 2024Sample Compression Scheme Reductionscited by 2
  10. 2022When are Local Queries Useful for Robust Learning?cited by 1
  11. 2026Distribution-Free Sequential Prediction with Abstentionscited by 1
  12. 2026Bagging Robustly Learns VC Classes with Linear Sample Complexitycited by 1
  13. 2022mathscrH-Consistency Estimation Error of Surrogate Loss Minimizerscited by 0
  14. 2022Adaptive adversarial training method for improving multi-scale GAN based on generalization bound theorycited by 0
  15. 2024A Model for Combinatorial Dictionary Learning and Inferencecited by 0
  16. 2026Adversarially Robust PAC Learning with Optimal VC Ratescited by 0