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

arXiv:2504.19952v2 Announce Type: replace-cross 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 operatorname{KL_{inf}}. The second lower bound applies to the Farrell setting'', where alpha 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.

Source: arXiv cs.LG | 2026-08-18