60 citations · 269 across the 42 of their papers we have counts for
5 papers · 1 filter
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…
Optimal Stopping vs Best-of- for Inference Time Optimization
Yusuf Kalayci, Vinod Raman, Shaddin Dughmi
Large language model (LLM) generation often requires balancing output quality against inference cost, especially when using multiple generations. We introduce a new framework for i…
Local Regularizers Are Not Transductive Learners
Sky Jafar, Julian Asilis, Shaddin Dughmi
We partly resolve an open question raised by Asilis et al. (COLT 2024): whether the algorithmic template of local regularization -- an intriguing generalization of explicit regular…
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.…
PAC Learning is just Bipartite Matching (Sort of)
Shaddin Dughmi
The main goal of this article is to convince you, the reader, that supervised learning in the Probably Approximately Correct (PAC) model is closely related to -- of all things -- b…