14 papers
Is Randomness Necessary for Adaptive Data Analysis?
Edith Cohen, Haim Kaplan, Yishay Mansour +2
The Adaptive Data Analysis (ADA) problem formalizes the challenge of preventing false discovery and overfitting when a dataset is repeatedly reused. Formally, our input is a datase…
Learning from Equivalence Queries, Revisited
Mark Braverman, Roi Livni, Yishay Mansour +2
Modern machine learning systems, such as generative models and recommendation systems, often evolve through a cycle of deployment, user interaction, and periodic model updates. Thi…
The Hidden Cost of Approximation in Online Mirror Descent
Ofir Schlisselberg, Uri Sherman, Tomer Koren +1
Online mirror descent (OMD) is a fundamental algorithmic paradigm that underlies many algorithms in optimization, machine learning and sequential decision-making. The OMD iterates…
A Theoretical Framework for Statistical Evaluability of Generative Models
Shashaank Aiyer, Yishay Mansour, Shay Moran +1
Statistical evaluation aims to estimate the generalization performance of a model using held-out i.i.d. test data sampled from the ground-truth distribution. In supervised learning…
The Sample Complexity of Multiclass and Sparse Contextual Bandits
Liad Erez, Fan Chen, Alon Cohen +4
We study contextual bandits in the stochastic i.i.d.\ setting, where a learner observes contexts drawn from an unknown distribution, selects actions from a finite set , and aims…
Learning Conditional Averages
Marco Bressan, Nataly Brukhim, Nicolo Cesa-Bianchi +4
We introduce the problem of learning conditional averages in the PAC framework. The learner receives a sample labeled by an unknown target concept from a known concept class, as in…