arXiv:2606.28309v1 [stat.ML] 26 Jun 2026
Surprises in Proper Positive-Only Learning Shai Ben-David
Farnam Mansouri
University of Waterloo and Vector Institute
University of Waterloo and Vector Institute
Anay Mehrotra
Manolis Zampetakis
Stanford University
Yale University
Abstract Binary classification from positive-only samples is a variant of PAC learning in which the learner receives i.i.d. samples from the positive region of an unknown target concept, but is evaluated under the original distribution (which places mass on both positive and negative regions). This model dates back to [Nat87, STOC], and the characterization of improper learning is well-known – it even appears in textbooks [KV94, Exercise 3.7]. The characterization of proper positive-only learning, however, has long remained open. In this work, we revisit and settle this question: a concept class is properly learnable from positive-only samples if and only if it has finite VC dimension and satisfies a new combinatorial condition, which we call uniform exterior separability. Together with several separation results, this characterization reveals a surprisingly rich landscape that differs sharply from standard PAC learning: proper and improper learning are separated, randomized and deterministic proper learning are separated, there are classes for which no ERM is a learner, and finite VC dimension does not suffice even for non-uniform learning. Along the way, we introduce new combinatorial dimensions that we believe can be of broader interest in learning theory.
1
Introduction
In the celebrated PAC learning model [Val84a], a learner observes positive and negative examples drawn from an unknown distribution and must output a classifier with small misclassification error. This formulation assumes that the learner has access to labeled samples from both sides of the target concept. However, in practical scenarios, this assumption is often violated because negative examples are expensive to collect, scarce, or completely absent. This issue was already motivated by Valiant, who wrote: “While it may be reasonable to discuss the distribution of the attributes of elephants, we may prefer not discussing the distribution of the attributes of non-elephants” — [Val84b]. It also arises in many modern applications: for instance, in medical diagnosis, confirmed cases of a condition are recorded but healthy controls may be unlabeled [EN08]; in web search and recommendation systems, engagement provides positive feedback while non-engagement remains ambiguous [LDLL+03]. These practical challenges can be modeled through a natural extension of the PAC framework, where the learner receives positive samples, but receives no negative samples.
1
Let D be an unknown distribution over the feature space X , and let h⋆ ∈ H be the target concept. The learner receives a multiset of n i.i.d. samples from the conditional distribution D+ = D | (h⋆ ( X ) = 1), and outputs a hypothesis whose error is measured under the original distribution D . Definition 1 (PAC Learning with Positive-Only Samples; cf. [KV94, Exercise 3.7]). A class H is learnable from positive-only samples if there exist a sample-complexity function n : (0, 1)2 → N and a learner A such that, for every accuracy and confidence parameters ε, δ ∈ (0, 1), every distribution D over X , and every target h⋆ ∈ H with PrX ∼D [h⋆ ( X ) = 1] > 0, given n(ε, δ) i.i.d. samples from D+ , A outputs a hypothesis b h satisfying PrX ∼D (b h( X ) ̸= h⋆ ( X )) ≤ ε , with probability at least 1 − δ over the sample and the learner’s internal randomness. Note that although the learner only sees samples from D+ , the hypothesis b h is evaluated under the full distribution D , which has mass on both the positive and the negative regions. The positive samples identify points that must be labeled positive, but they give no information about the negative region, where the learner must still avoid too many false positives. A learner is said to be proper if it always outputs a hypothesis in H, and improper otherwise (if it can output a hypothesis that is outside of H). In ordinary PAC learning, both types of learners are equally powerful: a class is PAC learnable if and only if it has finite VC dimension VCdim(H) < ∞. Moreover, whenever VCdim(H) < ∞, every empirical risk minimization (ERM) rule, which is any rule that returns a hypothesis in H consistent with the labeled samples, is a PAC learning algorithm.1 For positive-only learning, the improper version admits a clean characterization: Let H∩ denote the class of finite intersections of concepts in H. Then H is improperly learnable from positiveonly samples if and only if VCdim(H∩ ) < ∞ [KV94]. Gereb-Graus [Ger89] gives an alternate combinatorial characterization, which even appears as a textbook exercise [KV94, Exercise 3.7]. Recent work of Hanneke [Han24], as a corollary, pins down the tight sample complexity of improper positive-only learning via a dimension called the one-centered star number; see Mehrotra [Meh26] for an overview. However, despite the improper case being very well understood, and there being decades of work on various variants of PAC learning [Hau90], including variants of positive-only learning [Nat87; Shv90; Kiv95; FJK96; NR09; AGR13; DDS15; KTZ19; CDS20; MB25; LMZ26], the following natural question has remained unresolved: What is the characterization of learnability for proper positive-only PAC learning? Our contributions. In this work, we settle this question, and show that proper positive-only learning has a very rich structure. We make the following contributions. 1. A characterization of proper positive-only learning (Theorem 4). We prove that H is properly learnable from positive-only samples if and only if VCdim(H) < ∞ and H satisfies a new combinatorial condition, uniform exterior separability (Definition 3), which controls false positives in the parts of the input space not forced to be positive by the sample. 1While every ERM is a PAC learner, ERM rules, in general, do not attain the optimal sample complexity [Han16b;
Han16a; Lar23].
2
2. Separations from ordinary PAC learning (Theorems 6, 7, 8 and 14). Together with several separation results, our characterization shows that the landscape of learnability for proper positive-only learning is considerably different from that of ordinary PAC learning. In particular: (a) Proper and improper learning are separated (Theorem 14); (b) Randomized and deterministic proper learning are separated (Theorem 6); (c) There exist classes for which no deterministic ERM rule is a learner (Theorem 7); and (d) Finite VC dimension does not suffice even for non-uniform learning (Theorem 8). 3. Randomness as a resource (Theorems 5 and 6). We quantify the randomness needed for proper positive-only learning. On the positive side, we show that very few random bits suffice: if H admits a randomized proper learner from positive-only samples, then it admits one that e (d + log 1/ε) random bits (where d = VCdim(H)) and O e (d/ε) positive samples uses only O (Theorem 5). For classes of constant VC dimension (i.e., d = O(1)), this is exponentially fewer random bits than samples. On the negative side, as mentioned above, randomness cannot be eliminated entirely: there exist classes that are properly learnable by a randomized learner but by no deterministic one (Theorem 6). 4. A characterization of stable proper positive-only learning (Theorem 9). We also study a notion of stability for proper learners, which requires the learner’s output to remain unchanged when given additional samples consistent with its current hypothesis (Definition 5), in the spirit of stable sample compression schemes [BHMZ20]. We show that H is properly learnable by a stable learner if and only if VCdim(H) < ∞ and H satisfies exact exterior separation (Definition 2), a strict strengthening of uniform exterior separability (Theorem 9). More broadly, we view our results as part of an effort to understand how the right combinatorial dimension changes under different supervision models. The dimensions and conditions we introduce here, particularly the exterior separability notions, do not coincide with VC dimension and other standard parameters, and we expect they will find use beyond positive-only learning, in settings where the learner must extrapolate from limited supervision.
1.1
Related Work
We have already discussed key related work on learning from positive-only samples when motivating the model. Here, we situate our results within several neighboring literature. Learning with One-Sided Error. Positive-only learning has also been studied under the additional restriction that the learner makes no false-positive errors, known as the one-sided error model. Natarajan [Nat87] initiated this line of work and characterized proper learnability in the one-sided error setting. Subsequently Shvaytser [Shv90] and Kivinen [Kiv95] characterized improper learning and bounded its sample complexity. Natarajan conjectured that his characterization extends to the (two-sided) proper positive-only learning model studied in this paper.2 We disprove this conjecture in Theorem 15 (which, in turn, utilizes our main characterization; Theorem 4). 2 In support, he analyzed the two-sided problem under the uniform distribution, remarking that “if the distribution is
allowed to be arbitrary, we can show easily that any learning algorithm can be forced to deviate from the function to be learned with probability approaching unity.”
3
Distribution-Specific Positive-Only Learning. Several works study positive-only learning under specific distributional assumptions. When the distribution is Gaussian, Kontonis, Tzamos, and Zampetakis [KTZ19] and Lee, Mehrotra, and Zampetakis [LMZ24a] design computationally efficient algorithms with guarantees for concept classes with bounded Gaussian surface area. For unknown distributions satisfying a mild smoothness condition, Lee, Mehrotra, and Zampetakis [LMZ26] gave methods for learning all finite-VC classes as well as classes approximable by polynomials, and Kouridakis, Mehrotra, Kalavasis, and Caramanis [KMKC26] obtained a polynomial-time algorithm for finite-VC classes on the real line. A separate line studies positive-only learning when the distribution of positive examples is explicitly given to the learner [FJK96; NR09; RG09; AGR13; DDS15; CDS20; KKV23]. In contrast to all these works, and as is standard in statistical learning theory, we do not attempt to design computationally efficient algorithms and, instead, obtain characterizations of learnability, with a particular focus on proper learners. Learning from Positive and Unlabeled Examples. The positive-and-unlabeled (PU) model gives the learner access to unlabeled samples in addition to positive examples [Den98; LLYL02; EN08; BLS10; DNS15; BD18; LMZ24a; MB25; LMZ26]. Especially relevant to our work, Mansouri and BenDavid [MB25] proved lower bounds on the number of unlabeled samples required for PU learning, demonstrating a separation between PU learning and learning from positive examples alone. Out-of-Distribution Detection. The problem of learning from positive samples is also closely related to theoretical work on out-of-distribution detection. In the binary case, OOD detection can be viewed as learning from positive-only examples. The results of Fang, Li, Lu, Dong, et al. [FLLD+22] and Fang, Li, Liu, Han, et al. [FLLH+24] imply that consistency is impossible in full generality in the agnostic setup, and identify conditions under which consistency can be recovered. While in some of our results, we also consider consistency, our focus is on the stronger requirement of bounding the sample complexity of learning instead of just consistency. Language Identification in the Limit. The line of work on language identification in the limit, e.g., Gold [Gol67], Angluin [Ang79], and Angluin and Laird [AL88] can also be viewed as learning from positive examples only, but with a different success criterion: the sample size is allowed to depend on the target concept and on the order in which positive examples are presented. Thus, this line of work is closer in spirit to non-uniform learnability than to the uniform PAC-style guarantees studied here. Stochastic versions of these frameworks have also been studied [Ang88; KMV25; HP26] in the universal-learning formulation of [BHMv+21], which is quite different from the PAC learning model that we study here.
2
Preliminaries
In this section, we introduce basic notation and preliminaries. e (·), Notation. We use f ≲ g and f ≃ g to denote f = O( g) and f = Θ( g) respectively. We use O [∗] e e Ω(·), and Θ(·) to hide poly-logarithmic factors. Further, for a set A, we use A to denote the set of all finite multi-sets of members of A, and A∗ as the set of all finite sequences of elements of A. (A multi-set contains repetitions of instances, but not their order. A sequence also records their order.) Positive-only learning. Let H denote a concept class over a domain X . (Formally, H is a set of subsets of X .) We identify each concept with the set of points that it labels positive. A realizable
4
instance of positive-only learning is specified by an unknown distribution D over X and an unknown target concept ℓ ∈ H with D(ℓ) > 0. For measurable A ⊆ X , we define
D+ ( A) := D( A | x ∈ ℓ)
D− ( A) := D( A | x ∈ / ℓ)
and
whenever the conditioning is well-defined. The learner observes only positive examples, i.e., an i.i.d. sample from D+ . A hypothesis is a subset h ⊆ X and its loss or error is evaluated under the full distribution D : errD (h, ℓ) := D(h△ℓ) for h ⊆ X . Learning algorithms and sample complexity. A proper learning algorithm, or simply a proper learner A, is a function A : X [∗] × Ω → H where Ω = {0, 1}N provides a sequence of (potentially) random bits. For a fixed sample S+ ∈ X ∗ , we use A(S+ ) as shorthand for the random variable ω 7→ A(S+ , ω ). We say that a concept class H is learnable from positive-only samples by a proper learner A if there exists a function mH : (0, 1) × (0, 1) → N so that for every distribution D over X and every ℓ ∈ H, every accuracy and confidence ε, δ ∈ (0, 1), and every number n ≥ mH (ε, δ), with probability at least 1 − δ, the learner has an error at most ε, i.e., PrS+ ∼D+n ,A (errD (A (S+ ) , ℓ) ≤ ε) ≥ 1 − δ . Version space and closure. The concept of a closure of a sample set is frequently used in learning theory and will also be central in our characterizations. Consider a finite sample of “positive” points S ⊆ X realized by H. (Formally, S is a positive sample set realizable by H if there is some h ∈ H such that S ⊆ h.) The version space HS of S is the set of all hypotheses in H consistent with S. In other words, it is the set of all hypotheses that could be the target concept. Formally,
HS := {h ∈ H : S ⊆ h} .
(Version Space)
The closure of S with respect to H is the intersection of all hypotheses h in the version space, i.e., CLOSH (S) :=
\ h∈HS
h.
(Closure)
In particular, the closure is the largest subset of the domain that is guaranteed to be a subset of all hypotheses in the version space HS . In particular, since the target concept ℓ is always in the version space, CLOSH (S) is a subset of ℓ.
3
Characterizing Conditions
In this section, we introduce the conditions used to characterize proper positive-only learning. All of the conditions are stated using the closure operator from Section 2. Recall that if S is a finite set of observed positive examples and S ⊆ ℓ ∈ H, then CLOSH (S) ⊆ ℓ. Thus every point in CLOSH (S) is forced to be positive by the sample and the realizability assumption. The main challenge is what happens outside the closure. A point x ∈ / CLOSH (S) is not forced to be positive by the sample, and a proper learner must still output a member of H without labeling too much of this outside region as positive. The conditions below capture different ways in which hypotheses from H can control this outside region. 5
The improper benchmark. Before stating the conditions, it is useful to recall the characterization of improper positive-only learning. Let H∩ denote the finite-intersection closure of H: n\ o H∩ := h : A ⊆ H is finite . h∈A
(Here, the empty intersection is interpreted as X .) For instance, if H is the class of halfspaces in Rd , then H∩ contains all polyhedra obtained as intersections of finitely many halfspaces. Theorem 1 (Improper positive-only learning; [Ger89]; see also [KV94; LMZ26]). A concept class H is improperly learnable from positive-only samples if and only if VCdim (H∩ ) < ∞. The learning algorithm is simple: given positive samples S, it outputs CLOSH (S). Since this closure lies in H∩ but generally not in H, the learning algorithm is improper. A proper learner cannot do this, and the conditions below ask, in increasingly weaker forms, how well concepts in H can mimic this. The strongest condition asks that the closure itself is always proper. Definition 2 (Exact Exterior Separation). We say that H satisfies exact exterior separation if for every finite nonempty realizable set S ⊆ X , CLOSH (S) ∈ H. Under exact exterior separation, the proper learner can directly output CLOSH (S), recovering the improper strategy while being proper. This condition, however, turns out to be too strong (there are classes which violate this property while still being properly learnable from positive examples). Hence, we consider the following weaker version. Definition 3 (Uniform Exterior Separability). We say that H satisfies uniform exterior separability if for every η > 0 there exists an integer M (η ) such that for every finite nonempty realizable set S ⊆ X , there are hypotheses hS,1 , . . . , hS,M(η ) ∈ HS satisfying supx∈/CLOSH(S)
1 |{i ∈ {1, . . . , M(η )} : x ∈ hS,i }| ≤ η . M(η )
Here, instead of a single consistent hypothesis avoiding every exterior point, we ask only for a bounded list of consistent hypotheses, whose individual members may make false positives, but which on average covers any single exterior point only “sparingly.” The key point is that M(η ) depends only on η, and not on S. Equivalently: a hypothesis drawn uniformly from the list labels any fixed exterior point as positive with probability at most η. Finally, observe that exact exterior separation (Definition 2) is the special case M(η ) = 1 with hS,1 = CLOSH (S). The next condition replaces the uniform distribution over a bounded list with an arbitrary distribution, which is a bit more natural for randomized learners. Definition 4 (Distributional Exterior Separability). We say that H satisfies distributional exterior separability if for every finite nonempty realizable set S ⊆ X and every η > 0, there exists a probability distribution µS,η supported on HS such that supx∈/CLOSH(S) Prh∼µS,η ( x ∈ h) ≤ η .
6
In the next section, we use these conditions to give our main characterization. Before that, we establish the following relationships between these conditions to build some intuition; the proof is deferred to Section B.1. Proposition 2 (Relations between the exterior conditions). For every concept class H, exact exterior separation =⇒ uniform exterior separability
=⇒ distributional exterior separability . Moreover, the first implication is strict. The two implications follow from the definition of the conditions. Strictness of the first implication is important to refute a conjecture of [Nat87] (see Section 1.1). The second implication may not be strict in general. However, interestingly, using tools from the study of sample compression schemes [MY16], we are able to prove that distributional exterior separability implies uniform exterior separability for classes H with finite VC dimension, and this result turns out to be crucial for our characterization. The proof of this result appears in Section B.3. Theorem 3 (From distributional to uniform exterior separability). Suppose that VCdim (H) < ∞. If H satisfies distributional exterior separability, then H satisfies uniform exterior separability.
4
Our Results
In this section, we state our main results. Our first result settles the question posed in Section 1. Theorem 4 (Main characterization). The following are equivalent: 1. H is properly learnable from positive-only samples; 2. H satisfies uniform exterior-separability (Definition 3) and VCdim (H) < ∞. Thus, uniform exterior-separability plays the role for proper positive-only learning that finite VC dimension plays for ordinary PAC learning. This characterization is strictly stronger than that of improper positive-only learning (Theorem 14; see Section B.2 for a proof). Thus, unlike ordinary PAC learning, where requiring the learner to be proper does not change which classes are learnable, characterizations of proper and improper learning differ in the positive-only model, e.g., [SB14]. The proof of Theorem 4 appears in Section C.1. The learner in Theorem 4 is randomized, raising the question: how much randomness is needed for learning? Randomness is a fundamental algorithmic resource (alongside time and memory) and is widely studied in theoretical computer science [AB09]. It has also been extensively studied in learning theory both as a resource to minimize [CMY23; FHMM23; LMZ24b; HM25] and through models in which the learner or environment must be deterministic [Maa91; SS97; OS18]. Our next result shows that a very small number of random bits suffice for learning. To state our result, we need to recall the definition of the dual concept class H⋆ : for a binary class H ⊆ {0, 1} X , its dual class is H⋆ := {h 7→ h( x ) : x ∈ X } ⊆ {0, 1} H . (Here, each point x ∈ X defines a binary function on hypotheses by evaluating them at x.) The dual class H∗ is useful because VCdim(H∗ ) controls how many sample points are needed to distinguish hypotheses in H; this parameter appears throughout learning theory, perhaps most famously in bounds on the size of sample-compression schemes [MY16]. 7
Theorem 5 (Few random bits suffice). Consider a concept class H and its dual H⋆ . Let d = VCdim (H) and d⋆ = VCdim (H⋆ ). The following are equivalent: 1. H is properly PAC learnable from positive-only examples by a randomized learner. 2. H is properly PAC learnable from positive-only examples by a learner using at most e (log (d⋆/εδ)) random bits r (ε, δ) = O
e ((1/ε) (d + log 1/δ)) positive samples . m (ε, δ) = O e (d + log (1/εδ)) . In particular, by Assouad’s bound [Ass83], d⋆ < 2d+1 , so r (ε, δ) = O and
e (log 1/εδ). This is much For classes with VC dimension O(1), the number of random bits is only O smaller than the number of samples: even in ordinary PAC learning with positive and negative examples, the sample complexity is Ω(1/ε), which is exponentially larger. For additional details and proof of Theorem 5 we refer the reader to Section C.2. Given that so few random bits suffice, one might hope that randomness can be removed entirely. Our next result shows that this is not possible: some classes are properly learnable by a randomized learner but by no deterministic learner. Theorem 6 (Randomness is necessary). There exists a concept class H that is properly positive-only learnable by a randomized learner, but not by any deterministic learner. Thus, the power of randomized and deterministic learners is different in the proper positiveonly learning model. This is another contrast with ordinary PAC learning where characterizations of deterministic and randomized proper learning are equivalent, e.g., [BEHW89; EHKV89]. The proof of Theorem 6 appears in Section C.3. The preceding results already give two separations between positive-only learning and ordinary PAC learning: proper and improper learning differ (Theorem 4; also see Theorem 14), and randomized and deterministic proper learning differ (Theorem 6). We next state three further separations. Separation III: ERM is not a universal learner for positive-only learning. In the realizable PAC model, if a class H is learnable, then it is learnable by every empirical risk minimization (ERM) rule. An ERM rule is any rule that outputs any hypothesis from H consistent with the observed samples. Specifically, in the positive-only model, a learning rule is ERM if it outputs a hypothesis that contains all the observed positive examples. Our next result shows that such rules are not universal learners for deterministic proper positive-only learning. Its proof appears in Section D.3. Theorem 7 (ERM is not a universal deterministic learner). There exists a concept class H that is properly positive-only learnable by deterministic learners, but no deterministic proper ERM learner learns H from positive-only examples. Separation IV: Finite VC dimension does not imply non-uniform learnability. So far, we have focused on “uniform” guarantees on the sample complexity, where the sample complexity is the same for all target concepts. Non-uniform PAC learning relaxes this and allows the required sample size to depend on the target concept. Consistency further relaxes this: it only requires the error to converge to 0 for each fixed distribution-target pair as the number of samples goes to ∞ without requiring any specific rate for this convergence. (We refer the reader to Section A for formal definitions.) Both non-uniform and consistency guarantees are widely-studied in learning theory [Sto77; BI88; BJ93; BHMv+21; Lu24] and below we study these notions for proper positive-only learning. We show that these notions remain distinct for positive-only learning, even for classes of finite VC dimension; see Section D.4 for the proof. 8
Theorem 8 (Separation of learnability, non-uniform learnability, and consistency). There exist concept classes H1 and H2 , each with VC dimension 1, such that: 1. H1 is properly positive-only consistent, but not non-uniformly properly positive-only learnable. 2. H2 is non-uniformly properly positive-only learnable, but not properly positive-only learnable. Stable proper positive-only learning. Stability is a standard way to formalize the idea that small changes to the sample should not substantially change the output of the learner. We end with a characterization of stable proper positive-only learning. Concretely, we study the following notion of stability, which matches the notion of stable compression schemes introduced by Bousquet, Hanneke, Moran, and Zhivotovskiy [BHMZ20]. Definition 5 (Stability). Consider a proper learner A. The learner A is said to be stable if, for any multi-sets S, S′ ∈ X [∗] , with probability 1 over any randomness in A, the following holds if
S ⊆ S′ and Domain(S′ ) ⊆ A(S),
then
A(S′ ) = A(S) ,
where Domain(S′ ) is the set of distinct elements in S′ . The characterization shows that stability brings us back to exact exterior separation, the strongest closure condition from Definition 2. Theorem 9 (Characterization for stable learners). The following are equivalent: 1. H is properly positive-only learnable by a stable learner. 2. H satisfies exact exterior separation (Definition 2) and VCdim (H) < ∞. In fact, the necessity of exact exterior separation (Definition 2) and bounded VC dimension holds even under a weaker notion of stability. We refer the reader to Section D.5 for further details and the proof of Theorem 9.
5
Technical Overview
In this section, we outline the proof of our main results. A Natural Approach to Proper Positive-Only Learning. A natural way to learn from positiveonly examples is to output the closure of the observed positive samples S+ , namely CLOSH (S+ ) := T h∈H : S+ ⊆h h. This is an ERM rule for positive-only learning and has the property that it makes no false positive errors (since the target ℓ itself contains S+ and so is a part of the intersection). Its false negative errors are less straightforward but, if the output belongs to a finite VC dimension class, then it can be bounded using standard tools. The key issue is that it may not be proper as the closure can fall outside H. If H is intersection-closed, then this issue disappears, and combined with finite VC dimension, this closure rule becomes a proper positive-only learner. This sufficient condition was already known from the work of Natarajan [Nat87], who additionally showed it is necessary if the learner is required to satisfy an additional constraint—make no false positive errors—and conjectured that it remains necessary even without this additional constraint. A consequence of our main characterization, Theorem 4, is that this conjecture is false.
9
Refuting Natarajan’s Conjecture. To build toward the proof of Theorem 4, we first describe how we refute Natarajan’s conjecture. Consider the class
Hspr := {{1} , {2}} ∪ {{1, 2, i } : i ≥ 3} on the domain N. This class has finite VC dimension but is not intersection-closed. For instance, / Hspr . So the closure rule cannot be applied properly: after seeing a {1, 2, 3} ∩ {1, 2, 4} = {1, 2} ∈ sample S+ consisting of only 1s and 2s, the closure {1, 2} is the “safe” answer but it does not belong to Hspr , and Natarajan’s conjecture would, hence, predict that Hspr is not properly learnable. We refute this prediction. Fix ε, δ ∈ (0, 1), select N = N (ε, δ) so that 1/N ≲ εδ, and for a sample S+ of size n, let o (S+ ) be the number of copies of 1 in S+ . Consider the proper randomized learner3 if some i ≥ 3 appears in S+ , {1, 2, i } √ {1} if o (S+ ) ≥ n − n , A(S+ ) = √ if o (S+ ) ≤ n , {2} {1, 2, M} otherwise, where M ∼ Unif({3, . . . , N + 2}) . The first three cases cover the regime where the sample essentially identifies the target. If the target is {1} or {2}, the sample consists only of the corresponding point and the learner outputs the target. If the target is {1, 2, i⋆ } and D+ (i⋆ ) is non-negligible, then i⋆ is observed once n is large enough and case 1 again outputs the target. Finally, if one of {1, 2} has tiny mass under D+ , the corresponding singleton case fires; dropping that low-mass point creates only small false-negative error. The interesting regime is when the target is ℓ = {1, 2, i⋆ } with D+ (i⋆ ) much smaller than 1/n, so that i⋆ is not observed with high probability. In this regime, the sample contains only 1s and √ 2s (each having more than n copies): from this, the learner can infer that the target has the form {1, 2, i } but has no information about the value of i. Here, the closure {1, 2} is the natural “safe” choice which ensures zero false positive errors (and is exactly what Natarajan [Nat87]’s strategy would output), but it is improper. Our learner replaces this improper closure by a random proper extension {1, 2, M }, where M is uniformly chosen from a large set of values. The extension correctly covers 1 and 2, and the only point that could be misclassified as positive is the random choice M. For any fixed k ∈ / ℓ, the chance the learner outputs {1, 2, k} is at most 1/N, so the expected false-positive mass is E M [D (A(S+ ) \ ℓ)] = ∑k∈/ ℓ Pr [ M = k ] · D(k ) ≤
1 D(k) ≲ εδ . N ∑k∈/ ℓ
Markov’s inequality then upgrades this to a high-probability guarantee. To conclude, the key insight is to randomize over proper supersets of the closure {1, 2} so that no exterior point receives large probability mass; this gives a proper positive-only learner for a finite-VC class that is not intersection-closed, refuting Natarajan’s conjecture. Is Randomization Necessary for the Refutation? At first glance, randomization seems essential here: to remain proper, the learner had to commit to some proper extension {1, 2, k } in place of the improper closure {1, 2}, and randomizing over k seems like the only way to avoid placing large probability on any specific exterior point. Surprisingly, the external coin flips are not needed—for 3 This learner can be simplified by, e.g., removing some cases; we discuss this learner as we can readily derandomize it.
10
any fixed distribution D , a deterministic learner can extract sufficient randomness from the sample itself. Concretely, we construct a deterministic variant of the above algorithm in which the last case outputs {1, 2, o (S+ )}, using the count of 1s in the sample in place of the external M. When both 1 and 2 have non-negligible mass under D+ , o (S+ ) is sufficiently anti-concentrated that no fixed exterior k is output with large probability—the same role that the atom bound Pr [ M = k ] ≤ 1/N played above. We give the formal argument in Section D.3. This ability to de-randomize the learner is, however, a feature of Hspr : in general, Theorem 6 exhibits classes that are learnable by a randomized proper positive-only learner but by no deterministic one. Characterization of Proper Positive-Only Learning. We now turn to our main characterization. We prove that H is properly learnable from positive-only samples if and only if VCdim(H) < ∞ and H satisfies uniform exterior separability, or UES (Definition 3). Roughly speaking, UES is the structural property of H that lets the randomized strategy used for Hspr above be carried out uniformly across all realizable samples. Recall that for a finite realizable set S ⊆ X , HS = { h ∈ H : S ⊆ h} denotes the set of hypotheses in H that contain S, and T the closure CLOSH (S) = h∈HS h consists of the points forced to be positive by S. UES asks that for every accuracy level η, there is a list of proper hypotheses hS,1 , . . . , hS,M(η ) ∈ HS , of size M(η ) depending only on η (not on S), such that no exterior point x ∈ / CLOSH (S) is included in more than an η-fraction of the list. Equivalently, choosing a hypothesis uniformly from this list places probability at most η on any fixed exterior point. This is precisely the property exploited for the class Hspr above: although the closure CLOSH (S) may itself be improper, UES lets us simulate it by randomizing over proper hypotheses with sufficiently spread-out false positives. Sufficiency. The sufficiency direction is conceptually straightforward and is easiest to prove using the weaker distributional condition DES (Definition 4), which is implied by UES via the uniform distribution over the UES list. (DES is weaker because it permits an arbitrary distribution over HS rather than only ones supported on lists of bounded size.) Given a positive sample S+ , let S = Domain(S+ ), choose η ≍ εδ, and output h ∼ µS,η , where µS,η is the DES distribution supported on HS . The output is proper by construction and consistent with S+ since µS,η is supported on HS . We divide the error into two parts: • False negatives. Since VCdim(H) < ∞, a standard uniform-convergence argument under D+ ensures that, for |S+ | large enough, every h ∈ HS satisfies D(ℓ \ h) ≤ ε/2 with high probability. • False positives. Since CLOSH (S) ⊆ ℓ, every negative point x ∈ / ℓ is exterior, and DES gives Prh∼µS,η ( x ∈ h) ≤ η. Averaging over x ∼ D shows that the expected false-positive mass is at most η, and Markov’s inequality converts this into a high-probability bound as before. Taking η on the order of εδ and union-bounding these two events yields the desired guarantee. Necessity. The necessity direction proceeds in two steps: we first show that finite VC dimension is necessary, and then we show that UES is necessary. The first step is inherited from standard PAC learning; the second is the key part of the necessity direction. Necessity of finite VC dimension. The necessity of finite VC dimension is not specific to positive-only learning. Indeed, if H were properly learnable from positive-only samples, then it would also be learnable in the usual PAC model with both positive and negative examples and an improper 11
learner: if the target has very small D -mass, the learner may simply output ∅, and otherwise a labeled sample contains enough positive examples to simulate the positive-only learner. The necessity follows as ordinary PAC learnability requires VCdim(H) < ∞ [SB14]. Necessity of UES. The main difficulty is proving the necessity of UES, which we do in two stages. We first show that (the weaker requirement of) DES is necessary. Then, we use the fact that VCdim(H) < ∞ to strengthen this necessity proof to UES. Step 1 (DES is necessary): Fix a finite realizable set S ⊆ X and a parameter η > 0. Suppose A is a positive-only learner with sample complexity n = mH (ε, δ) for ε ≪ 1/ |S| and δ = η/2. Run A on a sample S+ ∼ USn , where US is the uniform distribution over S, and let ν denote the resulting distribution over outputs. We claim that ν is essentially the desired DES witness. We construct a single hard-instance: Fix any x ∈ / CLOSH (S). By definition of the closure, there is some ℓ x ∈ HS with x ∈ / ℓ x . Consider the data distribution D x that places half its mass on x and the remaining half uniformly on S. Under target ℓ x , the positive conditional distribution is exactly US , so A sees precisely the sample distribution used to define ν. If A outputs a hypothesis containing x, then x is a false positive of mass 1/2, violating the PAC guarantee. Hence ν ({ h : x ∈ h}) ≤ δ, which is exactly the DES bound at x. We can apply this for each x ∈ / CLOSH (S). However, there is one caveat: DES requires a distribution supported on HS , while ν may put mass outside HS (since, e.g., A may not be an ERM). We can modify our argument to handle this: if A outputs some h ∈ / HS , then h misses at least one s ∈ S, creating false-negative error at least 1/2|S| > ε under D x , so ν(H \ HS ) ≤ δ. Reassigning this excess mass to an arbitrary fixed hS ∈ HS yields a distribution µ supported on HS with Prh∼µ ( x ∈ h) ≤ 2δ = η for every exterior x, proving DES. Step 2 (From DES to UES): Upgrading DES to UES is the most technical step of the characterization. Fix S and let µ be the DES distribution over HS , with every exterior point having marginal at most η/2. For each exterior point x, define the range RSx = { h ∈ HS : x ∈ h} ⊆ HS ; DES requires exactly that each such range has µ-mass at most η/2. The key observation is that the family RSx : x ∈ / CLOSH (S) is a sub-family of the dual class H⋆ , and finite primal VC dimension implies finite dual VC dimension d⋆ = VCdim(H⋆ ). We can therefore apply a uniform-convergence argument to this dual class: sampling M(η ) = O(d⋆ log (1/η ) /η ) hypotheses from µ ensures, with positive probability, that every range of µ-mass at most η/2 is hit by at most an η-fraction of the sample. Any such realization yields hypotheses hS,1 , . . . , hS,M(η ) ∈ HS satisfying the UES guarantee, and crucially M (η ) depends only on η and d⋆ , not on S. Combining the necessity of DES with this DES-to-UES upgrade completes the proof of the characterization. The role of the dual class here is, in our view, a non-trivial and surprising element of the proof. To our knowledge, this kind of discretization argument has previously surfaced only in the study of sample compression schemes [MY16], a setting that bears no obvious connection to positive-only learning. Yet it is exactly the tool needed to convert the distributional condition DES into the combinatorial condition UES – a connection that, in our view, is far from obvious a priori.
6
Conclusion and Future Work
The problem of PAC learning from positive-only examples has been studied in many forms, dating back to Valiant [Val84b]. While positive-only learning with improper learners is well understood
12
and is even a textbook exercise, our understanding of proper learning from positive-only examples is much less well developed. Indeed, even a characterization of learnability was not known. In this work, we revisit and settle this problem by providing a characterization of concept classes that are properly learnable from positive-only examples (Theorem 4). Surprisingly, this characterization (along with additional analysis) shows that the landscape of proper positive-only learning is surprisingly rich and, in several concrete ways, quite different from the landscape of the usual PAC learning model (Theorems 6, 7, 8 and 14). These results were unexpected in the sense that Natarajan [Nat87], who studied a much more stringent variant of positive-only learning (where the learner is not allowed to make any false positives), conjectured that imposing this requirement of “no false positives” has no impact on learnability. We refute this conjecture using our characterization (Theorem 15; also see Section 1.1). Our work leaves several directions for proper positive-only learning. First, while we characterize learnability, the exact random-bit complexity remains open. Second, the characterization suggests analogous results for non-uniform learnability and consistency. Third, after identifying which classes are learnable from positive-only examples, it is natural to ask for optimal statistical rates and efficient algorithms.
13
References Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. URL: https://theory.cs.princeton.edu/complexity/book.pdf (cit. on p. 7). [AGR13] Joseph Anderson, Navin Goyal, and Luis Rademacher. “Efficient Learning of Simplices”. In: Proceedings of the 26th Annual Conference on Learning Theory (COLT). Vol. 30. Proceedings of Machine Learning Research. PMLR, 2013, pp. 1020–1045 (cit. on pp. 2, 4). [AL88] Dana Angluin and Philip Laird. “Learning from noisy examples”. In: Machine learning 2.4 (1988), pp. 343–370 (cit. on p. 4). [Ang79] 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. 4). [Ang88] Dana Angluin. Identifying Languages From Stochastic Examples. Yale University. Department of Computer Science, 1988. URL: http://www.cs.yale.edu/publications/techreports/ tr614.pdf (cit. on p. 4). [Ass83] Patrick Assouad. “Densité et dimension”. In: Annales de l’Institut Fourier 33.3 (1983), pp. 233– 282. URL: https://www.numdam.org/articles/10.5802/aif.938/ (cit. on pp. 8, 18, 25). [BBL05] 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. 21). [BD18] Jessa Bekker and Jesse Davis. “Estimating the class prior in positive and unlabeled data through decision tree induction”. In: Proceedings of the AAAI conference on artificial intelligence. Vol. 32. 1. 2018 (cit. on p. 4). [BEHW89] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. “Learnability and the Vapnik–Chervonenkis Dimension”. In: Journal of the ACM 36.4 (1989), pp. 929–965 (cit. on pp. 8, 23, 28). [BHMv+21] Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, and Amir Yehudayoff. “A Theory of Universal Learning”. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. STOC 2021. Association for Computing Machinery, 2021, pp. 532–541. URL : https://doi.org/10.1145/3406325.3451087 (cit. on pp. 4, 8). Olivier Bousquet, Steve Hanneke, Shay Moran, and Nikita Zhivotovskiy. “Proper learning, [BHMZ20] Helly number, and an optimal SVM bound”. In: Conference on Learning Theory. PMLR. 2020, pp. 582–609 (cit. on pp. 3, 9). [BI88] Gyora M Benedek and Alon Itai. “Nonuniform learnability”. In: International Colloquium on Automata, Languages, and Programming. Springer. 1988, pp. 82–92 (cit. on p. 8). [BJ93] Shai Ben-David and Michal Jacovi. “On learning in the limit and non-uniform (ε, δ)-learning”. In: Proceedings of the sixth annual conference on Computational learning theory. 1993, pp. 209–217 (cit. on p. 8). [BLS10] Gilles Blanchard, Gyemin Lee, and Clayton Scott. “Semi-supervised novelty detection”. In: The Journal of Machine Learning Research 11 (2010), pp. 2973–3009 (cit. on p. 4). [CCHM+24] 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. 18). [CDS20] 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). SIAM, 2020, pp. 82–101 (cit. on pp. 2, 4). [AB09]
14
[CMY23]
[DDS15]
[Den98] [DNS15]
[EHKV89]
[EN08]
[FHMM23]
[FJK96]
[FLLD+22]
[FLLH+24]
[Ger89] [Gol67] [Han16a]
[Han16b]
[Han24]
[Hau90]
Zachary Chase, Shay Moran, and Amir Yehudayoff. “Stability and Replicability in Learning”. In: 64th IEEE Annual Symposium on Foundations of Computer Science. IEEE, 2023, pp. 2430–2439. URL : https://doi.org/10.1109/FOCS57990.2023.00148 (cit. on p. 7). 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 (cit. on pp. 2, 4). François Denis. “PAC learning from positive statistical queries”. In: International conference on algorithmic learning theory. Springer. 1998, pp. 112–126 (cit. on p. 4). Marthinus Du Plessis, Gang Niu, and Masashi Sugiyama. “Convex formulation for learning from positive and unlabeled data”. In: International conference on machine learning. PMLR. 2015, pp. 1386–1394 (cit. on p. 4). Andrzej Ehrenfeucht, David Haussler, Michael Kearns, and Leslie Valiant. “A general lower bound on the number of examples needed for learning”. In: Information and Computation 82.3 (1989), pp. 247–261 (cit. on p. 8). 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. 2008, pp. 213–220 (cit. on pp. 1, 4). Yuval Filmus, Steve Hanneke, Idan Mehalel, and Shay Moran. “Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension”. In: Proceedings of Thirty Sixth Conference on Learning Theory. Vol. 195. Proceedings of Machine Learning Research. PMLR, 2023, pp. 773–836. URL: https://proceedings.mlr.press/v195/filmus23a.html (cit. on p. 7). Alan Frieze, Mark Jerrum, and Ravi Kannan. “Learning Linear Transformations”. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS). 1996, pp. 359–368 (cit. on pp. 2, 4). Zhen Fang, Yixuan Li, Jie Lu, Jiahua Dong, Bo Han, and Feng Liu. “Is Out-of-Distribution Detection Learnable?” In: Advances in Neural Information Processing Systems. Vol. 35. Curran Associates, Inc., 2022, pp. 37199–37213. URL: https://proceedings.neurips.cc/paper_ files/paper/2022/file/f0e91b1314fa5eabf1d7ef6d1561ecec- Paper- Conference.pdf (cit. on p. 4). Zhen Fang, Yixuan Li, Feng Liu, Bo Han, and Jie Lu. “On the Learnability of Out-of-distribution Detection”. In: Journal of Machine Learning Research 25.84 (2024), pp. 1–83. URL: http://jmlr. org/papers/v25/23-1257.html (cit. on p. 4). Mihaly Gereb-Graus. “Lower Bounds on Parallel, Distributed and Automata Computations”. AAI9013212. PhD thesis. 1989 (cit. on pp. 2, 6). E Mark Gold. “Language identification in the limit”. In: Information and control 10.5 (1967), pp. 447–474 (cit. on p. 4). Steve Hanneke. “The Optimal Sample Complexity of PAC Learning”. In: Journal of Machine Learning Research 17.38 (2016), pp. 1–15. URL: https://jmlr.org/papers/v17/15-389.html (cit. on p. 2). Steve Hanneke. “Refined Error Bounds for Several Learning Algorithms”. In: Journal of Machine Learning Research 17.135 (2016), pp. 1–55. URL: https://jmlr.org/papers/v17/15655.html (cit. on p. 2). Steve Hanneke. “The star number and eluder dimension: Elementary observations about the dimensions of disagreement”. In: The Thirty Seventh Annual Conference on Learning Theory. PMLR. 2024, pp. 2308–2359 (cit. on p. 2). David Haussler. “Probably Approximately Correct Learning”. In: Proceedings of the Eighth National Conference on Artificial Intelligence - Volume 2. AAAI’90. AAAI Press, 1990, pp. 1101– 1108 (cit. on p. 2).
15
[HM25]
[HP26]
[Kiv95] [KKV23]
[KMKC26]
[KMV25]
[KTZ19]
[KV94]
[Lar23]
[LDLL+03]
[LLYL02] [LMZ24a]
[LMZ24b]
[LMZ26]
[Lu24]
Max Hopkins and Shay Moran. “The Role of Randomness in Stability”. In: Proceedings of the 42nd International Conference on Machine Learning. Vol. 267. Proceedings of Machine Learning Research. PMLR, 2025, pp. 23805–23827. URL: https://proceedings.mlr.press/v267/ hopkins25a.html (cit. on p. 7). Mikael Møller Høgsgaard and Chirag Pabbaraju. Agnostic Language Identification and Generation. 2026. arXiv: 2601.23258 [cs.LG]. URL: https://arxiv.org/abs/2601.23258 (cit. on p. 4). Jyrki Kivinen. “Learning reliably and with one-sided error”. In: Mathematical systems theory 28.2 (1995), pp. 141–172 (cit. on pp. 2, 3). Pravesh K. Kothari, Adam R. Klivans, and Aravindan Vijayaraghavan. “Efficient Algorithms for Outlier-Robust Regression”. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC). Association for Computing Machinery, 2023, pp. 1643–1656 (cit. on p. 4). Alexandros Kouridakis, Anay Mehrotra, Alkis Kalavasis, and Constantine Caramanis. Linear Regression with Unknown Truncation Beyond Gaussian Features. 2026. arXiv: 2602.12534 [stat.ML]. URL: https://arxiv.org/abs/2602.12534 (cit. on p. 4). 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 (STOC’25). Association for Computing Machinery, 2025. URL: https://arxiv.org/abs/2411.09642 (cit. on p. 4). 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 (cit. on pp. 2, 4). Michael J. Kearns and Umesh V. Vazirani. An Introduction to Computational Learning Theory. The MIT Press, 1994, p. 222. URL: https://doi.org/10.7551/mitpress/3897.001.0001 (cit. on pp. 1, 2, 6). Kasper Green Larsen. “Bagging is an Optimal PAC Learner”. In: Proceedings of the 36th Conference on Learning Theory. Vol. 195. Proceedings of Machine Learning Research. PMLR, 2023, pp. 450–468. URL: https://proceedings.mlr.press/v195/larsen23a.html (cit. on p. 2). Bing Liu, Yang Dai, Xiaoli Li, Wee Sun Lee, and Philip S Yu. “Building text classifiers using positive and unlabeled examples”. In: Third IEEE international conference on data mining. IEEE. 2003, pp. 179–186 (cit. on p. 1). Bing Liu, Wee Sun Lee, Philip S Yu, and Xiaoli Li. “Partially supervised classification of text documents”. In: ICML. Vol. 2. 485. Sydney, NSW. 2002, pp. 387–394 (cit. on p. 4). 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). IEEE. 2024, pp. 988–1006 (cit. on p. 4). Kasper Green Larsen, Omar Montasser, and Nikita Zhivotovskiy. “Derandomizing MultiDistribution Learning”. In: Advances in Neural Information Processing Systems. Vol. 37. Curran Associates, Inc., 2024, pp. 94246–94264. URL: https://proceedings.neurips.cc/paper_ files / paper / 2024 / hash / ab63d1eb181e920273504411fe0942dc - Abstract - Conference . html (cit. on p. 7). 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. STOC ’26. To appear. Association for Computing Machinery, 2026. URL: https: //arxiv.org/pdf/2504.10428 (cit. on pp. 2, 4, 6, 37). Zhou Lu. “When is inductive inference possible?” In: Advances in Neural Information Processing Systems 37 (2024), pp. 92721–92744 (cit. on p. 8).
16
[Maa91]
[MB25]
[Meh26] [MY16] [Nat87]
[NR09] [OS18]
[RG09] [SB14] [Shv90] [SS97]
[Sto77] [Ush86] [Val84a] [Val84b]
Wolfgang Maass. “On-Line Learning with an Oblivious Environment and the Power of Randomization”. In: Proceedings of the Fourth Annual Workshop on Computational Learning Theory. Morgan Kaufmann, 1991, pp. 167–175. URL: http://dl.acm.org/citation.cfm?id=114852 (cit. on p. 7). Farnam Mansouri and Shai Ben-David. “Learning from Positive and Unlabeled Examples -Finite Size Sample Bounds”. In: Advances in Neural Information Processing Systems. 2025. URL: https://openreview.net/forum?id=bK3s3n0vPA (cit. on pp. 2, 4). Anay Mehrotra. “Learning Theory in the Wild: Foundations of Missing Data and Language Generation”. Ph.D. dissertation. Yale University, May 2026 (cit. on p. 2). 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. 7, 12, 21). Balaubramaniam Kausik Natarajan. “On learning boolean functions”. In: Proceedings of the nineteenth annual ACM symposium on Theory of computing. 1987, pp. 296–304 (cit. on pp. 1–3, 7, 9, 10, 13, 18, 20, 21). 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. 2, 4). Igor Carboni Oliveira and Rahul Santhanam. “Pseudo-Derandomizing Learning and Approximation”. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Vol. 116. Leibniz International Proceedings in Informatics. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018, 55:1–55:19. URL: https://drops.dagstuhl.de/ entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.55 (cit. on p. 7). Luis Rademacher and Navin Goyal. “Learning Convex Bodies is Hard”. In: Proceedings of the 22nd Annual Conference on Learning Theory (COLT). 2009 (cit. on p. 4). Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014 (cit. on pp. 7, 12, 23, 28). Haim Shvaytser. “A Necessary Condition for Learning from Positive Examples”. In: Machine Learning 5.1 (1990), pp. 101–113 (cit. on pp. 2, 3). Meera Sitharam and Timothy Straney. “Derandomized Learning of Boolean Functions”. In: Algorithmic Learning Theory. Vol. 1316. Lecture Notes in Computer Science. Springer, 1997, pp. 100–115. URL: https://doi.org/10.1007/3-540-63577-7_38 (cit. on p. 7). Charles J. Stone. “Consistent Nonparametric Regression”. In: The Annals of Statistics 5.4 (1977), pp. 595–620 (cit. on p. 8). Nikolai G Ushakov. “Upper estimates of maximum probability for sums of independent random vectors”. In: Theory of Probability & Its Applications 30.1 (1986), pp. 38–49 (cit. on p. 30). 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 p. 1). Leslie G. 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 pp. 1, 12).
17
A
Additional Preliminaries
In this section, we introduce additional notation and definitions that were omitted from the main body of the paper due to space constraints. Notations. For a multi-set S, define its domain as the set of distinct elements appearing in S, denoted by Domain(S) := { x : x ∈ S}. Furthermore, for a family {(D a , ℓ a ) | a ∈ A}, denote the conditional distributions by D+,a := (D a )+ and D−,a := (D a )− . Also, for any finite set A, denote by U A the uniform distribution over A. VC dimension and dual VC. For a concept class H, and a finite subset of the domain S ⊆ X , we say that S is shattered by H if for every F ⊆ S there exists a concept h ∈ H such that h ∩ S = F. The VC dimension of H, denoted by VCdim(H), is defined by the largest d ∈ N ∪ 0 such that there exists a finite set of instances S ⊆ X of size d that is shattered by H. If no such largest d exists, we say VCdim(H) = ∞. The dual class of H is the concept class H⋆ defined below over the domain H
H⋆ := { R x : x ∈ X }
where
R x := { h ∈ H : x ∈ h} .
Its VC dimension, VCdim (H⋆ ) , is called the dual VC dimension of H. By a classical theorem of Assouad [Ass83], if VCdim (H) < ∞, then the dual VC dimension is also finite. In fact, the following quantitative bound holds; see also the discussion in [CCHM+24]. Theorem 10 ([Ass83]). For any concept class H, VCdim (H⋆ ) < 2VCdim(H)+1 . Non-uniform learning, and consistency. We also consider two weaker notions of proper positiveonly learnability. The first is a non-uniform notion, in which the required sample size is allowed to depend on the target concept. The second is consistency, which requires the expected error to vanish in the limit. We say that a concept class H is non-uniformly properly positive-only learnable by a proper learner A if there exists a function mH : (0, 1) × (0, 1) × H 7→ N such that for every distribution D over X , ℓ ∈ H, ε, δ ∈ (0, 1), and n ≥ mH (ε, δ, ℓ), the following is satisfied Pr (errD (A (S+ ) , ℓ) ≤ ε) ≥ 1 − δ .
n S+ ∼D+
We say that H is properly positive-only consistent, if there exists a proper positive-only learner A such that for every distribution D over X and ℓ ∈ H, lim ES+ ∼D+n [errD (A (S+ ) , ℓ)] = 0 .
n→∞
B
Relationships Between Conditions
In this section, we prove the relationships between the exterior-separation conditions introduced in Section 3 and a new notion we call finite exterior separability. We first establish the general hierarchy between exact, uniform, distributional, and finite exterior separability. We then use this hierarchy to prove separations between proper and improper positive-only learning, and between proper positive-only learning and the one-sided-error model of Natarajan [Nat87]. Finally, we show that, under finite VC dimension, distributional exterior separability can be strengthened to uniform exterior separability. 18
B.1
General Hierarchy of Relationships: Extension of Proposition 2
In this section, we prove a slightly stronger version of Proposition 2, which includes finite exterior separability (defined below) as the weakest condition in the hierarchy. Definition 6 (Finite Exterior Separability). We say that H satisfies finite exterior separability if for every finite nonempty realizable set S ⊆ X and every finite set F ⊆ X \ CLOSH (S), there exists h ∈ HS such that h ∩ F = ∅. Proposition 11 (Exterior-separation hierarchy). For every concept class H, exact exterior separation =⇒ uniform exterior separability
=⇒ distributional exterior separability =⇒ finite exterior separability . Moreover, the first and third implications are strict. Proof. If H satisfies exact exterior separation, then for every finite nonempty realizable S we may take the single hypothesis hS,1 = CLOSH (S); this proves uniform exterior separability with M (η ) = 1 for every η > 0. If H satisfies uniform exterior separability, fix η > 0 and write M := M(η ) for the bound from Definition 3. For each finite nonempty realizable S, let µS,η be the uniform distribution on the corresponding family hS,1 , . . . , hS,M . Then for every x ∈ / CLOSH (S), Pr ( x ∈ h) =
h∼µS,η
1 |{i : x ∈ hS,i }| ≤ η , M
so distributional exterior separability holds. Finally, assume distributional exterior separability, fix a finite nonempty realizable S, and let F ⊆ X \ CLOSH (S) be finite. Choose η < 1/ | F | and let µS,η witness Definition 4. Then Eh∼µS,η [|h ∩ F |] = ∑ Pr ( x ∈ h) ≤ | F | η < 1 . x ∈ F h∼µS,η
Hence some h ∈ HS satisfies |h ∩ F | = 0, proving finite exterior separability. It remains to prove the strictness of the first and third implications. We divide this into the two propositions below. Proposition 12. There is a concept class H which satisfies uniform exterior separability (Definition 3) but does not satisfy exact exterior separation (Definition 2). Proof. Consider the class
Hspr := {{1} , {2}} ∪ {{1, 2, i } : i ≥ 3} on the domain N. It is not exact exterior separating, since for S = {1, 2} we have CLOSHspr (S) = / Hspr . {1, 2} ∈ We claim that Hspr nevertheless satisfies uniform exterior separability. Fix η > 0 and let M := ⌈1/η ⌉. If S = {1, 2}, choose hS,j := {1, 2, 2 + j} , 19
j = 1, . . . , M .
Every point outside CLOSHspr (S) = {1, 2} belongs to at most one of these M hypotheses, so its average frequency is at most 1/M ≤ η. For every other finite nonempty realizable S, the closure already belongs to the class: for instance, CLOSHspr ({1}) = {1}, CLOSHspr ({2}) = {2}, and if S contains some i ≥ 3 together with either 1 or 2, then HS is a singleton and its unique element is the closure. In all such cases we simply repeat CLOSHspr (S) exactly M times. Thus Hspr satisfies uniform exterior separability. Proposition 13. There is a concept class H which satisfies finite exterior separability (Definition 6) but does not satisfy distributional exterior separability (Definition 4). Proof. Consider the class
Htail := {h a : a ≥ 3} ,
h a := {1, 2} ∪ {m ∈ N : m ≥ a} .
where
We first check finite exterior separability. Let S ⊆ N be finite, nonempty, and realizable. If S contains some point m ≥ 3, then with a0 := min (S ∩ {3, 4, . . . }) we have CLOSHtail (S) = h a0 ∈ Htail , so the property is immediate. If S ⊆ {1, 2}, then CLOSHtail (S) = {1, 2}, and given any finite set F ⊆ N \ {1, 2}, choosing a > max F yields h a ∈ HS with h a ∩ F = ∅. Thus Htail satisfies finite exterior separability. We now show that distributional exterior separability fails. Fix S = {1, 2} and let µ be any probability distribution on HS = Htail . For each N ≥ 3, N
Pr ( N ∈ h) = ∑ µ(h a ) .
h∼µ
a =3
As N → ∞, the right-hand side increases to 1. Hence sup
Pr ( N ∈ h) = 1 ,
N∈ /CLOSHtail (S) h∼µ
so no distribution on HS can make the exterior marginals arbitrarily small. Therefore Htail does not satisfy distributional exterior separability.
B.2
Strict Separation between Proper Positive-Only Learning and Other Models
In this section, we use the hierarchy from the previous subsection to prove two strict separations: first, between proper and improper positive-only learning, and second, between proper positiveonly learning and the proper one-sided-error model introduced by Natarajan [Nat87]. Theorem 14. There exists a concept class that is improperly positive-only learnable, but not properly positive-only learnable.
20
Proof. Let X = {0, 1, 2} and H = {{0, 1}, {0, 2}}. Then H∩ := {{0}, {0, 1}, {0, 2}}. Note that VCdim(H∩ ) = 1. Therefore, by Theorem 1, H is improperly positive-only learnable. However, let S = {0} and F = {1, 2}. Note that F ∩ CLOSH (S) = F ∩ S = ∅, but there is no h ∈ H such that S ⊆ h and h ∩ F = ∅. Thus, H does not satisfy finite exterior separability (Definition 6), and, by Proposition 11, it does not satisfy uniform exterior separability either (Definition 3). In Theorem 4, we showed that any class that does not satisfy uniform exterior separability is not properly positive-only learnable. Theorem 15. There exists a concept class H that is properly learnable from positive-only examples, but it is not properly learnable with one-sided error (the model proposed by [Nat87]). Proof of Theorem 15. In Proposition 12, we introduced a concept class Hspr with VCdim(Hspr ) = 1 that satisfies uniform exterior separability (Definition 3), but does not satisfy exact exterior separation (Definition 2). From Theorem 4, this implies that Hspr is properly learnable from positive-only examples. However, Natarajan [Nat87] shows that exact exterior separation is necessary for properly learning with one-sided error.
B.3
Proof of Theorem 3
In this section, we prove Theorem 3. The main idea is that finite dual VC dimension lets us discretize any distribution witnessing distributional exterior separability into a uniform distribution over finitely many hypotheses, while preserving the exterior-marginal bounds up to constant factors. Theorem 3 (From distributional to uniform exterior separability). Suppose that VCdim (H) < ∞. If H satisfies distributional exterior separability, then H satisfies uniform exterior separability. We also show that if d⋆ := VCdim (H⋆ ), then, in Definition 3, for any η ∈ (0, 1), one may take ⋆ d log(1/η ) M(η ) = O . η We will use the following corollary of standard second-order uniform convergence, which has in the past been used in establishing the existence of sample-compression schemes [MY16]. Corollary 16 (Corollary of second-order uniform convergence for finite-VC classes; cf. [BBL05]). For every concept class H over a domain Ω with VCdim(H) ≤ d < ∞, every probability distribution ν on Ω, and each ε ∈ (0, 1), there is a multiset z1 , . . . , z M ∈ Ω, with M = O(d (log 1/ε)/ε) , such that every A ∈ H satisfies if
ν( A) ≤
ε 2
then
1 |{i ∈ {1, . . . , M} : zi ∈ A}| ≤ ε . M
Proof of Corollary 16. This is an immediate implication of the following (standard) second-order uniform convergence result; cf. Section 5.1.2 in [BBL05].
21
Theorem 17. There exists a universal constant C > 0 such that for every concept class H over a domain Ω with VCdim(H) ≤ d < ∞ the following holds. For every ε, δ ∈ (0, 1), if Z1 , . . . , Zm ∼ ν are i.i.d. and m ≥ C (d log 1/ε + log 1/δ) /ε, then with probability at least 1 − δ, every A ∈ H satisfies q ν( A△ A⋆ ) ≤ νbm ( A△ A⋆ ) + νbm ( A△ A⋆ ) ε + ε , q νbm ( A△ A⋆ ) ≤ ν( A△ A⋆ ) + ν( A△ A⋆ ) ε + ε , where νbm (·) is the empirical distribution: νbm ( B) := m1 |{i ∈ {1, . . . , m} : Zi ∈ B}| for each B ⊆ Ω. Indeed, let γ := ε/16. Apply the standard second-order uniform-convergence theorem with reference set A⋆ = ∅ and confidence parameter δ = 1/2. Then for d log 1/γ d log 1/ε =O , m=O γ ε there exists a realization z1 , . . . , zm ∈ Ω such that every A ∈ H satisfies q 1 |{i ∈ {1, . . . , m} : zi ∈ A}| ≤ ν ( A) + ν ( A) γ + γ . m If now ν ( A) ≤ ε/2, then 1 ε |{i ∈ {1, . . . , m} : zi ∈ A}| ≤ + m 2
r
ε ε ε · + ≤ ε. 2 16 16
Setting M := m proves the claim. Now we are ready to prove Theorem 3. Proof of Theorem 3. Recall that d⋆ is finite by the duality theorem (Theorem 10). Fix 0 < η < 1 and a finite nonempty realizable set S ⊆ X . By distributional exterior separability (Definition 4), applied with parameter η/2, there exists a probability distribution µ supported on HS such that sup
Pr ( x ∈ h) ≤
x∈ /CLOSH(S) h∼µ
η . 2
For each exterior point x ∈ / CLOSH (S), define RSx := { h ∈ HS : x ∈ h} , and let
n o RS := RSx : x ∈ / CLOSH (S) .
Observe that RS is obtained from H⋆ by restricting the domain from H to HS and then discarding the concepts only containing non-exterior points. Therefore, it follows that VCdim (RS ) ≤ VCdim (H⋆ ) = d⋆ . Since every set in RS has µ-measure at most η/2, this is exactly the regime in which the secondorder form of uniform convergence is useful. We use Corollary 16 to the concept class RS over the domain HS , under the probability measure µ. Since VCdim (RS ) ≤ d⋆ , this yields a multiset ⋆ d log 1/η hS,1 , . . . , hS,M(η ) ∈ HS with M(η ) = O η 22
such that every R ∈ RS with µ ( R) ≤ η/2 satisfies 1 |{i ∈ {1, . . . , M(η )} : hS,i ∈ R}| ≤ η . M(η ) η Now fix any x ∈ / CLOSH (S). Since RSx ∈ RS and µ RSx = Prh∼µ ( x ∈ h) ≤ 2 , the above implies n o 1 1 i : hS,i ∈ RSx ≤ η . |{i ∈ {1, . . . , M(η )} : x ∈ hS,i }| = M(η ) M(η ) Since x was arbitrary, the family hS,1 , . . . , hS,M(η ) witnesses UES at level η. As the bound on M(η ) depends only on η and d⋆ , this proves UES (Definition 3).
C
Proof of Main Results
In this appendix, we prove Theorems 4, 5 and 6 from Section 4.
C.1
Proof of Theorem 4
In this section, we prove Theorem 4, which we restate below. Theorem 4 (Main characterization). The following are equivalent: 1. H is properly learnable from positive-only samples; 2. H satisfies uniform exterior-separability (Definition 3) and VCdim (H) < ∞. Proof. Observe that in Theorem 3 we have proved that under the assumption VCdim(H) < ∞, uniform exterior separability is equivalent to distributional exterior separability (Definition 4). We divide the proof into two parts, one for each direction of the claim. Part 1 (2 =⇒ 1): Define the learner A for any multi-set S+ ∈ X [∗] as
A(S+ ) ∼ µS+ ,exp(−|S+ |) . n , for n ∈ N, and write Fix ε, δ ∈ (0, 1), a distribution D over X and ℓ ∈ H. Let S+ ∼ D+ d := VCdim (H). By the standard realizable VC bound applied to the positive distribution D+ (see, e.g., [BEHW89; SB14]), there is a universal constant C > 0 such that if
n≥
C (d ln 1/ε + ln 1/δ) , ε
then with probability at least 1 − δ/2 every h ∈ H such that Domain(S+ ) ⊆ h satisfies
D+ (ℓ \ h) ≤
ε . 2
Since D(ℓ \ h) = D(ℓ) · D+ (ℓ \ h) ≤ D+ (ℓ \ h), the same event implies D(ℓ \ h) ≤ ε/2 for every such h.
23
Observe that, for every y ∈ / CLOSH (S+ ), and n ≥ ln (δε/4) EA [1 {y ∈ A(S+ )}] ≤ exp(−n) ≤
εδ . 4
Because CLOSH (S+ ) ⊆ ℓ, every negative point lies outside the closure, and therefore by the DES property (Definition 4) εδ EA [D(A(S+ ) \ ℓ)] ≤ . 4 Thus, εδ ES+ ∼D+n ,A [D(A(S+ ) \ ℓ)] ≤ . 4 Markov’s inequality gives Prn
S+ ∼D+ ,A
(D(A(S+ ) \ ℓ) > ε/2) ≤
δ . 2
Combining this with the bound on false negatives, we obtain Pr
n ,A S+ ∼D+
(errD (A(S+ ), ℓ) > ε) ≤ δ .
Part 2 (1 =⇒ 2): Fix a finite nonempty realizable set S ⊆ X and a parameter η > 0. If X \ CLOSH (S) = ∅, then any point mass on a concept in HS witnesses distributional exterior separability, so there is nothing to prove. Thus assume X \ CLOSH (S) ̸= ∅. If η ≥ 1, the conclusion is again trivial, so assume η < 1. Choose and fix one concept hS ∈ HS . For each x ∈ / CLOSH (S), choose ℓ x ∈ HS such that x ∈ / ℓ x ; this is possible by the definition of the closure. Let 1 η k := |S| , ε := , δ := , 4k 2 and let n := mH (ε, δ) be the sample complexity of a proper learner A at these parameters. Let US denote the uniform distribution on S, and let ν be the law of A (S+ ) when S+ ∼ USn . Fix any exterior point x ∈ / CLOSH (S), consider distribution D x defined as
Dx (x) =
1 2
and
D x (s) =
1 for each s ∈ S , 2k
and zero elsewhere. Also let ℓ x be any concept with x ∈ / ℓ x and S ⊆ ℓ x . Observe that since x∈ / CLOSH (S) such ℓ x always exists. Also, D+,S := US . Hence the learner sees the same sample law USn for every such x, so its output law is always ν. Now, if x ∈ A (S+ ), then x is a false positive under the target ℓ x , and therefore errDx (A (S+ ) , ℓ x ) ≥ D x ( x ) =
1 > ε. 2
By the PAC guarantee, ν({ h : x ∈ h}) =
Pr
S+ ∼USn ,A
24
( x ∈ A (S+ )) ≤ δ ,
where the probability is over S+ ∼ USn and the learner’s internal randomness. Likewise, if A ( S+ ) ∈ / HS , then it misses some point s ∈ S, and since s ∈ ℓ x and D x (s) = 1/ (2k ) > ε, this again forces errDx (A (S+ ) , ℓ x ) > ε . Hence ν(H \ HS ) = Pr (A (S+ ) ∈ / HS ) ≤ δ , where again the probability is over S+ ∼ USn and over the learner’s internal randomness. Define a probability distribution µ on HS by moving all ν-mass outside HS onto the single concept hS : µ( A) := ν( A ∩ HS ) + ν(H \ HS ) 1 { hS ∈ A} ,
A ⊆ H.
Then µ is supported on HS , and for every x ∈ / CLOSH (S), Pr ( x ∈ h) ≤ ν({ h : x ∈ h}) + ν(H \ HS ) ≤ δ + δ = η .
h∼µ
Thus µ witnesses distributional exterior separability for the pair (S, η ). Since S and η were arbitrary, H satisfies distributional exterior separability.
C.2
Proof of Theorem 5
In this section, we prove Theorem 5, which we restate below. Theorem 5 (Few random bits suffice). Consider a concept class H and its dual H⋆ . Let d = VCdim (H) and d⋆ = VCdim (H⋆ ). The following are equivalent: 1. H is properly PAC learnable from positive-only examples by a randomized learner. 2. H is properly PAC learnable from positive-only examples by a learner using at most e (log (d⋆/εδ)) random bits r (ε, δ) = O
and
e ((1/ε) (d + log 1/δ)) positive samples . m (ε, δ) = O
e (d + log (1/εδ)) . In particular, by Assouad’s bound [Ass83], d⋆ < 2d+1 , so r (ε, δ) = O Proof of Theorem 5. Observe that the second item implies the first immediately since a learner using finitely many random bits is a randomized learner. Below we prove the converse. Assume that H is properly PAC learnable from positive-only examples by a randomized learner. Then, due to Theorem 4, VCdim (H) < ∞ and H satisfies distributional exterior separability. Now, applying the quantitative version of Theorem 3 from Section B.3, implies that for every η ∈ (0, 1) and every finite nonempty realizable set S ⊆ X , there are hypotheses hS,1 , . . . , hS,M(η ) ∈ HS such that M(η ) = O(((d⋆ +1)/η ) · log 1/η ) and 1 |{i ∈ {1, . . . , M(η )} : x ∈ hS,i }| ≤ η . x∈ /CLOSH(S) M ( η ) sup
Fix ε, δ ∈ (0, 1) and set εδ , and M := M (η ) . 8 For every finite nonempty realizable set S, fix a list hS,1 , . . . , hS,M ∈ HS at scale η (as above). η :=
25
Learning Algorithm. Let K be a power of two satisfying M ≤ K < 2M. The learner uses log2 K random bits to draw a uniform seed J ∼ U{1,...,K} . It then converts this seed into an index I ( J ) := 1 + ( J − 1 mod M) ∈ {1, . . . , M} . Thus, for every i ∈ {1, . . . , M}, Pr ( I ( J ) = i ) ≤
2 . M
Given a positive multiset S+ ∈ X [∗] , let T := Domain(S+ ) be the set of distinct examples in S+ . If T is empty or is not realizable, the learner outputs an arbitrary fixed concept in H. Otherwise, the learner outputs A (S+ , J ) := h T,I ( J ) . Observe that this learner is proper, since h T,I ( J ) ∈ H, and it is consistent with the observed positives, since h T,I ( J ) ∈ HT . Upper Bound on False Negative Rate. Fix a distribution D over X and a target concept ℓ ∈ H, and n . Write d = VCdim let S+ ∼ D+ (H). By the standard realizable VC bound applied to the positive distribution D+ , if n ≳ (1/ε) · (d log 1/ε + log 1/δ), then with probability at least 1 − δ/2 over S+ , every h ∈ H consistent with S+ satisfies D+ (ℓ \ h) ≤ ε/2. Since D(ℓ \ h) = D(ℓ) D+ (ℓ \ h) ≤ D+ (ℓ \ h) , the same event implies D(ℓ \ h) ≤ ε/2 for every consistent h ∈ H. The learner’s output is always consistent with S+ . Hence, conditioned on this event, D(ℓ \ A (S+ , J )) ≤ ε/2. Upper Bound on False Positive Rate. Condition on the observed multiset S+ , and therefore on T = Domain(S+ ). Since S+ is realizable, T ⊆ ℓ, and hence CLOSH ( T ) ⊆ ℓ. Thus every negative point x ∈ / ℓ satisfies x ∈ / CLOSH ( T ) . For such an x, the index I ( J ) and the UES list satisfy 2 Pr J ( x ∈ A (S+ , J )) = Pr J x ∈ h T,I ( J ) ≤ |{i ∈ {1, . . . , M} : x ∈ hT,i }| ≤ 2η . M Therefore, E J [D(A(S+ , J ) \ ℓ)|S+ ] =
Z X \ℓ
Pr J ( x ∈ A(S+ , J )) dD( x ) ≤ 2η .
Next, by Markov’s inequality, ε 4η δ 2η Pr D(A (S+ , J ) \ ℓ) > S+ ≤ = = . J 2 ε/2 ε 2 Finally, averaging over S+ gives ε δ Pr D(A (S+ , J ) \ ℓ) > ≤ . 2 2 S+ ,J Conclusion. Thus, with probability at least 1 − δ/2 over the sample, the false-negative mass is at most ε/2. Also, with probability at least 1 − δ/2 over the sample and the learner’s random bits, the false-positive mass is at most ε/2. A union bound gives that PrS+ ,J (errD (A (S+ , J ) , ℓ) > ε) ≤ δ. Thus, the learner properly PAC learns H from positive-only examples with sample complexity d log 1/ε + log 1/δ d + log 1/δ e m (ε, δ) = O =O . ε ε It remains to bound the number of random bits. Since M = O(((d⋆ +1)/η ) · (log 1/η )) and η = εδ/8, ⋆ e log d + 2 . log2 K ≤ 1 + log2 M = O εδ e (d + log 1/εδ) . Finally, by Theorem 10, d⋆ < 2d+1 , it follows that r (ε, δ) = O
26
C.3
Proof of Theorem 6
In this section, we prove Theorem 6, which we restate below. Theorem 6 (Randomness is necessary). There exists a concept class H that is properly positive-only learnable by a randomized learner, but not by any deterministic learner. The proof proceeds through a simple obstruction to deterministic proper learning. We first introduce a property called singleton closure, and then show in Proposition 18 that every class learnable from positive examples by a deterministic proper learner must satisfy this property. The theorem then follows by constructing a class that satisfies the conditions of Theorem 4, and is therefore learnable from positive-only examples, but violates singleton closure and hence is not learnable by a deterministic learner. Definition 7 (Singleton closure). A concept class H is said to satisfy singleton closure if for each realizable point x ∈ X (equivalently, for each x with at least one h ∈ H containing x), one has CLOSH ({ x }) ∈ H . Proposition 18 (Singleton closure is necessary). If H is properly learnable from positive-only examples by a deterministic learner, then H satisfies singleton closure (Definition 7). Proof. Let A be a deterministic proper learner such that H is properly learnable from positive-only examples by A. Suppose, toward a contradiction, that CLOSH ({ x }) ∈ / H for some realizable point x, and fix any n ∈ N. Let x n denote the multi-set consisting of n copies of x, and let h = A( x n ). We consider two cases. Case 1: x ∈ / h. Let ℓ ∈ H be any concept such that x ∈ ℓ, and define D = U{ x} . Then D+ = D , and the only possible positive sample is S+ = x n . Hence errD (h, ℓ) = 1. Case 2: x ∈ h. Since h ∈ H and x ∈ h, we have CLOSH ({ x }) ⊆ h. Because CLOSH ({ x }) ∈ / H, ′ it follows that there exists x ∈ h \ CLOSH ({ x }) . By the definition of CLOSH ({ x }), there exists a concept ℓ ∈ H such that x ∈ ℓ but x ′ ∈ / ℓ. Define D = U{ x,x′ } . Then D+ = U{ x} , so again the only possible positive sample is S+ = x n . Moreover, since x ′ ∈ h \ ℓ, errD (h, ℓ) ≥ 12 . Thus, for every n, there exists a distribution D and a target concept ℓ ∈ H such that 1 Pr n errD (A(S+ ), ℓ) ≥ = 1. 2 S+ ∼D+ This contradicts the assumption that H is properly learnable from positive-only examples by A. Proof of Theorem 6. Consider concept class
H = {{1, a} | a ∈ N \ {1}} , over X = N. Notice that CLOSH ({1}) = {1} ∈ / H. Thus, H does not satisfy the singleton closure property. Therefore, it is not properly learnable from positive examples by a deterministic learner. However, VCdim(H) = 1, and similarly to the proof of Proposition 12, it is easy to see that H satisfies the uniform exterior separability property. Therefore, due to Theorem 4, it is properly learnable from positive examples.
27
D
Proof of Additional Separation Results
First, we prove the following two structural results: 1. First, we prove that exact exterior separation (Definition 2) is sufficient for deterministic proper learning of VC classes, and 2. Then, we prove necessary and sufficient conditions for consistency over countable domains. We then prove the remaining results from Section 4.
D.1
Exact Exterior Separation is Sufficient for Deterministic Learning
We begin with proving that exact exterior separability is sufficient for deterministic proper learning, which will be used throughout this appendix. Lemma 19. Every concept class H that satisfies the exact exterior separability property (def 2) and has VCdim(H) < ∞ is properly positive-only learnable. Proof. Fix any ε, δ ∈ (0, 1) and distribution D over X and ℓ ∈ H. Let the learner be defined as 1 1 n. A(S) := CLOSH (S). Let n ≥ d ln /εε+ln /δ and S+ ∼ D+ Observe that CLOSH (S+ ) is an ERM for H. Thus, we can use standard realizable PAC bounds (see, e.g., [BEHW89; SB14]), and with probability at least 1 − δ,
D (ℓ \ CLOSH (S+ )) ≤ D+ (ℓ \ CLOSH (S+ )) ≤ ε . Moreover, due to realizability Domain(S+ ) ⊆ ℓ, and, hence, CLOSH (S+ ) ⊆ ℓ. Subsequently, D(CLOSH (S+ ) \ ℓ) = 0. Therefore, with probability 1 − δ, errD (CLOSH (S+ ), ℓ) ≤ ε.
D.2
Necessary and Sufficient Conditions for Consistency
We now characterize consistency over countable domains in terms of finite exterior separability. This condition will later be used to separate PAC learnability, non-uniform learnability, and consistency. Theorem 20 (Conditions for Consistency). The following holds: 1. No concept class H which does not satisfy finite exterior separability (Definition 6) is properly positive-only consistent. 2. Every concept class H over countable domain that satisfies finite exterior separability (Definition 6) is properly positive-only consistent. Proof. We divide the proof into two parts corresponding to the two claims. Part 1 (consistency implies FES). Consider any S, F that violate finite exterior separability in Definition 6. For any x ∈ F define D x as 1 Dx (x) = , 2
∀x′ ∈ S : Dx (x′ ) = 28
1 , 2 |S|
and zero elsewhere. Also, let ℓ x be any concept containing S that does not contain x; such a concept exists since x ∈ / CLOSH (S). Since S, F violate finite exterior separability, every h ∈ H satisfies at least one of the following two conditions: either (1) x1 ∈ / h for some x1 ∈ S, or (2) x2 ∈ h for some x2 ∈ F. In case (1),
| F|
∑ errD (h, ℓx ) ≥ 2 |S| . x
x∈ F
In case (2), 1
∑ errD (h, ℓx ) ≥ errD (h, ℓx ) ≥ 2 . x
x2
x∈ F
Therefore, for either case
2
1 ∑ x∈ F errDx (h, ℓ x ) . ≥ 2 max(|S| , | F |) | F|
This implies that, for every proper positive-only learner A and every n ∈ N, ∑ x∈ F ES+ ∼USn ,A [errDx (A(S+ ), ℓ x )] 1 ≥ . 2 max(|S| , | F |) | F|
(1)
Now for the sake of contradiction, assume that H is properly positive-only consistent. Therefore, there exists a proper learner A such that for every x ∈ F, lim ES+ ∼USn ,A [errDx (A(S+ ), ℓ x )] = 0 .
n→∞
Since F is finite, this would imply ∑ x∈ F ES+ ∼USn ,A [errDx (A(S+ ), ℓ x )] = 0, n→∞ | F| lim
contradicting Equation (1). Therefore, H is not properly positive-only consistent, which completes the proof of the first part. Part 2 (FES over countable domain implies consistency). Fix an enumeration X = { x1 , x2 , . . . } and write Xm = { x1 , . . . , xm }. Define the learner A as follows. Given a realizable sample S+ , choose A(S+ ) ∈ HDomain(S+ ) such that A(S+ ) ∩ X|S+ | \ CLOSH (S+ ) = ∅. Such a concept exists by finite exterior separability, applied to S = Domain(S+ ) and F = X|S+ | \ CLOSH (S+ ). Consider any distribution D over X and any ℓ ∈ H. Since X is countable, there exists nD (ε) ∈ N such that ε D X \ Xn D ( ε ) ≤ . 2 Now fix any n ≥ nD (ε) and any multi-set S+ ∈ X n . By construction, A(S+ ) has no false positives on XnD (ε) \ CLOSH (S+ ), and since CLOSH (S+ ) ⊆ ℓ, it has no false positives on XnD (ε) . Therefore, errD (A(S+ ), ℓ) ≤ D(ℓ ∩ XnD (ε) \ A(S+ )) + D(X \ XnD (ε) ) (2) ε ≤ D(ℓ ∩ XnD (ε) \ A(S+ )) + . 2 n o Let H′ = h ∩ XnD (ε) | h ∈ H . By definition VCdim(H′ ) ≤ nD (ε). Applying the standard realizable PAC bound to H′ and distribution D+ , for n ≳ 1ε · (nD (ε) ln 1/ε), h i ES+ ∼D+n D(ℓ ∩ XnD (ε) \ A(S+ )) ≤ ε/2 . 29
Combining with (2) this implies ES+ ∼D+n [errD (A(S+ ), ℓ)] ≤ ε. Therefore, lim ES+ ∼D+n [errD (A(S+ ), ℓ)] = 0 .
n→∞
Recall that in Theorem 14 we presented a concept class that is improperly positive-only learnable, but does not satisfy finite exterior separability. By Theorem 20, we immediately obtain the following corollary. Corollary 21. There exists a concept class that is improperly positive-only learnable, but not properly positive-only consistent.
D.3
Proof of Theorem 7
In this section, we prove Theorem 7, which we restate below. Theorem 7 (ERM is not a universal deterministic learner). There exists a concept class H that is properly positive-only learnable by deterministic learners, but no deterministic proper ERM learner learns H from positive-only examples. We begin with an anti-concentration lemma, Lemma 23, which allows us to bound the largest probability of observing any fixed multi-set under Qn in terms of the largest atom of Q. This lemma follows from a theorem of Ushakov [Ush86]. Theorem 22 (Theorem 3 of [Ush86]). Let X1 , . . . , Xn be independent random variables over domain Ω. For each i ∈ [n], define pi := sup Pr[ Xi = ω ] . ω ∈Ω
Then there exists a universal constant C > 1 such that " # s n
sup Pr ∑ Xi = ω ≤
ω ∈Ω
i =1
C
. ∑in=1 (1 − pi )
Lemma 23. Let γ ∈ (0, 1), let n > 0, and let Q be a distribution over a domain Ω satisfying Q(ω ) ≤ 1 − γ. Then, for a universal constant C > 1 we have s C sup ′Pr n [S = S′ ] ≤ . nγ S∈Ωn S ∼ Q Proof of Lemma 23. Let x1 , . . . , xn be i.i.d. from Q, and let N = ( Nω )ω ∈Ω be the random histogram, where Nω = ∑in=1 1{ xi = ω }. Then N completely determines the sampled multiset. So for any fixed multiset S ∈ Ωn , if m(S) denotes its multiplicity vector, then Pr [S′ = S as multisets] = Pr[ N = m(S)] .
S′ ∼ Qn
Now define, for each i, Yi = exi , where eω is the unit vector at coordinate ω. Then N = ∑in=1 Yi . So the probability of any fixed multiset is exactly a point mass of the sum of independent random vectors Y1 , . . . , Yn . 30
For each i, the distribution of Yi has maximal atom sup Pr[Yi = y] = sup Q(ω ) ≤ 1 − γ . ω ∈Ω
y
Hence 1 − sup Pr[Yi = y] ≥ γ
for every i .
y
Now apply Theorem 22, for independent random vectors Y1 , . . . , Yn , " # s n C . sup Pr ∑ Yi = x ≤ n ∑i=1 1 − supy Pr[Yi = y] x i =1 Therefore, s sup Pr[ N = x ] ≤
C
= ∑in=1 γ
x
s
C . nγ
The key idea of the proof is as follows. Consider the class Hspr used in the separation (see Equation (3)). Hspr is almost closed under intersections: the only positive samples S+ ∈ X n for which CLOSHspr (S+ ) ∈ / Hspr are those whose domain is exactly {1, 2}. Thus, all other samples can be handled in a straightforward way by outputting the corresponding closure. The main difficulty is therefore the case in which the learner observes a sample supported only on {1, 2}. This event has non-negligible probability only when the target is of the form {1, 2, i⋆ }, for some i⋆ ∈ N \ {1, 2}, and the positive mass of i⋆ is small. In this regime, the learner uses the empirical imbalance between the number of 1’s and 2’s to decide what to output: it returns {1} if the number of 2’s is very small, returns {2} if the number of 1’s is very small, and otherwise returns a hypothesis of the form {1, 2, o (S+ )}, where o (S+ ) is determined by the observed multiplicity of 1’s. The analysis then splits according to the masses of 1 and 2 under D+ . If one of these masses is small, the learner outputs the corresponding singleton with high probability, and the resulting error is small because the omitted point has small marginal mass. On the other hand, if both D+ (1) and √ D+ (2) are at least on the order of 1/ n, then Lemma 23 implies that the probability of observing any fixed multi-set is small. Consequently, the index o (S+ ) selected by the learner cannot have large marginal probability with significant chance, so the error of {1, 2, o (S+ )} is small. This proves that the specially designed deterministic learner succeeds. The second part of the proof shows that no deterministic proper ERM learner can learn this class. Now, we are ready to prove Theorem 7. Proof of Theorem 7. Recall the concept class defined in Proposition 12
Hspr := {{1} , {2}} ∪ {{1, 2, i } : i ≥ 3} .
31
(3)
Part 1 (Learnability by deterministic learners). We first show that there exists a deterministic proper learner A such that Hspr is proper positive-only learnable by A. For every n ≥ 9 and multi-set S+ ∈ X n , let o (S+ ) denote the number of repetitions of 1 in S+ . Consider the learning algorithm A defined as follows {1, 2, i } if i ∈ S+ \ {1, 2} √ {1} o ( S+ ) ≥ n − n A(S+ ) = (4) √ {2} o ( S+ ) ≤ n {1, 2, o (S )} o.w. + For samples of size less than 9, define A arbitrarily as any concept in Hspr . Note that A is proper and deterministic by definition. Consider any ε, δ ∈ (0, 1), distribution D over X , ℓ ∈ Hspr and n ≥ (16C/εδ)4 where C is the universal constant in Lemma 23. We prove that Pr [errD (A (S+ ) , ℓ) ≥ ε] ≤ δ .
n S+ ∼D+
We prove the claim for 3 distinct cases of D and ℓ. Case 1: ℓ = {1} or ℓ = {2}. Then the learner receives a sample consisting only of the corresponding point. If ℓ = {1}, then o (S+ ) = n and A(S+ ) = {1}; if ℓ = {2}, then o (S+ ) = 0 and A(S+ ) = {2}. In both cases, the error is zero. Case 2:
ℓ = {1, 2, i⋆ } and D+ (i⋆ ) > ε/4 for some i⋆ ∈ N \ {1, 2}. Since n > 4 ln(1/δ)/ε, we have Pr[i⋆ ∈ / S+ ] < (1 − ε/4)n ≤ e−nε/4 ≤ δ .
Thus, with probability at least 1 − δ, the sample contains i⋆ , and A outputs {1, 2, i⋆ }. On this event the error is zero. Case 3: ℓ = {1, 2, i⋆ } and D+ (i⋆ ) ≤ ε/4 for some i⋆ ∈ N \ {1, 2}. Since ℓ = {1, 2, i∗ }, the false negative rate of A is
D(ℓ \ A (S+ )) = D(1) 1[A(S+ )(1) = 0] + D(2) 1[A(S+ )(2) = 0] + D(i∗ )1[A(S+ )(i⋆ ) = 0] ≤ D+ (1) 1[A(S+ )(1) = 0] + D+ (2) 1[A(S+ )(2) = 0] + ε/4 .
(5)
Then, we divide case 3 into two cases depending on values D+ (1) and D+ (2). √
√
√
D+ (1) ≤ 1/2 n or D+ (2) ≤ 1/2 n. Without loss of generality assume D+ (1) ≤ 1/2 n. 2 1 Then, using multiplicative Chernoff bound, since n > 6 lnε /δ we have Case 3.1:
Pr[o (S+ ) >
√
√
n] ≤ e− n/6 ≤ δ .
Thus, with probability at least 1 − δ, A(S+ ) is either {2} or {1, 2, i⋆ }. In the latter case the error is zero. In the former case, Equation (5) implies errD (A(S+ ), ℓ) = D(ℓ \ A(S+ )) ≤ D+ (1) + Therefore, since n > (2/3ε)2 we have errD (A(S+ ), ℓ) ≤ ε. 32
ε 1 ε ≤ √ + . 4 2 n 4
Case 3.2:
√
√
D+ (1), D+ (2) > 1/2 n. First suppose D+ (1) ≤ 2/ n. Using n ≥ (8/ε)2 , we get ε 2 D+ (1)1[A(S+ )(1) = 0] ≤ √ ≤ . 4 n √
Otherwise, D+ (1) > 2/ n. Since n ≥
4 ln(4/δ) ε
Pr[o (S+ ) ≤
2
√
(6)
, another multiplicative Chernoff bound gives √
n] ≤ e− n/4 ≤
δ . 4
Thus, with probability at least 1 − δ/4 we have A(S+ )(1) = 1, and subsequently
D+ (1)1[A(S+ )(1) = 0] = 0 . Combining this with (6), shows that, regardless of the value of D+ (1), with probability 1 − δ/4,
D+ (1)1[A(S+ )(1) = 0] ≤ ε/4 . Similarly, with probability at least 1 − δ/4, D+ (2)1[A(S+ )(2) = 0] ≤ ε/4. Combining these two bounds with a union bound and (5), we get that, with probability at least 1 − δ/2, the false-negative rate is bounded by
D(ℓ \ A(S+ )) ≤
3ε . 4
(7)
It remains to bound the false-positive rate. For every k ∈ {0, 1, . . . , n}, let Sk denote the multi-set consisting of k copies of 1 and n − k copies of 2. By the definition of A, since n ≥ 9,
∑ D(k)1 [A(S+ ) (k) = 1] = √
D(A(S+ ) \ ℓ) =
k ∈N\ℓ
∑
√ n≤k ≤n− n,k ̸=i⋆
√
D(k)1 [S+ = Sk ] .
(8)
√
Since D+ (1), D+ (2) > 1/2 n, we have supk∈N D+ (k ) < 1 − 1/2 n. By Lemma 23, and since n ≥ (16C/εδ)4 , for every multi-set S we have s εδ 2C Pr n [S+ = S] ≤ √ ≤ . 8 S+ ∼D+ n Combining this with (8), we get E [D(A(S+ ) \ ℓ)] ≤
√
∑√
D(k) Pr[S+ = Sk ] ≤
n≤k ≤n− n, k ̸=i⋆
εδ εδ D(k) ≤ . √ 8 √n≤k≤n∑ 8 − n, k̸=i⋆
Therefore, by Markov’s inequality, Pr[D(A(S+ ) \ ℓ) > ε/4] ≤ δ/2. Combining this with Equation (7) shows that PrS+ ∼D+n [errD (A(S+ ), ℓ) > ε] ≤ δ, completing the proof of learnability by deterministic learners.
33
Part 2 (Non-learnability by deterministic ERM learners). We then prove that Hspr is not properly positive-only learnable by any deterministic ERM proper learner A. Fix any n ≥ 2. For any a ∈ N \ {1, 2}, define the pair (D a , ℓ a ) as follows:
ℓ a = {1, 2, a + 1} ,
D a (1) =
1 , 2n
D a (2) =
n−1 , 2n
Da ( a) =
1 , 2
where D a is zero elsewhere. Let S be a multi-set with exactly one copy of 1 and n − 1 copies of 2. Since A is an ERM learner, we have Domain(S) ⊆ A(S). Thus, A(S) = {1, 2, a⋆ } for some a⋆ ∈ N \ {1, 2}. Furthermore, under the target ℓ a⋆ = {1, 2, a⋆ + 1}, the point a⋆ is negative and has D a⋆ -mass 1/2. Hence, 1 errDa⋆ (A(S), ℓ a⋆ ) = . 2 In addition, under D+,a⋆ , the mass of 1 is 1/n and the mass of 2 is (n − 1)/n. Therefore, 1 Prn [S+ = S] ≥ n · n S+ ∼D+ ,a⋆
n−1 n
n −1
>
n−1 n
n
≥
1 . 4
Consequently, Pr
n S+ ∼D+ ,a⋆
1 1 ≥ . errDa⋆ (A(S+ ), ℓ ) ≥ 2 4 a⋆
Thus, Hspr is not properly positive-only learnable by A.
D.4
Proof of Theorem 8
In this section, we prove Theorem 8, which we restate below. Theorem 8 (Separation of learnability, non-uniform learnability, and consistency). There exist concept classes H1 and H2 , each with VC dimension 1, such that: 1. H1 is properly positive-only consistent, but not non-uniformly properly positive-only learnable. 2. H2 is non-uniformly properly positive-only learnable, but not properly positive-only learnable. Proof. We divide the proof into two parts corresponding to the two claims. Part 1 (Separation of consistency and non-uniform learnability). Consider the concept class
Hbin := {h a | a ≥ 3} ,
h a := {1, 2, a, a + 2, a + 4, . . .} .
Observe that VCdim(Hbin ) = 1. We first show that Hbin satisfies the finite exterior separability property. Consider any finite-sized S ⊆ N that is realized by Hbin , and any F ⊆ N \ CLOSHbin (S). We consider two cases for S, and in each case we show that there exists h ∈ Hbin such that Domain(S) ⊆ h, but F ∩ h = ∅. Case 1: There exists some a ≥ 3 such that a ∈ Domain(S). Denote t = min(Domain(S) \ {1, 2}) . It is easy to see that ht = CLOSHbin (S). Thus, since F ⊆ N \ CLOSHbin (S), we have ht ∩ F = ∅. Moreover, by the definition of the closure, Domain(S) ⊆ ht . 34
Case 2: Domain(S) ⊆ {1, 2}. If F = ∅, then any h ∈ Hbin satisfies the desired condition. Otherwise, choose r ≥ 3 such that r > max( F ). Then Domain(S) ⊆ {1, 2} ⊆ hr . Moreover, since r > max( F ), no element of F belongs to the tail {r, r + 2, r + 4, . . .} of hr . Also, since {1, 2} ⊆ CLOSHbin (S), we have {1, 2} ∩ F = ∅. Therefore, hr ∩ F = ∅. Combining these two cases, we conclude that Hbin satisfies finite exterior separability. By Theorem 20, Hbin is proper positive-only consistent. It remains to prove that Hbin is not nonuniformly proper positive-only learnable. For any a ≥ 3, define the pair (D a , ℓ a ) as follows: 1 D a (1) = D a (2) = , 4
ℓ a = h3+(a mod 2) ,
Da ( a) =
1 , 2
where D a is zero elsewhere. Notice that D a,+ = U{1,2} . Indeed, by the definition of ℓ a , the point a is not labeled positive by ℓ a , while both 1 and 2 are labeled positive. For the sake of contradiction, suppose that Hbin is non-uniformly proper positive-only learnable by a proper learner A. Consider any n ≥ max mHbin (1/4, 1/4, h3 ) , mHbin (1/4, 1/4, h4 ) . We now show that for any fixed S+ ∈ {1, 2}n , lim Pr [ a ∈ A(S+ ) or a + 1 ∈ A(S+ )] = 1 .
a→∞ A
Since A is proper, for every fixed S+ ∈ {1, 2}n , there exists an N≥3 -valued random variable BS+ such that A(S+ ) = h BS+ . For every realization BS+ = b, if a ≥ b, then exactly one of a and a + 1 belongs to hb , because a and a + 1 have opposite parity and hb contains all sufficiently large numbers with the same parity as b. Therefore,
{ BS+ ≤ a} ⊆ { a ∈ A(S+ ) or a + 1 ∈ A(S+ )} . Since BS+ is natural-number-valued, we have lima→∞ Pr[ BS+ ≤ a] = 1. Hence, lim Pr [ a ∈ A(S+ ) or a + 1 ∈ A(S+ )] = 1 .
a→∞ A
Since {1, 2}n is finite, averaging over S+ ∼ U{n1,2} gives lim
Pr
a → ∞ S + ∼U n
{1,2}
,A
[ a ∈ A(S+ ) or a + 1 ∈ A(S+ )] = 1 .
Now observe that the event a ∈ A(S+ ) implies errDa (A(S+ ), ℓ a ) ≥
1 , 2
/ ℓ a . Similarly, the event a + 1 ∈ A(S+ ) implies because D a assigns mass 12 to a, and a ∈ errDa+1 (A(S+ ), ℓ a+1 ) ≥ Therefore,
lim
Pr
a → ∞ S + ∼U n
{1,2}
,A
1 . 2
1 errDa (A(S+ ), ℓ a ) + errDa+1 (A(S+ ), ℓ a+1 ) ≥ = 1. 2 35
Consequently, there exists a⋆ ∈ N such that 1 1 ⋆ ⋆ ≥ Pr S ) , ℓ err S ) , ℓ + err > . ) (A( (A( ) + + a a +1 D a⋆ D a ⋆ +1 2 2 S+ ∼U{n1,2} , A Using a union bound we get 1 1 1 + Pr errDa⋆ +1 (A(S+ ), ℓ a⋆ +1 ) ≥ > . Pr errDa⋆ (A(S+ ), ℓ a⋆ ) ≥ n n 4 4 2 S+ ∼U{1,2} , A S+ ∼U{1,2} , A Thus, for some b ∈ { a⋆ , a⋆ + 1}, we have 1 1 > . Pr errDb (A(S+ ), ℓb ) ≥ n 4 4 S+ ∼U{1,2} , A By definition, ℓb ∈ {h3 , h4 }, and as observed above, Db,+ = U{1,2} . This contradicts n ≥ max mHbin (1/4, 1/4, h3 ) , mHbin (1/4, 1/4, h4 ) . Therefore, Hbin is not non-uniformly properly positive-only learnable. Part 2 (Separation of non-uniform learnability and learnability). Recall the concept class considered in Proposition 13:
Htail := {h a : a ≥ 3} ,
h a := {1, 2} ∪ {m ∈ N : m ≥ a} .
where
Observe that VCdim(Htail ) = 1. In Proposition 13, we already showed that Htail does not satisfy the distributional exterior separability property, and thus it also does not satisfy the uniform exterior separability property. Therefore, by Theorem 4, Htail is not properly positive-only learnable. It remains to prove that Htail is non-uniformly properly positive-only learnable. Define the learner A as follows. For any n ∈ N and S+ ∈ X n , let i (S+ ) := min Domain(S+ ) \ {1, 2} , whenever Domain(S+ ) \ {1, 2} is non-empty, and set ( h i ( S+ ) if Domain(S+ ) \ {1, 2} ̸= ∅, A(S+ ) := hmax{n,3} otherwise . Fix a target concept ℓ = h a⋆ for some a⋆ ≥ 3. We show that this learner succeeds with a sample size that may depend on a⋆ . Consider any n ≥ a⋆ . For every S+ ∈ ℓn , we claim that A(S+ ) ⊆ ℓ. Indeed, if Domain(S+ ) \ {1, 2} is non-empty, then i (S+ ) ∈ ℓ \ {1, 2}, and therefore i (S+ ) ≥ a⋆ . Hence hi(S+ ) ⊆ h a⋆ . On the other hand, if Domain(S+ ) \ {1, 2} = ∅, then A(S+ ) = hn ⊆ h a⋆ . Thus, for every positive-only sample S+ ∈ ℓn , the learner has zero false positives. Next, observe that A always satisfies Domain(S+ ) ⊆ A(S+ ). Therefore, by applying standard realizable PAC bounds to Htail under D+ , there exists a universal constant C > 0 such that for log(1/ε)+log(1/δ) n≥C , with probability at least 1 − δ, the false negative is bounded by ε
D(ℓ \ A(S+ )) ≤ D+ (ℓ \ A(S+ )) ≤ ε . Now using A(S+ ) ⊆ ℓ yields that Htail is non-uniformly proper positive-only learnable by A.
36
D.5
Proof of Theorem 9
In this section, we prove Theorem 9. The proof has two parts. First, we show that exact exterior separability together with finite VC dimension is sufficient for proper positive-only learning by a stable learner. This direction is immediate from the closure-based learner. Second, we prove a stronger necessity statement: exact exterior separability and finite VC dimension are necessary even for a weaker notion of stability, which we call size-dependent stability. We begin with sufficiency. Proposition 24. If H satisfies exact exterior separation and VCdim (H) < ∞, then H is properly learnable from positive-only examples by a stable learner. Proof. Consider the learner A(S+ ) = CLOSH (S+ ). Clearly A satisfies A(S′ ) = A(S) for all positive samples S and S′ such that S ⊆ S′ and Domain(S′ ) ⊆ A(S). Thus, A is stable. Combining this with Lemma 19 completes the proof. For the necessity direction, we prove a slightly stronger statement. We show that exact exterior separability and bounded VC dimension are necessary even if the learner satisfies only the following weaker stability condition. Definition 8 (Size-dependent Stability). We say that a proper learner A is size-dependent stable if there exists a function f : X [∗] × N → H such that for all S, S′ ∈ X [∗] with probability 1 over any randomness in A, the following holds if
S ⊆ S′ and Domain(S′ ) ⊆ A(S),
then
A(S′ ) = f (S, |S′ |) .
Proposition 25. If H is properly learnable from positive-only examples by a size-dependent stable learner, then H satisfies exact exterior separation and VCdim (H) < ∞. Proof. Assume that H does not satisfy the stated property. Then either VCdim(H) = ∞, which implies that VCdim(H∩ ) = ∞, and by the results of Lee, Mehrotra, and Zampetakis [LMZ26], this in turn implies that H is not positive-only learnable; or there exists a finite set B = { x1 , x2 , . . . , xs } ⊆ X such that CLOSH ( B) ∈ / H. Denote F := X \ CLOSH ( B). For any x ∈ F, define the distribution D x as
Dx (x) =
1 , 2
Dx (x′ ) =
1 for all x ′ ∈ B , 2s
and zero elsewhere. Also, let ℓ x be any concept in H such that B ⊆ ℓ x , but ℓ x ( x ) = 0. Note that since x ∈ / CLOSH ( B) such a concept ℓ x always exists. Notice that for all x ∈ F, we have D+,x = UB . We prove that for every proper size-dependent stable positive-only learner A, 1 lim sup Pr errDx (A(S+ ), ℓ x ) ≥ = 1. n→∞ x ∈ F S+ ∼UBn ,A 2s Therefore, A cannot learn H with positive-only examples. Let A be any proper size-dependent stable positive-only learner for H. We prove the claim for two distinct cases, depending on the output of A over input samples that contain all B. 37
Case 1: There exists a finite-sized multi-set E ∈ X [∗] such that Domain( E) = B, and Pr [ B ⊆ A( E)] > 0. A
Note that due to the stability of A, every sample S+ ∈ Bn that contains E satisfies A(S+ ) = f ( E, n) with probability 1 over the learner’s randomness. Moreover, as n goes to infinity the probability of a S+ sampled by UBn containing E goes to 1. Thus, lim
Pr
n→∞ S+ ∼UBn ,A
[A(S+ ) = f ( E, n)] = 1 .
(9)
We consider two distinct cases based on f ( E, n). Case 1.1: If B ⊈ f ( E, n), then for all x ∈ F we have 1 errDx ( f ( E, n), ℓ x ) ≥ 2s . By combining this with (9), we attain our objective. Case 1.2: If B ⊆ f ( E, n), then since f ( E, n) ∈ H, there exists an x E ∈ f ( E, n) ∩ F. Thus, errDxE ( f ( E, n), ℓ xE ) = 1/2. By combining this with (9), we attain our objective. Case 2: No such E exists. Then for every sample S+ containing B and every x ∈ F, we have Pr
S+ ∼UBn ,A
[errDx (A(S+ ), ℓ x ) ≥ 1/2s] = 1 .
Note that, as n goes to infinity, the probability of a S+ sampled by UBn containing B goes to 1. Combining Proposition 24 and Proposition 25 proves Theorem 9.
38