CISE Seminar: Aryeh Kontorovich, Ben-Gurion University

Local Glivenko-Cantelli (or: estimating the mean in infinite dimensions)

If μ is a distribution over the d-dimensional Boolean cube {0,1}d, our goal is to estimate its mean p∈[0,1]d based on n iid draws from μ. Specifically, we consider the empirical mean estimator p̂n and study the maximal deviation M=maxj∈[d]| p̂n(j)-p(j)|. In the classical Universal Glivenko-Cantelli setting, we seek distribution-free (i.e., independent of μ) bounds on M.Our present work seeks to establish dimension-free (i.e., without an explicit dependence on d) estimates on M, including those that hold for d=∞. As such bounds must necessarily depend on μ, we refer to this regime as Local Glivenko-Cantelli, and are aware of very few previous bounds of this type — which are quite sub-optimal. Already the special case of product measures μ is quite non-trivial.A number of challenging open problems are posed for future research. Joint work with Doron Cohen, appeared in COLT 2023.

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.

Faculty Host: Ari Tratchenberg

Zoom registration link:

When 2:15 pm to 3:15 pm on Wednesday, September 27, 2023
Location Zoom