Optimal Mistake Bounds for Transductive Online Learning

直推在线学习的最优错误界

Zachary Chase Kent State University 𝚣𝚌𝚑𝚊𝚜𝚎𝟸 ​ @ ​ 𝚔𝚎𝚗𝚝 . 𝚎𝚍𝚞 \mathtt{zchase2@kent.edu} Steve Hanneke Purdue University 𝚜𝚝𝚎𝚟𝚎 . 𝚑𝚊𝚗𝚗𝚎𝚔𝚎 ​ @ ​ 𝚐𝚖𝚊𝚒𝚕 . 𝚌𝚘𝚖 \mathtt{steve.hanneke@gmail.com} Shay Moran Departments of Mathematics, Computer Science, and Data and Decision Sciences Technion – Israel Institute of Technology; Google Research 𝚜𝚖𝚘𝚛𝚊𝚗 ​ @ ​ 𝚝𝚎𝚌𝚑𝚗𝚒𝚘𝚗 . 𝚊𝚌 . 𝚒𝚕 \mathtt{smoran@technion.ac.il} Jonathan Shafer MIT 𝚜𝚑𝚊𝚏𝚎𝚛𝚓𝚘 ​ @ ​ 𝚖𝚒𝚝 . 𝚎𝚍𝚞 \mathtt{shaferjo@mit.edu}

Abstract

摘要

We resolve a 30-year-old open problem concerning the power of unlabeled data in online learning by tightly quantifying the gap between transductive and standard online learning. In the standard setting, the optimal mistake bound is characterized by the Littlestone dimension $d$ of the concept class $\mathcal{H}$ (Littlestone 1987). We prove that in the transductive setting, the mistake bound is at least $\Omega\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$. This constitutes an exponential improvement over previous lower bounds of $\Omega\mathopen{}\left(\log\log d\right)\mathclose{}$, $\Omega\mathopen{}\left(\!\sqrt{\log d}\right)\mathclose{}$, and $\Omega\mathopen{}\left(\log d\right)\mathclose{}$, due respectively to Ben-David et al. 1995; Ben-David et al. 1997, and Hanneke et al. 2023. We also show that this lower bound is tight: for every $d$, there exists a class of Littlestone dimension $d$ with transductive mistake bound $O\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$. Our upper bound also improves upon the best known upper bound of $(2/3)\cdot d$ from Ben-David et al. 1997. These results establish a quadratic gap between transductive and standard online learning, thereby highlighting the benefit of advance access to the unlabeled instance sequence. This contrasts with the PAC setting, where transductive and standard learning exhibit similar sample complexities.

我们解决了一个历时三十年的开放问题：无标注数据在在线学习中究竟有多大力量——通过紧致刻画直推在线学习与标准在线学习之间的差距。在标准设定下，最优错误界由概念类 $\mathcal{H}$ 的 Littlestone 维 $d$ 刻画（Littlestone 1987）。我们证明：在直推设定下，错误界至少为 $\Omega\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$。这相对于先前由 Ben-David 等 1995、Ben-David 等 1997 以及 Hanneke 等 2023 给出的 $\Omega\mathopen{}\left(\log\log d\right)\mathclose{}$、$\Omega\mathopen{}\left(\!\sqrt{\log d}\right)\mathclose{}$ 与 $\Omega\mathopen{}\left(\log d\right)\mathclose{}$ 下界是指数级改进。我们还证明该下界是紧的：对每个 $d$，都存在 Littlestone 维为 $d$、且直推错误界为 $O\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$ 的概念类。我们的上界也改进了 Ben-David 等 1997 给出的当时最好上界 $(2/3)\cdot d$。这些结果确立了直推与标准在线学习之间的二次差距，从而凸显提前获知无标注实例序列的益处。这与 PAC 设定形成对照：在 PAC 中，直推学习与标准学习的样本复杂度相近。

1 Introduction

1 引言

Contents

The transductive model is a basic and well-studied framework in learning theory, dating back to the early works of Vapnik. It has been investigated both in statistical and online settings, and is motivated by the principle that to make good predictions on a specific set of test instances, one need not construct a fully general classifier that performs well on the entire domain — including points that may never actually appear. Rather, it may be sufficient to tailor predictions for a fixed, known set of instances.

目录

直推模型是学习理论中基础且研究充分的框架，可追溯到 Vapnik 的早期工作。它在统计设定与在线设定中都得到研究，其动机是：若只想在一组特定的测试实例上做出好预测，未必需要构造在整个定义域——包括那些可能永远不会出现的点——上都表现良好的完全一般分类器。针对一个固定且已知的实例集合定制预测，往往就够了。

This perspective naturally connects to a broader question in learning theory: what is the value of unlabeled data? In the transductive setting, the learner is given the sequence of unlabeled test instances in advance and is then required to predict their labels one by one. Thus, the transductive model can be viewed as a natural formalization of learning with unlabeled data: the test instances are known in advance, but their labels are not. The central question is whether such prior access to the unlabeled sequence can help reduce the number of prediction mistakes — compared to the standard online model, where the instances arrive and are labeled one at a time.

这一视角自然联系到学习理论中一个更宽的问题：无标注数据的价值是什么？在直推设定中，学习器预先获知无标注测试实例序列，再逐一预测其标签。因此，直推模型可视为「带无标注数据学习」的一种自然形式化：测试实例事先已知，但其标签未知。核心问题是：相比标准在线模型（实例逐个到达并被标注），这种对无标注序列的先验访问能否减少预测错误次数。

Recall for instance that in the standard PAC[^1] model of supervised learning, there are cases where access to unlabeled data is not helpful. Indeed, the ‘‘hard population distributions’’ used to prove the standard VC[^2] lower bound are constructed by taking a fixed and known marginal distribution over a VC-shattered set. Namely, the cases that are hardest to learn in the PAC setting include ones where the learner knows the marginal distribution over the domain, and can therefore generate as much unlabeled data as it wishes. And yet, in those cases, access to unlabeled data provides no acceleration compared to an algorithm (like ERM[^3]) that does not use unlabeled data.

回顾标准 PAC[^1] 监督学习模型：存在若干情形，无标注数据并无帮助。的确，用于证明标准 VC[^2] 下界的「困难总体分布」，是通过对一个 VC 可打散集合取固定且已知的边缘分布构造的。也就是说，PAC 中最难学的情形包含学习器已知定义域上边缘分布、因而可任意生成无标注数据的情形。即便如此，在这些情形中，使用无标注数据相对于不使用无标注数据的算法（如 ERM[^3]）并不能带来加速。

Seeing as unlabeled data is often a lot easier to obtain than labeled data, there have been considerable efforts to understand when and to what extent can access to unlabeled data accelerate learning.[^4]

鉴于无标注数据往往远比有标注数据容易获得，已有大量工作试图弄清：何时、以及在多大程度上，访问无标注数据能够加速学习。[^4]

In particular, it is natural to ask, for which plausible models of learning is access to unlabeled data beneficial? Online learning (Littlestone 1987) is perhaps the model of learning that is most-extensively studied in learning theory after the PAC model and its variants. Therefore, the general question considered in this paper is:

特别地，一个自然的问题是：在哪些合理的学习模型中，访问无标注数据是有益的？在线学习（Littlestone 1987）或许是继 PAC 及其变体之后在学习理论中被研究得最充分的模型。因此，本文考虑的一般问题是：

Question 1.

Quantitatively, how much (if at all) is access to unlabeled data beneficial for learning in the online learning setting?

问题 1。

定量地看，访问无标注数据对在线学习设定中的学习究竟有多大益处（若有的话）？

