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

[Holly Santos via Colloquium]

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS
                             
 
Ishaq Aden-Ali
University of California, Berkeley
 
 
  
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

---
Holly Santos
Executive Assistant to Hank Hoffmann, Liew Family Chair
Department of Computer Science
The University of Chicago
5730 S Ellis Ave-217   Chicago, IL 60637
P: 773-834-8977
hsantos at uchicago.edu






-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20250218/dd006c83/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpeg
Type: image/jpeg
Size: 27043 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20250218/dd006c83/attachment-0001.jpeg>