A0483
Title: On stopping times of power-one sequential tests: Tight lower and upper bounds
Authors: Shubhada Agrawal - Indian Institute of Science Bangalore (India) [presenting]
Aaditya Ramdas - Carnegie Mellon University (United States)
Abstract: Two lower bounds are proven for stopping times of sequential tests between general composite nulls and alternatives. The first lower bound is for the setting where the type-1 error level alpha approaches zero, and equals log(1/alpha) divided by a certain infimum KL divergence, termed KL-inf. The second lower bound applies to the setting where alpha is fixed and KL-inf approaches 0 (meaning that the null and alternative sets are not separated) and equals c KL-inf loglog(KL-inf) for a universal constant c > 0. A sufficient condition is also provided for matching the upper bounds, and it is shown that this condition is met in several special cases. Given past work, these upper and lower bounds are unsurprising in their form; the main contribution is the generality in which they hold, for example, not requiring reference measures or compactness of the classes.
