A Reverse-Gold Theorem: Positive-Data Identification by Substrate-Bounded Contrastive Learners
Abstract
Gold's theorem shows that no learner can identify an arbitrary language in a superfinite class from positive presentations alone. We prove a positive result of a different shape. Fix an innate \emph{recursive contrast operator} R mapping any string to a finite set of structurally bounded perturbations of it, and a discriminative scorer of bounded capacity trained by InfoNCE-style contrastive estimation \citep{vandenoord2018,macollins2018} on self-generated perturbations. Under a faithfulness condition relating operator, scorer, and target, the trained scorer achieves \emph{PAC conditional identification} from positive data alone: with high probability it ranks all but an ε-fraction of positives above every out-of-language perturbation in their own orbit, with sample complexity polynomial in the capacity, the orbit size, the score bound, and 1/ε. The negatives are constructed by the learner, not supplied by an oracle, and no global normalizing constant over strings is ever computed. The misranking bound follows from the geometry of the contrastive loss---per-example loss floors plus a definite loss increment under misranking---yielding an ε−2 rate, together with an explicit approximation gap that quantifies the cost of in-language (``colliding'') perturbations and vanishes for orbit-pure operators. The ranking guarantee lifts to a global membership classifier under a margin condition, and the same operator composed with the learned scorer is a normalization-free Metropolis--Hastings generator. We instantiate the hypotheses for substitutable context-free languages \citep{clarkeyraud2007} and the subregular classes \citep{heinz2010,hayashikamigaito2025}, and state an open conjecture locating the construction in the mildly context-sensitive hierarchy.
Related
- A global–local momentum contrastive framework with critical feature calibration for field plant disease identification in precision agriculture
- Positive effects of larval quality on early barnacle recruitment through adaptive substrate selection
- Genome-Wide Identification and Comparative Analysis of the TCP Transcription Factor Family in Three Glycyrrhiza Species Reveals GuTCP16 as a Positive Regulator of Salt Tolerance.
- Rapid identification and antimicrobial susceptibility testing of pathogenic microorganisms from positive blood cultures
- Retrieval Practice and the Acquisition of English Spelling Rules and Etymological Knowledge in Elementary EFL Learners
BibTeX
@misc{sengupta2026reversegold,
title = {{A Reverse-Gold Theorem: Positive-Data Identification by Substrate-Bounded Contrastive Learners}},
author = {Rakesh Sengupta},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.28747},
eprint = {2610.28747},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.28747},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - A Reverse-Gold Theorem: Positive-Data Identification by Substrate-Bounded Contrastive Learners
AU - Rakesh Sengupta
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2610.28747
UR - https://arxiv.org/abs/2610.28747
AB - Gold's theorem shows that no learner can identify an arbitrary language in a superfinite class from positive presentations alone. We prove a positive result of a different shape. Fix an innate \emph{recursive contrast operator} R mapping any string to a finite set of structurally bounded perturbations of it, and a discriminative scorer of bounded capacity trained by InfoNCE-style contrastive estimation \citep{vandenoord2018,macollins2018} on self-generated perturbations. Under a faithfulness condition relating operator, scorer, and target, the trained scorer achieves \emph{PAC conditional identification} from positive data alone: with high probability it ranks all but an ε-fraction of positives above every out-of-language perturbation in their own orbit, with sample complexity polynomial in the capacity, the orbit size, the score bound, and 1/ε. The negatives are constructed by the learner, not supplied by an oracle, and no global normalizing constant over strings is ever computed. The misranking bound follows from the geometry of the contrastive loss---per-example loss floors plus a definite loss increment under misranking---yielding an ε^−2 rate, together with an explicit approximation gap that quantifies the cost of in-language (``colliding'') perturbations and vanishes for orbit-pure operators. The ranking guarantee lifts to a global membership classifier under a margin condition, and the same operator composed with the learned scorer is a normalization-free Metropolis--Hastings generator. We instantiate the hypotheses for substitutable context-free languages \citep{clarkeyraud2007} and the subregular classes \citep{heinz2010,hayashikamigaito2025}, and state an open conjecture locating the construction in the mildly context-sensitive hierarchy.
ER -