סמינר מחלקת מערכות - Prof. Aryeh Kontorovich - Local Glivenko-Cantelli (or: estimating the mean in infinite dimensions)
(The talk will be given in English)
Speaker: Prof. Aryeh Kontorovich
Computer Science Department, Ben-Gurion University
011 hall, Electrical Engineering-Kitot Building
Monday, June 19th, 2023
15:00 - 16:00
Local Glivenko-Cantelli (or: estimating the mean in infinite dimensions)
Abstract
If $\mu$ is a distribution over the $d$-dimensional Boolean cube
$\set{0,1}^d$, our goal is to estimate its mean $p\in[0,1]^d$ based on
$n$ iid draws from $\mu$. Specifically, we consider the empirical mean
estimator $\hat p_n$ and study the expected maximal deviation
$\Delta_n=\E\max_{j\in[d]}|\hat p_n(j)-p(j)|$. In the classical
Universal Glivenko-Cantelli setting, one seeks distribution-free
(i.e., independent of $\mu$) bounds on $\Delta_n$. This regime is
well-understood: for all $\mu$, we have
$\Delta_n\lesssim\sqrt{\log(d)/n}$ up to universal constants, and the
bound is tight.
Our present work seeks to establish dimension-free (i.e., without an
explicit dependence on $d$) estimates on $\Delta_n$, including those
that hold for $d=\infty$. As such bounds must necessarily depend on
$\mu$, we refer to this regime as {\em local} Glivenko-Cantelli (also
known as $\mu$-GC), and are aware of very few previous bounds of this
type --- which are either "abstract" or quite sub-optimal. Already the
special case of product measures $\mu$ is rather non-trivial. We give
necessary and sufficient conditions on $\mu$ for $\Delta_n\to0$, and
calculate sharp rates for this decay. Along the way, we discover a
novel sub-gamma-type maximal inequality for shifted Bernoullis, of
independent interest.
A number of challenging open problems are posed for future research. Joint work with Doron Cohen.
https://arxiv.org/abs/2209.04054
Short Bio
Aryeh Kontorovich received his undergraduate degree in mathematics with a certificate in applied mathematics from Princeton University in 2001. His M.Sc. and Ph.D. are from Carnegie Mellon University, where he graduated in 2007. After a postdoctoral fellowship at the Weizmann Institute of Science, he joined the Computer Science department at Ben-Gurion University of the Negev in 2009, where he is currently a full professor. His research interests are mainly in machine learning, with a focus on probability, statistics, Markov chains, and metric spaces.
He served as the director of the Ben-Gurion University Data Science Research Center during 2021-2022.
השתתפות בסמינר תיתן קרדיט שמיעה = עפ"י רישום שם מלא + מספר ת.ז. בטופס הנוכחות שיועבר באולם במהלך הסמינר
