🤖 machine learning

Constrained Learning with Universally Learnable Concept Classes

本文通过在通用再生核希尔伯特空间（RKHS）框架下调和泛化性与拉格朗日对偶性，并引入闭包-实现间隙（closure-realization gap）来表征对偶算法的精确或近近似概率近似约束可行性（PACC）可行性，确立了无限维非凸假设类下约束统计学习问题解的普遍可学习性。

原作者： Herlock SeyedAbolfazl Rahimi, Spyridon Pougkakiotis, Dionysis Kalogerias

发布于 2026-08-11

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Herlock SeyedAbolfazl Rahimi, Spyridon Pougkakiotis, Dionysis Kalogerias

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

伟大的平衡术：当 AI 需要遵守规则时

想象一下，你正在教一个机器人玩电子游戏。你的目标很简单：获得尽可能高的分数。但有一个限制条件：游戏有严格的规则——机器人不能撞到墙，不能耗尽燃料，并且必须在特定的时间限制内完成。在机器学习的世界里，这被称为约束学习（constrained learning）。这里的“分数”是预测准确度，而“规则”则是安全性、公平性或隐私要求。

长期以来，科学家们认为教机器人学习这些规则的最佳方法是让游戏变得简单且可预测（数学上称为“凸”的/convex）。在一个简单的游戏中，你可以轻松找到一条既能获得最高分又能遵守所有规则的完美路径。但现代 AI（例如驱动自动驾驶汽车或医疗诊断的深度神经网络）所处的游戏极其复杂，充满了转折与变化（数学上称为“非凸”的/non-convex）。这就像是在一个墙壁会移动、地板是果冻材质的迷宫中导航。

当你试图将旧的、简单的规则应用于这个复杂的迷宫时，事情就会出错。计算机可能会找到一条在纸面上看起来很棒、但实际上会导致汽车撞毁的路径；或者它可能找到了一条完全遵守规则但得分却为零的路径。科学家们一直在问一个大问题：我们能否教这些超级聪明、复杂的 AI 系统既能出色地完成工作，又能完美地服从规则，而无需简化它们所生活的世界？

论文的核心思想：“无限图书馆”妙招

这篇题为《具有通用可学习概念类的约束学习》（Constrained Learning with Universally Learnable Concept Classes）的论文解决了这个问题。作者 Herlock Rahimi、Spyridon Pougkakiotis 和 Dionysis Kalogerias 提出了一种巧妙的新型 AI 训练方法，即使在规则复杂且 AI 极其复杂的情况下也同样有效。

以下是通过一个简单的类比讲述他们发现的过程。

问题所在：“太大”与“太小”的困境

想象一下，你正试图在一座巨大的、无限的图书馆中寻找隐藏的宝藏。

“太大”的图书馆： 如果你在整个无限大的图书馆中寻找（其中包含了每一本可能存在的书，包括毫无意义的书），你肯定能找到完美的藏宝图。然而，图书馆实在太大了，你可能要花上一辈子去搜寻，却永远找不到你需要的那本书。你有潜力找到答案，但你无法在合理的时间内证明你找到了它。
“太小”的图书馆： 如果你在一个微小且易于管理的区域（比如仅仅是“烹饪”分类区）寻找，你可以很快找到一本书。但完美的藏宝图可能根本不在“烹饪”分类区。你可能找到了一份汤的食谱，但你原本需要的是一张通往黄金的地图。

以往解决此类问题的尝试都迫使 AI 在两者之间做出选择。如果它们选择了微小的图书馆，就会错过最佳方案；如果选择了巨大的图书馆，则无法证明自己找到了正确答案。

解决方案：“不断增长的书架”策略

作者提出了一个精妙的策略：从小处着手，但保持增长。

想象你有一个神奇的书架，它最初只有一本书。你搜索它。如果没找到宝藏，你就神奇地在书架上增加几本书。你再次搜索。然后你再增加一些。你不断重复这个过程，慢慢扩大你的搜索范围。

为什么有效： 因为你从小处着手，你可以证明你的搜索是高效且可靠的（你不会在废话上浪费时间）。
为什么强大： 因为你不断增长，你最终会覆盖整个无限大的图书馆。你保证最终能找到那张完美的藏宝图，而不会在整个图书馆的混乱中迷失方向。

在论文的语言中，他们使用了一个“通用再生核希尔伯特空间”（Universal Reproducing Kernel Hilbert Space，一个非常具有表达力的数学库名称），并在随着计算机看到更多数据而不断扩大的“范数球”（norm balls，即书架）中进行搜索。

规则中的“间隙”

这里有一个棘手的转折。即使有了这个不断增长的书架，作者发现有时所谓的“完美”解并不可能以单本清晰的书籍形式存在。有时，规则如此复杂，以至于“完美”的解其实是许多不同书籍的混合体，没有任何单本书籍能完美代表这种混合。

他们称之为**“闭包-实现间隙”（Closure–Realization Gap）**。

