cs.LGJan 30, 2026

Agnostic Language Identification and Generation

Authors: Mikael Møller Høgsgaard, Chirag Pabbaraju

Organizations: University of Oxford. · Stanford University.

Abstract

Recent works on language identification and generation have established tight statistical rates at which these tasks can be achieved. These works typically operate under a strong realizability assumption: that the input data is drawn from an unknown distribution necessarily supported on some language in a given collection. In this work, we relax this assumption of realizability entirely, and impose no restrictions on the distribution of the input data. We propose objectives to study both language identification and generation in this more general "agnostic" setup. Across both problems, we obtain novel interesting characterizations and nearly tight rates.

Figures & tables

Explore similar work

CardsList
  1. Safe Language Generation in the Limit

    Jan 13, 2026Antonios Anastasopoulos, Giuseppe Ateniese, Evgenios M. KornaropoulosLanguage IdentificationText Generation

  2. On Language Generation in the Limit with Bounded Memory

    May 28, 2026Jon Kleinberg, Anay Mehrotra, Amin Saberi +1Statistical Learning TheoryText Generation

  3. Differentially Private Language Generation and Identification in the Limit

    Apr 9, 2026Anay Mehrotra, Grigoris Velegkas, Xifan Yu +1Text GenerationDifferential Privacy