In classical statistical learning theory, the boundaries of what can be learned are governed by elegant combinatorial dimensions. If a hypothesis class has a finite Vapnik-Chervonenkis (VC) dimension, it is learnable in the Probably Approximately Correct (PAC) framework. If it has a finite Littlestone dimension, it is learnable in the online adversarial setting.
However, these foundational pillars rest on a subtle, unrealistic assumption: they allow a "learner" to be any arbitrary mathematical function. In the real world, machine learning models are executed by algorithms running on physical computers. When we restrict our learners to the set of computable functions, the traditional guarantees of statistical learning theory shatter. Simple hypothesis classes with minimal statistical complexity suddenly become impossible to learn, and the very question of whether a problem is learnable can become mathematically undecidable.
The Algorithmic Breakdown of Statistical Dimensions
To understand why computability breaks classical learning theory, we must look at how statistical dimensions interact with Turing machines. In the standard PAC framework, a finite VC dimension guarantees that a learner can generalize from a finite sample. But as Agarwal et al. demonstrated when introducing Computable PAC (CPAC) learnability, this guarantee fails when the learning algorithm must be computable.
The mechanism behind this failure is a direct reduction to the Halting Problem. It is possible to construct a hypothesis class with a VC dimension of only 1, where each hypothesis encodes the behavior of a specific Turing machine. If a computable learning algorithm were able to successfully identify the correct hypothesis from data, that algorithm would inadvertently solve whether those Turing machines halt. Because the Halting Problem is computationally undecidable, no such computable learner can exist.
A similar breakdown occurs in sequential environments. In online learning, the Littlestone dimension perfectly characterizes a model's optimal mistake bound. Yet, Hasrati showed that by encoding the Halting Problem into adversarial hypothesis classes, an environment can force any computable online learner to fail, even when the underlying class has a small Littlestone dimension.
One might hope that "improper learning"—allowing the algorithm to output a hypothesis outside the target class—could bypass these constraints by expanding the search space. However, Sterkenburg proved that even improper learning cannot rescue computable agents from certain decidably representable classes. When computational constraints are introduced, the inherent structure of the hypothesis class matters far more than the optimization power or flexibility of the learner.
The Topological Trap: Why Computable Learners Fail
Why does an adversary always win against a computable learner in these adversarial settings? The answer lies in the topological structure of the hypothesis space.
When an online learning algorithm processes a stream of data, it is essentially traversing a path through a hypothesis space, attempting to converge on the true target function. Kalociński and Steifer analyzed this process by looking at the topological closure of the hypothesis class—the set containing all the original functions plus all their limit points.
Hypothesis Class (Computable Functions)
│
├───► Limit Point A (Computable) ──► Learner can approximate
│
└───► Limit Point B (Uncomputable) ──► Adversary exploits this gap!
If the mathematical closure of a computable hypothesis class contains functions that are themselves uncomputable, a fundamental vulnerability emerges. During an online game, an adversary can select a sequence of labels that forces the data distribution to converge toward one of these uncomputable limit points. Because a computable learner can only represent and output computable functions, it can never accurately approximate or reach this limit. The adversary exploits this representational blind spot, forcing the algorithmic learner to make an infinite number of errors.
This tension between what is mathematically definable and what is algorithmically executable extends to other learning paradigms as well. For instance, Gourdeau et al. demonstrated that requiring a learner to be adversarially robust introduces similar friction, rendering certain well-defined robust learning tasks completely uncomputable.
Meta-Learnability and Axiomatic Independence
The complications of computability do not stop at the execution of the learning algorithm. They also infect the meta-theoretical task of determining whether a class is learnable in the first place.
If a researcher wants to know whether a specific concept class can be efficiently learned, how difficult is it to find out? Nanashima established the principle of meta-learning complexity, proving that deciding whether a concept class is efficiently learnable is computationally just as difficult as the underlying learning task itself. The complexity that makes a class hard to learn effectively shields it from being verified as learnable.
When we push this meta-question to its logical extreme, it transcends computational complexity and enters the realm of mathematical logic. The question of learnability can become independent of standard set theory—meaning it can neither be proven nor disproven using the Zermelo-Fraenkel axioms with the Axiom of Choice (ZFC).
Hanneke et al. demonstrated this axiomatic undecidability within multi-armed bandit problems. They showed that for certain deterministic reward function classes, proving whether a universal learning rule exists is impossible within ZFC. Similarly, Asilis et al. mapped classification tasks to Estimating the Maximum (EMX) problems, revealing that the boundary of proper learnability (restricting predictions to the target class) is highly sensitive to set-theoretic axioms and inherently undecidable.
Restoring Decidability Through Noise
Is a unified theory of learning completely impossible due to these logical barriers? Not necessarily. The absolute predictability of deterministic environments is precisely what allows an adversary to construct the logical paradoxes and Halting-Problem reductions that break the theory.
Hanneke and Wang discovered a fascinating escape hatch: the introduction of stochastic noise. While determining learnability for deterministic multi-armed bandits is completely undecidable, adding even a minor amount of stochastic noise fundamentally alters the geometry of the problem.
By evaluating the function space using a new geometric metric called the generalized maximin volume, the authors proved that the learnability of stochastic noisy bandits becomes entirely decidable. The injection of noise smooths away the sharp, adversarial limit points that allow the Halting Problem to be encoded, restoring the mathematical tractability of the field.
Key Foundational Work
On Learnability wih Computable Learners (2020) — contributed 3 concept elements to this direction.
Extending Learnability to Auxiliary-Input Cryptographic Primitives and Meta-PAC Learning (2020) — contributed 3 concept elements to this direction.
The Strength of Weak Learnability (1990) — contributed 1 concept elements to this direction.