Research map / Label-efficient and robust learning / Recognition and long-tail

Active Learning From Positive and Unlabeled Examples

NeurIPS 2026 · Label-efficient and robust learning › Recognition and long-tail · approach: Learning from unlabeled and positive-unlabeled data · 0 citations (OpenAlex)

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.

Gives the first label complexity analysis of active PU learning under a SCAR-style feedback model, showing disagreement-based (CAL-style) algorithms achieve label complexity ~ θ²/ω · ln(1/ε) with known class prior, and extend to unknown prior via a binary-search estimation procedure.

Problem

Active learning from positive and unlabeled data, where a queried label is revealed only for positive instances with an independent coin flip (probability ω) and otherwise no information is returned; the goal is bounding label complexity in the realizable, continuous-distribution setting.

Approach

Applies the CAL-style disagreement-based active learner to a version space pruned using passive PU consistency (minimum predicted-positive mass over unlabeled data), exploiting that false positives are bounded by false negatives; for unknown class prior, a binary-search-style estimator of pi_D restricts the version space.

Key results

• With known class prior pi_D, the algorithm outputs an epsilon-accurate hypothesis with O(ln(1/ε) θ²(d ln θ + ln ln(1/ε) + ln(1/δ))/ω) label requests.
• With unknown pi_D, an additional term θ(d ln(θ/π_D)+ln(1/δ))/(π_D² ω) is incurred, and the feedback-rate estimator satisfies ω/2 ≤ estimate ≤ 2ω.
• The bound differs from classical CAL's θ ln(1/ε)(...) bound by roughly a factor θ/ω.

Limitations

• Analysis assumes a continuous data distribution (no atoms) and realizable setting.
• Label complexity has a theta^2 dependence that may not be tight, and a 1/omega dependence from feedback rate.
• Agnostic setting and discrete distributions are left open.

Experimental setup

Metrics: label complexity

Builds on: CAL algorithm Hanneke disagreement coefficient analysis passive PU learning (Theorem 1 of cited work) selected-completely-at-random (SCAR) assumption

Closest papers by meaning

• Learning from positive and unlabeled examples -Finite size sample bounds (NeurIPS 2025 · similarity 0.91)
• Accessible, Realistic, and Fair Evaluation of Positive-Unlabeled Learning Algorithms (ICLR 2026 · similarity 0.89)
• Theoretical Comparisons of Positive-Unlabeled Learning against Positive-Negative Learning (NeurIPS 2016 · similarity 0.89)
• A Closer Look to Positive-Unlabeled Learning from Fine-grained Perspectives: An Empirical Study (NeurIPS 2025 · similarity 0.89)
• Positive and Unlabeled Learning with Controlled Probability Boundary Fence (ICML 2024 · similarity 0.88)
• Universal Rates for Active Learning (NeurIPS 2024 · similarity 0.87)