mlsanityData to 7 Oct 2026

Adversarial Robustness: What fools you makes you stronger

arXiv 2102.05475 ↗First posted 10 Feb 2021cs.LG cs.CRcited by 1

Not on the map. Why?

Abstract (arXiv)

We prove an exponential separation for the sample complexity between the standard PAC-learning model and a version of the Equivalence-Query-learning model. We then show that this separation has interesting implications for adversarial robustness. We explore a vision of designing an adaptive defense that in the presence of an attacker computes a model that is provably robust. In particular, we show how to realize this vision in a simplified setting. In order to do so, we introduce a notion of a strong adversary: he is not limited by the type of perturbations he can apply but when presented with a classifier can repetitively generate different adversarial examples. We explain why this notion is interesting to study and use it to prove the following. There exists an efficient adversarial-learning-like scheme such that for every strong adversary A it outputs a classifier that (a) cannot be strongly attacked by A, or (b) has error at most ε. In both cases our scheme uses exponentially (in ε) fewer samples than what the PAC bound requires.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 23 of its 33 references that are in the map. First posted on arXiv 10 Feb 2021.

Builds on

23 of 33 references.

References · 23

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  3. 2013Intriguing properties of neural networkscited by 5,114
  4. 2016Practical Black-Box Attacks against Machine Learningcited by 893
  5. 2018Robustness May Be at Odds with Accuracycited by 873
  6. 2017Ensemble Adversarial Training: Attacks and Defensescited by 833
  7. 2014Deep Neural Networks are Easily Fooled: High Confidence Predictions for Unrecognizable Imagescited by 774
  8. 2017Evasion Attacks against Machine Learning at Test Timecited by 686
  9. 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 656
  10. 2017Provable defenses against adversarial examples via the convex outer adversarial polytopecited by 564
  11. 2016Delving into Transferable Adversarial Examples and Black-box Attackscited by 530
  12. 2018Certified Defenses against Adversarial Examplescited by 305
11 more
  1. 2018Generating Adversarial Examples with Adversarial Networkscited by 256
  2. 2019Adversarial Training and Robustness for Multiple Perturbationscited by 182
  3. 2017Exploring the Landscape of Spatial Robustnesscited by 81
  4. 2018Adversarial examples from computational constraintscited by 79
  5. 2015The Optimal Sample Complexity of PAC Learningcited by 72
  6. 2018Training for Faster Adversarial Robustness Verification via Inducing ReLU Stabilitycited by 67
  7. 2020Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examplescited by 44
  8. 2018Distributionally Adversarial Attackcited by 24
  9. 2019Adversarially Robust Learning Could Leverage Computational Hardnesscited by 13
  10. 2020Query complexity of adversarial attackscited by 5
  11. 2017Learning Universal Adversarial Perturbations with Generative Modelscited by 4

Built on by

Cited by year

Citing papers per year: 2021: 1.

1 paper.

  1. 2021Provable Adversarial Robustness in the Quantum Modelcited by 0