Contrastive Identification and Generation in the Limit

Technical Summary: Contrastive Identification and Generation in the Limit

Problem Definition
This work introduces the learning-theoretic investigation of contrastive identification and generation in the limit. The authors address a gap in classical limit-learning models (Gold, 1967; Angluin, 1980) and current generative models (Kleinberg and Mullainathan, 2024), which rely on streams of positive examples (Text) or fully labeled data (Informant). In many natural scenarios—such as A/B testing, comparative experiments, and similarity-dissimilarity annotations—data appear as unordered pairs $\{x, y\}$, where the learner knows that the examples disagree under the target hypothesis $h$ (i.e., $h(x) \neq h(y)$), but does not know which element is positive ($h(x)=1$) and which is negative ($h(x)=0$).

The learner observes a stream of such contrastive pairs, which eventually covers every positive example (coverage of the positive side) but never explicitly labels a single point. The goal is to determine the conditions under which a learner can:

1. Identify the target hypothesis $h$ from a known class $\mathcal{H}$ (stabilizing on the correct hypothesis).
2. Generate new positive examples of $h$ (outputting elements in $\text{supp}(h)$ that have not yet appeared in the stream).

Methodology and Technical Framework
The central technical contribution is the introduction of the common crossing graph, denoted as $\Gamma(h, g) = \Delta(h) \cap \Delta(g)$, where $\Delta(h)$ is the set of all pairs crossing the cut defined by $h$. This graph encodes pairwise ambiguity between hypotheses: an edge exists in $\Gamma(h, g)$ if the pair constitutes a valid observation for both $h$ and $g$.

The authors apply this geometric object at three scales:

• Pairs: To analyze eliminability between two hypotheses.
• Finite Families: To analyze generation obstructions caused by common presentations.
• Infinite Defect Sets: To analyze robustness against adversarial corruption.

The work employs a graph-theoretic translation, reducing pairwise contrastive ambiguity to a covering question: A hypothesis $g$ is non-eliminable from $h$ if and only if the support of $h$ is covered by the nodes incident to the edges in $\Gamma(h, g)$.

Main Contributions and Results

1. Exact Characterization of Contrastive Identification (CtrId)
The work provides a necessary and sufficient condition for a class $\mathcal{H}$ to be identifiable from contrastive data. A class belongs to CtrId if and only if:

• It is text-identifiable (satisfying Angluin's Tell-Tale condition).
• Overlapping-Cover Condition: Every pair of incomparable hypotheses in $\mathcal{H}$ must form an "overlapping cover." This means their supports must intersect ($\text{supp}(h) \cap \text{supp}(g) \neq \emptyset$) and their union must cover the entire example space ($\text{supp}(h) \cup \text{supp}(g) = X$).
• Implication: Contrastive data introduce a new obstruction: If two hypotheses are incomparable, disjoint, or intersecting but do not cover the space, they cannot be distinguished.

2. Contrastive Generation and the Closure Dimension
The authors introduce the contrastive closure dimension ($C^\Delta$), a combinatorial dimension analogous to the closure dimension for positive data (Raman et al., 2025).

• Definition: $C^\Delta(\mathcal{H})$ is the supremum of the size of finite "hollow" edge sets (sets of pairs that do not force new positive elements outside the observed nodes).
• Result: A class admits a uniform contrastive generator if and only if $C^\Delta(\mathcal{H}) < \infty$. The tight sample complexity is $C^\Delta(\mathcal{H}) + 1$.
• Non-uniform Generation: A class is non-uniformly generable if it can be decomposed into a chain of subclasses with finite contrastive closure dimensions.
• Obstructions: The work identifies "finite family obstructions," where a set of hypotheses admits a common contrastive presentation with a finite intersection of supports, thereby preventing the generation of new elements.

3. The Diamond Hierarchy
On countable classes with uniformly unbounded support (UUS), the four learning families form a strict diamond hierarchy rather than a linear chain:

• Strict Inclusions: $\text{CtrId} \subsetneq \text{CtrGen}$ and $\text{CtrId} \subsetneq \text{TxtId}$. Both $\text{CtrGen}$ and $\text{TxtId}$ are strictly contained in $\text{TxtGen}$.
• Incomparability: $\text{CtrGen}$ and $\text{TxtId}$ are mutually incomparable.
  • TxtId $\not\subseteq$ CtrGen: Classes with disjoint supports are text-identifiable but blocked from contrastive generation by obstructions of finite intersections.
  • CtrGen $\not\subseteq$ TxtId: Classes with "punctured supports" (removal of an element from an infinite set) are contrastively generable via eventual cores but lack finite Tell-Tale sets required for text identification.

4. Reversal of Robustness under Adversarial Corruption
The work proves a sharp reversal of the relationship between identification modes under finite adversarial corruption:

• Text Fragility: A single corrupted positive example can render a class unidentifiable in the text setting.
• Contrastive Robustness: The authors define a defect number $\kappa(h \to g)$, counting the minimum number of forced violations of a hypothesis $g$ in any valid presentation of $h$. If $\kappa(h \to g) = \infty$, no finite corruption can mask the violations.
• Co-Singleton Class: The class where every hypothesis labels all examples as positive except for one "hole" is identifiable under any finite corruption budget in the contrastive setting (using an "absence counting" algorithm) but unidentifiable under even a single corruption in the text setting.
• Result: For every $k \ge 1$, $k$-corrupt contrastive identification and $k$-corrupt text identification are mutually incomparable.

Significance and Claims
The work claims that the common crossing graph serves as a unifying technical object encoding pairwise ambiguity, family-wide generation obstructions, and corruption defects in a single language. The authors argue that while the lack of directionality in contrastive data constitutes a weakness in clean settings (introducing new obstructions compared to text), it evolves into a strength under adversarial corruption, as corrupted pairs generate structurally detectable "non-edges" that violate the XOR condition.

The work suggests that classical limit-learning paradigms admit fruitful refinements when observations are non-singleton, revealing a two-sided graph-theoretic structure: costly compared to labeled data when clean, but protective when adversarially disturbed. The work explicitly notes that its constructions for identification and non-uniform generation are of an information-theoretic nature (relying on the existence of Tell-Tale families or dimension chains) and leaves the question of effective, constructive procedures for broader classes as an open problem.