Computability aspects in statistical learning

Abstract

Probably approximately correct (PAC) learning is the standard framework for supervised binary classification in statistical learning theory. Its purpose is to describe from a statistical perspective how machines can learn to make binary decisions based on finitely many examples. A classical result is the Fundamental Theorem of PAC Learning due to Blumer et al. (1989), which characterizes several seemingly different notions of PAC learnability by the finiteness of a combinatorial measure called the VC-dimension. In this thesis, PAC learning is studied from the viewpoint of computability theory, the standard framework for formalizing algorithms in theoretical computer science. Interest in computability-theoretic aspects of PAC learning has developed in recent years, initially to exclude undecidability results relying on uncomputable learning functions. Unfortunately, it turned out that the classical Fundamental Theorem of PAC Learning fails when learning functions are required to be computable. This causes the landscape of computable PAC learning to be very diverse, with numerous non-equivalent intermediate notions. This thesis provides a comprehensive overview of the field by establishing necessary and sufficient conditions for various notions and constructing counterexamples separating them. A main result is a computable version of the Fundamental Theorem of PAC Learning due to Delle Rose et al. (2023) that is based on a computable analog of the VC-dimension called the effective VC-dimension. An extensive discussion of this fairly new measure is provided and its relation to the classical VC-dimension is analyzed. Another focus lies on the connection between computable PAC learnability and so-called RER classes. The last part discusses computability in the relaxed setting of nonuniform PAC learning. It is demonstrated that any RER class is nonuniformly PAC learnable with a computable learning function. Some of the results are generalized to continuous domains in the appendix using the framework of computable analysis.