This question is naturally instantiated by comparing transductive online learning — where the learner has advance access to the full sequence $x_{1},x_{2},\dots,x_{n}$ of unlabeled instances — with standard online learning, where no such access is given. This perspective has also been adopted in prior work: for example, Kakade and Kalai 2005, Cesa-Bianchi and Shamir 2013, and Hoi et al. 2021 (Section 7.3) all describe transductive online learning as a setting in which the learner has access to “unlabeled data”. We thus refine the question above as follows:

把该问题具体化，就是比较直推在线学习——学习器可预先获知完整无标注实例序列 $x_{1},x_{2},\dots,x_{n}$——与标准在线学习——没有这种访问。先前工作也采用这一视角：例如 Kakade 与 Kalai 2005、Cesa-Bianchi 与 Shamir 2013，以及 Hoi 等 2021（第 7.3 节），都把直推在线学习描述为学习器可访问「无标注数据」的设定。我们因此把上述问题细化如下：

Question 2.

Quantitatively, how much (if at all) is learning in the transductive online learning setting easier than learning in the standard online learning setting? Specifically, how much is the optimal number of mistakes in the transductive setting smaller than in the standard setting?

问题 2。

定量地看，直推在线学习设定下的学习究竟比标准在线学习容易多少（若有的话）？具体而言，直推设定下的最优错误次数比标准设定小多少？

Addressing this question, our main result (Theorem 1.1) states that the optimal number of mistakes in the transductive setting (with access to unlabeled data) is at most quadratically smaller than in the standard setting (without unlabeled data). Furthermore, there are hypothesis classes for which a quadratic gap is achieved.

针对这一问题，我们的主要结果（定理 1.1）表明：直推设定（可访问无标注数据）下的最优错误次数，至多比标准设定（无无标注数据）小一个二次因子。并且存在实现二次差距的假设类。

1.1 Setting: Standard vs. Transductive Online Learning

1.1 设定：标准与直推在线学习

Standard online learning (Littlestone 1987) is a zero-sum, perfect- and complete-information game played over $n$ rounds between two players, a learner and an adversary. The game is played with respect to a domain set $\mathcal{X}$ and a hypothesis class $\mathcal{H}\subseteq\{0,1\}^{\mathcal{X}}$ (consisting of functions $\mathcal{X}\to\{0,1\}$), where $n$, $\mathcal{X}$ and $\mathcal{H}$ are fixed and known to both players. The game proceeds as follows.

标准在线学习（Littlestone 1987）是一个在 $n$ 轮中由两名玩家——学习器与对手——进行的零和、完全且完备信息博弈。博弈相对于定义域 $\mathcal{X}$ 与假设类 $\mathcal{H}\subseteq\{0,1\}^{\mathcal{X}}$（由函数 $\mathcal{X}\to\{0,1\}$ 组成）进行，其中 $n$、$\mathcal{X}$ 与 $\mathcal{H}$ 固定且双方已知。博弈进程如下。

For each round $t=1,2,\dots,n$:

The adversary selects an instance $x_{t}\in\mathcal{X}$ and sends it to the learner.

The learner selects a prediction $\hat{y}_{t}\in\{0,1\}$ and sends it to the adversary.

The adversary selects a label $y_{t}\in\{0,1\}$ and sends it to the learner. The selected label must be realizable, meaning that $\exists h\in\mathcal{H}~\forall i\in[t]\!:~h(x_{i})=y_{i}$.

List of games 1 The standard online learning setting.

对每一轮 $t=1,2,\dots,n$：

对手选择一个实例 $x_{t}\in\mathcal{X}$ 并发送给学习器。

学习器选择一个预测 $\hat{y}_{t}\in\{0,1\}$ 并发送给对手。

对手选择一个标签 $y_{t}\in\{0,1\}$ 并发送给学习器。所选标签必须可实现，即存在 $h\in\mathcal{H}$ 使得 $\forall i\in[t]\!:~h(x_{i})=y_{i}$。

博弈列表 1 标准在线学习设定。

The number of mistakes for a learner $L$ and an adversary $A$ is $M_{\mathsf{std}}\mathopen{}\left(\mathcal{H},n,L,A\right)\mathclose{}=\left|\left\{t\in[n]:~\hat{y}_{t}\neq y_{t}\right\}\right|$. We are interested in understanding the optimal number of mistakes, which is

学习器 $L$ 与对手 $A$ 的错误次数为 $M_{\mathsf{std}}\mathopen{}\left(\mathcal{H},n,L,A\right)\mathclose{}=\left|\left\{t\in[n]:~\hat{y}_{t}\neq y_{t}\right\}\right|$。我们关心的是最优错误次数，即

$$M_{\mathsf{std}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}=\sup_{n\in\mathbb{N}}\>\inf_{L\in\mathcal{L}}\>\sup_{A\in\mathcal{A}}\>M_{\mathsf{std}}\mathopen{}\left(\mathcal{H},n,L,A\right)\mathclose{},$$

where $\mathcal{A}$ and $\mathcal{L}$ are the set of all deterministic adversaries and learners, respectively.[^5] It is well known that $M_{\mathsf{std}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}$ is characterized by the Littlestone dimension, namely, $M_{\mathsf{std}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}=\mathsf{LD}\mathopen{}\left(\mathcal{H}\right)\mathclose{}$ (see Theorems 5.7 and 5.6).

其中 $\mathcal{A}$ 与 $\mathcal{L}$ 分别是所有确定性对手与学习器的集合。[^5] 众所周知，$M_{\mathsf{std}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}$ 由 Littlestone 维刻画，即 $M_{\mathsf{std}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}=\mathsf{LD}\mathopen{}\left(\mathcal{H}\right)\mathclose{}$（见定理 5.7 与定义 5.6）。

The transductive online learning setting (Ben-David et al. 1995; Ben-David et al. 1997) is similar, except that the learner has access to the full sequence of unlabeled instances in advance. Namely,

直推在线学习设定（Ben-David 等 1995；Ben-David 等 1997）与之类似，区别在于学习器可预先获知完整的无标注实例序列。即：

The adversary selects a sequence $x_{1},x_{2},\dots,x_{n}\in\mathcal{X}$ and sends it to the learner.

For each round $t=1,2,\dots,n$:

The learner selects a prediction $\hat{y}_{t}\in\{0,1\}$ and sends it to the adversary.

The adversary selects a label $y_{t}\in\{0,1\}$ and sends it to the learner. The selected label must be realizable, meaning that $\exists h\in\mathcal{H}~\forall i\in[t]\!:~h(x_{i})=y_{i}$.

List of games 2 The transductive online learning setting.

对手选择一个序列 $x_{1},x_{2},\dots,x_{n}\in\mathcal{X}$ 并发送给学习器。

对每一轮 $t=1,2,\dots,n$：

学习器选择一个预测 $\hat{y}_{t}\in\{0,1\}$ 并发送给对手。

对手选择一个标签 $y_{t}\in\{0,1\}$ 并发送给学习器。所选标签必须可实现，即存在 $h\in\mathcal{H}$ 使得 $\forall i\in[t]\!:~h(x_{i})=y_{i}$。

博弈列表 2 直推在线学习设定。

The optimal number of mistakes for the transductive setting is defined exactly as before,

直推设定下的最优错误次数定义与此前完全相同：

$$M_{\mathsf{tr}}\mathopen{}\left(\mathcal{H},n,L,A\right)\mathclose{}=\left|\left\{t\in[n]:~\hat{y}_{t}\neq y_{t}\right\}\right|,~~\text{and}~~M_{\mathsf{tr}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}=\sup_{n\in\mathbb{N}}\>\inf_{L\in\mathcal{L}}\>\sup_{A\in\mathcal{A}}\>M_{\mathsf{tr}}\mathopen{}\left(\mathcal{H},n,L,A\right)\mathclose{},$$

with the only difference between the standard quantity $M_{\mathsf{std}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}$ and the transductive quantity $M_{\mathsf{tr}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}$ being in how the game is defined.

