Virtual CISE Seminar: Aryeh Kontorovich, Ben-Gurion University

Date: Wednesday, September 27, 2023
Time: 2:15pm – 3:15pm

Professor Ayreh Kontorovich, Ben-Gurion University

Aryeh Kontorovich
Professor in the Department of Computer Science
Ben-Gurion University of the Negev Beer-Sheva

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. This regime is well-understood: for all μ, we have𝔼[M]≲√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 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. We give necessary and sufficient conditions on μ for 𝔼[M]→0, and discover a novel sub-Gamma-type maximal inequality for shifted Bernoullis.
A number of challenging open problems are posed for future research. Joint work with Doron Cohen, appeared in COLT 2023.
https://arxiv.org/abs/2209.04054

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