mlsanityData to 7 Oct 2026

Adversarially Robust Learning with Unknown Perturbation Sets

arXiv 2102.02145 ↗First posted 3 Feb 2021cs.LG stat.MLcited by 24

Not on the map. Why?

Abstract (arXiv)

We study the problem of learning predictors that are robust to adversarial examples with respect to an unknown perturbation set, relying instead on interaction with an adversarial attacker or access to attack oracles, examining different models for such interactions. We obtain upper bounds on the sample complexity and upper and lower bounds on the number of required interactions, or number of successful attacks, in different interaction models, in terms of the VC and Littlestone dimensions of the hypothesis class of predictors, and without any assumptions on the perturbation set.

Key facts. Cited by 24 papers in the map (data through 7 Oct 2026). Builds on 22 of its 45 references that are in the map. First posted on arXiv 3 Feb 2021.

Builds on

22 of 45 references.

References · 22

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  3. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
  4. 2018Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examplescited by 1,259
  5. 2017Provable defenses against adversarial examples via the convex outer adversarial polytopecited by 564
  6. 2018Certified Robustness to Adversarial Examples with Differential Privacycited by 462
  7. 2019Provably Robust Deep Learning via Adversarially Trained Smoothed Classifierscited by 328
  8. 2018Adversarially Robust Generalization Requires More Datacited by 318
  9. 2018Certified Defenses against Adversarial Examplescited by 305
  10. 2019Adversarial Training and Robustness for Multiple Perturbationscited by 182
  11. 2018Semidefinite relaxations for certifying robustness to adversarial examplescited by 178
  12. 2020Perceptual Adversarial Robustness: Defense Against Unseen Threat Modelscited by 137
10 more
  1. 2019Adversarial Robustness Against the Union of Multiple Perturbation Modelscited by 88
  2. 2019VC Classes are Adversarially Robustly Learnable, but Only Improperlycited by 83
  3. 2018Private PAC learning implies finite Littlestone dimensioncited by 73
  4. 2020Proper Learning, Helly Number, and an Optimal SVM Boundcited by 52
  5. 2015Sample compression schemes for VC classescited by 46
  6. 2020Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examplescited by 44
  7. 2020Reducing Adversarially Robust Learning to Non-Robust PAC Learningcited by 28
  8. 2020Efficiently Learning Adversarially Robust Halfspaces with Noisecited by 22
  9. 2021Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Gamescited by 18
  10. 2020Black-box Certification and Learning under Adversarial Perturbationscited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 7; 2023: 4; 2024: 4; 2025: 3; 2026: 4.

24 papers.

Sort:

By area:

  1. 2023Cross-Entropy Loss Functions: Theoretical Analysis and Applicationscited by 206
  2. 2021Realizable Learning is All You Needcited by 25
  3. 2023Optimal Learners for Realizable Regression: PAC Learning and Online Learningcited by 23
  4. 2022Learning Losses for Strategic Classificationcited by 22
  5. 2022Robustly-reliable learners under poisoning attackscited by 19
  6. 2022A Characterization of Semi-Supervised Adversarially-Robust PAC Learnabilitycited by 13
  7. 2024Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorizationcited by 12
  8. 2023Adversarial Resilience in Sequential Prediction via Abstentioncited by 11
  9. 2022Adversarially Robust Learning with Tolerancecited by 9
  10. 2023Reliable learning in challenging environmentscited by 9
  11. 2022Formulating Robustness Against Unforeseen Attackscited by 8
  12. 2022Adversarially Robust PAC Learnability of Real-Valued Functionscited by 8
12 more
  1. 2024On the Computability of Robust PAC Learningcited by 6
  2. 2025PAC Learning with Improvementscited by 6
  3. 2024Sample Compression Scheme Reductionscited by 2
  4. 2025Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarkscited by 2
  5. 2022When are Local Queries Useful for Robust Learning?cited by 1
  6. 2024Position: Towards Resilience Against Adversarial Examplescited by 1
  7. 2025Defending Against Frequency-Based Attacks with Diffusion Modelscited by 1
  8. 2026Distribution-Free Sequential Prediction with Abstentionscited by 1
  9. 2026Bagging Robustly Learns VC Classes with Linear Sample Complexitycited by 1
  10. 2021Provable Adversarial Robustness in the Quantum Modelcited by 0
  11. 2026Robust Online Learningcited by 0
  12. 2026Adversarially Robust PAC Learning with Optimal VC Ratescited by 0