标准量 $M_{\mathsf{std}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}$ 与直推量 $M_{\mathsf{tr}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}$ 之间的唯一差别，在于博弈如何定义。

1.2 Main Result

1.2 主要结果

Notice that for every hypothesis class $\mathcal{H}$, $M_{\mathsf{tr}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}\leq M_{\mathsf{std}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}$. Indeed, in the transductive setting the adversary declares the sequence $x$ at the start of the game. This reduces the number of mistakes because the transductive adversary is less powerful (it cannot adaptively alter the sequence mid-game), and also because the transductive learner is more powerful (it has more information).[^6]

注意对每个假设类 $\mathcal{H}$，都有 $M_{\mathsf{tr}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}\leq M_{\mathsf{std}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}$。的确，在直推设定中对手在博弈开始时就声明序列 $x$。这会减少错误次数，因为直推对手更弱（不能在博弈中途自适应地改序列），也因为直推学习器更强（信息更多）。[^6]

While for some classes $M_{\mathsf{tr}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}=M_{\mathsf{std}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}$, we study the largest possible separation. The best previous lower bound on $M_{\mathsf{tr}}$, due to Hanneke et al. 2023, states that for every class $\mathcal{H}$,

虽然对某些类有 $M_{\mathsf{tr}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}=M_{\mathsf{std}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}$，我们研究的是最大可能的分离。先前关于 $M_{\mathsf{tr}}$ 的最好下界由 Hanneke 等 2023 给出：对每个类 $\mathcal{H}$，

$$M_{\mathsf{tr}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}\geq\Omega\mathopen{}\left(\log d\right)\mathclose{},$$

where $d=M_{\mathsf{std}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}$. In the other direction, Ben-David et al. 1997 constructed[^7] a class $\mathcal{H}$ such that $M_{\mathsf{std}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}=d$ and

其中 $d=M_{\mathsf{std}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}$。另一方面，Ben-David 等 1997 构造[^7] 了一个类 $\mathcal{H}$，满足 $M_{\mathsf{std}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}=d$ 且

$$M_{\mathsf{tr}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}\leq\tfrac{2}{3}d.$$

This left an exponential gap between the best known lower and upper bounds on $M_{\mathsf{tr}}$, namely $\Omega(\log d)$ versus $\frac{2}{3}d$. Our main result closes this gap:

这使得关于 $M_{\mathsf{tr}}$ 的已知最好下界与上界之间留下指数级缺口，即 $\Omega(\log d)$ 对 $\frac{2}{3}d$。我们的主要结果弥合了这一缺口：

Theorem 1.1(Main result).

• • For every hypothesis class$\mathcal{H}\subseteq\{0,1\}^{\mathcal{X}}$, $$M_{\mathsf{tr}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}=\Omega\mathopen{}\left(\!\sqrt{d}\right)\mathclose{},$$ where$d=M_{\mathsf{std}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}.$

定理 1.1（主要结果）。

• • 对每个假设类$\mathcal{H}\subseteq\{0,1\}^{\mathcal{X}}$， $$M_{\mathsf{tr}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}=\Omega\mathopen{}\left(\!\sqrt{d}\right)\mathclose{},$$ 其中$d=M_{\mathsf{std}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}.$

• • On the other hand, for every$d$there exists a hypothesis class$\mathcal{H}$with$M_{\mathsf{std}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}=d$and $$M_{\mathsf{tr}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}=O\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}.$$

• • 另一方面，对每个$d$都存在假设类$\mathcal{H}$满足$M_{\mathsf{std}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}=d$且 $$M_{\mathsf{tr}}\mathopen{}\left(\mathcal{H}\right)\mathclose{}=O\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}.$$

This result is stated in considerably greater detail in Theorems 6.1 and 8.1.

该结果在定理 6.1 与定理 8.1 中有更详细的陈述。

1.3 Related Works

1.3 相关工作

The notion of transductive inference as a more efficient alternative to inductive inference in statistical learning theory was introduced by Vapnik 1979; Vapnik 2006; Gammerman et al. 1998; Chapelle et al. 1999. The online learning setting is due to Littlestone 1987, who also proved that the optimal number of mistakes is characterized by the Littlestone dimension (see Theorem 5.7).

把直推推断作为统计学习理论中相对归纳推断更高效的替代方案这一观念，由 Vapnik 1979；Vapnik 2006；Gammerman 等 1998；Chapelle 等 1999 引入。在线学习设定由 Littlestone 1987 提出，他还证明最优错误次数由 Littlestone 维刻画（见定理 5.7）。

The transductive online learning setting studied in the current paper, was first defined by Ben-David et al. 1995, who used the name worst sequence off-line model. Among other results, they showed a lower bound of $\Omega\mathopen{}\left(\log\log d\right)\mathclose{}$ on the number of mistakes required to learn a class with Littlestone dimension $d$. The authors subsequently presented an exponentially stronger lower bound of $\Omega\mathopen{}\left(\!\sqrt{\log d}\right)\mathclose{}$ in Ben-David et al. 1997. However, understanding where the optimal number of mistakes is situated within the range $\left[\Omega\mathopen{}\left(\!\sqrt{\log d}\right)\mathclose{},2d/3\right]$ remained an open question.

本文研究的直推在线学习设定最早由 Ben-David 等 1995 定义，当时称为最坏序列离线模型。除其他结果外，他们给出了学习 Littlestone 维为 $d$ 的类所需错误次数的 $\Omega\mathopen{}\left(\log\log d\right)\mathclose{}$ 下界。作者随后在 Ben-David 等 1997 中给出指数更强的 $\Omega\mathopen{}\left(\!\sqrt{\log d}\right)\mathclose{}$ 下界。然而，最优错误次数落在区间 $\left[\Omega\mathopen{}\left(\!\sqrt{\log d}\right)\mathclose{},2d/3\right]$ 中的何处，仍是开放问题。

Kakade and Kalai 2005 presented an oracle-efficient algorithm for the transductive online learning setting, and may have been the first to use that name. Their result was subsequently improved upon by Cesa-Bianchi and Shamir 2013.

Kakade 与 Kalai 2005 给出了直推在线学习设定的 oracle 高效算法，或许是最早使用该名称的工作。其结果随后由 Cesa-Bianchi 与 Shamir 2013 改进。

The present work is most similar to that of Hanneke et al. 2023 which, among other results, gave a quadratically-stronger mistake lower bound of $\Omega\mathopen{}\left(\log d\right)\mathclose{}$ for classes with Littlestone dimension $d$ in the transductive online setting. The proof of our lower bound utilizes some of their ideas, but yields a quantitative improvement by combining it with some new ideas.

与本文最接近的是 Hanneke 等 2023：除其他结果外，他们为 Littlestone 维为 $d$ 的类在直推在线设定下给出了二次更强的 $\Omega\mathopen{}\left(\log d\right)\mathclose{}$ 错误下界。我们下界的证明利用了他们的部分想法，但通过与新想法结合得到了定量改进。

Hanneke et al. 2024 studied a setting of multi-class transductive online learning where the number of possible labels is unbounded.

Hanneke 等 2024 研究了可能标签数无界的多类直推在线学习设定。

$\bullet$

(a) A perfect binary tree of depth $2$. Each node is labeled by an element of the domain $\mathcal{X}$. These labels need not be distinct (e.g., it is possible that $x_{1}=x_{6}$). $x_{0}$ is the root of the tree, $x_{0}$, $x_{1}$ and $x_{2}$ are internal nodes, and $x_{3},\dots,x_{6}$ are leaves.

$\bullet$