如果间隙为零： AI 会找到一本遵守规则且得分最高的单本完美之书。这发生在规则是“平滑”且表现良好的情况下（具体而言，当对偶几何是良性的，例如当对偶函数是可微的时）。在这种情况下，解是**精确可行（exactly feasible）**的。
如果间隙不为零： AI 会找到一本“几乎完美”的书。它可能会以一个微小的、固定的量违反规则，且无论你给 AI 提供多少数据，这个量都无法消除。作者证明了这种微小的错误并非 AI 或数学的失败，而是问题本身的一个基本且不可改变的属性。这就像试图用一支方形铅笔画出一个完美的圆圈；并不是铅笔不好，而是形状本身无法完美契合，且误差的大小正好等于铅笔棱角的尺寸。

他们的证明

论文不仅仅是建议这可能奏效，而是通过数学进行了证明。

精确值： 他们证明了即使在这个复杂的非凸世界中，AI 也能学习到精确的最佳得分。
可行性： 他们证明了 AI 可以找到一个遵守规则的解。至关重要的是，如果问题的几何结构是“良性”的（间隙为零），则解是完全可行的。 如果几何结构是“非良性”的（间隙不为零），则解会带有一个特定的、非零的误差限度，而这个限度是问题内在的，而非算法的局限。
没有捷径： 他们证明了你不能仅仅假设规则是简单的（凸的）来简化数学计算。这种复杂性是真实存在的，而他们的方法是处理这种复杂性且不丢失寻找答案保证的唯一途径。

为什么这很重要

这是一件大事，因为它为我们构建既强大又安全的 AI 提供了一条路径。无论是决定谁能获得贷款的 AI（公平性）、驾驶汽车的机器人（安全性），还是诊断患者的医疗 AI（准确性），我们都需要它们遵守严格的规则。这篇论文表明，我们不必在“聪明”和“安全”之间做选择。只要我们使用正确的“不断增长的书架”策略来教学，我们就可以两者兼得。

作者谨慎地指出，虽然数学逻辑是稳固的，但将此转化为能在手机上运行的现实世界软件工具是下一步工作。但理论基础已经奠定：是的，我们可以教复杂的 AI 完美地遵守规则（如果问题允许）；或者如果规则本质上很棘手，也可以教它们尽可能完美地遵守规则，并拥有一个已知的、固定的误差极限。

技术摘要：具有通用可学习概念类的受限学习

1. 问题设定

本文研究了在全非凸设定下，针对无限维假设类进行的受限统计学习。目标是在满足 $m$ 个约束 $R_i(\phi) \leq 0$ （对于 $i=1,\dots,m$ ）的情况下，最小化主预测风险 $R_0(\phi)$ ，其中风险是不同数据分布 $D_i$ 下潜在非凸损失泛函的期望。

核心难点在于实现可行学习理论的两个要求之间存在结构性张力：

强对偶性（总体层面）： 为了保证拉格朗日对偶问题能够忠实地表征原约束问题（零对偶间隙），假设类必须是可分解的（在可测拼接下封闭）。这一性质与向量测度的 Lyapunov 凸性相关，它确保了即使单个泛函不是凸的，可实现的风险向量集也是凸的。然而，可分解空间（如 $L_p$ 空间）过于庞大，无法从有限数据中获得统计泛化保证（即消失的 Rademacher 复杂度）。
统计泛化能力（经验层面）： 为了确保从有限样本中可学习，假设类必须具有受控的统计复杂度（例如，衰减的 Rademacher 复杂度）。标准的再生核希尔伯特空间（RKHS）范数球虽然满足这一点，但它们不是可分解的，这导致了不可消除的近似误差（近 PACC 结果），即无论样本量如何增加，约束违反都无法趋于零。

现有方法通常通过使用单一的有限复杂度类来折衷，从而导致带有无法随数据量消失的残差的“近 PACC”保证。本文旨在解决这种张力，以实现精确或近精确的可学习性，而不引入此类不可消除的残差。

2. 方法论

作者提出了一个使用稠密 RKHS 类和对偶经验风险最小化（DERM）的变复杂度框架。

