多类别学习的算法原理难以获取：正则化与适当学习的极限

# 多分类学习的算法原理难得一觅：正则化与适当学习的局限性 来源：https://arxiv.org/html/2608.26516

###### 摘要
统计学习理论中最根本的两个问题是：哪些预测问题是可以学习的？以及应该如何学习它们？对于前者，优雅的答案通常以组合维度的形式呈现，尤其是用于二元分类的VC维度和用于多分类的DS维度。后者问题则显得更为棘手：所有已知的通用多分类学习器都依赖于对指数级大小的“单包含结构”的复杂定向，而诸如适当学习和正则化等熟悉的算法原理仍鲜为人知。受先前工作启发，我们探讨学习是否可归结为适当学习——可能在更大的假设类上进行——以及适当或多分类学习是否最终能被合适的正则化所刻画。我们的主要结果对这两个问题都给出了否定回答，解决了先前工作中的三个开放问题。首先，我们展示了一个可学习的多分类问题无法嵌入任何适当可学习的类中，这意味着通过扩大假设类无法将学习归结为适当学习。其次，我们证明了适当学习可能需要训练误差，并精确地描述了这一现象：每个适当可学习的类都允许一个适当学习器在大小为m的样本上产生o(m)个错误，但对于某些适当可学习的问题，任何规定的亚线性尺度a_m = o(m)都是必要的。第三，正则化并非通用学习器：我们展示了一个适当可学习的类无法被任何结构风险最小化学习器学习，以及一个可学习的类无法被任何局部正则化器学习。我们以积极的理论补充了这些不可能性结果，该理论为SRM可学习性给出了两个充分条件，并通过显示偏好的可积性刻画了SRM可表示性。综合我们的结果，我们界定了适当学习和正则化的局限性，以及正则化成功的结构性条件。

