Learning from positive and unlabeled examples -Finite size sample bounds
Authors: Farnam Mansouri
Shai Ben-David
Venue: NeurIPS 2025 poster ()
Keywords: Learning Theory
PU Learning
Domain Adaptation
Primary area: theory
TL;DR: This paper provides sample complexity bounds for learning from positive and unlabeled examples.

Abstract: PU (Positive Unlabeled) learning is a variant of supervised classification learning in which the only labels revealed to the learner are of positively labeled instances. PU learning arises in many real-world applications. Most existing work relies on the simplifying assumption that the positively labeled training data is drawn from the restriction of the data generating distribution to positively labeled instances and/or that the proportion of positively labeled points (a.k.a. the class prior) is known apriori to the learner. This paper provides a theoretical analysis of the statistical complexity of PU learning under a wider range of setups. Unlike most prior work, our study does not assume that the class prior is known to the learner. We prove upper and lower bounds on the required sample sizes (of both the positively labeled and the unlabeled samples).

Learning from positive and unlabeled examples -Finite size sample bounds
Farnam Mansouri
Shai Ben-David
University of Waterloo and Vector Institute fSmansou@uaterrooo.c
University of Waterloo and Vector Institute shai wwwatullooorccoomm ca
Abstract
PU (Positive Unlabeled) learning is variant of supervised classification learning in which the only labels revealed the learner are of positively labeled instances. PU learning arises in many real-world applications. Most existing work relies on the simplifying assumptions that the positively labeled training data is drawn from the restriction of the data generating distribution to positively labeled in- stances and/or that the proportion of positively labeled points (a.k.a. the class prior) is known apriori to the learner. This paper provides a theoretical analysis the statistical complexity of PU learning under a wider range of setups. Unlike most prior work, our study does not assume that the class prior is known to the learner. We prove upper and lower bounds on the required sample sizes (of both the positively labeled and the unlabeled samples).
Introduction
Learning from positive and unlabeled data (PU learning) is variant of binary classification predic- tion semi-supervised learning, where the training data consist only of positively labeled and unla- beled examples. PU learning arises in many applications, such personal advertisement (where person is labeled according to whether a given add is relevant to them. When person responds to the add, know they belong the set of positive instances. However, cannot tell the label of unresponsive customers), land cover classification Li all (201I) (say, we wish to classify forest land cover from aerial images, where training data consist of unlabeled land images and forest aerial images). prediction of protein similarity Elkan and Notd (200N) and many other applications like knowledge base completion Bekker and Davis (2020), discase-gene identification Yang al. (2012) and more.
Standard machine learning paradigms, such empirical risk minimization (namely, training clas- sifier to minimize the ciis-classification loss over the training data) or regularized risk minimization may fail badly in such settings, since their success guarantees rely on having access labels from both classes (positive and negative labels). We are interested finite sample size generalization guarantees. Having weaker supervision than standard fully supervised learning, achieving gener- alization bounds for PU learning requires stronger assumptions. In this work, we show how some of the common assumptions used in this domain can be relaxed, while also showing some negative, impossibility results.
Various setups for PU learning. We consider the case in which both training samples (the positively labeled and the unlabeled examples) are generated by random processes unknown to the learner. The learner's goal is to obtain classifier that minimizes misclassification with respect to a target evaluation distribution D over x {0, 1} (where X' is the domain set). Training data generating setup can be viewed along two basic axes; The first is whether the positively labeled data is generated independently of the unlabeled sample (as opposed to the case where the positively labeled examples
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

are sampled from an already sampled unlabeled set of instances). The other axis is the labeling mechanism through which positive labels are assigned training examples.
Our paper focuses on scenarios where the unlabeled sample and the positive sample are independent
of each other (called case-control scenarios by afl (20T6). As example of a case-control scenario, consider the task of predicting whether a given profile will become a user of a mobile application. For this example, the positive sample can be collected from individuals who already users of the application, while the unlabeled sample can be drawn from a broader pool of random individuals.
Let D+ and D_ denote the conditioning of D on the label being positive or negative respectively. We consider four setups for how positive training data is generated (See Section @ for formal definitions):
Selected completely at random (SCAR) Elkan and Notd (2008): Positive training data is
drawn i..dd from D+..
Selected at random (SAR) Bekker al (2019): Positive training data are drawn i.i.d. from a distribution whose support is a subset of the support of D4..
Positive covariate shift (PCS): Positive training data is drawn from a distribution that shares the same labeling function as 'D but has different marginal distributions (referred to as positive-only shift in Sakai and Shimizu (2019)).
Arbitrary positive distribution shift (APDS): Positive training data is drawn from ar- bitrary distribution (generalization bounds in this case depend on measures of similarity between the two distributions).
Following the common terminology, realizable setup refers learning with respect data distri- butions for which some member of the concept class has zero misclassification loss. The setup is agnostic PU learning when such condition is assumed. The class prior is the probability of posi- tive labels, a == DI (I. 1) E X}}. In most prior work on PU learning, the class prior assumed as prior knowledge.
Our Contributions. The main high-level contributions of this paper are follows:
1. We provide finite sample complexity bounds without relying on knowledge of the class prior a. To the best of our knowledge, prior provable results in PU learning typically as- sume that a is known and used by the learner. The only exceptions are Lwnet aD (2002), which provides result limited to realizable PU learning under the SCAR setup, Lee et all (20255 that are studying a setup where unlabeled data is sampled from a distribution dif- ferent from the target evaluation data, and Kato and Teshima (202T)); Zheng et all (22)2)
which study specific classes of neural networks.
2. We provide new sample complexity upper bounds in variety of setups, for which such bounds have not been previously proved.
3. We prove novel lower bounds that match existing positive results for the SCAR setup.
In more detail, our contributions are:
Realizable PU Learning (SCAR setup). In Theorem M. we provide a lower bound on the sample complexity of positive examples that nearly matches earlier upper bounds (e.g.. by Luu et all (2002)). Moreover, in Theorem B. we also provide a lower bound on the sample complexity of unlabeled examples based novel combinatorial parameter that we introduce, called claw number.
Realizable PU learning (SAR setup). We prove the first finite sample complexity for this setup that does not require knowledge a (Theorem N. We then provide an almost tight lower bound on the sample complexity of positive examples in Theorem EL
Realizable PU learning (PCS setup). For this setup, we introduce the first algorithm which guarantees finite sample complexity (Theorem I.). We then provide lower bounds on sum of sample complexity of positive and unlabeled examples (Theorem I and Theorem I[].
These results highlight the differences between the PCS and the SAR setups.
Agnostic PU Learning (SCAR setup, when is known). For this setup, in Theorem KK we propose a lower bound on the sample complexity of both positive and unlabeled examples that nearly matches existing upper bounds established in Du Plessix all (2015)).

---

Agnostic PU Learning (SCAR setup, when a is unknown). While without knowledge of a or additional assumptions on the data or concept class it is impossible find classifier whose misclassification rate is arbitrarily close to that of the best in the class, we show in Corollary I& that learner can always find a classifier whose misclassification rate is arbi- trarily close to min[a,1-a] class. Moreover, in Corollary [4, we show that this multiplicative factor is tight. Our result also yields an improved generalization bound in scenarios where an approximation of is available.
max(a,11aa) times the misclassification rate of the best concept in the concept
Agnostic PU learning (APDS setup). For this setup, we derive the first generalization bounds with finite sample complexity (Theorem I
Table 1: Summary of all results presented in this paper (excluding those in Section 5.2) Here, d
denotes the VC-dimension of the concept class C: & is the dimensionality of the input space; h is the claw number of C; r is a weight ratio between distribution of positively labeled training data and D.. : 7 is the margin parameter ş is any lower bound on a that is available to the learner. Logarithmic factors are suppressed in this table.
Bounds on the sample complexity of PU learning
Realizable (SCAR)
mc (2.8) á
To (s, 6) 0
me myntabale
(e, 6) =
all (2002)
me (e,8) .
unlabel
New results in this work.
Realizable (SAR)
m (e, 52
mc ( 8) = =0(
me (e, - (2)
mc
manlabel
untabal (c, = =0
New results in this work.
New results in this work.
Realizable (PCS)
me
pax (e, 8) = Ō (142))
me
unlabel (e, =
(x<)) (xF)*
me
+sad
New results in this work.
mc
pos (E,8) + me
unlabel
(5,0) 0) = 52(1 1/27)
New results in this work.
Agnostic
m pos (2, = 0
mc
unlabrd (e,
Du Plessrs et al (2OTS)
(SCAR, known a))
me (e. 5
pos
mc (c,
untubbll
New results in this work.
Related works. We briefly survey previous theoretical studies of PU learning. We start with works on the SCAR setup. For the casiest case of realizable learning, Lul (2002) describe an algorithm with finite sample complexity.
For the more challenging agnostic PU learning setting, previously proposed approaches typically rely on priori knowledge of the class prior (e.g.. Du Plessis all (2015)). When the class prior is unknown, existing studies often impose restrictive assumptions on the underlying distribution or the concept class. Much of this literature focuses on estimating the prior a. The assumptions employed in these works include: (i) Separability: non-overlapping support between the D_ and D+ Elkan and Notd (2008); Du Plessis and Sugiyama (2014); (ii) Anchor sel: requiring a subset of the instance space defined by partial attribute assignment, to be purely positive Scott (20T5): Lu
and Tao (2015); Christoiaa all (2016); Bekker and Davis (MI1N); (iii) Ramaswamy ct all (201G) discuss generalization of anchor set assumption and call it also separability; (iv) Irredueibility:
D_ cannot be expressed as a linear combination of 'D+ and any other distribution Blanchard et all (20T0); Dain all (2016). There also studies focusing on specific classes of neural networks Kata and Teshima (2021)); Zheng et all (2022), which adopt density-rati estimation method. Our results do not rely on any of these assumptions.
Next, we consider studies of PU learning that extend beyond the SCAR setup. Several articles examine PU learning in the SAR setting Coudray et al. (2023); at. (2023); Gong et al. (2021):
Na (2020); Bekker et all (2019); Kato all (2011)); He all (2018), among which only Coudray alll (212)); Gong et all (2021); Kato aall (2019); al (2I)) pursues theoretical analysis (the
others focus primarily on empirical evaluations). In contrast to our work, these studies assume that
is known. Under that assumption, they provide learnability results applicable to the agnostic PU learning setting. Kato et all (2019) focuses on establishing statistical consistency rather than finite
sample guarantees. He all (2018) analyze special case of the SAR setting, referred to as the probabilistic gap assumption.
Sakai Bad Shimizu (2019); Hammoudeh and Lowd (2020): Kumar and Lambert (2123) discuss
statistical consistency for different variations of PU learning. This is in contrast with our focus on finite sample size generalization bounds. Lee ct all (2025) studies both the sample complexity and
3

---

computational complexity in a setting where the distribution of unlabeled training data is drawn from a distribution that can differ from the target evaluation distribution, while the positive training data is drawn from the target evaluation distribution conditioned on the label being positive.
Note that, due space constraints, all proofs in this submission are deferred to the appendix.
2 Setting
We consider the following setup for learning with positive and unlabeled examples (PU learning). Let X' be the domain set, y {0, } the labels set. We consider two distributions, a distribution DD over X' x V, and distribution for sampling the positively labeled training data over X' denoted by P. Given function f X - V. define errp(f) == Pr(s..i~=lf(a) + y] as the error of with respect to D. Also, define positive distribution, and negative distribution respectively to be (A) ( y = and D- (A) == [(A y = 0) for every measurable set S X. Moreover, denote xx to be the marginal distribution of 'D over the domain set.
A PU learner takes (i) sample S of size i.i.d. drawn from marginal distribution Dx, and (ii) sample SP of size i.i.d. drawn from P independent of Sy, denoted by SP, and similar to classical machine learning, it aims output function f X y which minimizes err Formally, PU learner is a function
A:X² x X 10,
We now establish our framework for evaluating the success of PU learners:
Definition 1 (PU learnability). Let C be a concept class over domain X. Moreover, let W be a set of pairs (D, P), where D is distribution over X x Y; and P is a distribution over X. We say that concept class C is PU learnable over the class W if there exist functions m (0, 1) X (0, 1) +
N, mamtab (0. 1) x (0,1) + N, and a PU learner A such that for all (e.5)= E (0, x (0, 1) and m0p (e, 5) and a > m (c, d), we have
distributions (D,P) E W ifb mc
CITD (A(SP, ,S")) 2 min crT + < SP~PiisS SU DD
Pr
aEC
We also say A PU learns C over W.
Notations: Given any set J and E N, let U, denote the uniform distribution over J. and define Jk = (Ci..... jk) Jı. Ik J), and [k] == (1, (1,...,ki k)..
Given family of distributions D over X' x (0,1) 1}. where w ranges over some parameter set, we respectively denote the marginal over X, the positive distribution, and the negative distribution of D., by D D.,.. and D D_
Let C be a concept class over X. Define CAC == {c c, c' E CJ. Moreover, denote the best clas- sifier as c* == arg minleee (c), and mitleec (r) as the approximation error. Furthermore, for a function e : X > {0, 1} and distribution D over X' {0, 1}, define the false positive rate as (c) = Pra-D, (a(x) * 1], and the false negative rate as errā(e) == PrawD [o(x) * O]. Given subset B C X, define CnD B == n B c E C). Moreover, for a multiset (21,22,... _m) E X", define Domain(S) = {x x E S}. Define the restriction of S to B denoted by S B as the subsequence of elements T; S such that 2; B.
3 Analysis of Realizable PU Learning -SCAR setup
In this section, we study PU learning under the realizability assumption in the SCAR setup. It is already known that every concept class with finite VC dimension is PU learnable in this setting Lu all (2002). We begin by establishing lower bounds on the sample complexity. In particular, we provide lower bound on the sample complexity of positive examples that nearly matches the upper bound established by Luu Liu all (2002).
Theorem 1. Let C be a concept class with VC dimension d 2 2 over the domain X. There exists M 1 such that for any number of positive samples upper bounded by b S M [d+mm1188) and
for every number of unlabeled samples a E N. (s E (0, x (0, 1), and PU learner A there is distribution D realized by C over x {0, 1} such that Pr DD St SDD [CTTD(A(SP)) SSU) 2
8.

---

Next, we provide lower bound for the sample complexity of unlabeled samples with respect to combinatorial parameter we call claw namber. Claw number formally defined in the following. As mentioned in Remark 21 claw number is always smaller than VC dimension.
Let C be concepi class over domain X. We define claw number of to be the largest h E such that for every m 2 h, there exists a B S X with [B] = m such that {O C B |0]
Definition 2.
m b} _ B. no such h exists, we say the claw number C is O.
Remark 2. Claw number of a class is always less than or equal to VC dimension. This is because for every B S X with [B] 2 2h we have VCD((O S B |10 |B| b)) 2 h.
Theorem 3. Let C be a concept class with claw number h 2 1. There exists M > 1 such that for any number of unlabeled samples upper bounded by a S M (b+ln[1/6) and any number of positive samples E N, (e, d) E (0,1) x (0, 1), and PU learner there is a distribution D realized by C over X {0,1] 1) such that Pr gr ,8" DDx [eTTo(A(S?, SS 2 = 6.
Note that eee all (2025) showed that no concept class C with VCD(Cn) oo (where Cn is defined below) is realizably PU learnable in the SCAR setup without access to unlabeled examples. Note that VCD(Cn) is also studied as the slicing dimension Kivinen (1995) and as the 1-centered star number in Hanneke (2024). The following proposition shows that Theorem Bl extends the results of Lee et all (2025) by demonstrating that not only do positive examples alone not suffice when VCD(Cn) co, but there also exists concrete lower bound the number of required unlabeled examples.
Proposition 4. For concept class C, let Cr == {nEE e finite A CCJ. Then VCD(C,) = oo if and only if the claw number of least 1.
We then restate the Theorem of Liu all (20012) in Corollary & providing an alternative proof based on the notion of e-nets, which we formally define below. Our proof also leads to new results for the SAR and PCS setups, presented in Section
Definition 3 (e-net), Let X be some domain, B C 2 a collection of subsets of X and Qx a distribution over X. An e-net for W with respect 2x is subset N C X that intersects every member of B that has @x-weight at least E.
Let us also elaborate on the learning algorithm Lau et all (2002) introduced, appearing in (.). Note that (I)) simply selects the concept with the fewest number of is over S among all concepts con- sistent with SP In this sense, it can be seen as counterpart to empirical risk minimization in the PU learning setting. We therefore refer to any concept returned by (II) a positive empirical risk minimizer (PERM).
argmin (S |cl s
(1)
Lemma 5. Let C be a realizable concept class with VC dimension d over domain X. Let S be sample i.i.d. drawn from Dx and T E X be an e-net for CLC on D such that Domain(T") C c² Denote cPU == argmin Domaaie(ee |c S). Then there exists a M > such that if
|S|> M (d1m(1/))-1((46)) then with probability 1 - 26 we have errp(c < 14s.
Corollary 6. [Theorem I of Liu (2002)) Let C be concept class with VC dimension d over the domain X. Let W set of duos (D,D+) such that D is realized by C. Then is PU learnable over W with sample complexity pos (e, 6), m yntabell (e, = O dlm(1/c))+o(118)
Proof. For fixed constant M, long as > M (CDD)CA)))((11))+))
we have that S'P
with probability 1 5 5 is e net for C/C on D, (e.g.. see Haussler and Welz (1987)). Since (it can be shown similar to the manner claim of Ben-David and proved), combining this with Lemma El completes the proof.
VCD(CAC) < VCD(C)
Liman (198))
5

---

4 Analysis of Realizable PU Learning -Beyond SCAR
In this section, we study PU learning under the realizability assumption when positive examples are sampled from a distribution P which can differ from D+. Throughout this section we consider distributions D with deterministic labels, i.e., D(y a) always zero or one for every x E X, and we define ((x) Dly = 1 .) to be the labeling function. We study two classes of distributions for sampling positive examples P:
(i) Selected at random (SAR): For any distribution e over X, define DA(A) = f (DD and P belongs
K = (De any distribution e over }}.
(ii) Positive covariate shift (PCS): P belongs to
1D {PI P(A) 0 if D+ (A) 0 and ((A) 0, A is measurable set)
Note that the condition P E K is equivalent to having P(A) = 0 when D (+(A) - 0 for any mea- surable set A, i.e., support of P being subset of the support of D4. Thus, K is generalization
of the previous case.
We begin by analyzing the simpler case where P Koyrr and then extend our results to the more general setting Kig Even when p belongs to X additional assumptions on P are required for the PU learning problem be well-posed. For example, consider the case where P is single point mass on a positively labeled instance. In this scenario, the PU learner would only observe one labeled example, rendering the learning task trivial and unsolvable. To avoid such cases, impose a common assumption when dealing with distribution shift: a bounded weight ratio between P and D+- The weight ratio is formally defined as follows.
Definition 4 (weight ratio). Let B S 2x be collection of subsets of the domain X measurable with respect to both Qx.1 and 2x.2. We define the weight ratio of the source distribution and the target distribution with respect to B as
(A)
Rg (Qx.1, 2x.)= =
inf
AEB(X)
2x,²(A))
2x,2(A)#0
We denote the weight ratio with respect to the collection of all sets that are Q1 and Q2=mmasurabbe by R (1, 22).
Our sample complexity upper bound for the where P E Koyr is the direct implication of Lemma @ proven by Ben--avvid and Urner (2012), which we state below
Lemma (Lemma of [Bn== and Urnei (2)1)),. Let X some domain, C 2 a collection of subsets of X, and Qx,1 and Qx distributions over X with R := Ry (x,,1, 2 0. Then every Re-net for B with respect to Qx,1 is an e-net for B w.r.l. 2x.2-
Theorem 8. Let C be concept class over domain X with VC dimension d and r E (0, 1). Let W be
set of duos (P, D) such that D is realized by C, P E Ka and Reac (P, D+) T. Then PERM algorithm (II) PU learns C over W with sample complexity m myndabel (5,5) 0 [Il((//))
and m pas 6) = 0 ( (dln(1/re)+I((11A))
Next we derive a nearly tight lower bound for the sample complexity of positive examples when P E ICyer and R (P, D+) zr.
Theorem 9. Let C be a concept class over domain X with VC dimension d 2 2 and r E (0, 1). There exists a M > 1 such that for any number of positive samples upper bounded by S. M [d+lm11/8)
and any number of unlabeled samples a E N, e E (0, x (0, 1), and PU learner A. there is distribution D realized by C over X x {0, 1} and a distribution P E Kaar such that R (P,D.) 2 (AIS SS) 2
and Pryp-p". .p... SD.
8.
The proof of Theorem E closely follows that of Theorem II (see appendix). Now, we can shift our focus to E 13000 Theorem IIα inspired by BBen-David P Keov no weight ratio assumption is sufficient for PU learnability, unless the total number
(2012) we show that for

---

of positive and unlabeled samples depends on the size of the domain. Therefore, similar to Ben
David and Umer (2012) in the cases where P E KT", in addition weight ratio assumption
we assume that the labeling function 1 is 7-mmarinn classifier w.rl. D, and D is realizable by C with margin ?.. These notions are formally defined the following. Moreover, we also assume that D[((x.)) E X has a constant lower bound (note that we are not assuming D[((2, 1): E H is known).
Definition 5 (realizable with 7 m-margin). Let X C CR, , DD be a distribution over X' x {0, 13 and : X + {0, 1} classifier. For all I E X, denote (x) as the norm-2 ball with radius y centered on x. We say that e is a y-margin classifier with respect to Dxx for all x E X whenever Dx (z)) > O then cly) = c(z) holds for all y, 2 E (x). We say that class C realizes 'D with margin if the optimal (zero-error) classifier c' is a "ymmrgiin classifier.
Note that function being "-margin classifier with respect to Dx is equivalent to c satisfying the Lipschitz property with Lipschitz constant 1/2ry on the support of Dxx
Theorem 10. Consider any finite domain X. There exists concept class Co,1 with VCD(Co,1) 1, such that for every PU learner A, and e and ō with 2$ +6 < 11/2, b, a E N such that the total number
of positive and unlabeled data is upper bounded by b+a < v 211-2(2:+51122 22, there exists dis- tribution D over X x {0, 13 with deterministic labels which is realized by Co, and P Kog where R(P: D+) = 1/2, D D[[(,, 1)= x E x3] 2 1/2 and "ppp"="""//p (ArF 2 e] 6.
The following theorem is inspired by Theorem 2 of Ben--avid and Urned (2012), which establishes lower bound on sample size for infinite domains under the additional assumptions that the labeling function is X-Lipschitz and that DH{ 1) E X 2 1.2 As shown, even with these additional assumptions, the total number of samples must be at least exponential in the Lipschitz constant. This can be viewed as the additional cost incurred when P E KKD".
Theorem 11. Let X' = =0, There exists a concept class Co.1 with VCD(Co.1 = 1, such that for every PU learner A, and E and 8 with 22 + 5 < 1/2, b. a N such that the total number of positive and unlabeled data is upper bounded by b+ a < 2(144)((12
2, there exists a distribution D over X (0. 1) with deterministic labels which is realized by Co.1 and 'P E Kogo where C(P, = 1/2, (x 1) : x E xX] 2 1/2 and l a X-Lipschitz labeling function and Prgp-pt,su St DDx (e So) 1 > 66
3
Next, we present Algorithm M. designed for the case where P E KC The algorithm is inspired by the domain adaptation method introduced in Dand and Umerr (2012). In the standard domain adaptation setting, the goal is to minimize the error with respect to a target distribution Qr, given labeled samples from source distribution 2s and unlabeled samples from Qr.
Algorithm II adapts this approach to the PU learning setting, with 2s = P and Ωr = D+ (with labels being 1). However, unlike domain adaptation, PU learning lacks access unlabeled samples from 2:: instead, it only has access to unlabeled samples from Dx. To account for this difference, two key modifications are made to the algorithm from Ben-David and Urned (2012); (i) Instead of using a sample 7' from D+, Algorithm 0 uses the unlabeled sample SO drawn from Dx; (ii) The algorithm outputs a PERM rather than an ERM.
Notice that in Theorem respect to 1/7 (as it was required for the total number of samples to be exponential with respect to the Lipschitz constant in our lower bound appearing in Theorem ID.. However, in many learning scenarios, unlabeled data is abundantly available while labeled data is difficult to obtain, which makes this algorithm more practically appealing.
we require the number of unlabeled samples to be exponential with
Theorem 12. Let X [0, 1]th 7 0 a margin parameter. n, >> 0 and C be a realizable concept class with VC dimension d < ca. Let W to be the set of duos (P,D) such that:
P E Keov, D is realizable by C with margin y and has deterministic labels, and D(y 1) > n.
The labeling function 1 is a 7y-margin classifier with respect to Dx.
* Rı (P,D+) 21 r for the class I = (CAC) 7B, where B is partition of 10, 11th into boxes of sidelength V/V
7

---

Algorithm 1: Algorithm for PU learning in the positive covariate shift setup
Input: SP ii.dd. sampled from P with label and an unlabeled i.i.d. sample S from Dx and a margin parameter y.
Partition the domain [0, 1] into a collection B of boxes (axis-aligned rectangles) with
sidelength (7/vk):
Obtain sample S" by removing every point in SP, which sitting in box that is not hit by S st
return
Then Algorithm @ PU learns C over W with sample complexity
me (c, = dln (1/(r(1 (1/(r(1-=)))) =)=)) Im(11/))
72(1 6)
unlobel (c, =0 (VK/7)** in ((V617)+10) dln(1/e) + (1/6)))
me
RE
5 Analysis of the Agnostic PU Learning
In this section we analyze agnostic PU learning. It is already known that with the knowledge of class prior a, every class with finite VC dimension is PU learnable Du Plessis et all (2015) in the SCAR setup. In Section [ we derive nearly matching lower bound on both the sample complexity of unlabeled examples and positive examples to Plessis et all (2015) upper bounds. Then, we show that for concept class C with more than two concepts, without the knowledge of ax, no PU learner- without access a-can achieve error less than max(a,1-a) times the approximation min(a,1-a) in the SCAR setup (which makes the PU learning task impossible). Furthermore, in Section 5.2 we complement this result by showing that for every concept class, there exists algorithm whose max((a.1a)) times the approximation error in the SCAR setup. Finally, we derive generalization bounds for settings where S is drawn from an arbitrary distribution P.
error is arbitrarily close to min(a,1-a]
5.1 Lower Bounds -SCAR setup
The following theorem provides an almost tight lower bound on the sample complexity of both positive and unlabeled examples, assuming the learner knows that = 1.- We prove this theorem by reducing problem called the generalized weighted die problem, which is problem inspired by Ben- David and David () Detailed Proof of the theorem is deferred to the appendix.
Theorem 13. Let C be a concept class with VCD(C) = d where d 2 4. Consider W to be the set of duos (D, D+) with D[[(x,)) 1) I X} 0.5. Then is PU learnable over W with munlabel (c, 8), m pos (e, 8) Ω (d+lu(1/0) and m munlabel (c, 8), m (e,
sample complexity m
dd dln((1/e)4n((1())
Next, we present lower bound on the generalization of PU learners for the cases where is un- known.
Theorem 14. Let C be concept class over X containing least distinct concepts. Then, for every E 1), any number of positive samples E N, any number of unlabeled samples a E and PU learner A. there exists a distribution over X x {0, 1) with {n. 7) where = Di[(1, 1): XH,, such that
max(a, 1 a) min(a, 1 (x) cEC
Pr SP SP.DR, SU SUNDS
errp (A(SP, (U),
min err = 1.
Proof. Let x any instance such that two concepts in C disagree on its label. Define distribution Do over X x {0, 1) to assign probability 7 (z, 1) and 1 77 over (z, 0), and D == 1 - Do. Then

---

for any 2 E {0, we have mingec errp, (c) = min(n, 1 77) and D+.; Dx,= 1 (n)- Thus, for any b, E N and Sf , SU D there exists {0, 1 such that errp, (A(SP, ,))) max(n, 1 7). This completes the proof.
Remark 15. Our poof also demonstrates that, even when the approximation error is known, al- most no concept class is PU learnable. This finding is particularly noteworthy because agnostic PU learning with known approximation error can be viewed as a relaxation of the realizable PU learning setting.
5.2 Upper bounds
We start by proposing an algorithm for agnostic PU learning that, for a given 7 > 0, outputs a concept which minimizes the Lagrangian PU empirical loss eir? C - IR220 defined as
ce s
|
SPI
efr (c)
+
(2)
ISU
SP
[ [80T
Note that the PERM algorithm minimizes
while assuming that the empirical error of e (for
|
[SP] is the empirical error on S", this algorithm can also be viewed as Lagrangian function for the PERM algorithm. Also, notice that when 7 = 2a, eir" will be equivalent to the surrogate loss introduced Plessis et all (201S) when the loss function is the zero-one loss. We begin by analyzing the SCAR setup.
realizable concept classes) is zero on SP. Since
Theorem 16. Let C be any concept class over domain X with VC dimension d, and let P D.. Given any 7 2 a, denote e. argmmin eîr" (c). There exists M > 1 such that for all c E C, if |S Ad(d+ln(1/8)1 then with probability 46 we have
crrD(c max (~==: 1a'-a (erro(c) 2(1 + +7))
Let's also suppose as prior knowledge we have access to â a where 2à 2 Then one can incorporate the prior knowledge by setting ? 2ô. In particular, if was known with 20, would have eer PU S eer 6s. This is consistent with Du Plessix all (2013) results for cases where the class prior is known.
Remark 17.
The following corollary is direct consequence of applying Theorem IG with 7 = 1. Corollary 18. For any concept class C with VC dimension d, there exists PU learner A and constant M 1 such that for every a, E 1) and for all b, > Aldd-1((1/0) and for any distribution over X x {0, 1} with Di((z, 1) : x E X)] = a, the following holds: for any sample S of size drawn i..dd from D+ and any sample S of size drawn i.i.d. from Dx, with probability at least 1- -8. 8.
errp (A(SP, (U)) < max(a, 1- a)) min(a, ax)
min mninerr(()) oEC
+
Finally, we examine the most general PU learning setting. We derive generalization bounds that hold for arbitrary concept classes and any distribution P by combining Theorem IIA with Ben-David etal (2010) results. These bounds involve the CAC distance, which we formally define below.
Definition 6. Kifer et al. (20044 Given domain X' and a collection B of subsets of X, let Qx,1, 2x be probability distributions over X, such that every set in B is measurable with respect to both distributions. The B-distance between such distributions is defined as
dg 1xx11 2x sup
Pr Qx.1
[
Pr [ 2x
BEB
Theorem 19. Let C be any concept class over domain X with VC dimension d, and let P be any arbitrary distribution. Given any & 2 a, denote PU argmin eir" (c). There exists M 1 such that for all c C, if | > M(d+lm(1/6)) then with probability 1 - 45 we have
(7-a a 7 -a Where XP == min.ec (c) + eerp(c, 1)) and errp(c,)) = Præ-o(c(z) #1).
errp (c PU < max
(erro(c) + 2(1 + + + 27 (XP denc(P.D.

---

Conclusion
In conclusion, this work studies the sample complexity of PU learning in both realizable and ag- nostic settings, covering the SCAR setup well as more general scenarios. We provide theoretical guarantees finite sample complexity. Our results extend the existing literature by relaxing several restrictive assumptions that were made in previous publications, and by proving lower bounds on required sample sizes.
Acknowledgments and Disclosure of Funding
We thank Sandra Zilles and Alireza Fathollah Pour for helpful discussions during the development of this work, and the anonymous reviewer for pointing out the notions of slicing dimension and 1-centered star number.
References
Anthony, M. and Bartlett, P. L. (2009). Neural network learning: Theoretical foundations. cam- bridge university press.
Bekker, J. and Davis, J. (2018). Estimating the class prior in positive and unlabeled data through de- cision tree induction. In Proceedings of the AAAI conference artificial intelligence, volume 32.
Bekker, and Davis, J. (2020). Learning from positive and unlabeled data: A survey. Machine Learning, 109(4):719-76..
Bekker, J., Robberechts, P., and Davis, J. (2019). Beyond the selected completely at random as- sumption for learning from positive and unlabeled data. In Joint European conference on machine learning and knowledge discovery in databases, pages 71-85. Springer.
Ben-David, S. and Ben-David, S. (2011). Learning classifier when the labeling is known. In International Conference on Algorithmic Learning Theory, pages 440-451. Springer.
Ben-David, S., Blitzer, J., Crammer, K., Kulesza, A., Pereira, F, and Vaughan, W. (2010). theory of learning from different domains. Machine learning, 79:151-177
Ben-David, S. and Litman, A. (1998). Combinatorial variability of vapnik-chervonenkis classes with applications to sample compression schemes. Discrete Applied Mathematics, 86(1):3-25.
Ben-David, S. and Urner, R. (2012). On the hardness of domain adaptation and the utility of unla- beled target samples. In Algorithmic Learning Theory: 23rd International Conference, ALT 2012, Lyon, France, October 29-31, 2012. Proceedings 23, pages 139-153. Springer.
Blanchard, G., Lee, G., and Scott, C. (2010). Semi-supervised novelty detection. The Journal of Machine Learning Research, 11 11:2973-3009.
Christoffel, M., Niu, G., and Sugiyama, M. (2016). Class-prior estimation learning from positive and unlabeled data. In Holmes, G. and Liu, T.-Y., editors, Asian Conference on Machine Learning, volume Proceedings of Machine Learning Research, pages 221-236, Hong Kong. PMLR.
Coudray, O., Keribin, C., Massart, P., and Pamphile, P. (2023). Risk bounds for positive-unlabeled learning under the selected at random assumption. Journal of Machine Learning Research, 24(107):1-31.
Dai, S., Li, X., Zhou, Y., Ye, X., and Liu, т. (2023). Gradpu: positive-unlabeled learning via gradient penalty and positive upweighting. In Proceedings of the AAAI conference on artificial intelligence, volume 37, pages 7296-7303.
Du Plessis, M., Niu, G., and Sugiyama, M. (2015). Convex formulation for learning from positive and unlabeled data. In International conference on machine learning, pages 1 1386-1394. PMLR.
Du Plessis, M. C. and Sugiyama, M. (2014). Class prior estimation from positive and unlabeled data.
IEICE TRANSACTIONS Information and Systems,
10

---

Elkan, C. and Noto, K. (2008). Learning classifiers from only positive and unlabeled data. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 213-220.
Feller, W. (1991). An introduction to probability theory and its applications, Volume 2, volume 81. John Wiley & Sons.
Gong, C., Wang. Q., Liu, T., Han, B., You, J., Yang. J., and Tao, D. (2021). Instance-dependent pos- itive and unlabeled learning with labeling bias estimation. IEEE transactions on pattern analysis and machine intelligence, 44(8):4165 (118))46634444 -4777
Hammoudeh, Z. and Lowd, D. (2020). Learning from positive and unlabeled data with arbitrary positive shift. Advances in Neural Information Processing Systems, 33: 13088-1309.
Hanneke, S. (2024). The star number and eluder dimension: Elementary observations about the dimensions of disagreement. In The Thirty Seventh Annual Conference on Learning Theory, pages 2308-2359, PMLR.
Haussler, D. and Welzl, E. (1987). -nets and simplex range queries. Discrete & Computational Geometry, 22211177-51.
He, Liu, T., Webb, G. I., and Tao, D. (2018). Instance-dependent pu learning by bayesian optimal relabeling. arXiv preprint IrXiiv:8088.000 02100.
Hoeffding, W. (1994). Probability inequalities for sums of bounded random variables. The collected works of Wassily Hoeffding, pages 409-426.
Jain, S., White, M., and Radivojac, P. (2016). Estimating the class prior and posterior from noisy positives and unlabeled data. Advances in neural information processing systems, 29.
Kato, M. and Teshima, T. (2021). Non-negative bregman divergence minimization for deep direct density ratio estimation. In Meila, M. and Zhang, T., editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5320-5333. PMLR.
Kato, M., Teshima, T., and Honda, J. (2019). Learning from positive and unlabeled data with selection bias. In International conference on learning representations.
Kelly, B. G., Tularak, T., Wagner, A. B., and Viswanath, P. (2010). Universal hypothesis testing in the learming-limine regime. In 2010 IEEE International Symposium on Information Theory, pages 1778-1482. IEEE
Kifer, D., Ben-David, S., and Gehrke, J. (2004). Detecting change in data streams. In VLDB. volume 4, pages 180-191. Toronto, Canada.
Kivinen, J. (1995). Learning reliably and with one-sided error. 2812)1141-12.
Mathematical systems theory,
Kumar, P. and Lambert, C. G. (2023). Positive unlabeled learning selected not at random (pul- snar): class proportion estimation when the sear assumption does hold. arXiv preprint arXiv:2303.08269.
Lee, J. H., Mehrotra, A., and Zampetakis, M. (2025). Learning with positive and imperfect unlabeled data. arXiv preprint arXiv:2504.10422,
Li, W., Guo. Q. and Elkan, C. (2010). positive and unlabeled learning algorithm for one- class classification of remote-sensing data. IEEE transactions geoscience and remote sensing, 7972)27
Liu, B., Lee, W. S., Yu, P. S., and Li, X. (2002). Partially supervised classification of text documents. In ICML, volume 2, pages 387-394. Sydney, NSW.
Liu, T. and Tao, D. (2015). Classification with noisy labels by importance reweighting. IEEE Transactions pattern analysis and machine intelligence, 4474)444-441.
11

---

Motwani, R. and Raghavan, P. (1996). Randomized algorithms. ACM Computing Surveys (CSUR), 28(1)333337
Na, B., Kim, H., Song, K., Joo, W., Kim, Y.-Y., and Moon, I.-C. (2020). Deep generative positive- unlabeled learning under selection bias. In Proceedings of the 29th acm international conference on information & knowledge management, pages 1155-1164.
Niu, G., du Plessis, M. C., Sakai, T., Ma, Y., and Sugiyama, M. (2016). Theoretical comparisons of positive-unlabeled learning against positive-negation learning. In Lee, D., Sugiyama, M., Luxburg, U., Guyon, I., and Garnett, R., editors, Advances in Neural Information Processing Systems, vol- ume 29, Curran Associates, Inc.
Ramaswamy, H., Scott, C.,, and Tewari, A. (2016). Mixture proportion estimation via kernel em- beddings of distributions. In International conference on machine learning, pages 2052-2060.
PMLR.
Sakai, T. and Shimizu, N. (2019). Covariate shift adaptation on learning from positive and unlabeled data. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4838- 4845.
Scott, C. (2015). A rate of convergence for mixture proportion estimation, with application to learning from noisy labels. In Artificial Intelligence and Statistics, pages 838-846. PMLR.
Shalev-Shwartz, S. and Ben-David, S. (2014). Understanding machine learning: From theory to algorithms. Cambridge university press.
Slud, E. V. (1977). Distribution inequalities for the binomial law. The Annals of Probability, 5(4):404-412.
Tate, R. (1953). On a double inequality of the normal distribution. The Annals of Mathematical Statistics, 24(1):132-134.
Yang, P., Li, X.-I.., Mei, J.PP., Kwoh, C.-K., and Ng. S.-K. (2012). Positive-unlabeled learning for discase gene identification. Bioinformatics, 28(20):2640-2641
Zheng. S., SHEN, G., Jiao, Y., Lin, Y., and Huang, J. (2022). An error analysis of deep density-ratio estimation with bregman divergence.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide formal statements and proofs of contributions claimed in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
fine to include aspirational goals motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of our work are discussed in the introduction.
12

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specification asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex system might be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, the authors should discuss possible limitations their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Each formal statement begins with stating the premises under which it is claimed. Proofs not given in full in the main body are included in the appendix.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This is purely theoretical paper, without experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
13

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primanily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
This is purely theoretical paper, without experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so No an acceptable answer. Papers cannot rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
14

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: This is purely theoretical paper, without experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This is purely theoretical paper, without experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This is purely theoretical paper, without experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
15

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:///rrrr.....oo/a//ccaaaaaaa
Answer: [Yes]
Justification: This is a purely theoretical paper, without any anticipated harm or societal impact of any kind.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
We do not anticipate any broader socictal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (c.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our research does not involve data or predictive/generaiiee models, and does not pose any risks of the mentioned kind.
16

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswithcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer:
[NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
17

---

Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
Declaration LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs were not used as any non-standard, important, or original component of this research.
Guidelines:
The answer NA means that the core method development in this research does not involve L.Mss as any important, original, non standardd components.
Please refer to our LLM policy for what should should not be described.
A Useful Theorems
Lemma 20. Let Z be random variable such that Z E [0, and Pr(Z > e] S 8. Then E [2] < 76 + s(1 -8). 6).
Lemma 21 (Multiplicative Chernoff bounds Motwanı and Raghavan (196)). Let XI...., Xm be independent random variables drawn according to some distribution D with mean and support
included [0, 1). Then, for any y [o. 1]. - the following inequality holds for P = 1 Σ X;:
18

---

PD 2 (1 + 7)pl 3
P < (1- 1 mpy
Theorem 22 (Hoeffding Inequality Hoeftding (19944) ) Let X1, X1...., Xn be independent random variables such that a; Xi S by almost surely. Consider the variables,
S, = XI + ....4 Xn
Then Hoeffding's 's theorem states that, for all
21
Pr (1S,, - 2 S eexp
Ex (b, a,))
a,)²
Theorem 23 (Chebyshev's inequality Feller (1991))). Let be a random variable with bounded non-zero variance. Then for any h > 0.
Var[X]
Pr([X
E [ 2 k)) S
k²
Lemma 24 (Slud's inequality Slud (1977)). For S Bin(m, p) where Y and is an integer with mp < S mm1 p) then
mp
P
ZZ
m -
where Z ~ ((,, 1) is a normally distributed random variable with mean of and standard deviation 1f Lemma 25 (Normal tail bound Lale
195
For standard Gaussian random variable Z (0,
and x 2 0 we have
Plz 2 2 (1 v1 11-0-2
B Missing Proofs from Section
3
Let C be concept class with VC dimension d. 2 2 over the domain X. There exists a M such that for any number of positive samples upper bounded by S M (d+lm(1/6) and for every number of unlabeled samples a E N, (e, d) E (0,1) x (0, 1), and PU learner there is distribution realized by C over {0. 1) such that Pr SDD [eIrD(A(S? S")) 2
Theorem 1.
Proof. Proof of pos (e, 8) (()) We prove that for 2 9 we have po (e, 2000
d-1 Let
320002
B {I1, ..., ιaJ be a set size shattered by C, and e min
320006 0.0005) and = 2000s.
d-1
Denote B == B {æa), and for any O C B define Do over X x {0.1) be
Fa ,nd y O and y
Doll(r,V)))
(3)
x & O and y = 0 O.W.
Define Wa = (Do. O B). Note that for proving the claim it is enough to show
that for every PU learner A, there exists O* C B such that
Pr SPwDb
Terpoo (A(SP, ,S') 2
Do
500
19

---

Note that, for all 0,0' _ B we have Dx,0 Dx.o'. Therefore, for this set of distributions, the unlabeled sample does not help the learner, and doesn't affect the proof. Thus, for the sake of simplicity, we shorten A(S S to A(SP). Also, without loss of generality, we can assume that A always predicts on instance zdd-
From this point on for any sample S with Domain(S) B, denote $ == S { Next, define event E to be the event that [0] > d-1 and |S I d=1 Since maximum is no less than the average, we have
4
max E Sp OCB
eITDo (A(S*))]
EoL SP
(errDo (A(SP)))
B 2 SP (erTDo (A(SP)) E
Pr D
[E]
ONU 28 SP
We first derive a lower bound for PromU, (DOwU,B-e S..PPDD [b]. First, note that since O |O| Bin(d 1, 5) Thus, using the Multiplicative Chernoff bound, long d
U2e have
d - Promu,a 5 [1o|
1 (1-exp exp (- d 1111 )) > 0.3
(-1 16
(5)
4
Next fix any O C B with |O| 2 اله For every i such that x; E O,, and j E [b] let the random
variable Y be 1 if the jth sample drawn from D+.0 is x; and 0 otherwise. Note that Yı, is simply
a Bernoulli with parameter at least --1- Then, |SP|
Σ Eineo Σj=1 Yij- Therefore, using the
Multiplicative Chernoff bound (Lemma 21I for any y E 0, (d-1) - we have
Pr Swih
[|S (1+
se J:a-1f
bo1+101
Se 2pg
Set 1. Note that
d-1 Thus
165
Pr SwDe
S
d-
$ e 11 < 0.96
(6)
Combining (5) and (6) we derive that Prowu, 28 SP DD.
[E' > 0.012.
Next we try to derive a lower bound for Bo SP [errDo (A(SP)) | [.. Note that for
given SP,, due to symmetry for all O, O' C such that Domain 0, and |O| | have
we
Pr S S
Pr
[S SP
SwD4,
SNDD 4.0'
Moreover, it is clear that for O,0' C B such that Domain (S)) C 0,0' and |0| 2 |O'| we also have
Pr S= -S=$11
Pr
[S= SP]
S~Dh
SwD 1.0'
Next fix any S" with |S² < d-1 Since given fix SP. smaller O are more likely, due to symmetry
we can conclude that given event E, for every E B \ SP the probability of E O is at most } Moreover, note that for all |0] d-1 have
10 SP
d-1
B
SP
d-1
8"
Thus, again due symmetry, given event E for every x E B B/ SP the probability of x O is at least Thus, no matter what is A we have
B SP l
Eo nn SP
(errDo (A(SP)) E N
N 64
8(d 11-1) 1)
20

---

Combining this with (.), we conclude that there exists O _ B
0.012
B o.
[errpo. (A(SF))] > 64
>
0.001p
Note that since A always predicts the label of za to be 1, its error is always less than Therefore, using Lemma we derive
0.001p-2
Pr S SP 4.0*
(errDo- (A(SP)) 26
(p ()-
2000s
1
2000
Proof of me poe (e. 2 Ω [mnl//]))
Next, we prove that for every a N, s < 3.4 E (0,1), and PU learner A there is distribution D realized by C over X x {0, 1] such that
b In( 25
28
(erro (A(S", .S)) 2 2 5. Let B x2) S X' be any set shattered by C. For z {0. 1} and (x, E X {0, define and
Pr SP D
D2 over X' {0, 1] as
(=(((2,))) 1-E x x2 and
o.w.
Note that both Do and Dj are realized by C. First we try to derive lower bound for the probability that the sample SP Db doesn't 't contain 2 Note that, it is easy to see that the function f(a)
In(1-a) always has positive derivative for all a < Therefore, for all < 1 we have
In(1 - E) < 2 ln(2) < 2
Thus,
[1] $ 8 = 5)6 1i(1-2
28.
(7)
SPWDR
Thus since Pr D1
I $ SP 1. We derive
Pr =0(0.1) sD Su wD..
min
[errp, (A(S (AS)))s")))) 26]
(6)
2 min
Pr
[A(SP, S (x1) #2
sE(0,1) wD! SU.
2. min
Pr =E(0.1) SP-D
|SP = (02)"1 gUND"
Pr
[A((o)}" (5)) #z]
(8)
> 26 min
Pr =E(0.1) S ND
[A(tx2} ( (x11 x
28 min
Pr 1. S/ (x)) 0] ,1
[A(fz)]
Pr SUNDS
(5( = oj
SC DD
28
Where (i) due the fact that whenever the learner makes mistake at #i the error will be least e, and (ii) is due to the fact that Dx.0 Dx.1-
Theorem 3. Let C be a concept class with claw number 2 There exists M > such that for any number of unlabeled samples upper bounded by I M bb1n(11/)) and any number of positive samples b E N, (e, (0,1) (0, 1), and PU learner A there is distribution D realized by C over X x {0, 1} such that Prge-Di wDD (AISD(A(S? ( 2 E] >
é
21

---

muniabel (e,6)= 12 (1) First we prove that for every b, N, and PU learner A
Proof. Proof of m
there is distribution D realized by C over X {0, 1} such that
7h
1
Pr SP S DD
errD (A(SP, ,S)) min
2400
4800a
1000
Let E min 2400 4800g|
7h p 1200e and max [ a), bb, :)) h. Let B be any set
a),bb),,,
such that {O C B |0| - b) C C. For any O S B with |O| = h and any (2, E & {0,
we define the distribution Do over X {0, as
p/b (1 (1-p)) p)/(m h)
if x E O, and y
Do(((z.0))
if E B O, and y =
(9)
o.w.
Note that all such Do are realized by C. We prove our claim holds for one of Do. where O E V. Next, suppose learner predicts more than h + (m-ble instances of B to be negative. Then, since exactly h instances of B are negative in every distribution, the learner will predict more than (m-bbl positive instances of B be negative. Therefore, regardless of the distribution, its emro will be more than p. which is greater than the error of always predicting positive. Thus, without loss of generality, we can assume that the learner always predicts fewer than h (m-h)e negative labels. In the worst case, all of the negative predictions are over positive instances, in which case the enror will be less than
I-p
1-p
I-p
P 6. 9.6 h
b++ (m- 6)p 1 1-P
m m s (m - h)p 1- (1 (1-9) p) m - 3p
(1 (1-21 p)
where the inequality due to m 2 + In conclusion, without loss of generality, we can assume that any learner always incurs an error less than 3p.
Define V = to B
|0| = h). Note that [ =
m h
Since maximum is no less than the
average, we derive
max E Eg DD w SU.UND OEV 1
lerrDo ((SP,sS)))
E EgP D SU.DWDD
[erTDo (A(SP, ss
m h
OEV
Σ
Σ
EgunDa 0.0
(errDo (A(S ((S)))"))) s(")]]
m h
(m 6)5² OEV S"E(B)O)
(10)
m
b
Σ
E Dx.0
[oTTDo (A(SP, s5))]
b
mb DEV SPE(B\O)
h
Σ
Σ
Esa DD3
JerrDo (A(SP, (USP,,UU)) ,(U))]
3 m b
mn OEV SPE(BIO)
h
Where the last line is due to the fact that since m 2 b(6) + h. we have
b
h
b b- b) b
h
1
1
m
m
h
6
22

---

Next, for any SP E B define W(SP) = {0 C B SP |O| = 6), and notice that since \ 2 m we have [W(5
m - b
Therefore, using the fact that the average is
h
no less than the minimum, we derive
Σ
Σ
[orTDo (A(S", ,
BsonDs
m b m
3
OEV SPE(BIO))
h
E
Σ
BsUnDa [errDo (A(SP, SS))
(I1)
m -
m² SPEB' OEW(S")
h
1 min BO SPEB
[errDo (A(SP, ,5))
W(sP)
We fix any SP 0b, Furthermore, define event E to be the event that |S 0 S 9. The idea similar to Theorem is that, since E has a significant probability, we can lower bound [errDo (A(S", [A(S),S"))]] by conditioning on event as
EO-Uwish EgunDs
Eo~Uwis [Esu>DRo |errDo (A(SP, ((SP,)"))) ,
(12)
2 BonlWiss BSUnDz lerTDo (A(S", sS)) E
Pr SUNDA
[
Next, we try to lower bound Eo~Uw(s? [SU-DA (errDo (A(S",SU)) [ Fix any O E V,
notice that Dx,o(x) = (x,)(=)) the same for every x, x' E O. Moreover, Dx.o(x) = Dx.o(z') for every x, E B \ O. Therefore, for every St E B", and every 0,0' E W(SP) such that S 10 St |0, we have
Pr S S" E SwIe X.0'
Pr SwDR
[ St E].
Therefore, by fixing S Ba and any S with |S S h/2 which represents S O. can define
Psu.st == PrS-DD S SU EJ.
This fact gives away the idea of grouping all the O E W(SP) that have the same S O for fix S E B". Formally, we have
BoNu wisn)
EgenDs
[errDo (A(S", ,")) E]]
Σ
Pr
[S= St ElerTDO (A(SP, ,S
[W(SP))
(EW(SP) su
SwDR
X.
[W(S))
Σ
Σ
Σ
SNDA
Pr
S SU
E eIIDo (A(SP, (ASS,.50) ,S))
(13)
S'EB"
OSP
2.0
18']5h/2 (0=5'
Σ
Σ
Ps S'
errDo (A(SP, S
W(SP) EB
S'EB"
OeW(sP)
S8/1
s" (0=s'
23

---

Next, fixing any S E B" and any S" with |S'| < 6/2. Note that since the enror is always no less than the eтror restricted over B \ (SP USt"), we derive
E
erTDo )5))
OEW(s")
s Oms'
Σ
Σ
(o))== 1- (5")s) 0, -0,x=0,000
m
Oew(s") se ) s" 100=s
E
Σ
(BILAIS" (0)( (0)) - 1-P 1 (A(S* 0, $ 00)
m-h
(SPU()) (EW
S" O==s"
P 0051
Σ
Σ
USU (A(SSPSS , (x) 1}
6 B (8P (SP
REBU(SPUSE) (
S O=='
P \ (SP US UO]
H , (x) = 03
m b B (SP US
(14)
Where the last line is due to symmetry of WSP).. Next note that since |S S 2
have
10ys"
2 2
b
Moreover, since m 2 2(b + a) + h. we have
B (SP S UO)
a -
1
m h
m - h
2
Combining these facts with (I4), we derive
pL{A(S", (S(A(S",S)(z)) = 13 + +1 ()1(A (z)
0}
Σ
Σ OEW(S")
B USS)
S (0=s'
Σ
Σ
p
2
(15)
(S")
S s"=S"
Σ
P
2
(S"
$010==''
Where (i) due to the fact that p 2 Combining (L) and (15)
we derive
Eo~Uwaor
EgunDy SgunDDoo D2
erTDo (A(SP, ,S")
E
1
Psu S
Σ
2/
[(SP)
S W=
S'EB"
(S
|
S" O=
(16)
Σ
Σ
Pr
IS = 5
E
[W(P)
OEW(SP) 8 EB
SNDA
X.O
EONUU
EgtnDs
P
P
2
2
Next, we attempt to lower bound Prguwpy o
EE. Similar to the proof of Theoreom II using Multi-
To
1] we derive
plicative Chernoff bound (Lemma 21l for any 7 E
Pr gU-D
[|SU
10 2 (1 + yapp] Se u
24

---

We set y= 1. Note that since min
we get p min
[1
Thus, we get
2400 4800a
2 4a
Pr gu x
|su
|0
b
Se 0.93.
Therefore, PrsenDs DD 2,0
[ > 0.07. Combing this fact with (TI).
and (IG) we derive
max E
S.SuNDg 2.0 D SP
[eTTDO (A(SP, ,S )) 600 P
OEV
Thus, there exists a O E V such that BD .orm S0 -D x, error always less than 3p, and by using Lemma we derive
eerT (A(S))) >
600 Since the
7
6n0 /
Pr S
erTDo. (A(S)) 2 E]
S
~
(3p E)
3600
3599
1000
and this completes the proof.
Proof of me untabel () 52 (lu(//1). Next we prove that for every E N. 8 $. < 7.
In 1b)
and PU learner A there is a distribution D realized by C over X' {0,1) such that lerrD (A(SP, ,))) 2 _6] >
Pr SP SP-D"
Let m == 2(b+ a + 1). Note that since claw number is more than 1, there exists a B C X with size such that B \ {r} S C for all æ E B. For any C B and any (x' X' x {0, 1) we define the distribution D2 over x {0, 1] as
if x. and y
D D2 ,0H)
(1-c)
a' E B {x}. and =
(17)
(m-1)
O.w.
Note that all such D2 realized by C. is enough to show that
Pr Su A
eTTD (A(SP, ,s 2 >5
2
UU SP DD
Fix any B. Note that similar to the manner ( the proof of Theorem was obtained, for all
E < 2 we derive
Pr SD
Ix & S (1 =)
2ea 48.
(18)
Next, consider any positive sample S. and unlabeled sample S such that S doesn't contain at. Note that the probability of S and St is the same w.r.t. every D. such that E B (St U.)... We consider two cases based on the number of negative labels A(S 5t) predicts. We prove that for both cases the eтror of A(S SS") is more than with probability at least 1 Therefore, the probability that error of A(S", (()) )
least e would be more than
Prge DD.. [x+ $ S
= 6,
4
which completes the proof.
Case 1: AASSP, , has more than 2m + negative labels. Then, at least 2ms of them are not z", and subsequently, since & < the error is guaranteed to be at least
2m - E)
m
25

---

Case 2: A(SP, ) at most 2m + 1 negative labels. Note that, since = 2(6 + + 1), we have [B (S" US )| m + 1. Therefore, since & < A(S", ,S) predicts at least m ( 2s) 2 m positive labels over B (S UP). Therefore, since x² is drawn uniformly, with more than chance the label of x would be predicted positive, which indicates that A(S", ,S)) has more than e error.
Proposition 26. For a concept class C. let Cn == {N finite A CCJ. Then VCD(Cn) = co and only if the claw number of C is at least 1.
Proof. Only if side. Since VCD = oo, for every m E N, there exists a subset = {2 .... Im
that is shattered by Cn. Thus, for all i [m]] there should be a en C- such that on n B B [ This indicates that [xxx S Cn- Consequently, there should be a с E C such that cn C and I2 Since B\ { S G, in turn, implies that en Bxx3. Thus, (O C |0] m 1 S
C B, and therefore the claw number of C is at least 1.
If side: Since claw number is least 1, for every
N there exists subset B { .... Im+1)
such that for all E [m + we have Bx E C B. For every E [m + 1] define c; to be the concept such that C2 O B [x:))
Denote B = \ {Im+1}. Next, consider any S B we prove that there exists en E Cn that satisfies On n B = A, and this shows that B is shattered by Cn. This implies that for every E N we have VCD(Cn) 2 m, which completes the proof. When A = B define on == Gm+1, and we
derive on 0 B B. Otherwise, define := -iz,e G. It is easy to see on satisfies the desired
property.
O
Lemma 27. |Corollary Lf (2002)) Let C be a concept class with VC-dimension over X.
Let be an i.idd sample of size from a distribution Dx over X. There exists a constant M > such that in M [dlu[1/e)+bu(188) ) then for every c, E EC with probability 1 1 5 we have
(r(c()) # (x))))) 3 EEEE 1c(x)) + (x)) +
n
and
Exes (((x)) 1c(()) [z))) n Lemma 28. Let be a realizable concept class with VC dimension d over domain X. Let S be sample i.idd drawn from Dx and T E X be an e-net for CAC on D+, such that Domain(T) C c². Denote PU == argmin Domain(T)Cell |c S). Then there exists a M > 1 such that if |S|> > M (2lb(1/e)- then with probability 1 - 25 we have (rr S 14c.
3Pr (c(x) cx))
Proof. Proof of this theorem was extracted from Theorem 1 of etal (2002). First, note that according to the definition s for any such that T' C we have that
Pr(c(z) = 0, y 1) S err S.
(19)
Note that since T C c", have PU ||| < c S). Thus.
1c PU no
S| |c PU net S |e S
Therefore,
10 PU not
|S| |c S - le Pu
PU ||]
(20)
IC nct |
From Lemma DT it can be deduced that there exists a M > 1 such that long as M dln(1/c)- with probability 1 - we have
|S] >
PU 5 net |
[S] <
1, 1))++ +
(21)
26

---

Similarly long as |S| 2 M
[2lo(1/)+(l((/81 with probability 8 have
5
Pr(c" = 0, PU (x) = 1)) 3 Pu net
+
(22)
[S|
Combining 20
and (22) with probability 1 - 26 we have
Pr(c (ι) 0, c PU
(x) 1) s (x) 0, 0. (z) 1) + 42
(23)
(
S 13c
Where (i) is due to (19) and Pr(c' y) 0. Thus combining (19 and (23) and the fact that
Pr(c" (x)) # y) = 0 with probability 25 we derive
err (C) = Pr(cfU (x) (x))
P 0, c PU (x) = 1) + (r(c'(x) = 0, PU (xx) = 1)
S 14x.
Which completes the proof.
C
Missing Proofs from Section
Theorem 8. Let C be concept class over domain X with VC dimension d and (0,1). 1). Let W be
a set of duos (P, D) such that D is realized by C. P E KGD and Rese (P,D+) 2 r. Then PERM
algorithm (I) PU learns C over W with sample complexity me uunaabel (5, = 0 (d (ln(1/))+
and m (E, 6) = (
75
Proof. As mentioned in Corollary B. it is well-known that as long as > M (dla(L/re++la(1/)) for a constant M, S is a re-net for CAC with respect to P with probability - 8. Using lemma D we derive that S is e-net for CAC with respect D+ with probability 1- 8. Moreover, we know ((A) = 0 for every measurable A that has (AA= = 0. This indicates that given any c* with err (ce almost surely we have SPP c². Plugging these into lemma E completes the proof.
Theorem 9. Let C be a concept class over domain X with VC dimension d 2 2 and E (0, 1). There exists a M 1 such that for any number of positive samples upper bounded by S M ddtm(1//8) Tg
and any number of unlabeled samples E N, e, E (0, (0, 1), and PU learner A, there is distribution realized by over X' x {0, 1} and a distribution E Kap such that R (P, 2r and Prgr~ph Pp, (ATED(A(SP, SS)) 2 E]
Proof. Let p 320e, B = (I1,-.., Ra} be any set of size d shattered by C, and denote B ==
BY \ {xa). Consider the set of distributions Warar-pee = (Doo, D+.o) : O C B}. as defined
in the proof of Theorem MI For each O C B, define distribution Po such that (o( v)))
r D+,o(((x, y)} for every x E and y E (0, 1), and assign the remaining probability mass of Po to the point (Id, 1). By construction, we have R(Po, D+.0) 2r.
Now define the set of duos p.d == {PPo, Do) I 1 S B}. By denoting p' := 320er, it is easy to see that PU learnability over Waar is equivalent with PU learnability over Wyscarpos Consequently, p'
from the argument in the proof of Theorem II for 9 the number of positive examples required
by any algorithm that PU learns C over Wear must satisfy
d-1
pos mc (E, 319
512er
For d 2 2 an identical argument also gives
In (1/8
m
pos
(E, >
2re
This completes the proof.
27

---

Theorem 10. Consider any finite domain X. There exists a concept class Co,1 with (CD(C 1, such that for every PU learner A, and E and 6 with 2 +6 1/2, b, a E N such that the total number of positive and unlabeled data is upper bounded by b+a < 201 21-2(2++6)j22 22, there exists dis- 3
tribution D over X {0, 13 with deterministic labels which is realized by Co.1 and P KKB" where R(P: P+) = 1/2, D[[(2, x E x3]] 2 1/2 and Prom=pt,s"~DY [errD(A(SP, ,5 2 6.
We obtain our lower bound by reducing the following problem to the PU learning problem:
The Left/Right Problem. We consider the problem of distinguishing two distributions from finite samples. The Legh/Right Problem was introduced in Kelly et all (20I0):
Input:
Three finite samples, L, R and M of points from some domain set X.
Output: Assuming that L is an i.i.d. sample from some distribution P over X, that R is an i.i.d. sample from some distribution Q over X, and that M is an i.i.d. sample generated by one of these two probability distributions, was M generated by P or by Q?
Lower bound for the Left/Right problem: We say that (randomized) algorithm (6, 4, r, m -sooleess the Left/Right problem if, given samples I., R and M of sizes 7, r and m respectively, it gives the correct answer with probability at least - 8. Lemma 1 of Dev- and Urner (2012) shows that for any sample sizes I, r and m and for any < 1/2, there exists a finite domain X' (1.2...... ................................ and a finite class Wimi of triples of distributions over X' such that no algorithm can (7, 1,, r, m)- solve the Left/Right problem for this class. In this class, both the distribution generating L and the distribution generating are uniform over half of the points X, but their supports are disjoint. More formally,
W UB, Uc): AUB (l,..., n) An 100.An=-0000 0, = [B) and C' = Ar C = B},
where, for a finite set Y, Uy denotes the uniform distribution over Y.
Lemma 29 (Lemma of Ben- and Umei (2012)). For any given sample sizes l for L, r for R and for M and any 0 < < < 1/2, if k = max + m, then for n > -Ik + 1) 27) no algorithm has a probability of success greater than 1 ? over the class Wyni
Reducing the Left/Right problem to PU learning: In order to reduce the Left/Right problem to PU learning, we define a class of PU learning problems that corresponds to the class duos Wuni for which we have proven lower bound on the sample sizes needed for solving the I Left/Right problem. Let X' be some domain of size n. Let Y be the first n/3 elements of X' and Z to be the next 2n/3 elements of it. Let CO {co, C1) where C1 X and co = Z. Clearly VCD(Co.1) = 1. We define Were to be the class duos (P,D). where D is a distribution with a deterministic label such that Dx is uniform either over Y U or Y U (Z) J) for some uniform subset J of Z of size n/3,, and I assigns points in J to 1 and points
Z)J to O, and P is uniform over Y U J. Notice that P E Kee Note that always either have R(P, D+) = 1/2 R(P, D+) 1. Moreover, since the label of Y is always 1, Di 1) x E X'} 2 1/2. Furthermore, for all (P, P)D in W
min (r) =
cECo.1
for all elements of Weon
Lemma 30. Consider any 8, E N. The Left/Right problem reduces to Domain Adaptation. More precisely, given a number n, suppose there exists a PU learner A such that for all (P, PPD) E 3n/2 b 2 s and a 2 t satisfies
Ega -S DD. [errD(A S 2 228 28
Then, we can construct an algorithm that (22 8, s, s 1)- the Left/Right problem on Wimi
Proof. Assume we are given samples L = f 12,,,,,,,,,44 1,} and R = (ri, r2........ rrs } of size s and a sample M of size 1+1 1 for the Left/Right problem coming from triple (U,,UB, Uc of distributions in Wunn. Then consider any set Y of size n/2 distinct from A and B. We create the set 1s in the following manner. Initiate 1 = Ø. Keep flipping an unbiased coin until of them are head, and each time the outcome of the coin was tail sample a ~ Uy and add it to 1 Similarly, initiate 7P Ø, and keep flipping an unbiased coin until s of them are head, and each time the outcome of the coin was tail sample a ~ Uy and add it to P..
28

---

We construct an imput to PU learning problem by setting the unlabeled sample S M {p) 15 where p is point from M chosen uniformly random, and setting the positive sample S RUIP Observe that |S$| 2 and | 2 I. These sets can now be considered as an input to the PU learning problem generated from a sampling positive distribution P UYuB, and distribution 'D such that Dx equal to UYuA or to Uy (depending on whether M was a sample from UA or from UB with labeling function being ((x) = if æ E A and l(x) = 1 if x E U B. Observe that we have R(P, D+) = 1/2 or R(P,D+) = 1, and minegCs,, er) = 0, and (P, P) E 3n/2" The algorithm for the Left/Right problem then outputs UA if c(p) = 0 and
Denote c = A UB if c(p) 1. Note that errD (c) I with confidence 5. Thus, CITUM 2g with confidence 1- 6. Therefore, the algorithm is correct with probability at least 25 +
Proof of Theorem T Combining Lemma Bill and Lemma PA we conclude that there exists no A such that for all (P, D) Sn/2 satisfies
B Su (ArT .S") 2 $] S
unless b b+o 2 ((1 - 2(25 + 8))n - 2, which completes the proof.
Theorem 11. Let X = [0, There exists concept class Co.1 with VCD(Co.1 1, such that for every PU learner A, and e and with 2E + 5 1/2, a N such that the total number of positive and unlabeled data is upper bounded by + a < V - 2(1+)))(1 2(0+A)(1-2(22460) - 2, there exists distribution D over X' (0. 1) with deterministic labels which is realized by Co.1 and P Ke where C(P, D+) = 1/2, Da, 1): x E X)) 2 1/2 and I is a X-Lipschitz labeling function and Prgp=pusse DD2 (A SU) 22 E > 6.
3
Proof. Let S X be the points of grid in [0. 1] with distance 1 1/A. Then we have |J 1)*
Then the class W3 contains all duos (P. D). where the support of P and D is J. D has deterministic
labels and is realized by CO and P Koom C(P, D+) = 1/2, and D[[ 1) : E X}] 2 1/2, with any arbitrary labeling functions : : + {0, 1}. as every such function is X-Lipschitz. As J is finite, the bound follows from Theorem III
Theorem 12. Let X = (0. 11t 7 > a margin parameter, n, r > O and be a realizable concept class with VC dimension d < co. Let W to be the set of duos (P, D) such that:
P E KCp", D is realizable by C with margin r and has deterministic labels, and D(y 1) m.
n.
The labeling function 1 is ry-margin classifier with respect to Dx-
Ru (P,D+) 2 r for the class I (CAC) BB, where B is partition of [0, 1 into boxes of sidelength 7/ kk.
Then Algorithm 0 PU learns C over W with sample complexity
m (5, = ( d (1/(m(1==)e) + In(1/8)
,² - =)
unnobel (c,ō)= (V///T)* In ((Vk/7)+16)
dlI((1/e) + ln(10))
m
ne
Proof. Let 0 and 8 > O be given. We set g' e/28 and 8' 5/6 and divide the space X' up into heavy and light boxes from B. by defining a box A E B to be light (A) < e = <'/(vV//n)* and heavy otherwise. We let x denote the union of the light
boxes and x the union of the heavy boxes. Further, we let Pr. and D4.h denote the restrictions of the P and D4. to Xh, i.e. we have (A) = P(A)/P (2*) and (A) = D4 (A)/D+ (x²) for all A C 2 and (A(A) = (+) 0 for all A & xh. As |B] (vk/>)* we have
29

---

D+ (2 2 1 11--- e' and thus, P ((x)) 2 r1 111--) We will show that
Claim 1. With probability 1 1- 8' we have S hits every heavy box (Similar to claim of Theorem 3 of Ben--Davd Urnei (2012)).
Claim 2. With probability at least 1 - 28' the intersection of S and X is an s'-net for CAC with respect to D4,1 (claim 2 of Theorem of Ben-David and Urner (2(12)).
To see that these imply the claim of the theorem, let Shh = S 2 denote the intersection of the source sample and the union of heavy boxes. By Claim St hits every heavy box with high probability, thus Shh [ 5", where S' is the intersection of S with boxes that are hit by S (see the description of the algorithm A). Therefore, since 5h an n't for C&C with respect to D+.h, then so is S". Hence, with probability at least 1 35' = 6/2 the set 5' is an e'-net for CAC with respect to D- Now note that an net for CAC with respect to D4,6 an 2e'-net with respect to D4, as every set of D+-weight at least 25' has D+, weight at least e', by definition of X and D+.A-
Next, let c* E C denote the 7-margin classifier with (rr = O. We show that SP C Note that every box in B is labeled homogeneously with label 1 or label 0 by the labeling function as I is a y-margin classifier as well. Let 8 E S' be a sample point and A, E B be the box that contains As c* is a 7-margin classifier and Dx (A.) > (A. was hit by S by the definition of S'), A, is labeled homogeneously by e* as well and as errp(c") = this label has to correspond to the labeling by I. Thus (s)s 1(s)
St. This means that S' S c*. According to Lemma 5 for some M 1 since S' S c* and M [dl((3/e)+lm(16))
for all
long as S' is e/ e/14-net
for CAC w.r.t D4, with probability 1 8/2 we have ecrp(c) S s. This completes the proof.
Proof of Claim 1: Let A be a heavy box, thus (A) e//|B], therefore Dx 2 e Then, when drawing an i.idd. sample 5 from Dx the probability of not hitting A is at most (1- (IT' (BB)) Now the union bound implies that the probability that there is box in 1h that does not get hit by Xy is bounded by
|B4) (1 - (T . E < [B] (1 - (TT e
|B|e a/11/
B (I
28( 28(VK//7)* In(O(V//>3//) then S will hit every heavy box with
Thus, if a 2 probability at least 8'.
Proof of Claim 2: Let 5h == SP 2h Note that, as SP is an i.i.d. P sample, we can consider Sh to be an i..dd Ps, sample. We have the following bound on the weight ratio between Pa, and D+,,
inf (A(A)
Ri (Ph, D+.i)= =
A (A)30
D4,a(A)
P(A) D+ (xt)
inf
AEI,D+. (A)>0 D+ (A) P (x(h)
D4 (x*)
2 (1 (1))
P P(X)))
where the last inequality holds D. (2 > (1 8') and P (2*) 1. Note that every element in CAC can be partitioned into elements from I, therefore we obtain the same bound on the weight ratio for the symmetric differences of C: Resc (D+,,, D ++.)) 2
e').
As we argued in Corollary B. is well known that there is a constant M > such that, conditioned on Sh having size least n' .M (im(1 r(-2')e
with probability least 1 8' it
is a (1 e')=''''' e'nne with respect to Pa, and thus an e'-net with respect to D+,h by Lemma A
30

---

Thus, it remains to show that with probability at least 1 - 8' we have |SM 2 n'. As we have P (x*) 2 r r1- (1),'), can view the sampling of the points of S and checking whether they hit X as Bernoulli variable with mean μ P (2*h)
(1 - 5'). Thus, by Hoeffding's in- equality (see Theorem 22) we have that for all & > O, Pr (u|sP) |sa 2 1|S S 2=2
If we set r' = r (1 - E'), assume 1S 2 2n and set t = /2/ we obtain Pr ([s*) < n') -
Pr (u|sP)-13 - | 2 =1511) Se -2
2(din(1/<r(1->)) +mm(1/8)) implies that e -7
Now |sP|2 2n' that 5th is an enet of CAC with probability at least (1 - -0)²² 2 1 - 28'
S 8' thus we have shown
o
D Missing Proofs from Section
Theorem 13. Let C be a concept class with VCD(C) = where d 4. Consider W to be the
set of duos (D, DD) with D[[(x, 1) : I E XH = 0.5. Then C is PU learnable over W with
sample complexity mynlabel
mc (E, m) m (E, 8) = Ω [+ln(1166) and m manlabel 6), m (E, =
O dll(1//))
We prove the theorem by reducing to a problem we refer as the generalized weighted die problem. This approach is inspired by Theorem I of BBnn and Ben-David (20II), in which a learning problem -refereed to as learning a classifier when a labeling is known (KICL)- is reduced to the weighted die problem.
In the weighted die problem, die has face that is slightly biased, and the goal is identify the biased face using m rolls. In the generalized weighted die problem, multiple faces of the die may be slightly biased, and the goal is identify all of them.
We now formally define the generalized weighted die problem. Before doing so, we introduce some necessary notation. For any k E N, define the set Vix := 2 {[k), 23.. Next, define two weighting functions w w : Vi + [0, 1] as follows: for any Vis with |O| I set
|0|
w (0) =1 and w x0))) = k - 0
and for |0] >
k 2. set
1 |0|
w (0)
and w (0))== :
Definition 7 (Generalized Weighted Die Problem). We define the generalized weighted die problem
with parameters k > 2 and æ E (0, 1) as follows. For each O E Vv suppose there is die with k faces, with probability of each face j E [k]] being
1-w (O)E
jE0
Poli) =
1 (0)s 140
K
The die O is rolled m times. A learner gets the outcome of these m die rolls, and its target is to output a h E {0, 1)*h which minimizes err(h) : i hy (0) (0) Eigo(1-hhh)) (0))
Theorem 31, Suppose the die O in the generalized weighted die problem with parameters k ' 32 and E (0, 1) is drawn uniformly at random from the Vv. If the number of rolls is at most l 1 then any algorithum for the generalized weighted die problem incurs error of at least 1 160
with probability greater than 320
Proof. Set m = k 1 Note that it multiplied by k. With an argument similar to Lemma 5.1 of Anthony and Bartleti (2009) and Theorem 2 of Ben-Davit and Bev-David (20I.), it is easy to see that the perfect learner Top predicts j to have positive bias iff the number of samples from j is bigger than m/k.
31

---

For sample roll drawn from Po define to be the output of Lo. Define event E to be the event that min([O), (01) 2 4
Eo-Uve PB [err(es)]]
(24)
= -oowty [Bswp (err(es)]
E
Pr O~UVk
E
Note that since two set in 2/k|| \ 1 are not in event E is clear that PromUv, [ 2
Pro 2/4 [
Moreover, note that when O is chosen uniformly from U212) |0| can be looked upon as a random variable drawn from (in(k, 1/2). Therefore, long as 2 32, using Multiplicative Chernoff bound (Lemma 2T) we can derive
E 2 (1 11-2exp
Pr O 2M
(25)
16
2
Then we try bound Ro-Uv, [Bs-rg [err(cs)] E]. For every [k]] denote 8; to be the number
of in S. Then fix any O E Vv such that min( O), k - [0]) . and any i E O. Note that Lo will
make wrong prediction for the face i iff 2 m/k. Since s; is Bin(p, m) where 1-wr (O)e
using Slud's inequality (Lemma (2) we can derive
new (0)
Pr(s, 2 m/k)
2
ZZ
m(1 + 8) +
(
-
me
P
2 2
m(k
2m
(26)
72
k
((0)
2m22
1 -
- exp
(- k
2
IV
v1-e-- > 0.1
2
Where Z ~ (O, 1) is normally distributed random variable with mean of 0 and standard deviation 0, and (ii) is due Lemma [.]
of 1. Moreover, (i) is due to w (0) S and
Thus,
Pr[s 2 m/k
Pg [err(cs)] N
IE0
|0| (0) 0.1
(27)
0.1
min([O) 10))
k
40
Combining this with (24),, (25),, we conclude that EO-Un, ESapy [err(cs)]]
Using
80
Lemma 20 since err(cs) is always less than 2, we have
1
Pro Sa Smpo
err(cs) 2
>
160
320
which completes the proof.
Consider the specific case where 2. Then V22 ((1), In this case, one of the faces always has probability = -
L+3 and the other has probability = - Any algorithm with error less than must correctly identify which face has the higher probability. In other words, in this special case, the generalized weighted die problem reduces Lemma 5.1 Anthony and Bartlett (2009), stated below.
32

---

Lemma 32 (Lemna 5.1 of Anthony and Bartleti (2019)). Lete <
2 8 < 1. Suppose y= Ü- (-1,+1))
Then if m + In +1) there is algorithm that can predict y with probability more than 1 d using a sample S ~ Bin(m, a:) where a 1e
Corollary 33. Let E < 2. 8 2.555.5 4. Suppose the die O in the generalized weighted die problem with parameters k = 2 and is drawn uniformly at random from the set Vz- If the number of rolls is at most 1 In (26), then any algorithm for the generalized weighted die problem incurs an error of at least with probability greater than 6.
4ea
Proof of Theorem LE The upper bounds for Theorem are already known Du Plessis et all (2015)) We only foeus on the lower-bounds.
Consider any k E N. and consider any B S X' of size 2k, and any p E (0, 1). We randomly divide
B into two halves of size k named 8¹ { 22 .... -k. and B2 = 2 22 ... a. Let p E (0, 1), and for any O!, O E Vk, we define distribution Dot 0a over X' x {0, 1 for all (z,z) E X x {0, {0.1} as
1
if x E B1, and y =1
4
1+ + )
if x = s and i & O and y = 0
1k
10')
if æ = x and i E 0² and y =
Do,,02(Z.V)=
4 By 1e
4k
if x = 5f and i & 0
4k
(2y-Dix Div 10
if x 2a and O
4k
O.w.
We define p.B (DDo 02, D_, 00,000)))) 0 02 V..). Notice that every Do o0 satisfies Do oz (0, : x E x = Moreover, it is easy to see that the error with respect to Do ,0 is minimized by any function f X + f0, 1} that satisfies of n nB = = and f B B² O?. Therefore, for any function we have
CIT o0 (c) min CITD oo
(f)
P.
Σ
l[c(x)) * 1]w -0+) + Σ 1(((x)) * (O²)
functions f
4k
VEE
iE0
Σ SEO2
[[((x])
Olw (0 + Σ [[((x)) + 1| (0²)
$
(28)
The following lemma reduces both the number of unlabeled and positive samples in PU learning over p.B to the generalized weighted die problem.
Lemma 34. Let E (0,1) and m, n N. Suppose there exists a PU learner A such that for
all (D, D+) E Woore bz m, 2 satisfies
PrepaD su - www.pp/eeppaaae... (A(S ,5 - min efr 2
26 <
funetions
Then, (i) there exists a learner that with probability 1 - 8 achieves error less than 4z using rolls for weighted generalized with parameters k and p: (ii) there exists a learner that with probability 1 achieves error less than d using n rolls for a weighted generalized with parameters and g.
Proof. We prove the first part, and the second part is identical to the first part. Fix any die corre- sponding O E Vz- Suppose S fii, i2, ..., im is a roll of size from Po. Let O' {1}. First
notice that for any X' we have
E B
if x and #
D D+.0,0
2h
if = x
O.W.
33

---

Moreover,
1
x - x and +
1-p
if x: = #1
(29)
0
O.W.
Notice that both D+.0.0 and Dx,0,0*-. E B²) are independent from O, and thus learner can collect samples from them without requiring knowledge about O. Next, we define SP be an i.i.d sample of size from D+.0.0'. Then, construct S follows. Initialize j O. At each step, flip an unbiased coin. If it lands heads, increment j by and add z to S If it lands tails, draw sample from Ox, x B²) and add it to S Repeat this process until m.
Moreover, observe that Dx,0,orl I B') Po- Hence, each z!, is independent sample from Dx,0,0r-- æ B²). Since Dx.0,0 (B²) = = it follows that S an i.i.d. sample from D Dx,0,0'. Note that due to lemma's assumption, since | 2 m, |S 2 with probability - 5 we have
erroo (A((S (A(SP,St))
min lunctions
erro (J) <e
We define our leaner h 10, as h; = (1 - A (z))z)) for i E [b.]. Due to (28) we have
errDo (A(S
Functions f err (f)
min
1 (a))) x (0) + Σ
[A(SP, [A((P,)5))a)) +0] w+ wu((()))))
4k
VEO
$00
P err(h)
Thus err(h) = 4-
with probability 8.
p
pos (c, 1 Then, we first show that for d 2 64 we have m myniabel (E, 220) 2 1 s19200e= I, m
[ 2010000 J. Let < 640 and set h = - Let be any subset of of size 2/ that is shattered
1
by C. Define p = 640s, and let the number of unlabeled examples be a = k 2p of positive examples is any b E N. For the sake of contradiction, suppose there exists a PU learner A such that for all (D, D+) E Wagg satisfies
while the number
1
Prge-D St D (A(S ,S") min
min (Ar SS <EC
320
Using Lemma 3 generalized weighted die problem with parameters and can achieve error 160 with probability 320 with rolls. Assuming k 2 32 (which holds long d > 64) this contradicts Theorem I. Therefore, we can conclude that no matter how many positive samples the learner receives, the sample complexity of unlabeled examples should be at least me mantabel (e, 320 > L [ J. Similarly, we can see that no matter how many unlabeled sam- ples the learner receives, as long as d 2 64, the sample complexity of unlabeled examples should be least m (c, )20) Z [ 2-
Finally, we show that for d 2 we have m muntahel (E, 6) 2 25624 In (1))
me m (E, -4ं2 In (
T6 For < 1 and d 1. let & = 2 and let B any subset of size shattered by Define p = 8s, and let the number of unlabeled examples be = _ In (1t). while the number of positive examples 4p- is any b E N. For the sake of contradiction, suppose there exists PU learner A such that for all (D, D4) E Wemo satisfies
Pr su (ATT
min (A(S S E| 5
cEC
Then, by Lemma B4 the generalized weighted die problem with parameters and p would achieve error less than 1. Since p < $ and 8 < 1. this contradicts Corollary [2] Therefore, we conclude
34

---

that no matter how many positive samples the learner receives, the sample complexity of unlabeled examples should be at least m muniabel (e. 8) 2 256 In (7x) Similarly, we can see that no matter how many unlabeled samples the learner receives, as long as d 2 4 the sample complexity of unlabeled examples should be at least m (e, 6) z 65e
In a6
Theorem 16. Let C be any concept class over domain X' with VC dimension d. and let P = D+. Given any Y 2 a, denote cPU argmin efr' There exists M 1 such that for all E C. if
|sp1, >
M (d+1a(1/6)) then with probability 1 - 48 we have
7 (2=0 a : 7
(r mmax
(erro(e) 2(1 + +7)e)
Proof. Using standard PAC theory, for all d C there exists some M > such that if | >
Midin(1/s)+nn(1/0 then with probability 1 1- 8 we have Id's Pr(c((x) 1) S (e.g. see
Shalev-Shwartz and Ben-David (2014)) Similarly, there exists some M 1 such that if |S > MidIn(1/e)+In(1//))) then with probability 1 1-d á we have /eri((c) b-id'ss" these two facts, with probability 1- - 28 for all c' E C we derive (x)(d(x) = 1) + yerr eir (1+)) (1+
E. Combining
b
(30)
Then, for any E EC we have
Pr(c((x) 1) Pr(y 1) - Pr(y 1, 0) Pr(c((x) = =0=
(31)
a arr (c') + (1 (1-0)e15((c)
Now, fix any E C. For the cases where 2 2a, with probability 1 - 28 we have a + a err PU (1 a)) err PU)
+ err
a aa a) emr (c PU) + (1 a) (U)
(r(c 1) vert(c
S "cr" + (1 7)8
(1)
+c]+++++1++ 7)
(32)
I Pr(c(z) = 1) + + + +2(
a (7 a) (c)) (1- + 2(1 + 7)c
a ( - (2-27) +c))(((p)((()))) + 2(1 + +))
(
a 1 7 2x
(c) + 2(1 7))=.
a
Where (i) is due to the definition of PC and (ii) is due to the fact that err)(c) < etp((c
For the
cases where y < 2a with probability 25 we have
+
eerp(e = =a + (1 a) en
+ +1 (1-a) a) a1 7=7=a a a
crp
a
<a (1 - a) err (c PU) + (1 -1- a) (
(33)
< a + (7- a) en (1 a) enr (c) + 2(1 + 7)
<a + (crp(c) + 21 + 7)E
where (i) is derived similarly to (2) This completes the proof.
Theorem 35 (Ben- all (()))). Let be a VC-dimension d concept class over domain X,
and let Es and Qr be distributions over X x {0, 1}. Then, with probability at least - ô, for every CEC:
(cT < error (c) + desc (ex.s, 2x,r) + X
where X = inf erros (c) + (c)
35

---

Theorem 19. Let C be any concept class over domain X with VC dimension d, and let P be any arbitrary distribution. Given any Y 2 a, denote cPU argmin eir' (c). There exists M 1 such that for all c if 1 M(d+h(116)) then with probability 1 - 45 we have
2²
errp (c max (2-0-
a ' (" a _ (erro(e) + ())++)++++)+ (AP denc((, D+)))
-
Where XP = min (crrf(c) + (ctp(c, 1)) and (crp(c, 1) = Prz-p (c(x) 11)
Proof. Note that similar to (G0), again we know there exists some M > 1 such that for all e C with probability 25
Pr(c'(x) = 1) + err - ec) S (1 7)
(34)
Fix any c E C. Thus, for the cases where 2 2a similar to (52) with probability 25 we have
+ errppc
Pr(c (x) + + yerrt(c
S
Pr(c (I) = 1) + (erpp(c + 7 +dssc(P,D.))
cir
(x* + desc(P.D...
+ (x + dcscc(P, D+))
Pr(c(x)= = (rrp))=)))
s n (x" + desc((,
Theorem
Pr(e(x) = +
23 (A" + (esc(P,P (P,, PD)+)
(48)
7 2-2 20:
a
(c) 2(1 + + 2y (x + (e (D)))
a
(35)
Where (i) and (ii) are respectively due to the first two lines and last two lines of (32) Theorem IG. Again similar to (33),, in case < 2a with probability 28 we have
a errp (c (C) ecr 2(1 + 7)e 27 (AP + dcsc((,DD.)
(36)
This completes the proof.
36


Reviews:
[{"review_id": "91dQbKzvqy", "reviewer": "Reviewer_oWVS", "summary": "This study revisits a basic issue in PU learning. The authors define PU learnability and discuss under which conditions we can obtain a desirable classifier. Their analysis investigates each setting in PU learning, including those considered by Elkan and Noto (2008) and du Plessis et al. (2015), and provides a comprehensive framework.", "questions": "See above.", "limitations": "N/A.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The authors address a fundamental problem in PU learning. Although their problem setup is interesting, I have several questions regarding their results. I list the points below:\n- I believe the problem setup in Elkan and Noto (2008) and its subsequent works differs from that in du Plessis et al. (2015) and related studies. The former is referred to as censoring PU learning, while the latter is known as case-control PU learning. The difference is not related to knowledge of the class prior. Even when the class prior is known, the data-generating processes are distinct. It seems that the authors' setting largely follows that of du Plessis et al. (2015). If they were to follow the setting in Elkan and Noto (2008), we would usually assume access only to a single dataset from which labels can be observed. For an explanation of this difference, see Niu et al. (2016).\n- Theorem 14 appears to be somewhat trivial. The Bayes classifier is usually expressed as $p(y = 1 \\mid x) = \\alpha, p(x \\mid y = 1) / p(x)$, where $p(x \\mid y = 1)$ is the class-conditional density of $x$, $p(x)$ is the marginal density, and $\\alpha$ is the class prior. This density ratio $p(x \\mid y = 1) / p(x)$ can be estimated via density-ratio estimation methods. Consequently, it is rather obvious that we can obtain the result stated in Theorem 14, because we can recover the ordering of $p(y = 1 \\mid x)$; the exact classification boundary is then determined by the class prior. For the relationship between density-ratio estimation and PU learning, see Kato and Teshima (2021).\n\nReference:\n- Niu, du Plessis, Sakai, Ma, and Sugiyama (2016). Theoretical Comparisons of Positive-Unlabeled Learning against Positive-Negative Learning. NeurIPS.\n- Kato and Teshima (2021). Non-Negative Bregman Divergence Minimization for Deep Direct Density Ratio Estimation. ICML.", "was_revised": true, "final_justification": "As a result of the discussion, I feel that the contribution has become clearer. While the study is interesting, the results are not particularly surprising, so I will give it a weak accept.", "rebuttal": "Thank you for carefully evaluating our work and for offering constructive feedback. We would like to address your questions bellow:\n1. **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).\n2. **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. \\\nThe 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. \\\nWe will include an extended discussion clarifying the relationship between our work and that of Kato and Teshima (2021).\n\nReferences: \\\nBekker, Jessa, and Jesse Davis. \"Learning from positive and unlabeled data: A survey.\" Machine learning 109.4 (2020): 719-760."}, {"review_id": "RJQw146vD0", "reviewer": "Reviewer_13uY", "summary": "This paper presents a comprehensive theoretical analysis of the statistical complexity of PU learning. In contrast to most prior work, this study does not require the class prior, α, to be known by the learner. The paper explores both the realizable and agnostic learning paradigms across four distinct data-generating settings: Selected Completely at Random (SCAR), Selected at Random (SAR), Positive Covariate Shift (PCS), and Arbitrary Positive Distribution Shift (APDS) .The main contributions include: 1. Providing nearly tight upper and lower sample complexity bounds for the SCAR and SAR settings. 2. Establishing the first finite-sample generalization guarantees for the PCS and APDS settings.3. Introducing a novel combinatorial parameter, the \"claw number,\" to characterize the lower bound on unlabeled sample complexity.\n4. In the agnostic setting with an unknown α, proving that a learner can achieve an error bound proportional to the optimal error and showing that this proportionality factor is theoretically tight.", "questions": "The exponential dependency on dimensionality in your bound for Algorithm 1 seems to be a significant practical barrier. Could you comment on the tightness of this bound? Are there avenues for improvement, or could you outline specific scenarios where this complexity would be manageable?", "limitations": "As noted, the results for challenging distribution shifts rely on a margin assumption, which limits the applicability of these specific conclusions.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The most significant contribution of this work is its systematic treatment of the unknown class prior setting. This addresses a long-standing bottleneck in PU learning theory and brings the theoretical analysis closer to real-world application scenarios.\n2. The paper is impressively comprehensive, systematically analyzing settings from the well-studied SCAR to the more challenging PCS and APDS. By providing both upper bounds (algorithmic guarantees) and lower bounds (inherent problem difficulty) for several key settings, the analysis is remarkably complete and convincing.\n3. The introduction of the \"claw number\" is an interesting conceptual innovation. Furthermore, providing the first finite-sample guarantees for the PCS and APDS settings, where such results were previously lacking, represents a significant theoretical breakthrough.\n\nWeaknesses:\n1. To achieve theoretical guarantees in more challenging settings like PCS, the paper introduces new, strong assumptions, such as the γ-margin assumption. This leads to a sample complexity for unlabeled data that is exponential in the data dimensionality.\n2. This is a purely theoretical paper with no experimental section. While the theoretical contributions are self-contained and sufficient, the absence of experiments on synthetic or real-world datasets makes it difficult to assess the practical performance of the proposed algorithms (e.g., Algorithm 1), their sensitivity to hyperparameters, and the tightness of the theoretical bounds in practice.", "was_revised": true, "final_justification": "The authors have successfully adressed the majority of my concerns as mentioned in the rebuttal.", "rebuttal": "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."}, {"review_id": "HRdfRDq0O1", "reviewer": "Reviewer_cR8L", "summary": "This paper provides a theoretical analysis of PU learning. First, it identifies different PU learning settings, including cases with covariate shift of positive data. Then, it provides a detailed analysis of the sample complexity of these settings. The paper offers new insights into understanding PU learning with distribution shifts.", "questions": "Please see \"weaknesses\".", "limitations": "The limitations should be discussed.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "## Strengths\n- The theoretical analysis is comprehensive and well-executed.\n\n- The studied problem, i.e., the sample complexity of different PU learning settings, is important to the literature.\n\n- The presented theoretical results are interesting and novel, as shown in Table 1.\n\n## Weaknesses\n\n- The paper is novel for the PU learning literature. However, most of the analysis seems dependent on Ben-David and Urner (2012). Therefore, the authors should justify how their proposed setting differs significantly from that of Ben-David and Urner (2012). Additionally, could the authors discuss the differences with [1]?\n\n- The theoretical analysis of the paper is good and comprehensive. The study of different PU learning settings is also valid and sound. However, I am not familiar with the sample complexity analysis of transfer learning in Ben-David and Urner (2012), so it may be difficult for me to justify the soundness of the proposed theory.\n\n- Since the paper contains many theoretical analyses, it is important to write them in a clearer way so that readers can understand them.\n\n- The proposed assumptions need further discussion and justification. Additionally, it is unclear how the theoretical analysis can be applied to real-world applications. There are no experimental results in the paper.\n\n[1] Coudray O, Keribin C, Massart P, et al. Risk bounds for positive-unlabeled learning under the selected at random assumption[J]. Journal of Machine Learning Research, 2023, 24(107): 1-31.", "was_revised": true, "final_justification": "Thanks for the rebuttal. I will maintain my score.", "rebuttal": "Thank you for your constructive feedback and helpful suggestions. We would like to address your questions and concerns bellow:\n- **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.\n- **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$.\n- **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.\n- **Lack of experiments:** The *NeurIPS* conference welcomes a broad range of contributions, including purely theoretical work. Our submission falls within this scope."}, {"review_id": "WoTD03eQ80", "reviewer": "Reviewer_8f7e", "summary": "This paper provides sample complexity bounds in a general *positive unlabled* learning setting. Here the learner has access to two different distributions (from potentially known families of distributions). one generating the unlabeled data and the second generating positively labeled data. They study agnostic and realizable PAC learning variants, which previously appeared in the literature. Their main contributions are novel upper bounds when the class distribution is not known (which appears to be a standard assumption in this line of work), novel tighter lower bounds in various settings, and a novel combinatorial parameter, the *claw number*, allowing some lower bounds on the number of required unlabeled examples.", "questions": "Your proposition 4 strongly reminds me of learning with one-sided error [7]. There it is the same situation that learning is possible iff the intersection-closure has finite VC dimension. Is there any relationship here?\n\nPlease compare the claw number to existing combinatorial parameters beyond VC Dimension (e.g., [1,2], even invariants from convex geometry like Helly, Carathéodory, Radon numbers [3] etc). Are there any known related results? This could provide more context on the relevance of the claw number and perhaps even lead to tighter results.\n\nThe claw number based lower bounds are not fully matching the upper bounds, in particular, there is a remaining gap of $h\\le d$. Do you think the upper bound can be improved from vc to claw number or vice versa? Or is the gap in general unavoidable (using these parameters)?\n\nI think it is very interesting that you manage to get lower bound on the number of unlabeled examples. In related settings like semi-supervised [5,6] and and transductive learning [4] it is commonly known that unlabeled samples do not really in general.\n\n\n\n[1] Bousquet, Olivier, et al. \"Proper learning, Helly number, and an optimal SVM bound.\" COLT 2020.\n[2] Hanneke, Steve. \"The Star Number and Eluder Dimension: Elementary Observations About the Dimensions of Disagreement.\" COLT 2024.\n[3] Kay, David, and Eugene W. Womble. \"Axiomatic convexity theory and relationships between the Carathéodory, Helly, and Radon numbers.\" Pacific Journal of Mathematics 38.2 (1971): 471-485.\n[4] Tolstikhin, I., & Lopez-Paz, D. (2016). Minimax lower bounds for realizable transductive classification. arXiv preprint arXiv:1602.03027.\n[5] Balcan, M. F., & Blum, A. (2010). A discriminative model for semi-supervised learning. Journal of the ACM (JACM), 57(3), 1-46.\n[6] Darnstädt, M., & Simon, H. U. (2011). Smart PAC-learners. Theoretical Computer Science, 412(19), 1756-1766.\n[7] Natarajan, Balaubramaniam Kausik. \"On learning boolean functions.\" Proceedings of the nineteenth annual ACM symposium on Theory of computing. 1987", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n* summarizes and improves various previous results on PU learning.\n\nThe main weakness I see that this paper would benefit greatly from a deeper discussion with related work and if the results would be put into a broader context. See my questions below. **When these are addressed appropriately, I am happy to raise my score.**\n\nSome more smaller weaknesses:\n* some of the proposed/improved bounds are still not tight. While the claw number is interesting, it's unclear whether it gives the optimal tight bounds. See also questions below.\n* it's sometimes not fully clear when results are stated for general concept classes and when they focus on particular domains ($X=[0,1]^k$) and/or assume large margin etc. \n\nSmall comments:\n* there are appear to be various smaller formatting issues. The table 1 too large (and consider using booktabs and removing the vertical lines). Some typos. Usage of dashes seems wrong.", "was_revised": true, "final_justification": "Good paper. Authors clarified concerns.", "rebuttal": "Thank you for your detailed feedback and insightful questions. We would like to address your questions and concerns bellow:\n- **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.\n- **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.\n- **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.\n- **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.\nThere 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.\n- **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.\n- **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.)\n\nWe also thank the reviewer for pointing out those issues, and we will address them in the camera-ready version."}]

Author rebuttal:

Meta-review: This paper presents new sample complexities for positive and unlabeled learning based on relaxed assumptions and four problem setups.  In particular, it presents upper and lower bounds on the required training sample sizes, for both positively labeled and unlabeled data, without assuming class prior is known to the learner (which is assumed in most prior studies). It also introduces a novel quantity called claw number to characterize lower bounds. 

---

Overall, the work is solid. All reviewers are on the positive side. Many reviewers compliment on the comprehensiveness of setups. 

Most reviewers request more thorough comparisons with related works. Authors did a plausible job in responses. I should mention the concept of claw number is also created in graph theory [1]. Authors are encouraged to discuss potential connections to it and give proper credit to it. 

[1] Aditya and Chandran, Cubicity of interval graphs and the claw number. 

Reviewers also provide many good suggestions on improving the clarity of presented theorems and providing more thorough discussions on them. Authors are encouraged to incorporate them in revision.
Decision: Accept (poster)