Statistical Seminar: Every Monday at 2:00 pm.
Time: 2:00 pm – 3:15 pm
Date: 12th of June 2023
Place: Room 3001

Nikita Zhivotovskiy (UC Berkeley) – “Optimal PAC Bounds without Uniform Convergence”

Abstract:

In statistical learning theory, the problem of determining sample complexity of realizable binary classification for VC classes was a longstanding challenge. Notable advancements by Simon and Hanneke established sharp upper bounds, but their argument’s reliance on the uniform convergence principle curtailed its broader applicability to learning settings like multiclass classification. In this presentation, we will discuss a new technique to resolve this limitation and introduce optimal high probability risk bounds within a framework that surpasses uniform convergence constraints. Beyond binary classification, we will also delve into applications in scenarios where uniform convergence is notably sub-optimal. For multiclass classification, we will prove an optimal risk bound that scales with the one-inclusion hypergraph density of the class, effectively addressing the sub-optimality in the analysis by Daniely and Shalev-Shwartz. Additionally, for realizable bounded regression with absolute loss, we will derive an optimal risk bound based on a revised version of the scale-sensitive dimension, thus refining the results of Bartlett and Long. This talk is based on the joint work with Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, and Abhishek Shetty.

Organizers:
Cristina BUTUCEA (CREST), Alexandre TSYBAKOV (CREST), Karim LOUNICI (CMAP) , Jaouad MOURTADA (CREST)
Sponsors:
CREST-CMAP