8 papers
Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back
Alon Cohen, Liad Erez, Steve Hanneke +4
The fundamental theorem of statistical learning states that binary PAC learning is governed by a single parameter -- the Vapnik-Chervonenkis (VC) dimension -- which determines both…
Fast Inference via Hierarchical Speculative Decoding
Clara Mohri, Haim Kaplan, Tal Schuster +2
Transformer language models generate text autoregressively, making inference latency proportional to the number of tokens generated. Speculative decoding reduces this latency witho…
Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning
Uri Sherman, Tomer Koren, Yishay Mansour
We study reinforcement learning (RL) in the agnostic policy learning setting, where the goal is to find a policy whose performance is competitive with the best policy in a given cl…
Bayesian Perspective on Memorization and Reconstruction
Haim Kaplan, Yishay Mansour, Kobbi Nissim +1
We introduce a new Bayesian perspective on the concept of data reconstruction, and leverage this viewpoint to propose a new security definition that, in certain settings, provably…
Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
Uri Sherman, Tomer Koren, Yishay Mansour
Modern policy optimization methods roughly follow the policy mirror descent (PMD) algorithmic template, for which there are by now numerous theoretical convergence results. However…
Of Dice and Games: A Theory of Generalized Boosting
Marco Bressan, Nataly Brukhim, Nicolò Cesa-Bianchi +4
Cost-sensitive loss functions are crucial in many real-world prediction problems, where different types of errors are penalized differently; for example, in medical diagnosis, a fa…