<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body style="overflow-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"> <o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><i><span style="font-size: 12pt; font-family: Helvetica; color: rgb(139, 1, 2);">UNIVERSITY OF CHICAGO</span></i><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><i><span style="font-size: 12pt; font-family: Helvetica; color: rgb(139, 1, 2);">COMPUTER SCIENCE DEPARTMENT</span></i><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><i><span style="font-size: 12pt; font-family: Helvetica; color: rgb(139, 1, 2);">PRESENTS</span></i><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><span style="font-size: 11pt;"> </span></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 14pt; font-family: Helvetica;">Ishaq</span></b><span style="font-family: Arial, sans-serif; color: rgb(33, 33, 33);"> </span><b><span style="font-size: 14pt; font-family: Helvetica; color: rgb(33, 33, 33);">Aden-Ali</span></b><b><span style="font-size: 14pt; font-family: Helvetica;"><o:p></o:p></span></b></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 14pt; font-family: Helvetica;">University of California, Berkeley</span></b><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"> <o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> <img id="<image001.jpg@01DB7EF5.D94E5B80>" src="cid:04D6FC8F-D66B-4881-B325-EA80808B1EA5" alt="image001.jpeg" class="Apple-web-attachment Apple-edge-to-edge-visual-media" style="width: 2.6979in; height: 3.2291in; opacity: 1;"></span><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span> <o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt;">Tuesday, </span></b><b><span style="font-size: 11pt;">February 25, 2025, at 3:30pm</span></b><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt; background: yellow;">Kent Chemical Laboratory, Room 120</span></b><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><i><span style="font-size: 12pt; color: rgb(33, 33, 33);">Title:</span></i></b><span style="font-size: 12pt; color: rgb(33, 33, 33);"> </span><span style="font-size: 12pt; color: rgb(33, 33, 33);">Optimal PAC Bounds Without Uniform Convergence </span></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><o:p> </o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><i><span style="font-size: 12pt; color: rgb(33, 33, 33);">Abstract:</span></i></b><span style="color: rgb(33, 33, 33);"> </span><span style="font-size: 12pt; color: rgb(33, 33, 33);">Determining the sample complexity of realizable binary classification in the Probably Approximately Correct (PAC) learning model was an open problem in learning theory for decades. Hanneke (building on the work of Simon) finally resolved this problem not too long ago. Unfortunately, his argument relied heavily on certain ``uniform convergence’’ bounds that cannot be extended to more general learning settings, e.g. multiclass classification. In this work, we show how to close these gaps in a wide range of learning settings. Our unifying arguments are (necessarily) quite different and lead to a very different algorithmic landscape. <o:p></o:p></span></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt; color: rgb(33, 33, 33);"> </span></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt; color: rgb(33, 33, 33);">No prior knowledge of statistical learning theory will be assumed. This is based on joint work with Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy. </span></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt; color: rgb(33, 33, 33);"> </span><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><i><span style="font-size: 12pt; color: rgb(33, 33, 33);">Bio:</span></i></b><span style="color: rgb(33, 33, 33);"> </span><span style="font-size: 12pt; color: rgb(33, 33, 33);">Ishaq is a 4th year PhD student in the EECS department at the University of California, Berkeley. He is interested in problems at the intersection of learning theory, high dimensional probability, and theoretical computer science. A major goal of his work is to design statistically and computationally efficient algorithms for a wide range of learning tasks.</span></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 12pt; font-family: Helvetica;">Host:<span class="apple-converted-space"> </span></span></b><span class="apple-converted-space"><b><span style="font-size: 12pt; font-family: Helvetica;">Haotian Jiang</span></b></span></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span class="apple-converted-space"><b><span style="font-size: 12pt; font-family: Helvetica;"><br></span></b></span></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span class="apple-converted-space"><b><span style="font-size: 12pt; font-family: Helvetica;">---</span></b></span></p><div>
<meta charset="UTF-8"><div dir="auto" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; overflow-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div dir="auto" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; overflow-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div dir="auto" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; overflow-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div>Holly Santos<br>Executive Assistant to Hank Hoffmann, Liew Family Chair<br>Department of Computer Science<br>The University of Chicago<br>5730 S Ellis Ave-217 Chicago, IL 60637<br>P: 773-834-8977<br>hsantos@uchicago.edu</div><div><br></div></div><br class="Apple-interchange-newline"></div><br class="Apple-interchange-newline"></div><br class="Apple-interchange-newline"><br class="Apple-interchange-newline">
</div>
<br></body></html>