PAC Learning, VC Dimension, and the Arithmetic Hierarchy
Not on the map. Why?
Abstract (arXiv)
We compute that the index set of PAC-learnable concept classes is m-complete Sigma03 within the set of indices for all concept classes of a reasonable form. All concept classes considered are computable enumerations of computable Pi01 classes, in a sense made precise here. This family of concept classes is sufficient to cover all standard examples, and also has the property that PAC learnability is equivalent to finite VC dimension.
Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). First posted on arXiv 4 Jun 2014.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 2; 2022: 1; 2023: 0; 2024: 0; 2025: 1; 2026: 1.
5 papers.
- 2022On characterizations of learnability with computable learnerscited by 16
- 2021From Undecidability of Non-Triviality and Finiteness to Undecidability of Learnabilitycited by 4
- 2021On computable learning of continuous featurescited by 2
- 2025On statistical learning of graphscited by 0
- 2026Uniform Computability of PAC Learningcited by 0
- 2026Uniform Computability of PAC Learning26 Jan 2026
- 2025On statistical learning of graphs17 Jul 2025
- 2022On characterizations of learnability with computable learners10 Feb 2022
- 2021On computable learning of continuous features24 Nov 2021
- 2021From Undecidability of Non-Triviality and Finiteness to Undecidability of Learnability2 Jun 2021