8 papers
Agnostic Language Identification and Generation
Mikael Møller Høgsgaard, Chirag Pabbaraju
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 r…
A Characterization of List Language Identification in the Limit
Moses Charikar, Chirag Pabbaraju, Ambuj Tewari
We study the problem of language identification in the limit, where given a sequence of examples from a target language, the goal of the learner is to output a sequence of guesses…
Testing with Non-identically Distributed Samples
Shivam Garg, Chirag Pabbaraju, Kirankumar Shiragur +1
We examine the extent to which sublinear-sample property testing and estimation apply to settings where samples are independently but not identically distributed. Specifically, we…
A Simple Geometric Proof of the Optimality of the Sequential Probability Ratio Test for Symmetric Bernoulli Hypotheses
Chirag Pabbaraju, Gregory Valiant, Rishi Verma
This paper revisits the classical problem of determining the bias of a weighted coin, where the bias is known to be either or , while…
Pareto-optimal Non-uniform Language Generation
Moses Charikar, Chirag Pabbaraju
Kleinberg and Mullainathan (2024) recently proposed an interesting model for language generation in the limit: Given a countable collection of languages, and an adversary enumerati…
Relating Misfit to Gain in Weak-to-Strong Generalization Beyond the Squared Loss
Abhijeet Mulgund, Chirag Pabbaraju
The paradigm of weak-to-strong generalization constitutes the training of a strong AI model on data labeled by a weak AI model, with the goal that the strong model nevertheless out…