# A Theory of PAC Learnability of Partial Concept Classes

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

## Key facts

- Cited by 60 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 83 references that are in the map.
- First posted on arXiv 18 Jul 2021.

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

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Does Learning Require Memorization? A Short Tale about a Long Tail](https://mlsanity.com/paper/1906.05271/) (2019)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [Predicting Neural Network Accuracy from Weights](https://mlsanity.com/paper/2002.11448/) (2020)
- [When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?](https://mlsanity.com/paper/2012.06421/) (2020)
- [In Search of Robust Measures of Generalization](https://mlsanity.com/paper/2010.11924/) (2020)
- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [An Equivalence Between Private Classification and Online Prediction](https://mlsanity.com/paper/2003.00563/) (2020)
- [On the role of data in PAC-Bayes bounds](https://mlsanity.com/paper/2006.10929/) (2020)
- [What Do Neural Networks Learn When Trained With Random Labels?](https://mlsanity.com/paper/2006.10455/) (2020)
- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [Rates of Convergence for Nearest Neighbor Classification](https://mlsanity.com/paper/1407.0067/) (2014)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [Sample-efficient proper PAC learning with approximate differential privacy](https://mlsanity.com/paper/2012.03893/) (2020)
- [Sample Compression for Real-Valued Learners](https://mlsanity.com/paper/1805.08254/) (2018)
- [Boosting Simple Learners](https://mlsanity.com/paper/2001.11704/) (2020)
- [Efficient Private Algorithms for Learning Large-Margin Halfspaces](https://mlsanity.com/paper/1902.09009/) (2019)
- [A Compression Technique for Analyzing Disagreement-Based Active Learning](https://mlsanity.com/paper/1404.1504/) (2014)
- [Private Learning Implies Online Learning: An Efficient Reduction](https://mlsanity.com/paper/1905.11311/) (2019)
- [Near-optimal sample compression for nearest neighbors](https://mlsanity.com/paper/1404.3368/) (2014)
- [Exact Lower Bounds for the Agnostic Probably-Approximately-Correct (PAC) Machine Learning Model](https://mlsanity.com/paper/1606.08920/) (2016)
- [Nearest-Neighbor Sample Compression: Efficiency, Consistency, Infinite Dimensions](https://mlsanity.com/paper/1705.08184/) (2017)

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

- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [Optimal PAC Bounds Without Uniform Convergence](https://mlsanity.com/paper/2304.09167/) (2023)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [A Characterization of List Learnability](https://mlsanity.com/paper/2211.04956/) (2022)
- [Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization](https://mlsanity.com/paper/2209.07369/) (2022)
- [List Online Classification](https://mlsanity.com/paper/2303.15383/) (2023)
- [Regularization and Optimal Multiclass Learning](https://mlsanity.com/paper/2309.13692/) (2023)
- [Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes](https://mlsanity.com/paper/2210.02297/) (2022)
- [A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability](https://mlsanity.com/paper/2202.05420/) (2022)
- [Weisfeiler-Leman at the margin: When more expressivity matters](https://mlsanity.com/paper/2402.07568/) (2024)
- [The One-Inclusion Graph Algorithm is not Always Optimal](https://mlsanity.com/paper/2212.09270/) (2022)
- [The Optimal Sample Complexity of Multiclass and List Learning](https://mlsanity.com/paper/2604.24749/) (2026)
- [List Sample Compression and Uniform Convergence](https://mlsanity.com/paper/2403.10889/) (2024)
- [Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back](https://mlsanity.com/paper/2511.12659/) (2025)
- [Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes](https://mlsanity.com/paper/2211.09101/) (2022)
- [Multiclass Learnability Does Not Imply Sample Compression](https://mlsanity.com/paper/2308.06424/) (2023)
- [Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem](https://mlsanity.com/paper/2407.07765/) (2024)
- [A Characterization of List Regression](https://mlsanity.com/paper/2409.19218/) (2024)
- [Fat-Shattering Dimension of k-fold Aggregations](https://mlsanity.com/paper/2110.04763/) (2021)
- [Online Learning and Disambiguations of Partial Concept Classes](https://mlsanity.com/paper/2303.17578/) (2023)
- [Probably Approximately Precision and Recall Learning](https://mlsanity.com/paper/2411.13029/) (2024)
- [Online Learning of Neural Networks](https://mlsanity.com/paper/2505.09167/) (2025)
- [Is Transductive Learning Equivalent to PAC Learning?](https://mlsanity.com/paper/2405.05190/) (2024)
- [Transformation-Invariant Learning and Theoretical Guarantees for OOD Generalization](https://mlsanity.com/paper/2410.23461/) (2024)
- [Spherical dimension](https://mlsanity.com/paper/2503.10240/) (2025)
- [Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2503.15294/) (2025)
- [Leveraging Predictive Equivalence in Decision Trees](https://mlsanity.com/paper/2506.14143/) (2025)
- [Learning with Monotone Adversarial Corruptions](https://mlsanity.com/paper/2601.02193/) (2026)
- [Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?](https://mlsanity.com/paper/2406.11667/) (2024)

## Abstract (arXiv)

We extend the theory of PAC learning in a way which allows to model a rich variety of learning tasks where the data satisfy special properties that ease the learning process. For example, tasks where the distance of the data from the decision boundary is bounded away from zero. The basic and simple idea is to consider partial concepts: these are functions that can be undefined on certain parts of the space. When learning a partial concept, we assume that the source distribution is supported only on points where the partial concept is defined. This way, one can naturally express assumptions on the data such as lying on a lower dimensional surface or margin conditions. In contrast, it is not at all clear that such assumptions can be expressed by the traditional PAC theory. In fact we exhibit easy-to-learn partial concept classes which provably cannot be captured by the traditional PAC theory. This also resolves a question posed by Attias, Kontorovich, and Mansour 2019. We characterize PAC learnability of partial concept classes and reveal an algorithmic landscape which is fundamentally different than the classical one. For example, in the classical PAC model, learning boils down to Empirical Risk Minimization (ERM). In stark contrast, we show that the ERM principle fails in explaining learnability of partial concept classes. In fact, we demonstrate classes that are incredibly easy to learn, but such that any algorithm that learns them must use an hypothesis space with unbounded VC dimension. We also find that the sample compression conjecture fails in this setting. Thus, this theory features problems that cannot be represented nor solved in the traditional way. We view this as evidence that it might provide insights on the nature of learnability in realistic scenarios which the classical theory fails to explain.