[Theory] UC Theory Seminar

[Alexander Razborov via Theory]

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. 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250218/3ec94902/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 85353 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250218/3ec94902/attachment-0001.jpg>