这篇论文澄清了机器学习理论中一个长期被误解的基础问题——Valiant 原始模型与 PAC 学习的区别，做学习理论或计算复杂度研究的学者值得一读，尤其是对成员查询能力感兴趣的人。
这篇论文重新审视了 Valiant 1984 年提出的原始学习模型（不同于 PAC 学习），该模型中学习器只能接收正例、可发起成员查询、且必须输出无假正例的假设。作者对有限域（包括布尔超立方体）给出了可学习性的充要条件：每个可实现的样本必须能被一个多项式大小的自适应查询压缩方案认证。这一刻画表明，Valiant 模型的可学习类严格介于 PAC 模型和无查询的 Valiant 模型之间，是少数成员查询能改变可学习类集合而非仅复杂度的情况。对于任意域，同样的严格夹逼关系仍然成立。此外，论文首次给出了 d 维半空间在 Valiant 模型中的学习算法（多项式样本和查询），并证明了 Ω(d) 的样本或查询下界。
What is Learnable in Valiant's Theory of the Learnable?
Valiant's 1984 paper is widely credited with introducing the PAC learning model, but it, in fact, introduced a different model: unlike PAC learning, the learner receives only positives, may issue membership queries, and must output a hypothesis with no false positives. Prior work characterized variants, including the case without queries. We revisit Valiant's original model and ask: *Which classes are learnable in it?* For every finite domain, including Valiant's Boolean-hypercube setting, we show that a class is learnable if and only if every realizable positive sample can be certified by a poly-size adaptive query-compression scheme. This is a new variant of sample compression where the learner certifies samples via a short interaction with the membership oracle. Our characterization shows that learnability in Valiant's model is strictly sandwiched between learnability in the PAC model and the variant of Valiant's model without membership queries. This is one of the rare cases where introducing membership queries changes the set of learnable classes, and not just the sample or computational complexity. Next, we study the natural extension of the model to arbitrary domains. While we do not obtain an exact characterization, our techniques readily generalize and show that the same strict sandwiching persists. Finally, we show that $d$-dimensional halfspaces, which are not learnable without queries, are learnable with queries: we give a $\mathrm{poly}(d) \tilde{O}(1/ε)$ sample and $\mathrm{poly}(d) \mathrm{polylog}(1/ε)$ query algorithm, and prove that at least $Ω(d)$ samples or queries are necessary. To our knowledge, this is the first algorithm for halfspaces in Valiant's model. Together, these results uncover a surprisingly rich theory behind Valiant's original notion of learnability and introduce ideas that may be of independent interest in learning theory.