check
Colloquium: Shay Moran (Technion) | Einstein Institute of Mathematics

Colloquium: Shay Moran (Technion)

Date: 
Thu, 27/04/202314:30-15:30
Title: Characterizations of Uniform Learnability: Vapnik-Chervonenkis, Natarajan, and Daniely-Shalev Shwartz Dimensions.


Note:

I'll try to make the talk accessible to those without a learning theory background.


Abstract:

A seminal result in learning theory characterizes the PAC learnability of binary classes through the VC dimension.

Extending this characterization to the general multiclass setting has been open since the late 1980s.


We resolve this problem by characterizing multiclass PAC learnability through the DS dimension,

a combinatorial dimension defined by Daniely and Shalev-Shwartz (2014).


The classical characterization of the binary case boils down to empirical risk minimization.

In contrast, our characterization of the multiclass case involves a variety of algorithmic ideas;

these include a natural setting we call list PAC learning.

In the list learning setting, instead of predicting the label of a given unseen input,

the goal is to provide a short list of labels which contains the correct one with high probability.


Our second main result concerns the Natarajan dimension,

which has been a central candidate for characterizing multiclass learnability.

This dimension was introduced by Natarajan (1988) as a barrier for PAC learning.

Whether the Natarajan dimension characterizes PAC learnability in general

has been posed as an open question in several papers since.

We provide a negative answer: we construct a non-learnable class with Natarajan dimension one.


For the construction, we identify a fundamental connection between concept classes and topology.

We crucially rely on a deep and involved geometric-group-theoretic construction by Januszkiewicz and Swiatkowski.

This proof provides another demonstration of the fruitful links learning theory has with different areas in mathematics.

Live stream and recording link: https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=87aa5885-3409-4cb2-a54a-afe90058cf79