PhD Seminar • Machine Learning • On Learnability with Computable Learners

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.

To attend this PhD seminar in person, please go to DC 2314. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/j/96352899667.