60 citations · 269 across the 42 of their papers we have counts for
54 papers
On the Sample Complexity of Active Learning with Membership Queries
Ganghua Wang, Shaddin Dughmi
This work revisits a fundamental question in active learning: how powerful is the ability to synthesize arbitrary queries? Compared to pool-based active learning, where the learner…
The Strong Secretary Conjecture is True for Linear Matroids
Kristóf Bérczi, Shaddin Dughmi, Vasilis Livanos +2
We prove a guarantee for the matroid secretary problem on linear matroids, therefore settling the strong secretary conjecture in this class of matroids. The result holds both…
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-…
Batched Pandora's Box
Shaddin Dughmi, Yusuf Hakan Kalayci, Vasilis Livanos +1
Motivated by numerous parallelizable stochastic search problems, most notable and timely among them being LLM inference-time scaling, we propose and study batched versions of the P…
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…