Paper: 2606.28309 Authors: Shai Ben-David, Farnam Mansouri, Anay Mehrotra, Manolis Zampetakis Categories: stat.ML, cs.LG, math.ST
The Gap
Standard PAC learning (Valiant, 1984) gave us a clean characterization: a concept class is learnable (improperly) iff it has finite VC dimension. But Natarajan (1987) introduced a variant where the learner only sees positive examples—samples from the positive region of an unknown concept, with the full distribution hidden during training. The question: can a learner still guarantee low error on the full distribution?
For improper learning (where the hypothesis can be any function, not necessarily from the original class), the answer is “yes, iff finite VC dimension” — this is a textbook result (e.g., Kearns & Schapire). For proper learning (where the hypothesis must be chosen from the original concept class), the question remained open for nearly 40 years. The difficulty: positive-only data gives no information about what function values are *not in the class — the learner sees only positive points, and must extrapolate to the entire domain.
Prior attempts hit a wall because they tried to adapt the standard PAC machinery — but in standard PAC, ERM (empirical risk minimization) on labeled positive-negative data works. With positive-only data, you can’t even compute empirical risk because the loss depends on the unobserved negative examples. So entirely new combinatorial structure was needed.
Problem: Characterize proper positive-only learning
|
+-- Assumption 1: Learner sees i.i.d. positive samples from target concept c
| (no negative samples, no unlabeled data)
|
+-- Assumption 2: Evaluation under full distribution D (both positive & negative mass)
|
+-- Known: Improper learning iff finite VC-dim (Natarajan 1987)
| Missing: What extra structure does "proper" require?
|
+-- Method: Introduce "uniform exterior separability" (UES)
| +-- UES: For each concept c, there exists a set of "exterior" points
| | that can be used to define c relative to other concepts in the class.
| +-- Requires all concepts to be simultaneously "visible from outside"
| in a uniform way.
|
+-- Evidence:
| +-- Thm 1: Finite VC-dim + UES => proper learnability (upper bound)
| +-- Thm 2: Proper learnability => UES (lower bound, necessity)
| +-- Separation results (randomized vs deterministic, ERM vs general)
|
+-- Conclusion: Proper positive-only learning = Finite VC-dim + UES
(New dimension: uniform exterior separability index)
The Increment
One sentence: Before this paper, we knew improper positive-only learning was characterized by VC dimension; after this paper, proper positive-only learning is characterized by VC dimension plus a new combinatorial property (uniform exterior separability), revealing that proper and improper learning can diverge dramatically in this setting.
Core Mechanism
The key innovation is a new combinatorial dimension called the uniform exterior separability index (UES-index). It measures, roughly, whether every concept in a class can be distinguished from all other concepts by looking solely at “witness points” that lie in its exterior (the complement of its positive region). These witness points act as anchors: they are points that belong to *some other concept in the class, but not to the target concept. Critically, the same finite set of witness points must work for all concepts in the class—uniformly.
The learning algorithm works in two phases. First, it uses a sample of positive examples to find a concept in the class that is consistent with the observed positives. But because there are many consistent concepts (the data is positive-only!), the algorithm needs additional structure to break ties. The UES property provides this: for any two candidate concepts, there is a witness point that separates them. The algorithm constructs a hypothesis cover—a finite set of hypotheses that are “close enough” to any possible target—using the witness points. Then, from the observed positive sample, it selects the unique hypothesis that matches all positives and satisfies a “maximality” condition relative to the witnesses.
The construction is intricate but elegantly converts a geometric separation property into an algorithmic guarantee.
Data flow (proper positive-only learning with UES):
Positive sample S+ (i.i.d. from c)
|
v
Phase 1: Find all C in class consistent with S+
| (There may be many — no negative info)
|
Phase 2: Use UES witness points W = {w1, ..., wk}
| (pre-computed from class structure)
|
v
For each candidate C: check consistency with W
| (Witness separation: for any C1 != C2, some w in W
| is positive for exactly one of them)
|
v
Output: The C that matches both S+ and W
(exactly one such C exists by construction)
|
v
Guarantee: With enough samples, error < epsilon with high prob.
Internal structure of UES-index computation:
Concept class C on domain X.
|
+-- UES-index d = size of smallest set W subset of X s.t.
| for all distinct C1, C2 in C:
| exists w in W with w in (C1 \ C2) U (C2 \ C1)
| (W is a "separating set" for the class)
|
+-- If d is finite, the class is "uniformly exterior separable"
|
+-- UES-index plays role analogous to VC-dim for proper PLL
Structural Metaphor: The Museum Gallery
Imagine the concept class is a museum with many galleries (concepts). Each gallery has paintings (positive points). You’re only allowed to enter one gallery (the positive region of the target concept), and you must describe which gallery you’re in to a friend outside—but using a fixed, small set of reference paintings that are placed in the hallways between galleries.
The target gallery is unknown to your friend, but they know the museum’s blueprint. You walk through your gallery and see which paintings are present. But because you only see one gallery, you can’t be sure whether you’re in Gallery A or Gallery B if they overlap too much.
The UES property says: the museum is designed such that there exists a small set of special paintings placed in the hallways, with the property that for any two different galleries, at least one special painting is present in exactly one of them. These special paintings are the witness points. They sit exterior to some galleries but interior to others—hence “exterior separability.”
The learning algorithm is like a visitor who consults the museum’s directory (the UES witness set). After entering the gallery and seeing which paintings hang there, they can report back: “I saw paintings {x1, x2, x3}” and then check the directory to deduce, “Since witness painting w7 is absent but w9 is present, I must be in Gallery 17.” The directory’s special property ensures this deduction always works—no ambiguity—as long as the class has finite UES-index.
Without this property, you’d need an infinitely large directory, or you’d sometimes be confused between two different galleries. That’s exactly the gap between learnable and unlearnable.
Key Concepts
-
Uniform Exterior Separability (UES): This is the paper’s star concept. A class C has UES-index d if there exists a set W of at most d points in the domain such that for any two distinct concepts c1, c2 in C, there is a point w in W that lies in exactly one of them (either in c1 but not c2, or in c2 but not c1). The “exterior” part comes from the fact that W points can be outside some concepts—they’re not required to be positive for any particular concept. Intuitively, W serves as a “Rosetta Stone” that can tell any two concepts apart. For example, the class of all intervals [a,b] on the real line: can you find a finite set W that separates every pair of intervals? No—because you’d need a point between every possible pair of endpoints, which would be infinite. Therefore intervals have infinite UES-index and are not properly learnable from positive-only data.
-
Proper vs Improper Learning Gap: In standard PAC learning, proper and improper learning have the same characterization (finite VC dimension). This paper shows that in positive-only learning, they diverge. For instance, the class of all *open intervals on the real line: it has VC-dimension 2, but infinite UES-index (because you need a different exterior point for each interval endpoint). So it’s improperly learnable (via, say, threshold functions) but not properly learnable. This separation is a major surprise—it means the richness of the hypothesis space matters more in positive-only learning.
-
ERM Non-Learnability: A shocking result: there exist concept classes that are properly learnable from positive-only data, but *no empirical risk minimization (ERM) algorithm works for them. This is because ERM looks for a concept consistent with the data, but with positive-only data, many concepts are consistent—ERM has no principled way to choose among them. This violates a fundamental intuition from standard PAC learning, where ERM is always sufficient for learnability.
Framework Shift
Let’s compare how the field used to think about positive-only learning versus how this paper forces us to think.
Before (mainstream view of PLL):
Positive-only learning is "just standard PAC with no negatives"
|
+-- Characterization of improper learning: finite VC-dim
| (via Natarajan 1987)
|
+-- Proper learning was assumed "probably similar, maybe harder"
| but no one knew the exact boundary
|
+-- Working assumption: ERM should work if anything works
| (as in standard PAC)
|
v
Resulting blind spots:
- No way to distinguish learnable from unlearnable classes
- No explanation for why some classes resist proper learning
- No awareness of proper-improper separation
After (this paper):
Positive-only proper learning is a different beast
|
+-- Characterization: Finite VC-dim + UES
|
+-- UES-index is a strict refinement of VC-dimension:
Class A: VC-dim finite, UES finite -> learnable
Class B: VC-dim finite, UES infinite -> not properly learnable
Class C: VC-dim finite, UES infinite -> still improperly learnable
|
+-- New surprises:
- Proper != Improper (separation)
- Deterministic != Randomized (separation of learning types)
- ERM can fail entirely
|
v
Paradigm shift: Proper learning needs "external anchor points"
not just "internal consistency with data"
One sentence: From a VC-dimension-only view to a VC-dimension-plus-exterior-separability view, the core shift is recognizing that positive-only proper learning requires a global geometric witness property in addition to local finite-parameter complexity.
Expert Assessment
Problem choice: This is a real gap, and a beautiful one. The proper positive-only learning problem has been open since Natarajan’s 1987 paper—touched by multiple researchers over the decades but never cracked. Ben-David is a legend in learning theory, and tackling a problem that textbook authors left as an exercise (but couldn’t solve) is a bold choice. The trajectory is perfect: after decades of studying improper learning, the community needed closure on proper learning. This paper delivers.
Method maturity: The UES-index is a clean, elegant combinatorial concept. It’s reminiscent of the Sauer-Shelah lemma in spirit—a geometric property that turns out to be exactly what’s needed. The proof structure (upper bound via hypothesis cover, lower bound via constructing an unlearnable subclass with infinite UES-index) is classic and robust. No brute force here—it’s a deft insight. Could there be simpler approaches? Possibly, but the separation results (deterministic/randomized, ERM/non-ERM) suggest the structure is genuinely complex. The authors didn’t miss a simpler characterization—they found the right one.
Experimental integrity: This is a pure theory paper—no experiments. For theoretical computer science, this is standard and appropriate. The proofs are rigorous, the separation examples are carefully constructed. No red flags. However, the paper would benefit from an explicit example set that practitioners could understand—like showing exactly why “intervals on the line” fails UES and hence proper learning. The theory is tight.
Writing quality: Generally high, as expected from Ben-David’s group. The paper is organized logically: problem statement, characterization theorem, separation results, dimension definitions. One cut corner: the definition of UES-index could be more intuitively motivated before the formal version. A rewritten Section 3 that starts with the museum analogy and then formalizes it would elevate the paper from “good theory” to “memorable theory”. Also, the proof of Theorem 1 is dense—a high-level proof sketch (like the one in this review) inserted before the technical details would help readers who aren’t experts.
Verdict: strong accept — This is an elegant resolution of a long-standing open problem that reveals genuinely surprising structural complexity. It belongs in a top conference (STOC/FOCS/COLT) and will be cited as the definitive reference on proper positive-only learning.
Takeaways
Three concrete things to steal:
-
The UES construction trick: When facing a learning problem where you only see one side of the data, ask: can I find a small set of “anchor points” that separate every pair of hypotheses? This framing transfers to any partial-information setting—one-sided errors, positive-unlabeled learning, or even active learning where you can query specific points.
-
The proper-improper separation as a debugging tool: If you’re building a classifier on positive-only data and get poor results with a specific hypothesis class, don’t just blame sample size. Check whether the class has UES — if it doesn’t, no amount of data will make proper learning work. Switch to an improper method (like decision trees or neural nets) that can express exterior distinctions.
-
The ERM non-learnability insight: Never assume ERM is optimal in partial-information settings. This paper shows that the obvious algorithm (find a concept consistent with positives) can fail even when the class is learnable. If you’re doing positive-only learning, invest in a “tie-breaking” mechanism based on external structure—like using unlabeled auxiliary data as witness points. This insight transfers to other domains where the loss function is unobserved, such as learning with label noise or missing outcomes.
For practitioners in ML: the UES-index isn’t something you can compute easily for large modern classes like deep networks, but the concept matters. It tells you that for positive-only learning, you want hypothesis classes that are “visibly distinct from the outside”—not just ones that can fit the positive data well. This is a clean mathematical reason why contrastive learning (which uses negative points) works better than pure positive-only approaches: the negatives provide the exterior separability.
论文: 2606.28309 作者: Shai Ben-David, Farnam Mansouri, Anay Mehrotra, Manolis Zampetakis 分类: stat.ML, cs.LG, math.ST
缺口
标准PAC学习（Valiant, 1984）给出了一个干净的特征刻画：一个概念类可学习（非正确）当且仅当其VC维有限。但Natarajan（1987）引入了一个变体：学习器只能看到正样本——即未知概念正区域的样本，训练时完整分布不可见。问题是：学习器还能否保证在完整分布上有低错误率？
对于非正确学习（假设可以是任意函数，不必来自原始类），答案是”是，当且仅当VC维有限”——这已是教科书级的结果（如Kearns & Schapire）。但正确学习（假设必须从原始概念类中选择）的问题在近40年来一直悬而未决。困难在于：只有正样本的数据无法提供关于函数值**不在类中*的任何信息——学习器只看到正点，却要外推到整个领域。
此前的研究尝试适配标准PAC工具，但碰壁了——因为标准PAC中，带标签的正负数据上的ERM（经验风险最小化）是可行的。而只有正样本时，你甚至无法计算经验风险，因为损失依赖于未观察到的负样本。因此，全新的组合结构是必需的。
问题：刻画正确正样本学习
|
+-- 假设1：学习器看到目标概念c的i.i.d.正样本
| （无负样本，也无未标记数据）
|
+-- 假设2：在完整分布D上评估（正负区域均有质量）
|
+-- 已知：非正确学习当且仅当VC维有限（Natarajan 1987）
| 缺失："正确"需要什么样的额外结构？
|
+-- 方法：引入"均匀外部可分离性"（UES）
| +-- UES：对每个概念c，存在一组"外部"点，
| | 可用于定义c相对于类中其他概念的位置
| +-- 要求所有概念同时以统一方式"从外部可见"
|
+-- 证据：
| +-- 定理1：有限VC维 + UES => 正确可学习性（上界）
| +-- 定理2：正确可学习性 => UES（下界，必要性）
| +-- 分离结果（随机vs确定性，ERM vs一般）
|
+-- 结论：正确正样本学习 = 有限VC维 + UES
（新增维度：均匀外部可分离性指标）
增量
一句话: 这篇论文之前，我们知道非正确正样本学习由VC维刻画；这篇论文之后，正确正样本学习由VC维加上一个新的组合性质（均匀外部可分离性）共同刻画，揭示了正确与非正确学习在这一设定下可以戏剧性地分岔。
核心机制
核心创新是一个新的组合维度，称为均匀外部可分离性指标（UES-index）。它大致衡量：一个类中的每个概念能否仅通过位于其”外部”（其正区域的补集）的”见证点”来与类中所有其他概念区分开来。这些见证点充当锚点：它们是类中**其他概念的点，但不是目标概念的点。关键的是，同一组有限的见证点必须对类中所有*概念都有效——均匀地。
学习算法分两个阶段工作。第一阶段，使用正样本找到一个与观测正点一致的概念。但由于存在许多一致的概念（数据只有正样本！），算法需要额外结构来打破平局。UES性质提供了这一点：对任意两个候选概念，存在一个见证点将它们分开。算法利用见证点构建一个假设覆盖——一组有限个假设，它们”足够接近”任何可能的目标。然后，从观测到的正样本中，算法选择出唯一与所有正点匹配且相对于见证点满足”极大性”条件的假设。
这个构造虽然精巧，但优雅地将一个几何分离性质转化为算法保证。
正样本学习的UES数据流：
正样本 S+（来自c的i.i.d.样本）
|
v
阶段1：找出所有与S+一致的概念 C
| （可能有很多——缺乏负例信息）
|
阶段2：使用UES见证点集 W = {w1, ..., wk}
| （根据类结构预先计算）
|
v
对每个候选概念 C：检查与W的一致性
| （见证分离：对任意C1 != C2，存在w in W
| 恰好是其中之一的正点）
|
v
输出：同时匹配S+和W的C
（由构造唯一确定）
|
v
保证：样本足够多时，错误率小于epsilon
（高概率）
UES指标计算的内部结构：
概念类C在定义域X上
|
+-- UES指标 d = 满足以下条件的最小集合W包含X的子集
| 对任意不同的C1, C2 in C：
| 存在 w in W 使得 w in (C1 \ C2) U (C2 \ C1)
| （W是类的一个"分离集"）
|
+-- 如果d有限，则该类"均匀外部可分离"
|
+-- UES指标相当于正确正样本学习中的VC维角色
核喻：博物馆画廊
把概念类想象成一个拥有多个画廊（概念）的博物馆。每个画廊里都有画作（正点）。你只能进入一个画廊（目标概念的正区域），必须向馆外的朋友描述自己在哪个画廊——但只能使用一组固定的、放置在走廊里的参考画作。
你的朋友不知道是哪个画廊，但他们知道博物馆的设计蓝图。你走画廊，看到哪些画作在里面。但由于只看到一个画廊，如果画廊A和画廊B有重叠，你就无法确定自己是身在A还是B。
UES性质说的是：博物馆的设计保证了存在一小批放置在走廊里的特殊画作，其性质是：对任意两个不同画廊，至少有一幅特殊画作恰好出现在其中一家。这些特殊画作就是见证点。它们位于某些画廊的外部，却是另一些画廊的内部——因此得名”外部可分离性”。
学习算法就像一个查阅博物馆索引（UES见证集）的访客。进入画廊看到哪些画在墙上后，报告：“我看到了画作{x1, x2, x3}“，然后查阅索引推断：“由于见证画w7不在但w9在，我一定是画廊17。“索引的特殊性质确保这种推断总是有效——只要类有有限的UES指标，就不会有歧义。
没有这个性质，你就会需要无限大的索引，或者有时会在两个不同画廊之间弄混。这恰恰是可学习与不可学习之间的鸿沟。
关键概念
-
均匀外部可分离性（UES）：这是本文的明星概念。一个类C具有UES指标d，如果存在一个至多包含d个点的定义域子集W，使得对任意两个不同的概念c1, c2∈C，存在w∈W恰好属于其中之一（要么在c1中而不在c2中，要么相反）。“外部”来自W中的点可以在某些概念之外——它们不需要对某个特定概念为正。直观上，W是一套”罗塞塔石碑”，能区分任意两个概念。例如，实数线上所有区间[a,b]的类：是否能找到一个有限集W来分离每对区间？不能——因为你需要每对端点之间都有一个点，这是无限的。因此区间类有无穷大的UES指标，不能从正样本中正确学习。
-
正确vs非正确学习的分岔：在标准PAC学习中，正确学习和非正确学习由相同的条件刻画（有限VC维）。本文表明，在正样本学习中，它们分道扬镳。例如，实数线上所有**开*区间的类：它的VC维为2，但UES指标无穷大（因为每个区间端点都需要不同的外部点）。因此它可以非正确学习（比如通过阈值函数），但不能正确学习。这个分离是重大意外——它意味着在正样本学习中，假设空间的丰富性更重要。
-
ERM不可学习性：一个令人震惊的结果：存在一些概念类，虽然可以从正样本中正确学习，但**没有*任何经验风险最小化（ERM）算法能够做到。这是因为ERM寻找与数据一致的概念，但在只有正样本时，许多概念都是一致的——ERM没有原则性的方法从中选择。这违反了我们从标准PAC学习中获得的直觉，在标准PAC中，ERM对可学习性总是充分的。
框架转变
让我们比较一下学术界过去如何思考正样本学习，以及这篇论文迫使我们如何思考。
之前（PLL的主流观点）：
正样本学习就是"没有负样本的标准PAC"
|
+-- 非正确学习刻画：有限VC维
| （通过 Natarajan 1987）
|
+-- 正确学习被假定为"可能类似，但更难"
| 但没人知道精确边界
|
+-- 工作假设：如果有什么可行，ERM就该可行
| （正如标准PAC中那样）
|
v
由此产生的盲点：
- 无法区分可学习与不可学习的类
- 无法解释为什么有些类抗拒正确学习
- 对正确-非正确分离毫无察觉
之后（本文）：
正样本正确学习是另一头野兽
|
+-- 刻画：有限VC维 + UES
|
+-- UES指标是VC维的严格精细化：
类A：VC维有限，UES有限 -> 可学习
类B：VC维有限，UES无限 -> 不能正确学习
类C：VC维有限，UES无限 -> 仍可非正确学习
|
+-- 新的意外：
- 正确 != 非正确（分离）
- 确定性 != 随机性（学习类型的分离）
- ERM可能完全失败
|
v
范式转变：正确学习需要"外部锚点"，
而不仅仅是"数据内部的一致性"
一句话：从仅看VC维到看VC维加外部可分离性，核心转变在于认识到正样本正确学习除了需要局部有限参数复杂度外，还需要全局几何见证性质。
专家评审
选题眼光: 这是一个真实缺口，而且很漂亮。正确正样本学习问题自Natarajan 1987年的论文以来一直悬而未决——几十年来多位研究者触碰过但从未解开。Ben-David是学习理论界的传奇人物，选择解决教科书作者留作练习（却解不开）的问题是勇敢之举。从领域发展轨迹来看，经过数十年对非正确学习的研究，学术界需要为正确学习画上句号。本文做到了。
方法成熟度: UES指标是一个干净、优雅的组合概念。精神上让人想起Sauer-Shelah引理——一个几何性质恰好满足需求。证明结构（上界通过假设覆盖，下界通过构造具有无限UES指标的不可学习的子类）经典而稳健。没有蛮力——是灵巧的洞察。有没有更简单的方法？可能，但分离结果（确定性/随机性，ERM/非ERM）表明结构确实复杂。作者没有错过更简单的刻画——他们找到了对的。
实验诚意: 这是纯理论论文——没有实验。对于理论计算机科学来说，这是标准做法，也是恰当的。证明严谨，分离例子精心构造。没有可疑之处。但论文如果能包含一个实践者能理解的显式示例——比如展示为什么”实数线上的区间”在UES上失败从而不能正确学习——会更好。理论是紧的。
写作功力: 总体优秀，符合Ben-David团队的预期。论文组织逻辑清晰：问题陈述、刻画定理、分离结果、维度定义。一个偷懒之处：UES指标的定义可以在形式化之前有更直观的动机。重新写第3节，先从博物馆类比开始，然后形式化，会把论文从”好的理论”提升为”令人难忘的理论”。另外，定理1的证明很密集——如果在技术细节之前插入一个高级证明梗概（就像本评审中那样），将有助于非专家的读者。
判决: 强接收 — 这是对一个长期开放问题的优雅解决，揭示了真正令人惊讶的结构复杂性。它应被顶级会议（STOC/FOCS/COLT）接收，并将成为正确正样本学习的权威参考文献。
要点总结
三个可以”偷”走的具体想法：
-
UES构造技巧：当你面对一个只能看到单侧数据的学习问题时，问一问：我能否找到一小批”锚点”来分离每对假设？这个框架可以迁移到任何部分信息场景——单侧错误、正-无标签学习，甚至是可以查询特定点的主动学习。
-
正确-非正确分离作为调试工具：如果你在用特定假设类构建正样本分类器，结果不理想，不要只怪样本量。检查该类是否具有UES——如果没有，再多数据也没办法让正确学习工作。换成非正确方法（如决策树或神经网络）来表达外部区别。
-
ERM不可学习性洞见：在部分信息设定下，永远不要假设ERM是最优的。本文表明，即使在类可学习时，明显的算法（找到与正样本一致的概念）也可能失败。如果你在做正样本学习，要投入基于外部结构的”破平机制”——比如使用未标记的辅助数据作为见证点。这一洞见可以迁移到损失函数不可观察的其他领域，如带标签噪声的学习或缺失结果的学习。
对机器学习实践者来说：UES指标不是你能轻易计算的量，尤其是对于深度网络这样的大型现代类，但概念很重要。它告诉你，在正样本学习中，你需要的假设类是”从外部清晰可辨”的——而不仅仅是能拟合正数据。这为对比学习（使用负例）为何比纯正样本方法效果更好提供了一个干净的数学理由：负例提供了外部可分离性。