On characterizations of learnability with computable learners

Proceedings of Machine Learning Research 178:3365-3379 (2022)
  Copy   BIBTEX


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 provide a negative answer to the COLT open problem posed by Agarwal et al. (2021) whether all decidably representable VC classes are improperly CPAC learnable. Second, we consider undecidability of (computable) PAC learnability. We give a simple general argument to exhibit such ndecidability, and 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.



    Upload a copy of this work     Papers currently archived: 92,991

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

PAC learning, VC dimension, and the arithmetic hierarchy.Wesley Calvert - 2015 - Archive for Mathematical Logic 54 (7-8):871-883.
Inside the Muchnik degrees I: Discontinuity, learnability and constructivism.K. Higuchi & T. Kihara - 2014 - Annals of Pure and Applied Logic 165 (5):1058-1114.
Model theory and machine learning.Hunter Chase & James Freitag - 2019 - Bulletin of Symbolic Logic 25 (3):319-332.
Computational complexity on computable metric spaces.Klaus Weirauch - 2003 - Mathematical Logic Quarterly 49 (1):3-21.


Added to PP

24 (#677,847)

6 months
7 (#491,772)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Tom F. Sterkenburg
Ludwig Maximilians Universität, München

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references