# Effective Littlestone Dimension

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 11 references that are in the map.
- First posted on arXiv 22 Nov 2024.

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

- [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)

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

- [Computable universal online learning](https://mlsanity.com/paper/2510.18352/) (2025)
- [Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning](https://mlsanity.com/paper/2511.02644/) (2025)
- [Samplability makes learning easier](https://mlsanity.com/paper/2512.01276/) (2025)

## Abstract (arXiv)

Delle Rose et al.~(COLT'23) introduced an effective version of the Vapnik-Chervonenkis dimension, and showed that it characterizes improper PAC learning with total computable learners. In this paper, we introduce and study a similar effectivization of the notion of Littlestone dimension. Finite effective Littlestone dimension is a necessary condition for computable online learning but is not a sufficient one -- which we already establish for classes of the effective Littlestone dimension 2. However, the effective Littlestone dimension equals the optimal mistake bound for computable learners in two special cases: a) for classes of Littlestone dimension 1 and b) when the learner receives as additional information an upper bound on the numbers to be guessed. Interestingly, finite effective Littlestone dimension also guarantees that the class consists only of computable functions.