# Computable universal online learning

arXiv: https://arxiv.org/abs/2510.18352 · HTML: https://mlsanity.com/paper/2510.18352/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 29 references that are in the map.
- First posted on arXiv 21 Oct 2025.

## Builds on (most cited first, 9 of 9)

- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [On characterizations of learnability with computable learners](https://mlsanity.com/paper/2202.05041/) (2022)
- [On Computable Online Learning](https://mlsanity.com/paper/2302.04357/) (2023)
- [Online Learning and Solving Infinite Games with an ERM Oracle](https://mlsanity.com/paper/2307.01689/) (2023)
- [Find a witness or shatter: the landscape of computable PAC learning](https://mlsanity.com/paper/2302.04731/) (2023)
- [On the Computability of Robust PAC Learning](https://mlsanity.com/paper/2406.10161/) (2024)
- [Simple online learning with consistent oracle](https://mlsanity.com/paper/2308.08055/) (2023)
- [Effective Littlestone Dimension](https://mlsanity.com/paper/2411.15109/) (2024)
- [Contextual Bandits and Optimistically Universal Learning](https://mlsanity.com/paper/2301.00241/) (2022)

## Built on by (most cited first, 1 of 1)

- [An Order-Theoretic Characterization of Consistent Inductive Inference](https://mlsanity.com/paper/2609.28551/) (2026)

## Abstract (arXiv)

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.