Research map / Label-efficient and robust learning / Recognition and long-tail
Formal Models of Active Learning from Contrastive Examples
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.
Introduces a formal framework for active learning from contrast oracles (contrastive examples chosen by a known contrast-set rule), analyzes sample complexity under minimum-distance and proximity models, and links it to self-directed learning.
Problem
How the choice of contrastive examples (e.g., counterfactual nearest opposite-label points) affects the sample complexity of active learning when the learner knows how the oracle selects them.
Approach
A generic oracle model where each query returns a labeled contrastive example drawn from a known contrast set; the learner exploits knowledge of the selection rule. Two instantiations (minimum-distance and proximity) are analyzed, and the minimum-distance sample complexity is shown to be lower-bounded by half the self-directed learning complexity.
Key results
- Minimum-distance contrast sample complexity is at least ceil(SD(C)/2) for finite domains under any metric.
- Under Hamming distance, 1-decision lists DL^2_m require at least 2^(m-2)-1 queries in the minimum-distance model, while self-directed complexity of DL_m is at most 4km.
- For thresholds the minimum-distance model identifies the target with one query; for monotone monomials plus clauses it needs only 2 queries.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use minimum-distance contrast examples instead of no contrast | Active learning of one-sided thresholds · One-sided thresholds on [0, 1] | sample complexity: \Theta(\log \frac{1}{\varepsilon}) -> 1 | Helped |
| Use proximity contrast examples instead of no contrast | Active learning of one-sided thresholds · One-sided thresholds on [0, 1] | sample complexity: \Theta(\log \frac{1}{\varepsilon}) -> \Theta(\log \frac{1}{\varepsilon}) | No clear effect |
| Use minimum-distance contrast examples instead of no contrast | Active learning of axis-aligned rectangles · Axis-aligned rectangles in k dimensions | sample complexity: \Theta(k\log(\frac{1}{\varepsilon})) -> 2 | Helped |
| Use proximity contrast examples instead of no contrast | Active learning of axis-aligned rectangles · Axis-aligned rectangles in k dimensions | sample complexity: \Theta(k\log(\frac{1}{\varepsilon})) -> \Omega(\log(\frac{1}{\varepsilon})), O(\log(\frac{k}{\varepsilon})) | Mixed |
| Use minimum-distance contrast examples with Hamming distance instead of membership queries | Learning monotone monomials · Monotone monomials, B_m | sample complexity: m -> 1 | Helped |
| Extend the monotone-monomial representation with an extra Boolean component | Minimum-distance and proximity contrast learning · Extended monotone monomials, {0,1}^{m+1} | sample complexity: 1 -> m | Hurt |
| Use minimum-distance contrast examples with Hamming distance instead of membership queries | Learning parity functions · Parity functions, B_m | sample complexity: m -> m - 1 \leq \mathcal{S}_{\CS^d_{\min}}({\mathcal C}_{\parity}) \leq m | No clear effect |
| Use minimum-distance contrast examples with Hamming distance | Learning 1-decision lists with at most two label alternations · DL_m^2 | sample complexity: \ge 2^{m-2}-1 | Hurt |
| Use a version-space-dependent distance function rather than a fixed distance | Learning MDNF_{m,s,z} · MDNF_{m,s,z} | sample complexity: \leq s | Helped |
| Use minimum-distance contrast examples with the discrete metric instead of membership queries | Learning singleton concepts · Singleton concepts over finite domain | sample complexity: n-1 -> 1 | Helped |
Surprising findings
- Adding one dimension to a monotone-monomial class can make contrastive examples under Hamming distance entirely useless (sample complexity equals membership query complexity m).
- Some classes of VC dimension 1 admit a metric achieving at most 2 minimum-distance queries, so no VC-based bound holds.
Limitations
- Assumes the learner has perfect knowledge of the contrast set mapping.
- Results are for finite instance spaces in lower bounds and do not directly model noisy or passive settings.
Experimental setup
Metrics: sample complexity
Baselines: membership query learning
Builds on: self-directed learning counterexample-guided inductive synthesis recursive teaching
Closest papers by meaning
- Optimal Sample Complexity of Contrastive Learning (ICLR 2024 · similarity 0.84)
- Self-Supervised Contrastive Learning is Approximately Supervised Contrastive Learning (NeurIPS 2025 · similarity 0.84)
- Universal Rates for Active Learning (NeurIPS 2024 · similarity 0.84)
- Contrastive Identification and Generation in the Limit (NeurIPS 2026 · similarity 0.84)
- Weakly-Supervised Contrastive Learning for Imprecise Class Labels (ICML 2025 · similarity 0.84)
- The Complexity of Finding Local Optima in Contrastive Learning (NeurIPS 2025 · similarity 0.83)
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.