[2605.06211] Contrastive Identification and Generation in the Limit

Computer Science > Machine Learning arXiv:2605.06211 (cs) [Submitted on 7 May 2026] Title:Contrastive Identification and Generation in the Limit Authors:Xiaoyu Li, Andi Han, Jiaojiao Jiang, Junbin Gao View a PDF of the paper titled Contrastive Identification and Generation in the Limit, by Xiaoyu Li and 3 other authors View PDF HTML (experimental) Abstract:In the classical identification in the limit model of Gold [1967], a stream of positive examples is presented round by round, and the learner must eventually recover the target hypothesis. Recently, Kleinberg and Mullainathan [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, which encode relationships between examples rather than labels of individual ones. We initiate the 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 [1980]'s tell-tale condition), a combinatorial dimension called contrast...