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…
Incremental Dominating Set
Ilan Doron Arad, Jonathan Gal, Seffi Naor
Dominating Set is a fundamental problem in graph theory: given a graph, find a minimum-weight subset of vertices such that every vertex is either selected or adjacent to a selected…
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…
Mathematical perspective on genetic algorithms with optimization guided operators
Anna Brandenberger, Ilan Doron-Arad, Elchanan Mossel
Recent work in ML applies genetic algorithms at inference time to iteratively improve solutions to optimization problems. The basic mutation and recombination operators involved ar…
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…
An Algorithm-to-Contract Framework without Demand Queries
Ilan Doron-Arad, Hadas Shachnai, Gilad Shmerler +1
Consider costly and time-consuming tasks that add up to the success of a project, and must be fitted into a given time-frame. This is an instance of the classic budgeted maximizati…