On Stopping Times of Power-one Sequential Tests: Tight Lower and Upper Bounds

We present two general lower bounds for stopping times of sequential tests between arbitrary composite nulls \mathcal P and alternatives \mathcal Q. The first lower bound is for the Wald setting'' where the type-1 error level α approaches zero for a fixed alternative Q \in \mathcal Q, and equals \log(1/α) divided by a certain infimum KL divergence between \mathcal P and Q, termed \operatorname{KL_{inf}}. The second lower bound applies to the Farrell setting'', where α is fixed and \operatorname{KL_{inf}} approaches 0 along a sequence of alternatives such that the required expected sample size along that sequence is of order at least \operatorname{KL^{-1}{inf}} \log \log \operatorname{KL^{-1}{inf}}. Our main contribution is the generality of these bounds, which hold in non-parametric, composite settings, without requiring a dominating reference measure, substantially generalizing the known parametric results. We also provide sufficient conditions for matching upper bounds and show that these are met in several nontrivial non-parametric cases.