Sequential Nonparametric Testing with the Law of the Iterated Logarithm

Akshay Balsubramani, Aaditya Ramdas
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, PMLR R14:772-781, 2016.

Abstract

We propose a new algorithmic framework for sequential hypothesis testing with i.i.d. data, which includes A/B testing, nonparametric two-sample testing, and independence testing as special cases. It is novel in several ways: (a) it takes linear time and constant space to compute on the fly, (b) it has the same power guarantee as a nonsequential version of the test with the same computational constraints up to a small factor, and (c) it accesses only as many samples as are required - its stopping time adapts to the unknown difficulty of the problem. All our test statistics are constructed to be zero-mean martingales under the null hypothesis, and the rejection threshold is governed by a uniform non-asymptotic law of the iterated logarithm (LIL). For the case of nonparametric two-sample mean testing, we also provide a finite sample power analysis, and the first non-asymptotic stopping time calculations for this class of problems. We verify our predictions for type I and II errors and stopping times using simulations.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR14-balsubramani16a, title = {Sequential Nonparametric Testing with the Law of the Iterated Logarithm}, author = {Balsubramani, Akshay and Ramdas, Aaditya}, booktitle = {Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence}, pages = {772--781}, year = {2016}, editor = {Ihler, Alexander and Janzing, Dominik}, volume = {R14}, series = {Proceedings of Machine Learning Research}, month = {25--29 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r14/main/assets/balsubramani16a/balsubramani16a.pdf}, url = {https://proceedings.mlr.press/r14/balsubramani16a.html}, abstract = {We propose a new algorithmic framework for sequential hypothesis testing with i.i.d. data, which includes A/B testing, nonparametric two-sample testing, and independence testing as special cases. It is novel in several ways: (a) it takes linear time and constant space to compute on the fly, (b) it has the same power guarantee as a nonsequential version of the test with the same computational constraints up to a small factor, and (c) it accesses only as many samples as are required - its stopping time adapts to the unknown difficulty of the problem. All our test statistics are constructed to be zero-mean martingales under the null hypothesis, and the rejection threshold is governed by a uniform non-asymptotic law of the iterated logarithm (LIL). For the case of nonparametric two-sample mean testing, we also provide a finite sample power analysis, and the first non-asymptotic stopping time calculations for this class of problems. We verify our predictions for type I and II errors and stopping times using simulations.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Sequential Nonparametric Testing with the Law of the Iterated Logarithm %A Akshay Balsubramani %A Aaditya Ramdas %B Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2016 %E Alexander Ihler %E Dominik Janzing %F pmlr-vR14-balsubramani16a %I PMLR %P 772--781 %U https://proceedings.mlr.press/r14/balsubramani16a.html %V R14 %X We propose a new algorithmic framework for sequential hypothesis testing with i.i.d. data, which includes A/B testing, nonparametric two-sample testing, and independence testing as special cases. It is novel in several ways: (a) it takes linear time and constant space to compute on the fly, (b) it has the same power guarantee as a nonsequential version of the test with the same computational constraints up to a small factor, and (c) it accesses only as many samples as are required - its stopping time adapts to the unknown difficulty of the problem. All our test statistics are constructed to be zero-mean martingales under the null hypothesis, and the rejection threshold is governed by a uniform non-asymptotic law of the iterated logarithm (LIL). For the case of nonparametric two-sample mean testing, we also provide a finite sample power analysis, and the first non-asymptotic stopping time calculations for this class of problems. We verify our predictions for type I and II errors and stopping times using simulations. %Z Reissued by PMLR on 04 October 2026.
APA
Balsubramani, A. & Ramdas, A.. (2016). Sequential Nonparametric Testing with the Law of the Iterated Logarithm. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R14:772-781 Available from https://proceedings.mlr.press/r14/balsubramani16a.html. Reissued by PMLR on 04 October 2026.

Related Material