(a) 深度为 $2$ 的完美二叉树。每个结点由定义域 $\mathcal{X}$ 的一个元素标注。这些标注不必互异（例如可以有 $x_{1}=x_{6}$）。$x_{0}$ 是树的根，$x_{0}$、$x_{1}$ 与 $x_{2}$ 是内部结点，$x_{3},\dots,x_{6}$ 是叶子。

2 Technical Overview

2 技术概览

In this section we explain some of the main ideas in our proofs. Formal definition appear in Section 5. Full formal statements of the results, as well as detailed rigorous proofs, appear in Sections 6, 7, and 8.

本节解释证明中的若干主要想法。形式定义见第 5 节。结果的完整形式陈述与详尽严格证明见第 6、7、8 节。

2.1 Paths in Trees

2.1 树中的路径

We make extensive use of the following notion. Given a perfect binary tree ${T_{d}}$ of depth $d$, every function $f:~{T_{d}}\to\{0,1\}$ defines a unique path in the tree. The path is a sequence of nodes $\operatorname{path}\mathopen{}\left(f\right)\mathclose{}=\left(x_{i_{0}},x_{i_{1}},\dots,x_{i_{d}}\right)$, as explained in Fig. 1(c). See Section 5 for formal definitions.

我们大量使用如下概念。给定深度为 $d$ 的完美二叉树 ${T_{d}}$，每个函数 $f:~{T_{d}}\to\{0,1\}$ 在树中定义一条唯一的路径。该路径是结点序列 $\operatorname{path}\mathopen{}\left(f\right)\mathclose{}=\left(x_{i_{0}},x_{i_{1}},\dots,x_{i_{d}}\right)$，如图 1(c) 所示。形式定义见第 5 节。

2.2 Proof Ideas for the Lower Bound

2.2 下界的证明想法

We start with an elementary observation about the adversary’s dilemma in the transductive online learning setting. Before round $t$ of the game, the adversary selected a full sequence of instances $x_{1},x_{2},\dots,x_{n}\in\mathcal{X}$, and assigned some initial labels $y_{1},y_{2},\dots,y_{t-1}\in\{0,1\}$. At the start of round $t$, the adversary must consider the version space,

我们先从一个关于直推在线学习设定中对手困境的初等观察开始。在第 $t$ 轮之前，对手已选定完整实例序列 $x_{1},x_{2},\dots,x_{n}\in\mathcal{X}$，并赋给了若干初始标签 $y_{1},y_{2},\dots,y_{t-1}\in\{0,1\}$。在第 $t$ 轮开始时，对手必须考虑版本空间

$$\mathcal{H}_{t}=\big\{h\in\mathcal{H}:~\left(\forall i\in[t-1]:~h(x_{i})=y_{i}\right)\big\}.$$

If all $h\in\mathcal{H}_{t}$ assign $h(x_{t})=b$ for some $b\in\{0,1\}$, then the adversary has no choice but to assign the label $y_{t}=b$. Otherwise, the adversary can force a mistake at time $t$. Namely, after seeing the learner’s prediction $\hat{y}_{t}$, the adversary can assign $y_{t}=1-\hat{y}_{t}$, incrementing the number of learner mistakes by $1$.

若所有 $h\in\mathcal{H}_{t}$ 对某个 $b\in\{0,1\}$ 都满足 $h(x_{t})=b$，则对手别无选择，只能赋标签 $y_{t}=b$。否则，对手可以在时刻 $t$强制一次错误。即：在看到学习器的预测 $\hat{y}_{t}$ 后，对手可赋 $y_{t}=1-\hat{y}_{t}$，使学习器错误次数加 1。

But “just because you can, doesn’t mean you should”. If the adversary is greedy and forces a mistake at time $t$, they may pay dearly for that later. As an extreme example, consider the case where there is a single $h_{1}\in\mathcal{H}_{t}$ that assigns $h_{1}(x_{t})=1$, and all other functions $h\in\mathcal{H}_{t}$ assign $h(x_{t})=0$. If the learner selects $\hat{y}_{t}=1$ and the adversary forces a mistake at time $t$, the version space at all subsequent times $s>t$ will be $\mathcal{H}_{s}=\left\{h_{1}\right\}$, and the adversary will be prevented from forcing any further mistakes.

但「能做不意味着该做」。若对手贪婪地在时刻 $t$ 强制错误，日后可能付出沉重代价。极端例子：若 $\mathcal{H}_{t}$ 中仅有一个 $h_{1}$ 满足 $h_{1}(x_{t})=1$，而其余函数都赋 $h(x_{t})=0$。若学习器选 $\hat{y}_{t}=1$ 且对手在 $t$ 强制错误，则后续所有时刻 $s>t$ 的版本空间都是 $\mathcal{H}_{s}=\left\{h_{1}\right\}$，对手再也无法强制任何错误。

A natural strategy for the adversary is therefore to be greedy up to a certain limit. Namely, at each time $t$ the adversary computes the ratio[^8]

因此对手的一种自然策略是：贪婪到某个限度为止。即在每个时刻 $t$，对手计算比率[^8]

$$r_{t}=\frac{|\{h\in\mathcal{H}_{t}:~h(x_{t})=1\}|}{|\mathcal{H}_{t}|}.$$

If $r_{t}\in[\varepsilon,1-\varepsilon]$ for some parameter $\varepsilon>0$ (“the version space is not too unbalanced”), then the adversary forces a mistake. Otherwise, the adversary assigns the majority label, i.e., $y_{t}=\mathds{1}\mathopen{}\left(r_{t}\geq 1/2\right)\mathclose{}$. This ensures that the version space does not shrink too fast:

若对某个参数 $\varepsilon>0$ 有 $r_{t}\in[\varepsilon,1-\varepsilon]$（「版本空间不太不平衡」），则对手强制错误。否则对手赋多数标签，即 $y_{t}=\mathds{1}\mathopen{}\left(r_{t}\geq 1/2\right)\mathclose{}$。这保证版本空间不会收缩过快：

• • If no mistake is forced, then $|\mathcal{H}_{t+1}|\geq(1-\varepsilon)\cdot|\mathcal{H}_{t}|$, and

• • 若未强制错误，则 $|\mathcal{H}_{t+1}|\geq(1-\varepsilon)\cdot|\mathcal{H}_{t}|$，并且

• • If a mistake is forced, $|\mathcal{H}_{t+1}|\geq\varepsilon\cdot|\mathcal{H}_{t}|$.

• • 若强制了错误，则 $|\mathcal{H}_{t+1}|\geq\varepsilon\cdot|\mathcal{H}_{t}|$。

In particular, at the end of the game, the version space $\mathcal{H}_{n+1}$ is of size

特别地，博弈结束时版本空间 $\mathcal{H}_{n+1}$ 的大小满足

$$\left|\mathcal{H}_{n+1}\right|\geq\varepsilon^{M}\cdot(1-\varepsilon)^{n-M}\cdot\left|\mathcal{H}\right|\geq\varepsilon^{M}\cdot(1-\varepsilon)^{n}\cdot 2^{d}, \tag{1}$$

where $M$ is the number of mistakes that the adversary forces and $n$ is the length of the sequence. The class has size $|\mathcal{H}|\geq 2^{d}$ because $\mathsf{LD}\mathopen{}\left(\mathcal{H}\right)\mathclose{}=d$, and by removing functions from the class if necessary (which can only make learning easier), we may assume without loss of generality that $|\mathcal{H}|=2^{d}$. Namely, the class precisely shatters a Littlestone tree of depth $d-1$ such that for every assignment of labels to a root-to-leaf path in the tree, the class contains exactly one function that agrees with that assignment (see Definition 5.6 for detail).

