VC Classes are Adversarially Robustly Learnable, but Only Improperly

We study the question of learning an adversarially robust predictor. We show that any hypothesis class $\mathcal{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 $\mathcal{H}$ with finite VC dimension that are not robustly PAC learnable with any proper learning rule.

ML methods Security & robustness cs.LG stat.ML Adversarial Robustness in Machine Learning Machine Learning and Algorithms Domain Adaptation and Few-Shot Learning

Paper

Similar papers

VC Classes are Adversarially Robustly Learnable, but Only ImproperlyOmar Montasser, Steve Hanneke, Nathan Srebro2019 · Conference on Learning Theory In Library

Transductive Robust Learning GuaranteesOmar Montasser, Steve Hanneke, Nathan Srebro2021 · arXiv (Cornell University) · 12 citations In Library

On Proper Learnability between Average- and Worst-case RobustnessVInod Raman, Unique Subedi, Ambuj Tewari2022 · arXiv (Cornell University) · 4 citations In Library

Reducing Adversarially Robust Learning to Non-Robust PAC LearningOmar Montasser, Steve Hanneke, Nathan Srebro2020 · arXiv (Cornell University) · 33 citations In Library

Adversarially Robust PAC Learnability of Real-Valued FunctionsIdan Attias, Steve Hanneke2022 · arXiv (Cornell University) · 8 citations In Library

Open Problem: Are all VC classes learnable with computable learners?Sushant Agarwal, Nivasini Ananthakrishnan, Shai Ben-David et al.2021 In Library

On Robust Multiclass LearnabilityJingyuan Xu, Weiwei Liu2022 · Neural Information Processing Systems · 10 citations In Library

Simplifying Adversarially Robust PAC Learning with ToleranceHassan Ashtiani, Vinayak Pathak, Ruth Urner2025 · arXiv (Cornell University) In Library

PAC learnability versus VC dimension: a footnote to a basic result of statistical learningV. Pestov2011 · The 2011 International Joint Conference on Neural Networks · 13 citations In Library

On the Hardness of Robust ClassificationPascale Gourdeau, Varun Kanade, Marta Kwiatkowska et al.2019 · arXiv (Cornell University) In Library

Source of record

arXiv

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal