Partner: Valentino Delle Rose

University of Siena (IT)

Conference papers
1.Delle Rose V., Kozachinskiy A., Steifer T., Effective Littlestone Dimension, 36th International Conference on Algorithmic Learning Theory, 2025-02-24/02-27, Mediolan (IT), No.272:405-417, pp.1-13, 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.

Keywords:

online learning, Littlestone dimension, computability

Affiliations:
Delle Rose V.-University of Siena (IT)
Kozachinskiy A.-other affiliation
Steifer T.-IPPT PAN
2.Delle Rose V., Kozachinskiy A., Rojas C., Steifer T., Find a witness or shatter: the landscape of computable PAC learning, COLT 2023, The Thirty Sixth Annual Conference on Learning Theory, 2023-07-12/07-15, Bangalore (IN), No.195, pp.1-14, 2023
Abstract:

This paper contributes to the study of CPAC learnability—a computable version of PAC learning—by solving three open questions from recent papers. Firstly, we prove that every improperly CPAC learnable class is contained in a class which is properly CPAC learnable with polynomial sample complexity. This confirms a conjecture by Agarwal et al (COLT 2021). Secondly, we show that there exists a decidable class of hypotheses which is properly CPAC learnable, but only with uncomputably fast-growing sample complexity. This solves a question from Sterkenburg (COLT2022). Finally, we construct a decidable class of finite Littlestone dimension which is not improperly CPAC learnable, strengthening a recent result of Sterkenburg (2022) and answering a question posed by Hasrati and Ben-David (ALT 2023). Together with previous work, our results provide a complete landscape for the learnability problem in the CPAC setting

Keywords:

PAC learnability, CPAC learnability, VC dimension, Littlestone dimension, computability, foundations of machine learning

Affiliations:
Delle Rose V.-University of Siena (IT)
Kozachinskiy A.-other affiliation
Rojas C.-other affiliation
Steifer T.-IPPT PAN
3.Bienvenu L., Delle Rose V., Steifer T., Probabilistic vs deterministic gamblers, STACS 2022, 39th International Symposium on Theoretical Aspects of Computer Science, 2022-03-15/03-18, Marseille (FR), DOI: 10.4230/LIPIcs.STACS.2022.11, pp.11-1-13, 2022
Abstract:

Can a probabilistic gambler get arbitrarily rich when all deterministic gamblers fail? We study this problem in the context of algorithmic randomness, introducing a new notion – almost everywhere computable randomness. A binary sequence X is a.e. computably random if there is no probabilistic computable strategy which is total and succeeds on X for positive measure of oracles. Using the fireworks technique we construct a sequence which is partial computably random but not a.e. computably random. We also prove the separation between a.e. computable randomness and partial computable randomness, which happens exactly in the uniformly almost everywhere dominating Turing degrees.

Keywords:

algorithmic randomness, martingales, probabilistic computation, almost everywhere domination

Affiliations:
Bienvenu L.-Université de Bordeaux (FR)
Delle Rose V.-University of Siena (IT)
Steifer T.-IPPT PAN