mlsanityData to 14 Oct 2026

On Proper Learnability between Average- and Worst-case Robustness

arXiv 2211.05656 ↗First posted 10 Nov 2022cs.LG stat.MLcited by 5

Not on the map. Why?

Abstract (arXiv)

Recently, Montasser et al. [2019] showed that finite VC dimension is not sufficient for proper adversarially robust PAC learning. In light of this hardness, there is a growing effort to study what type of relaxations to the adversarially robust PAC learning setup can enable proper learnability. In this work, we initiate the study of proper learning under relaxations of the worst-case robust loss. We give a family of robust loss relaxations under which VC classes are properly PAC learnable with sample complexity close to what one would require in the standard PAC learning setup. On the other hand, we show that for an existing and natural relaxation of the worst-case robust loss, finite VC dimension is not sufficient for proper learning. Lastly, we give new generalization guarantees for the adversarially robust empirical risk minimizer.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 22 of its 38 references that are in the map. First posted on arXiv 10 Nov 2022.

Builds on

22 of 38 references.

References · 22

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
  2. 2019Theoretically Principled Trade-off between Robustness and Accuracycited by 1,517
  3. 2018Robustness May Be at Odds with Accuracycited by 880
  4. 2017Provable defenses against adversarial examples via the convex outer adversarial polytopecited by 567
  5. 2018Adversarially Robust Generalization Requires More Datacited by 318
  6. 2018Certified Defenses against Adversarial Examplescited by 306
  7. 2018Is Robustness the Cost of Accuracy? -- A Comprehensive Study on the Robustness of 18 Deep Image Classification Modelscited by 135
  8. 2018Rademacher Complexity for Adversarially Robust Generalizationcited by 132
  9. 2019Adversarial Training Can Hurt Generalizationcited by 132
  10. 2020Tilted Empirical Risk Minimizationcited by 106
  11. 2019VC Classes are Adversarially Robustly Learnable, but Only Improperlycited by 83
  12. 2019Functional Adversarial Attackscited by 82
10 more
  1. 2021On Tilted Losses in Machine Learning: Theory and Applicationscited by 43
  2. 2020Provable tradeoffs in adversarially robust classificationcited by 40
  3. 2022Probabilistically Robust Learning: Balancing Average- and Worst-case Performancecited by 37
  4. 2020Calibrated Surrogate Losses for Adversarially Robust Classificationcited by 36
  5. 2018Improved Generalization Bounds for Adversarially Robust Learningcited by 22
  6. 2020Black-box Certification and Learning under Adversarial Perturbationscited by 13
  7. 2022A Characterization of Semi-Supervised Adversarially-Robust PAC Learnabilitycited by 13
  8. 2022Adversarially Robust Learning with Tolerancecited by 9
  9. 2022Adversarially Robust PAC Learnability of Real-Valued Functionscited by 8
  10. 2022Robust Empirical Risk Minimization with Tolerancecited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 2; 2025: 1; 2026: 1.

5 papers.

  1. 2024On the Computability of Robust PAC Learningcited by 6
  2. 2025PAC Learning with Improvementscited by 6
  3. 2023It begins with a boundary: A geometric view on probabilistically robust learningcited by 3
  4. 2024Uniform Convergence of Adversarially Robust Classifierscited by 1
  5. 2026Adversarially Robust PAC Learning with Optimal VC Ratescited by 0