Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper tackles the well known problem of mixture proportion estimation and Positive-Unlabelled (PU) learning. The authors propose a a (new) estimator for MPE based on the assumption of a PU classifier having a "pure" top bin. The authors then develop a novel  iterative outlier-removal-like algorithm for learning a classifier separating the positives and negatives from PU data assuming access to the true MPE. Finally, they combine these two approaches to create a novel alternating algorithm that estimates MPE based on a current PvN classifier, and use the MPE estimate to learn a better PvN classifier from PU data.
main_review: The CvUO algorithm and TED procedure are novel, interesting, and deserve credit.

The BBE algorithm, on the other hand, seems extremely similar to other approaches, e.g. Scott (2015) gives an approach of learning a PvU classifier, and using held-out data to estimate the ROC (with confidence intervals) and give the smallest slope of the ROC curve to (1,1) as an MPE estimate.  This is, essentially, the same as finding a threshold and taking the (confidence adjusted) ratio of q_p/q_u. There are some subtle differences, but they seem rather negligible. While Scott (2015) uses Kernel logistic regression to generate the ROC, there is nothing preventing the use of deep learning methods to generate the ROC curve. The assumptions of irreducibility, i.e. existence of a set S such that P_n(S)=0 but P_p(S)>0 is exactly the same as the existence of a pure top bin when the sets S are generated by thresholding a learned PvU classifier.

The CvUO algorithm seems to essentially assume equal class priors between positive and negative. For example, if alpha=0, CvUO should just return a standard PvN classifier, but the loss function used weights the total positive samples as equal to total negative samples regardless of the actual number of samples of each type. A similar issue exists with the proof of proposition 1 in appendix D. I am guessing this is a bug and can be fixed.

Some guarantee of the sort to ensure that CvUO algorithm does not get progressively worse would be valuable. For example if in one iteration a majority of the alpha fraction of sample removed are not negative the classifier learned after that epoch might be even worse than the previous epoch and start a negative spiral. Can a guarantee be given for this to not happen? The proof in Appendix D does NOT take care of this.




limitations_and_societal_impact: No known negative social impact is conceivable for this work specifically, as it is primarily algorithmic in nature for solving a well-known problem.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes a unified framework for learning from positive-unlabeled (PU) data, including BBE for mixture proportion estimation (MPE)  and CVuO for PU learning. In the literature there are important and elegant works exists that analyze the consistency of the mixture proportion without the irreducibility assumption. They formalize their analyses based on an assumption that the percentage of a blackbox classifier's output for positive samples greater than a fixed value is higher than that for negative samples. I suggest a brief introduction of the conditions that this assumption satisfies, maybe the inductive bias or something, while intuitively such an assumption is quite reasonable. They provide finite sample guarantee for BBE and also empirically verify it. In the PU learning stage, the authors use an iterative manner to progressively identify and remove all the positive points from the unlabeled data during training. This is again quite a reasonable way of thinking because of the memorization of neural networks. The combination of BBE and CVuO is called (TED)^n. The authors provide a lot of supportive experiments to verify their methods.
main_review: 
Two main tasks have been solved in this paper. The first relaxes the strong irreducibility assumption in MPE. Since we don't have any prior information about Pn, it is hard to be verified whether the assumption is satisfied in a specific problem. If not, the existing MPE methods may suffer from estimation bias. BBE is just a clever way of solving that. The second uses a simple manner establishing the state of the art. Overall, new theoretical results provide important insights on an important topic. The paper is clear and well written. There is a good balance of theoretical findings and empirical validations.

Minor suggestions:
- In Algorithm 1, \hat{\alpha} cause some doubts. How to intuitively get this equation? From the supplementary materials, it seems to be a derivation back from the theoretical result? Besides, it would be better to introduce the notions that appear for the first time, e.g., ()_{+}.
- In (TED)^n, how to make a reasonable division between the training set and hold-out set? Should they be evenly split?
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper proposes two methods for PU learning. First, a method for estimating the fraction of positives among unlabeled examples, named Best Bin Estimation (BBE). Secondly, an approach for PU learning called Conditional Value Under Optimism (CVuO). The BBE works on top of the decision score of a given pretrained classifier. The score is used to find a region of the instance space with the minimal ratio of the portion of unlabeled and the portion of positive examples. The ratio is an upper bound on the fraction of positives being estimated. In case there exists a region populated only by positive examples (the condition called pure positive bin property), the bound is tight. The authors provide a finite sample bound for their estimator. The CVuO turns any supervised method to PU learning algorithm. The approach assumes the fraction of positive examples to be known. The idea is to rank the unlabeled examples by a score of a pretrained classifier and remove it the fraction of positive examples. The remaining examples are taken as true negatives and then used with the true positives to re-train the classifier. The procedure is repeated until convergence. Besides, the authors propose an algorithm, called $TED^n$, combining BBE and CVuO. The methods are empirically shown to outperform several recent methods on semisynthetic problems created from CIFAR, MNIST, and IMDB datasets. 
main_review: Originality. The idea of finding the "pure positive bin" and its usage for the estimation of the fraction of positives is to my knowledge novel. The CVuO is a straightforward heuristic to convert PU learning into supervised learning, however, I am not aware of its appearance in the literature. 

