Title:

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.

Bio:

Nikita Zhivotovskiy is a tenure-track Assistant Professor at the University of California Berkeley, Department of Statistics. From January 2021 to October 2022 he was a postdoctoral researcher at the department of mathematics ETH, Zürich hosted by Afonso Bandeira. Between January 2019 and December 2020 he was a postdoctoral researcher at Google Research, Zürich hosted by Olivier Bousquet. Before that he spent half a year at the department of mathematics, Technion I.I.T. hosted by Shahar Mendelson. Nikita defended my thesis at Moscow Institute of Physics and Technology Moscow in 2018 under the supervision of Vladimir Spokoiny and Konstantin Vorontsov. During my time in Moscow, he was affiliated (part-time) with the Institute for Information Transmission Problems, Higher School of Economics, and Skoltech. His main interests are in the intersection of mathematical statistics, probability and learning theory.