9 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…
Load Balancing under Adaptive Bin Deletions
Haim Kaplan, Shay Sapir, Uri Stemmer
We analyze a balls-and-bins game against an adaptive adversary that sequentially deletes bins. Starting with balls distributed across bins, the adversary deletes a bin in e…
Cost-Aware Learning
Clara Mohri, Amir Globerson, Haim Kaplan +2
We consider the problem of Cost-Aware Learning, where sampling different components of a finite-sum objective incurs different costs. The objective is to reach a target error while…
When Can Transformers Count to n?
Gilad Yehudai, Haim Kaplan, Guy Dar +4
Large language models based on the transformer architecture can solve highly complex tasks, yet their fundamental limitations on simple algorithmic problems remain poorly understoo…
Optimal Learning from Label Proportions with General Loss Functions
Lorne Applebaum, Travis Dick, Claudio Gentile +2
Motivated by problems in online advertising, we address the task of Learning from Label Proportions (LLP). We introduce a novel and versatile low-variance debiasing methodology to…
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…