AI RESEARCH
Smoothed Analysis of Learning from Positive Samples
arXiv CS.LG
•
ArXi:2504.10428v2 Announce Type: replace-cross Binary classification from positive-only samples is a variant of PAC learning where the learner receives i.i.d. positive samples and aims to learn a classifier with low error. Previous work by Natarajan, Gereb-Graus, and Shvaytser characterized learnability and revealed a largely negative picture: almost no interesting classes, including two-dimensional halfspaces, are learnable. This poses a challenge for applications from bioinformatics to ecology, where practitioners rely on heuristics.