# On Proper Learnability between Average- and Worst-case Robustness

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

## 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 (most cited first, 22 of 22)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Theoretically Principled Trade-off between Robustness and Accuracy](https://mlsanity.com/paper/1901.08573/) (2019)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Adversarially Robust Generalization Requires More Data](https://mlsanity.com/paper/1804.11285/) (2018)
- [Certified Defenses against Adversarial Examples](https://mlsanity.com/paper/1801.09344/) (2018)
- [Is Robustness the Cost of Accuracy? -- A Comprehensive Study on the Robustness of 18 Deep Image Classification Models](https://mlsanity.com/paper/1808.01688/) (2018)
- [Rademacher Complexity for Adversarially Robust Generalization](https://mlsanity.com/paper/1810.11914/) (2018)
- [Adversarial Training Can Hurt Generalization](https://mlsanity.com/paper/1906.06032/) (2019)
- [Tilted Empirical Risk Minimization](https://mlsanity.com/paper/2007.01162/) (2020)
- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [Functional Adversarial Attacks](https://mlsanity.com/paper/1906.00001/) (2019)
- [On Tilted Losses in Machine Learning: Theory and Applications](https://mlsanity.com/paper/2109.06141/) (2021)
- [Provable tradeoffs in adversarially robust classification](https://mlsanity.com/paper/2006.05161/) (2020)
- [Probabilistically Robust Learning: Balancing Average- and Worst-case Performance](https://mlsanity.com/paper/2202.01136/) (2022)
- [Calibrated Surrogate Losses for Adversarially Robust Classification](https://mlsanity.com/paper/2005.13748/) (2020)
- [Improved Generalization Bounds for Adversarially Robust Learning](https://mlsanity.com/paper/1810.02180/) (2018)
- [Black-box Certification and Learning under Adversarial Perturbations](https://mlsanity.com/paper/2006.16520/) (2020)
- [A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability](https://mlsanity.com/paper/2202.05420/) (2022)
- [Adversarially Robust Learning with Tolerance](https://mlsanity.com/paper/2203.00849/) (2022)
- [Adversarially Robust PAC Learnability of Real-Valued Functions](https://mlsanity.com/paper/2206.12977/) (2022)
- [Robust Empirical Risk Minimization with Tolerance](https://mlsanity.com/paper/2210.00635/) (2022)

## Built on by (most cited first, 5 of 5)

- [On the Computability of Robust PAC Learning](https://mlsanity.com/paper/2406.10161/) (2024)
- [PAC Learning with Improvements](https://mlsanity.com/paper/2503.03184/) (2025)
- [It begins with a boundary: A geometric view on probabilistically robust learning](https://mlsanity.com/paper/2305.18779/) (2023)
- [Uniform Convergence of Adversarially Robust Classifiers](https://mlsanity.com/paper/2406.14682/) (2024)
- [Adversarially Robust PAC Learning with Optimal VC Rates](https://mlsanity.com/paper/2609.24260/) (2026)

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