Optimal Learning Under Tsybakov Noise

技术摘要：Tsybakov 噪声下的最优学习

问题陈述
本文研究了在 Tsybakov 噪声条件下，针对二分类问题的概率近似正确（PAC）学习问题。在此设定下，学习者从分布 $D$（定义在实例空间 $\mathcal{X} \times \{0, 1\}$ 上）中接收独立同分布的有标签样本。目标是从概念类 $\mathcal{H}$（其 VC 维度为 $d$）中输出一个假设 $\hat{h}$，使得其相对于贝叶斯最优分类器 $h^*_D \in \mathcal{H}$ 的超额误差最小。

Tsybakov 噪声条件推广了 Massart 噪声模型，允许标签翻转的概率在实例空间的一个子集上趋近于 $1/2$（即“最难”的噪声），前提是该子集的概率质量较小。具体而言，对于参数 $(a, \alpha)$，该条件要求：
$$P_{x \sim D_X}(|\eta_D(x) - 1/2| \le t) \le a' t^{\frac{\alpha}{1-\alpha}}$$
其中 $\eta_D(x) = P(Y=1|X=x)$ 是回归函数。参数 $\alpha \in (0, 1)$ 控制噪声水平；$\alpha$ 越小，意味着噪声分布越具有挑战性，实现了从 Massart 噪声（$\alpha \to 1$）到不可知（agnostic）设定（$\alpha \to 0$）的插值。

开放性问题
先前的工作由 Massart 和 Nédélec [MN06] 建立，证明了经验风险最小化（ERM）算法可以实现大约 $\tilde{O}((d/n)^{\frac{1}{2-\alpha}})$ 的超额风险上界，其中波浪号表示隐藏了对数因子。然而，该问题的已知极小极大（minimax）下界为 $\Omega((d/n)^{\frac{1}{2-\alpha}})$。二十年来，一个悬而未决的问题是：能否消除上界与下界之间的对数间隙，特别是，一个适当学习器（即输出结果属于原始类 $\mathcal{H}$ 的学习器）是否能够达到最优速率。

方法论：MERIT 算法
作者提出了一种名为 “Massart” 误差区域隔离法（Massart Error Regions Isolation under Tsybakov noise，简称 MERIT） 的新学习算法。其核心概念创新在于，不再统一对待整个空间，而是对实例空间 $\mathcal{X}$ 进行具有不同噪声水平的自适应划分。

1. 自适应划分： 该算法递归地隔离高噪声的“误差区域” $\Delta_t$。空间被分解为不相交的区域 $(\Delta_{t-1} \setminus \Delta_t)$ 以及最终区域 $\Delta_T$。
2. 噪声调度： 算法通过一系列噪声分辨率参数 $\beta_t$ 和剪枝阈值 $\gamma_t$ 进行操作。
   • 在区域 $(\Delta_{t-1} \setminus \Delta_t)$ 中，算法确保该分布满足类似于 Massart 噪声（或线性 Bernstein 条件）且具有特定边际参数的条件。
   • 它识别当前存续类中的假设对 $(f, g)$，这些假设对具有较大的经验不一致性（伪距离）但较低的超额风险。这些不一致性是高噪声区域的指示。
   • 算法将这些不一致区域隔离到 $\Delta_t$ 中，从而有效地从当前的学习任务中移除这些“噪声”点。
3. 通过决策列表进行适当学习：
   • 算法在每个区域 $(\Delta_{t-1} \setminus \Delta_t)$ 限制的数据上独立运行 ERM。
   • 它通过这些区域内 ERM 预测器的**决策列表聚合（decision-list aggregation）**来构建最终假设。
   • 至关重要的是，作者证明了存在原类 $\mathcal{H}$ 中的单个假设，能够同时满足所有区域的误差约束。因此，该算法返回的是一个适当学习器（即属于概念 $\mathcal{H}$ 的概念），而非仅仅是不当聚合。
4. 样本分配： 为了确保区域隔离过程与最终风险估计之间的独立性，算法仔细分配了新鲜样本 ($S_1, S_2, S_3$) 用于：
   • 估计被剪枝的概念类。
   • 估计伪距离以识别不一致区域。
   • 在隔离区域上训练最终的 ERM 预测器。

主要贡献与结果

• 解决对数间隙： 本文证明了 Tsybakov 噪声下的最优极小极大学习速率为 $\Theta((d/n + \log(1/\delta)/n)^{\frac{1}{2-\alpha}})$。这与已知的最佳下界相匹配，消除了此前基于 ERM 的上界中所存在的对数因子。
• 最优适当学习器： MERIT 算法在保持适当学习器身份的同时，达到了这一最优速率。这一点非常重要，因为在可实现（realizable）设定中，此前仅已知非适当学习器（如 Hanneke 算法 [Han16a]）能达到最优速率；而在不可知（agnostic）设定中，适当学习器（如 ERM）已知是次优的。MERIT 通过证明在 Tsybakov 噪声下适当性是可达的，弥合了这一差距。
• 技术工具： 证明依赖于精炼的一致 Bernstein 不等式（引理 15）以及对隔离区域上由 Tsybakov 噪声诱导的 Bernstein 类条件 的仔细分析。作者展示了通过自适应剪枝概念类并隔离高方差区域，可以降低每个子区域学习的有效复杂度，从而使 ERM 实现紧致的上界。

意义与主张
作者声称解决了在学习理论领域持续了二十年的著名开放问题。其主要意义在于确立了 Tsybakov 噪声下学习的统计极限，并证明了这些极限可以通过一种基于自适应区域隔离的概念简单且适当的学习策略来实现。

文中明确指出以下局限性与范围：

• 算法需要预先知道 Tsybakov 噪声参数 $(a, \alpha)$。
• 该算法是 $\delta$ 依赖的（需要预先设定置信度），不像某些最优的可实现学习器。
• 该技术并不声称能以适当学习器最优地解决不可知设定，但作者推测噪声隔离技术可以优化不可知学习中的低阶项。
• 针对特定类（如半空间 Halfspaces）的计算效率仍是一个开放问题，尽管文中引用了 [DKK+21] 关于 Tsybakov 噪声下半空间多项式时间可学习性的结果。

综上所述，这项工作通过证明 Tsybakov 噪声下的学习统计极限严格由极小极大下界定义，并且这些极限可以通过一种基于自适应区域隔离的、概念简单的适当学习策略来达到，从而提供了理论上的突破。