Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning

David Kattermann, Lothar Sebastian Krapp
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3950-3969, 2026.

Abstract

We study computable probably approximately correct (CPAC) learning, where learners are required to be computable functions. It had been previously observed that the Fundamental Theorem of Sta- tistical Learning, which characterizes PAC learnability by finiteness of the Vapnik-Chervonenkis (VC-)dimension, no longer holds in this framework. Recent works recovered analogs of the Funda- mental Theorem in the computable setting, for instance by introducing an effective VC-dimension. In this work, we investigate the relationship between CPAC learning and recursively enumerable representable (RER) classes, hypothesis classes whose members can be algorithmically listed, in the context of the Fundamental Theorem. We demonstrate that the RER property is deeply con- nected to CPAC learning by characterizing several notions of CPAC learnability via the existence of certain RER classes realizing the same samples. We further establish that the RER property alone is sufficient to guarantee nonuniform CPAC learnability and give a sufficient condition for CPAC learnable classes to be RER. Other results show that the effective VC-dimension can take arbitrary values above the traditional one and we note that the two dimensions coincide given the existence of a computable empirical risk minimizer. This recovers classical PAC bounds for most practically relevant classes and establishes a family of examples separating several notions of learnability.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-kattermann26a, title = {Recursively {Enumerably} {Representable} {Classes} and {Computable} {Versions} of the {Fundamental Theorem} of {Statistical Learning}}, author = {Kattermann, David and Krapp, Lothar Sebastian}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {3950--3969}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/kattermann26a/kattermann26a.pdf}, url = {https://proceedings.mlr.press/v336/kattermann26a.html}, abstract = {We study computable probably approximately correct (CPAC) learning, where learners are required to be computable functions. It had been previously observed that the Fundamental Theorem of Sta- tistical Learning, which characterizes PAC learnability by finiteness of the Vapnik-Chervonenkis (VC-)dimension, no longer holds in this framework. Recent works recovered analogs of the Funda- mental Theorem in the computable setting, for instance by introducing an effective VC-dimension. In this work, we investigate the relationship between CPAC learning and recursively enumerable representable (RER) classes, hypothesis classes whose members can be algorithmically listed, in the context of the Fundamental Theorem. We demonstrate that the RER property is deeply con- nected to CPAC learning by characterizing several notions of CPAC learnability via the existence of certain RER classes realizing the same samples. We further establish that the RER property alone is sufficient to guarantee nonuniform CPAC learnability and give a sufficient condition for CPAC learnable classes to be RER. Other results show that the effective VC-dimension can take arbitrary values above the traditional one and we note that the two dimensions coincide given the existence of a computable empirical risk minimizer. This recovers classical PAC bounds for most practically relevant classes and establishes a family of examples separating several notions of learnability.} }
Endnote
%0 Conference Paper %T Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning %A David Kattermann %A Lothar Sebastian Krapp %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-kattermann26a %I PMLR %P 3950--3969 %U https://proceedings.mlr.press/v336/kattermann26a.html %V 336 %X We study computable probably approximately correct (CPAC) learning, where learners are required to be computable functions. It had been previously observed that the Fundamental Theorem of Sta- tistical Learning, which characterizes PAC learnability by finiteness of the Vapnik-Chervonenkis (VC-)dimension, no longer holds in this framework. Recent works recovered analogs of the Funda- mental Theorem in the computable setting, for instance by introducing an effective VC-dimension. In this work, we investigate the relationship between CPAC learning and recursively enumerable representable (RER) classes, hypothesis classes whose members can be algorithmically listed, in the context of the Fundamental Theorem. We demonstrate that the RER property is deeply con- nected to CPAC learning by characterizing several notions of CPAC learnability via the existence of certain RER classes realizing the same samples. We further establish that the RER property alone is sufficient to guarantee nonuniform CPAC learnability and give a sufficient condition for CPAC learnable classes to be RER. Other results show that the effective VC-dimension can take arbitrary values above the traditional one and we note that the two dimensions coincide given the existence of a computable empirical risk minimizer. This recovers classical PAC bounds for most practically relevant classes and establishes a family of examples separating several notions of learnability.
APA
Kattermann, D. & Krapp, L.S.. (2026). Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:3950-3969 Available from https://proceedings.mlr.press/v336/kattermann26a.html.

Related Material