arXiv:2605.13840v1 [stat.ML] 13 May 2026
What is Learnable in Valiant’s Theory of the Learnable? Steve Hanneke Purdue University [email protected]
Anay Mehrotra Stanford University [email protected]
Grigoris Velegkas Google Research [email protected]
Manolis Zampetakis Yale University [email protected]
Abstract Valiant’s seminal 1984 paper [Val84a, Commun. ACM] is widely credited with introducing the PAC learning model, but, in fact, it introduced a different model: while a PAC learner observes both positive and negative examples and may err on both sides, Valiant’s learner receives only positive examples, may issue membership queries, and must produce a hypothesis with no false positives. Several variants of this model have been studied and characterized: for instance, Natarajan [Nat87, STOC], Shvaytser [Shv90, Machine Learning], and Kivinen [Kiv95, Math. Systems Theory] characterized the special case of Valiant’s model without membership queries. We revisit the original model and ask: Which hypothesis classes are learnable in it? For every finite domain, and in particular for Valiant’s original Boolean-hypercube setting (where learnability requires polynomial dependence on the ambient dimension), we show: a concept class is learnable if and only if every realizable positive sample can be “certified” by a polynomial-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 instead of the usual non-interactive compression schemes that characterize PAC learning. Our characterization, along with simple examples, shows that learnability in Valiant’s model is strictly sandwiched between PAC learnability and the variant 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 of learning). Further, our characterization bounds the sample complexity of learning within polynomial factors. Next, we study the natural extension of the model to arbitrary domains. While we do not obtain an exact characterization here, our techniques readily generalize and show that learnability remains strictly sandwiched between PAC learning and the variant without queries. Finally, we show that, while halfspaces over Rd are not learnable without queries (for any e ((log 1/δ)/ε) d ≥ 2), they become learnable with queries: to show this, we give a poly(d) · O sample and poly(d) · polylog(1/εδ) query algorithm for learning halfspaces and show that at least Ω(d) samples or queries are necessary. To the best of our knowledge, this is the first algorithm to learn halfspaces in Valiant’s model; previous algorithms could only learn halfspaces with finite bit-complexity, which reduced the problem to learning a finite class. 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.
Contents 1
Introduction 1 1.1 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 Characterization of Learnability in Valiant’s Model . . . . . . . . . . . . . . . 2 1.1.2 Some Implications of Theorem 1.1 and Corollary 1.2 . . . . . . . . . . . . . . . 4 1.1.3 Results for Extension to General Domains . . . . . . . . . . . . . . . . . . . . . 5 1.2 Technical Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.1 Challenges in Characterizing Valiant’s model . . . . . . . . . . . . . . . . . . . 6 1.2.2 Overview of the Proof of Characterization . . . . . . . . . . . . . . . . . . . . 8 1.2.3 Overview of Learning Halfspaces in d-dimensional Euclidean Space . . . . . 10 1.3 Takeaways, Discussion, and Open Problems . . . . . . . . . . . . . . . . . . . . . . . 11 1.4 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2
Preliminaries 2.1 Discussion of Valiant’s Model of Learning . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Adaptive Query Strategies and Version Spaces . . . . . . . . . . . . . . . . . . . . . . 2.3 VC Dimension and One-Centered Star Number . . . . . . . . . . . . . . . . . . . . . .
14 14 15 16
3
Characterization of Learnability 3.1 Additional Discussion of Query-Compression and Characterization . . . . . . . . . . 3.2 Proof of Theorem 1.1 (Characterization) . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Boosting in Valiant’s Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Uniform Success Over All Potential Targets . . . . . . . . . . . . . . . . . . . . 3.2.3 Learnability Implies Query-Based Compression . . . . . . . . . . . . . . . . . 3.2.4 Query-Based Compression Implies Learnability . . . . . . . . . . . . . . . . . 3.2.5 A VC Lower Bound for Learnability in Valiant’s Model . . . . . . . . . . . . . 3.2.6 Completing the Characterization of Learnability in Valiant’s Model . . . . . .
17 17 18 18 19 21 25 28 30
4
Proofs of Remaining Results 30 4.1 Proof of Proposition 1.3 (Positive-Only Learning as the Non-Interactive Special Case) 30 4.2 Proof of Corollary 1.4 (Sandwich between PAC and Positive-Only Learning) . . . . . 31 4.3 Proof of Theorem 1.5 (Sandwich between PAC and Positive-Only on General Domain) 33 4.4 Proof That Conditions in Theorem 1.5 Are Not Tight for Learnability . . . . . . . . . 35 4.5 Proof of Theorem 1.6 (Halfspaces Are Learnable on Rd ) . . . . . . . . . . . . . . . . . 37 4.6 Proof of Proposition 1.7 (Halfspaces Are Not Learnable on the Boolean Cube) . . . . 43
A Additional Results A.1 Learning Intersections of s Halfspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Learnability in Valiant’s Model Is Closed under Unions . . . . . . . . . . . . . . . . . A.3 A Finite-VC Class whose 1-Point Closure has Infinite VC Dimension . . . . . . . . .
50 50 52 54
B Proof of Theorem 3.4 (Boosting; Deferred from Section 3)
55
1
Introduction
Valiant’s seminal 1984 paper [Val84a] is widely credited with introducing the PAC learning model, but the learning model it actually formulates is different. In particular, a PAC learner observes both positive and negative examples and may make mistakes on either side (that is, it may make both false positive and false negative errors, provided this happens with probability at most ε). A learner in Valiant’s model receives only positive examples (i.e., samples drawn from a distribution supported entirely on the positive region of an unknown target h⋆ ), may issue membership queries of the form “is h⋆ ( x ) = 1?” for any x in the domain, and must output a hypothesis that introduces no false positives while covering all but an ε-fraction of the positive distribution. Valiant defined learnability in this model for a sequence of concept classes H = (H1 , H2 , . . . ), where each Hd is a class of Boolean functions on {0, 1}d , as follows. Definition 1 (Valiant’s Learning Model [Val84a]). A sequence of concept classes H = (H1 , H2 , . . . ) is learnable in Valiant’s model if there exists a learner L such that, for every ε, δ ∈ (0, 1), d ∈ N, target hypothesis h⋆ ∈ Hd , and distribution D satisfying supp(D) ⊆ supp(h⋆ ), the learner uses at most m(d, ε, δ) = poly(d, 1/ε, 1/δ) positive examples and membership queries, and outputs a hypothesis h, such that, with probability at least 1 − δ, supp(h) ⊆ supp(h⋆ )
Prx∼D ( x ∈ / supp(h)) ≤ ε.
and
Compared to PAC learning, this model differs in three ways. First, the learner sees only positive data. Second, the guarantee is one-sided: the learner may miss an ε-fraction of the positive distribution, but may not cover any elements outside of h⋆ . Third, the learner may interact with the target through membership queries.1 The requirement that m(d, ε, δ) be polynomial in d is also essential as the domain {0, 1}d is finite, and so one can trivially learn any target with 2d queries. Hence, if m(d, ε, δ) is not required to be polynomial, then the model becomes vacuous. Finally, the learner’s membership queries may be adaptive: each query made by the learner may depend on the responses to their previous queries and any positive examples they have seen. Equivalently, the learner may traverse a binary query tree whose branches correspond to oracle responses. Each of these three ingredients has independent motivation: 1. The positive-only viewpoint has long been recognized as natural. Already in related early work [Val84b], Valiant defended his definition of learning compared to two-sided versions, such as PAC, by noting that “to discuss the distribution of the attributes of elephants, we may prefer not discussing the distribution of the attributes of non-elephants.” This perspective is even more compelling in modern settings motivated by generative models, where one typically observes valid text during training but there is no canonical distribution over invalid outputs [KM24; KMV25]. The idea itself dates back to Gold’s seminal model of identification in the limit [Gol67], where the learner is presented with positive examples but no negative examples. More broadly, there is a long and ongoing body of work on learning from positive-only examples, e.g., [FJK96; NR09; AGR13; DDS15; KTZ19; CDS20; JKV23; LMZ24; MB25; LMZ26]. 1 If there are multiple hypotheses consistent with D, all answers of the oracle are consistent with at least one of them.
1
2. The second ingredient, the one-sided guarantee, is important in many applications where false positives are substantially more costly than false negatives, so a conservative hypothesis is preferable; see [EN08; LGE10]. One-sided guarantees are also important in missing data problems, e.g., truncated statistics [DGTZ18; KTZ19; LMZ24], where without one-sided guarantees many classical estimators, like maximum-likelihood, are not well-defined [LMZ24]. This also naturally arises in generative modeling, where one-sided error is required to avoid hallucinations [HKKT18; KM24; CP25; KMV25]. 3. The third ingredient is membership queries, which allow the learner to acquire information about points that never appear in the positive sample. More broadly, they place the model within the long tradition of interactive and query-based learning. Since Angluin’s seminal work, membership queries and related query mechanisms have been studied extensively in exact learning, query learning, and active learning [Ang88; KMT93; Ang04; BBL06; Han07; BHV10; Bsh18; Han25]; we refer the reader to [Han09; Set12; AKGHY14] for an overview of active learning. Over the years, learnability has been characterized in several neighboring models that modify one or more of these ingredients: the positive-only sample model [Nat87; Shv90; Kiv95], the standard PAC setting and its query variants [BEHW89; ER90], and models with stronger or different query interfaces [Ang88; KMT93; HMST03; Ang04; Bsh18]. These results clarify the landscape around the original model, yet the question that Valiant [Val84a] posed, which combined all three ingredients, has resisted a complete answer: Which sequences of concept classes are learnable in Valiant’s original model?
1.1
Our Results
1.1.1
Characterization of Learnability in Valiant’s Model
Our first result answers the above question by giving a complete characterization of learnability in Valiant’s original model. A natural starting point is the existing characterizations of PAC learnability in binary classification. There are two standard ways to characterize binary classification in PAC learning. One is through finiteness of the VC dimension [VC71; VC74; BEHW89] and the other is via the existence of bounded-size sample compression schemes [LW86; FW95; MY16]. The VC-dimension viewpoint bounds the complexity of a hypothesis class through the labelings it can realize. The compression viewpoint asks whether datasets are compressible: given an arbitrary labeled sample consistent with some h ∈ H, can the learner retain only k examples (and a small number of additional bits) from which the labels of the entire sample can be recovered? The second viewpoint turns out to be more fruitful in Valiant’s model. Because the learner may ask membership queries, the natural analogue is not an ordinary “static” compression scheme but an adaptive one. This leads naturally to an interactive notion of compression, in which the certificate is not just a subsample, but an adaptive query transcript whose answers force the observed sample to be positive for every hypothesis consistent with the resulting transcript. To formulate this notion, we first introduce version spaces: For a finite set of positive examples S ⊆ {0, 1}d , let V(S) := { h ∈ Hd : S ⊆ supp(h)} be the set of hypotheses in Hd consistent with S. 2
Likewise, if T is a query-response transcript, let V( T ) denote the set of hypotheses in Hd consistent with that transcript. If Σ is an adaptive query strategy and r is a realized response sequence, we write V(Σ, r ) for the version space defined by the corresponding realized root-to-leaf transcript. Definition 2 (Adaptive-Query Compression Scheme). Fix d ∈ N and a set S ⊆ {0, 1}d with V(S) ̸= ∅. A deterministic adaptive query strategy ΣS is an adaptive-query compression scheme for S if, for every response transcript r of ΣS that is realizable with respect to V(S),2 S⊆
\
supp(h).
h∈V(ΣS ,r )
The size of the scheme is the depth of ΣS , i.e., the maximum number of queries on any root-to-leaf path. For brevity, we will also refer to an adaptive-query compression scheme simply as a query compression scheme. The role of the transcript is to certify the data S: once the responses are known, every hypothesis consistent with the transcript must already label every point of S as positive, so S carries no further information. Note that this compression scheme retains no explicit subsample of S. This is without loss of generality, as the learner has membership queries and if they wish to recover the labels of k sample points, they can simply query them directly. Further, because the learner only observes positive examples, a standard reconstruction map would make compression vacuous: one could always “reconstruct” the sample by simply labeling everything positive. The transcript must therefore certify the sample through the version space itself (Remark 3.2). There are two key differences between standard compression schemes and the scheme above, which make the two incomparable. On the one hand, query compression schemes are more general: in addition to the information already present in the sample, they can use additional information obtained through membership queries. On the other hand, query compression schemes are more restrictive in how reconstruction works (Remark 3.2). Our characterization is based on query compression schemes and is as follows: Theorem 1.1 (Characterization). A sequence of concept classes H = (H1 , H2 , . . . ) is learnable in Valiant’s model if and only if every realizable positive sample S ⊆ {0, 1}d admits an adaptive-query compression scheme of size poly(d). In other words, learnability in Valiant’s model is exactly the ability to replace an arbitrary realizable positive sample by a short interactive certificate. Moreover, the proof is quantitative: Corollary 1.2. Fix a sequence of classes H = (H1 , H2 , . . . ). The following hold in Valiant’s model: 1. If H admits an adaptive-query compression scheme of size q(d) for each realizable positive sample S ⊆ e ((d/ε) log 1/δ). {0, 1}d , then H is learnable with sample/query complexity m(d, ε, δ) ≤ q(d) · O 2. Conversely, if H is learnable with sample/query complexity m(d, ε, δ), then every finite realizable positive sample S ⊆ {0, 1}d admits an adaptive-query compression scheme of size O(m(d, 1/20, 1/20)2 · d2 ). Thus, adaptive-query compression captures the sample and query complexity of Valiant’s model up to polynomial factors. Here, the adaptivity of the queries is also essential. The learner does not know in advance which branch of the query tree will be realized, since this depends on the 2 Here, “realizable with respect to V ( S )” means that the transcript is produced by Σ
3
S on some hypothesis in V ( S ).
unknown target (Remark 3.3). The characterization extends naturally beyond the Boolean hypercube to any finite domain of size N, with the requirement that m be polynomial in log N instead of d (Remark 3.1). The proof of Theorem 1.1 and Corollary 1.2 appears in Section 3. 1.1.2
Some Implications of Theorem 1.1 and Corollary 1.2
A first benchmark for our characterization is the special case of Valiant’s model in which membership queries are not allowed and the learner must work only with the observed positive sample. As mentioned earlier, this positive sample-only variant was characterized by Natarajan [Nat87] and Shvaytser [Shv90] (with sharp sample complexity due to Kivinen [Kiv95]). Concretely, H is learnable from positive examples alone if and only if, for each d, the intersection closure of Hd , say Hd , has VC dimension poly(d) (Theorem 2.3).3 Our characterization allows us to recover one side of this characterization: if VC Hd = poly(d), then H is learnable in the above model. In particular, we get this by combining our characterization with the following simple result: Proposition 1.3 (Positive-Only Learning as the Non-Interactive Special Case). If, for each d, the intersection closure of Hd has VC dimension poly(d), then every finite realizable positive sample S ⊆ {0, 1}d admits an adaptive-query compression scheme of size poly(d). Moreover, this scheme can be chosen non-adaptively, and all of its queried points can be taken from S itself. Thus, whenever positive-only learning is possible without membership queries, the certificate in our characterization can already be extracted from the observed sample itself: no adaptivity or extra queries outside the sample are needed. In this sense, the classical characterization of positiveonly learning is a non-interactive special case of our characterization. The proof of Proposition 1.3 appears in Section 4.1. Another natural question is whether learnability in Valiant’s model coincides with one of the two familiar extremes: PAC learning (governed by VC(Hd )) or positive-only learning without membership queries (governed by the VC dimension of the intersection closure of Hd ). (Over the Boolean domain, the standard PAC learning model also requires the sample complexity to be poly(d) and is characterized by VC(Hd ) = poly(d); [KV94].) The following corollary shows that Valiant’s model does not collapse to either extreme. Corollary 1.4 (Sandwich between PAC and Positive-Only Learning). Fix H and its intersection closure H. The following hold in Valiant’s model. 1. If VC(Hd ) = dω (1) , then H is not learnable. 2. If, for infinitely many d, Hd contains every subset of {0, 1}d , then H is not learnable. In particular, there exists H with VC(Hd ) = 1 for each d ∈ N that is not learnable. 3. There exists a sequence of classes that is learnable even though, for infinitely many d, VC Hd = dω (1) . Taken together, these three items show that Valiant’s model lies strictly between PAC learning and positive-only learning without membership queries. Item 1 shows that Valiant’s model is no more permissive than PAC learning, while Item 2 shows that this containment is strict. In the other direction, positive-only learning without membership queries is a special case of Valiant’s model, 3 The intersection closure of H is the smallest superclass of H closed under finite intersections. d d
4
since a learner with query access can always ignore it. Item 3 shows that this inclusion is also strict. Thus Valiant’s model lies strictly between PAC learning and positive-only learning 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 of learning). The proof of Corollary 1.4 appears in Section 4.2. 1.1.3
Results for Extension to General Domains
Next, we study the natural extension of Valiant’s model to an arbitrary domain X. As is standard over arbitrary domains, learnability is defined for a single concept class H ⊆ {0, 1}X rather than for a sequence indexed by dimension. Definition 3 (Valiant’s Model over a General Domain). Fix a domain X and a concept class H ⊆ {0, 1}X . We say that H is learnable in Valiant’s model over X if there is a learner and m : (0, 1)2 → N such that for every target hypothesis h⋆ ∈ H, every distribution D over X compatible with h⋆ , and every ε, δ ∈ (0, 1), the learner, using m(ε, δ) positive examples from D and membership queries to h⋆ , outputs with probability at least 1 − δ a hypothesis h satisfying supp(h) ⊆ supp(h⋆ ) and Prx∼D ( x ∈ / supp(h)) ≤ ε. This is the same one-sided requirement as before; the only change is that the instance space is now arbitrary and learnability is defined for a fixed class rather than a dimension-indexed sequence. While we do not obtain an exact characterization in this setting, we prove the following generaldomain analogue of Corollary 1.4. Theorem 1.5 (Sandwich between PAC and Positive-Only Learning). Fix a concept class H ⊆ {0, 1}X and let H denote its intersection closure. The following hold in Valiant’s model over a general domain. 1. If H is learnable with m(ε, δ) positive examples/membership queries, then VC(H) ≤ 9 m(1/3, 1/3) + 1. 2. If |X| = ∞, H contains the constant-one hypothesis, and for every x ∈ X it also contains a hypothesis that labels x zero and every point in X \ { x } positive, then H is not learnable.4 In particular, there exists H with VC (H) = 1 that is not learnable. e (1/ε) · VC H + log1/δ . 3. If VC H < ∞, then H is learnable with sample and query complexity O This is the natural general-domain analogue of the picture from the Boolean setting. Item 1 is familiar from PAC learning. Item 2 gives a sufficient condition for non-learnability that already shows the containment inside PAC learning is strict: the class consisting of the constant-one hypothesis together with the complements of singletons has VC dimension 1, yet item 2 shows it is not learnable. Item 3 is the sufficient condition for learnability via the intersection closure H, mirroring the classical positive-only characterization. One might hope that, over arbitrary domains, one of the three criteria above could be turned into a characterization; we show that none of them is tight (Theorem 4.4). The proof of Theorem 1.5 appears in Section 4.3. Learnability of Halfspaces in d-Dimensional Euclidean Space. A particularly compelling instance of the gap between Valiant’s model and the version without membership queries is the 4 Equivalently, that H shatters the whole domain in a 1-star sense; see Definition 11.
5
class of halfspaces. Halfspaces (or linear threshold functions) are among the most basic and extensively studied concept classes in learning theory [SB14; MRT18], and their learnability is well understood in several different learning models. In our setting they are especially revealing because, by the characterizations of Natarajan [Nat87] and Shvaytser [Shv90], halfspaces over Rd (for d ≥ 2) are not learnable from positive examples alone, and yet we show that they become learnable once membership queries are available. Theorem 1.6 (Halfspaces Are Learnable on Rd ). There is an algorithm that learns halfspaces in Rd in Valiant’s model using m(ε, δ) positive examples and q(ε, δ) membership queries, where 2 d log d · log1/ε + log1/δ m(ε, δ) = O ε
and
3
3
q(ε, δ) = O d log
d · log1/εδ
.
To the best of our knowledge, this is the first algorithm for learning halfspaces in Valiant’s model. Moreover, using Theorem 1.5, we can also conclude that the total sample/query complexity of the above model is optimal up to polynomial factors: this is because halfspaces in Rd have VC dimension d + 1, and, hence, item 1 of Theorem 1.5 implies that any learner requires max{m(1/3, 1/3) , q(1/3, 1/3)} = Ω(d) positive examples or membership queries. The proof of Theorem 1.6 appears in Section 4.5. It is natural to ask whether the same holds over the Boolean cube. Perhaps surprisingly, restricting halfspaces in Rd to the Boolean cube {0, 1}d makes the class not learnable. Proposition 1.7 (Halfspaces Are Not Learnable on the Boolean Cube). Let HH = H1H , H2H , . . . , where HdH is the class of restrictions to {0, 1}d of halfspaces in Rd . Then HH is not learnable in Valiant’s model (where the learner can only query points in {0, 1}d ). The reason is that halfspaces on {0, 1}d can express every subset of the cube. The constant-one halfspace labels every vertex as positive, and for each vertex v ∈ {0, 1}d there is a halfspace that labels every vertex except v as positive. By intersecting these halfspaces one can obtain any arbitrary subset of the cube, so the impossibility result from Item 2 of Corollary 1.4 applies. Over Rd , by contrast, the learner can query points outside {0, 1}d , and the algorithm in Theorem 1.6 exploits exactly this additional freedom. See Section 4.6 for details.
1.2
Technical Overview
In this section, we explain the key ideas and challenges in characterizing Valiant’s model, and in learning halfspaces from positive examples and membership queries. 1.2.1
Challenges in Characterizing Valiant’s model
First, we discuss challenges in using standard approaches for characterizing Valiant’s model. Recall that Valiant’s model differs from the PAC learning model in three ways: (C1) the learner must make only one-sided error, (C2) the learner only observes positive examples, and (C3) the learner has access to membership queries to the target hypothesis. Challenge I: “One-Sided Covers” Are Not Known for General Concept Classes. A standard way of characterizing learnability in PAC learning is via the existence of uniform ε-covers C(H) for concept classes H with small VC dimensions, and then utilizing uniform convergence over 6
the hypotheses in the ε-cover. The resulting universal learning algorithm is then empirical risk minimization (ERM) over the ε-cover C(H). For such a learner to work in Valiant’s model, it has to achieve one-sided error, that is, satisfy Condition C1. To do this, we would need the cover to satisfy the following stronger “one-sided” guarantee:
∀h∈H , ∃c∈C(H) , s.t.,
supp(c) ⊆ supp(h)
and
Pr ( x ∈ supp(h) \ supp(c)) ≤ ε .
x ∼D
Let us call such a cover an ε-containee. Similar covers have been studied by prior work, e.g., by Braverman, Kol, Moran, and Saxena [BKMS21] and Dutta, Ghosh, and Moran [DGM22]. In particular, these works introduce a concept of ε-containers, which is equivalent to having ε-containees for the complement class {X \ supp(h) : h ∈ H}. However, unlike the standard ε-covers, these ε-containers and ε-containees are much less well understood, and, for instance, we do not know a general characterization of which pairs of concept classes H and distributions D admit them. Hence, any approach to characterize Valiant’s model by utilizing covers would need to first understand when ε-containees exist. Further, even if we are able to do this, it is still unclear whether this is the right approach because it is not clear how, given a ε-containee, one would utilize membership queries for learning. As we have seen, membership queries do change what is learnable in Valiant’s model, so we cannot simply ignore them. Challenge II: No Known “Universal” Learning Algorithm. Another idea is to try to take inspiration from Natarajan [Nat87] and Shvaytser [Shv90]’s characterization of the special case where the learner does not have access to membership queries. To get a characterization, they relied on the following simple observation: given positive samples S, any valid learner must output a subT set of the closure Closure(S) := h∈V(S) supp(h). Since the closure always has one-sided error (as T ′ ′ h∈V(S) supp( h ) ⊆ supp( h ) for any h ∈ V ( S )), one can always convert a learning algorithm into one that outputs the closure of S. And now, since one-sided error is guaranteed and the learner does not have access to membership queries, it is sufficient to analyze when uniform convergence T holds over the concept class of all closures: H = h∈G supp( h ) : G ⊆ H where |G | is finite . This is why the characterization in this special case turns out to be a bound on VC H . In Valiant’s model, however, the learner has access to membership queries and can use these queries to change the version space of hypotheses consistent with the observed transcript. Hence, to characterize Valiant’s model, we need to understand when queries can be used to alter the version space so that its closure is “well behaved,” e.g., it has a small VC dimension, and this is an algorithmic puzzle we need to solve to prove Theorem 1.1. Challenge III: Techniques for Characterizing Exact Learning Are Too “Coarse.” We saw in the previous paragraph that accounting for membership queries is an added challenge in characterizing Valiant’s model. Given this, a natural approach is to try to utilize techniques for characterizing classes that are learnable with membership queries. There are a number of dimensions known to characterize classes that are learnable from different forms of queries, including membership queries, equivalence queries, and disjointness queries (among others) [Ang88]. Essentially, all of these characterizations are for exact learning, where the goal is to identify the target concept from the hypothesis class exactly. At a high level, these characterizations build a “query tree” over the hypothesis class, where each query splits the surviving hypotheses according to the response, and the goal is to isolate the target with as few steps as possible. The characterization then corresponds 7
to the existence of a query tree of finite depth. This approach is insufficient for us for two reasons: First, because we see positive examples, given samples S, the hypothesis class for which we want to create a query tree is V(S) and not H. So at the least, we would need to understand some necessary and sufficient structure on H such that with high probability the resulting version space V(S) has a small finite-depth query tree. Second, because our goal is not to do exact learning, it is not even clear whether a query tree is the right combinatorial objective: it is certainly sufficient for learning, but it may not be necessary, since we do allow the output to make errors on one side. 1.2.2
Overview of the Proof of Characterization
Our proof makes a sequence of deliberate choices to overcome the challenges described above: Rather than pursuing a characterization via a notion of covers, we work with sample compression schemes, which turn out to be better suited to the one-sided requirement in Valiant’s model and thereby avoid Challenge I. Our compression schemes are query based (Definition 2) and so, at first sight, resemble the “query trees” used in exact learning (see Challenge III above). Indeed, both consist of finite adaptive sequences of queries. The key difference, however, is in the objective: while query trees for exact learning aim to isolate the target hypothesis h⋆ , our goal is to certify that S is a positive sample, in the sense that every hypothesis consistent with the realized query transcript must be positive on all of S (Definition 2). This shift in perspective avoids Challenge III. Finally, somewhat counterintuitively, this viewpoint also yields the right notion of a “universal” learning algorithm: whenever a concept class H is learnable in Valiant’s model, there is a learner that certifies the observed sample using poly(d) queries and then outputs the closure of the resulting version space (Theorem 3.9). This overcomes Challenge II. In the remainder of this section, we give an outline of our proof, in three parts. Part 1 (Learnability implies Small Query Compression Scheme) (Theorem 3.6) In this part, we show that if H is learnable, then Hd has a query compression scheme of size qd ≤ mW (d) · O(d VC(Hd )) . Here mW (d) is the query/sample complexity of “weak learning” for H (i.e., learning with ε, δ = Ω(1)). To establish the above upper bound, we first bound the size of a “weak” compression scheme (Definition 13), which is only required to certify an Ω(1)-fraction of the positive examples. Intuitively, given the existence of a weak compression scheme for each realizable set S of positive samples, we can get a strong compression scheme by repeating this process O(log |S|) times: in each round we certify a constant fraction of S, remove the certified samples, and recurse on the remainder (Theorem 3.6). Then we can deduce the result since O(log |S|) ≤ d as S ⊆ {0, 1}d . It remains to explain how to obtain such a weak compression scheme. Let T be the entire transcript of interaction between the learner and the environment, including positive samples, queries, and responses. Let V( T ) be the version space of hypotheses consistent with this transcript. Bound on weak compression-scheme size (assuming learner outputs a closure). If we knew the learner outputs a closure over this version space, then it is simple to bound the weak compressionscheme size: We can simply run a weak learner on the uniform distribution over S to produce a transcript T of length O(mW (d)). Since it is a weak learner that outputs the closure over V( T ), it 8
must be the case that |S ∩ h∈V(T ) supp(h)| ≥ Ω(|S|). Thus, we can obtain a weak compression scheme by compiling this realized run into an adaptive query strategy: every sampled point in T is turned into a membership query, and we also keep the learner’s ordinary membership queries. T
Bound on weak compression-scheme size (without assumptions on the learner). If the learner’s output can be non-closure, then the argument is much more challenging because we can no longer T assume that |S ∩ h∈V(T ) supp(h)| ≥ Ω(|S|). To address this, we show that whenever H is learnable, there is a learner that succeeds uniformly over all potential targets consistent with its realized transcript, namely, all hypotheses in V( T ). Concretely, in the (ordinary) Valiant model, for each fixed target h ∈ V( T ) the learner may fail with probability δ, but the failure event may depend on h. In the uniform version, with probability at least 1 − δ, the learner must succeed simultaneously for every h ∈ V( T ). The analogous strengthening of PAC learning is known as Probably Uniformly Approximately Correct (PUAC) learning and learnability in it is known to be equivalent to learnability in PAC learning [Vid03, see Chapters 3, 6, 7]. To avoid the case of non-closure learners, we prove the analogous statement for Valiant’s model, namely that whenever a class H is learnable in Valiant’s model, it is also learnable in this uniform version (Theorem 3.5). This then implies that whenever H is learnable, there is a weak learner whose output is the closure of the realized version space, which by the earlier argument suffices to bound the weak compression-scheme size. Part 2 (Small Query Compression Scheme implies Learnability) (Theorem 3.9) Next, we show that if Hd has a query compression scheme of size qd , then it is learnable with
dqd + log 1/δ m(d, ε, δ) = O ε
positive samples and membership queries .
As we alluded to before, the algorithm is simple: it runs the query compression scheme on the sample S to obtain a transcript T = (q, r ) that certifies S, and then outputs the closure over V( T ). Since all responses in the transcript were generated by the target h⋆ , h⋆ ∈ V( T ). Hence the closure has one-sided error, and it only remains to show that it generalizes. For this, it suffices to show that the set of all possible outputs of the learner has small VC dimension. This output class is \ Clqd (Hd ) := supp(h) : transcript T of length at most qd and V( T ) ̸= ∅ . (1) h∈V( T )
Here, V( T ) is the version space of hypotheses in Hd consistent with T. This is exactly the relevant output class because every possible output of the learner is the closure of some realized transcript of length at most qd . Note that while this output class takes intersections of hypotheses from Hd , it is not the class of intersections of at most qd hypotheses from Hd ; rather, each output is obtained by intersecting the entire version space V( T ), which may contain a large number of hypotheses. We show that VC Clqd (Hd ) ≤ (d + 1)(qd + 1) (Lemma 3.8). Interestingly, this bound does not depend on the VC dimension or complexity of Hd at all; it comes purely from counting labeled query transcripts of length at most qd over the finite domain {0, 1}d . This contrasts with the usual class of intersections of at most qd hypotheses from Hd , whose VC dimension generally does depend on VC(Hd ) (e.g., [BEHW89; EA07]). In this argument, we are crucially using the 9
finiteness of the domain; indeed, on infinite domains even 1-point query closures can have infinite VC dimension, despite the original class having VC dimension at most two (Theorem A.11). Remark 1.8. This compression-based structure of the learner is useful beyond establishing the characterization itself. For instance, it can also be used to deduce closure properties of learnability in Valiant’s model, such as union-closedness (see Theorem A.8). Part 3 (Small VC Dimension Is Necessary for Learning) (Theorem 3.10) In this part, we prove that learnability in Valiant’s model requires sample/query complexity at least linear in the VC dimension, namely that m(d, ε, δ) ≥ (VC(Hd ) − 1) /9 for ε, δ < 1/2. This lets us replace the VC(Hd ) term appearing in Part 1 by the complexity of the learner itself, and thereby deduce a polynomial-size compression scheme from learnability alone. To prove this, we use Yao’s minimax principle against deterministic learners under a carefully chosen hard prior. In particular, we select the following prior: Starting from a shattered set X, we choose a random hidden positive set U ⊆ X of size Θ( M ), let the target be the indicator of U, and let the example oracle draw uniformly from U, where M = m(d, ε, δ). Thus, to achieve one-sided error with nontrivial coverage, the learner must recover most of the hidden set U using only positive examples from U and at most M adaptive membership queries, which turns out to be impossible unless | X | = O( M). This implies that VC(Hd ) ≥ | X | = O( M) ≥ m(d, ε, δ). 1.2.3
Overview of Learning Halfspaces in d-dimensional Euclidean Space
In this section, we give an overview of our algorithm for learning halfspaces. As we have mentioned before, for halfspaces to be learnable in Valiant’s model, it is crucial to use membership queries, as without these queries halfspaces are not learnable [Nat87; Shv90]. One also needs to use positive examples because the class of halfspaces is an infinite class, and a result of Kulkarni, Mitter, and Tsitsiklis [KMT93] implies that with just membership queries, we can only learn finite classes (even if we remove the one-sided error requirement and allow for two-sided error). Our learning algorithm is based on a simple observation inspired by our characterization via compression schemes. Overview for d = 2. Suppose d = 2 and consider m positive examples S for an unknown target halfspace h⋆ . For any S, there is a set of just three points that certifies all of S (regardless of how large m is). To see this, construct the convex hull C of S and let its vertices be v1 , v2 , . . . , vm′ . Observe that there are exactly two facets or edges incident on each vertex vi , and form a triangle Ti by extending these two edges and then selecting a third line passing through one of the other vertices and enclosing the entirety of C. By construction, for each 1 ≤ i ≤ m′ , Ti ⊇ C. Then, the key observation is that, for at least one choice of 1 ≤ i⋆ ≤ m′ , the triangle Ti⋆ also satisfies Ti⋆ ⊆ supp(h⋆ ). To see this, imagine sliding a line parallel to the boundary of h⋆ toward C until it first touches the convex hull. Since C is a polygon, this first contact occurs at some vertex vi⋆ , and for this choice of i⋆ the two edges incident on vi⋆ form a wedge that is a subset of supp(h⋆ ). One can then choose the third line so that the resulting triangle Ti⋆ still contains C while remaining inside supp(h⋆ ). 10
If we knew i⋆ , we would be done (at least for d = 2), as we can simply query the three vertices of Ti⋆ , which gives us a query compression scheme of size three, and then output the closure of this scheme (which is a triangle, in fact, simply Ti⋆ ). This is sufficient because (1) one-sided error is guaranteed since Ti⋆ ⊆ supp(h⋆ ) and (2) a bound on the false-negative rate follows because the output of this learner is always a triangle, and the class of triangles has O(1) VC dimension and, hence, generalizes. Of course, the index i⋆ is unknown. We are able to overcome this because of the useful property that the condition Ti ⊆ supp(h⋆ ) can be certified using membership queries (this uses the convexity of supp(h⋆ ) and the fact that Ti is a closure over the class of hypotheses for three queries on its vertices). This then allows us to iterate over each 1 ≤ i ≤ m′ and output the first Ti that passes the check. This algorithm uses at most 3m′ ≤ 3m queries and, using standard VC analysis, we can bound the required number of positive samples by O((log 1/δ)/ε). Additional challenges in d > 2. A natural analog of this algorithm in high dimensions would form the convex hull C of the positive samples S, and iterate over its vertices v1 , v2 , . . . , vm . For each vertex vi , it would form a cone by picking all the facets F (vi ) incident on vi and then, as before, closing it off with another facet not in F (vi ) to obtain a polytope Pi . This algorithm can also certifiably find a polytope Pi⋆ with the guarantee that C ⊆ Pi⋆ ⊆ supp(h⋆ ), and this does indeed guarantee one-sided error for Pi⋆ . However, unlike the case for d = 2, where |F (vi )| = 2, here the number of incident facets can be as large as mO(d) . Hence, the corresponding class of outputs has VC dimension that grows with this complexity, so we do not obtain any useful generalization bound depending only on d. To overcome this, we simplify the set of outputs of this algorithm by not picking all facets adjacent to a vertex vi , but only a subset J of d facets with linearly independent normals; this suffices to ensure that the resulting wedge is full dimensional, after which we close it off with a final facet. There are several such choices of J, and due to certain examples, it turns out that we may need to iterate over all of them in order to find one for which the resulting polytope is a subset of supp(h⋆ ). Hence, we now need to index by both i and J, Pi,J . Since we have only removed facets, the guarantee that Pi,J ⊇ C continues to hold. Since each Pi,J is defined by d + 1 facets, it is a simplex and has a much smaller VC dimension of poly(d). A second challenge is that, for any vertex vi , the number of choices of the subset J can still 2 be as large as mO(d ) , and, since certifying each Pi,J requires d + 1 queries, a naive search will require exponentially many queries in d to find Pi⋆ ,J ⋆ . Here we are able to reduce the number of queries required to be polynomial in d by observing that the problem we are solving is equivalent to a point-location problem in which we must determine the labels of a finite set X of candidate witness points with respect to the unknown halfspace; recent point-location results imply that this e (d log | X |) queries [HKLM20]. can be done using only O
1.3
Takeaways, Discussion, and Open Problems
This work gives the first characterization of Valiant’s original learning model. In particular, we show that, despite its close connections to PAC learning and to positive-only learning without queries, learnability in this model is governed by a different combinatorial principle. Along the way, we introduce adaptive-query compression schemes (Definition 2), a querybased analogue of sample compression that may be useful more broadly in settings where learners receive examples and also have access to membership queries. We also introduce the class of k11
query closures (Equation (1) and Definition 14), which plays a key role in our proof and may be of independent interest in other one-sided or interactive learning problems. We view these results as a starting point. They raise a number of natural questions at the intersection of learning theory, query learning, and the theory of one-sided inference. The most immediate question is to characterize learnability in Valiant’s model beyond finite domains. While we obtain clean necessary and sufficient conditions over arbitrary domains, these are not tight, and so a full characterization remains open. Open Problem 1. What is the characterization of learnability in the extension of Valiant’s model to arbitrary infinite domains? Our characterization over finite domains is also quantitative: it characterizes the sample complexity of learning in Valiant’s model up to polynomial factors. A natural direction is to obtain a tight characterization of sample complexity, say up to logarithmic factors. Open Problem 2. What is the tight characterization of sample complexity of learning in Valiant’s model over Boolean domains? A third direction concerns the computational complexity of learning in this model. Our halfspace result over Rd shows that membership queries can fundamentally enlarge what is learnable in the general-domain setting. However, the algorithm we obtain is not polynomial time. This leads to the following question: Open Problem 3. Is there a polynomial-time algorithm for learning halfspaces in Valiant’s model? Finally, even at the information-theoretic level, our understanding of halfspaces is incomplete. There remains a substantial gap between the sample and query complexity achieved by our algorithm and the lower bounds we can currently prove. Open Problem 4. What are the optimal sample and query complexities for learning halfspaces in Valiant’s model? More broadly, it would be interesting to understand whether the structural notions that arise in our analysis, most notably adaptive-query compression schemes, can be useful beyond Valiant’s model itself.
1.4
Related Work
In this section, we present some further related work. We note that, given the vast amount of work on PAC learning, we cannot hope to survey all the work. For a comprehensive treatment of this setting, see, e.g., [KV94; Vid03; SB14; MRT18]. Learning from positive examples. There is a long line of work on learning from positive data, going back at least to Gold’s seminal model of language identification in the limit, where the learner is presented with a text, i.e., an arbitrary enumeration of the target “language” containing only positive examples [Gol67]. This viewpoint was developed further in the rich literature on inductive inference from positive data, e.g., Angluin [Ang79; Ang80]. Closer to our setting is the work of Natarajan [Nat87], who studied the special case of Valiant’s model without membership queries and characterized proper learnability from positive examples alone. Subsequently, 12
Shvaytser [Shv90] and Kivinen [Kiv95] completed this picture for improper learners and established sharp sample complexity bounds. These results paint a largely negative worst-case picture: even fundamental classes such as two-dimensional halfspaces are not learnable from positive samples alone. To bypass this bottleneck, a substantial line of work has studied positive-only learning under additional structural or distributional assumptions, often for specific hypothesis classes and typically under the uniform distribution on the Boolean hypercube or under Gaussian distributions; see, e.g., [FJK96; NR09; AGR13; DDS15; KTZ19; CDS20; JKV23; LMZ24; MB25; LMZ26] (also see [Meh26]). More broadly, learning from positive samples also arises in modern contexts motivated by (1) generative modeling – where training typically involves only valid text and there is no canonical distribution over invalid outputs [KM24; KMV25] – and (2) treatment-effect estimation in observational studies beyond unconfoundedness, which can be formulated as mean estimation from positive-only samples [CKMMZ25]. Learning from queries. There is a long and rich line of work on learning from different types of queries, starting with early work from Angluin [Ang88]. In the PAC learning literature, queries are most commonly studied in the form of active learning, where the learner observes a stream of unlabeled i.i.d. data and can ask membership queries for their labels [CAL94; BBL06; Han09; BHV10; Das11]. Learning through compression schemes. Compression schemes have been highly influential in learning theory, going back to the foundational work of Floyd and Warmuth [FW95], who connected compression to PAC learnability. Subsequently, Warmuth [War03] asked whether every class of VC dimension d admits a compression scheme of size O(d). This became one of the most extensively studied questions in learning theory. Moran and Yehudayoff [MY16] gave the first general compression bound that depends only on the VC dimension: every binary concept class of VC dimension d admits a sample compression scheme of size 2O(d) . This established the equivalence between binary PAC learnability and bounded-size sample compression. This line of work has since been extended in several directions, including efficient learner-to-compression conversions and compression for real-valued learners [HKS19]. On the negative side, Chase et al. [CCHMY24] identified limitations of one of the major approaches to the VC-size compression conjecture: embedding arbitrary VC classes into extremal classes of comparable dimension. Beyond binary classification, Pabbaraju [Pab24] showed that the analogue fails in the multiclass setting: learnability does not imply bounded-size sample compression as a function of DS dimension alone. Learning halfspaces with random examples and queries. There is a large body of work on learning halfspaces with random examples (typically both positive and negative examples) and binary-response queries (typically using, in addition to membership queries, other query types such as equivalence or label queries), e.g., [Bau91; BCGS98; KP98; BBZ07; BL13; GSS13; ABL17; YZ17; Zha18; ZSA20; DKM24; LZ24]. To the best of our knowledge, in the more relevant setting where the learner sees only positive examples and has access only to membership queries, the only prior work we are aware of is Goldberg and Kwek [GK00]. There are also the following implications for halfspaces: The set of halfspaces with bounded finite bit-complexity (which is a finite class) can be learned exactly (and, hence, also with one-sided error) using poly(d) membership queries and a single arbitrary positive example. Thus, to the best of our knowledge, our result on halfspaces is the first to learn halfspaces, without requiring assumptions on bit-complexity, in Valiant’s model. 13
2
Preliminaries
In this section, we collect notation and background used throughout the paper. Notation. Logarithms are base two throughout. We use calligraphic letters (such as D and P) for distributions over a domain X. When X is finite or countably infinite, D(·) denotes the probability mass function. When X is uncountable, for simplicity, we assume that D has a density and use the same notation for that density. We write supp(D) := { x ∈ X : D( x ) > 0} for the support of D. For a hypothesis h : {0, 1}d → {0, 1}, we write supp(h) := { x ∈ {0, 1}d : h( x ) = 1}. Given a statement E, we write 1{ E} for its indicator. Example and Membership Oracles. We work in the realizable binary classification setting. The domain is X = {0, 1}d , the target belongs to a concept class H ⊆ {0, 1}X , and D is a distribution over X. In Valiant’s model, the learner only receives positive examples from the target concept. To formalize this, we introduce the following notion of compatibility. Definition 4 (Compatibility). A distribution D over X is compatible with a concept h : X → {0, 1} if every point in the support of D is positive for h; equivalently, supp(D) ⊆ supp(h) := { x ∈ X : h( x ) = 1} . Thus, if D is compatible with a target hypothesis h⋆ , then every draw from D is a positive example for h⋆ . The learner is given access to a positive-example oracle and a membership oracle, defined as follows. Definition 5 (Example Oracle). An example oracle for D is a primitive that outputs x ∼ D on each query. Definition 6 (Membership Oracle). A membership oracle for h : X → {0, 1} is a primitive that, on input x ∈ X, returns the label h( x ).
2.1
Discussion of Valiant’s Model of Learning
There are several differences between Valiant’s model (Definition 1) and the usual PAC model for binary classification over arbitrary domains [BFKV98; SB14]. First, Definition 1 requires one-sided error: the output hypothesis must have no false positives. This is a strong constraint: even if one is given an ε-cover of Hd in the usual sense, it does not suffice for learning, since the covering hypotheses may introduce false positives. Second, the sample and query complexities are required to be polynomial in the ambient dimension d, whereas the PAC model only requires them to be finite [BFKV98; SB14]. This requirement is essential: for each fixed d, the domain {0, 1}d has size 2d , so exhaustively querying the membership oracle trivially learns any concept; without the polynomial requirement, the definition would be vacuous on finite domains, and, hence, requiring poly(d) samples and queries is the standard modeling choice for learning problems over the Boolean hypercube [KV94]. Third, unlike the PAC model where the feature distribution is arbitrary and unrelated to the target hypothesis, here the distribution D is required to be compatible with h⋆ , i.e., the learner only receives positive examples. Lastly, compared to work on active learning, the learner is allowed to query the label of arbitrary points of the domain. These differences place Valiant’s model outside the reach of the existing machinery and require us to explore new ideas.
14
The above model differs from Valiant’s original formulation in two respects: First, Valiant required the learning algorithm to be proper (i.e., its output was required to be in Hd ) and, second, he required the learner to run in polynomial time. We drop both requirements to develop a general theory, as both are known to complicate characterizations of learnability. Indeed, while sample-efficient learnability has been characterized in the PAC, online, and active learning models, among others [Lit88; BEHW89; Han14], no comparably general characterization of computationally efficient learnability is known in any of them. Further, requiring properness can make it much harder to obtain a clean general theory. This already happens in closely related PAC-style settings: for instance, in multiclass classification, a characterization of proper learning is known to be undecidable under ZFC [ADDST25]. Valiant’s original definition used a single parameter ε, for both the failure probability and the allowed false-negative mass. We separate them into ε and δ, since we require this flexibility in our proofs. We show that after appropriately boosting a weak learner, the sample and query complexities depend at most linearly on 1/ε (up to logarithmic factors) and logarithmically on 1/δ (see Theorem 3.4). Finally, for some of his results, Valiant allowed the features to be undetermined (partial assignments); for simplicity, we focus on total assignments over {0, 1}d .
2.2
Adaptive Query Strategies and Version Spaces
In Valiant’s model, the learner’s queries to the membership oracle may be adaptive: the i-th query may depend on all previously observed positive examples and past query-response pairs. We reserve q = (q1 , . . . , qt ) for a finite sequence of queried points in {0, 1}d and r = (r1 , . . . , rt ) for the corresponding responses. For a hypothesis h : {0, 1}d → {0, 1}, we write h(q) := (h(q1 ), . . . , h(qt )) . Definition 7 (Adaptive Query Strategy). Fix d ∈ N. A deterministic adaptive query strategy σ of depth at most t is a rooted binary tree of depth at most t whose internal nodes are labeled by points of {0, 1}d . The root label is the first query; if the current node is labeled qi and the response is ri ∈ {0, 1}, the strategy follows the left child when ri = 0 and the right child when ri = 1. For any response sequence r realized along a root-to-leaf path of σ, we write q(σ, r ) for the corresponding sequence of queried points on that path. When discussing randomized learners, we condition on their internal randomness and work with deterministic strategies. Remark 2.1 (Positive Examples May Be Collected First). Suppose a learner satisfying Definition 1 makes at most m(d, ε, δ) calls to the example oracle and at most the same number of calls to the membership oracle. Then, without changing its guarantee, we may assume that it first requests m(d, ε, δ) independent draws from the example oracle, stores them, and only then interacts with the membership oracle. This is because the transformed learner can simulate the original one. Hence, without loss of generality, one can assume that the learner first observes its entire positive sample and then, after fixing its internal randomness, runs a deterministic adaptive query strategy. A version space is the set of hypotheses consistent with the information revealed so far; this notion recurs throughout the paper. Definition 8 (Version Spaces). Fix d ∈ N. We introduce two associated version spaces: 1. For a finite set S ⊆ {0, 1}d , the positive-sample version space is V(S) := { h ∈ Hd : S ⊆ supp(h)} . 15
2. For a query sequence q and response sequence r, the query-transcript version space is V(q, r ) := {h ∈ Hd : h(q) = r } . Thus, the hypotheses consistent with both a positive sample S and a query transcript (q, r ) are precisely V(S) ∩ V(q, r ) . If T = {(q1 , r1 ), . . . , (qt , rt )} denotes a transcript, we write V( T ) := V(q, r ). Likewise, for a deterministic adaptive query strategy σ and a realized response sequence r, V(σ, r ) := V(q(σ, r ) , r ) .
2.3
(2)
VC Dimension and One-Centered Star Number
Next, we introduce relevant dimensions from learning theory that we will reference throughout. Definition 9 (VC Dimension [VC71; VC74]). The Vapnik–Chervonenkis (VC) dimension of H, denoted VC(H), is the largest integer k for which there exists a set of points { x1 , . . . , xk } ⊆ X that is shattered by H, i.e., h( x1 ), . . . , h( xk ) : h ∈ H = {0, 1}k . If no such finite k exists, then VC(H) = ∞. In other words, if VC(H) = k, then there exists a set of k points X = { x1 , x2 , . . . , xk } such that every pattern on the points X can be realized by some hypothesis h in the hypothesis class H. However, no set of size k + 1 is shattered. Definition 10 (Star Number [HY15]). For any concept class H ⊆ {0, 1} X and any function h : X → {0, 1} (not necessarily in H), the star number of H centered at h, denoted sh (H), is the largest integer k for which there exist points x1 , . . . , xk ∈ X such that for each i ∈ {1, . . . , k } there is a concept hi ∈ H satisfying ( h ( x j ), j ̸= i, hi ( x j ) = 1 − h ( x j ), j = i , and there is also a concept h0 ∈ H with h0 ( xi ) = h( xi ) for all 1 ≤ i ≤ k. If no such finite k exists, then sh (H) = ∞. Intuitively, the star number captures a notion of “local disagreement capacity.” Given a reference labeling h, it counts how many hypotheses in H can make exactly one “surgical edit” to h’s predictions, with no two hypotheses editing the same point. The star number has found a number of applications in active learning. Recently, Hanneke [Han24] identified and studied the specific star number defined by the all-one hypothesis, which they termed the 1-centered star number. Definition 11 (1-Centered Star Number [Han24]). Let 1 : X → {0, 1} be the constant-1 function. The 1-centered star number of H is denoted by s1 (H). The 1-centered star number is particularly interesting for us due to the following connection, found by Hanneke [Han24], between s1 (H) and the VC dimension of the intersection closure of H.5 Theorem 2.2 (Theorem 19 of [Han24]). For any concept class H ⊆ {0, 1}X , the smallest VC dimension of any class H containing H that is closed under intersections is s1 (H). 5 The intersection closure of a class H is the smallest class containing H that is closed under finite intersections.
16
The results of Natarajan [Nat87] and Shvaytser [Shv90], expressed in the notation of star numbers, lead to the following characterization of learnability in the special case of Valiant’s model in which no membership queries are allowed. Theorem 2.3 (Natarajan [Nat87] and Shvaytser [Shv90] Combined with Theorem 2.2). A sequence of concept classes H = (H1 , H2 , . . . ) is learnable in Valiant’s model without membership queries if and only if there is a polynomial q(·) such that s1 (Hd ) = q(d) for each d ∈ N. Next, we turn to our results that characterize Valiant’s model in its full generality.
3
Characterization of Learnability
In this section, we prove Theorem 1.1, which we restate below. Theorem 1.1 (Characterization). A sequence of concept classes H = (H1 , H2 , . . . ) is learnable in Valiant’s model if and only if every realizable positive sample S ⊆ {0, 1}d admits an adaptive-query compression scheme of size poly(d).
3.1
Additional Discussion of Query-Compression and Characterization
Before proving Theorem 1.1, in this section, we collect some useful remarks. Remark 3.1 (Extension to Any Finite Domain). Our proof of Theorem 1.1 naturally extends beyond the Boolean hypercube to any finite domain, where learnability is defined as follows: Fix a sequence of domains X = (X1 , X2 , . . . ) with |X N | = N for each N ∈ N, and fix a corresponding sequence of concept classes H = (H1 , H2 , . . . ). Then, H is learnable if there is a learner satisfying the requirements of Definition 1 with m( N, ε, δ) = poly(log N, 1/ε, 1/δ). The reason is that the proof of Theorem 1.1 uses the Boolean-cube structure only through two counting bounds, neither of which is essential: • To obtain compression schemes from learnability, the proof of Theorem 3.7 uses Sauer– Shelah’s lemma to bound the size of the class; over an N-point domain, this gives log |HN | ≤ O(VC(HN ) log N ). Together with Theorem 3.10, this yields a weak compression scheme of size poly(log N ), and then Theorem 3.6 upgrades it to a full query-based compression scheme of size poly(log N ) (where we used that log |S| ≤ log N). • To deduce learnability from compression schemes, the proof of Theorem 3.9 only needs a bound on the size of the k-query closure class. Over an N-point domain, a labeled query transcript of length t has at most (2N )t possibilities, so |Clk (HN )| ≤ ∑kt=0 (2N )t ≤ (2N )k+1 , and hence VC(Clk (HN )) ≤ O((k + 1) log N ). The same uniform-convergence argument then yields learnability from compression with dependence polynomial in log N. Thus the entire characterization carries over verbatim, replacing d by log N throughout. Remark 3.2 (Comparison of Definition 2 to Standard Compression Schemes). Query compression schemes and standard sample compression schemes are incomparable to each other and differ in two respects. First, query compression schemes are more general: a standard compression scheme 17
must compress the labels using only information already contained in the sample, whereas a query compression scheme may request additional information via membership queries. Second, query compression schemes are more restrictive in how labels are recovered: a standard compression scheme may reconstruct labels by any means, whereas here we require that the labels be forced by the version-space closure of the transcript. To see why this stronger requirement is needed, observe that in Valiant’s model the learner only observes positive examples. Under the usual notion of compression, any all-positive sample can be trivially compressed by a scheme of size 0: the reconstruction map simply labels every point as positive. This would make compression vacuous, so we instead require that the labels have to be forced by the version space. Remark 3.3 (The Role of Adaptivity). Adaptivity in Definition 2 is essential. Without it, the learner would need to query every node of the strategy tree ΣS , which may contain as many as 2t nodes when ΣS has depth t—far too many for learnability in Valiant’s model, where the complexity must be poly(d). After the interaction, the realized branch consists of only t query-response pairs along a single root-to-leaf path. Hence, the version space certifying S is only defined by these t query-response pairs. One might therefore hope to replace the adaptive strategy by a static list of t queries chosen in advance. However, the key difficulty is that the learner does not know in advance which of the 2t possible paths will be realized, since this depends on the responses of the membership oracle and hence on the unknown target h⋆ . Thus, the queries that are ultimately needed are only determined via interaction with the membership oracle.
3.2
Proof of Theorem 1.1 (Characterization)
In this section, we prove our main result: Theorem 1.1. An outline of the proof appears in Figure 1. 3.2.1
Boosting in Valiant’s Model
We begin by proving a boosting theorem for Valiant’s model. Theorem 3.4 (Boosting for Valiant’s Model). Suppose H is learnable in Valiant’s model (Definition 1), and let mW (d, ε, δ) denote the sample/query complexity of some learner witnessing this. Then, for every ε ∈ (0, 1) and δ ∈ (0, 1/2], there is a learner satisfying the Valiant guarantee with sample/query complexity m(d, ε, δ) = mW (d, 1/18, 1/3) · O
1 1 log ε δ
.
We present the proof of Theorem 3.4 in Appendix B. It uses standard boosting ideas adapted to Valiant’s learning model: First, we reduce the failure probability to δ by taking a majority vote over O(log 1/δ) independent runs. The argument for improving the dependence on ε is a bit more involved: we run O(1/ε) stages of the learner, where in the (i + 1)-th stage we “focus” on the positive samples which are not positively classified by any of the first i hypotheses. To do this, we use rejection sampling and only feed the learner the positive examples that are not positively classified by any of the first i hypotheses. (Since each intermediate hypothesis has no false positives, the resulting residual distribution remains compatible with the target.) Thus, the proof follows the standard boosting template of repeatedly learning the residual distribution, with the main change being how the residual distribution is defined and simulated. 18
Characterization of Learnability Theorem 1.1
Learnability implies query compression
VC(Hd ) ≤ m(d, ε, δ) Theorem 3.10
Theorem 3.6
Compression rate
Existence of weak query compression schemes
Definition 15
Theorem 3.4
Theorem 3.9
VC dimension of kquery closure class Lemma 3.8
Theorem 3.7 Boosting for Valiant’s model
Query compression implies learnability
Uniform success over all potential targets
Weak querybased compression scheme
Theorem 3.5
Definition 13
The k-query closure class Definition 14
Uniform success over all potential targets Definition 12
Figure 1: Outline of the proof of Theorem 1.1. 3.2.2
Uniform Success Over All Potential Targets
In this section, we show that any learnable class in Valiant’s model admits a learner whose output, with high probability, is simultaneously valid for every hypothesis that remains consistent with the realized interaction. Definition 12 (Uniform Success Over All Potential Targets). A learner L has uniform success over all potential targets with sample/query complexity munif (d, ε, δ) if the following holds. For every d ∈ N, ε, δ ∈ (0, 1), target h⋆ ∈ Hd , and distribution D compatible with h⋆ , run L on input (d, ε, δ) with access to the example oracle for D and the membership oracle for h⋆ . Let b h be the output, let S be the realized set of example-oracle samples, and let q, r be the realized membership-query transcript. Then, with probability at least 1 − δ, for every h ∈ V(S) ∩ V(q, r ) with supp(h) ̸= ∅, the hypothesis b h satisfies the conclusions of Definition 1 with target h and distribution Dh , where Dh denotes D conditioned on supp(h) (when D(supp(h)) = 0, Dh can be any fixed distribution supported on supp(h)). The above requirement is closely related to the model of Probably Uniformly Approximately Correct (PUAC) learning introduced by Vidyasagar [Vid03, see Chapters 3, 6, and 7]. In the PUAC model, with probability at least 1 − δ over the random sample, the learner must succeed simultaneously for all potential targets, rather than merely for each fixed target separately (as in the PAC model). Hence, the above requirement strengthens Valiant’s model in the same spirit as PUAC learning strengthens PAC learning. Our next result shows that if a class is learnable in Valiant’s model, then it is learnable by 19
a learner that also enjoys the uniform-success guarantee above. This parallels the equivalence between PAC and PUAC learning for binary classification proved by Vidyasagar [Vid03, Theorem 7.11]. However, that equivalence is obtained via classical uniform-convergence arguments based on suitable covering-number bounds. Because Valiant’s model requires a one-sided guarantee which is not compatible with standard bounds on covering numbers, we prove the corresponding statement from scratch. Theorem 3.5 (Uniform Success Over All Potential Targets). Suppose H is learnable in Valiant’s model, and let m(d, ε, δ) denote the sample/query complexity of some learner witnessing this. Then H admits a learner satisfying Definition 12 with sample/query complexity
δ munif (d, ε, δ) = m d, ε, |Hd |
.
Proof of Theorem 3.5. Fix d ∈ N, ε, δ ∈ (0, 1), a target h⋆ ∈ Hd , and a distribution D compatible with h⋆ (Definition 4). Let δ and δ′ := Nd := |Hd | . Nd Let L be a learner witnessing the learnability of H with sample/query complexity m, and let L ′ be the learner obtained by running L with confidence parameter δ′ . By Remark 2.1, we may assume that L ′ first draws M := m d, ε, δ′ example-oracle samples x1 , . . . , x M , and only then makes adaptive membership queries. Let S := h be the output of L ′ . { x1 , . . . , x M } . Let q, r be the realized membership-query transcript, and let b Fix h ∈ Hd with supp(h) ̸= ∅, and define Dh as in the theorem statement. Define the event n o Eh := h ∈ V(S) ∩ V(q, r ) and b h fails the conclusions of Definition 1 for target h under Dh . We claim that Pr (Eh ) ≤ δ′ . To prove this, condition on the internal randomness ρ of L ′ , so that the ρ ′ learner becomes deterministic; let this learner be Ldeter . Let Ah ⊆ ({0, 1}d ) M be the set of ordered sample sequences x = ( x1 , . . . , x M ) for which the corresponding deterministic run lands in Eh . If ρ x ∈ Ah , then xi ∈ supp(h) for every i, because h ∈ V(S). Also, h(q) = r, because h ∈ V(q, r ). Hence, if we rerun the same deterministic learner with the same ρ, but now with target h and example distribution Dh , then on the same sample sequence x the learner sees exactly the same transcript and therefore outputs the same hypothesis. In particular, this counterfactual run also ρ fails for the compatible pair (h, Dh ). Let Fh ⊆ ({0, 1}d ) M be the set of ordered sample sequences on which this counterfactual deterministic run fails for the pair (h, Dh ). The preceding paragraph ρ ρ shows that Ah ⊆ Fh . Therefore, if D(supp(h)) > 0, then ρ M
Pr (Eh | ρ) = D x ∈ Ah
ρ ρ = D(supp(h)) M · DhM x ∈ Ah ≤ DhM Fh ,
Otherwise, suppose D(supp(h)) = 0. If M ≥ 1, then on the event h ∈ V(S) all M example samples must lie in supp(h), which happens with probability 0 under D. Hence ρ Pr (Eh | ρ) = 0 ≤ DhM Fh .
20
If instead M = 0, then there are no example-oracle samples. On the event h ∈ V(q, r ), the deterministic run with target h and distribution Dh sees exactly the same membership-query transcript as the original run, and therefore outputs the same hypothesis. Thus, ρ Pr (Eh | ρ) ≤ DhM Fh .
Averaging over ρ and using the Valiant guarantee for the randomized learner L ′ on the compatible pair (h, Dh ) gives h i ρ Pr (Eh ) ≤ E DhM Fh = ρ
Pr
ρ, x ∼DhM
L ′ fails on (h, Dh ) ≤ δ′ .
Next, we apply a union bound over all h ∈ Hd with supp(h) ̸= ∅: Pr (∃h ∈ Hd with supp(h) ̸= ∅ such that Eh ) ≤ ∑ Pr (Eh ) ≤ Nd δ′ = δ. h∈Hd
Equivalently, with probability at least 1 − δ, no event Eh occurs. Thus, simultaneously for every h ∈ V(S) ∩ V(q, r ) with supp(h) ̸= ∅, the output b h satisfies the conclusions of Definition 1 for target h under Dh , implying Definition 12. Finally, the result follows since the learner L ′ is simply L run with confidence parameter δ′ = δ/ |Hd |. Hence its sample/query complexity is m(d, ε, δ/|Hd |) .
3.2.3
Learnability Implies Query-Based Compression
In this section, we show that learnability in Valiant’s model yields logarithmic-size query-based compression schemes for realizable positive samples. In other words, along every realizable branch of the strategy Σ, the transcript certifies that every point of S is positive for every hypothesis consistent with that branch. Theorem 3.6 (Learnability Implies Query-Based Compression). Suppose H is learnable in Valiant’s model, and let mW (d, ε, δ) denote the sample/query complexity of some learner witnessing this. Then for every d ∈ N and every nonempty finite set S ⊆ {0, 1}d with V(S) ̸= ∅, there exists a query-based compression scheme ΣS (Definition 2) for S whose compression rate is at most qd · 1 + log3/2 |S| , where qd is as in Theorem 3.7. In particular, qd ≤ mW (d, 1/18, 1/3) · O(d VC(Hd )) . The proof proceeds in two stages. First, we show that every realizable set S admits a weak querybased compression scheme whose transcript certifies a constant fraction of the points in S (Definition 13 and Theorem 3.7). Second, we recurse on the uncertified points. Since each round removes a constant fraction of the unresolved set, the recursion stops after at most O(log |S|) rounds. Definition 13 (Weak Query-Based Compression Scheme). Fix d ∈ N and a finite set S ⊆ {0, 1}d . We say that S admits a weak query-based compression scheme σ if σ is a deterministic adaptive query
21
strategy such that, for every response transcript r of σ that is realizable with respect to V(S), S∩
\
supp(h) ≥
h∈V(σ,r )
1 |S| . 3
When this holds, we also say that σ is a weak query-based compression scheme for S. The constant 1/3 in the above definition is not crucial; it can be replaced by any positive constant. This only changes the hidden constant in (3) and the base of the logarithm in Theorem 3.6. Theorem 3.7 (Existence of Weak Query-Based Compression Schemes). Suppose H is learnable in Valiant’s model, and let mW (d, ε, δ) denote the sample/query complexity of some learner witnessing this. Then for every d ∈ N and every nonempty finite set S ⊆ {0, 1}d with V(S) ̸= ∅, there exists a weak query-based compression scheme σS for S making at most qd membership queries, where one may take qd = mW (d, 1/18, 1/3) · O(d VC(Hd )) .
(3)
At a high level, the proof of Theorem 3.7 puts the uniform distribution on S and runs the learner from the previous subsection—with the uniform guarantee from Definition 12. This immediately gives the right coverage statement: if the learner has false-negative mass at most 2/3 under the uniform distribution on S, then its output contains at least one third of the points of S. The real difficulty is the one-sided guarantee. We do not merely want a hypothesis contained in the true target. Rather, we want a transcript that certifies positivity for every hypothesis that remains consistent with the realized interaction. This is exactly why we need the uniform guarantee from Definition 12: ordinary learnability controls the output only relative to the true target and says nothing about the rest of the version space. A second issue is target-independence. For each h ∈ V(S) there may be a different successful random seed and a different successful sample stream. That is not enough: the final query tree must depend only on S, not on the unknown target. To achieve this, we run the learner with confidence on the order of 1/ |Hd | and take a union bound over all potential targets. The result is a single realization that works simultaneously for every h ∈ V(S). Once such a realization is fixed, the random example stream can be compiled into actual membership queries, turning the randomized learner into a deterministic query strategy. Proof of Theorem 3.7. Fix d ∈ N and a nonempty finite set S ⊆ {0, 1}d with V(S) ̸= ∅. Let US denote the uniform distribution on S. For every h ∈ V(S), the distribution US is compatible with h. By Theorems 3.4 and 3.5, there is a learner Lunif which, on input (d, 2/3, 1/2|Hd |) , satisfies the uniform guarantee from Definition 12 and uses at most mW (d, 1/18, 1/3) · O(log |Hd |) example-oracle calls and at most the same number of membership queries. Since Hd is a class over a domain of size 2d , Sauer–Shelah’s lemma implies log |Hd | = O(d VC(Hd )) (see, e.g., ShalevShwartz and Ben-David [SB14]). Choose qd ≥ 1 satisfying (3) and large enough to absorb the factor 2 incurred below when example-oracle calls are compiled into membership queries.
22
A Single Successful “Run” for All Targets in V(S). Let ρ denote the internal randomness of Lunif together with an i.i.d. example stream from US . For each target h ∈ V(S), let Gh be the event that, when Lunif is run with target h, distribution US , and realization ρ, it satisfies the conclusion of Definition 12 (i.e., it succeeds for all other potential targets h′ which remain consistent with the 1 transcript and samples). Then for every such h, Pr(Gh ) ≥ 1 − 2|H . Hence, by the union bound, | d
Gh ≥ 1 −
\
Pr
h∈V(S)
1 |V(S)| ≥ . 2 |Hd | 2
Therefore there exists a realization ρ⋆ such that every event Gh , for h ∈ V(S), holds simultaneously. Fix such a realization ρ⋆ . A Deterministic and “Successful” Query Strategy. Using the fixed realization ρ⋆ , define a deterministic adaptive query strategy σS by simulating Lunif . Whenever the simulated learner requests its next example, the strategy reads the next point from the hardwired example stream encoded in ρ⋆ , queries that point to the membership oracle, and then feeds the point to the simulated learner as its next example. Whenever the simulated learner requests an ordinary membership query x, the strategy asks the same query x and feeds back the answer. Because every hardwired example lies in S, every target h ∈ V(S) answers 1 on those compiled example queries. Therefore, for every such h, the realized run of σS against the membership oracle for h is exactly the run of Lunif with realization ρ⋆ against target h and distribution US . By the choice of qd , the total number of membership queries made by σS is at most qd . A Weak Compression Scheme. We claim that σS is a weak query-based compression scheme. To see this, fix any response transcript r of σS that is realizable with respect to V(S), and let h⋆ ∈ V(S) be a target realizing r. Let Pr ⊆ S be the set of hardwired example points consumed along this branch, let qr , ar be the ordinary membership-query transcript seen by the simulated learner, and let gbr be the output of the simulation. Then V(σS , r ) = V( Pr ) ∩ V(qr , ar ) . Now ρ⋆ ∈ Gh⋆ , so the corresponding run of Lunif satisfies the uniform guarantee over all potential targets. Since h⋆ ∈ V( Pr ) ∩ V(qr , ar ) and S ⊆ supp(h⋆ ), conditioning US on supp(h⋆ ) leaves US unchanged. Therefore Pr ( gbr ( x ) = 0) ≤
x ∼US
2 , 3
\
supp( gbr ) ⊆
and
supp(h).
h∈V( Pr )∩V(qr ,ar )
The first inequality implies |S ∩ supp( gbr )| ≥ 13 |S| . Further, the second inclusion yields \
supp(h) =
h∈V(σS ,r )
\
supp(h) ⊇ supp( gbr ) .
h∈V( Pr )∩V(qr ,ar )
Hence S∩
\
supp(h) ≥ |S ∩ supp( gbr )| ≥
h∈V(σS ,r )
23
1 |S| . 3
Thus, σS is a weak query-based compression scheme for S. Now we are ready to prove Theorem 3.6. Proof of Theorem 3.6. Let qd be as in Theorem 3.7. Since the bound (3) is asymptotic, we may and do assume qd ≥ 1. For each finite set S ⊆ {0, 1}d with V(S) ̸= ∅, we define a deterministic adaptive query strategy ΣS recursively. Recursive Construction. If |S| ≤ qd , then ΣS queries every point of S and stops. If |S| > qd , then ΣS first runs the weak query-based compression scheme σS from Theorem 3.7. For each response transcript r of this first stage that is realizable with respect to V(S), define IS,r := S ∩
\
supp(h),
and
RS,r := S \ IS,r .
h∈V(σS ,r )
For such an r, any hypothesis in V(S) realizing r also witnesses V( RS,r ) ̸= ∅. On every such branch r, the strategy continues with the recursively defined strategy Σ RS,r . On first-stage branches that are not realizable with respect to V(S), define the continuation arbitrarily, say by stopping. This is well-defined because whenever r is realizable with respect to V(S), the weak-compression guarantee gives | RS,r | ≤ 32 |S| < |S| , so the recursion strictly decreases the size of the unresolved set. Correctness. We prove by induction on |S| that for every finite set S with V(S) ̸= ∅, and every T response transcript r of ΣS that is realizable with respect to V(S), S ⊆ h∈V(ΣS ,r) supp(h). • Case A (|S| ≤ qd ): If |S| ≤ qd , then ΣS queries every point of S, so every hypothesis in V(ΣS , r ) answers 1 on every point of S. Thus the claim is immediate. • Case B (|S| > qd ): Now suppose |S| > qd , and assume the claim has already been proved for all smaller realizable sets. Fix a realizable transcript r of ΣS . Write r = r0 ◦ r1 , where r0 is the first-stage transcript produced by σS . Since r is realizable with respect to V(S), there exists some h⋆ ∈ V(S) realizing r. In particular, h⋆ realizes r0 , so r0 is realizable with respect to V(S). Let I := IS,r0 , and R := RS,r0 . Because h⋆ ∈ V(S), we have S ⊆ supp(h⋆ ) and therefore R ⊆ supp(h⋆ ). Thus V( R) ̸= ∅, and by construction, the suffix r1 is a realizable transcript of the recursive strategy Σ R with respect to V( R) and | R| < |S| by the definition of the weak compression scheme σS . Thus, by the induction hypothesis, \ R⊆ supp(h). h∈V(Σ R ,r1 )
Now let h be any hypothesis in V(ΣS , r ). Since h is already consistent with the first-stage transcript r0 , it lies in V(σS , r0 ) and therefore contains I by definition of I. Also, since the continuation on branch r0 is Σ R , the same hypothesis h lies in V(Σ R , r1 ), and therefore contains R by the
24
induction hypothesis. Hence h contains I ∪ R = S. Since this holds for every h ∈ V(ΣS , r ), the induction is complete. Compression Rate. Each nonterminal stage uses at most qd queries and reduces the unresolved set by a factor of at most 2/3. Starting from a nonempty set of size n, after t := log3/2 n such stages, the unresolved set has size at most n (2/3)t ≤ 1 ≤ qd , so the next stage is terminal. Hence the total number of queries made by ΣS is at most qd · 1 + log3/2 |S| . Finally, Theorem 3.7 provides the desired upper bound on qd , completing the proof.
3.2.4
Query-Based Compression Implies Learnability
In this section, we prove the converse direction: query-based compression schemes yield learners in Valiant’s model. This mirrors the classical fact that sample compression implies PAC learnability [LW86; FW95]. As we have seen, a natural hypothesis to output after compression is the closure of the realized transcript, and so the key object to control is the class of all sets that can arise as such closures. Definition 14 (k-Query Closure Class). Fix d, k ∈ N. The k-query closure class of Hd is \ Clk (Hd ) := supp(h) : q, r have the same length t ≤ k and V(q, r ) ̸= ∅ . h∈V(q,r )
Each set in Clk (Hd ) is obtained by intersecting all hypotheses in Hd that remain consistent with a given transcript. However, this is quite different from the usual k-fold intersection class
{supp(h1 ) ∩ · · · ∩ supp(hk ) : h1 , . . . , hk ∈ Hd } . For ordinary k-fold intersections, the VC dimension is known to be O(VC(Hd ) k log k ), and this order is tight in general [BEHW89; EA07]. In contrast, a query closure intersects the entire version space after a transcript: the number of intersected concepts is not fixed in advance, can vary from branch to branch, and over infinite domains can even be infinite. To gain some intuition, consider monotone conjunctions on {0, 1}d . If a transcript consists only of positive answers on points x (1) , . . . , x (t) , then the corresponding closure is the upwardclosed set determined by the coordinates that are 1 in every x (i) . So even a short transcript can encode a closure obtained by intersecting many hypotheses at once. Despite this, the situation remains manageable on the finite domain {0, 1}d because the entire closure class is indexed by transcripts, and we can bound the number of distinct transcripts of length at most k. Later we will see that over general domains the behavior can be much wilder; in particular, even one-point query closures can have infinite VC dimension despite the base class having VC dimension at most two; see Theorem A.11. Lemma 3.8. For every d, k ∈ N, |Clk (Hd )| ≤ 2(d+1)(k+1) . Consequently, VC(Clk (Hd )) ≤ (d + 1)(k + 1).
25
Proof of Lemma 3.8. For each t ∈ {0, 1, . . . , k }, a labeled query transcript of length t is a sequence of t t t pairs (qi , ri ) ∈ {0, 1}d × {0, 1}. Hence there are at most {0, 1}d × {0, 1} = 2d · 2 = 2(d+1)t possible transcripts of length t. Each transcript determines at most one element of Clk (Hd ), so k
|Clk (Hd )| ≤ ∑ 2(d+1)t ≤ 2(d+1)(k+1) . t =0
Before stating our result, we need to define the compression rate of a query-based compression scheme: Definition 15 (Compression Rate). Fix a concept class H = (H1 , H2 , . . . ). If for each S with V(S) ̸= ∅, there is a query-based compression scheme Σ for S that makes at most k = κ (|S|) membership queries, we say that the compression rate for H is κ. Theorem 3.9 (Query-Based Compression Implies Learnability). Suppose that for each d ∈ N, the class Hd has a nondecreasing query-based compression rate κd : N → N in the sense of Definition 15. Then there is a learner with the following guarantee. For every ε, δ ∈ (0, 1), every target h⋆ ∈ Hd , and every distribution D compatible with h⋆ , for any n≥Ω
(d + 1) (κd (n) + 1) + log 1/δ ε
the learner uses exactly n example-oracle calls and at most κd (n) membership queries and, with probability at least 1 − δ, outputs a hypothesis satisfying Definition 1. In particular, m(d, ε, δ) = n + κd (n) is a valid sample/query complexity bound. In particular, if κd (n) = qd · 1 + log3/2 n , then
dqd + log 1/δ m(d, ε, δ) = O · log ε
dqd + log 1/δ ε
.
The learner in the above result first compresses the sample S and outputs the closure of the realized transcript. Then two properties are immediate: the closure has no false positives (because the true target is consistent with its own transcript), and it has zero empirical false-negative error (because the compression scheme certifies that every sampled point lies in the closure). The proof therefore reduces to a uniform convergence argument over the closure class Clk (Hd ), which holds due to Lemma 3.8. Proof of Theorem 3.9. Fix d ∈ N, ε, δ ∈ (0, 1), a target h⋆ ∈ Hd , and a distribution D compatible with h⋆ . Let n be any integer satisfying the displayed lower bound in the theorem, draw an ordered sample x1 , . . . , xn ∼ D, and let S := { x1 , . . . , xn } be the underlying set of distinct sample points. Since D is compatible with h⋆ (Definition 4), every sample point is positive for h⋆ , and hence h ⋆ ∈ V ( S ). Learning Algorithm. The learning algorithm runs a query-based compression scheme ΣS for S of size at most κd (|S|) ≤ κd (n) against the membership oracle for h⋆ . Let rS be the realized response 26
transcript. It outputs the indicator of the set CS :=
\
supp(h).
h∈V(ΣS ,rS )
One-Sided Error. Since h⋆ generated the transcript rS , we have h⋆ ∈ V(ΣS , rS ) and hence CS ⊆ supp(h⋆ ) . So the output has no false positives. Also, because ΣS is a query-based compression scheme for S, S ⊆ CS . Therefore every sample point lies in both CS and supp(h⋆ ), and so the empirical symmetric-difference error of CS relative to supp(h⋆ ) is zero. Bound on False-Negative Rate. Because ΣS makes at most κd (n) queries, we have CS ∈ Clκd (n) (Hd ) . Let and Fd,n := {C △ supp(h⋆ ) : C ∈ Clkn (Hd )} . k n := κd (n) Then |Fd,n | = |Clkn (Hd )|. By the second-order uniform convergence bound from [BBL05, Theorem 5.1 and Eq. (15)], with probability at least 1 − δ, every set F ∈ Fd,n with zero empirical measure on x1 , . . . , xn satisfies O(log |Fd,n | + log 1/δ) D( F ) ≤ . n Applying this to FS := CS △ supp(h⋆ ) and using Lemma 3.8, we obtain with probability at least 1 − δ that D(CS △ supp(h⋆ )) ≤
O(log |Clkn (Hd )| + log 1/δ) O((d + 1)(k n + 1) log 2 + log 1/δ) ≤ ≤ ε, n n
where the last inequality holds by the choice of n. Since CS ⊆ supp(h⋆ ) and supp(D) ⊆ supp(h⋆ ), Pr (CS ( x ) = 0 and h⋆ ( x ) = 1) = D(supp(h⋆ ) \ CS ) = D(CS △ supp(h⋆ )) ≤ ε.
x ∼D
Thus, with probability at least 1 − δ, the output satisfies the guarantees in Definition 1. The learner uses exactly n example-oracle calls and at most κd (n) membership queries, proving the first part of the theorem. Logarithmic Compression Rate. Suppose now κd (n) = qd · 1 + log3/2 n . Let A :=
d (qd + 1) + log 1/δ , ε
and choose n := ⌈c′ A log (c′ A)⌉ for a sufficiently large absolute constant c′ > 0. Then κd (n) + 1 ≤ c′′ (qd + 1) log(n + 1) for an absolute constant c′′ , and hence
(d + 1) (κd (n) + 1) + log 1/δ ≤ c′′′ ( A log(n + 1) + A) ε for another absolute constant c′′′ . Since log(n + 1) = O(log A) for this choice of n, the right-hand 27
side is at most n/c once c′ is chosen large enough relative to c, c′′ , c′′′ . Thus the displayed condition of the theorem holds. Moreover, κd (n) = O((qd + 1) log A) ≤ O( A log A) = O(n) , so both the example-oracle and membership-query complexities are at most
d (qd + 1) + log 1/δ · log O(n) = O ε
3.2.5
d (qd + 1) + log 1/δ ε
.
A VC Lower Bound for Learnability in Valiant’s Model
In this section, we show that learnability in Valiant’s model requires sample/query complexity at least linear in the VC dimension. Theorem 3.10 (VC Lower Bound for Valiant’s Model). Suppose H = (H1 , H2 , . . . ) is learnable in Valiant’s model with sample/query complexity m(d, ε, δ). Then for every d ∈ N and every ε, δ ∈ (0, 1/2), VC(Hd ) − 1 . 9
m(d, ε, δ) ≥
In particular, if H is learnable in Valiant’s model, then VC(Hd ) = poly(d). Proof of Theorem 3.10. Fix d ∈ N, ε ∈ (0, 1/2), and δ ∈ (0, 1/2). Set M := m(d, ε, δ) ,
k := 4M + 1,
and
n := 2k + M = 9M + 2.
Suppose toward a contradiction that VC(Hd ) ≥ n. Then there exists a set X ⊆ {0, 1}d of size n shattered by Hd . Hard Prior. For each subset U ⊆ X of size k, let hU ∈ Hd be a hypothesis satisfying hU ( x ) = 1{ x ∈ U }
for every x ∈ X.
(This hypothesis exists since X is VC-shattered.) Let DU be the uniform distribution on U; then DU is compatible with hU . Now choose U uniformly at random among all k-subsets of X, and let the target/distribution pair be (hU , DU ). By Yao’s minimax principle, it suffices to show that every deterministic learner that makes at most M example-oracle calls and at most M membership queries fails with probability at least 1/2 against this prior. Fix such a deterministic learner L . Padding with ignored queries if necessary, we may assume that L makes exactly M example-oracle calls and exactly M membership queries. We may also assume that all M example-oracle samples are revealed before any membership query is asked, since this can only help the learner. Let P = ( x1 , . . . , x M ) ∈ X M be the ordered sample sequence, and let P := { x1 , . . . , x M } be the corresponding set of distinct sampled points. Fix an arbitrary realization P0 ∈ X M , and let r := 28
P0 . Conditioned on P = P0 , the hidden set U is uniform over V ⊆ X : |V | = k and P0 ⊆ V . Indeed, for every V ⊆ X of size k, Pr ( P = P0 | U = V ) = k− M · 1 P0 ⊆ V , and the prior on U is −r uniform. Hence, conditioned on P = P0 , there are exactly (nk− r ) possible hidden sets given P = P0 . Since r ≤ M and −r −1 (nk− k−r r −1 ) = < 1, n −r n−r ( k −r ) this quantity is minimized when r = M. Therefore, for every P0 , # {possible U’s given P = P0 } ≥
n−M k−M
=
8M + 2 . 3M + 1
(4)
Upper Bound on the Number of Hidden Sets per Transcript. Now fix the sample sequence P0 . Once the sample is fixed, the query phase produces one of at most 2 M response transcripts. For each such response transcript r ∈ {0, 1} M , let HP0 ,r ⊆ X denote the set of points in X that the learner’s output labels as positive after seeing P0 and the response string r. +1 We claim that for any fixed response transcript r, the learner can succeed on at most (7M 2M ) different hidden sets U. Indeed, suppose the learner succeeds on some hidden set U of size k after receiving response transcript r. Since the output has no false positives, we must have HP0 ,r ⊆ U. Since DU is uniform on U and ε ≤ 1/2, the coverage guarantee implies
|U \ HP0 ,r | ≤ εk ≤
k < 2M + 1. 2
Since |U | = k = 4M + 1, it follows that
| HP0 ,r | ≥ k − 2M = 2M + 1. Therefore every successful hidden set U must contain HP0 ,r , which has size at least 2M + 1. The −(2M+1) number of k-subsets of X that contain a fixed (2M + 1)-element subset is at most (nk−( ) = 2M +1) +1 (7M 2M ). This proves the claim. Summing over all 2 M response transcripts, the total number of hidden sets on which the learner can succeed given P = P0 is at most M 7M + 1 2 (5) 2M
It remains to compare the candidate count (4) with the success count (5). Direct calculation shows: +2 (8M 3M +1) +1 (7M 2M )
=
M 7M + 2 + j (8M + 2)! (2M)! =∏ . (3M + 1)! (7M + 1)! 2M +1+j j =0
(8M+2) ( 2M )
M +1 . Therefore, 2 M 7M+1 ≤ 1 8M +2 . +1 Each factor in the product is at least 2, so 3M ( 2M ) 2 (3M+1) 7M +1 ≥ 2
That is, conditioned on any realization P0 , the learner succeeds on at most half of the candidate hidden sets. Therefore Pr (L succeeds | P = P0 ) ≤ 1/2 for every P0 , and averaging over P gives Pr (L succeeds) ≤ 1/2. So every deterministic learner with budget M fails with probability at least 1/2 under the hard prior. This contradicts learnability in Valiant’s model, since δ < 1/2. 29
Therefore our assumption VC(Hd ) ≥ 9M + 2 was false, and so VC(Hd ) ≤ 9M + 1 = 9 m(d, ε, δ) + 1. Applying this with ε = δ = 1/3: if H is learnable in Valiant’s model, then m(d, 1/3, 1/3) = poly(d), and hence VC(Hd ) = poly(d).
3.2.6
Completing the Characterization of Learnability in Valiant’s Model
We now combine the previous sections to obtain a complete characterization of learnability in Valiant’s model. In particular, we prove Theorem 1.1, which we restate below. Theorem 1.1 (Characterization). A sequence of concept classes H = (H1 , H2 , . . . ) is learnable in Valiant’s model if and only if every realizable positive sample S ⊆ {0, 1}d admits an adaptive-query compression scheme of size poly(d). Proof of Theorem 1.1. We prove the two implications separately. (1) ⇒ (2): Assume that H is learnable, and let mW (d, ε, δ) denote the sample/query complexity of some learner witnessing this. By Theorem 3.10, applied with ε = δ = 1/3, we have VC(Hd ) = poly(d). Moreover, Theorem 3.6 implies that for every nonempty finite set S ⊆ {0, 1}d with V(S) ̸= ∅, there is a query-based compression scheme for S of size mW (d, 1/18, 1/3) · O(d VC(Hd ) log(|S| + 1)) . Since |S| ≤ 2d , the factor log(|S| + 1) is O(d). Since both mW (d, 1/18, 1/3) and VC(Hd ) are polynomial in d, the displayed bound is poly(d); this completes the proof of (2). (2) ⇒ (1): Assume now that Condition (2) holds, witnessed by a polynomial q. For each d ∈ N, define κd (n) := q(d) (for all n ∈ N). Then κd is a nondecreasing query-based compression rate for Hd . By Theorem 3.9, H is learnable in Valiant’s model with sample/query complexity dq(d) + log 1/δ dq(d) + log 1/δ · log . O ε ε
4
Proofs of Remaining Results
In this section, we present the proofs of our remaining results.
4.1
Proof of Proposition 1.3 (Positive-Only Learning as the Non-Interactive Special Case)
In this section, we prove Proposition 1.3, which we restate below. Proposition 1.3 (Positive-Only Learning as the Non-Interactive Special Case). If, for each d, the intersection closure of Hd has VC dimension poly(d), then every finite realizable positive sample S ⊆ {0, 1}d admits an adaptive-query compression scheme of size poly(d). Moreover, this scheme can be chosen non-adaptively, and all of its queried points can be taken from S itself.
30
Proof of Proposition 1.3. Let Cd denote the intersection closure of Hd . For R ⊆ S, write I ( R) := T h∈V( R) supp( h ). Choose an inclusion-minimal set T ⊆ S such that I ( T ) = I ( S ). We first construct a query compression scheme. To this end, query every point of T, nonadaptively. Since V(S) ̸= ∅, there exists h⋆ ∈ V(S), and because T ⊆ S, every query in T is answered positively. After this transcript, the consistent hypotheses are exactly V( T ), so the certified set is \
supp(h) = I ( T ) = I (S).
h∈V( T )
Moreover, since every h ∈ V(S) labels every point of S positively, S ⊆ I (S) = I ( T ). Hence these queries indeed certify S. Thus T defines a deterministic query compression scheme for S whose queries are nonadaptive and all belong to S. Now fix any center hypothesis c ∈ V(S) , which exists since V(S) ̸= ∅. We claim that T is a 1-centered star set for Hd , and hence also for Cd . To prove this, fix any t ∈ T. By minimality of T, we have I ( T \ {t}) ̸= I ( T ). In particular, V( T \ {t}) ̸= V( T ) , since equality of these two version spaces would force equality of the corresponding intersections. Therefore we may choose ht ∈ V( T \ {t}) \ V( T ) . Then ht (t′ ) = 1 for all t′ ∈ T \ {t} , while necessarily ht (t) = 0, because otherwise ht would belong to V( T ) . Since also c(t′ ) = 1 for every t′ ∈ T, this proves that T is a 1-centered star set for Hd . Now Hd ⊆ Cd , so the same witnesses show that T is a 1-centered star set for Cd . Because Cd is closed under intersections, Theorem 2.2 (Theorem 19 of Hanneke [Han24]) implies | T | ≤ s1 (Cd ) ≤ VC(Cd ) . Therefore the above query compression scheme has size at most VC(Cd ).
4.2
Proof of Corollary 1.4 (Sandwich between PAC and Positive-Only Learning)
In this section, we prove Corollary 1.4, which we restate below. Corollary 1.4 (Sandwich between PAC and Positive-Only Learning). Fix H and its intersection closure H. The following hold in Valiant’s model. 1. If VC(Hd ) = dω (1) , then H is not learnable. 2. If, for infinitely many d, Hd contains every subset of {0, 1}d , then H is not learnable. In particular, there exists H with VC(Hd ) = 1 for each d ∈ N that is not learnable. 3. There exists a sequence of classes that is learnable even though, for infinitely many d, VC Hd = dω (1) . Below, we state the equivalent version of this theorem using the notation of one-centered star dimension, which we prove below. Corollary 4.1. The following hold for a sequence of concept classes H = (H1 , H2 , . . . ) in Valiant’s model. 1. If VC(Hd ) = dω (1) for infinitely many d, then H is not learnable in Valiant’s model. In particular, if VC(Hd ) ≥ 2Ω(d) for infinitely many d, then H is not learnable. 2. If s1 (Hd ) = 2d for infinitely many d, then H is not learnable in Valiant’s model. In particular, there exists H with VC(Hd ) = 1 for each d ∈ N that is not learnable. 3. There exists a sequence of classes that is learnable even though, for infinitely many d, s1 (Hd ) = dω (1) . 31
Proof of Corollary 4.1. We prove Items 1 to 3 in order. Proof of Item 1. Suppose H is learnable in Valiant’s model. Now fix d, and let B ⊆ {0, 1}d be shattered by Hd , with | B| = m. For each T ⊆ B, let h T ∈ Hd satisfy h T ( x ) = 1 { x ∈ T } for x ∈ B. Since T is realizable, it admits a query compression scheme of size at most q(d); let (q T , r T ) be the query-response transcript realized when this scheme is run against h T . Then, on the one hand, as T the scheme certifies T, T ⊆ B ∩ h∈V(qT ,rT ) supp(h). On the other hand, h T ∈ V(q T , r T ), and hence T T B ∩ h∈V(qT ,rT ) supp(h) ⊆ B ∩ supp(h T ) = T. Thus T = B ∩ h∈V(qT ,rT ) supp(h), so distinct subsets T ⊆ B yield distinct query-response transcripts. Finally, the number of query-response transcripts of length at most q(d) is at most 2O(d·q(d)) . Since there are 2m choices of T ⊆ B, it follows that 2m ≤ 2poly(d) , and hence m ≤ poly(d). Therefore VC(Hd ) ≤ poly(d) for all d. This proves Item 1 by contraposition. Proof of Item 2. Suppose for contradiction that H is learnable in Valiant’s model. By Theorem 1.1, there exists a polynomial q such that every realizable set S ⊆ {0, 1}d admits a query compression scheme of size at most q(d). Since s1 (Hd ) = 2d for infinitely many d, we may fix such a d large enough that q(d) < 2d . Then Hd 1-star shatters X = {0, 1}d . Let g ∈ Hd be the all-one center of this 1-star, and set S = {0, 1}d . Consider any query compression scheme Σ for S, and let r be the transcript realized when Σ is run against g. If some point x ∈ {0, 1}d is not queried, then the corresponding star witness h x lies in V(Σ, r ), since h x agrees with g on every queried point and T differs only at x. But h x ( x ) = 0, so x ∈ / h∈V(Σ,r) supp(h), contradicting that Σ certifies S = {0, 1}d . Thus every query compression scheme for S must query every point of {0, 1}d and so have size at least 2d , contradicting q(d) < 2d . This proves Item 2. Proof of the final sentence in Item 2. For each d ∈ N, define gd ( x ) := 1 for each x ∈ {0, 1}d and for each v ∈ {0, 1}d , define h(v) ( x ) := 1{ x ̸= v} . Let o n Hd := { gd } ∪ h(v) : v ∈ {0, 1}d . Then every singleton {v} is shattered by Hd , since gd (v) = 1 and h(v) (v) = 0, so VC(Hd ) ≥ 1. On the other hand, no two-point set {u, v} can be shattered, since every hypothesis in Hd is negative on at most one point of {0, 1}d . Thus VC(Hd ) = 1 for every d. Moreover, {0, 1}d is a 1-star for Hd centered at gd , with witnesses { h(v) : v ∈ {0, 1}d }, so s1 (Hd ) = 2d . Moreover, for every A ⊆ {0, 1}d , A=
supp h(v) ,
\ v∈{0,1}d \ A
so the intersection closure Hd contains every subset of {0, 1}d . Therefore Item 2 applies, and the sequence H = (H1 , H2 , . . . ) is not learnable in Valiant’s model. Proof of Item 3. For each d ≥ 1, let Nd := 2d−1 , and identify {0, 1}d with [ Nd ] × {0, 1} via the first (d) d − 1 bits and the last bit. For each i ∈ [ Nd ], define hi : {0, 1}d → {0, 1} by (d)
hi ( x, 0) := 1{ x ̸= i }
and
(d)
hi ( x, 1) := 1{ x ≥ i } .
n o (d) Set Hd := hi : i ∈ [ Nd ] . We claim that the sequence H = (H1 , H2 , . . . ) witnesses Item 3. 32
(d)
We first show that H is learnable. Fix d, a target hi⋆ ∈ Hd , and a distribution D compatible (d)
with hi⋆ . Let D0 denote the marginal of D on the first coordinate. Given ε, δ ∈ (0, 1), the learner draws log1/ε + log1/δ m=O ε independent examples ( x1 , y1 ), . . . , ( xm , ym ) ∼ D, lets Z := { x1 , . . . , xm } ⊆ [ Nd ], writes the distinct values of Z as z(1) < · · · < z(r) , and adds sentinels z(0) := 0 and z(r+1) := Nd + 1. By the εnet theorem for intervals, with probability at least 1 − δ every interval J ⊆ [ Nd ] with D0 ( J ) ≥ ε contains at least one sampled coordinate; fix a realization for which this holds. The learner then (d) uses membership queries on the slice [ Nd ] × {1}. Since hi⋆ ( x, 1) = 1{ x ≥ i⋆ }, a binary search (d)
over z(1) , . . . , z(r) finds the smallest index t ∈ {1, . . . , r + 1} such that hi⋆ (z(t) , 1) = 1, with the convention t = r + 1 if all answers are 0. Setting L := z(t−1) and R := z(t) , we have i⋆ ∈ ( L, R]. If R ≤ Nd , the learner asks one additional membership query at ( R, 0). If the answer is 0, then R = i⋆ , (d) so it outputs the exact target hypothesis h R . Otherwise, or if R = Nd + 1, let J := ( L, R) ∩ [ Nd ] and output the hypothesis b h defined by b h( x, 0) = 1{ x ∈ / J}
and
b h( x, 1) = 1{ x ≥ R} ,
where 1{ x ≥ Nd + 1} = 0 by convention. A direct verification shows that b h has no false positives and that every false negative has first coordinate in J. Since J contains no sampled coordinate, the ε-net property gives D0 ( J ) < ε, so the false-negative probability is less than ε. Thus H is learnable in Valiant’s model with sample complexity O((log(1/ε) + log(1/δ))/ε) and O(log(m + 1)) membership queries. We now show that s1 (Hd ) is superpolynomial. Fix any k ≤ Nd − 1 and let Sk := {(1, 0), . . . , (k, 0)}. (d) (d) (d) Then hk+1 labels every point of Sk by 1, while for each t ∈ [k ] the hypothesis ht agrees with hk+1 on Sk \ {(t, 0)} and labels (t, 0) by 0. Thus Sk is a 1-star for Hd . Taking k = Nd − 1, we obtain s1 (Hd ) ≥ Nd − 1 = 2d−1 − 1. Hence s1 (Hd ) = dω (1) for infinitely many d, proving Item 3.
4.3
Proof of Theorem 1.5 (Sandwich between PAC and Positive-Only on General Domain)
In this section, we prove Theorem 1.5, which we restate below. Theorem 1.5 (Sandwich between PAC and Positive-Only Learning). Fix a concept class H ⊆ {0, 1}X and let H denote its intersection closure. The following hold in Valiant’s model over a general domain. 1. If H is learnable with m(ε, δ) positive examples/membership queries, then VC(H) ≤ 9 m(1/3, 1/3) + 1. 2. If |X| = ∞, H contains the constant-one hypothesis, and for every x ∈ X it also contains a hypothesis that labels x zero and every point in X \ { x } positive, then H is not learnable.6 In particular, there exists H with VC (H) = 1 that is not learnable. 6 Equivalently, that H shatters the whole domain in a 1-star sense; see Definition 11.
33
e (1/ε) · VC H + log1/δ . 3. If VC H < ∞, then H is learnable with sample and query complexity O Below, we state the equivalent version of this theorem using the notation of one-centered star dimension, which we prove below. Theorem 4.2. The following hold in Valiant’s model over a general domain (Definition 3): 1. If H is learnable, then VC(H) ≤ 9 m(1/3, 1/3) + 1. 2. If |X| = ∞ and X is a 1-star for H, then H is not learnable in Valiant’s model. s (H) log1/ε+log1/δ 3. If s1 (H) < ∞, then H is learnable with m(ε, δ) ≤ O 1 . ε Proof sketch of Part I of Theorem 4.2. This is an immediate corollary of the hard-prior argument as in Theorem 3.10. Remark 4.3. This, in particular, implies that finite VC dimension (VC(H) < ∞) is necessary for learning H. This special result also follows from Theorem 3 of Kulkarni, Mitter, and Tsitsiklis [KMT93], who show that infinite VC dimension rules out learnability even in a stronger model where the learner knows the feature distribution exactly and may ask arbitrarily many binary queries. For the quantitative bound above, we required the new proof presented above. Proof of Part II of Theorem 4.2. This is the same conditioning-on-the-sample/counting argument as in Theorem 3.10, except that the hidden object is now a single index rather than a k-subset. Because X is a 1-star for H, for every x ∈ X, there exists a concept h ( x ) ( y ) = 1{ y ̸ = x }
for every y ∈ X.
Fix ε, δ ∈ (0, 1/2) and suppose, toward a contradiction, that H is learnable with sample/query complexity M := m(ε, δ) . Choose a large enough finite set Xn = { x1 , . . . , xn } ⊆ X such that 1 M + ε ( n − 1) + 1 < . n−M 2
(6)
This is possible since ε < 1/2 and X is infinite. For each i ∈ [n], let Di be the uniform distribution on
Xn \ { xi }, so Di is compatible with h(xi ) . Choose I uniformly from [n] and use the pair h(x I ) , D I as the hard prior. By Yao’s minimax principle, it suffices to analyze deterministic learners with budget M for each oracle. Fix such a deterministic learner L . Padding with ignored queries if necessary, we may assume that L makes exactly M example-oracle calls and exactly M membership queries, and that all membership queries are asked after the samples are seen. Let P = (z1 , . . . , z M ) ∈ XnM be the ordered sample sequence, and let P := {z1 , . . . , z M } be the set of distinct sampled points. Now fix any sample sequence P0 ∈ XnM , and write r := P0 . For each i ∈ [n], / P0 . Pr ( P = P0 | I = i ) = (n − 1)− M · 1 xi ∈ Since the prior on I is uniform, conditioning on P = P0 makes I uniform over i ∈ [n] : xi ∈ / P0 , so there are exactly n − r ≥ n − M candidate hidden indices after the sample. 34
Ignoring queries outside Xn (which always return 1), the learner’s behavior before it hits the hidden negative point is completely determined by the all-ones transcript. Let Q↑ ( P0 ) ⊆ Xn be the set of points of Xn queried along this branch. Since Q↑ ( P0 ) ≤ M, at most M candidate indices can ever be identified by a negative answer, namely those with xi ∈ Q↑ ( P0 ) \ P0 . For every remaining candidate index i with xi ∈ / P0 ∪ Q↑ ( P0 ), all membership answers are 1, so the learner reaches the same all-ones leaf and outputs the same positive region HP↑0 ⊆ X, independent of i. Success on target h(xi ) then requires xi ∈ / HP↑0
and
{ x j ∈ Xn \ { x i } : x j ∈ / HP↑0 } ≤ ε(n − 1).
Writing TP0 := Xn \ HP↑0 , this says that xi ∈ TP0
and
| TP0 | ≤ ε(n − 1) + 1.
Hence among the no-hit candidates, the learner can succeed on at most ε(n − 1) + 1 indices. Combining the hit and no-hit cases, conditioned on P = P0 the learner can succeed on at most M + ε(n − 1) + 1 of the n − r candidate hidden indices. Therefore Pr (L succeeds | P = P0 ) ≤
M + ε ( n − 1) + 1 M + ε ( n − 1) + 1 1 ≤ < , n−r n−M 2
where the last inequality is exactly (6). Averaging over P, we obtain Pr (L succeeds) < 12 . Thus every deterministic learner with budget M for each oracle fails with probability greater than 1/2 under the hard prior. By Yao’s minimax principle, the same holds for randomized learners, contradicting learnability at confidence 1 − δ > 1/2. Hence H is not learnable in Definition 3. Proof of Part III of Theorem 4.2. By Theorem 2.2, there exists a concept class H ⊇ H that is closed under intersections and satisfies VC H = s1 (H). The claim now follows from the standard closure-learner theorem for intersection-closed classes, applied to H: using no membership queries and O (1/ε) · VC H log1/ε + log1/δ positive examples, one obtains a hypothesis with no false positives and ε-false negatives. Since every target h⋆ ∈ H also belongs to H, the same learner is valid for H. Substituting VC H = s1 (H) gives the stated bound.
4.4
Proof That Conditions in Theorem 1.5 Are Not Tight for Learnability
In this section, we prove the following result, which shows that the conditions in Theorem 1.5 are not tight. Theorem 4.4. The following hold in Valiant’s model over a general domain (Definition 3). 1. (Finite VC dimension is not sufficient) There exists a concept class H with VC(H) < ∞ that is not learnable in Valiant’s model. 2. (Finite 1-star number is not necessary) There exists a concept class H with s1 (H) = ∞ that is learnable in Valiant’s model. 35
3. (The whole-domain 1-star condition is not necessary) There exists a concept class H that is not learnable in Valiant’s model, even though the whole domain is not a 1-star for H. Proof of Part I of Theorem 4.4. The first witness is the simplest possible infinite 1-star. Let X = Z, h◦ ≡ 1, and, for each i ∈ Z, hi ( x ) := 1{ x ̸= i } . Define Hsing := { h◦ } ∪ { hi : i ∈ Z} . We first verify that VC Hsing = 1. To see this, note that: (1) Any singleton { a} is shattered, since h◦ ( a) = 1 and h a ( a) = 0, so VC Hsing ≥ 1. (2) Further, no two-point set is shattered, as every hypothesis in Hsing labels at most one point by 0. Next, by construction, the domain Z is a 1-star for Hsing centered at h◦ . Therefore Part II of Theorem 4.2 implies that Hsing is not learnable. Proof of Part II of Theorem 4.4. Let X := Z × {0, 1}, and for each i ∈ Z define hi : X → {0, 1} by hi ( x, 0) := 1{ x ̸= i }
and
hi ( x, 1) := 1{ x ≥ i } .
Set Hpre := { hi : i ∈ Z}. Intuitively, on the slice Z × {0} each hypothesis acts as the complement of a singleton, and on the slice Z × {1} it acts as a threshold. We first verify that s1 (Hpre ) = ∞. Fix any k ∈ N and let Sk := {(1, 0), . . . , (k, 0)}. Then hk+1 labels every point of Sk by 1, while for each t ∈ [k ] the hypothesis ht agrees with hk+1 on Sk \ {(t, 0)} and labels (t, 0) by 0. Thus Sk is a 1-star for Hpre , and since k is arbitrary, s1 (Hpre ) = ∞. We now show that Hpre is learnable. Fix a target hi⋆ ∈ Hpre and a distribution D compatible with hi⋆ , and let D0 denote the marginal of D on the first coordinate. Given ε, δ ∈ (0, 1), the learner draws log1/ε + log1/δ m=O ε independent examples ( x1 , y1 ), . . . , ( xm , ym ) ∼ D, lets Z := { x1 , . . . , xm } ⊆ Z, writes the distinct values of Z as z(1) < · · · < z(r) , and adds sentinels z(0) := −∞ and z(r+1) := ∞. By the ε-net theorem for intervals (which have VC dimension 2), with probability at least 1 − δ every interval J ⊆ R with D0 ( J ) ≥ ε contains at least one sampled coordinate. Fix a realization for which this holds. The learner then uses membership queries on the slice Z × {1}. Since hi⋆ ( x, 1) = 1{ x ≥ i⋆ }, a binary search over z(1) , . . . , z(r) finds the smallest index t ∈ {1, . . . , r + 1} such that hi⋆ (z(t) , 1) = 1 (with the convention t = r + 1 if all answers are 0). Setting L := z(t−1) and R := z(t) , we have i⋆ ∈ ( L, R]. If R < ∞, the learner asks one additional membership query at ( R, 0). If the answer is 0, then R = i⋆ , so it outputs the exact target hypothesis h R . Otherwise, or if R = ∞, let J := ( L, R) ∩ Z (with the convention ( L, ∞) ∩ Z when R = ∞), and output the hypothesis b h defined by b h( x, 0) = 1{ x ∈ / J}
and
b h( x, 1) = 1{ x ≥ R} ,
where 1{ x ≥ ∞} = 0. We now verify correctness. If R = i⋆ , then b h = hi⋆ and there is nothing to prove. Suppose we b are in the remaining case. First, h has no false positives. Indeed, since i⋆ ∈ ( L, R] and we are not in the exact case, we actually have i⋆ ∈ J = ( L, R) ∩ Z. Therefore, if b h( x, 0) = 1, then x ∈ / J, so 36
x ̸= i⋆ and hence hi⋆ ( x, 0) = 1. Also, if b h( x, 1) = 1, then necessarily R < ∞ and x ≥ R > i⋆ , so again hi⋆ ( x, 1) = 1. Next, every false negative of b h has first coordinate in J. For points of the form ( x, 0), this is immediate from the definition of b h. For points of the form ( x, 1), if b h( x, 1) = 0 while hi⋆ ( x, 1) = 1, ⋆ ⋆ then i ≤ x < R, and since i ∈ J, this implies x ∈ J. Thus the total false-negative probability is at most D0 ( J ). Finally, the interval J contains no sampled coordinate by construction, so the ε-net property gives D0 ( J ) < ε, and the learner succeeds with probability at least 1 − δ. The total cost is O((1/ε) · (log1/ε + log1/δ)) example-oracle calls and O(log(m + 1)) membership queries. Therefore Hpre is learnable in Valiant’s model and satisfies s1 (Hpre ) = ∞. Proof of Part III of Theorem 4.4. For each finite set A ⊆ N, let h A ( x ) := 1{ x ∈ A}, and set Hfin := { h A : A ⊆ N finite} . We first show that VC(Hfin ) = ∞. Fix any n ∈ N and let Sn := {1, . . . , n}. For every subset T ⊆ Sn , the set T is finite, so h T ∈ Hfin and h T realizes exactly that labeling on Sn . Thus Sn is shattered, and since n is arbitrary, VC(Hfin ) = ∞. By Part (1) of Theorem 4.2, Hfin is not learnable. It remains to show that the whole domain N is not a 1-star for Hfin . If N were a 1-star, then in particular there would exist a center hypothesis h◦ ∈ Hfin such that h◦ ( x ) ≡ 1 (for each x ∈ N) and, further, for each z, there would need to be a hypothesis hz ∈ Hfin such that hz ( x ) = 1{ x ̸= z} (for each x ∈ N). But every hypothesis in Hfin has finite support, so neither h◦ nor hz (for any z ∈ N) exists. Hence, N is not a 1-star for Hfin .
4.5
Proof of Theorem 1.6 (Halfspaces Are Learnable on Rd )
In this section, we prove Theorem 1.6, which we restate below. Theorem 1.6 (Halfspaces Are Learnable on Rd ). There is an algorithm that learns halfspaces in Rd in Valiant’s model using m(ε, δ) positive examples and q(ε, δ) membership queries, where m(ε, δ) = O
2 d log d · log1/ε + log1/δ ε
and
q(ε, δ) = O d3 log3 d · log1/εδ .
Remark 4.5 (Comparison with the Boolean Hypercube). It is useful to contrast Theorem 1.6 with the Boolean setting. For each d ∈ N, let Hdcube denote the restriction of halfspaces in Rd to the Boolean cube {0, 1}d . Perhaps surprisingly, the sequence H1cube , H2cube , . . . is not learnable in Valiant’s model, even though the unrestricted class over Rd is learnable by Theorem 1.6 (see Proposition 1.7). The key difference is that over Rd , the learner may query any point in the ambient space, whereas on the Boolean cube the learner is confined to queries inside {0, 1}d . This additional geometric freedom is exactly what makes Theorem 1.6 possible. Setup. To prove Theorem 1.6, fix ε, δ ∈ (0, 1), a target halfspace H⋆ =
n
o x ∈ Rd : ⟨ n ⋆ , x ⟩ ≥ c ⋆ , 37
where n⋆ ̸= 0 is a normal vector of H ⋆ , and fix a distribution D compatible with H ⋆ (Definition 4). Let m be the sample size as specified later, and draw m independent examples x1 , . . . , xm ∼ D. Define C := conv( P), and A := aff (C ) . P := { x1 , . . . , xm } , Here, C is the convex hull of the observed positive sample and A is the smallest affine subspace containing C. Let L be the linear subspace of directions parallel to A, and let r denote its dimension: L := { x − y : x, y ∈ A}
and
r := dim( L) .
Facets, Cones, and Simplexes Next, we introduce facets of C and define certain cones and simplexes derived from them, which the learning algorithm will use. In the degenerate case where r = 0 and, hence, C is a single sampled point, we do not need these additional definitions; the learner will simply return C. Hence, for the remainder of this part, assume r ≥ 1. Consider a vertex v of C, and let F (v) denote the set of facets of C (within A) that are incident to v. For each F ∈ F (v), let n F ∈ L be the outward unit normal of F. The supporting halfspace of F is HF := { x ∈ A : ⟨n F , x − v⟩ ≤ 0}, which contains C by construction. We first recall a standard fact: Lemma 4.6 (Incident Normals Span L). The outward normals of the facets in F (v) span L. For completeness, we prove Lemma 4.6 at the end of this section. Next, consider any set of r facets with linearly independent normals: J = { F1 , . . . , Fr } ⊆ F (v) For each such choice, Wv,J denotes the cone cut out by these facets: Wv,J :=
\
HF = { x ∈ A : ⟨n F , x − v⟩ ≤ 0 for all F ∈ J } .
F∈ J
Since each HF contains C, we have Wv,J ⊇ C. Next, define av,J := − ∑ n F
Tv,J := max⟨ av,J , x − v⟩.
and
x ∈C
F∈ J
(7)
The vector av,J aggregates the inward-pointing normals, and Tv,J measures the extent of C from v in direction av,J . Next, we use av,J and Tv,J to “close off” the cone Wv,J : for each v and J, define Sv,J := { x ∈ Wv,J : ⟨ av,J , x − v⟩ ≤ Tv,J } . The learning algorithm outputs Sv,J for a suitable choice of v and J. We now establish the key properties of these sets. First, every candidate contains the sample hull: Lemma 4.7. For every vertex v of C and size-r subset of facets J ⊆ F (v) with linearly independent normals, C ⊆ Sv,J . Proof. We already saw C ⊆ Wv,J and, by Tv,J ’s definition, each x ∈C satisfies ⟨ av,J , x − v⟩ ≤ Tv,J . 38
Next, we show that there always exists a choice of v⋆ and J ⋆ for which the candidate simplex lies inside the target halfspace H ⋆ . Lemma 4.8 (Safe Candidate Exists). There exist a vertex v⋆ of C and a size-r subset J ⋆ ⊆ F (v⋆ ) with linearly independent normals such that Sv⋆ ,J ⋆ ⊆ H ⋆ . Proof of Lemma 4.8. Let Π L (n⋆ ) denote the orthogonal projection of n⋆ onto L. The restriction of the affine functional x 7→ ⟨n⋆ , x ⟩ to A differs from x 7→ ⟨Π L (n⋆ ), x ⟩ by an additive constant, so the latter is minimized on C at some vertex. Fix a vertex v⋆ minimizing x 7→ ⟨Π L (n⋆ ), x ⟩ over C. By the normal-cone characterization of minimizing vertices, the vector −Π L (n⋆ ) lies in the normal cone of C at v⋆ . For a polytope, this normal cone is exactly the conic hull of the outward normals of the facets incident to v⋆ . Therefore −Π L (n⋆ ) is a nonnegative combination of the outward normals of the facets in F (v⋆ ). By conic Carathéodory in the r-dimensional space L, there exists a set J0 ⊆ F (v⋆ ) of size | J0 | ≤ r, whose outward normals already generate −Π L (n⋆ ). Choose such a representation with minimal support, so that the corresponding outward normals are linearly independent. Now, using Lemma 4.6, enlarge J0 if necessary to an r-element set J ⋆ = { F1 , . . . , Fr } ⊆ F (v⋆ ) whose outward normals are linearly independent. Let x ∈ Wv⋆ ,J ⋆ . Then for every F ∈ J ⋆ , ⟨n F , x − v⋆ ⟩ ≤ 0. Since −Π L (n⋆ ) is a nonnegative combination of the outward normals in J0 ⊆ J ⋆ , ⟨Π L (n⋆ ), x − v⋆ ⟩ ≥ 0. But x − v⋆ ∈ L, so
⟨n⋆ , x − v⋆ ⟩ = ⟨Π L (n⋆ ), x − v⋆ ⟩ ≥ 0. Because v⋆ ∈ C ⊆ H ⋆ , we have ⟨n⋆ , v⋆ ⟩ ≥ c⋆ , and therefore
⟨n⋆ , x ⟩ = ⟨n⋆ , v⋆ ⟩ + ⟨n⋆ , x − v⋆ ⟩ ≥ c⋆ . Thus x ∈ H ⋆ , so Wv⋆ ,J ⋆ ⊆ H ⋆ . Since Sv⋆ ,J ⋆ ⊆ Wv⋆ ,J ⋆ by definition, we conclude that Sv⋆ ,J ⋆ ⊆ H ⋆ . Finally, to bound the false-negative rate, we use that the candidate outputs are all simplexes, a class of bounded VC dimension. The following lemma confirms that each Sv,J is indeed a simplex: Lemma 4.9. The set Sv,J is an r-simplex in A. (Recall that an r-simplex is a polytope which is the convex hull of its r + 1 vertices.) The proof is straightforward and appears at the end of this section. This is useful for two reasons. First, the class of simplexes has bounded VC dimension: Fact 4.10 ([BEHW89]). Let Td be the set of simplexes in d dimensions. Then, VC(Td ) = O d2 log d . Second, since Sv,J is a simplex with at most r + 1 ≤ d + 1 vertices, the learner can check whether Sv,J ⊆ H ⋆ by querying the membership oracle on these vertices alone: if all vertices are positive (i.e., they lie in H ⋆ ), convexity implies that the entire simplex lies in H ⋆ .
Learning Algorithm We now describe the learning algorithm (see Algorithm 1). If r = 0, the algorithm returns the hypothesis b h( x ) = 1{ x ∈ C }. Otherwise, it enumerates every vertex v of C and every size-r subset J ⊆ F (v) of facets with linearly independent normals, constructs the corresponding candidate 39
simplex Sv,J for each pair (v, J ), and collects the vertices of all these simplexes into a finite set V. It then runs the point-location procedure of Hopkins, Kane, Lovett, and Mahajan [HKLM20, Theorem 1.5 and Section 7] on V with failure parameter δ/2, and returns the first candidate simplex whose vertices are all labeled 1 by this procedure. If no such candidate exists, it returns the all-zero hypothesis. When the algorithm returns a candidate simplex, we denote it by Sb and write b h( x ) := 1{ x ∈ Sb} for the resulting hypothesis. Algorithm 1 H ULL -S IMPLEX L EARNER (d) (Learning halfspaces in Valiant’s model) 1: procedure H ULL -S IMPLEX L EARNER (ε, δ, d)
4:
Set m ← O (1/ε) · d2 log d · log1/ε + log1/δ and η ← δ/2 Obtain m i.i.d. examples x1 , . . . , xm from the example oracle Set P ← { x1 , . . . , xm } , C ← conv( P), A ← aff (C ), and r ← dim( A)
5:
If r = 0 (i.e., all samples are identical), then return hypothesis b h ( x ) = 1{ x ∈ C }
2: 3:
6: 7: 8: 9: 10:
11: 12:
# Phase A: Construct list of simplexes {Sv,J : v, J } containing C Initialize an ordered list of candidate simplexes: S ← ∅ for each vertex v of C do Let F (v) be the set of facets of C in A that are incident to v for each size-r subset J ⊆ F (v) of facets with linearly-independent normals do For each F ∈ J, let n F be the outward unit normal of F, and define HF = { x ∈ A : ⟨ n F , x − v ⟩ ≤ 0} Set av,J ← − ∑ F∈ J n F and Tv,J ← maxx∈C ⟨ av,J , x − v⟩ Use av,J and Tv,J to define the candidate simplex as follows: Wv,J ←
13: 14: 15:
16: 17: 18:
19: 20:
\ F∈ J
HF
and
Sv,J ← Wv,J ∩ { x ∈ A : ⟨ av,J , x − v⟩ ≤ Tv,J }
Append Sv,J to S end for end for # Phase B: Find labels of vertices of all simplexes Let V be the set of all vertices of all simplexes in S Run the point-location procedure of [HKLM20] on V with failure parameter η Let λ(z) ∈ {0, 1} denote the returned label for each z ∈ V # Phase C: Select output hypothesis if there exists S ∈ S all of whose vertices z satisfy λ(z) = 1 then return b h ( x ) = 1{ x ∈ S } otherwise return all-zero hypothesis
21: end procedure
Analysis of Correctness Next, we prove correctness of the learning algorithm. Lemma 4.11 (Correctness on the Point-Location Event). Let EPL denote the event that the pointlocation subroutine labels every point of V correctly. On EPL , the learner returns a candidate simplex Sb 40
that contains the entire sample P and satisfies Sb ⊆ H ⋆ . Hence on EPL , the output b h has no false positives. Proof of Lemma 4.11. If r = 0, then the learner returns Sb = C ⊆ H ⋆ , so the claim is immediate. Assume therefore that r ≥ 1. By Lemma 4.8, there exists a candidate simplex Sv⋆ ,J ⋆ contained in H ⋆ . All of its vertices belong to V and are positively labeled (i.e., they lie in H ⋆ ). Therefore, on EPL , the point-location subroutine labels all vertices of Sv⋆ ,J ⋆ by 1, so the learner returns some candidate b By Lemma 4.7, every candidate simplex contains C, and hence P ⊆ C ⊆ S. b Again on simplex S. ⋆ ⋆ b EPL , all vertices of S are labeled correctly, so they all lie in H . Since H is convex and Sb is the convex hull of its vertices, we obtain Sb ⊆ H ⋆ . Thus the output has no false positives. On the event EPL , the learner returns a simplex of dimension at most d that contains the entire sample. To control its false-negative error, we use the fact that the class of simplexes has VC dimension O(d2 log d) (Fact 4.10). Lemma 4.12 (False-Negative Error). If m = O (1/ε) · d2 log d · log1/ε + log1/δ then with probability 1 − δ over the sample draw, every simplex T ∈ Td containing P satisfies Prx∼D ( x ∈ / T ) ≤ ε. Consequently, on the intersection of this event with EPL , the returned Sb satisfies Prx∼D ( x ∈ / Sb) ≤ ε, and therefore Pr
x ∼D
b h( x ) = 0 and H ⋆ ( x ) = 1 ≤ ε.
Proof of Lemma 4.12. Let Td be the class of simplexes of dimension at most d. Define Gd to be the class of complements of hypotheses in Td , i.e., Gd := { x 7→ 1{ x ∈ / T } : T ∈ Td } . Since complementing a class does not change its VC dimension, VC(Gd ) = VC(Td ). By Fact 4.10 and the standard VC bound for zero empirical error, if
VC(Gd ) log1/ε + log1/δ m=O ε
2 d log d · log1/ε + log1/δ =O , ε
then with probability at least 1 − δ every function in Gd with empirical mean zero has true mean at most ε. Now fix any simplex T ∈ Td containing P. Its miss indicator gT ( x ) := 1{ x ∈ / T } belongs to Gd and has empirical mean zero on the sample, because P ⊆ T. Hence Prx∼D ( x ∈ / T ) ≤ ε, proving the first claim. On the event EPL , Lemma 4.11 shows that the returned simplex Sb contains P and satisfies Sb ⊆ H ⋆ . Applying the first claim with T = Sb gives Prx∼D ( x ∈ / Sb) ≤ ε. Since D is ⋆ ⋆ b compatible with H (Definition 4), it is supported on H . Therefore Prx∼D (h( x ) = 0 and H ⋆ ( x ) = 1) = Prx∼D ( x ∈ / Sb) ≤ ε. Lemma 4.13 (Query Complexity). The learner uses O(d3 log2 d · log d/εδ) membership queries. Proof of Lemma 4.13. If r = 0, the learner uses no membership queries. Assume therefore that r ≥ 1. Let V denote the set of all vertices of all candidate simplexes Sv,J . Definition 16 (Point-Location Problem). Given a finite set X ⊆ Rd and an unknown closed halfspace H = x ∈ Rd : ⟨n, x ⟩ ≥ c , the point-location problem asks for the labels 1{ x ∈ H } of all points in X using binary queries at adaptively chosen points of Rd .
41
Hopkins, Kane, Lovett, and Mahajan [HKLM20] prove the following result.7 Theorem 4.14 (Theorem 1.5 and Section 7 in [HKLM20]). For every finite X ⊆ Rd and η ∈ (0, 1), there is a randomized query procedure which, with probability at least 1 − η over its internal randomness, correctly labels every point of X with respect to the unknown closed halfspace, using q binary queries for q = O d log2 d · log|X |/η . We apply this result to the set V and the target halfspace H ⋆ , to which we have membership access. Upper Bound on |V|. It remains to bound |V|. The polytope C has at most m vertices. Let f (C ) denote the number of facets of C in A. Each facet of the r-dimensional polytope C contains r affinely independent vertices, and any such r-tuple determines the affine hull of that facet uniquely. Choosing one such r-tuple for each facet gives an injection from the set of facets into the set of r-subsets of the vertex set of C. Hence f (C ) ≤ (mr) ≤ mr . For each vertex v, the learner 2 considers at most ( f (rC)) ≤ (mr ) r = mr choices of J. Since there are at most m vertices, the total 2 2 number of candidate pairs (v, J ) is at most mr +1 ≤ md +1 . Each candidate simplex has at most 2 r + 1 ≤ d + 1 vertices, so |V| ≤ (d + 1)md +1 . Because m = O (1/ε) · d2 log d · log1/ε + log1/δ is polynomial in d, 1/ε, and 1/δ, we have log m = O(log d/εδ) . Hence log |V| ≤ log(d + 1) + (d2 + 1) log m = O d2 log d/εδ . The learner runs the point-location procedure with failure parameter η = δ/2. Therefore, the number of membership queries is O(d log2 d · log|V|/η ) = O(d3 log3 d · log 1/εδ).
Completing the Proof of Theorem 1.6 Proof of Theorem 1.6. The learner uses exactly m calls to the example oracle. Let EPL denote the event from Lemma 4.11. Because the point-location subroutine is run with failure parameter δ/2, for every fixed sample we have Pr(EPL | x1 , . . . , xm ) ≥ 1 − δ/2. Hence, Pr(EPL ) ≥ 1 − δ/2. Next, apply Lemma 4.12 with δ/2 in place of δ. If m = O (1/ε) · d2 log d · log1/ε + log1/δ , then with probability at least 1 − δ/2 over the sample draw, every simplex containing P has falsenegative mass at most ε. On the intersection of these two events, Lemma 4.11 shows that the learner returns a simplex Sb with P ⊆ Sb ⊆ H ⋆ , and Lemma 4.12 gives Prx∼D (b h( x ) = 0 and H ⋆ ( x ) = 1) ≤ ε. Moreover, Lemma 4.11 gives that the output has no false positives. A union bound therefore shows that the learner succeeds with probability at least 1 − δ. Finally, Lemma 4.13 gives the membership-query bound O(d3 log3 d · log 1/εδ). This completes the proof of the theorem.
Proofs Deferred from Earlier in this Section Proof of Lemma 4.6. Suppose toward a contradiction that the normals of F (v) do not span L. Then there exists a nonzero vector y ∈ L orthogonal to the outward normals of all facets in F (v). For every facet of C that is incident to v, the defining inequality of its supporting halfspace remains 7 While Hopkins, Kane, Lovett, and Mahajan [HKLM20] focus on ternary queries and homogeneous halfspaces for most of their paper, Section 7 of their work extends their result to non-homogeneous halfspaces with binary queries.
42
tight along the line v + τy. For every facet of C that is not incident to v, the defining inequality is strict at v, and therefore remains satisfied for all sufficiently small |τ |. Hence both v + τy and v − τy lie in C for all sufficiently small τ > 0. This contradicts that v is a vertex of C. Proof of Lemma 4.9. Recall that an r-simplex is an r-dimensional polytope that is the convex hull of its r + 1 vertices. To show Sv,J is an r-simplex, introduce the affine map Φv,J : A → Rr defined as Φv,J ( x ) := (−⟨n F1 , x − v⟩, . . . , −⟨n Fr , x − v⟩) . This coordinate map is useful because it converts the facet inequalities defining Wv,J into the standard nonnegativity constraints in Rr . In particular, by the definitions of Wv,J , av,J , and Φv,J , Φv,J (Sv,J ) = y ∈ Rr≥0 : y1 + · · · + yr ≤ Tv,J . Assume Tv,J is positive. Then Φv,J (Sv,J ) is the standard r-simplex in Rr . Further, since the vectors n F1 , . . . , n Fr are linearly independent and dim( A) = dim( L) = r, Φv,J is an isomorphism from A to Rr . Putting these two observations together implies that Sv,J also is an r-simplex in A. It remains to show that Tv,J is positive. To see this, observe that, for every 1 ≤ ℓ ≤ r, C ⊆ HFℓ (by construction), so for every x ∈ C, Φv,J ( x ) ∈ Rr≥0 . Since r ≥ 1, the set C is not equal to {v}. Choose x ∈ C \ {v}. Because Φv,J is injective, Φv,J ( x ) ̸= Φv,J (v) = 0, and therefore ∑rℓ=1 Φv,J ( x )ℓ = ⟨ av,J , x − v⟩ > 0. Thus, Tv,J (see (7)) is positive.
4.6
Proof of Proposition 1.7 (Halfspaces Are Not Learnable on the Boolean Cube)
In this section, we prove Proposition 1.7, which we restate below. Proposition 1.7 (Halfspaces Are Not Learnable on the Boolean Cube). Let HH = H1H , H2H , . . . , where HdH is the class of restrictions to {0, 1}d of halfspaces in Rd . Then HH is not learnable in Valiant’s model (where the learner can only query points in {0, 1}d ). Proof of Proposition 1.7. For every d, the class HdH contains the constant-one hypothesis. Further, for each v ∈ {0, 1}d , it contains a hypothesis that is positive on every point of {0, 1}d \ {v} and negative on v alone. Indeed, if we define Dv ( x ) := ∑i:vi =0 xi + ∑i:vi =1 (1 − xi ) , then Dv is an affine function of x, Dv (v) = 0, and Dv ( x ) ≥ 1 for every x ∈ {0, 1}d \ {v}. Hence the halfspace hv ( x ) := 1{ Dv ( x ) ≥ 1/2} belongs to HdH and excludes exactly the point v. Therefore, for every T A ⊆ {0, 1}d , A = v∈{0,1}d \ A supp(hv ), so the intersection closure of HdH contains every subset of
{0, 1}d . Thus Item 2 of Corollary 1.4 applies, and HH is not learnable in Valiant’s model.
43
References [ABL17]
[ADDST25]
[AGR13]
[AKGHY14]
[Ang04] [Ang79] [Ang80] [Ang88] [Bau91] [BBL05]
[BBL06]
[BBZ07]
[BCGS98]
[BEHW89]
[BFKV98]
[BHV10]
Pranjal Awasthi, Maria-Florina Balcan, and Philip M. Long. “The Power of Localization for Efficiently Learning Linear Separators with Noise”. In: Journal of the ACM 63.6 (2017) (cit. on p. 13). Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, and Shang-Hua Teng. “Proper Learnability and the Role of Unlabeled Data”. In: Proceedings of The 36th International Conference on Algorithmic Learning Theory. Vol. 272. Proceedings of Machine Learning Research. PMLR, 2025, pp. 112–133. URL: https://proceedings.mlr.press/v272/asilis25b. html (cit. on p. 15). Joseph Anderson, Navin Goyal, and Luis Rademacher. “Efficient Learning of Simplices”. In: Proceedings of the 26th Annual Conference on Learning Theory. Vol. 30. Proceedings of Machine Learning Research. PMLR, Dec. 2013, pp. 1020–1045. URL: https://proceedings.mlr. press/v30/Anderson13.html (cit. on pp. 1, 13). Charu C. Aggarwal, Xiangnan Kong, Quanquan Gu, Jiawei Han, and Philip S. Yu. “Active Learning: A Survey”. In: Data Classification: Algorithms and Applications. CRC Press, 2014, pp. 599–634 (cit. on p. 2). Dana Angluin. “Queries Revisited”. In: Theoretical Computer Science 313.2 (2004), pp. 175–194 (cit. on p. 2). Dana Angluin. “Finding patterns common to a set of strings”. In: Proceedings of the eleventh annual ACM Symposium on Theory of Computing. 1979, pp. 130–141 (cit. on p. 12). Dana Angluin. “Inductive inference of formal languages from positive data”. In: Information and control 45.2 (1980), pp. 117–135 (cit. on p. 12). Dana Angluin. “Queries and Concept Learning”. In: Machine Learning 2.4 (1988), pp. 319– 342. URL: https://doi.org/10.1023/A:1022821128753 (cit. on pp. 2, 7, 13). Eric B. Baum. “Neural Net Algorithms That Learn in Polynomial Time from Examples and Queries”. In: IEEE Transactions on Neural Networks 2.1 (1991), pp. 5–19 (cit. on p. 13). Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi. “Theory of Classification: A Survey of Some Recent Advances”. In: ESAIM: Probability and Statistics 9 (2005), pp. 323–375 (cit. on p. 27). Maria-Florina Balcan, Alina Beygelzimer, and John Langford. “Agnostic active learning”. In: Proceedings of the 23rd international conference on Machine learning. 2006, pp. 65–72 (cit. on pp. 2, 13). Maria-Florina Balcan, Andrei Z. Broder, and Tong Zhang. “Margin Based Active Learning”. In: Learning Theory, 20th Annual Conference on Learning Theory (COLT 2007). Vol. 4539. Lecture Notes in Computer Science. Springer, 2007, pp. 35–50 (cit. on p. 13). Avrim Blum, Prasad Chalasani, Sally A. Goldman, and Donna K. Slonim. “Learning with Unreliable Boundary Queries”. In: Journal of Computer and System Sciences 56.2 (1998), pp. 209– 222 (cit. on p. 13). Anselm Blumer, A. Ehrenfeucht, David Haussler, and Manfred K. Warmuth. “Learnability and the Vapnik-Chervonenkis dimension”. In: J. ACM 36.4 (Oct. 1989), pp. 929–965. URL: https://doi.org/10.1145/76359.76371 (cit. on pp. 2, 9, 15, 25, 39). Avrim Blum, Alan Frieze, Ravi Kannan, and Santosh Vempala. “A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions”. In: Algorithmica 22.1 (1998), pp. 35– 52. URL: https://doi.org/10.1007/PL00013833 (cit. on p. 14). Maria-Florina Balcan, Steve Hanneke, and Jennifer Wortman Vaughan. “The true sample complexity of active learning”. In: Machine learning 80.2 (2010), pp. 111–139 (cit. on pp. 2, 13).
44
[BKMS21]
[BL13]
[Bsh18] [CAL94] [CCHMY24]
[CDS20]
[CKMMZ25]
[CP25]
[Das11] [DDS15]
[DGM22]
[DGTZ18]
[DKM24]
[EA07]
Mark Braverman, Gillat Kol, Shay Moran, and Raghuvansh R. Saxena. “Near Optimal Distributed Learning of Halfspaces with Two Parties”. In: Proceedings of the 34th Conference on Learning Theory. Vol. 134. Proceedings of Machine Learning Research. PMLR, 2021, pp. 724– 758 (cit. on p. 7). Maria-Florina Balcan and Phil Long. “Active and Passive Learning of Linear Separators under Log-Concave Distributions”. In: Proceedings of the 26th Annual Conference on Learning Theory. Vol. 30. Proceedings of Machine Learning Research. PMLR, 2013, pp. 288–316. URL: https://proceedings.mlr.press/v30/Balcan13.html (cit. on p. 13). Nader H. Bshouty. “Exact Learning from an Honest Teacher that Answers Membership Queries”. In: Theoretical Computer Science 733 (2018), pp. 4–43 (cit. on p. 2). David Cohn, Les Atlas, and Richard Ladner. “Improving generalization with active learning”. In: Machine learning 15.2 (1994), pp. 201–221 (cit. on p. 13). Zachary Chase, Bogdan Chornomaz, Steve Hanneke, Shay Moran, and Amir Yehudayoff. “Dual VC Dimension Obstructs Sample Compression by Embeddings”. In: Proceedings of Thirty Seventh Conference on Learning Theory. Vol. 247. Proceedings of Machine Learning Research. PMLR, 2024, pp. 923–946. URL: https : / / proceedings . mlr . press / v247 / chase24a.html (cit. on p. 13). Clément L. Canonne, Anindya De, and Rocco A. Servedio. “Learning From Satisfying Assignments Under Continuous Distributions”. In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA). 2020, pp. 82–101. URL: https://epubs.siam.org/ doi/abs/10.1137/1.9781611975994.6 (cit. on pp. 1, 13). Yang Cai, Alkis Kalavasis, Katerina Mamali, Anay Mehrotra, and Manolis Zampetakis. “What Makes Treatment Effects Identifiable? Characterizations and Estimators Beyond Unconfoundedness (Extended Abstract)”. In: Proceedings of Thirty Eighth Conference on Learning Theory. Vol. 291. Proceedings of Machine Learning Research. PMLR, 30 Jun–04 Jul 2025, pp. 755– 756. URL: https://proceedings.mlr.press/v291/cai25b.html (cit. on p. 13). Moses Charikar and Chirag Pabbaraju. “Exploring Facets of Language Generation in the Limit”. In: Proceedings of Thirty Eighth Conference on Learning Theory. Vol. 291. Proceedings of Machine Learning Research. PMLR, 2025, pp. 854–887. URL: https://proceedings. mlr.press/v291/charikar25a.html (cit. on p. 2). Sanjoy Dasgupta. “Two faces of active learning”. In: Theoretical computer science 412.19 (2011), pp. 1767–1781 (cit. on p. 13). Anindya De, Ilias Diakonikolas, and Rocco A. Servedio. “Learning From Satisfying Assignments”. In: Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2015, pp. 478–497. URL: https://epubs.siam.org/doi/abs/10.1137/1. 9781611973730.33 (cit. on pp. 1, 13). Kunal Dutta, Arijit Ghosh, and Shay Moran. “Uniform Brackets, Containers, and Combinatorial Macbeath Regions”. In: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Vol. 215. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, 59:1–59:10 (cit. on p. 7). Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, and Manolis Zampetakis. “Efficient Statistics, in High Dimensions, from Truncated Samples”. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). 2018, pp. 639–649 (cit. on p. 2). Ilias Diakonikolas, Daniel M. Kane, and Mingchen Ma. “Active Learning of General Halfspaces: Label Queries vs Membership Queries”. In: Advances in Neural Information Processing Systems. Vol. 37. 2024 (cit. on p. 13). David Eisenstat and Dana Angluin. “The VC dimension of k-fold union”. In: Information Processing Letters 101.5 (2007), pp. 181–184 (cit. on pp. 9, 25).
45
[EN08]
[ER90]
[FJK96]
[FW95]
[GK00]
[Gol67] [GSS13]
[Han07] [Han09] [Han14]
[Han24]
[Han25]
[HKKT18]
[HKLM20]
[HKS19]
Charles Elkan and Keith Noto. “Learning Classifiers From Only Positive and Unlabeled Data”. In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD ’08. Association for Computing Machinery, 2008, pp. 213–220. URL : https://doi.org/10.1145/1401890.1401920 (cit. on p. 2). Bonnie Eisenberg and Ronald L. Rivest. “On the Sample Complexity of PAC-Learning Using Random and Chosen Examples”. In: Proceedings of the Third Annual Workshop on Computational Learning Theory. Morgan Kaufmann, 1990, pp. 154–162 (cit. on p. 2). Alan Frieze, Mark Jerrum, and Ravi Kannan. “Learning linear transformations”. In: Proceedings of 37th Conference on Foundations of Computer Science. 1996, pp. 359–368 (cit. on pp. 1, 13). Sally Floyd and Manfred K. Warmuth. “Sample Compression, Learnability, and the Vapnik– Chervonenkis Dimension”. In: Machine Learning 21.3 (1995), pp. 269–304 (cit. on pp. 2, 13, 25). Paul W Goldberg and Stephen Kwek. “The Precision of Query Points as a Resource for Learning Convex Polytopes with Membership Queries.” In: COLT. 2000, pp. 225–235 (cit. on p. 13). E Mark Gold. “Language identification in the limit”. In: Information and control 10.5 (1967), pp. 447–474 (cit. on pp. 1, 12). Alon Gonen, Sivan Sabato, and Shai Shalev-Shwartz. “Efficient Active Learning of Halfspaces: An Aggressive Approach”. In: Journal of Machine Learning Research 14.43 (2013), pp. 2583–2615. URL: https://jmlr.csail.mit.edu/papers/v14/gonen13a.html (cit. on p. 13). Steve Hanneke. “A bound on the label complexity of agnostic active learning”. In: Proceedings of the 24th international conference on Machine learning. 2007, pp. 353–360 (cit. on p. 2). Steve Hanneke. Theoretical foundations of active learning. Carnegie Mellon University, 2009 (cit. on pp. 2, 13). Steve Hanneke. “Theory of Disagreement-Based Active Learning”. In: Foundations and Trends® in Machine Learning 7.2–3 (2014), pp. 131–309. URL: https://www.nowpublishers.com/ article/Details/MAL-037 (cit. on p. 15). Steve Hanneke. “The Star Number and Eluder Dimension: Elementary Observations About the Dimensions of Disagreement”. In: Proceedings of Thirty Seventh Conference on Learning Theory. Vol. 247. Proceedings of Machine Learning Research. PMLR, 30 Jun–03 Jul 2024, pp. 2308–2359 (cit. on pp. 16, 31). Steve Hanneke. “Agnostic Active Learning Is Always Better Than Passive Learning”. In: The Thirty-ninth Annual Conference on Neural Information Processing Systems. 2025. URL: https: //openreview.net/forum?id=XPe55Uffd7 (cit. on p. 2). Steve Hanneke, Adam Tauman Kalai, Gautam Kamath, and Christos Tzamos. “Actively Avoiding Nonsense in Generative Models”. In: Proceedings of the 31st Conference On Learning Theory. Vol. 75. Proceedings of Machine Learning Research. PMLR, June 2018, pp. 209–227. URL : https://proceedings.mlr.press/v75/hanneke18a.html (cit. on p. 2). Max Hopkins, Daniel Kane, Shachar Lovett, and Gaurav Mahajan. “Point Location and Active Learning: Learning Halfspaces Almost Optimally”. In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). 2020, pp. 1034–1044 (cit. on pp. 11, 40, 42). Steve Hanneke, Aryeh Kontorovich, and Menachem Sadigurschi. “Sample Compression for Real-Valued Learners”. In: Proceedings of the 30th International Conference on Algorithmic Learning Theory. Vol. 98. Proceedings of Machine Learning Research. PMLR, 2019, pp. 466– 488 (cit. on p. 13).
46
[HMST03]
[HY15] [JKV23]
[Kiv95]
[KM24] [KMT93]
[KMV25]
[KP98] [KTZ19]
[KV94] [LGE10]
[Lit88] [LMZ24]
[LMZ26]
[LW86]
[LZ24]
Yosuke Hayashi, Satoshi Matsumoto, Ayumi Shinohara, and Masayuki Takeda. “Uniform Characterizations of Polynomial-Query Learnabilities”. In: Theoretical Computer Science 292.2 (2003), pp. 377–385 (cit. on p. 2). Steve Hanneke and Liu Yang. “Minimax analysis of active learning”. In: J. Mach. Learn. Res. 16.1 (Jan. 2015), pp. 3487–3602 (cit. on p. 16). He Jia, Pravesh K. Kothari, and Santosh S. Vempala. “Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error”. In: 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). 2023, pp. 2408–2429 (cit. on pp. 1, 13). J. Kivinen. “Learning reliably and with one-sided error”. In: Mathematical systems theory 28.2 (1995), pp. 141–172. URL: https://doi.org/10.1007/BF01191474 (cit. on pp. 1, 2, 4, 13). Jon Kleinberg and Sendhil Mullainathan. “Language Generation in the Limit”. In: Advances in Neural Information Processing Systems. Vol. 37. 2024 (cit. on pp. 1, 2, 13). S. R. Kulkarni, S. K. Mitter, and J. N. Tsitsiklis. “Active Learning Using Arbitrary Binary Valued Queries”. In: Machine Learning 11.1 (1993), pp. 23–35. URL: https://doi.org/10. 1023/A:1022627018023 (cit. on pp. 2, 10, 34). Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas. “On the Limits of Language Generation: Trade-Offs Between Hallucination and Mode Collapse”. In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, 2025, pp. 1732–1743. URL: https://doi.org/10.1145/3717823.3718108 (cit. on pp. 1, 2, 13). Stephen Kwek and Leonard Pitt. “PAC Learning Intersections of Halfspaces with Membership Queries”. In: Algorithmica 22.1–2 (1998), pp. 53–75 (cit. on p. 13). Vasilis Kontonis, Christos Tzamos, and Manolis Zampetakis. “Efficient Truncated Statistics with Unknown Truncation”. In: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). 2019, pp. 1578–1595. URL: https://doi.org/10.1109/FOCS.2019. 00095 (cit. on pp. 1, 2, 13). Michael J Kearns and Umesh Vazirani. An introduction to computational learning theory. MIT press, 1994 (cit. on pp. 4, 12, 14). Wenkai Li, Qinghua Guo, and Charles Elkan. “A positive and unlabeled learning algorithm for one-class classification of remote-sensing data”. In: IEEE transactions on geoscience and remote sensing 49.2 (2010), pp. 717–725 (cit. on p. 2). Nick Littlestone. “Learning Quickly When Irrelevant Attributes Abound: A New LinearThreshold Algorithm”. In: Machine Learning 2.4 (1988), pp. 285–318 (cit. on p. 15). Jane H. Lee, Anay Mehrotra, and Manolis Zampetakis. “Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians”. In: 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). 2024, pp. 988–1006. URL: https : //doi.org/10.1109/FOCS61266.2024.00066 (cit. on pp. 1, 2, 13). Jane H. Lee, Anay Mehrotra, and Manolis Zampetakis. “Smoothed Analysis of Learning from Positive Samples”. In: Proceedings of the 58th Annual ACM Symposium on Theory of Computing. To appear. 2026. URL: https : / / arxiv . org / pdf / 2504 . 10428 (cit. on pp. 1, 13). Nick Littlestone and Manfred K. Warmuth. Relating Data Compression and Learnability. Tech. rep. Technical report / unpublished manuscript. University of California, Santa Cruz, 1986 (cit. on pp. 2, 25). Yinan Li and Chicheng Zhang. “Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach”. In: Proceedings of The 27th International Conference on Artificial Intelligence and Statistics. Vol. 238. Proceedings of Machine Learning Research. PMLR, 2024, pp. 4744–4752 (cit. on p. 13).
47
[MB25]
[Meh26] [MRT18]
[MY16] [Nat87]
[NR09] [Pab24] [SB14] [Set12] [Shv90]
[Val84a] [Val84b]
[VC71]
[VC74] [Vid03]
[War03]
[YZ17]
[Zha18]
Farnam Mansouri and Shai Ben-David. “Learning from Positive and Unlabeled Examples - Finite Size Sample Bounds”. In: The Thirty-ninth Annual Conference on Neural Information Processing Systems. 2025. URL: https : / / openreview . net / forum ? id = bK3s3n0vPA (cit. on pp. 1, 13). Anay Mehrotra. “Learning Theory in the Wild: Foundations of Missing Data and Language Generation”. Ph.D. dissertation. Yale University, May 2026 (cit. on p. 13). M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning. Adaptive Computation and Machine Learning series. MIT Press, 2018. URL: https : / / books . google.com/books?id=dWB9DwAAQBAJ (cit. on pp. 6, 12). Shay Moran and Amir Yehudayoff. “Sample Compression Schemes for VC Classes”. In: Journal of the ACM 63.3 (2016), 21:1–21:10 (cit. on pp. 2, 13). Balasubramaniam Kausik Natarajan. “On Learning Boolean Functions”. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing. STOC ’87. Association for Computing Machinery, 1987, pp. 296–304. URL: https://doi.org/10.1145/28395. 28427 (cit. on pp. 1, 2, 4, 6, 7, 10, 12, 17). Phong Q. Nguyen and Oded Regev. “Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures”. In: Journal of Cryptology 22.2 (2009), pp. 139–160 (cit. on pp. 1, 13). Chirag Pabbaraju. “Multiclass learnability does not imply sample compression”. In: International Conference on Algorithmic Learning Theory. PMLR. 2024, pp. 930–944 (cit. on p. 13). Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014 (cit. on pp. 6, 12, 14, 22). Burr Settles. Active Learning. Vol. 6. Synthesis Lectures on Artificial Intelligence and Machine Learning 1. Morgan & Claypool Publishers, 2012 (cit. on p. 2). Haim Shvaytser. “A Necessary Condition for Learning From Positive Examples”. In: Machine Learning 5.1 (1990), pp. 101–113. URL: https://doi.org/10.1007/BF00115896 (cit. on pp. 1, 2, 4, 6, 7, 10, 13, 17). Leslie G Valiant. “A Theory of the Learnable”. In: Commun. ACM 27.11 (Nov. 1984), pp. 1134– 1142. URL: https://doi.org/10.1145/1968.1972 (cit. on pp. 1, 2). Leslie Gabriel Valiant. “Deductive learning”. In: Philosophical Transactions of the Royal Society of London. Series A, Mathematical and Physical Sciences 312.1522 (1984), pp. 441–446 (cit. on p. 1). Vladimir Vapnik and Alexey Chervonenkis. “On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities”. In: Theory of Probability & Its Applications 16.2 (1971), pp. 264–280. URL: https://doi.org/10.1137/1116025 (cit. on pp. 2, 16). Vladimir N. Vapnik and Alexey Ya. Chervonenkis. Theory of Pattern Recognition: Statistical Learning Problems. In Russian. Nauka, 1974 (cit. on pp. 2, 16). M. Vidyasagar. Learning and Generalisation: With Applications to Neural Networks. 2nd ed. Communications and Control Engineering. Springer-Verlag London, 2003 (cit. on pp. 9, 12, 19, 20). Manfred K. Warmuth. “Compressing to VC Dimension Many Points”. In: Learning Theory and Kernel Machines. Vol. 2777. Lecture Notes in Computer Science. Springer, 2003, pp. 743– 744 (cit. on p. 13). Songbai Yan and Chicheng Zhang. “Revisiting Perceptron: Efficient and Label-Optimal Learning of Halfspaces”. In: Advances in Neural Information Processing Systems. Vol. 30. 2017, pp. 1057– 1067 (cit. on p. 13). Chicheng Zhang. “Efficient Active Learning of Sparse Halfspaces”. In: Proceedings of the 31st Conference On Learning Theory. Vol. 75. Proceedings of Machine Learning Research. PMLR, 2018, pp. 1856–1880 (cit. on p. 13).
48
[ZSA20]
Chicheng Zhang, Jie Shen, and Pranjal Awasthi. “Efficient Active Learning of Sparse Halfspaces with Arbitrary Bounded Noise”. In: Advances in Neural Information Processing Systems. Vol. 33. 2020 (cit. on p. 13).
49
A
Additional Results
A.1
Learning Intersections of s Halfspaces
In this section, we show that intersections of s halfspaces are learnable in Valiant’s model. Theorem A.1 (Intersections of Halfspaces Are Learnable in Valiant’s Model). Fix d, s ≥ 1. The class of intersections of s halfspaces in Rd is learnable in the extension of Valiant’s model to Rd (Definition 3) with sample complexity m(ε, δ) and query complexity q(ε, δ) for sd2 log(sd) · log1/ε + log1/δ m(ε, δ) = O ε
and
2
q(ε, δ) = (2es)d ms(d +1) .
The proof builds directly on the geometric machinery developed for the single-halfspace case. The reader may find it helpful to review the proof of Theorem 1.6 before proceeding. At a high level, in this proof, we reuse the candidate simplices Sv,J from the proof of Theorem 1.6 and intersect s of them, one for each halfspace defining the target. Proof of Theorem A.1. Fix ε, δ ∈ (0, 1), a target set P⋆ =
s \
Ht⋆ ,
n
Ht⋆ =
o x ∈ Rd : ⟨n⋆t , x ⟩ ≥ c⋆t ,
t =1
and a distribution D compatible with P⋆ (Definition 4). We allow repetitions among the halfspaces Ht⋆ , so this representation exists even when P⋆ is defined by fewer than s irredundant halfspaces. As in the proof of Theorem 1.6, draw m independent examples x1 , . . . , xm ∼ D (with m to be specified), and define the sample set P := { x1 , . . . , xm }, its convex hull C := conv( P), the affine hull A := aff (C ), the linear space L := { x − y : x, y ∈ A}, and the intrinsic dimension r := dim( L). If r = 0, then C is a singleton and the learner returns b h( x ) := 1{ x ∈ C }. We henceforth assume r ≥ 1. We reuse the family of candidate simplices from Theorem 1.6’s proof:
S(C ) := {Sv,J : v is a vertex of C, J ⊆ F (v), | J | = r, the normals in J are linearly independent} . Recall from Lemma 4.7 that every Sv,J ∈ S(C ) contains C, and from Lemma 4.9 that each Sv,J is an r-simplex in A. For each ordered s-tuple σ = (S1 , . . . , Ss ) ∈ S(C )s , define the candidate polytope Pσ :=
s \
St .
t =1
Since each St ⊇ C, every candidate satisfies Pσ ⊇ C. Lemma A.2 (A Safe Candidate Polytope Exists). There exists σ⋆ ∈ S(C )s such that C ⊆ Pσ⋆ ⊆ P⋆ . Proof of Lemma A.2. For each t ∈ [s], the distribution D is compatible with Ht⋆ (since P⋆ ⊆ Ht⋆ ). By Lemma 4.8, there exists St⋆ ∈ S(C ) with St⋆ ⊆ Ht⋆ . Setting σ⋆ := (S1⋆ , . . . , Ss⋆ ), we have Pσ⋆ =
s \
St⋆ ⊆
t =1
s \ t =1
50
Ht⋆ = P⋆ .
Since each St⋆ ⊇ C, we also have Pσ⋆ ⊇ C. Lemma A.3 (Candidate Polytopes Have Few Vertices). Every candidate polytope Pσ has at most 1) ( s (r + r ) vertices. Proof. Fix σ = (S1 , . . . , Ss ) ∈ S(C )s . Each St is an r-simplex in A (by Lemma 4.9), so it has exactly T r + 1 facets. Therefore Pσ = st=1 St is an r-dimensional polytope in A cut out by at most s(r + 1) facet-defining inequalities (it is r-dimensional because C ⊆ Pσ ⊆ A and dim(C ) = r). At each vertex u of Pσ , choose r active facet inequalities whose normals are linearly independent. The corresponding r hyperplanes meet in the unique point u. Hence distinct vertices can be assigned 1) distinct r-subsets of the at most s(r + 1) facets, so the number of vertices is at most (s(r+ r ). Learning Algorithm. If r = 0, return the hypothesis b h( x ) = 1{ x ∈ C }. Otherwise, enumerate all ordered s-tuples σ ∈ S(C )s . For each σ, compute Pσ , query the membership oracle on every vertex of Pσ , and return the first candidate all of whose vertices receive label 1. Write Pb for the returned candidate and b h( x ) := 1{ x ∈ Pb} for the output hypothesis. Lemma A.4 (One-Sided Error). The learner always halts, and its output hypothesis b h has no false posib tives. Moreover, P ⊆ C ⊆ P. Proof. By Lemma A.2, there exists σ⋆ ∈ S(C )s with Pσ⋆ ⊆ P⋆ . All vertices of Pσ⋆ lie in P⋆ and therefore receive label 1, so the learner eventually halts. Now let Pb be the returned candidate. Every vertex of Pb received label 1 and hence lies in P⋆ . Since P⋆ is convex and Pb is the convex hull of its vertices, Pb ⊆ P⋆ , and so b h has no false positives. Finally, P ⊆ C ⊆ Pb because every candidate polytope contains C. To control the false-negative error, we bound the VC dimension of the class of sets the learner can output. Define Td,s := { T1 ∩ · · · ∩ Ts : T1 , . . . , Ts are affine simplices of dimension at most d} . Every output Pb belongs to Td,s . Lemma A.5 (The Output Class Has Small VC Dimension). If Gd,s := { x 7→ 1{ x ∈ / T } : T ∈ Td,s } , 2 then VC(Gd,s ) = VC(Td,s ) = O sd log(sd) . Proof. Complementation preserves VC dimension, so it suffices to bound VC(Td,s ). Each simplex in Rd can be written as the intersection of at most 2d + 1 halfspaces, so every T ∈ Td,s is the intersection of at most s(2d + 1) halfspaces. By the standard VC bound for intersections of halfspaces in Rd , VC(Td,s ) = O(d · s(2d + 1) · log(s(2d + 1))) = O sd2 log(sd) . 1/ε) · sd2 log( sd ) · log1/ε + log1/δ Lemma A.6 (False-Negative Error). If m = O ( , then with prob / Pb ≤ ε. Consequently, Prx∼D b h( x ) = 0 and P⋆ ( x ) = 1 ≤ ε. ability at least 1 − δ, Prx∼D x ∈
51
b so the function g b( x ) := 1{ x ∈ Proof. By Lemma A.4, P ⊆ P, / Pb} ∈ Gd,s has empirical mean zero P on the sample. By Lemma A.5 and the standard VC bound for zero empirical error, if 2 VC(Gd,s ) log1/ε + log1/δ sd log(sd) · log1/ε + log1/δ m=O =O , ε ε then with probability at least 1 − δ, Prx∼D x ∈ / Pb ≤ ε. Since Pb ⊆ P⋆ (Lemma A.4) and D is supported on P⋆ , Pr b h( x ) = 0 and P⋆ ( x ) = 1 = Pr x ∈ / Pb ≤ ε.
x ∼D
x ∼D
2
Lemma A.7 (Query Complexity). The learner uses at most (2es)d ms(d +1) membership queries. Proof. If r = 0, no membership queries are made. Assume r ≥ 1. By the counting in the proof of 2 2 Lemma 4.13, |S(C )| ≤ md +1 , so the number of s-tuples is at most ms(d +1) . By Lemma A.3, each n 1) en k , Pσ has at most (s(r+ r ) vertices. Using ( k ) ≤ k
s (r + 1) r
≤
es(r + 1) r
r
≤ (2es)r ≤ (2es)d ,
since r ≥ 1 implies (r + 1)/r ≤ 2. The learner queries at most (2es)d vertices per candidate across 2 2 at most ms(d +1) candidates, giving at most (2es)d ms(d +1) membership queries in total. The theorem follows by combining Lemmas A.4, A.6 and A.7.
A.2
Learnability in Valiant’s Model Is Closed under Unions
In this section, we show that learnability is closed under unions. Theorem A.8 (Learnability Is Closed under Unions). Let H = (H1 , H2 , . . . ) and G = (G1 , G2 , . . . ) be sequences of concept classes that are learnable in Valiant’s model (Definition 1). Then their union H ∪ G := (H1 ∪ G1 , H2 ∪ G2 , . . . ) is also learnable in Valiant’s model. More precisely, if Hd and Gd admit query compression schemes of size qH (d) and qG (d) respectively, then there is a learner for H ∪ G that, for every d, ε, δ, uses at most d (qH (d) + qG (d)) + log 1/δ O examples and qH (d) + qG (d) membership queries . ε Setup. For K ∈ {H, G} and a transcript (q, r ), write VK (q, r ) := { f ∈ K : f (q) = r } , and similarly for VK (S) and VK (σ, r ). Fix a finite set S ⊆ {0, 1}d and a target h⋆ ∈ H ∪ G. For each K ∈ {H, G}, if VK (S) ̸= ∅, let ΣS,K be a query compression scheme for S of size at most k K , as guaranteed by Theorem 1.1; otherwise, let ΣS,K be an arbitrary depth-0 strategy. Run ΣS,K against the membership oracle for h⋆ and let rS,K denote the realized transcript. Define
DS,K :=
\
supp( f )
if VK (ΣS,K , rS,K ) ̸= ∅,
f ∈VK(ΣS,K ,rS,K )
{0, 1}d
otherwise. 52
First, we run the query compression scheme for each of the two classes H and G separately, and show that the resulting version-space closure either certifies the sample or rules out that class as containing the target. Lemma A.9. For K ∈ {H, G}, the following hold: 1. if h⋆ ∈ K, then S ⊆ DS,K ⊆ supp(h⋆ ); 2. if S ̸⊆ DS,K , then h⋆ ∈ / K. Proof. Suppose h⋆ ∈ K. Every point in S is positive for h⋆ , so h⋆ ∈ VK (S). Hence ΣS,K is a valid query compression scheme for S, and the realized transcript rS,K is realizable with respect to VK (S). The defining property of query compression gives S ⊆ DS,K . Moreover, since h⋆ itself generated the transcript rS,K , we have h⋆ ∈ VK (ΣS,K , rS,K ), and therefore DS,K ⊆ supp(h⋆ ). This proves the first item; the second is its contrapositive. Next, we discard any closure that fails to contain the sample and take the intersection of the survivors, and show that the resulting set CS still satisfies S ⊆ CS ⊆ supp(h⋆ ). Lemma A.9 provides exactly the dichotomy we need: for each class, the corresponding closure either certifies the sample or certifies that the target does not belong to that class. We now combine the two candidates. For K ∈ {H, G}, set ( DS,K if S ⊆ DS,K , CS,K := d {0, 1} otherwise, and define CS := CS,H ∩ CS,G . Lemma A.10. The set CS satisfies S ⊆ CS ⊆ supp(h⋆ ). Proof. Without loss of generality, suppose h⋆ ∈ H. By Lemma A.9, S ⊆ DS,H ⊆ supp(h⋆ ), so CS,H = DS,H . For the G-side, either S ⊆ DS,G , in which case CS,G = DS,G , or S ̸⊆ DS,G , in which case CS,G = {0, 1}d . In either case, S ⊆ CS,G . Combining gives S ⊆ CS,H ∩ CS,G = CS
and
CS ⊆ CS,H ⊆ supp(h⋆ ) .
Finally, we transfer this empirical guarantee to the population level via a finite-class uniform convergence argument. Lemma A.10 shows that after running both class-specific procedures and discarding any candidate that fails to contain the sample, the intersection CS is a one-sided consistent hypothesis with zero empirical false-negative error. It remains to show that this guarantee transfers to the population level. Proof of Theorem A.8. Fix ε, δ ∈ (0, 1), a target h⋆ ∈ H ∪ G, and a distribution D compatible with h⋆ . Draw an ordered sample x1 , . . . , xn ∼ D with
d (kH + kG ) + log 1/δ n≥Ω ε
53
,
and let S := { x1 , . . . , xn } be the underlying set of distinct sample points. Construct DS,H , DS,G , CS,H , CS,G , and CS as above, and output the indicator of CS . By construction, the learner uses exactly n examples and at most kH + kG membership queries. By Lemma A.10, the output satisfies S ⊆ CS ⊆ supp(h⋆ ), so it has no false positives and zero empirical false-negative error. It remains to bound the population false-negative rate. Consider the finite class C :=
n
n n o oo A ∩ B : A ∈ ClkH (Hd ) ∪ {0, 1}d , B ∈ ClkG (Gd ) ∪ {0, 1}d .
By construction, CS ∈ C, and Lemma 3.8 gives log |C| ≤ O(d (kH + kG )) . The rest of the proof is identical to the final step in the proof of Theorem 3.9. Applying the finite-class realizablecase uniform convergence argument to {C △ supp(h⋆ ) : C ∈ C} shows that, with probability at least 1 − δ, D(CS △ supp(h⋆ )) ≤ ε. Since CS ⊆ supp(h⋆ ) and supp(D) ⊆ supp(h⋆ ), this implies Prx∼D (CS ( x ) = 0 and h⋆ ( x ) = 1) ≤ ε. The output therefore satisfies the guarantees in Definition 1 with probability at least 1 − δ.
A.3
A Finite-VC Class whose 1-Point Closure has Infinite VC Dimension
In this section, we prove that when the domain is infinite, the VC dimension of the k-query closure class (Definition 14) can be much larger than that of the base class itself, even for k = 1. For each nonempty subfamily G ⊆ H and for a point p ∈ X, define Closure(G) :=
\ h ∈G
supp(h)
V( p, H) := { h ∈ H : p ∈ supp(h)} .
and
We prove the following result. Theorem A.11. There exists a countably infinite domain X and a hypothesis class H ⊆ {0, 1}X such that VC(H) = 2, but the 1-point closure class Cl1 (H) := {Closure(V( p, H)) : p ∈ X} (Definition 14) has infinite VC dimension. Proof. Let Q := {qi : i ∈ N}
R := {r A : A ⊆ N finite} ,
and
and set X := Q ∪ R. Since the family of finite subsets of N is countable, both Q and R are countable, and therefore X is countably infinite. For every finite set A ⊆ N and every i ∈ N \ A, define a hypothesis h A,i : X → {0, 1} by h A,i (r B ) := 1{ B = A}
and
h A,i (q j ) := 1{ j ̸= i } .
Let H := { h A,i : A ⊆ N finite and i ∈ N \ A} . We first show that VC(H) = 2. Claim A.12. It holds that VC(H) = 2. Proof. The set {r∅ , q1 } is shattered, since h∅,2 , h∅,1 , h{1},2 , h{2},1 realize the four labelings (1, 1), (1, 0), (0, 1), and (0, 0) on {r∅ , q1 }, respectively. Thus VC(H) ≥ 2. Conversely, no 3-point subset of X is shattered by H. Indeed, if T ⊆ X has size 3, then T contains either at least two points 54
of R or at least two points of Q. In the first case, no hypothesis in H labels both of those R-points by 1, since every h A,i is positive on exactly one point of R. In the second case, no hypothesis in H labels both of those Q-points by 0, since every h A,i is negative on exactly one point of Q. So T is not shattered, and therefore VC(H) ≤ 2. Hence VC(H) = 2. Now fix a finite set A ⊆ N. We claim that Closure(V(r A , H)) = {r A } ∪ {qi : i ∈ A} . Indeed, V(r A , H) = { h A,i : i ∈ N \ A}, since a hypothesis contains r A if and only if its first index is exactly A. Every hypothesis in this family contains r A , so r A ∈ Closure(V(r A , H)). If j ∈ A, then every h A,i with i ∈ N \ A satisfies i ̸= j, and hence h A,i (q j ) = 1; thus q j ∈ Closure(V(r A , H)). If j ∈ / A, then h A,j ∈ V(r A , H) and h A,j (q j ) = 0, so q j ∈ / Closure(V(r A , H)). Finally, if B ̸= A, then every hypothesis in V(r A , H) labels r B by 0, so r B ∈ / Closure(V(r A , H)). This proves the claim. To conclude, let Tn := {q1 , . . . , qn }. We show that Tn is shattered by Cl1 (H) for every n ∈ N. Fix any subset B ⊆ {1, . . . , n}. Since B is finite, the point r B belongs to X, and by the previous paragraph, Closure(V(r B , H)) = {r B } ∪ {qi : i ∈ B} . Therefore Closure(V(r B , H)) ∩ Tn = {qi : i ∈ B} . Thus every subset of Tn is realized by some member of Cl1 (H), so Tn is shattered by Cl1 (H). Since this holds for every n, we conclude that VC(Cl1 (H)) = ∞.
B
Proof of Theorem 3.4 (Boosting; Deferred from Section 3)
In this section, we prove Theorem 3.4. Toward this, we first prove the following intermediate result: Lemma B.1 (Confidence Amplification). Suppose H is learnable in Valiant’s model (Definition 1), and let mW (d, ε, δ) denote the sample/query complexity of some learner witnessing this. Fix m := mW (d, 1/18, 1/3) .
(8)
Then for every η ∈ (0, 1/2], there is a learner Lη , s.t., for every target h⋆ ∈ Hd and every distribution µ compatible with h⋆ , with probability at least 1 − η the learner Lη outputs a hypothesis satisfying the Valiant conditions with error parameter 1/3, while using O(m log 1/η ) example-oracle calls and membership queries. Proof. Fix d ∈ N, η ∈ (0, 1/2], a target h⋆ ∈ Hd , and a distribution µ compatible with h⋆ . Let L0 be a learner witnessing the learnability of H in Valiant’s model with sample/query complexity mW . Thus, when run with parameters (d, 1/18, 1/3), the learner L0 uses at most m example-oracle calls and at most m membership queries, and with probability at least 2/3 outputs a hypothesis with no false positives and false-negative mass at most 1/18 under µ. Let 1 k := C log , η
55
where C > 0 is a sufficiently large absolute constant. Run L0 independently kntimes on fresh data o and let h1 , . . . , hk be the resulting hypotheses. Output their majority: h( x ) := 1 ∑kj=1 h j ( x ) ≥ k/2 . Call run j successful if: h j has no false positives
and
1 Pr h j ( x ) = 0 ≤ . x ∼µ 18
(Successful run)
Each run is successful with probability at least 2/3, and these events are independent across j. Hence, by a Chernoff bound, with probability at least 1 − η at least 3k/5 runs are successful. Let E denote this event. No false positives. Assume E holds and fix any x ∈ {0, 1}d with h⋆ ( x ) = 0. Every successful h j satisfies h j ( x ) = 0, so at most the unsuccessful runs can output 1 on x. Since there are at most 2k/5 unsuccessful runs, fewer than half of the h j ’s output 1 on x. Therefore h( x ) = 0. Thus h has no false positives. Upper bound on false negatives. Assume E and let G ⊆ [k ] be the set of successful indices. Then | G | ≥ 3k/5. Fix any x ∈ {0, 1}d with h( x ) = 0. At least k/2 of the values h j ( x ) are 0. Even k successful runs must if every unsuccessful run outputs 0, at least 2k − (k − | G |) = | G | − 2k ≥ 10 3k G | | also output 0. Since | G | ≥ /5, this quantity is also at least /6. Therefore, 1{ h( x ) = 0} ≤ 6 · |G1 | ∑ j∈G 1 h j ( x ) = 0 . Taking expectation over x ∼ µ gives Pr (h( x ) = 0) ≤ 6 ·
x ∼µ
1 1 1 = . Pr h j ( x ) = 0 ≤ 6 · ∑ 18 3 | G | j∈ G x ∼µ
The learner makes k independent runs of L0 , each using at most m example-oracle calls and at most m membership queries. Hence the total sample/query complexity is O(m log 1/η ) for each type of oracle. By the preceding no-false-positive and false-negative arguments, on the event E the output h satisfies the Valiant conditions with error parameter 1/3. This suffices to complete the proof since Pr (E ) ≥ 1 − η. Proof of Theorem 3.4. Fix δ ∈ (0, 1/2]. Fix d ∈ N, ε ∈ (0, 1), a target h⋆ ∈ Hd , and a compatible distribution D. Recall that m := mW (d, 1/18, 1/3) from (8). By Lemma B.1, for every η ∈ (0, 1/2] there is a learner Bη such that on every compatible distribution µ, with probability at least 1 − η, the learner Bη outputs a hypothesis g satisfying the Valiant conditions with error parameter 1/3, while using O(m log 1/η ) example-oracle calls and at most the same number of membership queries. By the structural observation preceding this section, we may assume that Bη first draws all its example samples and only then makes its membership queries. Let T := log3 1/ε
and
ws :=
1 = 3s τs
τs := 3−s
for s ∈ {0, 1, . . . , T } ,
and define weights T
and
W := ∑ ws . s =0
56
Then W = O(1/ε). For each scale s ∈ {0, 1, . . . , T }, let ηs :=
δws . 100W
δ Since ∑sT=0 ws = W, we have ∑sT=0 ηs ≤ 100 . We now describe the learner. Initialize H0 ≡ 0. For each scale s = 0, 1, . . . , T, given Hs , let
ps := Pr ( Hs ( x ) = 0) . x ∼D
Because D is compatible with h⋆ , this is exactly the D-mass of the current residual positive region. log 1/η
Testing the residual mass. Draw As := C1 τs s fresh samples from D, where C1 > 0 is a sufficiently large absolute constant. Let pbs be the fraction of these samples on which Hs ( x ) = 0. By a Chernoff bound, with probability at least 1 − ηs the following two implications hold simultaneously: ps ≥ τs =⇒ pbs ≥
2τs 3
and
ps ≤
τs 2τs =⇒ pbs < . 3 3
(9)
If pbs < 2τs/3, set Hs+1 := Hs and continue to the next scale. Simulating the residual oracle. Otherwise, draw fresh samples from D until either O(m log 1/ηs ) m log 1/ηs +log 1/ηs of them satisfy Hs ( x ) = 0, or until a budget of Bs := C2 original example-oracle τs calls has been exhausted, where C2 > 0 is a sufficiently large absolute constant. If the budget is exhausted first, declare failure. Otherwise, let Ss be the first O(m log 1/ηs ) retained points. These are i.i.d. samples from the conditional distribution of D given Hs ( x ) = 0. Moreover, on the residual-test event in (9), whenever we simulate the residual oracle we have ps > τs /3; hence, conditioned on the past, by another Chernoff bound and for C2 large enough, the probability that the residual-oracle simulation fails is at most ηs . Learning on the residual distribution. Run Bηs on the simulated residual examples Ss and the membership oracle for h⋆ , and let hs be the output. Set Hs+1 ( x ) := Hs ( x ) ∨ hs ( x ). Let E be the event that every residual-mass test, every residual-oracle simulation, and every call to Bηs succeeds. By a union bound, Pr (E ) ≥ 1 − 3 ∑sT=0 ηs ≥ 1 − δ, after adjusting the absolute constants. An Invariant. On E , for every s ∈ {0, 1, . . . , T + 1} the hypothesis Hs has no false positives. Moreover, for every s ∈ {1, 2, . . . , T + 1}, ps ≤ τs−1 .
(10)
We prove this by induction on s. The statement for s = 0 is trivial. Assume it holds for some s ∈ {0, 1, . . . , T }. If the residual-mass test skips scale s, then on E either ps ≤ τs /3 or ps (τs /3, τs ). In either case, ps+1 = ps ≤ τs , and Hs+1 = Hs still has no false positives. Suppose instead that we simulate the residual oracle. On E , the residual-test guarantee (9) 57
guarantees that ps > τs /3. Let µs denote D conditioned on Hs ( x ) = 0. Since D is compatible with h⋆ and Hs has no false positives, the distribution µs is also compatible with h⋆ . Because the call to Bηs succeeds on E , the hypothesis hs has no false positives and Prx∼µs (hs ( x ) = 0) ≤ 31 . Therefore Hs+1 = Hs ∨ hs has no false positives, and ps+1 = Pr ( Hs ( x ) = 0 and hs ( x ) = 0) = ps Pr (hs ( x ) = 0) ≤ x ∼D
x ∼µs
ps . 3
If s = 0, then p0 ≤ 1, so p1 ≤ 13 = τ0 . If s ≥ 1, then the induction hypothesis gives ps ≤ τs−1 , and hence ps+1 ≤ τs3−1 = τs . This completes the induction. Correctness. By the no-false-positive invariant and (10), on E the final hypothesis HT +1 has no false positives and Pr ( HT +1 ( x ) = 0) = p T +1 ≤ τT = 3−T ≤ ε. x ∼D
Since D is compatible with h⋆ , this is exactly the required false-negative guarantee. 1 Membership-query complexity. Each invocation of Bηs uses O(m log /ηs) membership queries.
Hence the total number of membership queries is at most O m ∑sT=0 log 1/ηs . Since ηs ≥ δ/(100W ) for every s, this is m · O( T log 100W/δ) . Now T = O(log 1/ε) and W = O(1/ε), so 100W 1 1 1 1 2 1 T log = O log + log log =O log , δ ε ε δ ε δ
because δ ≤ 1/2 implies log 1/δ = Ω(1) and log 1/ε ≤ 1/ε. Therefore the membership-query complexity is m · O((1/ε) log 1/δ) . Example-oracle complexity. At scale s, the residual-mass test uses As = O((1/τs ) log 1/ηs ) samples from the original example oracle. The residual-oracle simulation uses at most Bs = O((m/τs ) log 1/ηs ) additional samples fromthe original example oracle. Since m ≥ 1, the total number of original example-oracle calls is O m ∑sT=0 (1/τs ) · log 1/ηs . Now
T T 100W 1 100W log 1/ηs = ∑ ws log = W log + ∑ ws log . τs δws δ s =0 ws s =0 s =0 T
∑
Also, wWs = ∑ Tj=0 3 j−s = O 3T −s + 1 , so T
100W ∑ ws log ws = O s =0
T
∑ 3s ( T − s + 1 )
!
= O (W ) .
s =0
Because δ ≤ 1/2, this is O(W log 1/δ) . Therefore, T
log 1/ηs 1 1 1 ∑ τs = O W log δ = O ε log δ . s =0 It follows that the total number of original example-oracle calls is O((m/ε) log 1/δ) . Combining this with the membership-query complexity proves the claimed sample/query complexity.
58