Time-uniform Chernoff bounds via nonnegative supermartingales

Steven R. Howard, Aaditya Ramdas, Jon McAuliffe +1

We develop a class of exponential bounds for the probability that a martingale sequence crosses a time-dependent linear threshold. Our key insight is that it is both natural and fr…