# On the Computability of Robust PAC Learning

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 52 references that are in the map.
- First posted on arXiv 14 Jun 2024.

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

- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Rademacher Complexity for Adversarially Robust Generalization](https://mlsanity.com/paper/1810.11914/) (2018)
- [Are adversarial examples inevitable?](https://mlsanity.com/paper/1809.02104/) (2018)
- [Robustness of classifiers: from adversarial to random noise](https://mlsanity.com/paper/1608.08967/) (2016)
- [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)
- [Adversarial vulnerability for any classifier](https://mlsanity.com/paper/1802.08686/) (2018)
- [Analysis of classifiers' robustness to adversarial perturbations](https://mlsanity.com/paper/1502.02590/) (2015)
- [Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks](https://mlsanity.com/paper/2004.13617/) (2020)
- [The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure](https://mlsanity.com/paper/1809.03063/) (2018)
- [Adversarial Risk and Robustness: General Definitions and Implications for the Uniform Distribution](https://mlsanity.com/paper/1810.12272/) (2018)
- [Adversarially Robust Learning with Unknown Perturbation Sets](https://mlsanity.com/paper/2102.02145/) (2021)
- [PAC-learning in the presence of evasion adversaries](https://mlsanity.com/paper/1806.01471/) (2018)
- [On the Hardness of Robust Classification](https://mlsanity.com/paper/1909.05822/) (2019)
- [Improved Generalization Bounds for Adversarially Robust Learning](https://mlsanity.com/paper/1810.02180/) (2018)
- [A Theory of PAC Learnability under Transformation Invariances](https://mlsanity.com/paper/2202.07552/) (2022)
- [Robustly-reliable learners under poisoning attacks](https://mlsanity.com/paper/2203.04160/) (2022)
- [Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization](https://mlsanity.com/paper/2209.07369/) (2022)
- [On characterizations of learnability with computable learners](https://mlsanity.com/paper/2202.05041/) (2022)
- [The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise](https://mlsanity.com/paper/2007.15220/) (2020)
- [Adversarially Robust Learning Could Leverage Computational Hardness](https://mlsanity.com/paper/1905.11564/) (2019)
- [Black-box Certification and Learning under Adversarial Perturbations](https://mlsanity.com/paper/2006.16520/) (2020)
- [A PAC-Bayes Analysis of Adversarial Robustness](https://mlsanity.com/paper/2102.11069/) (2021)
- [A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability](https://mlsanity.com/paper/2202.05420/) (2022)
- [Lower Bounds for Adversarially Robust PAC Learning](https://mlsanity.com/paper/1906.05815/) (2019)
- [On Computable Online Learning](https://mlsanity.com/paper/2302.04357/) (2023)
- [Can Adversarially Robust Learning Leverage Computational Hardness?](https://mlsanity.com/paper/1810.01407/) (2018)
- [Computational Limitations in Robust Classification and Win-Win Results](https://mlsanity.com/paper/1902.01086/) (2019)
- [Find a witness or shatter: the landscape of computable PAC learning](https://mlsanity.com/paper/2302.04731/) (2023)
- [Reliable learning in challenging environments](https://mlsanity.com/paper/2304.03370/) (2023)

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

- [Effective Littlestone Dimension](https://mlsanity.com/paper/2411.15109/) (2024)
- [Proper Learnability and the Role of Unlabeled Data](https://mlsanity.com/paper/2502.10359/) (2025)
- [On the Computability of Multiclass PAC Learning](https://mlsanity.com/paper/2502.06089/) (2025)
- [Computable universal online learning](https://mlsanity.com/paper/2510.18352/) (2025)
- [Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning](https://mlsanity.com/paper/2511.02644/) (2025)
- [Uniform Computability of PAC Learning](https://mlsanity.com/paper/2601.18663/) (2026)

## Abstract (arXiv)

We initiate the study of computability requirements for adversarially robust learning. Adversarially robust PAC-type learnability is by now an established field of research. However, the effects of computability requirements in PAC-type frameworks are only just starting to emerge. We introduce the problem of robust computable PAC (robust CPAC) learning and provide some simple sufficient conditions for this. We then show that learnability in this setup is not implied by the combination of its components: classes that are both CPAC and robustly PAC learnable are not necessarily robustly CPAC learnable. Furthermore, we show that the novel framework exhibits some surprising effects: for robust CPAC learnability it is not required that the robust loss is computably evaluable! Towards understanding characterizing properties, we introduce a novel dimension, the computable robust shattering dimension. We prove that its finiteness is necessary, but not sufficient for robust CPAC learnability. This might yield novel insights for the corresponding phenomenon in the context of robust PAC learnability, where insufficiency of the robust shattering dimension for learnability has been conjectured, but so far a resolution has remained elusive.