5 citations · 6 across the 17 of their papers we have counts for
17 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…
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…
Exploring Facets of Language Generation in the Limit
Moses Charikar, Chirag Pabbaraju
The recent work of Kleinberg & Mullainathan [KM24] provides a concrete model for language generation in the limit: given a sequence of examples from an unknown target language, the…
Quantifying the Gain in Weak-to-Strong Generalization
Moses Charikar, Chirag Pabbaraju, Kirankumar Shiragur
Recent advances in large language models have shown capabilities that are extraordinary and near-superhuman. These models operate with such complexity that reliably evaluating and…
Embedding Probability Distributions into Low Dimensional : Tree Ising Models via Truncated Metrics
Moses Charikar, Spencer Compton, Chirag Pabbaraju
Given an arbitrary set of high dimensional points in , there are known negative results that preclude the possibility of always mapping them to a low dimensional s…
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…
Harnessing the Power of Choices in Decision Tree Learning
Guy Blanc, Jane Lange, Chirag Pabbaraju +3
We propose a simple generalization of standard and empirically successful decision tree learning algorithms such as ID3, C4.5, and CART. These algorithms, which have been central t…
Multiclass Learnability Does Not Imply Sample Compression
Chirag Pabbaraju
A hypothesis class admits a sample compression scheme, if for every sample labeled by a hypothesis from the class, it is possible to retain only a small subsample, using which the…
Provable benefits of score matching
Chirag Pabbaraju, Dhruv Rohatgi, Anish Sevekari +3
Score matching is an alternative to maximum likelihood (ML) for estimating a probability distribution parametrized up to a constant of proportionality. By fitting the ''score'' of…
A Characterization of List Learnability
Moses Charikar, Chirag Pabbaraju
A classical result in learning theory shows the equivalence of PAC learnability of binary hypothesis classes and the finiteness of VC dimension. Extending this to the multiclass se…
Pitfalls of Gaussians as a noise distribution in NCE
Holden Lee, Chirag Pabbaraju, Anish Sevekari +1
Noise Contrastive Estimation (NCE) is a popular approach for learning probability density functions parameterized up to a constant of proportionality. The main idea is to design a…
Universal Approximation for Log-concave Distributions using Well-conditioned Normalizing Flows
Holden Lee, Chirag Pabbaraju, Anish Sevekari +1
Normalizing flows are a widely used class of latent-variable generative models with a tractable likelihood. Affine-coupling (Dinh et al, 2014-16) models are a particularly common t…
Efficient semidefinite-programming-based inference for binary and multi-class MRFs
Chirag Pabbaraju, Po-Wei Wang, J. Zico Kolter
Probabilistic inference in pairwise Markov Random Fields (MRFs), i.e. computing the partition function or computing a MAP estimate of the variables, is a foundational problem in pr…
Learning Functions over Sets via Permutation Adversarial Networks
Chirag Pabbaraju, Prateek Jain
In this paper, we consider the problem of learning functions over sets, i.e., functions that are invariant to permutations of input set items. Recent approaches of pooling individu…