# A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 89 references that are in the map.
- First posted on arXiv 11 Feb 2022.

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

- [Unlabeled Data Improves Adversarial Robustness](https://mlsanity.com/paper/1905.13736/) (2019)
- [Adversarially Robust Generalization Requires More Data](https://mlsanity.com/paper/1804.11285/) (2018)
- [Theoretical Analysis of Self-Training with Deep Networks on Unlabeled Data](https://mlsanity.com/paper/2010.03622/) (2020)
- [Are Labels Required for Improving Adversarial Robustness?](https://mlsanity.com/paper/1905.13725/) (2019)
- [Rademacher Complexity for Adversarially Robust Generalization](https://mlsanity.com/paper/1810.11914/) (2018)
- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [Adversarially Robust Generalization Just Requires More Unlabeled Data](https://mlsanity.com/paper/1906.00555/) (2019)
- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Robustness to Adversarial Perturbations in Learning from Incomplete Data](https://mlsanity.com/paper/1905.13021/) (2019)
- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [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)
- [Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound](https://mlsanity.com/paper/2011.04586/) (2020)
- [Reducing Adversarially Robust Learning to Non-Robust PAC Learning](https://mlsanity.com/paper/2010.12039/) (2020)
- [Refined Error Bounds for Several Learning Algorithms](https://mlsanity.com/paper/1512.07146/) (2015)
- [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)
- [Improved Generalization Bounds for Adversarially Robust Learning](https://mlsanity.com/paper/1810.02180/) (2018)
- [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)
- [When can unlabeled data improve the learning rate?](https://mlsanity.com/paper/1905.11866/) (2019)
- [Black-box Certification and Learning under Adversarial Perturbations](https://mlsanity.com/paper/2006.16520/) (2020)
- [Transductive Robust Learning Guarantees](https://mlsanity.com/paper/2110.10602/) (2021)
- [Domain Invariant Adversarial Learning](https://mlsanity.com/paper/2104.00322/) (2021)

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

- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [The One-Inclusion Graph Algorithm is not Always Optimal](https://mlsanity.com/paper/2212.09270/) (2022)
- [Adversarially Robust PAC Learnability of Real-Valued Functions](https://mlsanity.com/paper/2206.12977/) (2022)
- [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)
- [On Proper Learnability between Average- and Worst-case Robustness](https://mlsanity.com/paper/2211.05656/) (2022)
- [Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?](https://mlsanity.com/paper/2406.11667/) (2024)
- [Uniformly Stable Algorithms for Adversarial Training and Beyond](https://mlsanity.com/paper/2405.01817/) (2024)
- [Sample Compression Scheme Reductions](https://mlsanity.com/paper/2410.13012/) (2024)
- [Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning](https://mlsanity.com/paper/2506.00135/) (2025)
- [Bagging Robustly Learns VC Classes with Linear Sample Complexity](https://mlsanity.com/paper/2608.13514/) (2026)
- [Adversarially Robust PAC Learning with Optimal VC Rates](https://mlsanity.com/paper/2609.24260/) (2026)

## Abstract (arXiv)

We study the problem of learning an adversarially robust predictor to test time attacks in the semi-supervised PAC model. We address the question of how many labeled and unlabeled examples are required to ensure learning. We show that having enough unlabeled data (the size of a labeled sample that a fully-supervised method would require), the labeled sample complexity can be arbitrarily smaller compared to previous works, and is sharply characterized by a different complexity measure. We prove nearly matching upper and lower bounds on this sample complexity. This shows that there is a significant benefit in semi-supervised robust learning even in the worst-case distribution-free model, and establishes a gap between the supervised and semi-supervised label complexities which is known not to hold in standard non-robust PAC learning.