Abstract
This paper contributes to the study of CPAC learnability —a computable version of PAC learning– by solving three open questions from recent papers. Firstly, we prove that every improperly CPAC learnable class is contained in a class which is properly CPAC learnable with polynomial sample complexity. This confirms a conjecture by Agarwal et al (COLT 2021). Secondly, we show that there exists a decidable class of hypotheses which is properly CPAC learnable, but only with uncomputably fast-growing sample complexity. This solves a question from Sterkenburg (COLT 2022). Finally, we construct a decidable class of finite Littlestone dimension which is not improperly CPAC learnable, strengthening a recent result of Sterkenburg (2022) and answering a question posed by Hasrati and Ben-David (ALT 2023). Together with previous work, our results provide a complete landscape for the learnability problem in the CPAC setting.
Introduction: The Computability Gap in Learning Theory
In classical learning theory, the Fundamental Theorem of Statistical Learning provides a clean characterization of learnability: a hypothesis class is learnable if and only if its Vapnik-Chervonenkis (VC) dimension is finite. However, this framework treats the learner as an abstract mathematical function. In practice, learning is performed by algorithms. Computable PAC (CPAC) learning introduces a critical constraint: the learning algorithm and the functions it outputs must be computable by a Turing Machine.
Recent research has revealed that this constraint fundamentally alters the landscape of learnability. Some classes with finite VC dimension are not learnable by any computer. This paper maps the resulting hierarchy, addressing three core dimensions: the distinction between proper and improper learning, the computability of sample complexity, and the relationship between online and batch learning.
Methodology
The study employs formal logic and computability theory to explore the boundaries of CPAC. Key methodological innovations include:
- Effective VC Dimension: A computable refinement of VC dimension. Beyond requiring that a set cannot be shattered, this metric requires the existence of a "witness"—an algorithm that can identify a labeling not present in the hypothesis class.
- Diagonalization: A classic tool from computability theory used to construct "pathological" hypothesis classes that elude any possible computable learner.
- Asymptotic ERM: A relaxed version of Empirical Risk Minimization (ERM) designed to characterize learners that converge toward optimal hypotheses even when they cannot find them perfectly for small samples.
The Landscape of Computable Learning
The central contribution of this work is the formalization of the hierarchy between different learning paradigms. Unlike the classical setting where many of these distinctions collapse, the computable world is strictly stratified.
As illustrated in the figure above, PAC learning remains the broadest category. Within it, CPAC learning is a subset. A significant finding of this paper is the collapse of several improper learning categories: the set of improperly CPAC learnable classes is equivalent to those that are improperly Strong CPAC (SCPAC) learnable, and also to those that are subsets of properly learnable classes. However, proper learning remains a strictly more difficult requirement, with proper SCPAC (where sample complexity is computable) being the most restrictive.
Key Insights and Results
The paper settles several major open questions in the field:
- Settling Agarwal’s Conjecture: The authors prove that every improperly CPAC learnable class is a subset of some properly CPAC learnable class. This simplifies the theoretical landscape by showing that improper learning does not grant fundamentally more power than proper learning in terms of the classes that can be covered.
- Characterization via Effective VC Dimension: The paper establishes that a class is improperly CPAC learnable if and only if its effective VC dimension is finite. This provides the "computable" analogue to the classical VC dimension characterization.
- Uncomputable Sample Complexity: The authors demonstrate the existence of a class that is learnable, yet its sample complexity (the data required for a specific accuracy) grows faster than any computable function. This implies that while a concept may be learnable in principle, we cannot algorithmically determine how much data is needed to achieve a desired performance.
- Limits of Online Simplicity: Even classes with a Littlestone dimension of 1—indicating extreme simplicity in online learning—can be impossible for a computer to learn in a batch setting, strengthening previous results by Sterkenburg.
Conclusion and Future Directions
This work provides a comprehensive map of the CPAC landscape in the realizable setting. However, the agnostic setting—where the target function may lie outside the hypothesis class—remains only partially characterized. Furthermore, while this paper defines what is computable, it does not address efficiency. Future research into "Efficiently Computable PAC learning" (e.g., polynomial-time constraints) will be necessary to bridge these theoretical foundations with practical machine learning applications.
Summary updated