Contrastive Identification and Generation in the Limit

In the classical *identification in the limit* model of Gold [Inf. Control, 1967], a stream of positive examples is presented round by round, and the learner must eventually recover the target hypothesis. Recently, Kleinberg and Mullainathan [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 [Angluin, Inf. Control 1980]), a combinatorial dimension called *contrastive closure dimension* extending the closure dimension of Raman et al. [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.