# Decidability of Sample Complexity of PAC Learning in finite setting

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2020.

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

- [Undecidability of Underfitting in Learning Algorithms](https://mlsanity.com/paper/2102.02850/) (2021)
- [From Undecidability of Non-Triviality and Finiteness to Undecidability of Learnability](https://mlsanity.com/paper/2106.01382/) (2021)

## Abstract (arXiv)

In this short note we observe that the sample complexity of PAC machine learning of various concepts, including learning the maximum (EMX), can be exactly determined when the support of the probability measures considered as models satisfies an a-priori bound. This result contrasts with the recently discovered undecidability of EMX within ZFC for finitely supported probabilities (with no a priori bound). Unfortunately, the decision procedure is at present, at least doubly exponential in the number of points times the uniform bound on the support size.