其中 $M$ 是对手强制的错误次数，$n$ 是序列长度。因为 $\mathsf{LD}\mathopen{}\left(\mathcal{H}\right)\mathclose{}=d$，类的大小 $|\mathcal{H}|\geq 2^{d}$；必要时可从类中删去函数（这只会让学习更容易），因而可无损一般性地假定 $|\mathcal{H}|=2^{d}$。即：该类恰好打散一棵深度为 $d-1$ 的 Littlestone 树，使得对树中任一条根到叶路径上的任意标签赋值，类中恰有一个与之相符的函数（细节见定义 5.6）。

Notice that we have not yet specified how the adversary selects the sequence $x$. While the adversary’s labeling strategy is extremely simple (determined by the ratio $r_{t}$ and the prediction $\hat{y}_{t}$), constructing of the sequence $x$ requires some care, to ensure that it has the following two properties:

注意我们尚未说明对手如何选择序列 $x$。虽然对手的标注策略极其简单（由比率 $r_{t}$ 与预测 $\hat{y}_{t}$ 决定），构造序列 $x$ 却需要小心，以确保它具有以下两条性质：

• • Property I: The length $n$ of the sequence satisfies $n=2^{\Theta\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}}$, and

• • 性质 I： 序列长度 $n$ 满足 $n=2^{\Theta\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}}$，并且

• • Property II: For every sequence of predictions $\hat{y}_{1},\dots,\hat{y}_{n}$ selected by the learner, the resulting sequence of labels $y_{1},\dots,y_{n}$ selected by the adversary are consistent with some function $h\in\mathcal{H}$ such that $x$ contains all the nodes in $\operatorname{path}\mathopen{}\left(h\right)\mathclose{}$.[^9]

• • 性质 II： 对学习器所选的每一预测序列 $\hat{y}_{1},\dots,\hat{y}_{n}$，对手所得标签序列 $y_{1},\dots,y_{n}$ 都与某个 $h\in\mathcal{H}$ 一致，且 $x$ 包含 $\operatorname{path}\mathopen{}\left(h\right)\mathclose{}$ 中的全部结点。[^9]

These properties can be achieved by carefully simulating all possible execution paths of the adversary.

这些性质可通过仔细模拟对手所有可能的执行路径来达成。

Observe that if $\operatorname{path}\mathopen{}\left(h\right)\mathclose{}=\left(u_{1},\dots,u_{d}\right)$ then the sequence of labels $h(u_{1}),h(u_{2}),\dots,h(u_{d})$ uniquely identifies the function $h$ within the class $\mathcal{H}$. Hence, Property II and the assumption $|\mathcal{H}|=2^{d}$ imply that at the end of the game, the version space $\mathcal{H}_{n+1}$ has cardinality

观察到：若 $\operatorname{path}\mathopen{}\left(h\right)\mathclose{}=\left(u_{1},\dots,u_{d}\right)$，则标签序列 $h(u_{1}),h(u_{2}),\dots,h(u_{d})$ 在类 $\mathcal{H}$ 内唯一标识函数 $h$。因此，性质 II 与假定 $|\mathcal{H}|=2^{d}$ 意味着博弈结束时版本空间 $\mathcal{H}_{n+1}$ 的基数为

$$\left|\mathcal{H}_{n+1}\right|=1. \tag{2}$$

Combining Property I ($n=2^{\Theta\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}}$), Eqs. 2 and 1, and choosing $\varepsilon=2^{-\Theta\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}}$ gives

结合性质 I（$n=2^{\Theta\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}}$）、式 2 与式 1，并取 $\varepsilon=2^{-\Theta\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}}$，得到

$$1\geq\varepsilon^{M}\cdot(1-\varepsilon)^{n}\cdot 2^{d}\geq 2^{-\Theta\mathopen{}\left(M\cdot\sqrt{d}\right)\mathclose{}}\cdot 2^{d},$$

which implies

从而推出

$$M=\Omega\mathopen{}\left(\!\sqrt{d}\right)\mathclose{},$$

as desired.

此即所需。

2.3 Proof Ideas for the Upper Bound

2.3 上界的证明想法

In this section we explain the main ideas in the proof of Theorem 8.1, which states that for every $d\in\mathbb{N}$, there exists a class of Littlestone dimension $d$ that is learnable in the transductive online setting with a mistake bound of $O\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$.

本节解释定理 8.1 证明中的主要想法。该定理断言：对每个 $d\in\mathbb{N}$，都存在 Littlestone 维为 $d$ 的类，可在直推在线设定下以 $O\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$ 的错误界学习。

Of course, not every Littlestone class satisfies this property. For instance, the set of all functions $[d]\to\{0,1\}$ has Littlestone dimension $d$, but the adversary can force the learner to make $d$ mistakes when learning this class in the transductive setting.[^10] So our task in this proof is to construct a class that is especially easy to learn in the transductive setting (i.e., learnable with $O\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$ mistakes), while still being hard (requiring $d$ mistakes) in the standard setting.

当然，并非每个 Littlestone 类都满足这一性质。例如，所有函数 $[d]\to\{0,1\}$ 构成的集合 Littlestone 维为 $d$，但对手可在直推设定下迫使学习器犯 $d$ 次错误。[^10] 因此本证明的任务是：构造一个在直推设定下特别容易学（即可用 $O\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$ 次错误学会）、而在标准设定下仍然困难（需要 $d$ 次错误）的类。

2.3.1 Sparse Encodings are Easy to Guess

We start with an elementary observation. Consider the following two bit strings:

2.3.1 稀疏编码易于猜测

$$\displaystyle~110101 \\ \displaystyle~0000000000000000000000000000000000000000000000000000100000000000$$

我们从一个初等观察开始。考虑以下两个比特串：

Both of these strings encode the number $53$. However, one of the encodings is much easier to guess than the other: suppose we are tasked with guessing the bits in an encoding of an integer between $0$ and $2^{6}-1$. We guess the bits one at a time, and after each guess, an adaptive adversary tells us whether our guess was correct.

这两个串都编码数字 $53$。然而其中一个编码远比另一个容易猜：假设任务是猜测某个介于 $0$ 与 $2^{6}-1$ 之间整数的编码中的各位。我们一次猜一位，每次猜测后自适应对手告诉我们是否正确。

Now, if the bit string is a binary encoding, the task is hard. Each bit can either be $0$ or $1$, regardless of the values of the previous bits, and so the adversary can force a mistake on every bit. On the other hand, if we know that the string is a one-hot encoding, there exists an attractive strategy — always guess $0$. This ensures that we will make at most $1$ mistake.

若比特串是二进制编码，任务就难：每一位无论先前各位取值如何都可以是 $0$ 或 $1$，对手可在每一位上强制错误。反之，若已知该串是独热编码，则存在有吸引力的策略——始终猜 $0$。这保证我们至多犯 $1$ 次错误。

Note that at the end of the guessing game we have learned the same amount of information (for a number between $0$ and $2^{n}-1$, we learned $n$ bits of information), but the number of mistakes is very different ($n$ mistakes vs. $1$ mistake).

注意：猜测游戏结束时我们学到的信息量相同（对 $0$ 到 $2^{n}-1$ 之间的数，学到 $n$ 比特信息），但错误次数截然不同（$n$ 次对 $1$ 次）。

2.3.2 Construction of the Hypothesis Class

We now describe a construction of a hypothesis class that is easy to learn in the transductive setting, using the idea of a sparse encoding. Recall that a class $\mathcal{H}$ has Littlestone dimension at least $d$ (Definition 5.6 in Section 5) if there exists a Littlestone tree of depth $d-1$ such that for every $b\in\{0,1\}^{d}$ there exists $h=h_{b}\in\mathcal{H}$ such that the values on the path of $h$ agree with $b$. More formally, $\forall i\in[d]:~h(b_{<i})=b_{i}$, and in particular $\operatorname{path}\mathopen{}\left(h\right)\mathclose{}=\left(\lambda,b_{\leq 1},b_{\leq 2},b_{\leq 3},\dots,b_{\leq d-1}\right)$. Thus, when constructing a class that shatters a specific Littlestone tree of depth $d-1$, we need to define $2^{d}$ functions $\left\{h_{b}:~b\in\{0,1\}^{d}\right\}$. For each function $h_{b}$, the on-path values of the function are fixed (fully determined by $b$), while for the remaining values there is complete freedom (for the nodes $u$ that are off-path we may assign any values $h_{b}(u)\in\{0,1\}$).

