You’re invited to a seminar talk by Tomer Galanti (Texas A&M University): Title: Revisiting ERM in the LLM Era: Old Ideas, New Tools Host: Dr. Chaim Baskin

Abstract: We seek algorithms for program learning that are both sample-efficient and computationally feasible. Classical results show that targets admitting short program descriptions (e.g., with short "python code") can be learned with a "small" number of examples (scaling with the size of the code) via length-first program enumeration, but the search is exponential in description length. Consequently, Gradient-based training avoids this cost yet can require exponentially many samples on certain short-program families. To address this gap, we introduce a propose-and-verify framework that replaces exhaustive enumeration with an LLM-guided search over candidate programs while retaining ERM-style selection on held-out data. Specifically, we draw k candidates with a pretrained reasoning-augmented LLM, compile and check each on the data, and return the best verified hypothesis, with no feedback, adaptivity, or gradients. Theoretically, we show that coordinate-wise online mini-batch SGD requires many samples to learn certain short programs. Empirically, our method solves tasks such as parity variants, pattern matching, and primality testing with as few as 200 samples, while SGD-trained transformers overfit even with 100,000 samples. These results indicate that language-guided program synthesis recovers much of the statistical efficiency of finite-class ERM while remaining computationally tractable, offering a practical route to learning succinct hypotheses beyond the reach of gradient-based training. Short bio: Tomer Galanti is an Assistant Professor of Computer Science and Engineering at Texas A&M University. His research combines theoretical and empirical approaches to understand the foundations of modern deep learning and large language models. Before joining Texas A&M, he was a Postdoctoral Associate at MIT’s Center for Brains, Minds and Machines (CBMM) and CSAIL, working with Tomaso Poggio, and a Research Scientist Intern at Google DeepMind. He received his Ph.D. in Computer Science from Tel Aviv University under the supervision of Lior Wolf. His work has appeared in leading venues such as NeurIPS, ICML, ICLR, and JMLR, and has been recognized with a NeurIPS oral presentation (2020) and an ICLR spotlight presentation (2025).