Please note: This PhD seminar will take place in DC 2314 and online.
Tosca Lechner, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Shai Ben-David
We initiate a study of learning with computable learners and computable output predictors. Re- cent results in statistical learning theory have shown that there are basic learning problems whose learnability cannot be determined within ZFC (Ben-David et al. (2017, 2019)). This motivates us to consider learnability by algorithms with computable output predictors (both learners and predictors are then representable as finite objects). We thus propose the notion of CPAC learnability, by adding some basic computability requirements into a PAC learning framework. As a first step towards a characterization, we show that in this framework learnability of a binary hypothesis class is not implied by finiteness of its VC-dimension anymore. We also present some situations where we are guaranteed to have a computable learner.