2.3.2 假设类的构造

我们现在描述一个在直推设定下易于学习的假设类构造，其核心是稀疏编码的想法。回顾：若存在深度为 $d-1$ 的 Littlestone 树，使得对每个 $b\in\{0,1\}^{d}$ 都存在 $h=h_{b}\in\mathcal{H}$，其在路径上的取值与 $b$ 一致，则类 $\mathcal{H}$ 的 Littlestone 维至少为 $d$（定义 5.6，第 5 节）。更形式地，$\forall i\in[d]:~h(b_{<i})=b_{i}$，特别地 $\operatorname{path}\mathopen{}\left(h\right)\mathclose{}=\left(\lambda,b_{\leq 1},b_{\leq 2},b_{\leq 3},\dots,b_{\leq d-1}\right)$。因此，在构造打散一棵特定深度 $d-1$ 的 Littlestone 树的类时，需要定义 $2^{d}$ 个函数 $\left\{h_{b}:~b\in\{0,1\}^{d}\right\}$。对每个函数 $h_{b}$，路径上的取值是固定的（完全由 $b$ 决定），而其余取值则完全自由（对路径外结点 $u$，可任意赋 $h_{b}(u)\in\{0,1\}$）。

Perhaps the simplest way to construct a class of Littlestone dimension $d$ is simply to assign all on-path values as required, and assign $0$ to all other values. Namely, if $u$ is a prefix of $b$ then $h_{b}(u)=b_{|u|+1}$, and otherwise $h_{b}(u)=0$. In a sense, this is the ‘minimal’ class of Littlestone dimension $d$ for a specific Littlestone tree.[^11]

构造 Littlestone 维为 $d$ 的类，最简单的方式或许是：按要求赋所有路径上取值，其余一律赋 $0$。即：若 $u$ 是 $b$ 的前缀则 $h_{b}(u)=b_{|u|+1}$，否则 $h_{b}(u)=0$。在某种意义上，这是针对特定 Littlestone 树的「极小」Littlestone 维 $d$ 类。[^11]

Observe that the ‘minimal’ class does not have the desired property of being easy to learn in the transductive setting.[^12] However, a certain variation of the ‘minimal’ class that embeds a sparse encoding does satisfy the requirement. In this variation, on-path value of the function $h_{b}$ are assigned as they must (as determined by $b$), while the off-path values are sampled independently using a biased coin, such that each of them is $0$ with high probability, but has a small probability of being $1$. The probability is chosen carefully so that the class satisfies some simple combinatorial properties, as described further in Sections 2.3.6 and 8.2.

可以观察到：「极小」类并不具有「在直推设定下易学」这一期望性质。[^12] 然而，「极小」类的某种嵌入了稀疏编码的变体确实满足要求。在该变体中，$h_{b}$ 的路径上取值仍按 $b$ 必须赋的方式赋值，而路径外取值则用有偏硬币独立采样：每个以高概率为 $0$，但有小概率为 $1$。概率被仔细选取，使该类满足若干简单组合性质，细节见第 2.3.6 节与第 8.2 节。

2.3.3 Naïve Learning Strategy

We now explain in broad strokes how the probabilistic construction of the hypothesis class in Section 2.3.2 is useful for learning with few mistakes in the transductive setting.

2.3.3 朴素学习策略

我们现在粗线条地说明：第 2.3.2 节中假设类的概率构造，如何有助于在直推设定下以较少错误学习。

Notice that when predicting labels for the ‘minimal’ class with nodes in breadth-first order, the learner knows at each step whether they are labeling an on-path or off-path node, because the learner has already seen the correct labels for all ancestors of the current node. For off-path nodes, the learner knows that the true label is $0$, so it never makes mistakes on off-path nodes, but it also gains no new information when the true labels for off-path nodes are revealed. No risk, but no reward either. Instead, all the information about the true labeling function is revealed only at on-path nodes, where the adversary has complete freedom to assign labels and force mistakes. That’s why the adversary can force $d$ mistakes.

注意：当按广度优先顺序为「极小」类的结点预测标签时，学习器在每一步都知道自己在标注路径上还是路径外结点，因为当前结点所有祖先的正确标签都已见过。对路径外结点，学习器知道真标签是 $0$，因而从不在路径外结点上犯错，但路径外真标签揭晓时也不获得新信息——无风险，亦无回报。关于真标注函数的全部信息只在路径上结点揭晓，而对手在那里可完全自由赋标签并强制错误。这就是对手能强制 $d$ 次错误的原因。

For the randomly-chosen class, when predicting labels for off-path nodes, the learner may still safely predict a label of $0$. But the reasoning for this is quite different. Conceptually, every off-path label is part of a sparse codeword that identifies the correct labeling function.[^13] Because the coin is biased, each bit of the codeword is easy to guess (it is likely to be $0$), but every time that the adversary reveals that the true label for an off-path node is indeed $0$, the learner gains a small (nonzero) amount of information about the true labeling function. Additionally, when the adversary selects an off-path label of $1$, that reveals a lot of information about the true labeling function (such labels are rare in the hypothesis class), and therefore the adversary cannot force many off-path mistakes. Overall, the information about the true labeling function is ‘smeared’ throughout all labels of the tree ($0$s and $1$s, on-path and off-path).[^14]

对随机选取的类，在预测路径外结点的标签时，学习器仍可安全地预测 $0$。但理由大不相同。概念上，每个路径外标签都是识别正确标注函数的稀疏码字的一部分。[^13] 因为硬币有偏，码字的每一位都容易猜（很可能是 $0$），但每当对手揭示某个路径外结点的真标签确实是 $0$，学习器就获得关于真标注函数的少量（非零）信息。此外，当对手选择路径外标签为 $1$ 时，这揭示了大量关于真标注函数的信息（这类标签在假设类中稀少），因而对手不能强制太多路径外错误。总体而言，关于真标注函数的信息被「涂抹」在树的所有标签上（$0$ 与 $1$，路径上与路径外）。[^14]

Thus, the naïve general strategy for the learner when using the probabilistically-constructed class is to learn most of the information about the true labeling function by observing off-path labels. By the time the learner reaches an on-path node, it hopefully has already learned enough about the true labeling function in order to make a good prediction on that node.

因此，使用概率构造类时学习器的朴素一般策略是：通过观察路径外标签来学习关于真标注函数的大部分信息。待学习器到达路径上结点时，希望已经学到足够多，从而能在该结点上做出好预测。

However, making this general strategy work requires overcoming some very substantial obstacles:

然而，要使这一一般策略奏效，需要克服若干相当实质性的障碍：

1. Recall that in the transductive setting, the adversary can present the nodes of the tree in any order of its choosing — it does not have to present the tree in breadth-first order. The naïve strategy works only if the learner sees many off-path nodes before it sees most on-path nodes. But what happens if the adversary decides to present many on-path nodes near the beginning of the sequence? To handle this, the learner incorporates a strategy we call ‘danger zone minimization’, as described in Section 2.3.4.

1. 回顾：在直推设定中，对手可以按任意自选顺序呈现树的结点——不必按广度优先。朴素策略仅当学习器在见到多数路径上结点之前先见到许多路径外结点时才奏效。但若对手决定在序列开头呈现许多路径上结点会怎样？为处理这一点，学习器引入我们称为「危险区最小化」的策略，见第 2.3.4 节。

