1 citations · 1 across the 13 of their papers we have counts for
12 papers · 1 filter
Optimal Randomized Proper Online Learning
Zachary Chase, Idan Mehalel
We prove that the optimal expected mistake bound of online learning a function class by a randomized proper learning algorithm is ,…
Stochastic Autoregressive Learning
Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel
Motivated by LLMs, which generate outputs by iteratively sampling from next-token distributions, we introduce a PAC-learning model for binary stochastic autoregressive learning. Th…
A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning
Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel
Autoregressive generation lies at the heart of the mechanism of large language models. It can be viewed as the repeated application of a next-token generator: starting from an inpu…
Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End
Steve Hanneke, Idan Mehalel, Shay Moran
Modern large language models generate text autoregressively, producing tokens one at a time. To study the learnability of such systems, Joshi et al. (COLT 2025) introduced a PAC-le…
Most Convolutional Networks Suffer from Small Adversarial Perturbations
Amit Daniely, Idan Mehalel
The existence of adversarial examples is relatively understood for random fully connected neural networks, but much less so for convolutional neural networks (CNNs). The recent wor…
Online Realizable Regression and Applications for ReLU Networks
Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel
Realizable online regression can behave very differently from online classification. Even without any margin or stochastic assumptions, realizability may enforce horizon-free (fini…
A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice
Zachary Chase, Shinji Ito, Idan Mehalel
We determine the minimax optimal expected regret in the classic non-stochastic multi-armed bandit with expert advice problem, by proving a lower bound that matches the upper bound…
Deterministic Apple Tasting
Zachary Chase, Idan Mehalel
In binary () online classification with apple tasting feedback, the learner receives feedback only when predicting . Besides some degenerate learning tasks, all previously…
Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs
Yuval Filmus, Steve Hanneke, Idan Mehalel +1
Consider the domain of multiclass classification within the adversarial online setting. What is the price of relying on bandit feedback as opposed to full information? To what exte…
Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension
Yuval Filmus, Steve Hanneke, Idan Mehalel +1
A classical result in online learning characterizes the optimal mistake bound achievable by deterministic learners using the Littlestone dimension (Littlestone '88). We prove an an…
On Optimal Learning Under Targeted Data Poisoning
Steve Hanneke, Amin Karbasi, Mohammad Mahmoody +2
Consider the task of learning a hypothesis class in the presence of an adversary that can replace up to an fraction of the examples in the training set with arbit…
A Resilient Distributed Boosting Algorithm
Yuval Filmus, Idan Mehalel, Shay Moran
Given a learning task where the data is distributed among several parties, communication is one of the fundamental resources which the parties would like to minimize. We present a…