- Optimal PAC Bounds without ...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in November 2023
Optimal PAC Bounds without Uniform Convergence
Speaker:
Yeshwanth Cherapanamjeri
, MIT
Date: Monday, November 27, 2023
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Public: Yes
Location: 32-D507
Event Type: Seminar
Room Description: 32-D507
Host: Noah Golowich, MIT
Contact: Noah Golowich, nzg@csail.mit.edu
Relevant URL:
Speaker URL: https://yeshwanth94.github.io/
Speaker Photo:
None
Reminders to:
theory-seminars@csail.mit.edu, seminars@csail.mit.edu
Reminder Subject:
TALK: Yeshwanth Cherapanamjeri : Optimal PAC Bounds without Uniform Convergence
Abstract: In statistical learning theory, the problem of determining the optimal sample complexity of binary classification was a longstanding challenge only recently resolved by Hanneke. Unfortunately, these arguments rely on the so-called uniform convergence principle which limits its applicability to more general learning settings. In this talk, we will discuss a new technique that overcomes this limitation and allows us to derive optimal sample complexity bounds for settings where uniform convergence is provably suboptimal and in some cases, does not yield any quantitative finite sample guarantees, e.g. multiclass classification, partial concept classification, and bounded regression. Our bounds resolve a few open questions in the literature, and our learning algorithm is based on a novel analysis of the online-to-batch framework of Littlestone and the celebrated one-inclusion graph algorithm of Haussler, Littlestone, and Warmuth.
Based on joint work with Ishaq Aden-Ali, Abhishek Shetty, and Nikita Zhivotovskiy.
Research Areas:
Algorithms & Theory, AI & Machine Learning
Impact Areas:
Big Data
Created by Noah Golowich at Sunday, November 26, 2023 at 12:37 PM.