Decidability of Sample Complexity of PAC Learning in finite setting
This work addresses a theoretical problem in machine learning theory for researchers, providing a decidability result for sample complexity in a finite setting, but it is incremental as it builds on prior undecidability findings.
The authors tackled the problem of determining the sample complexity of PAC learning for concepts like EMX, showing it can be exactly computed when there is an a priori bound on the support size of probability measures, in contrast to known undecidability results without such bounds. The result is a decision procedure, though it is computationally inefficient, being at least doubly exponential in the number of points times the bound.
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.