BEGIN:VCALENDAR VERSION:2.0 PRODID:-//jEvents 2.0 for Joomla//EN CALSCALE:GREGORIAN METHOD:PUBLISH BEGIN:VTIMEZONE TZID:America/New_York BEGIN:STANDARD DTSTART:20241103T010000 RDATE:20250309T030000 TZOFFSETFROM:-0400 TZOFFSETTO:-0500 TZNAME:America/New_York EST END:STANDARD BEGIN:STANDARD DTSTART:20251102T010000 RDATE:20260308T030000 TZOFFSETFROM:-0400 TZOFFSETTO:-0500 TZNAME:America/New_York EST END:STANDARD BEGIN:STANDARD DTSTART:20261101T010000 RDATE:20270314T030000 TZOFFSETFROM:-0400 TZOFFSETTO:-0500 TZNAME:America/New_York EST END:STANDARD BEGIN:STANDARD DTSTART:20271107T010000 RDATE:20280312T030000 TZOFFSETFROM:-0400 TZOFFSETTO:-0500 TZNAME:America/New_York EST END:STANDARD BEGIN:STANDARD DTSTART:20281105T010000 RDATE:20290311T030000 TZOFFSETFROM:-0400 TZOFFSETTO:-0500 TZNAME:America/New_York EST END:STANDARD BEGIN:DAYLIGHT DTSTART:20241028T140000 RDATE:20241103T010000 TZOFFSETFROM:-0500 TZOFFSETTO:-0400 TZNAME:America/New_York EDT END:DAYLIGHT BEGIN:DAYLIGHT DTSTART:20250309T030000 RDATE:20251102T010000 TZOFFSETFROM:-0500 TZOFFSETTO:-0400 TZNAME:America/New_York EDT END:DAYLIGHT BEGIN:DAYLIGHT DTSTART:20260308T030000 RDATE:20261101T010000 TZOFFSETFROM:-0500 TZOFFSETTO:-0400 TZNAME:America/New_York EDT END:DAYLIGHT BEGIN:DAYLIGHT DTSTART:20270314T030000 RDATE:20271107T010000 TZOFFSETFROM:-0500 TZOFFSETTO:-0400 TZNAME:America/New_York EDT END:DAYLIGHT BEGIN:DAYLIGHT DTSTART:20280312T030000 RDATE:20281105T010000 TZOFFSETFROM:-0500 TZOFFSETTO:-0400 TZNAME:America/New_York EDT END:DAYLIGHT END:VTIMEZONE BEGIN:VEVENT UID:6de34ba351b9be34f9f9b2165d55ac7a CATEGORIES:Lean Seminar CREATED:20251025T132518 SUMMARY:LLM-ERM: Sample-Efficient Program Learning via LLM-Guided Search LOCATION:CoRE 431 DESCRIPTION:We seek algorithms for program learning that are both sample-efficient and computationally feasible. Classical results show that targets admitting sho rt program descriptions (e.g., with short "python code") can be learned wit h a "small" number of examples (scaling with the size of the code) via leng th-first program enumeration, but the search is exponential in description length. Consequently, Gradient-based training avoids this cost yet can requ ire exponentially many samples on certain short-program families.\nTo addre ss this gap, we introduce LLM-ERM, a propose-and-verify framework that repl aces exhaustive enumeration with an LLM-guided search over candidate progra ms while retaining ERM-style selection on held-out data. Specifically, we d raw k candidates with a pretrained reasoning-augmented LLM, compile and che ck each on the data, and return the best verified hypothesis, with no feedb ack, adaptivity, or gradients. Theoretically, we show that coordinate-wise online mini-batch SGD requires many samples to learn certain short programs . Empirically, LLM-ERM solves tasks such as parity variants, pattern matchi ng, and primality testing with as few as 200 samples, while SGD-trained tra nsformers overfit even with 100,000 samples. These results indicate that la nguage-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 gradien t-based training.\n X-ALT-DESC;FMTTYPE=text/html:

We seek algorithms for program learning that are both sample -efficient and computationally feasible. Classical results show that target s 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 co st yet can require exponentially many samples on certain short-program fami lies.

To address this gap, we introduce LLM-ERM, a propos e-and-verify framework that replaces exhaustive enumeration with an LLM-gui ded search over candidate programs while retaining ERM-style selection on h eld-out data. Specifically, we draw k candidates with a pretrained reasonin g-augmented LLM, compile and check each on the data, and return the best ve rified hypothesis, with no feedback, adaptivity, or gradients. Theoreticall y, we show that coordinate-wise online mini-batch SGD requires many samples to learn certain short programs. Empirically, LLM-ERM solves tasks such as parity variants, pattern matching, and primality testing with as few as 20 0 samples, while SGD-trained transformers overfit even with 100,000 samples . These results indicate that language-guided program synthesis recovers mu ch of the statistical efficiency of finite-class ERM while remaining comput ationally tractable, offering a practical route to learning succinct hypoth eses beyond the reach of gradient-based training.

CONTACT:Tomer Galanti DTSTAMP:20260827T005745 DTSTART;TZID=America/New_York:20251029T140000 DTEND;TZID=America/New_York:20251029T150000 SEQUENCE:0 TRANSP:OPAQUE END:VEVENT END:VCALENDAR