On characterizations of learnability with computable learners

Tom F. Sterkenburg
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:3365-3379, 2022.

Abstract

We study computable PAC (CPAC) learning as introduced by Agarwal et al. (2020). First, we consider the main open question of finding characterizations of proper and improper CPAC learning. We give a characterization of a closely related notion of *strong* CPAC learning, and we provide a negative answer to the COLT open problem posed by Agarwal et al. (2021) whether all decidably representable PAC learnable classes are improperly CPAC learnable. Second, we consider undecidability of (computable) PAC learnability. We give a simple general argument to exhibit such undecidability, and we initiate a study of the arithmetical complexity of learnability. We briefly discuss the relation to the undecidability result of Ben-David et al. (2019), that motivated the work of Agarwal et al.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-sterkenburg22a, title = {On characterizations of learnability with computable learners}, author = {Sterkenburg, Tom F.}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {3365--3379}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/sterkenburg22a/sterkenburg22a.pdf}, url = {https://proceedings.mlr.press/v178/sterkenburg22a.html}, abstract = {We study computable PAC (CPAC) learning as introduced by Agarwal et al. (2020). First, we consider the main open question of finding characterizations of proper and improper CPAC learning. We give a characterization of a closely related notion of *strong* CPAC learning, and we provide a negative answer to the COLT open problem posed by Agarwal et al. (2021) whether all decidably representable PAC learnable classes are improperly CPAC learnable. Second, we consider undecidability of (computable) PAC learnability. We give a simple general argument to exhibit such undecidability, and we initiate a study of the arithmetical complexity of learnability. We briefly discuss the relation to the undecidability result of Ben-David et al. (2019), that motivated the work of Agarwal et al.} }
Endnote
%0 Conference Paper %T On characterizations of learnability with computable learners %A Tom F. Sterkenburg %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-sterkenburg22a %I PMLR %P 3365--3379 %U https://proceedings.mlr.press/v178/sterkenburg22a.html %V 178 %X We study computable PAC (CPAC) learning as introduced by Agarwal et al. (2020). First, we consider the main open question of finding characterizations of proper and improper CPAC learning. We give a characterization of a closely related notion of *strong* CPAC learning, and we provide a negative answer to the COLT open problem posed by Agarwal et al. (2021) whether all decidably representable PAC learnable classes are improperly CPAC learnable. Second, we consider undecidability of (computable) PAC learnability. We give a simple general argument to exhibit such undecidability, and we initiate a study of the arithmetical complexity of learnability. We briefly discuss the relation to the undecidability result of Ben-David et al. (2019), that motivated the work of Agarwal et al.
APA
Sterkenburg, T.F.. (2022). On characterizations of learnability with computable learners. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:3365-3379 Available from https://proceedings.mlr.press/v178/sterkenburg22a.html.

Related Material