Seminars

View all Seminars  |  Download ICal for this event

Optimal PAC Bounds without Uniform Convergence

Series: Bangalore Theory Seminars

Speaker: Abhishek Shetty, Department of Computer Science, University of California, Berkeley

Date/Time: Jun 21 11:00:00

Location: CSA Lecture Hall (Room No. 112, Ground Floor)

Abstract:
In statistical learning theory, determining the sample complexity of realizable binary classification for VC classes was a long-standing open problem. The results of Simon and Hanneke established sharp upper bounds in this setting. However, the reliance of their argument on the uniform convergence principle limits its applicability to more general learning settings such as multiclass classification and bounded regression, where improved bounds in expectation can be achieved through exchangeability based arguments.

In this talk, we will discuss a simple technique that addresses this issue. We will present optimal high probability risk bounds through a framework that surpasses the limitations of uniform convergence arguments by bringing together exchangeability arguments with techniques from sequential decision making.

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


Microsoft teams link:

Link


We are grateful to the Kirani family for generously supporting the theory seminar series


Hosts: Rameesh Paul, KVN Sreenivas, Rahul Madhavan, Debajyoti Kar