一句话总结

作者证明，就 Littlestone 维数 $d$d 而言，直推式在线学习的错误界下界为 $\Omega \left( { \sqrt { d } } \right)$Ω(d​)，并且上界 $O \left( { \sqrt { d } } \right)$O(d​) 是紧确的，这解决了长达 30 年的公开问题，并在直推式在线学习与标准在线学习之间确立了平方级差距。

核心贡献

• 对于每个 Littlestone 维数为 d 的概念类，证明直推式在线学习错误界的下界为 Ω(√d)，改进了此前 Ω(log log d)、Ω(√log d) 和 Ω(log d) 的下界。

• 建立匹配上界：对每个 d，构造一个 Littlestone 维数为 d 且直推式错误界为 O(√d) 的概念类，改进了此前最好的上界 (2/3)d。

• 上下界共同确立直推式在线学习与标准在线学习之间的平方级差距，表明提前获得无标签实例序列能带来优势，并与 PAC 设置中直推式复杂度和标准复杂度相当的情况形成对比。

引言

在线学习中，标准模型假设学习器一次接收一个实例，而直推式模型提前把学习器需要的全部无标签测试实例序列交给学习器。其重要性在于，无标签数据通常比有标签数据容易获得得多，因此理解这种提前信息何时真正降低预测误差是学习理论的核心问题。

早期工作已证明直推式在线学习可能比标准在线学习更容易，但量化差距仍未解决。最好的已知界显示常量因子级别的大分离，而最强下界相对于标准最优错误数只有对数级别，使真实分离中存在指数级差距。

作者通过证明平方级分离弥合该差距。如果假设类的标准最优错误界为 d，那么其在直推式设置中的最优错误界至少为 Omega(sqrt(d))。作者还构造了直推式错误界为 O(sqrt(d)) 的类，表明该分离在常量因子意义下是紧确的。

方法

作者围绕在线学习的二叉树表示展开分析。对于深度为 $d$d 的完全二叉树 $T_d$Td​，每个标记函数 $f: T_d \to \{0,1\}$f:Td​→{0,1} 都确定树中的一条唯一路径。从根开始，该路径沿对应于当前函数值的子节点前进。因此，若当前节点取值为 $0$0，路径移动到 $0$0-子节点，若取值为 $1$1，则移动到 $1$1-子节点。这一概念之所以核心，是因为在深度为 $d$d 的破碎 Littlestone 树中，一条从根到叶的路径唯一标识假设类中的一个函数。

下界论证被组织成两部分对抗策略。对抗者选择一长串定义域实例，并在观察学习器的预测后自适应选择标签。在每一轮 $t$t 之前，学习器已在较早实例上给出预测，而对抗者维护假设空间

$$\mathcal{H}_t=\left\{h\in\mathcal{H}: \forall i\in[t-1],\ h(x_i)=y_i\right\}.$$Ht​={h∈H:∀i∈[t−1], h(xi​)=yi​}.

若 $\mathcal{H}_t$Ht​ 中的所有假设都对当前实例 $x_t$xt​ 指派相同标签，那么对抗者必须使用该标签。否则，在观察学习器的预测 $\hat{y}_t$y^​t​ 之后，对抗者可以选择 $y_t=1-\hat{y}_t$yt​=1−y^​t​，从而迫使一次错误。

关键洞见是，立即迫使错误可能会太快压缩假设空间，并消灭未来迫使更多错误的机会。为了控制这一点，对抗者使用一个平衡参数

$$r_t=\frac{\left|\{h\in\mathcal{H}_t:h(x_t)=1\}\right|}{|\mathcal{H}_t|}.$$rt​=∣Ht​∣∣{h∈Ht​:h(xt​)=1}∣​.

如果 $r_t\in[\varepsilon,1-\varepsilon]$rt​∈[ε,1−ε]，对抗者迫使一次错误。如果 $r_t$rt​ 位于该区间之外，对抗者指派多数标签。这可以防止假设空间快速收缩。如果未迫使错误，则

$$|\mathcal{H}_{t+1}|\ge (1-\varepsilon)|\mathcal{H}_t|,$$∣Ht+1​∣≥(1−ε)∣Ht​∣,

而如果迫使错误，则

$$|\mathcal{H}_{t+1}|\ge \varepsilon|\mathcal{H}_t|.$$∣Ht+1​∣≥ε∣Ht​∣.

在 $n$n 轮和 $M$M 次被迫错误之后，得到

$$|\mathcal{H}_{n+1}|\ge \varepsilon^M(1-\varepsilon)^{n-M}|\mathcal{H}| \ge \varepsilon^M(1-\varepsilon)^n2^d.$$∣Hn+1​∣≥εM(1−ε)n−M∣H∣≥εM(1−ε)n2d.

随后，对抗者构造序列，使 $n=2^{\Theta(\sqrt{d})}$n=2Θ(d​)，并使最终假设空间仍包含路径完全由该序列表示的函数。选择 $\varepsilon=2^{-\Theta(\sqrt{d})}$ε=2−Θ(d​) 给出

$$1\ge 2^{-\Theta(M\sqrt{d})}\cdot 2^d,$$1≥2−Θ(Md​)⋅2d,

这意味着

