<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=Windows-1252">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
{font-family:Helvetica;
panose-1:0 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Aptos;
panose-1:2 11 0 4 2 2 2 2 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:10.0pt;
font-family:"Calibri",sans-serif;}
span.apple-converted-space
{mso-style-name:apple-converted-space;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;
mso-ligatures:none;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple" style="word-wrap:break-word">
<div class="WordSection1">
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102"> </span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">UNIVERSITY OF CHICAGO</span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">COMPUTER SCIENCE DEPARTMENT</span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">PRESENTS</span></i><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:12.0pt;font-family:Helvetica">Nathan Srebro, PhD</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121">Toyota Technological Institute at Chicago</span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica;color:black"> <img width="169" height="219" style="width:1.7604in;height:2.2812in" id="Picture_x0020_2" src="cid:image001.jpg@01DA3197.C6CC9550" alt="A person with a beard and mustache
Description automatically generated"></span></b><o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;color:black">Tuesday, </span>
</b><b><span style="font-size:11.0pt">January 16<span style="color:black">, 202</span>4<span style="color:black"> at 3:30pm</span></span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;color:black;background:yellow">Room – Ryerson 251</span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><i><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121">Title:</span></i></b><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121"> Shortest Program (Minimum Description Length) Interpolation
Learning</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><i><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121">Abstract:</span></i></b><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121"> 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.</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><i><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121">Bio:</span></i></b><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121"> Nati (Nathan) Srebro is a professor at the Toyota Technological
Institute at Chicago working on Machine Learning and its intersection with Optimization.</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p><span style="color:black"> </span><o:p></o:p></p>
<p style="margin-bottom:12.0pt"><b><span style="font-size:12.0pt;font-family:Helvetica;color:black">Host:<span class="apple-converted-space"> Alexander Razborov</span></span></b><o:p></o:p></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</body>
</html>