Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



Effective Littlestone Dimension
Indexado
Scopus SCOPUS_ID:85219169067
DOI
Año 2025
Tipo

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras


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.

Revista



Revista ISSN
2640-3498

Disciplinas de Investigación



WOS
Sin Disciplinas
Scopus
Sin Disciplinas
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



Ord. Autor Género Institución - País
1 Delle Rose, Valentino - Agenzia per la Valutazione del Sistema Universitario e Della Ricerca - Italia
2 Kozachinskiy, Alexander - Centro Nacional de Inteligencia Artificial - Chile
3 Steifer, Tomasz - Pontificia Universidad Católica de Chile - Chile
Polish Academy of Sciences - Polonia

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento



Fuente
Agencia Nacional de Investigación y Desarrollo
National Center for Artificial Intelligence CENIA

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



Agradecimiento
Kozachinskiy is funded by the National Center for Artificial Intelligence CENIA FB210017, Basal ANID, while Steifer received financial support from the Millennium Science Initiative Program - Code ICN17002 and the Agencia Nacional de Investigaci\u00F3n y Desarrollo grant no. 3230203.

Muestra la fuente de financiamiento declarada en la publicación.