提出可计算在线学习的有效Littlestone维数，揭示其与学习错误率的关系。
Effective Littlestone Dimension
- 定义有效Littlestone维数，用于刻画可计算在线学习的能力
- 维数为1时，其值等于最优错误次数；已知上界时也成立
- 有限有效维数保证类别中函数均为可计算函数
Delle Rose 等人（COLT'23）提出了Vapnik-Chervonenkis维数的有效版本，并证明其刻画了具有总可计算学习器的非正则PAC学习。本文引入并研究了Littlestone维数的类似有效化。有限有效Littlestone维数是可计算在线学习的必要条件，但非充分条件——我们已在有效Littlestone维数为2的学习类中确立这一点。然而，在两种特殊情况下，有效Littlestone维数等于可计算学习器的最优错误界限：a) Littlestone维数为1的类别；b) 学习者额外获得待猜测数目的上界信息。有趣的是，有限有效Littlestone维数还保证该类别仅包含可计算函数。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。