Computable PAC learning

Abstract: PAC (probably approximately correct) learning is a framework for the theoretical analysis of machine learning, proposed by Valiant in 1984. Intuitively, we consider a certain class of hypotheses: a learner for this class receives a finite amount of random samples of an unknown objective function and, with high probability, outputs a function which approximates the objective function no worse than any hypothesis in the given class. The fundamental theorem of statistical learning characterizes the existence of a learner for a certain class of hypotheses with a combinatorial property of the class itself, namely the finiteness of its so-called VC dimension (Vapnik and Chervonenkis, 1971; Blumer et al., 1989). However, all this theory deals with learners when simply considered as functions, without taking into account any effectiveness aspect: what does it happen, then, when we only focus on learners which can be implemented by some algorithmic procedure? To investigate this question, Agarwal et al. (2020) introduced computable PAC (CPAC) learning, where both the learner and the functions it outputs are required to be computable. Their key observation is that, in this new framework, the finiteness of VC dimension does no longer suffice to ensure the existence of a computable learner. Moreover, this computable setting is affected by certain aspects which do not make any difference in classical PAC learning: for example, whether the learner is required to be proper (i.e. its range must be contained in the class of hypotheses to be learned) or allowed to be improper (i.e. it can output any function), or whether the number of samples the learner needs to actually learn the class is bounded by a computable function. But which of these aspects actually lead to different versions of computable learnability? In this talk, we will provide a landscape of the field, based on previous work of Agarwal et al. (2020), Sterkenburg (2022) and recent joint work with Alexander Kozachinskiy, Cristóbal Rojas and Tomasz Steifer (Pontificia Universidad Católica de Chile).

logic

Audience: researchers in the topic

Computability theory and applications

Series comments: Description: Computability theory, logic

The goal of this endeavor is to run a seminar on the platform Zoom on a weekly basis, perhaps with alternating time slots each of which covers at least three out of four of Europe, North America, Asia, and New Zealand/Australia. While the meetings are always scheduled for Tuesdays, the timezone varies, so please refer to the calendar on the website for details about individual seminars.