PaperlayerView exact revision on arXiv

Source-linked AI summary

A Reverse-Gold Theorem: Positive-Data Identification by Substrate-Bounded Contrastive Learners

Rakesh Sengupta

arXiv:2610.28747v2stat.MLcs.CLcs.LGq-bio.NC

TL;DR

Gold’s theorem rules out identification of arbitrary languages in superfinite classes from positive data alone. This paper uses a fixed contrast operator and bounded-capacity scorer to learn from learner-generated perturbations, establishing conditional ranking guarantees and a normalization-free generator.

  • Problem

    Gold’s theorem means a learner cannot identify an arbitrary language in a superfinite class from positive presentations alone.

    Source: §1 · p. 2

  • Method

    A bounded-capacity scorer contrasts each positive string with perturbations generated by a fixed operator, framing the task as identifying the positive among its orbit.

    Source: §2 · p. 6, §3 · p. 7

  • Results

    Under saturated realization and an orbit-pure operator, the learner achieves positive-data PAC conditional identification; the contrastive-loss argument gives an ε^-2 misranking rate.

    Source: §1 · p. 2, §9 · p. 16

  • Takeaways & Limitations

    Composing the operator with the learned scorer yields a normalization-free Metropolis–Hastings sampler with a score-reweighted stationary law on finite components.

    Source: §1 · p. 3

    The guarantees are weaker than identifying the full language: one-step ranking does not certify strings outside the operator’s closure, and closure rejection requires a margin condition.

    Source: §3 · p. 7, §4 · p. 11

Abstract

