Learning from positive and unlabeled examples -Finite size sample bounds

Thank you for your detailed feedback and insightful questions. We would like to address your questions and concerns bellow:

• Broader context to our contribution and extended discussion of related work: In lines 63–70 of the paper, we briefly summarized our main high-level contributions. We will expand this summary and provide a more detailed discussion of related work in the camera-ready version.
• Tightness of the lower bound for unlabeled examples: The reviewer is right. Our lower bound for the number of unlabeled examples is not tight. A complete characterization of the sample complexity for realizable PU learning in the SCAR setup remains an open problem. That said, to the best of our knowledge, this is the first lower bound on the sample complexity of unlabeled examples in this setting, and we believe it constitutes a meaningful contribution to the literature. We would also like to highlight that Theorem 3 was among the most technically challenging results in the paper.
• Clarity of assumptions: Any additional assumptions required for a given theorem are stated explicitly within that theorem. Otherwise, the results hold for general concept classes. Let us also briefly summarize every major assumption made in the paper (by major we are not including obvious ones such as bounded VC dimension, etc.). Note that all of them appear in Section 4. For the SAR setup (Theorem 8), we assumed a lower bound on the weight ratio, and we motivated its necessity in lines 207–212. For the PCS setup, in addition to the lower bound on the weight ratio, we assumed that the domain is $[0, 1]^k$ and imposed a $\gamma$-margin assumption. We demonstrated the necessity of the $\gamma$-margin assumption in Theorem 10. We will add further discussion of these assumptions and mark them more explicitly in the text.
• Relation to one-sided error: This is a good observation. First, note that for any intersection-closed concept class with finite VC dimension, we have $C_\cap = C$, so the assumption $\operatorname{VCD}(C_\cap) < \infty$ is indeed weaker than assuming both intersection-closure and finite VC dimension. There are indeed connections between realizable PU learning without access to unlabeled examples (i.e., learning from positive-only examples) and learning with one-sided error. In short, learning with one-sided error corresponds to realizable learning from positive-only examples while imposing two additional constraints: (i) the learner must be proper, and (ii) the false negative must be zero. Consequently, stronger assumptions are required for one-sided error learning. We will clarify this connection further in the camera-ready version.
• Relationship between claw number and other combinatorial parameters: We discussed the relationship between $\operatorname{VCD}(C_\cap)$ and the claw number in Proposition 4. In fact, $\operatorname{VCD}(C_\cap)$ was the original motivation for defining the claw number. However, at present, we are not aware of any connection between the claw number and other established combinatorial parameters beyond VC dimension. We agree that this is an excellent direction for future research.
• Lower bounds on the complexity of unlabeled examples: One fundamental difference between PU learning and semi-supervised learning is that, except for certain restricted classes, learning from positive-only examples is generally not possible. This makes it less surprising that we are able to establish lower bounds on the number of unlabeled examples required. However, an interesting line for future work is “For which setups we can elevate the need for positive examples”. Theorem 1 in our paper shows that reducing the number of required labeled examples necessitates additional assumptions either on the marginal distribution or the concept class (as is the case in semi-supervised learning.)

We also thank the reviewer for pointing out those issues, and we will address them in the camera-ready version.

Rereading the paper I believe there is a tiny issue with Def. 2 (the claw number). Independently of $\frak h$ (even if its 0) the definition requires sets $B$ of arbitrary large size $m\ge \frak h$. However if the domain is finite this is not possible. I guess a fix like $|X|\ge m \ge \frak h$ is sufficient?

One small clarification on one-sided: I did not meant to say that the class is intersection-closed and has finite VC dimension. I meant to say the "intersection closure" of a class $C$ (i.e., what you call $C_\cap$) has finite VC dimension (see, e.g., Kivinen 1995). So this is exactly as in your Proposition 4. I digged a bit deeper, and in fact there seems to be some relationship between claw number and Kivinen's slicing dimension. E.g., (haven't though deeply here) for $\frak h=1$ you get sets $B$, which are "sliced", of arbitrary size. Thus the slicing dimension is infinite. Also a similar fact is also captured by the fact that the VC-dim of $C_\cap$ is the (one-centered) star number of the original class $C$ (see Theorem of 19 of Hanneke 2024). Having said that it is perhaps better to (at least partially) attribute Proposition 4 to these 2 papers, if what I said is valid.

