Document Open Access Logo

Optimal Stopping Rules for Sequential Hypothesis Testing

Authors Constantinos Daskalakis, Yasushi Kawase

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.32.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Constantinos Daskalakis
Yasushi Kawase

Cite As Get BibTex

Constantinos Daskalakis and Yasushi Kawase. Optimal Stopping Rules for Sequential Hypothesis Testing. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.32

Abstract

Suppose that we are given sample access to an unknown distribution p over n elements and an explicit distribution q over the same n elements. We would like to reject the null hypothesis "p=q" after seeing as few samples as possible, when p =/= q, while we never want to reject the null, when p=q. Well-known results show that Theta(sqrt{n}/epsilon^2) samples are necessary and sufficient for distinguishing whether p equals q versus p is epsilon-far from q in total variation distance. However, this requires the distinguishing radius epsilon to be fixed prior to deciding how many samples to request. Our goal is instead to design sequential hypothesis testers, i.e. online algorithms that request i.i.d. samples from p and stop as soon as they can confidently reject the hypothesis p=q, without being given a lower bound on the distance between p and q, when p =/= q. In particular, we want to minimize the number of samples requested by our tests as a function of the distance between p and q, and if p=q we want the algorithm, with high probability, to never reject the null. Our work is motivated by and addresses the practical challenge of sequential A/B testing in Statistics.

We show that, when n=2, any sequential hypothesis test must see Omega(1/{d_{tv}(p,q)^2} log log 1/{d_{tv}(p,q)}) samples, with high (constant) probability, before it rejects p=q, where d_{tv}(p,q) is the - unknown to the tester - total variation distance between p and q. We match the dependence of this lower bound on d_{tv}(p,q) by proposing a sequential tester that rejects p=q from at most O({\sqrt{n}}/{d_{tv}(p,q)^2}log log 1/{d_{tv}(p,q)}) samples with high (constant) probability. The Omega(sqrt{n}) dependence on the support size n is also known to be necessary.
We similarly provide two-sample sequential hypothesis testers, when sample access is given to both p and q, and discuss applications to sequential A/B testing.

Subject Classification

