60 citations · 269 across the 42 of their papers we have counts for
12 papers · 1 filter
Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning
Shaddin Dughmi, Alireza F. Pour
We continue the study of relatively smart learning, introduced by Dughmi and Pour (2026), which asks a supervised learner to compete, marginal by marginal, with every distribution-…
Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper Learning
Julian Asilis, Shaddin Dughmi, Vatsal Sharan +3
Two of the most fundamental questions in statistical learning theory are the following: which prediction problems are learnable, and how should they be learned? For the former, ele…
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…
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…
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…