2. Another, equally problematic, issue also arises from the fact that the sequence presented by the adversary might not be in breadth-first order. Recall that breadth-first order[^15] has the property that for every node $u$ in the sequence, all the ancestors of $u$ appear before $u$ in the sequence. This means that by the time the learner needs to predict a label for $u$, the learner knows whether $u$ is on-path or off-path for the true labeling function. But what happens if the adversary presents $u$ before some of $u$’s ancestors? Or omits some of $u$’s ancestors from the sequence altogether? In this case the learner doesn’t know if $u$ is on-path or off-path, and this presents a double hazard. One hazard is that the leaner doesn’t know what label to predict for $u$ — if $u$ is off-path, the learner can simply predict $0$, but if it is on-path it must do something more elaborate. The second hazard is that, after seeing the correct label for $u$, it is not clear what the learner can infer from it. If $u$ is off-path, its label should be interpreted as part of a sparse encoding of the labeling function. But if $u$ is on-path, the interpretation must be entirely different. To overcome this challenge, the learner incorporates a strategy we call ‘splitting experts’, described in Section 2.3.5.

2. 另一个同样棘手的问题也来自对手呈现的序列可能不是广度优先。回顾：广度优先顺序[^15] 具有如下性质：对序列中每个结点 $u$，$u$ 的所有祖先都在序列中出现于 $u$ 之前。这意味着学习器需要为 $u$ 预测标签时，已知道对真标注函数而言 $u$ 在路径上还是路径外。但若对手在 $u$ 的某些祖先之前呈现 $u$，或根本从序列中省略某些祖先？此时学习器不知道 $u$ 在路径上还是路径外，从而面临双重风险。其一是不知道该为 $u$ 预测什么标签——若 $u$ 在路径外，学习器可简单预测 $0$，但若在路径上则必须做更复杂的事。其二是：见到 $u$ 的正确标签后，不清楚能从中推断什么。若 $u$ 在路径外，其标签应解释为标注函数稀疏编码的一部分；若 $u$ 在路径上，解释必须完全不同。为克服这一挑战，学习器引入我们称为「分裂专家」的策略，见第 2.3.5 节。

3. Limiting off-path mistakes. Thanks to the coin’s bias, most off-path nodes have a true label of $0$. Nonetheless, each function in the hypothesis class still has an expected number of $2^{\Omega\mathopen{}\left(d\right)\mathclose{}}$ off-path nodes labeled $1$, so the learner can afford to misclassify only a vanishing fraction of them! To limit the number of mistakes, the learner extracts information from the sparse encoding and executes a ‘transition to Halving’ strategy, as described in Section 2.3.6.

3. 限制路径外错误。得益于硬币的偏置，多数路径外结点的真标签是 $0$。尽管如此，假设类中每个函数仍期望有 $2^{\Omega\mathopen{}\left(d\right)\mathclose{}}$ 个标注为 $1$ 的路径外结点，因而学习器只能错分其中消失比例的一小部分！为限制错误次数，学习器从稀疏编码中提取信息，并执行「过渡到折半」策略，见第 2.3.6 节。

2.3.4 Danger Zone Minimization

Utilizing information from the ‘sparse encoding’ of the off-path nodes to make good predictions for on-path nodes requires that the learner first see the true labels for many off-path nodes. Until that happens, the learner expects to make many mistakes on on-path nodes. However, whether a node is on-path or off-path is not fixed in advanced — the adversary may decide this adaptively, in response to the learners predictions.

2.3.4 危险区最小化

利用路径外结点「稀疏编码」中的信息来对路径上结点做出好预测，要求学习器先见到许多路径外结点的真标签。在此之前，学习器预期会在路径上结点上犯许多错误。然而，结点在路径上还是路径外并非事先固定——对手可响应学习器的预测自适应地决定。

Danger zone minimization is a strategy used by the learner, to force the adversary to assign few nodes in the beginning of the sequence as on-path (otherwise, if initial nodes are assigned to be on-path by the adversary, then the learner will make few mistakes on those nodes). This is analogous to the standard Halving algorithm (7), but instead of minimizing the cardinality of the set of consistent hypotheses (the ‘version space’), the learner minimizes a subset of the domain (the ‘danger zone’).

危险区最小化是学习器使用的一种策略，用以迫使对手在序列开头把较少结点赋为路径上（否则，若开头结点被对手赋为路径上，则学习器在这些结点上会犯较少错误）。这类似于标准折半算法（7），但学习器最小化的不是一致假设集合（「版本空间」）的基数，而是定义域的一个子集（「危险区」）。

Concretely, at the beginning of the game the learner initializes a set $S=\left\{x_{1},x_{2},\dots,x_{t_{\mathsf{max}}}\right\}$ consisting of the first $t_{\mathsf{max}}=2^{\Omega\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}}$ instances in the sequence $x$ selected by the adversary. This set represents the ‘danger zone’ — nodes in the beginning of the sequence that have not been labeled yet, that might be on-path, and that are not ancestors of a previously-labeled on-path node.[^16] To predict a label for an instance $x_{i}$, the learner selects a label $\hat{y}_{i}$ such that if $\hat{y}_{i}$ is wrong, the danger zone will shrink by at least $1/3$. That is, for $b\in\{0,1\}$, if the set $S_{b}$ of $b$-descendants of $x_{i}$ has cardinality $|S_{b}|\geq|S|/3$, the learner predicts $\hat{y}_{i}=b$. Then, if the adversary selects $y_{i}=1-b$, that implies that all $b$-descendants of $x_{i}$ are off-path for the true labeling functions. Therefore, the learner removes all $b$-descendants of $x_{i}$ from the danger zone, and the new cardinality is $|S\setminus S_{b}|\leq(2/3)\cdot|S|$. This guarantees that the learner can make at most $O\mathopen{}\left(\log t_{\mathsf{max}}\right)\mathclose{}=O\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$ such mistakes before the danger zone is empty.[^17]

具体地，博弈开始时学习器初始化集合 $S=\left\{x_{1},x_{2},\dots,x_{t_{\mathsf{max}}}\right\}$，由对手所选序列 $x$ 的前 $t_{\mathsf{max}}=2^{\Omega\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}}$ 个实例组成。该集合表示「危险区」——序列开头尚未标注、可能在路径上、且不是先前已标注路径上结点之祖先的结点。[^16] 为实例 $x_{i}$ 预测标签时，学习器选择 $\hat{y}_{i}$，使得若 $\hat{y}_{i}$ 错误，危险区将至少缩小 $1/3$。即：对 $b\in\{0,1\}$，若 $x_{i}$ 的 $b$-后代集合 $S_{b}$ 满足 $|S_{b}|\geq|S|/3$，则学习器预测 $\hat{y}_{i}=b$。于是，若对手选 $y_{i}=1-b$，则意味着 $x_{i}$ 的所有 $b$-后代对真标注函数都在路径外。因此学习器从危险区移除所有这些 $b$-后代，新基数 $|S\setminus S_{b}|\leq(2/3)\cdot|S|$。这保证学习器在危险区变空之前至多犯 $O\mathopen{}\left(\log t_{\mathsf{max}}\right)\mathclose{}=O\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$ 次此类错误。[^17]

If neither $S_{0}$ nor $S_{1}$ have cardinality at least $|S|/3$, the learner predicts $\hat{y}_{i}=0$. If $y_{i}=1$ and $x_{i}$ is on-path for the true labeling function, then the learner updates the danger zone to be $S_{0}\cup S_{1}$,[^18] again shrinking the danger zone by a factor of at most $2/3$. Otherwise, if $y_{i}=1$ and $x_{i}$ is off-path, then it was an off-path node labeled $1$ (which is rare), and the learner can afford to misclassify it (see Section 2.3.6).

