Theory Lunch Seminar

Wednesday, December 1, 2021 - 12:00pm to 1:00pm

Location:

In Person and Virtual ET Gates Hillman 8102 and Zoom

Speaker:

IAN WAUDBY-SMITH, Ph.D. Student https://ian.waudbysmith.com/

Estimating means of bounded random variables by betting

This work 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 deriving a new 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. 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.

Additional Information

In Person and Zoom Participation. See announcement.

Event Website:

http://www.cs.cmu.edu/~theorylunch/

For More Information, Contact:

Keywords:

Seminar Series