Research map / Label-efficient and robust learning / Semi-supervised learning
Learning from positive and unlabeled examples -Finite size sample bounds
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.
Theoretical finite-sample analysis of PU learning across SCAR, SAR, positive covariate shift and arbitrary shift setups, without assuming the class prior is known, with new upper and lower bounds including a "claw number" parameter.
Problem
Sample complexity of PU learning (learning from positive and unlabeled examples) under several positive-sampling setups (SCAR, SAR, PCS, arbitrary shift), in realizable and agnostic regimes, especially when the class prior is unknown.
Approach
Introduces the claw number as a combinatorial parameter giving unlabeled-sample lower bounds; uses epsilon-nets and weight ratios to bound positive-sample complexity under SAR; adapts domain adaptation with margin/boxes for covariate shift; and shows a Lagrangian PU empirical loss achieves a ratio max(α,1-α)/min(α,1-α) to the best error without knowing α, which is tight.
Key results
- Lower bound Ω̃(d/ε) on positive samples in the SCAR realizable setting, nearly matching the O(d ln(1/ε)/ε) upper bound.
- Without knowledge of α, no learner beats max(α,1-α)/min(α,1-α) times the approximation error; a Lagrangian learner achieves this ratio plus ε.
- For SAR, PERM achieves O((d ln(1/ε)+ln(1/δ))/ε) unlabeled and O(d/(rε)) positive samples.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Remove the assumption that the class prior α is known in realizable SCAR PU learning | PU learning with finite-VC concept classes · Realizable SCAR | sample complexity: m^{pos}_\mathcal{C}(\varepsilon, \delta), m^{unlabel}_\mathcal{C}(\varepsilon, \delta) = O \left( \frac{d \ln (1 / \vare | Helped |
| Use positive sampling with support restricted to D+ and weight ratio at least r | PERM · Realizable SAR | positive sample complexity: O\left(\frac{d \ln (1 / r \varepsilon) + \ln(1 / \delta)}{r \varepsilon} \right) | Helped |
| Allow positive covariate shift beyond the SAR support restriction, with margin and prior lower-bound assumptions | PCS algorithm · Realizable PCS | sample complexity: m^{pos}=O(d ln(1/(r (1-ε) ε))/(r²(1-ε)² ε)); m^{unlabel}=O(((√k/γ)^k ln((√k/γ)^k/δ))/(π ε) + (d ln(1/ε)+ln(1/δ))/ε) | Mixed |
| Assume the class prior α is unknown rather than known | Agnostic SCAR PU learning · Agnostic SCAR, unknown α | approximation-error multiplicative factor: \frac{\max(\alpha, 1 - \alpha)}{\min(\alpha, 1 - \alpha)} | Hurt |
| Use γ = 1 in the Lagrangian PU empirical loss learner when α is unknown | Agnostic SCAR PU learning · Agnostic SCAR, unknown α | approximation-error multiplicative factor: \frac{\max(\alpha, 1 - \alpha)}{\min(\alpha, 1 - \alpha)} | Helped |
| Allow an arbitrary positive sampling distribution and include its mismatch from D+ in the bound | Lagrangian PU empirical loss learner · Agnostic APDS | generalization error bound: 2 \gamma \left( \lambda^P + d_{\mathcal{C} \triangle \mathcal{C}} (\mathcal{P}, \mathcal{D}_+) \right) | Mixed |
Surprising findings
- Under positive covariate shift, no weight-ratio assumption suffices for PU learnability unless sample size depends on the domain size.
- Without knowing α, almost no concept class with more than one concept is PU learnable in agnostic settings with approximate error ratio guarantees.
Limitations
- Results are purely theoretical with no empirical validation.
- PCS upper bound requires unlabeled sample exponential in 1/gamma (in k-dimensional space).
Experimental setup
Metrics: sample complexity misclassification error
Builds on: PERM (positive empirical risk minimization) Lagrangian PU surrogate loss domain adaptation with unlabeled target samples
Closest papers by meaning
- Theoretical Comparisons of Positive-Unlabeled Learning against Positive-Negative Learning (NeurIPS 2016 · similarity 0.93)
- Dist-PU: Positive-Unlabeled Learning From a Label Distribution Perspective (CVPR 2022 · similarity 0.93)
- Accessible, Realistic, and Fair Evaluation of Positive-Unlabeled Learning Algorithms (ICLR 2026 · similarity 0.92)
- Active Learning From Positive and Unlabeled Examples (NeurIPS 2026 · similarity 0.91)
- Positive and Unlabeled Learning with Controlled Probability Boundary Fence (ICML 2024 · similarity 0.90)
- Surprises in Proper Positive-Only Learning (NeurIPS 2026 · similarity 0.88)
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.