Estimating means of bounded random variables by betting (Online)

Date: Tuesday 23 May 2023, 4.00PM
Location: Online
Discussion Paper Meeting

Share this event

This paper derives confidence intervals (CI) and time-uniform confidence sequences (CS) for the classical problem of estimating an unknown mean from bounded observations. We present a general approach for deriving concentration bounds, that can be seen as a generalization and improvement of the celebrated Chernoff method. At its heart, it is based on a class of composite non negative martingales, with strong connections to testing by betting and the method of mixtures. We show how to extend these ideas to sampling without replacement, another heavily studied problem. In all cases, our bounds are adaptive to the unknown variance, and empirically vastly outperform existing approaches based on Hoeffding or empirical Bernstein inequalities and their recent super martingale generalizations by Howard et al.[2021]. In short, we establish a new state-of-the-art for four fundamental problems: CSs and CIs for bounded means, when sampling with and without replacement.

RSS - Discussion paper meetings
 

Paper: ‘Estimating means of bounded random variables by betting’

Authors: Ian Waudby-Smith and Aaditya Ramdas, Carnegie Mellon University, USA
 
Contact Judith Shorten