Surprises in Proper Positive-Only Learning

Understanding PAC learning variants like binary classification from positive-only samples matters because the learner receives i.i.d. samples from the positive region of an unknown target concept yet must perform under the original distribution.

Binary classification from positive-only samples is a variant of PAC learning in which the learner receives i.i.d. samples from the positive region of an unknown target concept, but is evaluated under the original distribution (which places mass on both positive and negative…