New Theory Solves 40-Year-Old Problem in Positive-Only Machine Learning

Researchers Shai Ben-David, Farnam Mansouri, Anay Mehrotra, and Manolis Zampetakis have settled a 40-year-old open problem in learning theory: the characterization of proper learning from positive-only samples. In standard binary classification, a learner receives both positive and negative examples; but in positive-only learning, only samples from the positive region are provided during training, while evaluation occurs under the full distribution. While improper learning (allowing any function) was well understood, proper learning (where the output must belong to the original concept class) had remained elusive. The team proves that a concept class is properly learnable if and only if it has finite VC dimension and satisfies a new condition they call 'uniform exterior separability.' This result closes a gap first noted by Natarajan in 1987.

The characterization reveals a far more complex landscape than classical PAC learning. The researchers demonstrate several surprising separations: proper and improper learning are not equivalent, randomized learners can succeed where deterministic ones fail, finite VC dimension alone does not guarantee even non-uniform learning, and there exist concept classes for which no empirical risk minimization (ERM) algorithm is a proper learner. Along the way, the paper introduces new combinatorial dimensions that measure the complexity of positive-only learning. These results challenge long-held assumptions about the power of proper learning and offer new theoretical tools for designing algorithms in data-scarce settings where only positive examples are available.