Estimating means of bounded random variables by betting

By Ian Waudby-Smith, Aaditya Ramdas. Journal of The Royal Statistical Society Series B-statistical Methodology, 2020

274 citations recorded by the source corpus.

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 nonnegative 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 supermartingale 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.

Subfields: Artificial Intelligence, Management Science and Operations Research, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/d39e8e4d2ee7d61119a376511121555cb3b8fa29

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Statistics and Probability

Citations in the corpus

False discovery rate control with e‐values (2020, background): “These observations form the basis of all time-uniform Empirical-Bernstein inequalities (Howard et al., 2021; Waudby-Smith & Ramdas, 2020a,b).”
Time-uniform central limit theory and asymptotic confidence sequences (2021, background): “3 [65] Ian Waudby-Smith and Aaditya Ramdas.”
Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference (2024, methodology): “…users could be improved and made more formally rigorous by using the theory of nonnegative supermartingales and E-values (Howard et al., 2020; Waudby-Smith & Ramdas, 2020; Vovk & Wang, 2021; Ramdas et al., 2023); this would deal with the dependence, but the variants we tried did not perform…”
Martingale posterior distributions (2021, background): “An interesting aside is the recent work of Waudby-Smith and Ramdas (2020) which utilizes adaptive betting with martingale conditions for the purpose of constructing frequentist confidence intervals.”