Contrastive Identification and Generation in the Limit
Contrastive Identification and Generation
in the Limit
May 07, 2026
Abstract
In the classical identification in the limit model of [1] [Inf. Control 1967], a stream of positive examples is presented round by round, and the learner must eventually recover the target hypothesis. Recently, [2] [NeurIPS 2024] introduced generation in the limit, where the learner instead must eventually output novel elements of the target’s support. Both lines of work focus on positive-only or fully labeled data. Yet many natural supervision signals are inherently relational rather than singleton: comparative experiments, A/B tests, side-by-side judgments, and similarity–dissimilarity annotations produce observations that encode relationships between examples rather than labels of individual ones. This motivates us to initiate the learning-theoretic study of contrastive identification and generation in the limit, where the learner observes a contrastive presentation of data: a stream of unordered pairs \(\{x,y\}\) satisfying \(h(x)\ne h(y)\) for an unknown target binary hypothesis \(h\), but which element is positive is hidden from the learner. We first present three results in the noiseless setting: an exact characterization of contrastive identifiable classes (a one-line geometric refinement of Angluin’s tell-tale condition [[3], Inf. Control 1980]), a combinatorial dimension called contrastive closure dimension (a contrasitive analogue of the closure dimension in [4] [COLT 2025]) and exactly characterizing uniform contrastive generation with tight sample complexity, and a strict hierarchy in which contrastive generation and text identification are mutually incomparable. We then prove a sharp reversal under finite adversarial corruption: there exist classes identifiable from contrastive pairs under any finite corruption budget by a single budget-independent algorithm, yet not identifiable from positive examples under even one corrupted observation. The unifying technical object is the common crossing graph, which encodes pairwise ambiguity, family-level generation obstructions, and corruption defects in a single coverage-and-incidence language.
In the classical identification in the limit model of [1] [Inf. Control 1967], a stream of positive examples is presented round by round, and the learner must eventually recover the target hypothesis. Recently, [2] [NeurIPS 2024] introduced generation in the limit, where the learner instead must eventually output novel elements of the target’s support. Both lines of work focus on positive-only or fully labeled data. Yet many natural supervision signals are inherently relational rather than singleton: comparative experiments, A/B tests, side-by-side judgments, and similarity–dissimilarity annotations produce observations that encode relationships between examples rather than labels of individual ones. This motivates us to initiate the learning-theoretic study of contrastive identification and generation in the limit, where the learner observes a contrastive presentation of data: a stream of unordered pairs \(\{x,y\}\) satisfying \(h(x)\ne h(y)\) for an unknown target binary hypothesis \(h\), but which element is positive is hidden from the learner. We first present three results in the noiseless setting: an exact characterization of contrastive identifiable classes (a one-line geometric refinement of Angluin’s tell-tale condition [[3], Inf. Control 1980]), a combinatorial dimension called contrastive closure dimension (a contrasitive analogue of the closure dimension in [4] [COLT 2025]) and exactly characterizing uniform contrastive generation with tight sample complexity, and a strict hierarchy in which contrastive generation and text identification are mutually incomparable. We then prove a sharp reversal under finite adversarial corruption: there exist classes identifiable from contrastive pairs under any finite corruption budget by a single budget-independent algorithm, yet not identifiable from positive examples under even one corrupted observation. The unifying technical object is the common crossing graph, which encodes pairwise ambiguity, family-level generation obstructions, and corruption defects in a single coverage-and-incidence language.
1 Introduction↩︎
Identification in the limit, the foundational model introduced by [1], asks how a learner can recover an unknown target hypothesis \(h\) drawn from a known class \(\mathcal{H}\) by observing an infinite stream of examples and stabilizing its guesses on the truth. With a fully labeled stream (an informant), every countable class is identifiable; with only positive examples (a text), even simple classes become unlearnable. [3]’s celebrated tell-tale theorem characterized exactly which classes are identifiable from positive data: each hypothesis must be distinguished from its proper sub-hypotheses by a finite “tell-tale” subset of positives, a structural condition that has anchored inductive inference for four decades [5].
Recently, [2] initiated the parallel study of generation in the limit: instead of naming the target, the learner must eventually output novel positives of \(h\) not yet seen, and on countable classes with infinite supports they showed this is always possible from a text, in stark contrast to identification. [4] reformulated the model in learning-theoretic notation and sharpened the picture by introducing a combinatorial closure dimension that exactly characterizes uniform generation, where the learner must succeed within a bounded number of rounds. Subsequent work has refined this paradigm along three main axes: refined criteria (density, breadth, mode collapse, hallucination), robustness (noise, corruption, replay), and structural extensions (representative, metric, agnostic, safe, and union-closed variants). 2 reviews this body of work.
A common thread runs through this body of work: the learner observes a stream of positive examples of the unknown target. But many natural data sources are inherently relational rather than singleton. Comparative experiments, A/B tests, side-by-side judgments, and similarity-dissimilarity annotations all produce observations that encode relationships between examples rather than labels of individual ones. This raises a basic question: what can a learner accomplish in the limit when its only information is that two examples disagree under the target, with no indication of which is positive?
Contrastive identification and generation in the limit. We introduce contrastive identification and generation in the limit5, where the unknown target \(h:\mathcal{X}\to\{0,1\}\) is a binary hypothesis with positive set (or support) \(\operatorname{supp}(h):=\{x\in\mathcal{X}:h(x)=1\}\), and the learner observes a contrastive presentation of data: at each round, an unordered pair \(\{x,y\}\) of examples that disagree under \(h\), i.e., \(h(x)\ne h(y)\), but with no information about which endpoint is positive. Over time, the contrastive presentation covers every positive (each appears as an endpoint of some pair) and reveals the local structure of the boundary between positives and negatives, yet never explicitly labels a single point. This setting is different from Gold’s text and informant models since each pair carries an XOR constraint between its endpoints, yet hides the labels themselves.
It is natural to read a contrastive presentation geometrically: take the example space as the vertex set of a graph and each observed pair as an edge, so that the disagreement condition forces every edge to cross the unknown cut \((\operatorname{supp}(h),\mathcal{X}\setminus\operatorname{supp}(h))\) separating positives from negatives. A contrastive presentation is therefore, equivalently, a stream of crossing edges of an unknown bipartition, from which the learner must extract structure without any individual endpoint being marked. The central technical object that emerges from this lens is the common crossing graph of two hypotheses: the pairs that cross both hypotheses’ cuts simultaneously, hence look like valid observations under either as the target. This graph captures pairwise ambiguity, family-level generation obstructions, and corruption defects in a single coverage-and-incidence language, and controls all three of our main learnability questions at three scales: pairs for identification, finite families for generation, and infinite defect sets for robustness.
1.1 Our main results↩︎
Throughout the paper we work with countable classes over a countably infinite example space and write \(\mathsf{Ctr}\mathrm{Id}\), \(\mathsf{Ctr}\mathrm{Gen}\) for the families admitting an identifier or a generator in the limit from contrastive presentations, and \(\mathsf{Txt}\mathrm{Id}\), \(\mathsf{Txt}\mathrm{Gen}\) for the corresponding text-stream families. Formal definitions are deferred to 3.
1.1.0.1 (1) Exact characterization of contrastive identification.
We give an exact combinatorial condition for when a hypothesis class admits an identifier in the limit from contrastive presentations: it must be text-identifiable in the sense of Angluin’s tell-tale theorem, and additionally every two incomparable hypotheses must form an overlapping cover, meaning their supports intersect and together cover the entire example space ([thm:ctrid-characterization]). The overlapping-cover requirement is the only obstruction contrastive data introduce beyond positive-only text data.
1.1.0.2 (2) A combinatorial dimension for contrastive generation.
We introduce a closure-style combinatorial dimension that exactly characterizes which hypothesis classes admit a uniform contrastive generator: the edge-set analogue of the closure dimension of [4] for positive-data generation, measuring how long pair constraints can keep an adversary from forcing a novel target element. Finiteness of this dimension is both necessary and sufficient, with tight sample complexity equal to the dimension plus one ([thm:uniform-contrastive-generation]). A non-uniform variant follows by chain decomposition ([thm:nonuniform-contrastive-generation]).
1.1.0.3 (3) The clean diamond hierarchy.
On countable classes with infinite supports, the four families \(\mathsf{Ctr}\mathrm{Id}, \mathsf{Txt}\mathrm{Id}, \mathsf{Ctr}\mathrm{Gen}, \mathsf{Txt}\mathrm{Gen}\) form a strict diamond rather than a chain (1): \(\mathsf{Ctr}\mathrm{Id}\) is strictly weaker than both \(\mathsf{Ctr}\mathrm{Gen}\) and \(\mathsf{Txt}\mathrm{Id}\), both of which are strictly weaker than \(\mathsf{Txt}\mathrm{Gen}\), but \(\mathsf{Ctr}\mathrm{Gen}\) and \(\mathsf{Txt}\mathrm{Id}\) are mutually incomparable ([thm:hierarchy-chain], [thm:hierarchy-incomparability]). The mutual incomparability is witnessed by two natural classes: pairs of hypotheses with disjoint supports (text-identifiable from the first positive, but blocked from contrastive generation by a finite-intersection family obstruction), and punctured-support classes obtained by removing one element from a fixed infinite set (contrastively generatable via an eventually-correct enumeration, but lacking a finite tell-tale for text identification).
1.1.0.4 (4) Robustness reversal under corruption.
The inclusion \(\mathsf{Ctr}\mathrm{Id}\subsetneq\mathsf{Txt}\mathrm{Id}\) reverses under finite adversarial corruption, where an adversary plants a bounded number of arbitrary observations into the stream. We isolate the defect number, an invariant counting the minimum forced wrong-cut violations in any clean contrastive presentation ([prop:defect-number]). When this number is infinite between every pair of hypotheses, identification becomes possible by violation counting under any finite corruption. The co-singleton class (each hypothesis labels every example positive except a single “hole”) realizes this mechanism: it is identifiable under any finite corruption budget by a single budget-independent absence-count algorithm, yet fails text identification at one corruption ([thm:co-singleton-fin-ctrid]). The construction generalizes to mutual incomparability of \(k\)-corrupted contrastive and text identification for every \(k\ge 1\) ([thm:corrupted-incomparability]).
1.2 Technical overview↩︎
Our results are driven by a single piece of geometry, the common crossing graph \(\Gamma(h,g):=\Delta(h)\cap\Delta(g)\), where \(\Delta(h):=\{\{x,y\}\in[\mathcal{X}]^2:h(x)\ne h(y)\}\) is the set of pairs crossing \(h\)’s cut and \(\operatorname{V}(E)\) is the vertex set of an edge set \(E\). We apply \(\Gamma\) at three scales (pair, finite family, infinite defect set).
1.2.0.1 Identification: coverage on \(\Gamma\).
Pairwise eliminability has a one-line graph-theoretic translation: \(g\) is not eliminable from \(h\) iff \(\operatorname{supp}(h)\subseteq\operatorname{V}(\Gamma(h,g))\) ([prop:common-crossing-coverage]). Case analysis on the four-region partition of \(\mathcal{X}\) by membership in \(\operatorname{supp}(h),\operatorname{supp}(g)\) identifies three non-eliminable regimes (superset, disjoint, non-covering). The last two are exactly the new obstructions contrastive data introduce beyond text, driving the exact characterization ([thm:ctrid-characterization]).
1.2.0.2 Generation: edge-induced closure replaces positive-data closure.
Contrastive data confirm only relative parities between endpoints, so we replace the positive version space by the edge-induced version space \(\mathcal{H}_{\Delta}(E)\) and the closure by \(\langle E\rangle^{\Delta}_\mathcal{H}\) (7). The contrastive closure dimension \(\mathrm C_{\Delta}\) (9) is the contrastive analogue of [4]’s closure dimension. Sufficiency is a one-line coverage argument, necessity uses attainment of the supremum on a finite witness, and standard threshold-and-defer extends both to non-uniform classes.
1.2.0.3 Robustness: defects as forced cut violations.
Corrupted contrastive data are \(k\)-close to a clean crossing-edge stream, while corrupted positive data have no such internal structure. The positive-side defect set \(D^+_{h\to g}:=\operatorname{supp}(h)\setminus\operatorname{V}(\Gamma(h,g))\) lower-bounds the number of pairs violating \(g\)’s cut in any clean valid presentation of \(h\) ([prop:defect-number]). When \(\kappa(h\to g):=|D^+_{h\to g}|=\infty\), no finite corruption masks all forced violations. For the co-singleton class \(\Gamma(h_s,h_t)\) is the single edge \(\{s,t\}\), so \(\kappa=\infty\), and the absence-count algorithm ([alg:absence-count]) exploits that the unique negative \(s\) is incident to every honest pair, yielding \(\mathrm{Fin}\textrm{-}\mathsf{Ctr}\mathrm{Id}\) identifiability ([thm:co-singleton-fin-ctrid]).
1.2.0.4 Organization.
2 surveys related work, 3 introduces the preliminaries, [sec:identification,sec:generation,sec:robust] prove the four contributions above, and 7 concludes the findings. Full proofs, discussion, and additional related work are deferred to the appendix.
2 Related Work↩︎
2.0.0.1 Identification in the limit.
The paradigm originates with [1], with [3]’s tell-tale theorem giving the canonical positive-data characterization; see [5] for indexed-family results. Robust and noise-tolerant variants have been studied since the 1980s; recent work [7] characterizes limit-learnability of recursive functions when the learner sees evaluations on every domain point (a labeled, two-sided setting). [8] augment Gold’s model with computational traces of the accepting machine and obtain identifiability across the Chomsky hierarchy with varying corruption tolerance, which is a complementary mechanism for circumventing Gold’s negative results.
2.0.0.2 Generation in the limit.
[2] introduced generation in the limit and proved its universality on countable UUS classes. [4] reformulated the model in learning-theoretic notation and introduced the closure dimension that exactly characterizes uniform generation. Subsequent work has examined breadth, density, noise trade-offs, hallucination detection, generation in continuous spaces, agnostic generation, safe generation, differentially private generation, and union closure properties [9]–[20]. Our contrastive closure dimension is a direct edge-set analogue of the closure dimension of [4], recovering the closure formalism with finite positive samples replaced by finite sets of pair constraints.
2.0.0.3 Learning from pair signals.
The data model studied here, pairs known to disagree but with the labels stripped, is a special case of pair-level supervision studied in a long line of weakly supervised learning, including similarity-dissimilarity (Sim-Conf) learning [6], learning from positive and unlabeled data [21], [22], complementary-label learning [23], learning from label proportions [24], and multiple-instance learning with the exactly-one-positive constraint [25]. Those literatures study finite-sample PAC and risk minimization with stochastic noise; we study the asymptotic identification/generation-in-the-limit regime, in which structural combinatorics (rather than concentration of measure) governs feasibility, and adversarial corruption rather than i.i.d.label noise drives the robustness analysis.
3 Preliminaries↩︎
3.0.0.1 Setting.
We adopt the learning-theoretic notations from [4]. Throughout, \(\mathcal{X}\) is a countably infinite example space and \(\mathcal{H}\subseteq\{0,1\}^{\mathcal{X}}\) is a countable class. The support of \(h\in\mathcal{H}\) is \(\operatorname{supp}(h):=\{x\in\mathcal{X}:h(x)=1\}\). A hypothesis is proper nontrivial if \(\varnothing\subsetneq\operatorname{supp}(h)\subsetneq\mathcal{X}\). We work extensionally; \(\mathcal{X}=\{u_0,u_1,\ldots\}\) is fixed once for “least element” constructions. We restrict to proper nontrivial targets for contrastive presentation (otherwise no XOR pair exists), and to the standard infiniteness condition for generation:
Definition 1 (Uniformly unbounded support [4]). \(\mathcal{H}\) satisfies the uniformly unbounded support (UUS) property if \(|\operatorname{supp}(h)|=\infty\) for every \(h\in\mathcal{H}\).
Definition 2 (Positive-data closure and version spaces [4]). For \(x_{1:n}=(x_1,\ldots,x_n)\), we define the version space \(\mathcal{H}(x_{1:n}):=\{g\in\mathcal{H}:\{x_1,\ldots,x_n\}\subseteq\operatorname{supp}(g)\}\) and the positive-data closure \(\langle x_{1:n}\rangle_{\mathcal{H}}:=\bigcap_{g\in\mathcal{H}(x_{1:n})}\operatorname{supp}(g)\) when nonempty (else \(\bot\)).
Definition 3 (Presentation modes). Let \([\mathcal{X}]^2\) be the set of two-element subsets of \(\mathcal{X}\), and let \(h\in\mathcal{H}\). A text presentation \(T=(x_t)_{t\ge1}\) for \(h\) has \(x_t\in\operatorname{supp}(h)\) and covers \(\operatorname{supp}(h)\); write \(\mathrm{Seen}_n(T):=\{x_t\}_{t\le n}\). An informant presentation \(I=((x_t,h(x_t)))_{t\ge1}\) for \(h\) covers all of \(\mathcal{X}\); write \(\mathrm{Seen}_n(I):=\{x_t\}_{t\le n}\). A contrastive presentation \(P=(p_t)_{t\ge1}\subseteq[\mathcal{X}]^2\) for proper nontrivial \(h\) satisfies (i) \(\sum_{x\in p_t}h(x)=1\) (XOR condition), and (ii) \(\operatorname{supp}(h)\subseteq\bigcup_t p_t\) (positive-side coverage); pairs are observed as unordered sets and may repeat, and we write \(\mathrm{Seen}_n(P):=\bigcup_{t\le n}p_t\) and \(\mathrm{Seen}(P):=\bigcup_{t\ge 1} p_t\).
For \(\mathsf X\in\{\mathsf{Txt},\mathsf{Inf},\mathsf{Ctr}\}\) and any presentation \(Q\), let \(Q_{\le n}\) denote the length-\(n\) prefix.
Definition 4 (Identification and generation in the limit [1], [2]). An \(\mathsf X\)-identifier is a map from valid \(\mathsf X\)-prefixes to \(\mathcal{H}\); it identifies \(h\) if for every valid presentation \(Q\) of \(h\) there exists \(N\) with \(I(Q_{\le n})=h\) for all \(n\ge N\). An \(\mathsf X\)-generator is a map from valid \(\mathsf X\)-prefixes to \(\mathcal{X}\); it generates \(h\) if for every valid presentation \(Q\) of \(h\) there exists \(N\) such that its outputs \(\hat{x}_n=G(Q_{\le n})\) satisfy \(\hat{x}_n\notin\mathrm{Seen}_n(Q)\) and \(\hat{x}_n\in\operatorname{supp}(h)\) for all \(n \geq N\). We write \(\mathcal{H}\in\mathsf X\mathrm{Id}\) (resp.\(\mathsf X\mathrm{Gen}\)) when some identifier (resp.generator) succeeds on every \(h\in\mathcal{H}\).
We will state several foundational results from prior work.
Theorem 1 (Gold’s positive result for informant data [1]). Every countable class \(\mathcal{H}\subseteq\{0,1\}^{\mathcal{X}}\) lies in \(\mathsf{Inf}\mathrm{Id}\).
Theorem 2 (Angluin’s tell-tale theorem [3]). \(\mathcal{H}\in\mathsf{Txt}\mathrm{Id}\) iff for every \(g\in\mathcal{H}\) there is a finite “tell-tale” set \(T_g\subseteq\operatorname{supp}(g)\) such that no \(f\in\mathcal{H}\) with \(\operatorname{supp}(f)\subsetneq\operatorname{supp}(g)\) contains \(T_g\).
Theorem 3 (Universality of text generation [2]). Every countable \(\mathcal{H}\subseteq\{0,1\}^\mathcal{X}\) satisfying UUS lies in \(\mathsf{Txt}\mathrm{Gen}\).
4 Identification: Eliminability via Common Crossings↩︎
This section proves the exact characterization of \(\mathsf{Ctr}\mathrm{Id}\) advertised in 1.1. The argument has two layers: first, a coverage criterion translates pairwise eliminability into a graph-theoretic incidence condition. Second, this geometric reduction combines with Angluin’s tell-tale theorem to yield the exact theorem.
4.0.0.1 Notation.
For \(h\in\mathcal{H}\), the crossing-edge set is \(\Delta(h):=\{\{x,y\}\in[\mathcal{X}]^2:h(x)\ne h(y)\}\); a contrastive pair for \(h\) is precisely an edge in \(\Delta(h)\). For two hypotheses \(h,g\), the common crossing graph is \(\Gamma(h,g):=\Delta(h)\cap\Delta(g)\), viewed as an undirected graph on \(\mathcal{X}\) (2). For an edge set \(E\), \(\operatorname{V}(E)\) denotes the vertices incident to some edge of \(E\). The point of this notation is that pairwise contrastive ambiguity reduces to a coverage question: \(g\) survives a presentation for \(h\) iff every \(h\)-positive is incident to a common-crossing edge.
4.1 Pairwise eliminability as common-crossing coverage↩︎
Definition 5 (Pairwise eliminability). For distinct proper nontrivial \(h,g\), we say \(g\) is eliminable from \(h\) if every valid contrastive presentation for \(h\) contains a pair outside \(\Delta(g)\); equivalently, \(g\) is not eliminable from \(h\) iff there is a valid presentation for \(h\) with all pairs in \(\Gamma(h,g)\).
propositionpropCoverage For distinct proper nontrivial \(h, g\), \(g\) is not eliminable from \(h\) iff \(\operatorname{supp}(h)\subseteq\operatorname{V}(\Gamma(h,g))\).
Proof. (\(\Rightarrow\)) Positive-side coverage forces every \(x\in\operatorname{supp}(h)\) to appear in a common-crossing pair, so \(\operatorname{supp}(h)\subseteq\operatorname{V}(\Gamma(h,g))\). (\(\Leftarrow\)) For each \(x\in\operatorname{supp}(h)\), pick a partner \(y_x\) with \(\{x,y_x\}\in\Gamma(h,g)\); enumerate \(\operatorname{supp}(h)\) (or list-and-repeat if finite) and emit the corresponding pairs to obtain a valid presentation for \(h\) with all pairs in \(\Gamma(h,g)\). ◻
The four-region form of [prop:common-crossing-coverage] reveals exactly which support configurations create barriers.
theoremthmCtrEliminability For distinct proper nontrivial \(h,g\), partition \(\mathcal{X}\) by membership: \(A=\operatorname{supp}(h)\cap\operatorname{supp}(g)\), \(B=\operatorname{supp}(h)\setminus\operatorname{supp}(g)\), \(C=\operatorname{supp}(g)\setminus\operatorname{supp}(h)\), \(D=\mathcal{X}\setminus(\operatorname{supp}(h)\cup\operatorname{supp}(g))\). Then \[\begin{align} g\text{ is not eliminable from }h \;\iff\; (A\ne\varnothing\Rightarrow D\ne\varnothing)\;\wedge\; (B\ne\varnothing\Rightarrow C\ne\varnothing). \end{align}\] Equivalently, \(g\) is not eliminable from \(h\) in exactly three regimes: (N1) \(\operatorname{supp}(h)\subsetneq\operatorname{supp}(g)\) (superset); (N2) incomparable and disjoint (disjoint); (N3) incomparable, intersecting, and non-covering (non-covering).
Proof sketch. For \(x\in A\), a pair \(\{x,y\}\) lies in \(\Delta(h)\) iff \(y\notin\operatorname{supp}(h)\), and additionally in \(\Delta(g)\) iff \(y\notin\operatorname{supp}(g)\); hence \(A\)-vertices are coverable iff \(D\ne\varnothing\). Symmetrically for \(B\). The named regimes follow by case analysis on the support relation. The full proof is in 8. ◻
lemmalemPairwiseShared \(h,g\in\mathcal{H}\) admit a common contrastive presentation valid for both targets iff \(\operatorname{supp}(h)\cup\operatorname{supp}(g)\subseteq\operatorname{V}(\Gamma(h,g))\). Mutual non-eliminability implies confusability.
4.2 Exact characterization of \(\mathsf{Ctr}\mathrm{Id}\)↩︎
Definition 6 (Overlapping cover). \(h,g\) with incomparable supports form an overlapping cover if \(\operatorname{supp}(h)\cap\operatorname{supp}(g)\ne\varnothing\) and \(\operatorname{supp}(h)\cup\operatorname{supp}(g)=\mathcal{X}\).
lemmalemCtrIdSubsetTxtId On classes of proper nontrivial hypotheses, \(\mathsf{Ctr}\mathrm{Id}\subseteq\mathsf{Txt}\mathrm{Id}\), with strict inclusion even on UUS classes.
Proof sketch. A text identifier simulates a contrastive identifier \(I\) by feeding it the synthetic prefix \((\{x_t,z_n\})_{t\le n}\), where \(z_n\) is the least unseen example. For target \(h\), \(z_n\) eventually stabilizes at \(z^*=\min(\mathcal{X}\setminus\operatorname{supp}(h))\); from that stage onward the synthetic prefix is the prefix of a single fixed valid contrastive presentation \((\{x_t,z^*\})_{t\ge1}\) for \(h\), on which \(I\) converges. Strictness: disjoint-support \(\{h_A,h_B\}\) is in \(\mathsf{Txt}\mathrm{Id}\) but the stream \((\{a_n,b_n\})\) confuses contrastive identification. The full proof is in 8. ◻
Combining the geometric reduction of [thm:ctr-eliminability] with the text-side inclusion of [lem:ctrid-subset-txtid] and Angluin’s tell-tale theorem, we obtain the section’s main result: a clean structural characterization of \(\mathsf{Ctr}\mathrm{Id}\) that locates it exactly relative to \(\mathsf{Txt}\mathrm{Id}\).
theoremthmCtrIdCharacterization For a countable class \(\mathcal{H}\) of proper nontrivial hypotheses, the following are equivalent: (i) \(\mathcal{H}\in\mathsf{Ctr}\mathrm{Id}\); (ii) \(\mathcal{H}\in\mathsf{Txt}\mathrm{Id}\) and the contrastive non-eliminability relation is contained in the positive-data superset relation; (iii) \(\mathcal{H}\in\mathsf{Txt}\mathrm{Id}\) and every incomparable pair in \(\mathcal{H}\) is an overlapping cover.
Proof sketch. (ii)\(\iff\)(iii) is immediate from [thm:ctr-eliminability]: among contrastive non-eliminability relations, those not in the superset relation are exactly the disjoint and non-covering incomparable barriers, which are excluded precisely by the overlapping cover condition. (i)\(\Rightarrow\)(ii) uses [lem:pairwise-shared-presentation]. (iii)\(\Rightarrow\)(i): by 2, build an enumerator that outputs the least eligible hypothesis (consistent and \(T_{h_i}\)-seen). The crucial case \(\operatorname{supp}(h)\subsetneq\operatorname{supp}(h_j)\) uses the XOR pair structure: any \(t\in T_{h_j}\setminus\operatorname{supp}(h)\) appears in a pair whose other endpoint must lie in \(\operatorname{supp}(h)\subsetneq\operatorname{supp}(h_j)\), so both endpoints lie in \(\operatorname{supp}(h_j)\), contradicting consistency. Full proof in 8. ◻
Remark 1. The (iii)\(\Rightarrow\)(i) construction uses the tell-tale family \(\{T_g\}_{g\in\mathcal{H}}\) from 2; Angluin’s theorem asserts existence but does not provide the family constructively. The result is therefore information-theoretic; effective construction from natural oracles is open.
5 Generation: Closure, Cores, and Confusability↩︎
Generation asks for eventually-correct novel outputs rather than recovery, and it admits a two-layer theory: a uniform layer governed exactly by a closure dimension, and an ordinary layer governed by safe/eventual cores together with a confusability complex. We treat the uniform layer first because of its exact characterization, then return to the ordinary layer and the diamond hierarchy.
5.1 Edge-induced closure and the contrastive closure dimension↩︎
The proof of 3 relies on confirmed positives. Contrastive data confirm only relative parities, so we replace the version space \(\mathcal{H}(x_{1:n})\) by an edge-induced version space and develop a closure operator over edge sets.
Definition 7 (Edge-induced closure). For finite \(E\subseteq[\mathcal{X}]^2\), let \(\mathcal{H}_{\Delta}(E):=\{g\in\mathcal{H}:E\subseteq\Delta(g)\}\). The contrastive closure is \(\langle E\rangle^{\Delta}_{\mathcal{H}}:=\bigcap_{g\in\mathcal{H}_{\Delta}(E)}\operatorname{supp}(g)\) when \(\mathcal{H}_{\Delta}(E)\ne\varnothing\), and \(\bot\) otherwise. For a contrastive prefix \(P_{\le n}\), \(E_n(P):=\{p_t:t\le n\}\) is the set of distinct observed pairs and \(\mathrm{Safe}_n(P):=\langle E_n(P)\rangle^{\Delta}_{\mathcal{H}}\) when nonempty.
For prefixes \(P_{\le n}\) valid for \(h\), we have \(h\in\mathcal{H}_{\Delta}(E_n(P))\), so \(\mathrm{Safe}_n(P)\subseteq\operatorname{supp}(h)\); a point in \(\mathrm{Safe}_n(P)\setminus\mathrm{Seen}_n(P)\) is therefore a certified novel positive.
Definition 8 (Uniform/non-uniform contrastive generation). A generator \(G\) is a uniform contrastive generator with distinct-edge sample complexity \(d\) if for every \(h\in\mathcal{H}\) and crossing-edge stream \(P\subseteq\Delta(h)\), every prefix length \(n\) with \(|E_n(P)|\ge d\) yields \(G(P_{\le n})\in\operatorname{supp}(h)\setminus\mathrm{Seen}_n(P)\). \(\mathcal{H}\) is non-uniformly contrastively generatable if for one fixed \(G\), some \(d_h<\infty\) suffices for each \(h\).
Definition 9 (Hollow edge set; contrastive closure dimension). Finite \(E\subseteq[\mathcal{X}]^2\) is contrastively hollow for \(\mathcal{H}\) if \(\mathcal{H}_{\Delta}(E)\ne\varnothing\) and \(\langle E\rangle^{\Delta}_{\mathcal{H}}\setminus\operatorname{V}(E)=\varnothing\). The contrastive closure dimension is \(\mathrm C_{\Delta}(\mathcal{H}):=\sup\{|E|:E\text{ finite contrastively hollow}\}\in\mathbb{N}\cup\{0,\infty\}\) (empty sup is \(0\)).
A hollow edge set is a finite contrastive prefix after which every currently forced positive already lies in \(\operatorname{V}(E)\). The dimension measures how long the adversary can keep the novel contrastive closure empty.
theoremthmUniformCtrGen \(\mathcal{H}\) is uniformly contrastively generatable iff \(\mathrm C_{\Delta}(\mathcal{H})<\infty\). Quantitatively, if \(\mathrm C_{\Delta}(\mathcal{H})=d\), then distinct-edge sample complexity \(d+1\) is both necessary and sufficient.
Proof sketch. Sufficiency: when \(|E_n(P)|>d\), \(E_n(P)\) is not hollow, so the closure has a point outside \(\operatorname{V}(E_n(P))=\mathrm{Seen}_n(P)\); output the least such, which lies in \(\operatorname{supp}(h)\) since \(h\in\mathcal{H}_{\Delta}(E_n(P))\). Necessity: the supremum is attained on a bounded nonempty set, so a hollow \(E^*\) with \(|E^*|=d\) exists; presenting its edges, the generator either violates novelty or the chosen point is misclassified by some \(h\in\mathcal{H}_{\Delta}(E^*)\), which extends to a valid presentation. The full proof is in 9. ◻
The same exhaustion principle yields the non-uniform variant, where one only requires that for each individual target the generator is eventually correct. Standard threshold-and-defer arguments translate finiteness of \(\mathrm C_{\Delta}\) on each level of an increasing chain into non-uniform generation.
theoremthmNonUniformCtrGen \(\mathcal{H}\) is non-uniformly contrastively generatable iff there is a nondecreasing chain \(\mathcal{H}_1\subseteq\mathcal{H}_2\subseteq\cdots\) with \(\mathcal{H}=\bigcup_m\mathcal{H}_m\) and \(\mathrm C_{\Delta}(\mathcal{H}_m)<\infty\) for all \(m\).
Remark 2. The construction underlying [thm:nonuniform-contrastive-generation] is information-theoretic: the generator takes the chain \((\mathcal{H}_m)\) and the per-level dimensions \(\{\mathrm C_{\Delta}(\mathcal{H}_m)\}_m\) as inputs. Effective construction from natural oracles (closure-membership, ERM, consistency) is left open.
The dimension does not capture ordinary contrastive generation: classes whose generation relies on eventual cores rather than uniform safe sets can have infinite \(\mathrm C_{\Delta}\), as the next example shows.
Example 1 (Punctured-support class). With \(A=\{a_m\}_{m\ge1}\subsetneq\mathcal{X}\) infinite and \(b\in\mathcal{X}\setminus A\), define \(\operatorname{supp}(h_\infty)=A\) and \(\operatorname{supp}(h_m)=A\setminus\{a_m\}\) for \(m\ge1\). The eventual core \((a_m)_{m\ge1}\) (see [prop:eventual-core]) gives \(\mathcal{H}\in\mathsf{Ctr}\mathrm{Gen}\), yet \(E_n=\{\{a_i,b\}:1\le i\le n\}\) is hollow with \(|E_n|=n\), so \(\mathrm C_{\Delta}(\mathcal{H})=\infty\).
5.2 Cores and confusability↩︎
The dimension theorems above govern uniform generation, where convergence speed is bounded across the class. Ordinary contrastive generation requires only individual convergence and admits two natural sufficient conditions: a uniform infinite safe core (the contrastive closure remains rich at every prefix) and a fixed eventual core (a single sequence whose tail eventually enters every target’s support). The negative side is governed by confusability: families of hypotheses whose supports admit a shared contrastive presentation whose pairwise behavior cannot be disambiguated.
propositionpropSafeCore Suppose that for every \(h\in\mathcal{H}\), every contrastive presentation \(P\) valid for \(h\), and every \(n\ge0\), the safe set \(\mathrm{Safe}_n(P)\) is infinite. Then \(\mathcal{H}\in\mathsf{Ctr}\mathrm{Gen}\).
Example 2 (Augmented-support class). With \(A=\{a_m\}_{m\ge1}\subsetneq\mathcal{X}\) infinite and \(\{b_m\}_{m\ge1}=\mathcal{X}\setminus A\), define \(\operatorname{supp}(h_\infty)=A\) and \(\operatorname{supp}(h_m)=A\cup\{b_m\}\) for \(m\ge1\). The safe core \(A\) certifies \(\mathcal{H}\in\mathsf{Ctr}\mathrm{Gen}\) via [prop:safe-sufficiency], but the non-covering barrier between \(h_\infty\) and any \(h_m\) (incomparable supports intersecting in \(A\) yet missing \(b_{m'}\) for \(m'\ne m\)) blocks \(\mathsf{Ctr}\mathrm{Id}\).
Definition 10 (Eventual core). An injective sequence \((r_m)_{m\ge1}\) in \(\mathcal{X}\) is an eventual core for \(\mathcal{H}\) if \(\{m:r_m\notin\operatorname{supp}(h)\}\) is finite for every \(h\in\mathcal{H}\).
propositionpropEventualCore A countable class of infinite proper nontrivial hypotheses with an eventual core lies in \(\mathsf{Ctr}\mathrm{Gen}\).
For the obstruction, given a finite \(\mathcal{F}\subseteq\mathcal{H}\) let \(\Gamma(\mathcal{F}):=\bigcap_{h\in\mathcal{F}}\Delta(h)\) be the family common crossing graph. A shared contrastive presentation for \(\mathcal{F}\) is a sequence valid for every \(h\in\mathcal{F}\); equivalently, \(\bigcup_{h\in\mathcal{F}}\operatorname{supp}(h)\subseteq\operatorname{V}(\Gamma(\mathcal{F}))\) (see [prop:shared-family-criterion] in 9). Writing \(\mathcal{F}\Subset\mathcal{H}\) for “\(\mathcal{F}\) is a finite subset of \(\mathcal{H}\)”, the confusability complex is \[\begin{align} \mathfrak C(\mathcal{H}):=\{\mathcal{F}\Subset\mathcal{H}:\mathcal{F}\ne\varnothing\text{ and admits a shared contrastive presentation}\}, \end{align}\] an abstract simplicial complex (downward closed under nonempty subsets); we adopt the convention that the empty face is excluded.
propositionpropFiniteFamilyObstruction If \(\mathcal{F}\in\mathfrak C(\mathcal{H})\) with \(|\mathcal{F}|\ge 2\) satisfies \(|\bigcap_{h\in\mathcal{F}}\operatorname{supp}(h)|<\infty\), then \(\mathcal{H}\notin\mathsf{Ctr}\mathrm{Gen}\). (Under UUS the case \(|\mathcal{F}|=1\) is vacuous: a single \(h\in\mathcal{H}\) has \(\bigcap_{h\in\mathcal{F}}\operatorname{supp}(h)=\operatorname{supp}(h)\), which is infinite.)
Proof sketch. A deterministic generator on the shared presentation must serve every \(h\in\mathcal{F}\) simultaneously, eventually outputting from the finite intersection. But the shared presentation covers each \(\operatorname{supp}(h)\), so the (finite) intersection eventually appears in \(\mathrm{Seen}_n(P)\), forcing a novelty/precision contradiction. The full proof is in 9. ◻
Pairwise analysis is incomplete: a family of three hypotheses can lie in \(\mathfrak C(\mathcal{H})\) with finite triple intersection while every pairwise intersection is infinite (11).
5.3 The clean hierarchy↩︎
The identification characterization ([thm:ctrid-characterization]), the dimension theorems ([thm:uniform-contrastive-generation,thm:nonuniform-contrastive-generation]), the core sufficiencies ([prop:safe-sufficiency,prop:eventual-core]), and the finite-family obstruction ([prop:finite-family-obstruction]) together resolve the relations between contrastive learning and text learning. The picture is a strict diamond rather than a chain: contrastive identification is strictly weaker than both contrastive generation and text identification, but contrastive generation and text identification are mutually incomparable.
theoremthmHierarchyChain On countable UUS classes, \(\mathsf{Ctr}\mathrm{Id}\subsetneq\mathsf{Ctr}\mathrm{Gen}\subsetneq\mathsf{Txt}\mathrm{Gen}\) and \(\mathsf{Ctr}\mathrm{Id}\subsetneq\mathsf{Txt}\mathrm{Id}\subsetneq\mathsf{Txt}\mathrm{Gen}\).
theoremthmHierarchyIncomp \(\mathsf{Ctr}\mathrm{Gen}\not\subseteq\mathsf{Txt}\mathrm{Id}\) and \(\mathsf{Txt}\mathrm{Id}\not\subseteq\mathsf{Ctr}\mathrm{Gen}\).
Proof sketch of [thm:hierarchy-chain,thm:hierarchy-incomparability]. Two witness classes do all the work. Disjoint-support \(\{h_A,h_B\}\) is in \(\mathsf{Txt}\mathrm{Id}\) but not in \(\mathsf{Ctr}\mathrm{Gen}\) (pairwise finite-intersection obstruction). The punctured class \(\{h_\infty\}\cup\{h_m:\operatorname{supp}(h_m)=A\setminus\{a_m\}\}\) of 1 is in \(\mathsf{Ctr}\mathrm{Gen}\) (eventual core \((a_m)\)) but not in \(\mathsf{Txt}\mathrm{Id}\) (no finite tell-tale for \(h_\infty\)). The augmented-support class of 2 is in \(\mathsf{Ctr}\mathrm{Gen}\) (safe core \(A\)) but not in \(\mathsf{Ctr}\mathrm{Id}\) (non-covering barrier). The remaining inclusions follow from [lem:ctrid-subset-txtid,thm:KM]. The full proof is in 9. ◻
6 Robustness under Adversarial Corruption↩︎
The clean hierarchy puts contrastive identification strictly below text identification. Adversarial corruption changes the comparison: a corrupted text false positive is indistinguishable from a real one, while a corrupted contrastive pair is structurally a non-edge of \(\Delta(h)\), a detectable defect. We make this asymmetry rigorous through a defect number that counts forced wrong-cut violations.
6.1 Corrupted presentations and defect numbers↩︎
Definition 11 (Corrupted presentations). For \(k\ge0\), a \(k\)-corrupted text for \(h\) has at most \(k\) terms outside \(\operatorname{supp}(h)\) and covers \(\operatorname{supp}(h)\). A \(k\)-corrupted contrastive presentation for \(h\) has at most \(k\) pairs violating XOR, with \(\operatorname{supp}(h)\subseteq\mathrm{Seen}(P)\). Write \(k\text{-}\mathsf{Txt}\mathrm{Id}\), \(k\text{-}\mathsf{Ctr}\mathrm{Id}\) for the corresponding identification notions when \(k\) is known, and \(\mathrm{Fin}\text{-}\mathsf{Ctr}\mathrm{Id}\) when a single identifier succeeds for every finite contrastive corruption budget. Corruption affects only the XOR condition; positive-side coverage is preserved.
Definition 12 (Defect number). For distinct \(h,g\), the positive-side defect set is \(D^+_{h\to g}:=\operatorname{supp}(h)\setminus\operatorname{V}(\Gamma(h,g))\), and the defect number is \(\kappa(h\to g):=|D^+_{h\to g}|\in\mathbb{N}\cup\{0,\infty\}\).
propositionpropDefectNumber For any clean valid contrastive presentation \(P\) of \(h\), let \(\operatorname{viol}_g(P):=|\{t:p_t\notin\Delta(g)\}|\). Then \(\inf_{P\textrm{ valid for }h}\operatorname{viol}_g(P)=\kappa(h\to g)\). In particular, \(g\) is not eliminable from \(h\) if and only if \(\kappa(h\to g)=0\).
[prop:defect-number] is the core mechanism behind the corruption-side reversal: for distinct \(h,g\), each positive of \(h\) not covered by any pair valid for both forces a \(g\)-violation in any clean valid presentation of \(h\). When the defect set is infinite, no finite corruption budget can mask all forced violations, opening a path to robust identification by violation counting. For the co-singleton class this defect set is almost the entire example space, and recovery reduces to identifying the unique vertex incident to every honest pair.
6.2 The co-singleton reversal↩︎
We instantiate the infinite-defect mechanism on the simplest class where it applies: in the co-singleton class, each hypothesis labels every example positive except a single “hole”, and the common-crossing graph between any two distinct targets is a single edge. The reversal it exhibits is sharp: under one-corrupted text the class is unidentifiable, but under any finite contrastive corruption it is identifiable by a single algorithm.
Definition 13 (Co-singleton class). Let \(h_s\) be the hypothesis with \(\operatorname{supp}(h_s):=\mathcal{X}\setminus\{s\}\). We define co-singleton class \(\mathcal{H}_{\mathrm{co}}:=\{h_s:s\in\mathcal{X}\}\).
theoremthmTextFragile \(\mathcal{H}_{\mathrm{co}}\notin 1\textrm{-}\mathsf{Txt}\mathrm{Id}\).
Proof. The enumeration of \(\mathcal{X}\) is a one-corrupted text for every \(h_s\) (the false positive is \(s\)). No identifier can distinguish targets on identical input. ◻
theoremthmStarRecovery \(\mathcal{H}_{\mathrm{co}}\in\mathrm{Fin}\textrm{-}\mathsf{Ctr}\mathrm{Id}\), i.e., \(\mathcal{H}_{\mathrm{co}}\in k\textrm{-}\mathsf{Ctr}\mathrm{Id}\) for every \(k\ge0\).
Proof sketch. The absence-count algorithm ([alg:absence-count]) outputs the co-singleton centered at the example with minimum \(a_n(x):=|\{i\le n:x\notin p_i\}|\). It does not depend on the corruption budget. For target \(h_s\): every honest pair has the form \(\{s,z\}\), so \(a_n(s)\le k_0\) where \(k_0\) is the (unknown) corruption count. For \(t\ne s\), positive-side coverage forces infinitely many honest pairs \(\{s,u\}\) with \(u\ne t\), each omitting \(t\), so \(a_n(t)\to\infty\). Eventually \(s\) is the strict minimum. The full proof is in 10. ◻
Example 3 (Trace on \(\mathcal{H}_{\mathrm{co}}\) with \(k=1\)). Let \(\mathcal{X}=\mathbb{N}\), target \(h_3\), and budget \(k=1\). A possible \(1\)-corrupted prefix is \(P_{\le6}=\big(\{3,0\},\{3,1\},\underline{\{0,4\}},\{3,2\},\{3,4\},\{3,5\}\big)\), with the underlined pair corrupted. The absence counts after \(n=6\) are \(a_6(0)=4\), \(a_6(1)=5\), \(a_6(2)=5\), \(a_6(3)=1\), \(a_6(4)=4\), \(a_6(5)=5\), identifying \(s=3\) as the absence-minimizer. As \(n\to\infty\) along any extension, \(a_n(3)\le1\) stays bounded while each \(a_n(t)\) for \(t\ne3\) diverges.
theoremthmCorruptedIncomp For every \(k\ge1\), \(k\textrm{-}\mathsf{Ctr}\mathrm{Id}\) and \(k\textrm{-}\mathsf{Txt}\mathrm{Id}\) are incomparable.
Proof sketch. \(k\text{-}\mathsf{Ctr}\mathrm{Id}\not\subseteq k\text{-}\mathsf{Txt}\mathrm{Id}\) by [thm:co-singleton-fin-ctrid,thm:text-fragile]. For \(k\text{-}\mathsf{Txt}\mathrm{Id}\not\subseteq k\text{-}\mathsf{Ctr}\mathrm{Id}\), use blocks of size \(k+1\): with disjoint infinite \(A,B\) and \(B=\bigsqcup_i B_i\) with \(|B_i|=k+1\), the class \(\mathcal{H}_k=\{h_i:\operatorname{supp}(h_i)=A\cup B_i\}\) is in \(k\text{-}\mathsf{Txt}\mathrm{Id}\) (no false block is fully observable under \(k\) corruptions) but already fails clean contrastive identification by the non-covering barrier between any two distinct supports. The full proof is in 10. ◻
7 Conclusion↩︎
We studied contrastive identification and generation in the limit, where the learner observes a contrastive presentation of pair-level data with hidden direction. The common crossing graph \(\Gamma\) unifies pairwise ambiguity, family-level generation obstructions, and corruption defects in a single coverage-and-incidence language; the lack of direction is a weakness in clean settings but a strength under corruption. More broadly, this work suggests that classical limit-learning paradigms admit fruitful refinements in which observations are non-singleton, and the graph-theoretic structure that emerges is genuinely two-sided: costly relative to labeled data when the stream is clean, protective when it is adversarially perturbed.
Several natural extensions remain open, and we develop them at greater length in 12 and summarize them here: (i) Does the closure-dimensional characterization of [thm:uniform-contrastive-generation] extend to a corrupted contrastive generation regime, and what is the right robust closure dimension (12.1)? (ii) Random crossing-edge streams induce random bipartite graphs over the unknown cut; do phase-transition phenomena govern statistical contrastive identification and generation (12.2)? (iii) Do effective procedures, in the spirit of the absence-count algorithm ([alg:absence-count]), extend to broader classes with infinite defect gaps (12.3)?
Appendix
8 Omitted Proofs from 4↩︎
Proof. We use [prop:common-crossing-coverage]. For \(x\in A\), a pair \(\{x,y\}\) lies in \(\Delta(h)\) iff \(y\notin\operatorname{supp}(h)\), i.e.\(y\in C\cup D\); to additionally lie in \(\Delta(g)\) (so the pair is in \(\Gamma(h,g)\)), since \(x\in\operatorname{supp}(g)\) we need \(y\notin\operatorname{supp}(g)\), i.e.\(y\in D\). Hence \(A\)-vertices are coverable iff \(D\ne\varnothing\). For \(x\in B\), a similar analysis shows the partner must lie in \(C\), so \(B\)-vertices are coverable iff \(C\ne\varnothing\). This proves the equivalence.
The named regimes are by case analysis on the support relation. If \(\operatorname{supp}(h)\subsetneq\operatorname{supp}(g)\): \(B=\varnothing\) and the only constraint is \(A\ne\varnothing\Rightarrow D\ne\varnothing\), which holds since \(\operatorname{supp}(g)\ne\mathcal{X}\) so \(D\ne\varnothing\); thus (N1) is non-eliminable. If \(\operatorname{supp}(g)\subsetneq\operatorname{supp}(h)\): \(C=\varnothing\) but \(B\ne\varnothing\), so the second implication fails and \(g\) is eliminable. If \(h,g\) are incomparable, \(B,C\ne\varnothing\), so the second implication is automatic and only \(A\ne\varnothing\Rightarrow D\ne\varnothing\) matters: it fails iff \(A\ne\varnothing\) and \(D=\varnothing\), i.e.iff supports cover \(\mathcal{X}\) and intersect (so the pair forms an overlapping cover; \(g\) is eliminable). Otherwise non-eliminable, giving (N2) and (N3). ◻
![Figure 3: Four-region partition of \mathcal{X} by membership in \operatorname{supp}(h) and \operatorname{supp}(g): A in both, B in \operatorname{supp}(h) only, C in \operatorname{supp}(g) only, D in neither. An A-vertex needs a partner in D to lie in \Gamma(h,g); a B-vertex needs a partner in C ([thm:ctr-eliminability]).](/article/2605.06211/_pdflatex/ougfchlj.png "fig:")
Proof. A shared presentation can use only edges in \(\Gamma(h,g)\) and must cover both positive supports, giving necessity. Conversely, choose an incident edge in \(\Gamma(h,g)\) for each element of \(\operatorname{supp}(h)\cup\operatorname{supp}(g)\); enumerate this set if infinite, list-and-repeat if finite, and emit the corresponding chosen edges. Every emitted pair is valid for both hypotheses and both positive sides are covered. The final statement follows because a deterministic identifier produces the same hypothesis on the resulting presentation regardless of which target generated it. ◻
Proof. Inclusion. Let \(\mathcal{H}\in\mathsf{Ctr}\mathrm{Id}\) with contrastive identifier \(I\) (extended arbitrarily to all finite sequences in \([\mathcal{X}]^2\)). Define a text identifier as follows: on prefix \(T_{\le n}=(x_1,\ldots,x_n)\), let \(z_n\) be the least element of \(\mathcal{X}\setminus\mathrm{Seen}_n(T)\) and feed \(I\) the synthetic prefix \((\{x_t,z_n\})_{t\le n}\).
Fix target \(h\) and let \(z^*:=\min(\mathcal{X}\setminus\operatorname{supp}(h))\). The text covers \(\operatorname{supp}(h)\), so every example before \(z^*\) eventually appears in \(\mathrm{Seen}_n(T)\) while \(z^*\) does not; therefore \(z_n=z^*\) for all sufficiently large \(n\). Beyond that stage, the synthetic prefix is exactly the length-\(n\) prefix of the single fixed contrastive presentation \(P^*:=(\{x_t,z^*\})_{t\ge1}\), which is valid for \(h\) (each pair lies in \(\Delta(h)\) and positive-side coverage holds). Since \(I\) identifies \(h\) on \(P^*\), the simulated text identifier converges.
Strictness. Pick disjoint infinite \(A=\{a_n\},B=\{b_n\}\) in \(\mathcal{X}\), and let \(h_A,h_B\) have supports \(A,B\). Then \(\{h_A,h_B\}\) is text-identified from the first positive example, but \((\{a_n,b_n\})_{n\ge1}\) is a valid contrastive presentation for both \(h_A\) and \(h_B\), so no contrastive identifier can distinguish them. ◻
Proof. Write \(h\to_\Delta g\) for “\(g\) is not eliminable from \(h\)” and \(h\to_+ g\) for “\(\operatorname{supp}(h)\subsetneq\operatorname{supp}(g)\)”.
(ii)\(\iff\)(iii). By [thm:ctr-eliminability], the contrastive non-eliminability relations not already in \(\to_+\) are precisely the disjoint and non-covering incomparable barriers (N2, N3). These are excluded iff every incomparable pair is an overlapping cover.
(i)\(\Rightarrow\)(ii). \(\mathcal{H}\in\mathsf{Txt}\mathrm{Id}\) follows from [lem:ctrid-subset-txtid]. Suppose \(h\to_\Delta g\) but \(h\not\to_+ g\). Since [thm:ctr-eliminability] rules out the case \(\operatorname{supp}(g)\subsetneq\operatorname{supp}(h)\), the pair must be incomparable, satisfying (N2) or (N3). Both are symmetric, so \(g\to_\Delta h\) as well, and [lem:pairwise-shared-presentation] produces a single presentation valid for both targets, contradicting \(\mathcal{H}\in\mathsf{Ctr}\mathrm{Id}\).
(iii)\(\Rightarrow\)(i). By 2, for each \(g\in\mathcal{H}\) there is a finite \(T_g\subseteq\operatorname{supp}(g)\) such that no proper sub-support inside \(\mathcal{H}\) contains \(T_g\). Fix an enumeration \(\mathcal{H}=\{h_0,h_1,\ldots\}\). Call \(h_i\) eligible at time \(n\) if \(T_{h_i}\subseteq\mathrm{Seen}_n(P)\) and every observed pair lies in \(\Delta(h_i)\). The identifier outputs the eligible hypothesis of smallest index (default arbitrary if none).
Let \(h=h_i\) be the target. Since \(T_h\) is finite and \(\operatorname{supp}(h)\) is covered, \(h\) is eventually eligible. We show every \(h_j\) with \(j<i\) is eventually ineligible.
Case 1: \(\operatorname{supp}(h_j)\subsetneq\operatorname{supp}(h)\). \(h_j\) is eliminable from \(h\) by the superset direction (already from positive data), so eventually inconsistent.
Case 2: \(\operatorname{supp}(h),\operatorname{supp}(h_j)\) are incomparable. Condition (iii) makes them an overlapping cover, so by [thm:ctr-eliminability] \(h_j\) is eliminable from \(h\), eventually inconsistent.
Case 3: \(\operatorname{supp}(h)\subsetneq\operatorname{supp}(h_j)\). We show \(h_j\) is never eligible. Suppose for contradiction \(h_j\) is eligible at some time \(n\), so \(T_{h_j}\subseteq\mathrm{Seen}_n(P)\) and every observed pair lies in \(\Delta(h_j)\). The tell-tale property of \(T_{h_j}\) rules out \(T_{h_j}\subseteq\operatorname{supp}(h)\) (since \(\operatorname{supp}(h)\) is a proper sub-support of \(\operatorname{supp}(h_j)\)). Take \(t\in T_{h_j}\setminus\operatorname{supp}(h)\): by eligibility \(t\in\mathrm{Seen}_n(P)\), so \(t\) appeared in some observed pair \(\{t,y\}\), which lies in \(\Delta(h)\) by validity. Since \(t\notin\operatorname{supp}(h)\), the pair has \(y\in\operatorname{supp}(h)\subsetneq\operatorname{supp}(h_j)\) and \(t\in T_{h_j}\subseteq\operatorname{supp}(h_j)\), so both endpoints lie in \(\operatorname{supp}(h_j)\), contradicting \(\{t,y\}\in\Delta(h_j)\).
Thus every earlier \(h_j\) is eventually ineligible. Only finitely many indices precede \(i\), so the identifier converges to \(h\). ◻
9 Omitted Proofs from 5↩︎
Proof. Sufficiency. Suppose \(\mathrm C_{\Delta}(\mathcal{H})=d<\infty\). On prefix \(P_{\le n}\), let \(E:=E_n(P)\). If \(|E|\le d\) or \(\mathcal{H}_{\Delta}(E)=\varnothing\), output anything; otherwise output the least element of \(\langle E\rangle^{\Delta}_{\mathcal{H}}\setminus\operatorname{V}(E)\). For target \(h\) and any crossing-edge stream \(P\), \(h\in\mathcal{H}_{\Delta}(E_n(P))\), so the version space is nonempty; when \(|E_n(P)|>d\), \(E_n(P)\) is not hollow, so the closure has a point outside \(\operatorname{V}(E_n(P))=\mathrm{Seen}_n(P)\), and the chosen point lies in \(\operatorname{supp}(h)\) since \(h\in\mathcal{H}_{\Delta}(E_n(P))\).
Necessity. Set \(d:=\mathrm C_{\Delta}(\mathcal{H})\). The supremum is over a bounded nonempty subset of \(\mathbb{N}\) (assuming \(d\ge1\); the case \(d=0\) is trivial), hence attained: there exists a hollow \(E^*\) with \(|E^*|=d\). Suppose for contradiction that \(G\) is a uniform contrastive generator with distinct-edge sample complexity \(d^*\le d\). Present \(E^*\)’s edges in any order as the first \(d\) pairs of a presentation; then \(|E_d|=d\ge d^*\), so \(G\) is required to output a novel positive at step \(d\). If \(G\) outputs \(x\in\operatorname{V}(E^*)\), it violates novelty; otherwise hollowness gives \(x\notin\langle E^*\rangle^{\Delta}_{\mathcal{H}}\), so there is \(h\in\mathcal{H}_{\Delta}(E^*)\) with \(x\notin\operatorname{supp}(h)\). Since \(h\) is proper nontrivial, the prefix extends to a valid contrastive presentation for \(h\) by covering remaining positives via any \(h\)-crossing edges. On this extension \(G\) errs at step \(d\), contradicting \(d^*\le d\). Hence sample complexity \(d+1=\mathrm C_{\Delta}(\mathcal{H})+1\) is necessary. ◻
Proof. Necessity. Let \(G\) be a non-uniform contrastive generator and define \(\mathcal{H}_m\) as the set of \(h\in\mathcal{H}\) for which \(G\) is correct after \(m\) distinct edges, on every crossing-edge stream for \(h\). Then \(\mathcal{H}_1\subseteq\mathcal{H}_2\subseteq\cdots\) and \(\bigcup_m\mathcal{H}_m=\mathcal{H}\). If \(\mathcal{H}_m\) had a hollow edge set \(E\) of size \(\ge m\), the necessity argument of [thm:uniform-contrastive-generation] applied inside \(\mathcal{H}_m\) would produce a target in \(\mathcal{H}_m\) on which \(G\) errs after \(m\) distinct edges. Hence \(\mathrm C_{\Delta}(\mathcal{H}_m)<m\).
Sufficiency. Set \(d_m:=m+\mathrm C_{\Delta}(\mathcal{H}_m)+1\); then \(d_m\to\infty\) and \(|E|\ge d_m\Rightarrow|E|>\mathrm C_{\Delta}(\mathcal{H}_m)\). On prefix \(P_{\le n}\) with \(E:=E_n(P)\), choose the largest \(m\) with \(d_m\le|E|\) (default arbitrarily otherwise). If \(\mathcal{H}_{\Delta}(E)\cap\mathcal{H}_m=\varnothing\), output arbitrarily; else output the least element of \(\langle E\rangle^{\Delta}_{\mathcal{H}_m}\setminus\operatorname{V}(E)\), which is nonempty because \(|E|>\mathrm C_{\Delta}(\mathcal{H}_m)\). For target \(h\in\mathcal{H}\), pick \(m_0\) with \(h\in\mathcal{H}_{m_0}\); once \(|E_n(P)|\ge d_{m_0}\), the chosen \(m\) is at least \(m_0\) and \(h\in\mathcal{H}_m\), so the output lies in \(\operatorname{supp}(h)\setminus\mathrm{Seen}_n(P)\). ◻
Proof. At step \(n\), output the least element of \(\mathrm{Safe}_n(P)\setminus(\mathrm{Seen}_n(P)\cup\{\hat{x}_1,\ldots,\hat{x}_{n-1}\})\). The excluded set is finite and \(\mathrm{Safe}_n(P)\) is infinite by hypothesis, so the choice exists, giving novelty. Since \(P\) is valid for the target \(h\), every observed pair lies in \(\Delta(h)\), so \(h\in\mathcal{H}_{\Delta}(E_n(P))\), hence \(\mathrm{Safe}_n(P)\subseteq\operatorname{supp}(h)\); every output therefore lies in \(\operatorname{supp}(h)\), giving precision. ◻
Proof. At step \(n\), output \(r_m\) for the least \(m\ge n\) with \(r_m\notin\mathrm{Seen}_n(P)\cup\{\hat{x}_1,\ldots,\hat{x}_{n-1}\}\). The tail \(\{r_m:m\ge n\}\) is infinite (the sequence is injective) while the excluded set is finite, so such \(m\) exists, satisfying novelty. For target \(h\), the eventual-core hypothesis states that \(\{m:r_m\notin\operatorname{supp}(h)\}\) is finite, so for all sufficiently large \(m\) the term \(r_m\) lies in \(\operatorname{supp}(h)\). Since the chosen index satisfies \(m\ge n\) and \(n\to\infty\), the output is eventually in \(\operatorname{supp}(h)\), giving precision. ◻
propositionpropSharedFamily A finite family \(\mathcal{F}\) admits a shared contrastive presentation iff \(\bigcup_{h\in\mathcal{F}}\operatorname{supp}(h)\subseteq\operatorname{V}(\Gamma(\mathcal{F}))\).
Proof. A shared presentation uses only edges in \(\Gamma(\mathcal{F})\) and covers each \(\operatorname{supp}(h)\), giving necessity. Sufficiency: pick an incident edge in \(\Gamma(\mathcal{F})\) for each \(x\in\bigcup_h\operatorname{supp}(h)\), enumerate (or list-and-repeat) and emit the corresponding pairs. ◻
Proof. [prop:shared-family-criterion] produces a shared presentation \(P\) for \(\mathcal{F}\). On \(P\), a deterministic generator outputs the same sequence \((\hat{x}_n)\) regardless of which \(h\in\mathcal{F}\) is the target. If it succeeds for every \(h\in\mathcal{F}\), then beyond the maximum individual convergence time all outputs lie in \(\bigcap_{h\in\mathcal{F}}\operatorname{supp}(h)\). This intersection is finite, and \(P\), being valid for each \(h\), covers \(\operatorname{supp}(h)\supseteq\bigcap_{h'\in\mathcal{F}}\operatorname{supp}(h')\), so the (finite) intersection eventually appears in \(\mathrm{Seen}_n(P)\). Beyond that stage novelty forbids outputting from the intersection, while eventual precision for every target requires it: contradiction. ◻
Proof. \(\mathsf{Ctr}\mathrm{Id}\subseteq\mathsf{Ctr}\mathrm{Gen}\). Given a contrastive identifier \(I\), define \(G(P_{\le n})\) as the least element of \(\operatorname{supp}(I(P_{\le n}))\setminus(\mathrm{Seen}_n(P)\cup\{\hat{x}_1,\ldots,\hat{x}_{n-1}\})\). Once \(I\) converges to the (infinite-support) target \(h\), every output lies in \(\operatorname{supp}(h)\) and is novel.
Strictness of \(\mathsf{Ctr}\mathrm{Id}\subsetneq\mathsf{Ctr}\mathrm{Gen}\). Pick disjoint infinite \(A,B\subseteq\mathcal{X}\) with \(\mathcal{X}\setminus(A\cup B)\ne\varnothing\) (possible since \(\mathcal{X}\) is countably infinite). Define \(\operatorname{supp}(h_\infty):=A\) and \(\operatorname{supp}(h_m):=A\cup\{b_m\}\) for \(m\ge1\). For any target and any valid presentation \(P\) with edge set \(E_n(P)\), the version space \(\mathcal{H}_{\Delta}(E_n(P))\) contains the target itself, and every hypothesis in \(\mathcal{H}\) has support \(\supseteq A\); hence \(\mathrm{Safe}_n(P)=\bigcap_{g\in\mathcal{H}_{\Delta}(E_n(P))}\operatorname{supp}(g)\supseteq A\) is infinite, and [prop:safe-sufficiency] gives \(\mathcal{H}\in\mathsf{Ctr}\mathrm{Gen}\). The class is not in \(\mathsf{Ctr}\mathrm{Id}\): for \(m\ne r\), \(\operatorname{supp}(h_m)\) and \(\operatorname{supp}(h_r)\) are incomparable, intersect in \(A\), and miss \(\mathcal{X}\setminus(A\cup B)\), failing [thm:ctrid-characterization].
\(\mathsf{Ctr}\mathrm{Gen}\subseteq\mathsf{Txt}\mathrm{Gen}\) and strictness. Inclusion follows from 3. For strictness, take disjoint infinite \(A=\{a_n\}, B=\{b_n\}\) and consider \(\{h_A,h_B\}\) with supports \(A,B\). It is in \(\mathsf{Txt}\mathrm{Gen}\) by 3, but \((\{a_n,b_n\})_{n\ge1}\) is valid for both targets while \(A\cap B=\varnothing\), so [prop:finite-family-obstruction] applies.
\(\mathsf{Ctr}\mathrm{Id}\subseteq\mathsf{Txt}\mathrm{Id}\) and strictness are [lem:ctrid-subset-txtid].
\(\mathsf{Txt}\mathrm{Id}\subseteq\mathsf{Txt}\mathrm{Gen}\) and strictness follow from 3 and the punctured-support example below. ◻
Proof. \(\mathsf{Txt}\mathrm{Id}\not\subseteq\mathsf{Ctr}\mathrm{Gen}\). The class \(\{h_A,h_B\}\) above is in \(\mathsf{Txt}\mathrm{Id}\) (identified from the first observed positive) but not in \(\mathsf{Ctr}\mathrm{Gen}\).
\(\mathsf{Ctr}\mathrm{Gen}\not\subseteq\mathsf{Txt}\mathrm{Id}\). Take infinite \(A=\{a_m\}\subsetneq\mathcal{X}\) and define \(\operatorname{supp}(h_\infty)=A\), \(\operatorname{supp}(h_m)=A\setminus\{a_m\}\). Then \((a_m)\) is an eventual core, so \(\mathcal{H}\in\mathsf{Ctr}\mathrm{Gen}\) by [prop:eventual-core]. For any finite \(T\subseteq A\), pick \(m\) with \(a_m\notin T\); then \(T\subseteq A\setminus\{a_m\}\subsetneq A=\operatorname{supp}(h_\infty)\), so \(h_\infty\) has no finite text tell-tale and \(\mathcal{H}\notin\mathsf{Txt}\mathrm{Id}\). ◻
10 Omitted Proofs from 6↩︎
Proof. Lower bound. Fix any valid presentation \(P\) of \(h\). For each \(x\in D^+_{h\to g}\), positive-side coverage forces \(x\) to appear in at least one pair of \(P\); let \(t(x)\) be the index of its first appearance. Since \(p_{t(x)}\in\Delta(h)\) and \(x\) has no incident edge in \(\Gamma(h,g)\), the pair \(p_{t(x)}\) lies outside \(\Delta(g)\), i.e., it is a \(g\)-violation. The map \(x\mapsto t(x)\) is injective: each \(h\)-valid pair has exactly one endpoint in \(\operatorname{supp}(h)\) (the other being a non-positive of \(h\)), so a single pair can be the first-covering pair of at most one defect. Therefore \(\operatorname{viol}_g(P)\ge|\{t(x):x\in D^+_{h\to g}\}|=|D^+_{h\to g}|\).
Upper bound. If \(D^+_{h\to g}\) is infinite, enumerate \(\operatorname{supp}(h)\) and pair every non-defect with a common-crossing partner and every defect with any \(h\)-negative partner; the result is a valid presentation with infinitely many violations, matching \(\kappa(h\to g)=\infty\).
If \(D^+_{h\to g}\) is finite, cover each defect once with an \(h\)-negative partner (contributing exactly \(|D^+_{h\to g}|\) violations) and each non-defect via a chosen common-crossing partner (no violations). For infinite \(\operatorname{supp}(h)\) the enumeration provides infinitely many pairs; for finite \(\operatorname{supp}(h)\) we may, after these covering pairs, repeat any non-defect common-crossing pair forever, provided one exists.
Claim 1. If both \(h\) and \(g\) are proper nontrivial, there exists \(x\in\operatorname{supp}(h)\setminus D^+_{h\to g}\), i.e.a non-defect positive.
Proof of claim. Suppose otherwise: \(\operatorname{supp}(h)\subseteq D^+_{h\to g}\), so no vertex of \(\operatorname{supp}(h)=A\cup B\) is incident to a common-crossing edge. An \(A\)-vertex has a common-crossing partner iff \(D\ne\varnothing\); a \(B\)-vertex iff \(C\ne\varnothing\). Hence \(A=\varnothing\) or \(D=\varnothing\), and \(B=\varnothing\) or \(C=\varnothing\). Each of the four resulting sub-cases violates a standing assumption:
\(A=\varnothing\) and \(B=\varnothing\): then \(\operatorname{supp}(h)=A\cup B=\varnothing\), contradicting \(h\) proper nontrivial.
\(A=\varnothing\) and \(C=\varnothing\): then \(\operatorname{supp}(g)=A\cup C=\varnothing\), contradicting \(g\) proper nontrivial.
\(B=\varnothing\) and \(D=\varnothing\): then \(\operatorname{supp}(h)\subseteq\operatorname{supp}(g)\) and \(\operatorname{supp}(h)\cup\operatorname{supp}(g)=\mathcal{X}\), so \(\operatorname{supp}(g)=\mathcal{X}\), contradicting \(g\) proper nontrivial.
\(C=\varnothing\) and \(D=\varnothing\): symmetrically \(\operatorname{supp}(g)\subseteq\operatorname{supp}(h)\) and \(\operatorname{supp}(h)\cup\operatorname{supp}(g)=\mathcal{X}\), so \(\operatorname{supp}(h)=\mathcal{X}\), contradicting \(h\) proper nontrivial.
The claim ensures the construction terminates, completing the upper bound. ◻
Proof. We show that [alg:absence-count] is independent of the corruption budget.
Fix target \(h_s\) and let \(k_0\) be the actual (finite, unknown) corruption count. Every honest pair has the form \(\{s,z\}\) with \(z\ne s\), so \(s\) is incident to every honest pair; hence \(s\) is absent from at most \(k_0\) pairs, giving \(a_n(s)\le k_0\) for all \(n\).
For \(t\ne s\): every honest pair has the form \(\{s,u\}\) with \(u\ne s\), so the only honest pair-set containing \(t\) is \(\{s,t\}\) (it may appear in the stream any number of times, but every other honest pair omits \(t\)). We claim that infinitely many distinct \(u\in\mathcal{X}\setminus\{s,t\}\) each appear in at least one honest pair \(\{s,u\}\) in the stream. Indeed, positive-side coverage forces \(\mathcal{X}\setminus\{s\}\subseteq\mathrm{Seen}(P)\), so each \(u\in\mathcal{X}\setminus\{s,t\}\) appears in at least one pair. At most \(k_0\) pairs are corrupted, so at most \(2k_0\) distinct vertices appear only in corrupted pairs; since \(|\mathcal{X}\setminus\{s,t\}|=\infty\), all but finitely many such \(u\) appear in some honest pair, which is necessarily \(\{s,u\}\) and omits \(t\). Each such honest pair occurrence increments \(a_n(t)\), so \(a_n(t)\to\infty\).
Therefore only examples appearing in the first \(k_0+1\) pairs ever have absence count at most \(k_0\); only finitely many false candidates can compete with \(s\), each with divergent absence count. From some stage on, \(s\) is the unique minimizer, and the identifier outputs \(h_s\) forever. ◻
Proof. \(k\textrm{-}\mathsf{Ctr}\mathrm{Id}\not\subseteq k\textrm{-}\mathsf{Txt}\mathrm{Id}\): the co-singleton class is in \(\mathrm{Fin}\text{-}\mathsf{Ctr}\mathrm{Id}\subseteq k\text{-}\mathsf{Ctr}\mathrm{Id}\) ([thm:co-singleton-fin-ctrid]). For the text side, \(k\text{-}\mathsf{Txt}\mathrm{Id}\subseteq 1\text{-}\mathsf{Txt}\mathrm{Id}\) (more corruption can only hurt the learner), so co-singleton \(\notin 1\text{-}\mathsf{Txt}\mathrm{Id}\) ([thm:text-fragile]) implies co-singleton \(\notin k\text{-}\mathsf{Txt}\mathrm{Id}\).
\(k\textrm{-}\mathsf{Txt}\mathrm{Id}\not\subseteq k\textrm{-}\mathsf{Ctr}\mathrm{Id}\): fix \(k\) and pick disjoint infinite \(A,B\subseteq\mathcal{X}\) with \(\mathcal{X}\setminus(A\cup B)\ne\varnothing\) (possible since \(\mathcal{X}\) is countably infinite); partition \(B\) into pairwise disjoint blocks \(B_0,B_1,\ldots\) with \(|B_i|=k+1\). Set \(\operatorname{supp}(h_i):=A\cup B_i\) and \(\mathcal{H}_k:=\{h_i:i\ge0\}\).
\(\mathcal{H}_k\in k\text{-}\mathsf{Txt}\mathrm{Id}\): in any \(k\)-corrupted text for \(h_i\), the entire \(B_i\) eventually appears; for \(j\ne i\), \(B_j\) is disjoint from \(\operatorname{supp}(h_i)\), so every observed element of \(B_j\) is a false positive. Since \(|B_j|=k+1>k\), no false block is fully observable. The identifier waits until some block has been entirely seen, then outputs the corresponding \(h_i\).
\(\mathcal{H}_k\notin k\text{-}\mathsf{Ctr}\mathrm{Id}\): the class fails already in the clean case. For \(i\ne j\), \(\operatorname{supp}(h_i)\) and \(\operatorname{supp}(h_j)\) are incomparable, intersect in \(A\), and miss \(\mathcal{X}\setminus(A\cup B_i\cup B_j)\ne\varnothing\), giving the non-covering barrier (N3) of [thm:ctr-eliminability]; [lem:pairwise-shared-presentation] produces a clean shared presentation, which is in particular a \(0\)-corrupted (hence \(k\)-corrupted) shared presentation. ◻
11 Membership Patterns and Higher-Order Shared Presentations↩︎
The shared-presentation criterion can be restated as a finite combinatorial condition on membership patterns, which is convenient for higher-order obstructions.
Proof. Necessity. For \(x\in R_\alpha\) with \(\alpha\ne\mathbf{0}\), \(x\) belongs to some target support; positive-side coverage forces \(x\) to appear in a pair \(\{x,y\}\) lying in \(\Delta(h_i)\) for every \(i\), so the pattern of \(y\) must equal \(\mathbf{1}-\alpha\).
Sufficiency. For each \(x\in\bigcup_i\operatorname{supp}(h_i)\), pick a witness \(y_x\) in the complementary cell (existing by hypothesis). Enumerate (or list-and-repeat) the union and emit the chosen pairs; each pair has patterns summing to \(\mathbf{1}\), so it lies in \(\Delta(h_i)\) for every \(i\). ◻
Example 4 (A higher-order obstruction). Partition \(\mathcal{X}\) into six infinite cells with patterns \(100,010,001\), \(110,101,011\), with \(R_{000}=R_{111}=\varnothing\). Each pairwise intersection \(\operatorname{supp}(h_i)\cap\operatorname{supp}(h_j)\) is infinite, but \(\operatorname{supp}(h_1)\cap\operatorname{supp}(h_2)\cap\operatorname{supp}(h_3)=R_{111}=\varnothing\). The realized nonzero patterns occur in complementary pairs (\(100\leftrightarrow011\), \(010\leftrightarrow101\), \(001\leftrightarrow110\)), so ?? holds and \(\{h_1,h_2,h_3\}\) admits a shared contrastive presentation. [prop:finite-family-obstruction] then rules out contrastive generation. Pairwise analysis is therefore insufficient for \(\mathsf{Ctr}\mathrm{Gen}\).
12 Discussion and Extensions↩︎
This section outlines several natural extensions of the contrastive learning framework that lie beyond the present paper’s scope. We give formal definitions where appropriate, articulate the structural difficulties that prevent direct transfer of our techniques, and pose open questions to seed future work.
12.1 Corrupted contrastive generation↩︎
The robustness analysis of 6 concerns identification. The parallel question for generation is the following.
Definition 14 (\(k\)-corrupted contrastive generator). For \(k\ge0\), a generator \(G\) is a \(k\)-corrupted contrastive generator for \(\mathcal{H}\) if for every \(h\in\mathcal{H}\) and every \(k\)-corrupted contrastive presentation \(P\) for \(h\) (11), there exists \(N\) such that \(G(P_{\le n})\in\operatorname{supp}(h)\setminus\mathrm{Seen}_n(P)\) for all \(n\ge N\). Write \(\mathcal{H}\in k\textrm{-}\mathsf{Ctr}\mathrm{Gen}\) when such a generator exists, and \(\mathrm{Fin}\textrm{-}\mathsf{Ctr}\mathrm{Gen}\) when a single \(G\) succeeds for every finite corruption budget.
Whether the closure-dimensional characterization ([thm:uniform-contrastive-generation]) extends to the corrupted regime is open. The basic difficulty is structural: closure-based generation rests on the edge-induced version space \(\mathcal{H}_{\Delta}(E)\), and a single corrupted pair \(p^*\notin\Delta(h)\) can eject the true target \(h\) from this version space. The remaining hypotheses in \(\mathcal{H}_{\Delta}(E_n(P))\) need not have supports contained in \(\operatorname{supp}(h)\), so the closure \(\langle E_n(P)\rangle^{\Delta}_{\mathcal{H}}\) can leak outside \(\operatorname{supp}(h)\), and the closure-based generator can output a non-positive of \(h\). By contrast, the identification reversal of 6 exploits an incidence invariant (the defect number) whose redundancy is preserved under finitely many inserted edges; the closure operator has no such redundancy.
Remark 3 (Identify-then-generate). The co-singleton class lies in \(\mathrm{Fin}\textrm{-}\mathsf{Ctr}\mathrm{Gen}\): [alg:absence-count] identifies the unique negative \(s^*\) in finite time, after which any unseen \(x\ne s^*\) is a novel positive of the target. This “identify-then-generate” template lifts \(\mathrm{Fin}\textrm{-}\mathsf{Ctr}\mathrm{Id}\) to \(\mathrm{Fin}\textrm{-}\mathsf{Ctr}\mathrm{Gen}\) for any class for which absence-count style identification succeeds. The converse direction (whether classes in \(\mathsf{Ctr}\mathrm{Gen}\setminus\mathsf{Ctr}\mathrm{Id}\) can achieve \(\mathrm{Fin}\textrm{-}\mathsf{Ctr}\mathrm{Gen}\)) may require new tools, since it cannot route through identification.
A natural target is a robust closure dimension \(\mathrm C_{\Delta}^{(k)}(\mathcal{H})\) measuring how far the closure can be pushed outside the target’s support by \(k\) adversarially inserted pairs; a quantitative theorem in the spirit of [thm:uniform-contrastive-generation] would then express \(k\textrm{-}\mathsf{Ctr}\mathrm{Gen}\) in terms of \(\mathrm C_{\Delta}^{(k)}\).
12.2 Statistical contrastive presentations↩︎
The presentations of [sec:problem,sec:robust] are adversarial: a contrastive presentation is any sequence satisfying XOR and positive-side coverage, and corruption is adversarial. A natural statistical relaxation samples pairs i.i.d.from a distribution over \([\mathcal{X}]^2\) supported on \(\Delta(h)\).
Definition 15 (\(\mu\)-random contrastive presentation). Fix a target \(h\) and a probability distribution \(\mu\) on \([\mathcal{X}]^2\) with \(\mathrm{supp}(\mu)\subseteq\Delta(h)\). A \(\mu\)-random contrastive presentation is a sequence \((p_t)_{t\ge1}\stackrel{\textrm{i.i.d.}}{\sim}\mu\). Positive-side coverage holds almost surely iff every \(x\in\operatorname{supp}(h)\) lies in some pair in \(\mathrm{supp}(\mu)\).
In this regime, the observed edge set \(E_n(P)\) becomes a random subgraph of \(\Delta(h)\). For natural pair distributions (e.g., uniform over a finite edge set, or a product distribution on the unknown bipartition), the induced random graph is a bipartite Erdős–Rényi-type model, conditioned on staying inside the cut \((\operatorname{supp}(h),\mathcal{X}\setminus\operatorname{supp}(h))\). This connects \(\mathsf{Ctr}\mathrm{Id}\) and \(\mathsf{Ctr}\mathrm{Gen}\) to community-detection problems on stochastic block models: recovering the cut from random crossing edges is structurally analogous to recovering the planted bipartition. We expect phase-transition phenomena: a critical edge density below which contrastive identification is statistically impossible, and above which spectral or message-passing algorithms succeed. The development of such a statistical theory is conceptually orthogonal to the asymptotic limit-learning paradigm of the present paper but sits naturally within its geometric framework.
12.3 Effective procedures↩︎
The contrastive identifier of [thm:ctrid-characterization] and the non-uniform generator of [thm:nonuniform-contrastive-generation] are information-theoretic: they consume the Angluin tell-tale family \(\{T_g\}_{g\in\mathcal{H}}\) and the per-level dimensions \(\{\mathrm C_{\Delta}(\mathcal{H}_m)\}_m\) as oracle inputs. Whether these constructions can be made effective depends on the available oracles and the computability of the input class.
12.3.0.1 Oracle hierarchy.
Three natural oracles on a hypothesis class span an increasing strength order:
a consistency oracle returning whether \(E\subseteq\Delta(g)\) for given finite \(E\subseteq[\mathcal{X}]^2\) and \(g\in\mathcal{H}\);
a closure-membership oracle returning whether \(x\in\langle E\rangle^{\Delta}_{\mathcal{H}}\) for given \(x\in\mathcal{X}\) and finite \(E\);
an ERM oracle returning some \(g\in\mathcal{H}_{\Delta}(E)\) if such \(g\) exists, else \(\bot\).
The closure-based generator of [thm:uniform-contrastive-generation] requires both the ERM oracle (to detect \(\mathcal{H}_{\Delta}(E)\ne\varnothing\)) and the closure-membership oracle (to enumerate \(\langle E\rangle^{\Delta}_{\mathcal{H}}\setminus\operatorname{V}(E)\)). The eligibility-based identifier of [thm:ctrid-characterization] additionally requires the tell-tale family \(\{T_g\}\), which 2 asserts to exist but does not construct.
By contrast, our absence-count algorithm is fully constructive: given the contrastive prefix as a finite list of pairs, the absence count \(a_n(x)\) is a primitive computable function of the input, and the minimization is over the finite set \(\mathrm{Seen}_n(P)\). No oracle on \(\mathcal{H}\) is needed. This places \(\mathrm{Fin}\textrm{-}\mathsf{Ctr}\mathrm{Id}\) for the co-singleton class in a strictly stronger constructivity class than the general \(\mathsf{Ctr}\mathrm{Id}\) characterization.
A natural target for future work is to identify combinatorial conditions on \(\mathcal{H}\) under which the eligibility-based identifier becomes effective from a closure-membership or ERM oracle alone, without requiring the tell-tale family as a separate input.
13 Additional Related Work↩︎
13.1 Identification in the limit↩︎
The classical paradigm originates with [1], with [3]’s tell-tale theorem giving the canonical positive-data characterization. Earlier work of [26] introduces the framework of pattern languages, a concrete subclass that admits positive-data identification despite the negative results of [1] on broader classes; this work foreshadows much of the structural analysis underlying tell-tale conditions. [27] considers an approximate variant of identification in which the learner is permitted small deviations from the target language, an early precursor to noise- and corruption-tolerant limit learning. The detailed survey is [5].
A line of recent work studies relaxed criteria for identification. [28] introduce a list-identification model in which the learner is allowed to output a small list of candidate languages, succeeding if the true target appears on the list, and they fully characterize list-identifiability. [7] characterize limit-learnability of recursive functions when the learner observes evaluations on every domain point. [8] augment Gold’s model with computational traces of the accepting machine and obtain identifiability across the Chomsky hierarchy with varying corruption tolerance, providing a complementary mechanism for circumventing Gold’s negative results.
13.2 Generation in the limit↩︎
[2] introduced generation in the limit, proving its universality on countable UUS classes; [4] reformulated the model in learning-theoretic notation and introduced the closure dimension that exactly characterizes uniform generation. The closure dimension of [4] is the direct positive-data ancestor of our contrastive closure dimension; we recover the same formalism with finite positive samples replaced by finite sets of pair constraints.
A recent thread examines refinements of the generation criterion. [9], [29] characterize generation under various breadth constraints and study trade-offs between hallucination and mode collapse. [30] introduce representative generation, requiring the generator to cover meaningful sub-collections of the target rather than producing arbitrary novel positives. [13], [31] explore facets of language generation in the limit and Pareto-optimal trade-offs in non-uniform generation. [12], [32] introduce density measures and partial-enumeration variants, providing fine-grained analyses across the space of possible enumeration orderings. [33] establish complexity barriers separating different generation modes and draw implications for learning. [34] study Banach density, which measures the breadth of language generation in the limit when strings live in a \(d\)-dimensional embedding.
A second thread targets noise tolerance. [10] analyze generation from noisy examples, [11] study generation under noise, loss, and feedback, and [35] push noise tolerance to infinite contamination budgets. [36] propose quantitative measures of noise in language generation, complementing the qualitative noise-tolerance results. [37] study generation in a replay-based model that captures forms of model collapse.
A third thread addresses semantic and structural extensions. [20] analyze union closure properties of generation, showing that countable closure can fail. [14] study the (im)possibility of automated hallucination detection. [15] extend generation to metric spaces, and [16] introduce agnostic notions of identification and generation. [17] formalize a setting of safe language generation in the limit. None of these works addresses the undirected-pair signal structure we study, but each contributes orthogonally to the broader generation landscape.