Kivinen, Jyrki. "Learning reliably and with one-sided error." Mathematical systems theory 28.2 (1995): 141-172.
Hanneke, Steve. "The star number and eluder dimension: Elementary observations about the dimensions of disagreement." COLT 2024.

We would first like to thank the reviewer for pointing out these papers. We were not aware of Kivinen (1995). You are correct that both the slicing dimension and the one-centered star number are equal to $VCD(C_\cap)$. While we had observed that $VCD(C_\cap)$ lower bounds the star number, we were not aware that the notion of the one-centered star number has been explicitly discussed in the literature. We will include a discussion of this relationship in our revised manuscript.

Clarification on learning from one-sided error:

The definitions of learning from one-sided error in Kivinen (1995) and Natarajan (1987) differ slightly. Both require the learner to have zero false negative. However, Natarajan (1987) additionally assumes that the training data consists solely of positive examples and that the learner is proper. Specifically, Natarajan (1987) defines one-sided error as follows:

Following (Valiant, 1984), we say that a family of functions $F$ is learnable with one-sided error if and only if there exists an algorithm that (a) makes polynomially many calls of EXAMPLE both in an adjustable error parameter $h$ and in the number of variables $n$. The algorithm need not run in polynomial time.
(b) For all functions $f \in F$, and all probability distributions $P$ over the assignments, the algorithm deduces with probability $(1 - 1/h)$ a function $g \in F$, such that for any assignment $a$: $g(a)=1 \implies f(a)=1$ $\text{if } S=\{a \mid f(a)=1 \text{ and } g(a)=0\},$ $\text{ then } \quad \sum_{a \in S} P(a) \leq \frac{1}{h}.$

The condition $g \in F$ enforces properness. They also define a learning algorithm as follows:

A learning algorithm is an algorithm that attempts to infer a function $f$ on the variables, from positive examples for $f$.

This shows that they require training data to be positively labeled. By contrast, in Definition 4.1 of Kivinen (1995) I cannot find any such restrictions. In Section 2.4, they explicitly emphasize that they do not impose properness:

In PAC learning it is sometimes required that the hypothesis must be from the concept class to be learned. In reliable learning and learning with one-sided error the criteria for a good hypothesis are tighter, and we must allow the learner to choose its hypothesis from a larger set. In learning with one-sided error we accept as a hypothesis any measurable set.

Natarajan (1987) condition:

The characterizing condition that Natarajan (1987) establishes for their setup in Theorem 3 is that $F$ has polynomial dimension. Having polynomial dimension entails that the concept class is well-ordered, i.e., the intersection of every two concepts remains in the class (we referred to this property as intersection closedness in our rebuttal).

On loosening the $|X| = \infty$ condition in the definition of claw number :

A fixed $m$ is insufficient in the definition of claw number. This is because any concept class over a finite domain $X$ satisfies $VCD(C_\cap) \leq |X| < \infty$. By the results of Lee et al. (2025), such classes can be learned with zero unlabeled examples, and it is impossible to establish a lower bound on unlabeled examples. Consequently, the notion of claw number should be zero when the domain has a finite size.

References

Lee, J. H., Mehrotra, A., and Zampetakis, M. (2025). Learning with positive and imperfect unlabeled data. arXiv preprint arXiv:2504.10428.

Thank you for your constructive feedback and helpful suggestions. We would like to address your questions and concerns bellow:

