5 papers · 1 filter
On the Hardness of Learning Regular Expressions
Idan Attias, Lev Reyzin, Nathan Srebro +1
Despite the theoretical significance and wide practical use of regular expressions, the computational complexity of learning them has been largely unexplored. We study the computat…
Learning to Answer from Correct Demonstrations
Nirmit Joshi, Gene Li, Siddharth Bhandari +3
We study the problem of learning to generate an answer (or completion) to a question (or prompt), where there could be multiple correct answers, any one of which is acceptable at t…
Learning single-index models via harmonic decomposition
Nirmit Joshi, Hugo Koubbi, Theodor Misiakiewicz +1
We study the problem of learning single-index models, where the label depends on the input only through an unknown one-dimensio…
Temperature is All You Need for Generalization in Langevin Dynamics and other Markov Processes
Itamar Harel, Yonathan Wolanowsky, Gal Vardi +2
We analyze the generalization gap (gap between the training and test errors) when training a potentially over-parametrized model using a Markovian stochastic training algorithm, in…
A Theory of Learning with Autoregressive Chain of Thought
Nirmit Joshi, Gal Vardi, Adam Block +4
For a given base class of sequence-to-next-token generators, we consider learning prompt-to-answer mappings obtained by iterating a fixed, time-invariant generator for multiple ste…