Effective Littlestone dimension

Valentino Delle Rose, Alexander Kozachinskiy, Tomasz Steifer
Proceedings of The 36th International Conference on Algorithmic Learning Theory, PMLR 272:405-417, 2025.

Abstract

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, a finite effective Littlestone dimension also guarantees that the class consists only of computable functions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v272-delle-rose25a, title = {Effective Littlestone dimension}, author = {Delle Rose, Valentino and Kozachinskiy, Alexander and Steifer, Tomasz}, booktitle = {Proceedings of The 36th International Conference on Algorithmic Learning Theory}, pages = {405--417}, year = {2025}, editor = {Kamath, Gautam and Loh, Po-Ling}, volume = {272}, series = {Proceedings of Machine Learning Research}, month = {24--27 Feb}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v272/main/assets/delle-rose25a/delle-rose25a.pdf}, url = {https://proceedings.mlr.press/v272/delle-rose25a.html}, abstract = {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, a finite effective Littlestone dimension also guarantees that the class consists only of computable functions. } }
Endnote
%0 Conference Paper %T Effective Littlestone dimension %A Valentino Delle Rose %A Alexander Kozachinskiy %A Tomasz Steifer %B Proceedings of The 36th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2025 %E Gautam Kamath %E Po-Ling Loh %F pmlr-v272-delle-rose25a %I PMLR %P 405--417 %U https://proceedings.mlr.press/v272/delle-rose25a.html %V 272 %X 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, a finite effective Littlestone dimension also guarantees that the class consists only of computable functions.
APA
Delle Rose, V., Kozachinskiy, A. & Steifer, T.. (2025). Effective Littlestone dimension. Proceedings of The 36th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 272:405-417 Available from https://proceedings.mlr.press/v272/delle-rose25a.html.

Related Material