• Dependence on Ben-David and Urner (2012): While we clearly stated that our results in Section 4 are inspired by Ben-David and Urner (2012), our application to PU learning and the results in this domain are new. Furthermore, as described in lines 265–270, the application to PU required significant alterations to Ben-David and Urner (2012). Also, note that Section 4 constitutes only a small portion of our overall contribution.
• Comparison with Coudray et al (2023): The results of Coudray et al. (2023) are for the SAR setup; however, they are not directly comparable to ours. Their work addresses the more general agnostic PU learning setting and assumes knowledge of the class prior $\alpha$, whereas we focus on the realizable setting without requiring knowledge of $\alpha$.
• Further discussion about assumptions: Let us briefly summarize every major assumption made in the paper (by major we are not including obvious ones such as bounded VC dimension, etc.). Note that all of them appear in Section 4. For the SAR setup (Theorem 8), we assumed a lower bound on the weight ratio, and we motivated its necessity in lines 207–212. For the PCS setup, in addition to the lower bound on the weight ratio, we assumed that the domain is $[0, 1]^k$ and imposed a $\gamma$-margin assumption. We demonstrated the necessity of the $\gamma$-margin assumption in Theorem 10. We will add further discussion of these assumptions and mark them more explicitly in the text.
• Lack of experiments: The NeurIPS conference welcomes a broad range of contributions, including purely theoretical work. Our submission falls within this scope.

We would like to thank the reviewer for assessing our work and for valuable feedback. The reviewer expressed concern about $\gamma$-margin assumption and sample complexity for unlabeled data that being exponential in the data dimensionality: Informally, Theorem 10 demonstrates that in PCS setup without $\gamma$-margin assumption, any PU learner that achieves error less than $\varepsilon$ with probability more than $1 - \delta$ should at least receive a total number of positive and unlabeled examples which is in order of square root of domain size. Consequently, the task of PU learning in the PCS setup without $\gamma$-margin assumption is impossible. Similarly, Theorem 11 demonstrates that the exponential dependence of the total number of unlabeled and positive examples is unavoidable in the PCS setup. Interestingly, our results for the SAR setup (Theorem 8) do not require either of these assumptions. This highlights that the PCS setup is inherently more challenging than the SAR setup.

Thank you for carefully evaluating our work and for offering constructive feedback. We would like to address your questions bellow:

1. Case-control vs Censoring PU learning: Yes, our paper focuses on the case-control PU learning setting. We tried to emphasize this on line 40 of the manuscript (although we mistakenly referred to it as "control set PU learning" – this was a typo). While we briefly outlined the distinction between censoring PU learning and case-control PU learning in lines 34-37, we will happily explain this distinction in more detail. We followed the naming convention from the survey by Bekker and Davis (2020), which is why we cited their work. We will update the citations to Elkan and Noto (2008) and du Plessis et al. (2015).
2. Relation with Kato and Teshima (2021): We agree that there is a connection between density ratio estimation and PU learning. However, the results presented in Section 5.2 of our paper hold for any hypothesis class with VC dimension $d$ and any distribution with class prior $\alpha$. In contrast, Theorem 1 of Kato and Teshima (2021) relies on strong Assumptions 3 and 4 introduced in Section 4.1, and does not provide any lower bound. In our Theorem 14, we show that our upper bound on the generalization error is tight.
   The difference between our work and that of Kato and Teshima (2021) is further highlighted by the fact that Theorem 1 in their paper shows that the error of the BD minimization method can approach the error of the best concept in the class as the number of training examples goes to infinity. In contrast, our Theorem 14 demonstrates that, for a given $\alpha$, no algorithm can achieve an error better than a factor of $\frac{\max(\alpha, 1 - \alpha)}{\min(\alpha, 1 - \alpha)}$ times the error of the best classifier in the class regardless of the number of unlabeled or positive training examples.
   We will include an extended discussion clarifying the relationship between our work and that of Kato and Teshima (2021).

References:
Bekker, Jessa, and Jesse Davis. "Learning from positive and unlabeled data: A survey." Machine learning 109.4 (2020): 719-760.