论文标题
通用在线学习：乐观的通用学习规则
Universal Online Learning: an Optimistically Universal Learning Rule
论文作者
论文摘要
我们使用非i.i.d研究普遍在线学习的主题。有限损失的过程。汉纳克（Hanneke）定义了普遍一致学习的概念，以在最小化的假设下研究学习理论，在这种假设中，目的是为任何目标功能获得低长期的平均损失。我们有兴趣表征学习可能的过程以及是否存在保证的学习规则是普遍一致的，鉴于唯一可能的学习是可能的。无界损失的情况非常限制，因为可学习的过程几乎肯定会访问有限的点，因此，简单的记忆非常普遍。我们专注于有限的设置，并为承认强大而弱的通用学习的过程进行完整的表征。我们进一步表明，K-Nearest邻居算法（KNN）并非乐观地通用，并提出了1NN的新型变体，对于在强和弱环境中的一般输入和价值空间而言，这在一般的输入和价值空间上都是乐观的。这关闭了Hanneke在通用在线学习方面提出的所有小马驹2021。
We study the subject of universal online learning with non-i.i.d. processes for bounded losses. The notion of an universally consistent learning was defined by Hanneke in an effort to study learning theory under minimal assumptions, where the objective is to obtain low long-run average loss for any target function. We are interested in characterizing processes for which learning is possible and whether there exist learning rules guaranteed to be universally consistent given the only assumption that such learning is possible. The case of unbounded losses is very restrictive, since the learnable processes almost surely visit a finite number of points and as a result, simple memorization is optimistically universal. We focus on the bounded setting and give a complete characterization of the processes admitting strong and weak universal learning. We further show that k-nearest neighbor algorithm (kNN) is not optimistically universal and present a novel variant of 1NN which is optimistically universal for general input and value spaces in both strong and weak setting. This closes all COLT 2021 open problems posed by Hanneke on universal online learning.
