12 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…
Relatively Smart: A New Approach for Instance-Optimal Learning
Shaddin Dughmi, Alireza F. Pour
We revisit the framework of Smart PAC learning, which seeks supervised learners which compete with semi-supervised learners that are provided full knowledge of the marginal distrib…
Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verification
Shaddin Dughmi, Mahdi Haghifam, Yusuf Hakan Kalayci
Many inference-time language-model pipelines combine a cheap reward signal with an expensive verifier, such as exact answer checking in mathematical reasoning or hidden-test execut…
A Theory of Time-Sensitive Language Generation: Sparse Hallucination Beats Mode Collapse
Atul Ganju, Travis McVoy, Shaddin Dughmi +1
We study language generation in the limit under a global preference ordering on strings, as introduced by Kleinberg and Wei. As is done in previous work, we aim for breadth, but im…
Proper Learnability and the Role of Unlabeled Data
Julian Asilis, Siddartha Devic, Shaddin Dughmi +2
Proper learning refers to the setting in which learners must emit predictors in the underlying hypothesis class , and often leads to learners with simple algorithmic forms (e.g.…
Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
Shaddin Dughmi, Yusuf Hakan Kalayci, Xinyu Liu
When uncertainty meets costly information gathering, a fundamental question emerges: which data points should we probe to unlock near-optimal solutions? Sparsification of stochasti…