$$M=\Omega(\sqrt{d}).$$M=Ω(d​).

对于上界构造，作者设计了一个在直推式设置中仅用 $O(\sqrt{d})$O(d​) 次错误即可学习的假设类，尽管它仍然具有 Littlestone 维数 $d$d。构造从一个规范的“最小”类开始，其中每条从根到叶路径上的标签被固定，用于编码 $2^d$2d 个函数之一，而所有非路径节点都标记为 $0$0。这个最小类对直推式设置来说太难，因为学习器无法从非路径节点学到任何东西，所有信息都只来自对抗者控制的路径节点。

为了让该类更容易学习，作者将确定性非路径标签替换为稀疏随机标签。路径上的标签仍由路径编码固定，而非路径标签从一个有偏硬币中采样。每个非路径节点以高概率标记为 $0$0，以较小概率标记为 $1$1，大致为 $2^{-\sqrt{d}}$2−d​。从概念上讲，非路径标签构成一个稀疏码字，用于标识真实标记函数。由于该码字稀疏，大多数比特容易猜测，因为 $0$0 很可能是标签。当罕见的 $1$1 出现时，它会披露关于真实函数的大量信息。因此，关于隐藏标记函数的信息分布在路径节点和非路径节点中，而不是仅集中在路径节点上。

学习算法围绕三个耦合模块组织。第一个是危险区域最小化模块。在直推式设置中，对抗者可能以任意顺序揭示节点，早期揭示的节点最终可能被证明在路径上。在学习器观察足够多的非路径标签之前，它缺乏足够信息来准确预测路径标签。因此，学习器维护一个危险区域 $S$S，将其初始化为序列中前 $t_{\max}=2^{\Omega(\sqrt{d})}$tmax​=2Ω(d​) 个实例。这些可能是真实函数仍在路径上的早期节点。为了预测实例 $x_i$xi​ 的标签，学习器检查对应标签 $0$0 和 $1$1 的后代子集 $S_0$S0​ 与 $S_1$S1​。如果对某个 $b\in\{0,1\}$b∈{0,1}，集合 $S_b$Sb​ 的大小至少为 $|S|/3$∣S∣/3，学习器预测 $b$b。如果该预测错误，那么 $x_i$xi​ 的所有 $b$b-后代都必须是非路径节点，于是学习器将它们从危险区域移除。这至少将危险区域缩小一个常量因子。重复这一论证可知，此类错误至多 $O(\log t_{\max})=O(\sqrt{d})$O(logtmax​)=O(d​) 次。

第二个模块处理由非广度优先呈现顺序引起的不确定性。在广度优先顺序中，每个节点的每个祖先都出现在该节点之前，因此学习器可以确定该节点是否在路径上。然而在直推式设置中，节点可能出现在某些祖先之前，或某些祖先可能永远不出现。在这种情况下，学习器无法知道一个节点属于路径编码还是稀疏非路径编码。为处理这一点，作者实现了基于乘性权重的拆分专家机制。当一个节点需要知道它是否在路径上时，每个当前专家会拆分为两个专家：一个假设该节点在路径上，另一个假设该节点不在路径上。任意时刻，总有一个专家的假设全局正确。乘性权重策略保证整体学习器产生的错误数量与这个最优专家相当，即 $O(\sqrt{d})$O(d​)。

第三个模块是向 Halving 的过渡。随机构造经过调节，使得在观察前 $t_{\max}=2^{\Omega(\sqrt{d})}$tmax​=2Ω(d​) 个真实标签之后，或在观察 $\Theta(\sqrt{d})$Θ(d​) 个值为 $1$1 的非路径标签之后，与观测一致且仍存活的假设集合大小至多为 $2^{O(\sqrt{d})}$2O(d​)。此时，学习器停止使用危险区域最小化，而改为在假设类的存活子集上运行标准 Halving 算法。在 $2^{O(\sqrt{d})}$2O(d​) 个函数上运行 Halving 算法会产生至多 $O(\sqrt{d})$O(d​) 次额外错误。由于学习器使用具有不同路径假设的专家，每个专家可以独立决定何时转向 Halving。具有正确路径假设的唯一专家会在正确时刻转向 Halving，因此其总错误数保持在 $O(\sqrt{d})$O(d​) 内。

稀疏标记概率指数 $\sqrt{d}$d​ 的选择反映了两类困难之间的权衡。如果非路径节点以概率 $2^{-k}$2−k 标记为 $1$1，那么长度为 $n=d/(2k)$n=d/(2k) 的叶节点序列可由对抗者用于迫使大约 $\Omega(d/k)$Ω(d/k) 次错误，因为许多稀疏标签模式仍与不同函数一致。同时，如果对抗者以广度优先顺序呈现树的上层，它可以在许多路径节点上迫使错误，从而给出一个量级为 $k$k 的项。由此产生的错误下界形如 $\Omega(d/k+k)$Ω(d/k+k)，当 $k$k 接近 $\sqrt{d}$d​ 时达到最优。因此，作者将稀疏编码偏差选择为 $2^{-\sqrt{d}}$2−d​ 量级，使非路径节点提供的信息足以标识函数，同时使罕见的非路径错误数量足够少，以保持 $O(\sqrt{d})$O(d​) 错误界。