6 papers
Transductive and Learning-Augmented Online Regression
Vinod Raman, Shenghao Xie, Samson Zhou
Motivated by the predictable nature of real-life in data streams, we study online regression when the learner has access to predictions about future examples. In the extreme case,…
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…
Representative Language Generation
Charlotte Peale, Vinod Raman, Omer Reingold
We introduce "representative generation," extending the theoretical framework for generation proposed by Kleinberg et al. (2024) and formalized by Li et al. (2024), to additionally…
Faster Rates for Private Adversarial Bandits
Hilal Asi, Vinod Raman, Kunal Talwar
We design new differentially private algorithms for the problems of adversarial bandits and bandits with expert advice. For adversarial bandits, we give a simple and efficient conv…
Tracking the Best Expert Privately
Aadirupa Saha, Vinod Raman, Hilal Asi
We design differentially private algorithms for the problem of prediction with expert advice under dynamic regret, also known as tracking the best expert. Our work addresses three…
Generation from Noisy Examples
Ananth Raman, Vinod Raman
We continue to study the learning-theoretic foundations of generation by extending the results from Kleinberg and Mullainathan [2024] and Li et al. [2024] to account for noisy exam…