# VC Classes are Adversarially Robustly Learnable, but Only Improperly

arXiv: https://arxiv.org/abs/1902.04217 · HTML: https://mlsanity.com/paper/1902.04217/

## Key facts

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

## Built on by (most cited first, 30 of 83)

- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Robust Learning Meets Generative Models: Can Proxy Distributions Improve Adversarial Robustness?](https://mlsanity.com/paper/2104.09425/) (2021)
- [Probable Domain Generalization via Quantile Risk Minimization](https://mlsanity.com/paper/2207.09944/) (2022)
- [Calibration and Consistency of Adversarial Surrogate Losses](https://mlsanity.com/paper/2104.09658/) (2021)
- [Adversarial Robustness with Semi-Infinite Constrained Learning](https://mlsanity.com/paper/2110.15767/) (2021)
- [Probabilistically Robust Learning: Balancing Average- and Worst-case Performance](https://mlsanity.com/paper/2202.01136/) (2022)
- [Stability Analysis and Generalization Bounds of Adversarial Training](https://mlsanity.com/paper/2210.00960/) (2022)
- [WAT: Improve the Worst-class Robustness in Adversarial Training](https://mlsanity.com/paper/2302.04025/) (2023)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [On the Existence of the Adversarial Bayes Classifier (Extended Version)](https://mlsanity.com/paper/2112.01694/) (2021)
- [Adversarially Robust Learning with Unknown Perturbation Sets](https://mlsanity.com/paper/2102.02145/) (2021)
- [Excess Capacity and Backdoor Poisoning](https://mlsanity.com/paper/2109.00685/) (2021)
- [Strategic Classification under Unknown Personalized Manipulation](https://mlsanity.com/paper/2305.16501/) (2023)
- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [Learning Losses for Strategic Classification](https://mlsanity.com/paper/2203.13421/) (2022)
- [Robustly-reliable learners under poisoning attacks](https://mlsanity.com/paper/2203.04160/) (2022)
- [Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games](https://mlsanity.com/paper/2102.01646/) (2021)
- [Adversarial Rademacher Complexity of Deep Neural Networks](https://mlsanity.com/paper/2211.14966/) (2022)
- [Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization](https://mlsanity.com/paper/2209.07369/) (2022)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [Learnability Gaps of Strategic Classification](https://mlsanity.com/paper/2402.19303/) (2024)
- [Robust learning under clean-label attack](https://mlsanity.com/paper/2103.00671/) (2021)
- [FedImpro: Measuring and Improving Client Update in Federated Learning](https://mlsanity.com/paper/2402.07011/) (2024)
- [Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization](https://mlsanity.com/paper/2402.09327/) (2024)
- [A PAC-Bayes Analysis of Adversarial Robustness](https://mlsanity.com/paper/2102.11069/) (2021)
- [Learning and Certification under Instance-targeted Poisoning](https://mlsanity.com/paper/2105.08709/) (2021)
- [A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability](https://mlsanity.com/paper/2202.05420/) (2022)
- [Multiclass Online Learnability under Bandit Feedback](https://mlsanity.com/paper/2308.04620/) (2023)
- [Adversarial Resilience in Sequential Prediction via Abstention](https://mlsanity.com/paper/2306.13119/) (2023)
- [Understanding Generalization in Adversarial Training via the Bias-Variance Decomposition](https://mlsanity.com/paper/2103.09947/) (2021)

## 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.