若 $S_{0}$ 与 $S_{1}$ 的基数都达不到 $|S|/3$，学习器预测 $\hat{y}_{i}=0$。若 $y_{i}=1$ 且 $x_{i}$ 对真标注函数在路径上，则学习器把危险区更新为 $S_{0}\cup S_{1}$，[^18] 再次把危险区缩小至多 $2/3$ 倍。否则，若 $y_{i}=1$ 且 $x_{i}$ 在路径外，则这是一个标注为 $1$ 的路径外结点（稀少），学习器可以承受错分它（见第 2.3.6 节）。

2.3.5 Splitting Experts

The danger zone minimization strategy requires that the learner know whether the node $u$ being classified is on-path or off-path for the true labeling function. However, if $u$ appears in the sequence before some of its ancestors, the learner does not know this. To overcome this difficulty, the learner implements a variant of the standard multiplicative weights algorithm using splitting experts. This means that initially there is a single expert executing danger zone minimization. When a node $u$ is reached for which danger zone minimization requires knowing whether $u$ is on-path or off-path and that information is not yet evident, each expert is split into two experts, one of which continues the execution of danger zone minimization under the assumption that $u$ is on-path, and the other under the opposite assumption. Thus, at each point in time, there exists precisely one expert for which all path-related assumptions are correct, and therefore that expert will make at most $O\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$ mistakes. The multiplicative weights algorithm guarantees that the overall number of mistakes will be linear in the number of mistakes of the best expert, i.e., $O\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$.

2.3.5 分裂专家

危险区最小化策略要求学习器知道正在分类的结点 $u$ 对真标注函数在路径上还是路径外。然而，若 $u$ 在其某些祖先之前出现在序列中，学习器并不知道这一点。为克服这一困难，学习器使用分裂专家实现标准乘性权重算法的一个变体。这意味着一开始只有一个专家在执行危险区最小化。当到达某个结点 $u$，危险区最小化需要知道 $u$ 在路径上还是路径外而该信息尚未明确时，每个专家分裂为两个：一个在假定 $u$ 在路径上的前提下继续危险区最小化，另一个在相反假定下继续。因此，在每个时刻，恰存在一个专家其所有路径相关假定都正确，因而该专家至多犯 $O\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$ 次错误。乘性权重算法保证总体错误次数与最佳专家的错误次数成线性关系，即 $O\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$。

2.3.6 Transition to Halving

The hypothesis class is engineered such that it satisfies the following property: there are at most $2^{O\mathopen{}\left(\sqrt{d}\right)\mathclose{}}$ functions in the hypothesis class that agree with any set of $t_{\mathsf{max}}=2^{\Omega\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}}$ labels, or that agree that a set of $\Theta\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$ nodes are all off-path and labeled $1$ (this follows from Lemma 8.2).

2.3.6 过渡到折半

假设类被设计成满足如下性质：与任意 $t_{\mathsf{max}}=2^{\Omega\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}}$ 个标签一致的函数，或一致认定某 $\Theta\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$ 个结点都在路径外且标注为 $1$ 的函数，在假设类中至多有 $2^{O\mathopen{}\left(\sqrt{d}\right)\mathclose{}}$ 个（这由引理 8.2 推出）。

Therefore, once the true labels for the first $t_{\mathsf{max}}$ instances $x_{1},x_{2},\dots,x_{t_{\mathsf{max}}}$ have been revealed, or once $\Theta\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$ off-path labels of $1$ have been revealed (whichever happens first), the learner can transition to halving: stop doing danger zone minimization, and instead predict the labels for the remaining nodes using the standard Halving algorithm (7) on the subset of the hypothesis class that survived. Halving on $2^{O\mathopen{}\left(\sqrt{d}\right)\mathclose{}}$ functions is guaranteed to make at most $O\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$ mistakes (A.1).

因此，一旦前 $t_{\mathsf{max}}$ 个实例 $x_{1},x_{2},\dots,x_{t_{\mathsf{max}}}$ 的真标签已揭晓，或一旦已揭晓 $\Theta\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$ 个路径外标签 $1$（以先发生者为准），学习器就可以过渡到折半：停止危险区最小化，转而在幸存的假设类子集上用标准折半算法（7）预测其余结点的标签。在 $2^{O\mathopen{}\left(\sqrt{d}\right)\mathclose{}}$ 个函数上折半，保证至多犯 $O\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$ 次错误（A.1）。

However, seeing as the learner lacks information on which nodes are off-path, it uses experts, and each expert maintains different path-related assumptions. Thus, each expert decides separately at which point to transition to Halving. The unique expert that makes only correct assumptions will transition ‘at the right time’. That expert will make at most $O\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$ mistakes during danger zone minimization, and then at most $O\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$ additional mistakes during halving.

然而，由于学习器缺少哪些结点在路径外的信息，它使用专家，且每个专家维护不同的路径相关假定。因此，每个专家各自决定何时过渡到折半。那个只做正确假定的唯一专家会在「正确时机」过渡。该专家在危险区最小化期间至多犯 $O\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$ 次错误，随后在折半期间再至多犯 $O\mathopen{}\left(\!\sqrt{d}\right)\mathclose{}$ 次错误。

2.4 Some Intuition for the Quantity $\sqrt{d}$

2.4 关于量 $\sqrt{d}$ 的若干直觉

We briefly sketch where the quantity $\sqrt{d}$ arises from. This is a back-of-the-envelope calculation without proof, intended purely as an aid for intuition. Suppose we assigned off-path labels of $1$ with probability $2^{-k}$ instead of $2^{-\sqrt{d}}$. Consider a sequence $x_{1},\dots,x_{n}$ of $n=d/2k$ leaves. For any sequence of labels $y_{1},\dots,y_{n}\in\{0,1\}$, taking $s=\sum_{i\in[n]}y_{i}$, there exist roughly

我们简要勾勒 $\sqrt{d}$ 这一量从何而来。这是没有证明的粗略估算，仅作直觉辅助。假设我们以概率 $2^{-k}$ 而非 $2^{-\sqrt{d}}$ 赋路径外标签 $1$。考虑由 $n=d/2k$ 片叶子组成的序列 $x_{1},\dots,x_{n}$。对任意标签序列 $y_{1},\dots,y_{n}\in\{0,1\}$，取 $s=\sum_{i\in[n]}y_{i}$，大约存在

$$2^{d}\cdot\left(2^{-k}\right)^{s}\cdot\left(1-2^{-k}\right)^{n-s}\geq 2^{d}\cdot\left(2^{-k}\right)^{n}\gg 0$$

functions in the class for which these leaves are off-path and which agree with the labels $y_{1},\dots,y_{n}$. Therefore, the adversary can force at least $n=\Omega\mathopen{}\left(d/k\right)\mathclose{}$ mistakes.

个函数使这些叶子在路径外且与标签 $y_{1},\dots,y_{n}$ 一致。因此对手至少可强制 $n=\Omega\mathopen{}\left(d/k\right)\mathclose{}$ 次错误。

Similarly, for the sequence $x_{1},\dots,x_{n}$ consisting of all the nodes in the tree of depth at most $k/2$ in breadth-first order, the adversary can force a mistake on every on-path node while assigning a label of $0$ to all off-path nodes, for a total of $k/2$ mistakes. This is true because for any assignment of on-path labels, the fraction of functions which agree with the on-path labels that assign a label of $0$ to all off-path nodes is roughly

类似地，对由深度至多 $k/2$ 的树中全部结点按广度优先组成的序列 $x_{1},\dots,x_{n}$，对手可在每个路径上结点强制错误，同时给所有路径外结点赋标签 $0$，总共 $k/2$ 次错误。这成立是因为：对任意路径上标签赋值，与路径上标签一致、且给所有路径外结点赋 $0$ 的函数所占比例大约为