[Colloquium] CS Theory Seminar - Tuesday, February 25, 2025

[Jose J Fragoso via Colloquium]

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS




Ishaq Aden-Ali
University of California, Berkeley

 [cid:image001.jpg at 01DB7EF5.D94E5B80]

Tuesday, February 25, 2025, at 3:30pm
Kent Chemical Laboratory, Room 120



Title: Optimal PAC Bounds Without Uniform Convergence


Abstract: 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.

No prior knowledge of statistical learning theory will be assumed. This is based on joint work with Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy.



Bio: 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.






  Host: Haotian Jiang
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20250224/ddc66253/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 1464351 bytes
Desc: image001.jpg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20250224/ddc66253/attachment-0001.jpg>