Computable universal online learning

AI summary

Overview

• Research area: Computational learning theory, specifically the intersection of online binary classification (universal online learning) and computability theory.
• Technical level: Advanced. The paper assumes familiarity with hypothesis classes, mistake bounds, ordinal Littlestone dimension, and computability-theoretic notions such as computably enumerable (c.e.) sets, recursively enumerably representable (RER) classes, and decidably representable (DR) classes. The authors note readers may wish to consult an introductory computability textbook (Cutland, 1980) or a more advanced work (Odifreddi, 1989).
• Scope: The paper asks when universal online learning — a generalist adversarial model of online binary classification characterized by Bousquet et al. (STOC'21) — can be carried out by an actual computer program rather than by an abstract mathematical function.

What This Paper Is About

Bousquet et al. (2021) showed that a hypothesis class is universally online learnable if and only if it has an ordinal Littlestone dimension, but that guarantee only establishes the existence of a learner as a mathematical function, which may be uncomputable. This paper adds computability constraints to the framework, requiring the learner to be implementable as a computer program, and asks when such computable learners exist for realizable, agnostic, and proper variants of universal online learning. The authors restrict attention to hypotheses on the natural numbers ℕ, arguing that all practical machine learning takes place over countable domains.

Key Contributions

1. A separation between abstract and computable universal online learning. The authors show (Proposition 1) that there exists a class that is universally online learnable but not computably universally online learnable, and that such a class can even be DR (decidably representable). This contrasts with the known result that RER classes of finite Littlestone dimension are always learnable by a computable learner with a uniform mistake bound (Assos et al., 2023; Kozachinskiy and Steifer, 2024).
2. An exact characterization of agnostic learning in the computable regime. Theorem 5 gives three equivalent conditions for computable agnostic learnability, and Theorem 6 shows that computable universal online learning does not imply computable agnostic learning. Theorem 7 restores the standard equivalence between realizable and agnostic learning when attention is restricted to RER classes.
3. An exact characterization of proper learning and a separation from improper learning. Theorem 8 characterizes computably universally online learnable classes that admit a proper learner, and Theorem 9 gives an RER class that is computably universally online learnable but has no computable proper learner.
4. A computability-theoretic bridge. By requiring classes to consist of total computable functions and analyzing their closures, the paper shows that the closure of a computably universally online learnable class consists entirely of computable functions (Lemma 4), and that the closure may contain uncomputable functions even when the class itself is RER — the mechanism behind Proposition 1.

Main Findings

• Universal online learning does not imply computable universal online learning. Proposition 1 states that there exists an RER class that is universally online learnable but not computably universally online learnable; in fact, such a class can even be DR. The proof relies on the fact that even if ℋ contains only computable functions, its closure may contain uncomputable functions.
• The closure is what matters. Definition 2 introduces the closure of a class, containing all functions locally consistent with the class after finitely many steps. Lemma 2 (Closure Lemma) shows every realizable sequence is consistent with some element of the closure; Lemma 3 (Projection Lemma) shows that every element of the closure is computable for any computably universally online learnable class.
• A characterization of agnostic learnability (Theorem 5). For an arbitrary class ℋ, the following are equivalent: (1) ℋ is computably universally online learnable in the realizable setting by a total learner; (2) there exists an RER class 𝒵 such that the closure of ℋ is a subset of 𝒵; (3) ℋ is computably agnostically learnable.
• Agnostic learning is strictly harder than realizable learning in the computable regime (Theorem 6). There exists a class ℋ that is computably universally online learnable but not computably agnostically learnable. The class used in the proof is not RER. Without computability constraints, universal online learning implies agnostic learning (Hanneke et al., 2025).
• The equivalence is restored for RER classes (Theorem 7). For an RER class ℋ, the following are equivalent: ℋ is computably universally online learnable; there exists an RER class 𝒵 containing the closure of ℋ; ℋ is computably universally online learnable by a total learner.
• A characterization of proper learning (Theorem 8). For every RER class ℋ, ℋ is computably universally online learnable by a proper learner if and only if the closure of ℋ is an RER class. Here "proper" means that for every realizable sample S, the function L(S, ·) is ℋ-realizable.
• Proper learning is harder than improper learning (Theorem 9). There exists an RER class that is computably universally online learnable but has no computable proper learner. Such examples can be found even among RER classes.
• Agnostic learning uses randomized, almost total programs. A randomized program has access to random bits sampled with probability 1/2; a randomized computable function is almost total if, with probability 1, once internal randomness is fixed, the computation halts on each input. Agnostic learnability is defined via sublinear expected regret.
• Illustrative examples from the paper. The class of all singletons on ℕ is uniformly online learnable with a uniform mistake bound; the class of functions with finitely many nonzero labels is not universally online learnable; the classes of all functions with finite support, thresholds on ℕ, and thresholds on ℤ are DR and computably universally online learnable but not with a uniform mistake bound (Examples 3.8–3.10 in Bousquet et al., 2020).
• No empirical results. The paper reports no experiments, datasets, benchmarks, or quantitative performance measurements; it is a purely theoretical and proof-based contribution.

Methodology in Plain English

The authors set up an infinite game between a Learner and an Adversary. In each round the Adversary hands the Learner a natural number, the Learner predicts a binary label, and the Adversary reveals the true label. The Adversary must stay consistent with some function in a fixed hypothesis class ℋ, but is allowed to change their mind between rounds — they can switch which hypothesis they are behaving like, as long as every finite prefix of the revealed labels matches some hypothesis in ℋ. The Learner succeeds if it makes only finitely many mistakes.

To bring computability into this picture, the authors restrict to hypothesis classes containing only total computable functions and focus on RER classes — classes that can be listed by a program that enumerates programs computing exactly the functions in the class. A learner counts as computable if it can be implemented as a program (a partial function of samples and numbers to binary labels). Many learners may be undefined on non-realizable samples; such behavior is harmless for the realizable case but breaks down in the agnostic setting.

The technical work proceeds through a small set of lemmas. The Closure Lemma says that a mind-changing Adversary behaves as if they had picked a fixed function from the closure ℋ̄ in advance. The Projection Lemma, analogous to "locking sequences" from inductive inference theory (Blum and Blum, 1975), shows that under a weak correctness condition a learner's behavior on some realizable sample pins down a hypothesis from the closure — implying every element of the closure is computable (Lemma 4). For agnostic learning, the authors move to randomized learners and show how to convert an almost total randomized agnostic learner into a deterministic learner that is correct infinitely often, using a majority-vote argument plus a trick of simulating only the random advices that halt with probability 1 − (k+1)^(−2), and applying the dominated convergence theorem and Markov's inequality. For the separation results, they build adversarial classes directly — for instance, an "evil sequence" for each total learner φ_n, namely a sequence whose (n+1)-bit prefix is 0^n 1 and on which φ_n always predicts the wrong bit.

Why This Matters

• Impact on research. The paper shifts the standard theory of online binary classification from existence-based characterizations (like the ordinal Littlestone dimension) toward computationally realistic ones. It shows that some universally online learnable RER classes have no computable learner at all, that agnostic and proper learning have exact computable characterizations, and that the usual equivalence between realizable and agnostic learning survives only when restricted to RER classes. It also connects to existing work on computable analogs of PAC learning (Agarwal et al., 2020; Sterkenburg, 2022; Delle Rose et al., 2023), robust PAC learning (Gourdeau et al., 2024), uniform online learning (Hasrati and Ben-David, 2023), and inductive inference.
• Real-world applications (as motivated in the paper):
  • Predicting a large language model's generated token sequence, where the token stream is produced online and is always consistent with the set of all possible outputs of that model (Example 3).
  • Agnostic classification with small decision trees of depth 3, where perfect classification is impossible but interpretability motivates doing almost as well as the best small tree (Example 4).
  • Online binary classification on countable domains such as images or binary strings, which the authors argue is the setting in which all practical machine learning takes place.
  • Inductive inference, the related problem of inferring a function from its data, which the paper frames as sharing its questions with this framework.
• Industry relevance. The results bear on when an online prediction guarantee can actually be delivered by running code, as opposed to holding only in principle — a distinction that matters for deployment, because a claimed guarantee from an uncomputable learner cannot be realized on hardware. The paper does not report deployment studies, benchmarks, or measured savings.

Future Directions

• Characterize realizable computable universal online learning for arbitrary classes. Theorems 5 and 8 give exact characterizations for agnostic and proper learning, and Theorem 7 covers realizable learning for RER classes, but the authors state that an exact characterization for arbitrary classes remains an open problem.
• Characterize computable online learning with a uniform mistake bound. The authors raise this as a related open question and note that a recent attempt by Delle Rose et al. (2025) suggests the question may be hard.
• Measure the complexity of learners for classes without computable learners. Proposition 1 shows universally online learnable RER classes without computable learners exist and can arise in naturally occurring problems; the authors state that how complex such learners can be has a precise computability-theoretic formulation whose resolution will appear in a separate manuscript (in preparation).
• Extensions beyond the binary setting. The paper is uniquely concerned with the adversarial setting of Bousquet et al. (2020, Section 3) and with binary labels; the framework has recently been extended to multiclass classification with bandit feedback (Hanneke et al., 2025), and the paper does not report whether its computable characterizations carry over there.

Target Audience

Researchers in computational learning theory and the theory of machine learning who care about online learning, mistake bounds, and the Littlestone dimension; computability theorists and logicians working on effective mathematics, reverse mathematics, or inductive inference; and theoretically inclined graduate students or practitioners who want to know when a learning guarantee corresponds to a program that can actually be run. The paper is written to be accessible to the machine learning community, though the authors acknowledge that some background in computability theory may be needed.

Authors’ abstract

Understanding when learning is possible is a fundamental task in the theory of machine learning. However, many characterizations known from the literature deal with abstract learning as a mathematical object and ignore the crucial question: when can learning be implemented as a computer program? We address this question for universal online learning, a generalist theoretical model of online binary classification, recently characterized by Bousquet et al. (STOC'21). In this model, there is no hypothesis fixed in advance; instead, Adversary -- playing the role of Nature -- can change their mind as long as local consistency with the given class of hypotheses is maintained. We require Learner to achieve a finite number of mistakes while using a strategy that can be implemented as a computer program. We show that universal online learning does not imply computable universal online learning, even if the class of hypotheses is relatively easy from a computability-theoretic perspective. We then study the agnostic variant of computable universal online learning and provide an exact characterization of classes that are learnable in this sense. We also consider a variant of proper universal online learning and show exactly when it is possible. Together, our results give a more realistic perspective on the existing theory of online binary classification and the related problem of inductive inference.