8 papers · 1 filter
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…
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…
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…
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'…
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…