Surprises in Proper Positive-Only Learning

arXiv:2606.28309 · stat.ML, cs.LG, math.ST · Submitted 2026-06-26 · Read on arXiv

Shai Ben-David, Farnam Mansouri, Anay Mehrotra, Manolis Zampetakis

stat.ML, cs.LG, math.ST

Submitted: 2026-06-26

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• VC Dimension — 35× in this paper · explained in 2 episodes
• Consistency — 19× in this paper · explained in 3 episodes
• Sample Complexity — 12× in this paper · explained in 20 episodes
• Accuracy — 3× in this paper · explained in 1 episode
• Annual Conference on Learning Theory — 3× in this paper
• Papers — 3× in this paper · explained in 3 episodes
• Sufficiency — 3× in this paper · explained in 2 episodes
• Annual Symposium on Foundations of Computer Science — 2× in this paper
• False Negatives — 2× in this paper · explained in 2 episodes
• Adam — 1× in this paper · explained in 3 episodes
• Annual ACM-SIAM Symposium on Discrete Algorithms — 1× in this paper
• Benchmark — 1× in this paper · explained in 2 episodes
• Combinatorial Optimization — 1× in this paper · explained in 2 episodes
• Embeddings — 1× in this paper · explained in 2 episodes
• Hallucination — 1× in this paper · explained in 4 episodes
• Mode Collapse — 1× in this paper · explained in 2 episodes

Sources

• Agnostic Language Identification and Generation
• Linear Regression with Unknown Truncation Beyond Gaussian Features
• On the Limits of Language Generation: Trade-Offs Between Hallucination and Mode Collapse
• Smoothed Analysis of Learning from Positive Samples

Related papers

• Behavior of prediction performance metrics with rare events
• Optimal Estimation of Generic Dynamics by Path-Dependent Neural Jump ODEs
• A Posterior-Dynamics Framework for Imaging Inverse Problems with Pretrained Diffusion Priors
• Scalable Posterior Uncertainty for Flexible Density-Based Clustering
• A Transport Geometry of Benign Overfitting
• Efficient quadratic entropy with distance sketches