mlsanityData to 7 Oct 2026

VC Classes are Adversarially Robustly Learnable, but Only Improperly

arXiv 1902.04217 ↗First posted 12 Feb 2019cs.LG stat.MLcited by 83

Not on the map. Why?

Abstract (arXiv)

We study the question of learning an adversarially robust predictor. We show that any hypothesis class H with finite VC dimension is robustly PAC learnable with an improper learning rule. The requirement of being improper is necessary as we exhibit examples of hypothesis classes H with finite VC dimension that are not robustly PAC learnable with any proper learning rule.

Key facts. Cited by 83 papers in the map (data through 7 Oct 2026). First posted on arXiv 12 Feb 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 19; 2022: 20; 2023: 17; 2024: 13; 2025: 7; 2026: 7.

83 papers.

Sort:

By area:

  1. 2023Cross-Entropy Loss Functions: Theoretical Analysis and Applicationscited by 206
  2. 2021Robust Learning Meets Generative Models: Can Proxy Distributions Improve Adversarial Robustness?cited by 113
  3. 2022Probable Domain Generalization via Quantile Risk Minimizationcited by 66
  4. 2021Calibration and Consistency of Adversarial Surrogate Lossescited by 47
  5. 2021Adversarial Robustness with Semi-Infinite Constrained Learningcited by 39
  6. 2022Probabilistically Robust Learning: Balancing Average- and Worst-case Performancecited by 36
  7. 2022Stability Analysis and Generalization Bounds of Adversarial Trainingcited by 30
  8. 2023WAT: Improve the Worst-class Robustness in Adversarial Trainingcited by 27
  9. 2021Realizable Learning is All You Needcited by 25
  10. 2021On the Existence of the Adversarial Bayes Classifier (Extended Version)cited by 25
  11. 2021Adversarially Robust Learning with Unknown Perturbation Setscited by 24
  12. 2021Excess Capacity and Backdoor Poisoningcited by 24
38 more
  1. 2023Strategic Classification under Unknown Personalized Manipulationcited by 23
  2. 2023Optimal Learners for Realizable Regression: PAC Learning and Online Learningcited by 23
  3. 2022Learning Losses for Strategic Classificationcited by 22
  4. 2022Robustly-reliable learners under poisoning attackscited by 19
  5. 2021Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Gamescited by 18
  6. 2022Adversarial Rademacher Complexity of Deep Neural Networkscited by 18
  7. 2022Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterizationcited by 17
  8. 2021Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Gamescited by 16
  9. 2024Learnability Gaps of Strategic Classificationcited by 16
  10. 2021Robust learning under clean-label attackcited by 15
  11. 2024FedImpro: Measuring and Improving Client Update in Federated Learningcited by 15
  12. 2021A PAC-Bayes Analysis of Adversarial Robustnesscited by 13
  13. 2021Learning and Certification under Instance-targeted Poisoningcited by 13
  14. 2022A Characterization of Semi-Supervised Adversarially-Robust PAC Learnabilitycited by 13
  15. 2023Multiclass Online Learnability under Bandit Feedbackcited by 12
  16. 2024Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorizationcited by 12
  17. 2023Adversarial Resilience in Sequential Prediction via Abstentioncited by 11
  18. 2021Understanding Generalization in Adversarial Training via the Bias-Variance Decompositioncited by 10
  19. 2021Transductive Robust Learning Guaranteescited by 10
  20. 2022A Law of Robustness beyond Isoperimetrycited by 9
  21. 2022Adversarially Robust Learning with Tolerancecited by 9
  22. 2023Reliable learning in challenging environmentscited by 9
  23. 2022Formulating Robustness Against Unforeseen Attackscited by 8
  24. 2022Adversarially Robust PAC Learnability of Real-Valued Functionscited by 8
  25. 2021Domain Invariant Adversarial Learningcited by 7
  26. 2022Robust Empirical Risk Minimization with Tolerancecited by 6
  27. 2023Generalization Bounds for Adversarial Contrastive Learningcited by 6
  28. 2023Characterizing the Optimal 0-1 Loss for Multi-class Classification with a Test-time Attackercited by 6
  29. 2023Sup-Norm Convergence of Deep Neural Network Estimator for Nonparametric Regression by Adversarial Trainingcited by 6
  30. 2024On the Computability of Robust PAC Learningcited by 6
  31. 2025PAC Learning with Improvementscited by 6
  32. 2022On Proper Learnability between Average- and Worst-case Robustnesscited by 5
  33. 2024Coverage-Guaranteed Prediction Sets for Out-of-Distribution Datacited by 5
  34. 2024Stability and Generalization in Free Adversarial Trainingcited by 5
  35. 2025Should Decision-Makers Reveal Classifiers in Online Strategic Classification?cited by 5
  36. 2021Regional Adversarial Training for Better Robust Generalizationcited by 4
  37. 2022Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attackscited by 4
  38. 2024Transformation-Invariant Learning and Theoretical Guarantees for OOD Generalizationcited by 4

50 most cited of 83 All 83 (JSON)