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

See other events that are part of the Algorithms and Complexity Seminar 2023.

Created by Noah Golowich Email at Sunday, November 26, 2023 at 12:37 PM.