What is Learnable in Valiant's Theory of the Learnable?

Problem
This paper addresses a gap in the understanding of Valiant’s original model of learnability, which differs from the PAC learning framework. Specifically, it investigates the learnability of classes under Valiant’s model, where the learner receives only positive samples, can issue membership queries, and must produce a hypothesis with no false positives. Prior work has characterized variants of this model, particularly the case without queries, but a comprehensive analysis of learnability in the presence of membership queries has been lacking. This work is presented as a preprint and has not yet undergone peer review.

Method
The authors introduce a novel characterization of learnability in Valiant’s model, establishing that a class is learnable if every realizable positive sample can be certified by a polynomial-size adaptive query-compression scheme. This approach extends the concept of sample compression, allowing the learner to interact with a membership oracle to certify samples. The authors demonstrate that learnability in this model is strictly sandwiched between the learnability in the PAC model and the variant of Valiant’s model without membership queries. They also explore the extension of this model to arbitrary domains, showing that the same strict sandwiching holds. For the specific case of $d$-dimensional halfspaces, the authors provide a polynomial sample and query algorithm, specifically $\mathrm{poly}(d) \tilde{O}(1/ε)$ samples and $\mathrm{poly}(d) \mathrm{polylog}(1/ε)$ queries, while proving that at least $Ω(d)$ samples or queries are necessary.

Results
The paper presents a significant theoretical contribution by establishing that the introduction of membership queries alters the landscape of learnable classes. The authors show that for every finite domain, including the Boolean hypercube, the learnability condition is met if the aforementioned query-compression scheme is applicable. They provide a concrete algorithm for learning $d$-dimensional halfspaces, which are not learnable without queries, demonstrating that this class is learnable with the proposed method. The results indicate that the learnability of classes in Valiant’s model is more nuanced than previously understood, with implications for the complexity of learning tasks.

Limitations
The authors acknowledge that their characterization does not extend to an exact formulation for arbitrary domains, leaving some aspects of the model’s learnability open for further exploration. Additionally, while they provide a specific algorithm for halfspaces, the generalizability of their results to other classes remains to be fully established. The paper does not address potential computational limitations or the practical implications of implementing the proposed query-compression schemes in real-world scenarios.

Why it matters
This work enriches the theoretical foundation of learning theory by clarifying the implications of membership queries on learnability. The findings suggest that the introduction of queries can significantly expand the set of learnable classes, which may influence future research directions in both theoretical and applied machine learning. The results could lead to new algorithms and methodologies for learning in complex environments where only positive feedback is available, thereby enhancing the robustness and applicability of learning systems.

Authors: Steve Hanneke, Anay Mehrotra, Grigoris Velegkas, Manolis Zampetakis
Source: arXiv:2605.13840
URL: https://arxiv.org/abs/2605.13840v1