Computable Universal Online Learning

会议: NEURIPS2025
arXiv: 2510.18352
代码: 无（纯理论工作）
领域: others
关键词: universal online learning, computability, online binary classification, Littlestone dimension, agnostic learning, proper learning

一句话总结

在 universal online learning 框架中引入可计算性约束，证明了"数学上可学习"不等于"可用计算机程序实现的可学习"，并给出了 agnostic 和 proper 变体下可计算学习的精确刻画。

背景与动机

Universal online learning 是 Bousquet et al. (STOC'21) 提出的在线二分类理论框架。与经典的 Littlestone 设定不同，该框架不要求 uniform mistake bound——Learner 只需保证犯有限次错误（但次数可随对手策略变化）。同时 Adversary 可以动态改变目标假设（只要保持与假设类的局部一致性）。

Bousquet et al. 给出了 universal online learnability 的组合刻画：一个假设类可学习当且仅当它具有序数 Littlestone 维度。然而，该刻画中的学习器仅作为数学对象（抽象函数）存在——它可能是不可计算的，即无法被计算机程序实现。

本文的核心动机是：什么时候 universal online learning 可以由一个实际的计算机程序实现？ 这一问题在此前的文献中尚未被系统研究。

核心问题

1. 可计算性间隙：是否存在数学上 universally online learnable 但不存在可计算学习器的假设类？
2. Agnostic 学习：在可计算约束下，realizable 学习与 agnostic 学习是否仍然等价？
3. Proper 学习：在可计算约束下，何时存在 proper 学习器（输出始终属于假设类闭包）？

方法详解

基本设定

模型是一个 Learner 与 Adversary 之间的无限轮博弈。每轮 Adversary 给出 \(x \in \mathbb{N}\)，Learner 预测标签 \(\hat{y} \in \{0,1\}\)，然后 Adversary 揭示真实标签 \(y\)。Adversary 必须保持与假设类 \(\mathcal{H}\) 的局部一致性，但可以在不同轮次更换目标假设。

关键概念——闭包 \(\overline{\mathcal{H}}\)：包含所有与 \(\mathcal{H}\) 局部一致的函数。一个可换目标的 Adversary 本质上等价于事先选定一个 \(\overline{\mathcal{H}}\) 中的函数不再改变（Closure Lemma）。

主要结果一：可计算性间隙（Proposition 2）

存在 RE 表示的假设类，它 universally online learnable 但不可计算地 universally online learnable。

证明思路：利用可计算二叉树中存在不可计算无穷路径的经典结论。构造 \(\mathcal{H} = \{\sigma 0^\infty : \sigma \in T\}\)，其闭包 \(\overline{\mathcal{H}}\) 包含树 \(T\) 的所有无穷路径。由 Lemma 4（可计算学习器的闭包中所有元素必须可计算），若存在不可计算路径则不存在可计算学习器。

主要结果二：Agnostic 学习刻画（Theorem 4 系列）

给出三个等价条件：

• (1) \(\mathcal{H}\) 可被一个 total 可计算学习器在 realizable 设定下学习
• (2) 存在 RE 类 \(\mathcal{Z}\) 使得 \(\overline{\mathcal{H}} \subseteq \mathcal{Z}\)
• (3) \(\mathcal{H}\) 可计算地 agnostically learnable（达到 sublinear regret）

关键洞察：从 realizable 到 agnostic 的标准转换需要学习器在非 realizable 样本上也有定义（即 total）。而存在可计算 universal online learnable 但不可计算 agnostically learnable 的假设类（Separation Theorem）。

Separation 证明构造了一个"evil sequence"类：对每个 total 学习器 \(\varphi_n\)，构造一个唯一的序列使其犯无穷错误。该类可被 partial 学习器学习但不可被 total 学习器学习。

主要结果三：对 RE 类的统一（Theorem 4）

对 RE 类，上述间隙消失——computable universal online learning 与 agnostic learning 重新等价。证明利用了 RE 类可以可计算地枚举所有 realizable sample 的性质。

主要结果四：Proper 学习刻画（Theorem 4）

对 RE 类 \(\mathcal{H}\)：存在可计算 proper 学习器当且仅当 \(\overline{\mathcal{H}}\) 本身也是 RE 类。

同时证明存在 RE 类可计算地 universally online learnable 但不存在 proper 学习器（Separation of proper vs. improper）。构造采用优先级论证（priority argument）风格，通过逐步枚举假设来击败每个候选 proper 学习器。

实验关键数据

本文为纯理论工作，无实验。主要贡献是一系列定理和反例构造：

结果	内容
Proposition 2	存在 RE（甚至 DR）类 universally online learnable 但不可计算地学习
Theorem 4 (agnostic)	Total 可计算 realizable ⟺ RE 覆盖闭包 ⟺ 可计算 agnostic
Theorem 4 (separation)	存在可计算 realizable learnable 但不可计算 agnostically learnable 的类
Theorem 4 (RE)	对 RE 类，可计算 realizable ⟺ 可计算 agnostic
Theorem 4 (proper)	对 RE 类，可计算 proper learnable ⟺ \(\overline{\mathcal{H}}\) 是 RE
Theorem 4 (sep-proper)	存在 RE 类可计算地学习但无 proper 学习器

亮点

• 填补重要理论空白：首次系统研究 universal online learning 的可计算性，揭示了"存在性证明"与"可实现性"之间的深层差异
• 精确刻画：对 agnostic 和 proper 两个变体分别给出了充要条件，结果非常干净
• 闭包概念的核心作用：\(\overline{\mathcal{H}}\) 的可计算性质（是否可 RE 覆盖、是否本身 RE）成为可学习性的关键判据
• 与归纳推理理论的联系：Projection Lemma 类似于 Blum & Blum (1975) 的 locking sequence 概念，建立了在线学习与归纳推理之间的桥梁
• evil sequence 构造精巧：Separation Theorem 的对角化论证思路清晰，构造简洁而有力

局限性 / 可改进方向

• 仅限可数域：假设域为 \(\mathbb{N}\)，虽有实践理由但限制了理论的一般性
• 一般类的 realizable 刻画缺失：对非 RE 的一般假设类，可计算 realizable 学习的精确刻画仍是 open problem
• uniform mistake bound 的可计算刻画：相关问题被指出可能很难（Delle Rose et al., 2025）
• 缺乏计算复杂性分析：仅讨论了可计算与否，未涉及效率（如多项式时间可计算）
• 无实际应用示例：理论结果虽深刻，但未展示如何指导实际系统设计

与相关工作的对比

工作	关注点	本文区别
Bousquet et al. (STOC'21)	Universal online learning 的组合刻画	加入可计算性约束，揭示间隙
Littlestone (1988)	Uniform mistake bound（Littlestone 维度）	扩展到非 uniform 设定下的可计算性
Assos et al. (2023)	RE 类 + finite Littlestone dim → 可计算	有限维度结论不推广到无穷维度
Hasrati & Ben-David (2023)	Uniform 在线学习的可计算性	本文处理更一般的 non-uniform 情形
Delle Rose et al. (2023)	可计算 PAC 学习	不同学习框架（PAC vs online）

启发与关联

• 对可计算学习理论的研究者：闭包 \(\overline{\mathcal{H}}\) 的可计算性质是核心判据，这一观察可能推广到其他学习框架
• 对 LLM 理论：Example 3 将 LLM 的 token 生成类比为 Adversary 的行为，暗示 universal learning 框架可用于分析 LLM 的可预测性
• 对实际系统：当假设类可 RE 表示时（大多数实际假设类满足此条件），可计算性间隙消失，理论保证更强
• Total vs. partial 学习器的区分具有实际意义——partial 学习器在非法输入上可能死循环，这在实际部署中不可接受

评分

• 新颖性: ⭐⭐⭐⭐⭐
• 实验充分度: N/A（纯理论）
• 写作质量: ⭐⭐⭐⭐⭐
• 价值: ⭐⭐⭐⭐