Quality. The paper is technically sound. 

Clarity. I am missing a high level explanation of the core idea behind the BBE. The reader is in general left on its own to extract the ideas from a dense text. On the other hand, I understand it is not easy given the limited space. I would suggest to start with showing the equation $q_u(z)=\alpha q_p(z) + (1-\alpha) q_n(z)$ which is easy to understand, and one can immediately see form it that $q_u(z)/q_p(z)\geq \alpha$ and that the bound is tight if $q_n(z) = 0$. The function of the hyper-parameter $\gamma$ of Algorithm 1 is unclear. I do not fully see the logic behind the name "Conditional Value Under Optimism". I had also an impression that the limits of the proposed method are not emphasized, namely, that it requires a prediction model nearly perfectly separating the classes for the top ranked instances.

Significance. The proposed methods are simple and on standard benchmarks outperform several recent approaches. On the other hand, the methods are tested only on data favourable for the proposed method, i.e., almost perfectly separable classes and the fraction of positives equal to 0.5. 

Experiments. As I already mentioned, the methods are tested in the simplest setting when the fraction of positives is just 0.5. It is known that PU methods tend to fail when the classes are imbalanced and it is important to know how the proposed method behaves. The errors are reported without any measure of uncertainty and hence it is hard to judge significance of the the observed differences. The evaluation protocol is not completely clear, but the details are perhaps in the appendix. 

Typos:
- line 30: "of of"
- line 114: ". in our experiments"
- Algo 3, line 4: the same iterator "i" is used in both loops
- Algo 3, line 14: "Lines 4-7" -> "Lines 4-9" 
limitations_and_societal_impact: I don't see any potentially negative societal impact of the work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper targets the problems of mixture proportion estimation and PU learning. The authors propose two simple but effective methods to address two problems. Also, the combination of two methods is proposed to train an accurate binary classifier under mild conditions. A series of experiments are conducted to verify the effectiveness of the proposed method. 
main_review: **Contributions and Novelty**

This paper proposes two advanced methods to tackle the problem of mixture proportion estimation and PU learning, i.e., BBE and CVuO. BBE produces consistent estimates $\hat{\alpha}$ under mild assumptions and achieves a $\mathcal{O}(1/\sqrt{n})$ convergence rate under some assumptions. Moreover, CVuO discards a certain proportion of training examples during training, which reduces the overfitting to the unlabeled positive ones. Finally, the method TED that combines the BBE and CVuO is presented to train a binary classifier under the settings of PU learning. The proposed methods are effective and somewhat novel. 

**Quality**
- Theory. Detailed theoretical analyses are provided for the method BBE, which shows that, with high probability, the estimation is close to the ground truth. 
- Experiments. The experimental results are convincing. The proposed method outperforms baselines in most cases. 

**Clarity**

- Motivation. Although the proposed method works well, the motivation of this paper needs a clearer explanation. 
- Comparison with related works. The authors state that the issues of the prior methods, e.g., complexity or strong assumptions, and aims to address these issues. However, a clearer explanation for their issues is expected to present. At the present stage (Section 2), it is still a bit hard to understand the weaknesses of the prior methods. The descriptions of experimental settings are appreciated.
limitations_and_societal_impact: The **limitations and concerns** in my view are as follows. 
- The authors argue the proposed method only relies on milder conditions. Such a description is somewhat not intuitive. A explanation at a high level is encouraged and expected. 
- More detailed analyses for experimental results are suggested. 
- The procedure of the proposed method is relatively simple. However, it still is comprised of some parts. Would the method bring a lot of extra computational consumption?
- The method consists of some hyper-parameters needed to be determined. The analyses for them (e.g. an ablation study) should be added to discuss their influence in experiments.
review_title: null

Meta-review: 
This paper proposes new methods for the related problems of mixture proportion estimation and positive-unlabeled learning, with theoretical support, and shows state of the art performance, especially for large scale problems. I tend to agree with one of the reviewers that the MPE method is not really that novel, sharing many conceptual similarities with previous ROC based methods. This should be clearly addressed in the final revision, as should all reviewer comments. In addition it would be desired to have some theory for the iterative scheme. Without such, the authors also need to address possible failure cases and limitations of $(TED)^n$. Nonetheless, there is still sufficiently novelty and merit to warrant publication.

Additional comments:

While the experimental contributions are clear, I'd like to ask the authors to comment on how the MPE theory compares to prior work. Is this theory merely "supporting", or does it offer advances in MPE theory in any substantive way?

Relevant reference: Henry Reeve and Ata Kaban. Exploiting geometric structure in mixture proportion estimation with generalised Blanchard-Lee-Scott estimators, ALT 2019
Decision: Accept (Spotlight)