14 papers
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…
Strategic PAC Learnability via Geometric Definability
Yuval Filmus, Shay Moran, Elizaveta Nesterova +2
Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision. A central question is…
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…
Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale
Shashaank Aiyer, Yishay Mansour, Shay Moran +2
We study the optimal scale at which real-valued function classes exhibit uniform convergence and learnability. Our main result establishes a scale-sensitive generalization of the f…
Online Set Learning from Precision and Recall Feedback
Lee Cohen, Yishay Mansour, Shay Moran +1
We consider the problem of learning an unknown subset of a domain in an online setting. In each round , the learner predicts a set of items and receive…