# Adversarially Robust PAC Learnability of Real-Valued Functions

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 72 references that are in the map.
- First posted on arXiv 26 Jun 2022.

## Builds on (most cited first, 30 of 30)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Adversarially Robust Generalization Requires More Data](https://mlsanity.com/paper/1804.11285/) (2018)
- [Rademacher Complexity for Adversarially Robust Generalization](https://mlsanity.com/paper/1810.11914/) (2018)
- [Online Control with Adversarial Disturbances](https://mlsanity.com/paper/1902.08721/) (2019)
- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [Adversarial examples from computational constraints](https://mlsanity.com/paper/1805.10204/) (2018)
- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks](https://mlsanity.com/paper/2004.13617/) (2020)
- [Calibration and Consistency of Adversarial Surrogate Losses](https://mlsanity.com/paper/2104.09658/) (2021)
- [Online Learning for Time Series Prediction](https://mlsanity.com/paper/1302.6927/) (2013)
- [Adversarial Risk and Robustness: General Definitions and Implications for the Uniform Distribution](https://mlsanity.com/paper/1810.12272/) (2018)
- [Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification](https://mlsanity.com/paper/2006.16384/) (2020)
- [Reducing Adversarially Robust Learning to Non-Robust PAC Learning](https://mlsanity.com/paper/2010.12039/) (2020)
- [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)
- [On the Hardness of Robust Classification](https://mlsanity.com/paper/1909.05822/) (2019)
- [Efficiently Learning Adversarially Robust Halfspaces with Noise](https://mlsanity.com/paper/2005.07652/) (2020)
- [Adversarially Robust Estimate and Risk Analysis in Linear Regression](https://mlsanity.com/paper/2012.10278/) (2020)
- [Sample Compression for Real-Valued Learners](https://mlsanity.com/paper/1805.08254/) (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)
- [Transductive Robust Learning Guarantees](https://mlsanity.com/paper/2110.10602/) (2021)
- [Classification with Low Rank and Missing Data](https://mlsanity.com/paper/1501.03273/) (2015)
- [Primal and Dual Combinatorial Dimensions](https://mlsanity.com/paper/2108.10037/) (2021)
- [A Non-generative Framework and Convex Relaxations for Unsupervised Learning](https://mlsanity.com/paper/1610.01132/) (2016)
- [An optimal unrestricted learning procedure](https://mlsanity.com/paper/1707.05342/) (2017)

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

- [PAC Learning with Improvements](https://mlsanity.com/paper/2503.03184/) (2025)
- [On Proper Learnability between Average- and Worst-case Robustness](https://mlsanity.com/paper/2211.05656/) (2022)
- [Sample Compression Scheme Reductions](https://mlsanity.com/paper/2410.13012/) (2024)
- [On damage of interpolation to adversarial robustness in regression](https://mlsanity.com/paper/2601.16070/) (2026)
- [Bagging Robustly Learns VC Classes with Linear Sample Complexity](https://mlsanity.com/paper/2608.13514/) (2026)
- [Robust Online Learning](https://mlsanity.com/paper/2602.06775/) (2026)
- [Adversarially Robust PAC Learning with Optimal VC Rates](https://mlsanity.com/paper/2609.24260/) (2026)
- [An Agnostic Sample Compression Scheme for Squared Loss of Near-Linear Size in the Fat-Shattering Dimension](https://mlsanity.com/paper/2609.29696/) (2026)

## Abstract (arXiv)

We study robustness to test-time adversarial attacks in the regression setting with ℓp losses and arbitrary perturbation sets. We address the question of which function classes are PAC learnable in this setting. We show that classes of finite fat-shattering dimension are learnable in both realizable and agnostic settings. Moreover, for convex function classes, they are even properly learnable. In contrast, some non-convex function classes provably require improper learning algorithms. Our main technique is based on a construction of an adversarially robust sample compression scheme of a size determined by the fat-shattering dimension. Along the way, we introduce a novel agnostic sample compression scheme for real-valued functions, which may be of independent interest.