Positive-Unlabeled Learning with Non-Negative Risk Estimator
From only positive (P) and unlabeled (U) data, a binary classifier could be trained with PU learning, in which the state of the art is unbiased PU learning. However, if its model is very flexible, empirical risks on training data will go negative, and we will suffer from serious overfitting. In this paper, we propose a non-negative risk estimator for PU learning: when getting minimized, it is more robust against overfitting, and thus we are able to use very flexible models (such as deep neural networks) given limited P data. Moreover, we analyze the bias, consistency, and mean-squared-error reduction of the proposed risk estimator, and bound the estimation error of the resulting empirical risk minimizer. Experiments demonstrate that our risk estimator fixes the overfitting problem of its unbiased counterparts.
Summary
The paper builds on the literature of Positive and Unlabeled (PU) learning and formulates a new risk objective that is negatively bounded. The need is mainly motivated by the fact that the state of the art risk formulation for PU can be unbounded from below. This is a serious issue when dealing with models with high capacity (such as deep neural networks), because the model can overfit.
A new lower-bounded formulation is provided. Despite not being unbiased, the new risk is consistent and its bias decreases exponentially with the sample size. Generalization bounds are also proven.
Experiments confirm that state of the art cannot be used with high-capacity models, while the new risk is robust to overfitting and can be applied for classification with simple deep neural networks. 
 
Comments
The paper is very well written, easy to follow and tells a coherent story.
The theoretical results are flawless from my point of view; I have checked the proofs in the supplementary material. The theory is also supported by many comments helping intuition of the arguments behind the proofs. This is very good. I am only confused by the meaning of those two sentences in Section 4:
- Theorem 3 is not a necessary condition even for meeting (3): what is the condition the authors refer to?
- In the proof, the reduction in MSE was expressed as a Lebesgue-Stieltjes integral [29]: why is this relevant?
The authors successfully show that optimisation of this new risk formulation may be effective in practice, on deep neural networks, with only a few (positively) labeled data points. From this, it could help to see what is the point of view of the authors in comparing PU with current trends in deep learning, such as few-shots learning.
The dataset `epsilon` is never mentioned before talking about the model trained on it; I find that confusing for the reader.
Experimental results well address the main point of the paper (i.e. loweboundness/overfitting), but could be expanded. Fig. 1 shows two graphs with a very similar information: PU overfits when training a deep net. A curious reader who does not know about [16] could wonder whether the previous approach actually works at all. Why not showing the same graph (for one among the 2 losses) on a scenario where [16] is effective? For example, given the thesis of the paper, [16] should work fine if we train a linear model on MNIST, right? 
Additionally, it would be interesting to see what is the effect of estimating the class-prior on performance. Experiments in Fig. 2 are designed to show that NNPU can be even better than PN. But what happens if the class priors are estimated by a state of the art method? Since the paper is mostly focus on the theory side, I think this lack is not a major issue for acceptance. Although it will be for any realistic implementation of the proposed method.
Minor
53: Menon et al. ICML 2015 is another valid method for estimating class priors other than [22, 23, 24]
56: Curiosity on notation: why not denoting R_n(g) as R_n^-(g) ? That would be symmetric with R_n^+ (same for the empirical risks)
237: performance of [35] on CIFAR10 has been surpassed, see
https://www.eff.org/ai/metrics or
http://rodrigob.github.io/are_we_there_yet/build/classification_datasets_results.html#43494641522d3130
I think it might be said that [35] is "among the best performing architectures for classifying on CIFAR10"