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 $\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.

Statistics Theory (math.ST); Machine Learning (cs.LG); Machine Learning (stat.ML)

arXiv:2504.19952 [math.ST]

(or arXiv:2504.19952v2 [math.ST] for this version)

https://doi.org/10.48550/arXiv.2504.19952 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.