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

Delivered on Thursday, December 8th, 2022, 10:30 AM
Speaker
Aryeh Kontorovich, BGU
Title
Local Glivenko-Cantelli (or: estimating the mean in infinite dimensions)
Abstract
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.
arxiv.org/abs/...
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 is currently serving as the director of the Ben-Gurion University Data Science Research Center.
Link for the Panopto Meeting
huji.cloud.pan...
Link to past lectures
/ @hujimachinelearningcl...
Online Calendar
Learning Club @ HUJI
www.google.com...
Calendar ID: [e-mail]
Mailing List
subscription-manager: mailman.cs.huji...

[@mateuszokonski4318]

Thank you and best regards from Poland 🙂