###### 目录
1. 引言 (https://arxiv.org/html/2608.26516#S1)
   1. 结果 (https://arxiv.org/html/2608.26516#S1.SS1)
   2. 技术 (https://arxiv.org/html/2608.26516#S1.SS2)
   3. 相关工作 (https://arxiv.org/html/2608.26516#S1.SS3)
2. 预备知识 (https://arxiv.org/html/2608.26516#S2)
   1. 正则化模型 (https://arxiv.org/html/2608.26516#S2.SS1)
   2. 拓扑条件 (https://arxiv.org/html/2608.26516#S2.SS2)
3. 适当学习与非插值性 (https://arxiv.org/html/2608.26516#S3)
   1. 学习不能归结为适当学习 (https://arxiv.org/html/2608.26516#S3.SS1)
   2. 适当学习需要经验误差 (https://arxiv.org/html/2608.26516#S3.SS2)
   3. 经验非插值性的精确尺度 (https://arxiv.org/html/2608.26516#S3.SS3)
4. 全局与局部正则化的局限 (https://arxiv.org/html/2608.26516#S4)
   1. 超越加权SRM的封闭关联类 (https://arxiv.org/html/2608.26516#S4.SS1)
   2. 针对硬局部正则化的PAC反例 (https://arxiv.org/html/2608.26516#S4.SS2)
5. 结构性条件与可积性 (https://arxiv.org/html/2608.26516#S5)
   1. 后备定位 (https://arxiv.org/html/2608.26516#S5.SS1)
   2. 有序分歧复杂度 (https://arxiv.org/html/2608.26516#S5.SS2)
   3. 显示偏好的可积性 (https://arxiv.org/html/2608.26516#S5.SS3)
6. 结论 (https://arxiv.org/html/2608.26516#S6)
7. 参考文献 (https://arxiv.org/html/2608.26516#bib)
8. 附录：概率与结构性引理 (https://arxiv.org/html/2608.26516#A1)
   1. 选择轻量标记器 (https://arxiv.org/html/2608.26516#A1.SS1)
   2. 隐藏半集引理 (https://arxiv.org/html/2608.26516#A1.SS2)
   3. 射影平面关联估计 (https://arxiv.org/html/2608.26516#A1.SS3)
   4. 加权近似插值原理 (https://arxiv.org/html/2608.26516#A1.SS4)
9. 附录：经验非插值性的省略证明 (https://arxiv.org/html/2608.26516#A2)
   1. 可调下界 (https://arxiv.org/html/2608.26516#A2.SS1)
   2. 病态学习器 (https://arxiv.org/html/2608.26516#A2.SS2)

## 1 引言
设计针对可学习问题的最优、可处理学习器是统计学习理论最核心的目标之一。这样一个可学习问题由一个定义域X、标签集Y以及假设函数类H⊆Y^X来描述。学习器接收一个训练样本S = {(x_i, y_i)}_{i≤n}，其中每个x_i独立同分布地来自X上的边缘分布D，并由一个假设h*∈H标注，即y_i = h*(x_i)。学习器A的目的仅利用样本S，输出一个预测器A(S): X→Y，该预测器能以高概率正确分类一个新抽取的测试点x_test∼D。即，学习器旨在最小化L_D(A(S)) = P_{x_test∼D}(A(S)(x_test) ≠ h*(x_test))。

二元分类，即采用标签集Y={0,1}，其（最优）学习器具有简单的特征。经验风险最小化在可学习时总能学习，具有近乎最优的样本复杂度，并且仅需三个ERM学习器的简单多数表决即可达到最优速率（Aden-Ali et al., 2024 (https://arxiv.org/html/2608.26516#bib.bib1); Rawal and Zhivotovskiy, 2026 (https://arxiv.org/html/2608.26516#bib.bib9)）。或许令人惊讶的是，当Y任意时，多分类学习的格局要复杂得多。所有已知的通用多分类学习器都依赖于所谓的“单包含图”的抽象定向，这些图在训练集S的大小上可能是指数级大的，如果Y是无限的甚至可能是无限的（Brukhim et al., 2022 (https://arxiv.org/html/2608.26516#bib.bib2); Aden-Ali et al., 2023 (https://arxiv.org/html/2608.26516#bib.bib8); Pabbaraju, 2026 (https://arxiv.org/html/2608.26516#bib.bib10)）。这种对难以处理的OIG的部分依赖可以解释如下：一些自然的算法模板已被证明不适用于多分类学习。特别是，Daniely and Shalev-Shwartz (2014) (https://arxiv.org/html/2608.26516#bib.bib3) 证明了存在可学习的问题无法被任何“适当”学习器学习，即一个总是输出底层类H中函数的学习器。随后，Asilis et al. (2025b) (https://arxiv.org/html/2608.26516#bib.bib7) 展示了对于有界数量的适当学习器的任何聚合（例如3个ERM学习器的多数表决）也存在同样的失败。那么，人们如何希望能设计出一个简单的多分类学习算法框架呢？先前工作提出了两条路径。第一条是诉诸“正则化”，这是学习中最基本的算法模板之一，在理论和实践方面都取得了巨大成功。111实践上，正则化经验风险目标——最突出的是如Lasso的ℓ₁惩罚和如岭回归或权重衰减的ℓ₂惩罚——通常用于控制有效模型复杂度并鼓励泛化（Hoerl and Kennard, 1970 (https://arxiv.org/html/2608.26516#bib.bib17); Tibshirani, 1996 (https://arxiv.org/html/2608.26516#bib.bib18); Krogh and Hertz, 1991 (https://arxiv.org/html/2608.26516#bib.bib19); Hastie et al., 2009 (https://arxiv.org/html/2608.26516#bib.bib20)）。理论上，SRM已被证明刻画了非均匀可学习性（Shalev-Shwartz and Ben-David, 2014 (https://arxiv.org/html/2608.26516#bib.bib6)）。回忆一下，一个正则化器ψ: H→ℝ_{≥0}为每个假设h∈H分配一个分数，通常被认为是衡量h的“复杂度”，而“结构风险最小化”学习器则在经验风险与假设复杂度之间进行权衡，以避免过拟合。在多分类学习中，Asilis et al. (2024b) (https://arxiv.org/html/2608.26516#bib.bib4) 展示了基于“无监督局部正则化”的最优学习器。在这个框架中，学习器接收一个标注样本S={(x_i, y_i)}_{i≤n}，并仅使用其未标注的数据点(x_i)_{i≤n}来学习一个局部正则化器ψ: H×X→ℝ_{≥0}。直观地，局部正则化器ψ(h, x)衡量函数h在测试点x处的“复杂度”，这反映了假设可能在定义域的某些区域表现简单，而在其他区域表现复杂。在测试时，对于一个未标注的数据点x_test∈X，学习器进行预测：A(S)(x_test) ∈ {h(x_test): h ∈ argmin_H L̂_S(h) + ψ(h, x_test)}。注意，正则化器依赖于测试点x_test对于表达不当学习器至关重要。（直观上，它允许学习器在产生预测器时“拼接”H中的不同假设。）然而，尚不清楚局部正则化的无监督预训练阶段是否可以省略。也许学习一个分类问题所需要的只是一个适当的局部正则化器ψ: H×X→ℝ_{≥0}，它编码了定义域特定区域中假设的“复杂度”。正是这个问题最近由Asilis et al. (2024a) (https://arxiv.org/html/2608.26516#bib.bib5) 提出。

###### 开放问题 1（Asilis et al., 2024a (https://arxiv.org/html/2608.26516#bib.bib5)）
所有可学习的多分类问题H能否被一个局部正则化器学习？如果可以，是否具有（近乎）最优的样本复杂度？

第二条通往多分类学习简洁性的路径是对底层假设类H施加一个额外的假设。最自然的可能是适当可学习性，即假设H可以被学习，同时只输出H本身中的函数。在这种情况下，最雄心勃勃的目标是证明经典正则化就是所需要的全部。这个问题先前也被提出，且仍未解决。

###### 开放问题 2（Asilis et al., 2025a (https://arxiv.org/html/2608.26516#bib.bib11)）
令H是一个适当可学习的多分类问题。H是否必须能被SRM学习器学习？

让我们简要评论一下与开放问题2相关的微妙之处。在设计可学习多分类问题的不当学习器时，人们利用了一个关键事实：可学习性等同于DS维度的有限性（Brukhim et al., 2022 (https://arxiv.org/html/2608.26516#bib.bib2); Pabbaraju, 2026 (https://arxiv.org/html/2608.26516#bib.bib10)）。也就是说，H的DS维度的有限性通过H的单包含图为分析成功的学习器提供了一个重要的着手点。然而，适当可学习性本质上是一种更奇怪的存在。Asilis et al. (2025a) (https://arxiv.org/html/2608.26516#bib.bib11) 证明它不能被任何组合维度刻画，甚至在逻辑上可能是不可判定的，即独立于ZFC公理。这使得以任何方向解决开放问题2的任务变得复杂，因为仅仅建立一个假设类的适当可学习性就可能出奇地复杂（甚至是不可判定的！）。最后，现有设计为可不当学习但不可适当学习的假设类有一个奇特的共同点：只需向类中添加少量函数，它们就很容易变得适当可学习。这包括Daniely and Shalev-Shwartz (2014) (https://arxiv.org/html/2608.26516#bib.bib3) 的第一个Cantor类，以及Ben-David et al. (2019) (https://arxiv.org/html/2608.26516#bib.bib13) 的EMX学习问题，当如Asilis et al. (2025a) (https://arxiv.org/html/2608.26516#bib.bib11) 那样被视为分类问题时。这引出了一个诱人的可能性：也许所有可学习的类都可以嵌入到适当可学习的类中。

###### 开放问题 3（Asilis et al., 2025a (https://arxiv.org/html/2608.26516#bib.bib11)）
每个可学习的假设类H是否都包含在一个适当可学习的类H_prop ⊇ H中？

请注意，如果开放问题3得到肯定解决，大体上将意味着通用多分类学习可以归结为适当学习。如果它伴随着开放问题2的肯定解决，证明适当学习可以归结为SRM，那么通用多分类学习将归结为SRM！不幸的是，我们的结果表明情况并非如此乐观：即使有适当可学习性的承诺，多分类学习仍抗拒简单的算法原理。我们将在第1.1节 (https://arxiv.org/html/2608.26516#S1.SS1) 中阐述我们的不可能性结果，以及我们对SRM可学习性的刻画。

### 1.1 结果
我们的主要结果对开放问题1、2和3都给出了否定回答。我们将贡献分为三组。

- • **适当学习与非插值性**。我们首先表明，通用多分类学习不能归结为适当学习，即使扩大了学习器的输出空间。也就是说，存在一个可学习的类无法嵌入任何适当可学习的包中，从而否定了开放问题3（定理3.1）。接下来，我们构造了一个拓扑性质良好的假设类，它是适当可学习的，但无法被任何插值的适当学习器学习（定理3.6）。最后，我们对此现象给出了精确的量化描述：每个适当可学习的类都允许一个适当学习器在每个大小为m的可实现样本上产生o(m)个错误，并且对于某些适当可学习的问题，任何规定的亚线性尺度a_m = o(m)都是必要的（定理3.8和3.9）。因此，适当学习器永远不需要牺牲其训练样本的常数比例，但在亚线性范围内，基本上任何数量的错误都可能被迫产生。
- • **全局与局部正则化的局限**。我们首先证明，基于正则化的学习器即使在适当可学习的问题上也可能失败。也就是说，我们展示了一个适当可学习的类无法被任何结构风险最小化学习器学习。其次，我们展示了一个可学习的类无法被任何局部正则化器学习。