# Simple online learning with consistent oracle

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 17 references that are in the map.
- First posted on arXiv 15 Aug 2023.

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

- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [Statistical Indistinguishability of Learning Algorithms](https://mlsanity.com/paper/2305.14311/) (2023)
- [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)
- [Bounds in Query Learning](https://mlsanity.com/paper/1904.10122/) (2019)
- [Finite Littlestone Dimension Implies Finite Information Complexity](https://mlsanity.com/paper/2206.13257/) (2022)
- [Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique](https://mlsanity.com/paper/2211.01443/) (2022)

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

- [Oracle-Efficient Differentially Private Learning with Public Data](https://mlsanity.com/paper/2402.09483/) (2024)
- [Effective Littlestone Dimension](https://mlsanity.com/paper/2411.15109/) (2024)
- [Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning](https://mlsanity.com/paper/2506.00135/) (2025)
- [Computable universal online learning](https://mlsanity.com/paper/2510.18352/) (2025)
- [Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning](https://mlsanity.com/paper/2605.07155/) (2026)

## Abstract (arXiv)

We consider online learning in the model where a learning algorithm can access the class only via the consistent oracle -- an oracle, that, at any moment, can give a function from the class that agrees with all examples seen so far. This model was recently considered by Assos et al.~(COLT'23). It is motivated by the fact that standard methods of online learning rely on computing the Littlestone dimension of subclasses, a computationally intractable problem. Assos et al.~gave an online learning algorithm in this model that makes at most Cd mistakes on classes of Littlestone dimension d, for some absolute unspecified constant C > 0. We give a novel algorithm that makes at most O(256d) mistakes. Our proof is significantly simpler and uses only very basic properties of the Littlestone dimension. We also show that there exists no algorithm in this model that makes less than 3d mistakes.