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

Abstract

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 $\alpha$ approaches zero for a fixed alternative $Q\in \mathcal{Q}$, and equals $\log (1/\alpha )$ divided by a certain infimum KL divergence between $\mathcal{P}$ and $Q$, termed $\mathrm{K}{\mathrm{L}}_{\inf }$. The second lower bound applies to the ``Farrell setting'', where $\alpha$ is fixed and $\mathrm{K}{\mathrm{L}}_{\inf }$ approaches $0$ along a sequence of alternatives such that the required expected sample size along that sequence is of order at least $\mathrm{K}{\mathrm{L}}_{\inf }^{-1}\log \log \mathrm{K}{\mathrm{L}}_{\inf }^{-1}$. 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.

57 pages, 1 figure