In the abstract realm of statistical learning theory, the "Fundamental Theorem of Statistical Learning" provides a clean characterization of learnability: a hypothesis class is learnable in the Probably Approximately Correct (PAC) framework if and only if it has a finite Vapnik-Chervonenkis (VC) dimension. However, this theorem assumes the existence of a learner without considering its algorithmic nature. This paper investigates the "computable" landscape, where the learner must be a Turing Machine, revealing a far more complex structure than classical theory suggests.
The Computability Gap
In classical PAC learning, we do not concern ourselves with how a learner finds a hypothesis, only that a hypothesis with low error exists and can be identified given enough data. Computable PAC (CPAC) learning introduces a critical constraint: the learner must be a computer program.
Recent research has demonstrated that a finite VC dimension is a necessary but insufficient condition for computable learnability. This paper addresses three major open problems in this field, mapping the boundaries of what can be learned by algorithms and proving that computational constraints create a strict hierarchy between different types of learners—distinctions that do not exist in standard statistical theory.
The "Witness" and Effective VC Dimension
The authors' primary theoretical contribution is the definition of Effective VC Dimension. In classical theory, VC dimension is defined by the existence of "shattered" sets. To bridge this with computability, the authors require a "witness": a computable function that, given any $k+1$ points, can algorithmically point to a labeling that the hypothesis class cannot produce.
Essentially, to learn computably, it is not enough for a class to simply have a finite VC dimension; one must be able to algorithmically prove that the class fails to shatter certain sets. If an algorithm cannot "witness" this failure, it cannot effectively narrow down the hypothesis space.
Key Insights into the Learning Landscape
The research settles several long-standing conjectures regarding the power and limitations of computable learners:
1. Improper vs. Proper Learning
In classical theory, the distinction between proper learning (where the learner must output a hypothesis from the target class) and improper learning (where the learner can output any computable function) is often treated as a matter of convenience. The authors show that while improper learners are more flexible, every improperly learnable class is actually a subset of some properly learnable class. However, they prove a strict hierarchy: Strong Proper CPAC ⊂ Proper CPAC ⊂ CPAC (Improper), meaning improper learning does provide a genuine expansion of algorithmic capability.
2. The Complexity of Data Needs
One of the paper's most striking results involves sample complexity—the amount of data required to reach a certain level of accuracy. The authors prove that there are hypothesis classes that are computable PAC learnable, but for which the sample complexity function is uncomputable. In these cases, we know a learner exists, but we can never compute how much data it will need to succeed.
3. Separation from Online Learning
In classical theory, any class that is learnable in an online setting (having a finite Littlestone dimension) is also PAC learnable. The authors demonstrate that this relationship collapses under computability constraints. They construct a hypothesis class with a Littlestone dimension of 1—making it extremely simple for online learning—that is nonetheless impossible to learn via any computable PAC algorithm.
Formal Results and Theorems
The paper establishes a complete landscape of inclusions and separations:
- Theorem 3: A class is CPAC learnable if and only if its effective VC dimension is finite.
- Theorem 4: There exists a class that is learnable, but its sample complexity grows faster than any computable function, separating "Strong CPAC" from standard "CPAC."
- Theorem 5: There is a class with Littlestone dimension 1 that is not CPAC learnable, proving that online learnability does not imply computable PAC learnability.
Conclusion and Future Directions
This work provides a definitive map of the possibilities of computable learning in the realizable setting (where the true function is assumed to be within the class). By employing tools from recursion theory and diagonalization, the authors show that the transition from statistical existence to algorithmic implementation is non-trivial.
While the hypothesis classes used to prove these separations are specifically engineered "pathological" examples, they raise fundamental questions about the limits of AI. Future research is needed to determine if these gaps—such as uncomputable sample complexity—manifest in the "natural" hypothesis classes used in practical machine learning or within the agnostic setting, where the target function may lie outside the hypothesis class.
Summary updated