On Stopping Times of Power-one Sequential Tests: Tight Lower and Upper Bounds
This work provides foundational theoretical guarantees for sequential testing in statistics, with broad implications for fields like machine learning and signal processing, though it is incremental in extending known results to more general settings.
The paper tackles the problem of deriving tight lower and upper bounds for stopping times in sequential tests between composite null and alternative hypotheses, proving bounds that scale with error levels and KL divergence, and showing these bounds hold under general conditions without requiring reference measures or compactness.
We prove two lower bounds 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 $α$ approaches zero, and equals $\log(1/α)$ divided by a certain infimum KL divergence, termed $\operatorname{KL_{inf}}$. The second lower bound applies to the setting where $α$ is fixed and $\operatorname{KL_{inf}}$ approaches 0 (meaning that the null and alternative sets are not separated) and equals $c \operatorname{KL_{inf}}^{-1} \log \log \operatorname{KL_{inf}}^{-1}$ for a universal constant $c > 0$. We also provide a sufficient condition for matching the upper bounds and show that this condition is met in several special cases. Given past work, these upper and lower bounds are unsurprising in their form; our main contribution is the generality in which they hold, for example, not requiring reference measures or compactness of the classes.