[Colloquium] CS Theory Seminar - Nathan Srebro, January 16, 2024

[Jose J Fragoso]

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS



Nathan Srebro, PhD
Toyota Technological Institute at Chicago


 [A person with a beard and mustache  Description automatically generated]

Tuesday, January 16, 2024 at 3:30pm
Room – Ryerson 251


Title: Shortest Program (Minimum Description Length) Interpolation Learning

Abstract: We consider learning by using the shortest program that perfectly fits the training data, even in situations where labels are noisy and there is no way of exactly predicting the labels on the population. Classical theory tells us that in such situations we should balance program length with training error, in which case we can compete with any (unknown) program with sample complexity proportional to the length of the program. But in the spirit of recent work on benign overfitting, we ignore this wisdom and insist on zero training error even in noisy situations. We study the generalization property of the shortest program interpolator, and ask how it performs compared to the balanced approach, and how much we suffer, if at all, due to such overfitting. To do so, we analyze the Kolmogorov complexity of a noisy sequence with information-theoretic generalization guarantees.

Bio: Nati (Nathan) Srebro is a professor at the Toyota Technological Institute at Chicago working on Machine Learning and its intersection with Optimization.




Host: Alexander Razborov
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20240108/6125d267/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 431510 bytes
Desc: image001.jpg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20240108/6125d267/attachment-0001.jpg>