from arXiv · show

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 $\varepsilon$-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/\varepsilon$. 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 $\varepsilon^{-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.

1 Introduction

The paper asks whether a target language can be learned from positive data alone when a fixed structural operator supplies candidate negatives. It proves a conditional-ranking guarantee for a bounded-capacity contrastive learner and describes its limits and extensions.

1 Introduction

  • Gold's theorem rules out identifying arbitrary languages in superfinite classes from positive presentations alone, motivating a weaker criterion than exact convergence.The usual alternatives include external negative evidence, a restricted hypothesis space, or approximate PAC convergence.Source: §1 · pp. 1–2
  • A target-independent recursive contrast operator generates structurally bounded perturbations, which a bounded-capacity scorer evaluates through an InfoNCE objective.The learner uses these perturbations as candidate negatives without knowing which are outside the target language.Source: §1 · p. 2
  • Under saturated realizability and an orbit-pure operator, InfoNCE training yields PAC conditional identification from positive data, with polynomial sample complexity.The guarantee ranks all but an ε-fraction of positives above every out-of-language string in each positive's orbit.Source: §1 · p. 2
  • The misranking bound follows from InfoNCE loss geometry, giving an ε^-2 sample-complexity rate and an explicit additive approximation gap.The loss floor and the increase forced by misranking yield a linear relation between misranking probability and excess loss.Source: §1 · p. 2
  • The approximation gap measures in-language perturbation collisions and vanishes for orbit-pure operators, but is strictly positive under the stated collision condition.Under saturated realizability it is bounded by the expected log-collision count.Source: §1 · pp. 2–3
  • Under an additional margin condition, conditional ranking lifts to a global membership classifier, while the same operator and scorer define a normalization-free Metropolis–Hastings sampler.On finite components, the sampler's stationary law is the score-reweighted measure under the symmetrized operator.Source: §1 · pp. 2–3
  • The paper gives an end-to-end zero-gap instance for a strictly local language, relates its framework to substitutable context-free and subregular classes, and conjectures an extension to mildly context-sensitive languages.The stated cognitive motivation is separate; the paper develops the mathematics.Source: §1 · p. 3

2 Formal Setup

The setup combines a target-independent perturbation operator, a bounded-capacity real-valued scorer, and an input distribution supported on the target language. Faithfulness requires the operator to expose out-of-language examples and the scorer to separate them; stronger saturated realizability controls the collision gap.

2 Formal Setup

  • The learner receives i.i.d. positive examples from a distribution supported on the target, which need not cover the entire language.The orbit-size bound is required only on the distribution's support, not globally over all strings.Source: §2 · pp. 3–4
  • A recursive contrast operator assigns each string a finite orbit of structurally bounded perturbations and is defined uniformly without reference to the target.Its recursivity requires perturbations of structural parts to remain available when those parts are composed.Source: §2 · p. 3
  • The theory covers a fixed bracketing, not iterative re-estimation of bracketing on the same sample; sample splitting would restore pass-wise independence.The joint fixed point of bracketing and scorer is presented as a procedure, not a theorem.Source: §2 · p. 4
  • The discriminative hypothesis class contains real-valued scorers with bounded empirical Rademacher complexity, and every score is bounded in magnitude by B.The score bound supports uniform-convergence arguments for the InfoNCE log-loss.Source: §2 · p. 4
  • Pointwise faithfulness requires boundary support from the operator and realizability by a scorer that ranks positives above out-of-language orbit elements.The two clauses are logically independent: one concerns the operator and target, the other the scorer and target.Source: §2 · p. 5
  • Saturated realizability additionally allows a scorer to assign B to positives and −B to out-of-language orbit elements, bounding the approximation gap by collisions.That bound vanishes for orbit-pure operators; a strict realizer alone need not achieve saturation.Source: §2 · p. 5
  • Uniform faithfulness requires one operator–scorer pair to be faithful for every language in a class, and establishing it for mildly context-sensitive classes remains open.The main theorem instead uses pointwise faithfulness for the particular target being learned.Source: §2 · p. 5
  • InfoNCE is equivalently the expected multinomial-logistic loss for identifying the positive among itself and its orbit perturbations.Its empirical version averages this objective over the positive training sample.Source: §2 · pp. 5–6

3 Main Result

Theorem 10 bounds one-step conditional misranking by an approximation gap plus a sample-estimation term; under saturated realizability and orbit purity, the gap vanishes. This is PAC conditional identification relative to the input distribution and operator, not unconditional identification of the language.

3 Main Result

  • The approximation gap measures the best scorer’s excess loss over the mean per-example floor; saturated realizability bounds it by E[log(1 + m+(x))].Here m+(x) counts in-language perturbations in the positive’s orbit.Source: §3 · pp. 6, 9
  • Theorem 10 bounds misranking by the approximation gap divided by log 2 − ℓmax_0, plus ε, with probability at least 1 − δ.The bound applies directly to the empirical maximizer and needs no population-maximizer assumption.Source: §3 · pp. 6, 8
  • Under saturated realizability and orbit purity, the approximation gap is zero, so the trained scorer misranks at most an ε-fraction of positives with probability at least 1 − δ.The guarantee ranks each positive above every out-of-language string in its own orbit.Source: §3 · pp. 6, 9
  • Theorem 10 certifies only one-step ranking on each positive’s own orbit; a global membership classifier requires uniform separation and positive-only threshold calibration.Under that margin condition, the classifier rejects every ill-formed string in the operator closure and misses at most an ε-fraction of positives.Source: §3 · pp. 7, 10
  • A misranked positive incurs loss at least log 2, while every example has a per-example loss floor, directly calibrating excess loss to misranking.The condition B > 1/2 log M ensures ℓmax_0 < log 2, making the calibration denominator positive.Source: §3 · pp. 8, 10
  • When a positive’s orbit contains a supported positive with its own nonempty orbit, collisions impose a strictly positive approximation gap for any scorer.The two examples require contradictory scores for the shared perturbation; this is an intrinsic self-supervision limitation, not proof slack.Source: §3 · p. 9

4 Where the Bias Lives

The paper locates its inductive bias in a fixed structural operator, a finite-capacity scorer, and realizability, each with a distinct role. The resulting guarantee concerns a one-step criterion and does not identify all of the target language.

4 Where the Bias Lives

  • The fixed operator R exposes the target boundary through structural perturbations; in-language outputs raise the collision bound and can increase the approximation gap.The operator is the construction’s substantive structural commitment, rather than a restriction on which languages are possible.Source: §4 · p. 11
  • Finite capacity κ makes sample complexity polynomial, while realizability places a correct target ranking in H but does not give the learner its parameters.The approximation gap also reflects operator collisions and limitations of H; saturated realizability bounds it by E[log(1 + m+(x))].Source: §4 · p. 11
  • The theorem’s one-step ranking and its closure-based classification are weaker than identifying L: neither certifies strings outside ClR(supp(pd)).Even perfect one-step ranking need not control closure elements whose violations are long-distance; reaching natural target classes with a fixed operator remains open.Source: §4 · p. 11

5 From Discrimination to Production

The operator and trained scorer also define a Metropolis–Hastings generator using symmetrized proposals. Its behavior is limited to the seed’s connected component, with a stationary sampling law only for finite components.

5 From Discrimination to Production

  • The generator proposes uniformly from the symmetrized neighborhood, accepts using the scorer, and stays within the seed’s connected component.The neighborhood must be finite at each state, though no uniform bound is required.Source: §5 · p. 12
  • On a finite seed component, the induced chain has stationary law proportional to exp(s(x)); on an infinite component, it has no stationary probability law.It remains a reversible local explorer on infinite components, and its acceptance rule requires no global partition function.Source: §5 · pp. 12–13
  • The generator may explore only one of several components, and the paper gives no mixing-time bound; polynomial mixing remains an open practical requirement.Reverse moves are needed for non-self-inverse operators such as deletion.Source: §5 · p. 12

6 A Worked Instance and Two Correspondences

The framework is verified end to end only for a strictly 2-local target; the other language-class connections are correspondences whose required hypotheses remain unestablished. Substitutability and subregularity suggest possible operators and scorers, while in-language edits make collision accounting important.

6 A Worked Instance and Two Correspondences

  • The hypotheses are verified end to end for a strictly 2-local target, but the Clark–Eyraud and subregular cases remain correspondences rather than verified instantiations.A full instantiation would require establishing boundary support, a capacity bound, and (saturated) realizability for the stated operator and scorer.Source: §6 · p. 13

6.1 Substitutable context-free languages

  • For substitutable context-free languages, substitutions across matching contexts are collisions, while substitutions across non-matching contexts provide out-of-language negatives.The collision-quantified bound is non-vacuous only if most positives admit no grammatical substitution, which is not typical for unrestricted substitution.Source: §6.1 · p. 13

6.2 Subregular classes

  • For subregular classes, finite observability yields linear separability over predicate embeddings, and clipped linear factor-count scorers can represent forbidden-pattern membership.This is a correspondence; the framework does not verify all required hypotheses for a specific class and operator.Source: §6.2 · pp. 13–14
  • Generic segment edits need not be orbit-pure, but an operator can be chosen to make purity hold identically on a strictly 2-local target.The appendix also quantifies what goes wrong when the chosen operator is not pure.Source: §6.2 · p. 14

7 Related Work

The related work connects internally generated contrasts to implicit negative evidence, contrastive-learning theory, and active language learning. The paper distinguishes its deterministic within-orbit contrasts and passive conditional-ranking guarantee from those prior settings.

Implicit negatives and the size principle

  • The contrastive construction parallels the Bayesian size principle by using expected-but-unobserved structure as implicit negative evidence, while avoiding global normalization.The size principle computes expected frequencies in a generative model; this construction generates perturbations with R and treats their dispreference as informative.Source: §7 · p. 14

Statistical theory of contrastive estimation

  • Unlike analyses with i.i.d. marginal negatives, this setting uses dependent, deterministic perturbations R(x), motivating conditional within-orbit guarantees and a collision penalty.The paper relates that penalty to class-collision analysis and identifies dependence-aware analysis as a route to sharper bounds.Source: §7 · p. 14

Relation to active (query) learning

  • Unlike active L∗ learning, the construction uses only positive examples and learner-made contrasts; conditional ranking is weaker than exact identification and dispenses with both query oracles.Boundary support makes the proposed candidates informative often enough; the paper connects the criterion's trade-off to the closure-versus-target gap.Source: §7 · p. 14

8 Open Problems

The open problems ask whether fixed bounded-fan-out operators cover mildly context-sensitive languages and whether the framework's rates and collision accounting can be improved. The proposed linguistic scope rests on an empirical bounded-fan-out hypothesis, not a result established by the theorem.

8.1 The mildly context-sensitive conjecture

  • The bounded-fan-out MCS conjecture proposes polynomial-capacity hypotheses and a non-vacuous conditional-ranking guarantee when the operator closure is polynomially bounded.The conjecture requires saturated realizability and a bounded expected collision term; Rtrain uses dependency-breaking moves, while dependency-preserving co-substitutions serve closure and generation.Source: §8.1 · p. 15
  • For cross-serial dependencies and long-distance agreement, breaking one linked site can expose an out-of-language string, but additive window scorers may fail realizability.Co-substitution preserves linked dependencies and can create training collisions, while supplying moves needed by closure and generation.Source: §8.1 · p. 15

8.2 Bounded fan-out and what it bets on

  • The empirical bet is that human language has some fixed small fan-out; an attested dependency requiring unbounded fan-out to expose would refute it.The text says no clear counterexample is known, but whether this bounded-fan-out hypothesis holds is empirical and unsettled.Source: §8.2 · pp. 15–16

8.3 Sharper rates and collision-aware calibration

  • Open rate questions include reducing the conservative (M + 1) factor and possibly improving the exact-realizability rate from ε^-2 to ε^-1.A separate open question is whether refined calibration can remove the collision term, which may dominate for collision-heavy operators such as constituent substitution.Source: §8.3 · p. 16

9 Conclusion

The paper's result is conditional ranking from positive data using a fixed recursive contrast operator and bounded-capacity scorer, with learner-generated negatives. The guarantee depends on substrate realizability and orbit purity, while global classification requires a margin condition and the mildly context-sensitive scope remains conjectural.

9 Conclusion

  • A fixed recursive contrast operator and bounded-capacity scorer yield polynomial-sample conditional ranking from positive data when the substrate realizes separation and the operator is orbit-pure.Otherwise, the guarantee includes an explicit approximation gap; the learner constructs negatives without computing a global normalizing constant.Source: §9 · p. 16
  • The contrastive-loss geometry gives an ε^-2 misranking rate, and the ranking guarantee lifts to a global classifier under a margin condition.The approximation gap reflects substrate inadequacy and orbit collisions, and vanishes under saturated realizability with an orbit-pure operator.Source: §9 · p. 16
  • The same operator and scorer also yield a normalization-free generator, making the construction both discriminative and generative in a controlled sense.Source: §9 · p. 16
  • Whether a fixed bounded-fan-out operator suffices for the mildly context-sensitive range remains open.The paper locates the remaining bias in the operator, capacity bound, and realizability clause.Source: §9 · p. 16

Appendix A. Deferred Proofs

The deferred proofs establish the scorer’s excess-risk bound from uniform loss-class control, then derive a threshold classifier and analyze the operator-based Metropolis–Hastings chain.

Appendix A. Deferred Proofs

  • The per-example contrastive loss has a floor determined by the positive score and negative scores; varying orbit sizes require the pointwise floor rather than ℓmax₀.The loss is minimized when the positive score is B and perturbation scores are −B; its maximum grows with orbit size.Source: Appendix A · p. 18
  • Uniform deviation control yields a one-sided excess-risk bound for the empirical maximizer, using the loss-class Rademacher term and a bounded-loss concentration term.The loss-class complexity is bounded by vector contraction applied to transformed samples in the operator-expanded domain.Source: Appendix A · p. 18
  • The Metropolis–Hastings chain is reversible with respect to the score-weighted measure and stays within the starting component; finite components yield a stationary probability law, but infinite ones do not.Acceptance uses score differences, so no global normalizer is computed; recurrence or transience on an infinite component remains open.Source: Appendix A · p. 19
  • Under uniform separation, a threshold learned from held-out positives gives no false positives among reachable out-of-language strings and at most an ε-fraction of false negatives.The sample condition for the false-negative step is N ≥ ε⁻¹ log(2/δ).Source: Appendix A · p. 19

Appendix B. A Worked Instance, and Its Collision-Heavy Shadow

The worked instance uses b-doubling to generate only out-of-language perturbations for a binary strictly 2-local language, permitting a zero approximation gap with an explicit bounded scorer. Single-symbol substitution can instead create in-language collisions that make the bound vacuous for collision-heavy distributions.

A Worked Instance

  • For strings without factor bb, doubling any b creates a bb factor, so every perturbation of a positive lies outside the target language.The operator is universal, local, and recursive; strings in a* have empty orbits, so the example excludes them from the positive-data support.Source: Appendix B · p. 20
  • A bounded affine bigram scorer assigns B to target strings and −B to strings containing bb, giving saturated realizability and approximation gap aH = 0.The resulting conditional misranking probability is at most ε.Source: Appendix B · p. 20
  • On support strings of length at most K, the orbit bound is M ≤ ⌈K/2⌉, the sufficient score bound grows logarithmically with K, and capacity grows as B²K².The example satisfies boundary support, saturated realizability, and orbit purity with an explicit bounded-weight scorer.Source: Appendix B · p. 20

Collision-Heavy Shadow

  • Single-symbol substitution can map aba to the positive aaa, forcing contradictory score demands and a strictly positive approximation gap when both occur in the support.For collision-heavy input distributions, the normalized gap can approach one, making the bound vacuous; operator choice therefore matters, not only hypothesis class.Source: Appendix B · pp. 20–21
Loading 2610.28747v2…