基于通用 RKHS 的总体问题： 总体约束问题是在一个与可分解包络空间 $\mathcal{G}$ （例如 $L_p$ 空间）稠密的通用 RKHS $\mathcal{H}_K$ 上定义的。虽然 $\mathcal{H}_K$ 本身不是可分解的，但其在 $\mathcal{G}$ 中的稠密性允许通过连续性论证将 $\mathcal{G}$ 的强对偶性质传递给 $\mathcal{H}_K$ 。
具有增长范数球的经验问题： 学习者在一个序列化的闭范数球 $B_{Q_n} = \{f \in \mathcal{H}_K : \|f\|_{\mathcal{H}_K} \leq Q_n\}$ $B_{Q_{n}} = {f \in H_{K} : ∥ f ∥_{H_{K}} \leq Q_{n}}$ 上运行，其中半径 $Q_n$ $Q_{n}$ 随样本量 $n$ $n$ 增长，满足 $Q_n \to \infty$ $Q_{n} \to \infty$ 但 $Q_n/\sqrt{n} \to 0$ $Q_{n} / n \to 0$ 。
- 这确保了搜索空间最终耗尽 RKHS（捕捉到总体解）。
- 同时，范数球 $B_{Q_n}$ 的统计复杂度（Rademacher 复杂度）以 $O(Q_n/\sqrt{n})$ 的速度消失，确保了一致收敛。
DERM 算法： 学习者在非负乘子上最大化经验对偶函数，然后在当前的球 $B_{Q_n}$ 上最小化经验拉格朗日函数。
可行性分析： 由于非凸性阻止了拉格朗日函数达到其下确界，或者无法保证单个预测器能实现对偶次梯度，作者引入了闭包–实现间隙 $\varepsilon^\star_\infty$ 。这个几何常数衡量了对偶函数的超微分与由 RKHS 内预测器所能实现的风险向量集合之间的距离。

3. 核心贡献

1. 通用（近）PACC 可学习性：
本文确立了**不可知通用概率近似正确且满足约束（PACC）**的可学习性。不同于无分布限制的 PAC 学习，这里的样本复杂度允许依赖于底层分布（具体通过 Slater 边际和 Tikhonov 复杂度），作者认为由于 RKHS 的高表达能力，这是必要的。

精确可学习性： 当 $\varepsilon^\star_\infty = 0$ 时（例如在对偶可微条件下），学习者实现精确的可行性和最优性。
近 PACC 可学习性： 当 $\varepsilon^\star_\infty > 0$ 时，学习者在恰好等于 $\varepsilon^\star_\infty$ 的残差范围内实现最优性和可行性。至关重要的是，该残差是问题几何结构的内在属性，而非固定建模选择的产物，并且在良性条件下会消失。

2. 无需原问题达成的可行性证书：
在完全非凸的机制下，约束原问题可能不存在达成的解。本文证明了即使在不存在原问题极小值者的假设下，DERM 输出也是渐近可行且近优的（至多偏差为 $\varepsilon^\star_\infty$ ）。这是通过对偶侧的变分论证实现的，利用了对偶函数的 Levin–Valadier 表示法。

3. 显式的统计速率：
作者推导出了学习最优值的显式多项式样本阈值。他们引入了 Tikhonov 复杂度 $T^\varepsilon_n$ ，定义为达到 $\varepsilon$ -最优拉格朗日水平集的最小 RKHS 范数。在正则化路径满足标准源条件（source condition）的情况下，他们证明了 $T^\varepsilon_n$ 是有限的，并推导出样本复杂度为 $O(\varepsilon^{-\max\{4, 2(1-\beta)/\beta\}})$ ，其中 $\beta$ 表征了源条件。

4. 通用框架的必要性：
本文证明，在其设定的无约束特例中，由于通用 RKHS 的无界容量，不存在无分布限制的样本阈值。因此，通用学习框架（其速率依赖于分布）不仅是方便的，而且是规范的，适用于大假设类上的对偶算法。

4. 主要结果

定理 1： 确立了在具有增长范数球的稠密 RKHS 上的 DERM 是通用 PACC 可学习的。
- (i) 最优值的精确可学习性及其显式阈值。
- (ii)–(v) 由闭包–实现间隙 $\varepsilon^\star_\infty$ 控制的可行性和近优性保证。
- (vi) 当 $\varepsilon^\star_\infty = 0$ 时，实现精确 PACC 可学习性。
推论 1： 在源条件下提供了显式的多项式样本复杂度界限。
引理 1： 表征了闭包–实现间隙，表明如果对偶函数在最优处可微，则该间隙消失。

5. 意义与主张

本文声称解决了总体层面的强对偶性（需要可分解性）与有限样本泛化能力（需要低复杂度）之间的基本结构性张力。通过利用通用 RKHS 在可分解包络中的稠密性，作者展示了可以在保持统计控制（通过范数球限制）的同时，继承大空间的精确对偶性质。

其意义在于超越了带有不可消除残差的“近 PACC”结果。本文认为，先前的残差是固定参数近似的产物，而他们的残差（ $\varepsilon^\star_\infty$ ）是问题本身的几何常数，并且在良性几何结构下可以证明是消失的。这为非凸设定下的约束学习（例如带有公平性或安全性约束的深度学习）提供了理论基础，而无需依赖可能无法在异构分布下保持约束可行性的凸代理函数。

作者承认的局限性：

实现可行性所需的恢复条件（假设 5）仅在精确情形（ $\varepsilon^\star_\infty=0$ ）下通过一般准则得到验证。
关于可行性的不可知（agnostic）主张依赖于此假设，而价值学习则是无需达成的（attainment-free）。
DERM 程序是一个理想化算法的规范；实际计算实现及实用原-对偶方案的收敛性属于未来工作。
显式速率依赖于源条件；如果没有该条件，阈值是有限的但不是显式的。