<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

Effective Littlestone Dimension

Name: Effective Littlestone Dimension
Keywords: FOS: Computer and information sciences, Computer Science - Machine Learning, Computer Science - Logic in Computer Science, Machine Learning (cs.LG), Logic in Computer Science (cs.LO)

descriptionPublicationkeyboard_double_arrow_right Article , Preprint 01 Jan 2024Embargo end date: 01 Jan 2024Publisher:arXiv

Authors: Rose, Valentino Delle; Kozachinskiy, Alexander; Steifer, Tomasz;

doi: 10.48550/arxiv.2411.15109

arXiv: http://arxiv.org/abs/2411.15109

Effective Littlestone Dimension

- Summary
- Subjects
- Metrics

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

12 pages

Keywords

FOS: Computer and information sciences, Computer Science - Machine Learning, Computer Science - Logic in Computer Science, Machine Learning (cs.LG), Logic in Computer Science (cs.LO)

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	0
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average

Found an issue? Give us feedback

Average

Green