Contrastive Identification and Generation in the Limit

Abstract

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) ≠ 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 (a contrasitive analogue of the closure dimension in 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.