Research map / Learning theory and algorithms / Sample complexity
Surprises in Proper Positive-Only Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Characterizes when a concept class is properly learnable from positive-only samples (finite VC dimension plus uniform exterior separability), and derives separations from improper, deterministic, ERM, and non-uniform learning.
Problem
Proper PAC learning from positive-only samples (evaluated under the full distribution) has no known characterization, unlike the well-understood improper case.
Approach
A class is properly positive-only learnable iff it has finite VC dimension and satisfies uniform exterior separability, a condition that allows a bounded list of consistent hypotheses whose false positives on any exterior point are spread out; the proof passes from distributional to uniform separability via dual VC dimension and second-order uniform convergence.
Key results
- Characterization: a class is properly positive-only learnable iff VCdim < infinity and uniform exterior separability holds.
- Few random bits suffice: O~(d + log(1/eps)) random bits and O~(d/eps) positive samples for randomized proper learners.
- Separations: proper vs improper, randomized vs deterministic proper learning, ERM not universal, and finite VC not sufficient for non-uniform learning.
Surprising findings
- Natarajan's conjecture that no-false-positive closure-based characterization extends to two-sided proper positive-only learning is false.
- Randomness can be partially derandomized using sample counts for specific classes, yet randomness is provably necessary for some classes.
Limitations
- Characterizes learnability only; does not give optimal sample complexity or efficient algorithms.
- Exact random-bit complexity left open.
- Analysis is theoretical with no experiments.
Experimental setup
Baselines: Natarajan's conjecture closure rule (improper learner)
Builds on: Natarajan one-sided error model closure-based improper positive-only learning sample compression schemes
Closest papers by meaning
- Learning from positive and unlabeled examples -Finite size sample bounds (NeurIPS 2025 · similarity 0.88)
- Improved Sample Complexity for Multiclass PAC Learning (NeurIPS 2024 · similarity 0.86)
- A Trichotomy for List Transductive Online Learning (ICML 2025 · similarity 0.85)
- Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale (NeurIPS 2026 · similarity 0.85)
- An Õptimal Differentially Private PAC Learner for Concept Classes with VC Dimension 1 (NeurIPS 2026 · similarity 0.85)
- Active Learning From Positive and Unlabeled Examples (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.