12/06/2025
WHO: Prof. Aryeh Kontorovich, Ben-Gurion University
WHEN: Thursday, June 12th 2025 at 12:00
WHERE: BUILDING 503 (Computer Science) AUDITORIUM
Title
Learning infinitely many coins simultaneously
Abstract:
Inferring the bias of a single coin from independent flips is a well-understood problem, technically known as estimating the Bernoulli parameter p. In particular, how the sample size (number of flips) n, the precision ε, and the confidence δ constrain each other is known within tight upper and lower bounds. When we want to estimate the bias of d coins simultaneously, this problem is well-understood as well, at least in the worst case over the Bernoulli parameters pᵢ. What if we want to estimate infinitely many pᵢ's simultaneously?
A simple argument shows that this is impossible in the "worst case" over the pᵢ's; thus, any result must depend on their actual values. If we define M as the expected maximum deviation between any pᵢ and its estimate, we want to understand for which sequences pᵢ this quantity decays to zero and at what rate. We obtain tight, exhaustive answers to these questions.
The exhaustive answers mentioned above were obtained for independent (or negatively dependent) Bernoullis. Allowing positive dependencies complicates the story significantly. We have upper and lower bounds but no simple general characterization of convergence.
Joint work with Moïse Blanchard, Doron Cohen, Václav Voráček
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.
