Research map / Learning theory and algorithms / Sample complexity

Contrastive Identification and Generation in the Limit

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Sample complexity of ranking and selection · 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.

Initiates learning-theoretic study of identification and generation in the limit from contrastive (unordered crossing pair) presentations, giving exact characterizations, a closure-dimension for uniform generation, a hierarchy, and a corruption-robustness reversal.

Problem

Gold-style identification and Kleinberg-Mullainathan generation in the limit assume positive or fully labeled examples, but many supervision signals are relational (pairs known to disagree without labels). The paper asks what a learner can achieve in the limit from such contrastive pair streams, noi

Approach

Model the data as a stream of unordered pairs that cross the unknown target's cut (XOR condition with hidden direction). Use the common crossing graph of two hypotheses to get an exact characterization of contrastive identifiability (text-identifiable plus overlapping-cover condition), a contrastive closure dimension for uniform generation, and a defect-number argument showing that finite corrupti

Key results

• Exact characterization: contrastively identifiable iff text-identifiable and every incomparable pair of hypotheses is an overlapping cover.
• Uniform contrastive generation is possible iff the contrastive closure dimension is finite, with sample complexity d+1 for dimension d.
• Co-singleton class is identifiable under any finite contrastive corruption budget by a single absence-count algorithm, yet not identifiable from text with one corrupted element.

Surprising findings

• Contrastive generation and text identification are mutually incomparable, so contrastive data is not simply weaker than text data.
• Under finite adversarial corruption the inclusion reverses: classes identifiable from contrastive pairs are not identifiable from positive examples even with one corrupted observation.

Limitations

• Purely theoretical; no experiments on real data.
• Results are information-theoretic; effective construction of identifiers/generators from natural oracles is left open.
• Corrupted contrastive generation characterization is open.

Experimental setup

Builds on: Gold's identification in the limit Angluin's tell-tale theorem Kleinberg and Mullainathan generation in the limit closure dimension for uniform generation

Closest papers by meaning

• Generating in the Limit with Infinitely Many Hallucinations (NeurIPS 2026 · similarity 0.87)
• Generation from Noisy Examples (ICML 2025 · similarity 0.86)
• Diversity Is All You Need for Contrastive Learning: Spectral Bounds on Gradient Magnitudes (NeurIPS 2025 · similarity 0.86)
• Nonparametric Identification of Latent Concepts (ICML 2025 · similarity 0.85)
• A Statistical Theory of Contrastive Learning via Approximate Sufficient Statistics (NeurIPS 2025 · similarity 0.85)
• The two clocks and the innovation window: When and how generative models learn rules (NeurIPS 2026 · similarity 0.85)