16 papers
When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification
Julian Asilis, Shaddin Dughmi, Chirag Pabbaraju
Optimal learners are tailored to exploit the i.i.d.\ data assumption underlying the classic PAC model. What if an i.i.d.\ training sample were corrupted with correctly labeled exam…
Optimal Unambiguous DNFs and Alon-Saks-Seymour
Chirag Pabbaraju
We construct unambiguous DNFs having width but -certificate complexity . By utilizing the special structure of these DNFs, we prove a lifting theorem with a const…
Language Identification with Succinct Machine-Independent Traces
Moses Charikar, Jon Kleinberg, Chirag Pabbaraju
Motivated by the power of large language models, there has been renewed interest in the Gold-Angluin model of language identification in the limit, with an eye toward variants of t…
Globally Consistent Coloring Schemes for Language Identification
Moses Charikar, Jon Kleinberg, Chirag Pabbaraju
We study how little extra information is needed to make adversarial language learning possible. In Gold's model of language identification in the limit, a learner is given an enume…
Space-Efficient Language Generation in the Limit
Nicolas Flammarion, Chirag Pabbaraju, Hristo Papazov +2
We initiate a resource-aware theory of \textit{language generation in the limit} under the minimal constraint of space efficiency. In our framework, a learner observes an adversari…
From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization
Moses Charikar, Chirag Pabbaraju, Ambuj Tewari
Curvature adaptivity is a classical theme in online optimization: for convex Lipschitz losses, adaptive methods interpolate between the optimal regret for general con…
The Optimal Sample Complexity of Multiclass and List Learning
Chirag Pabbaraju
While the optimal sample complexity of binary classification in terms of the VC dimension is well-established, determining the optimal sample complexity of multiclass classificatio…
An Optimal Algorithm for Stochastic Vertex Cover
Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju +5
The goal in the stochastic vertex cover problem is to obtain an approximately minimum vertex cover for a graph that is realized by sampling each edge independently with s…
A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
Sumegha Garg, Jabari Hastings, Chirag Pabbaraju +1
We present a unified framework for proving memory lower bounds for multi-pass streaming algorithms that detect planted structures. Planted structures -- such as cliques or biclique…
The Sample Complexity of Replicable Realizable PAC Learning
Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju +1
In this paper, we consider the problem of replicable realizable PAC learning. We construct a particularly hard learning problem and show a sample complexity lower bound with a clos…
Learning with Monotone Adversarial Corruptions
Kasper Green Larsen, Chirag Pabbaraju, Abhishek Shetty
We study the extent to which standard machine learning algorithms rely on exchangeability and independence of data by introducing a monotone adversarial corruption model. In this m…
Lower Bounds for Greedy Teaching Set Constructions
Spencer Compton, Chirag Pabbaraju, Nikita Zhivotovskiy
A fundamental open problem in learning theory is to characterize the best-case teaching dimension of a concept class with finite VC dimensi…
Proofs as Explanations: Short Certificates for Reliable Predictions
Avrim Blum, Steve Hanneke, Chirag Pabbaraju +1
We consider a model for explainable AI in which an explanation for a prediction consists of a subset of the training data (if it exists) such that all classifiers $h'…
New and Improved Bounds for Markov Paging
Chirag Pabbaraju, Ali Vakilian
In the Markov paging model, one assumes that page requests are drawn from a Markov chain over the pages in memory, and the goal is to maintain a fast cache that suffers few page fa…
A Characterization of List Regression
Chirag Pabbaraju, Sahasrajit Sarmasarkar
There has been a recent interest in understanding and characterizing the sample complexity of list learning tasks, where the learning algorithm is allowed to make a short list of $…
Credit Attribution and Stable Compression
Roi Livni, Shay Moran, Kobbi Nissim +1
Credit attribution is crucial across various fields. In academic research, proper citation acknowledges prior work and establishes original contributions. Similarly, in generative…