Keywords
  • property testing
  • sequential hypothesis testing
  • A/B testing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Jayadev Acharya, Clément L. Canonne, and Gautam Kamath. A chasm between identity and equivalence testing with conditional queries. In Proceedings of APPROX/RANDOM, 2015. Google Scholar
  2. Jayadev Acharya, Constantinos Daskalakis, and Gautam C. Kamath. Optimal Testing for Properties of Distributions. In Proceedings of NIPS, pages 3591-3599, 2015. Google Scholar
  3. Akshay Balsubramani. Sharp finite-time iterated-logarithm martingale concentration. page 25, 2014. URL: http://arxiv.org/abs/1405.2639.
  4. Akshay Balsubramani. Sharp finite-time iterated-logarithm martingale concentration. arXiv preprint arXiv:1405.2639, 2014. Google Scholar
  5. Akshay Balsubramani and Aaditya Ramdas. Sequential nonparametric testing with the law of the iterated logarithm. arXiv preprint arXiv:1506.03486, 2015. Google Scholar
  6. Jay Bartroff, Tze Leung Lai, and Mei-Chiung Shih. Sequential experimentation in clinical trials: design and analysis, volume 298. Springer Science &Business Media, 2012. Google Scholar
  7. Tuğkan Batu, Eldar Fischer, Lance Fortnow, Ravi Kumar, Ronitt Rubinfeld, and Patrick White. Testing random variables for independence and identity. In Proceedings FOCS, pages 442-451, 2001. Google Scholar
  8. Tuğkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D Smith, and Patrick White. Testing that distributions are close. In Proceedings of FOCS, pages 259-269, 2000. Google Scholar
  9. Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, and Paul Valiant. Testing monotonicity of distributions over general partial orders. In Proceedings of ICS, pages 239-252, 2011. Google Scholar
  10. Clément L. Canonne. A survey on distribution testing: Your data is big. but is it blue? Electronic Colloquium on Computational Complexity (ECCC), 22:63, 2015. Google Scholar
  11. Clément L. Canonne, Ilias Diakonikolas, Themis Gouleakis, and Ronitt Rubinfeld. Testing shape restrictions of discrete distributions. In Proceedings of STACS, 2016. Google Scholar
  12. Clément L. Canonne, Dana Ron, and Rocco A. Servedio. Testing probability distributions using conditional samples. SIAM Journal on Computing, 44(3):540-616, 2015. Google Scholar
  13. Siu-On Chan, Ilias Diakonikolas, Gregory Valiant, and Paul Valiant. Optimal algorithms for testing closeness of discrete distributions. In Proceedings of SODA, pages 1193-1203, 2014. Google Scholar
  14. Roger H. Farrell. Asymptotic behavior of expected sample size in certain one sided tests. The Annals of Mathematical Statistics, pages 36-72, 1964. Google Scholar
  15. Oded Goldreich and Dana Ron. On Testing Expansion in Bounded-Degree Graphs. Electronic Colloquium on Computational Complexity (ECCC), 7(20), 2000. Google Scholar
  16. Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58(301):13-30, 1963. Google Scholar
  17. Kevin Jamieson, Matt Malloy, Robert Nowak, and Sebastien Bubeck. lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits. In Proceedings of COLT, 2014. Google Scholar
  18. Ramesh Johari, Leo Pekelis, and David J Walsh. Always valid inference: Bringing sequential analysis to A/B testing. arXiv preprint arXiv:1512.04922, 2015. Google Scholar
  19. Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In Proceedings of ICML, 2013. Google Scholar
  20. Eugene Kharitonov, Aleksandr Vorobev, Craig Macdonald, Pavel Serdyukov, and Iadh Ounis. Sequential testing for early stopping of online experiments. In Proceedings of SIGIR, pages 473-482, 2015. Google Scholar
  21. Aleksandr Khintchine. über einen satz der wahrscheinlichkeitsrechnung. Fundamenta Mathematicae, 6(1):9-20, 1924. Google Scholar
  22. Martin Kulldorff, Robert L Davis, Margarette Kolczak, Edwin Lewis, Tracy Lieu, and Richard Platt. A maximized sequential probability ratio test for drug and vaccine safety surveillance. Sequential analysis, 30(1):58-78, 2011. Google Scholar
  23. Tze Leung Lai. Sequential analysis. Wiley Online Library, 2001. Google Scholar
  24. K.K. Gordon Lan and David L. DeMets. Discrete sequential boundaries for clinical trials. Biometrika, 70(3):659-663, 1983. Google Scholar
  25. Evan Miller. How Not To Run An A/B Test. 2010. URL: http://www.evanmiller.org/how-not-to-run-an-ab-test.html.
  26. Peter C. O'Brien and Thomas R Fleming. A multiple testing procedure for clinical trials. Biometrics, pages 549-556, 1979. Google Scholar
  27. Liam Paninski. A coincidence-based test for uniformity given very sparsely sampled discrete data. IEEE Transactions on Information Theory, 54(10):4750-4755, 2008. Google Scholar
  28. Stuart J. Pocock. Group sequential methods in the design and analysis of clinical trials. Biometrika, pages 191-199, 1977. Google Scholar
  29. Ronitt Rubinfeld. Taming big probability distributions. XRDS, 19(1):24-28, 2012. Google Scholar
  30. David Siegmund. Estimation following sequential tests. Biometrika, 65(2):341-349, 1978. Google Scholar
  31. David Siegmund. Sequential analysis: tests and confidence intervals. Springer Science &Business Media, 2013. Google Scholar
  32. Gregory Valiant and Paul Valiant. The power of linear estimators. In Proceedings of FOCS, pages 403-412, 2011. Google Scholar
  33. Gregory Valiant and Paul Valiant. An automatic inequality prover and instance optimal identity testing. In Proceedings of FOCS, pages 51-60, 2014. Google Scholar
  34. Abraham Wald. Sequential tests of statistical hypotheses. The Annals of Mathematical Statistics, 16(2):117-186, 1945. Google Scholar
  35. Abraham Wald and Jacob Wolfowitz. Optimum character of the sequential probability ratio test. The Annals of Mathematical Statistics, pages 326-339, 1948. Google Scholar
  36. Samuel K. Wang and Anastasios A. Tsiatis. Approximately optimal one-parameter boundaries for group sequential trials. Biometrics, pages 193-199, 1987. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact