9 papers
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…
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 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…
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…