Contrastive Identification and Generation in the Limit

• URL: http://arxiv.org/abs/2605.06211v1
• Date: Thu, 07 May 2026 13:14:51 GMT
• Title: Contrastive Identification and Generation in the Limit
• Abstract summary: We study contrastive identification and generation in the limit, where the learner observes a contrastive presentation of data.<n>We prove a sharp reversal under adversarial corruption: there exist classes identifiable from contrastive pairs under any finite corruption budget.<n>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.
• Score: 39.91890433860882
• License: http://creativecommons.org/licenses/by/4.0/
• 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 contrastive closure dimension (a contrasitive analogue of the closure dimension in Raman et al. [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.

Related papers

• Beyond Nodes vs. Edges: A Multi-View Fusion Framework for Provenance-Based Intrusion Detection [6.343815622517112]
  PROVfusion is a multi-view anomaly fusion framework for provenance-based intrusion detection.<n>It fuses heterogeneous anomaly signals through lightweight fusion schemes and determines the final anomaly decisions through a voting-based integration process.<n>Experiments on nine widely used benchmark entity datasets demonstrate that PROVfusion achieves higher detection accuracy and lower false-positive rates than single node- and edge-centric baselines.
  arXiv  Detail & Related papers  (2026-04-16T06:40:50Z)
• AC2L-GAD: Active Counterfactual Contrastive Learning for Graph Anomaly Detection [15.639397005651558]
  We propose AC2L-GAD, an Active Counterfactual Contrastive Learning framework.<n>We show that AC2L-GAD achieves competitive or superior performance compared to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2026-01-29T02:11:56Z)
• Fundamental limits to contrast reversal of self-fidelity correlations [0.0]
  In measurement design, it is common to engineer anti-contrast readouts.<n>We ask whether two evolutions can be made uniformly opposite over a broad input ensemble.<n>We adopt the Pearson correlation coefficient as a device-agnostic measure of global opposition between two evolutions.
  arXiv  Detail & Related papers  (2025-09-30T15:07:28Z)
• Pseudo Contrastive Learning for Graph-based Semi-supervised Learning [67.37572762925836]
  Pseudo Labeling is a technique used to improve the performance of Graph Neural Networks (GNNs) We propose a general framework for GNNs, termed Pseudo Contrastive Learning (PCL)
  arXiv  Detail & Related papers  (2023-02-19T10:34:08Z)
• Keywords and Instances: A Hierarchical Contrastive Learning Framework Unifying Hybrid Granularities for Text Generation [60.62039705180484]
  We propose a hierarchical contrastive learning mechanism, which can unify hybrid granularities semantic meaning in the input text.<n> Experiments demonstrate that our model outperforms competitive baselines on paraphrasing, dialogue generation, and storytelling tasks.
  arXiv  Detail & Related papers  (2022-05-26T13:26:03Z)
• Resolving label uncertainty with implicit posterior models [71.62113762278963]
  We propose a method for jointly inferring labels across a collection of data samples. By implicitly assuming the existence of a generative model for which a differentiable predictor is the posterior, we derive a training objective that allows learning under weak beliefs.
  arXiv  Detail & Related papers  (2022-02-28T18:09:44Z)
• A Low Rank Promoting Prior for Unsupervised Contrastive Learning [108.91406719395417]
  We construct a novel probabilistic graphical model that effectively incorporates the low rank promoting prior into the framework of contrastive learning. Our hypothesis explicitly requires that all the samples belonging to the same instance class lie on the same subspace with small dimension. Empirical evidences show that the proposed algorithm clearly surpasses the state-of-the-art approaches on multiple benchmarks.
  arXiv  Detail & Related papers  (2021-08-05T15:58:25Z)
• Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss [72.62029620566925]
  Recent works in self-supervised learning have advanced the state-of-the-art by relying on the contrastive learning paradigm. Our work analyzes contrastive learning without assuming conditional independence of positive pairs. We propose a loss that performs spectral decomposition on the population augmentation graph and can be succinctly written as a contrastive learning objective.
  arXiv  Detail & Related papers  (2021-06-08T07:41:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.