March 14, 2024 10:20
Talk by Prof. Shai Ben-David (University of Waterloo/Vector Institute, Canada) on Learning probability distributions; what can, what can't be done. thumbnails


Date and Time: March 11, 2024: 10:30 am – 12:00 am (JST)
Venue: Online and Open Space at the RIKEN AIP Nihonbashi office

TITLE: Learning probability distributions; what can, what can’t be done.
SPEAKER: Prof. Shai Ben-David (University of Waterloo/Vector Institute, Canada)
A possible high-level description of statistical learning is that it aims to learn about some unknown probability distribution (“environment”) from samples it generates (“training data”). In its most general form, assuming no prior knowledge and asking to find accurate approximations to the data generating distributions (a.k.a. density estimation), there can be no success guarantee. In this talk I will discuss two major directions of relaxing that too hard problem.

First, I will address the situation under common prior knowledge assumption – I will describe settling the question of the sample complexity of learning mixtures of Gaussians.

I will also mention unpublished recent results about characterization of the learnable families of distributions.

Secondly, I will address what can be learnt about unknown distributions when no prior knowledge is applied. I will describe a surprising result. Namely, the independence from set theory of a basic statistical learnability problem. As a corollary, I will show that there can be no combinatorial dimension that characterizes the families of random variables that can be reliably learnt (in contrast with the known VC-dimension-like characterizations of common supervised learning tasks).

Both parts of the talks use novel notions of sample compression schemes as key components.

The first part is based on joint work with Hasan Ashiani, Nick Harvey, Chris Law, Abas Merhabian and Yaniv Plan and the second part on work with Shay Moran, Pavel Hrubes, Amir Shpilka and Amir Yehudayoff. The recent characterization results are with my student Tosca lechner.