Positive-Unlabeled Learning with Extreme Scarcity of Labeled Positives

Positive-Unlabeled (PU) learning is a weakly-supervised paradigm that trains a binary classifier from labeled positive and unlabeled instances. In PU risk estimation, the empirical risk consists of an unlabeled term and a positive term. In this paper, we observe that when labeled positives are scarce, the risk deviation is dominated by the generalization bound of the positive term, which is composed of a complexity term governed by Rademacher complexity and a concentration term governed by the uniform range bound, leading to estimator instability. Based on this observation, we theoretically derive the sufficient sample threshold, defined as the smallest number of labeled positives required to achieve a target excess risk with high probability, and reveal its explicit dependence on both components. Inspired by this insight, we propose ScalePU, which incorporates variance regularization to induce a restricted sub-hypothesis space with reduced Rademacher complexity, and geometric regularization to encourage compact clustering of positive samples with a tighter effective range. Theoretical analysis demonstrates that both mechanisms effectively lower the threshold through improvements to different components of the bound. Experiments on eight benchmark datasets validate the effectiveness of ScalePU, with significant improvements under extreme label scarcity.

When training models with limited supervision, comparing pairs of examples often provides better learning signals than labeling individual examples. However, we discover a critical challenge: small confidence differences between paired examples can introduce unreliable signals, as these examples might belong to either the same or different classes, potentially misleading the model during training. To solve this problem, we develop a method that separates data pairs based on their confidence differences. For pairs with small differences, we apply a special technique called consistency regularization that encourages the model to produce similar outputs, assuming they likely belong to the same class. For pairs with large differences, we maintain their strong guidance signals since they reliably indicate different classes. Our experiments across multiple datasets demonstrate that this approach consistently outperforms existing methods, even when data contains significant noise. This makes our technique particularly valuable for real-world applications like medical diagnosis, where precise labeling is challenging but comparing patient cases is often more straightforward and reliable.