CoChat
Sign Up
Cited by 190Statistical Methods and InferenceProbability and Statistical ResearchAdvanced Bandit Algorithms Research

Time-uniform, nonparametric, nonasymptotic confidence sequences

Open access
Howard, Steven R., Ramdas, Aaditya, McAuliffe, Jon, Sekhon, Jasjeet·2021·The Annals of Statistics
DOI 10.1214/20-aos1991
Open this paper in CoChat — free accountOpen PDF

Abstract

A confidence sequence is a sequence of confidence intervals that is uniformly valid over an unbounded time horizon. Our work develops confidence sequences whose widths go to zero, with nonasymptotic coverage guarantees under nonparametric conditions. We draw connections between the Cramér–Chernoff method for exponential concentration, the law of the iterated logarithm (LIL) and the sequential probability ratio test—our confidence sequences are time-uniform extensions of the first; provide tight, nonasymptotic characterizations of the second; and generalize the third to nonparametric settings, including sub-Gaussian and Bernstein conditions, self-normalized processes and matrix martingales. We illustrate the generality of our proof techniques by deriving an empirical-Bernstein bound growing at a LIL rate, as well as a novel upper LIL for the maximum eigenvalue of a sum of random matrices. Finally, we apply our methods to covariance matrix estimation and to estimation of sample average treatment effect under the Neyman–Rubin potential outcomes model.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1214/20-aos1991

Cites

3 of 3 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Conditional Ville's inequality justifies acceptance when E_{k,n} ≥ 1/α_k at any inspected stopping time.

    “Conditional Ville's inequality justifies acceptance when E k,n ≥ 1/α k at any inspected stopping time (Howard et al., 2021;Waudby-Smith & Ramdas, 2024).”

    From SGM: A Statistical Godel Machine for Risk-Controlled Recursive Self-Modification (2025) · cites this paper as Howard et al., 2021

    Section 3.2 gives a time-uniform crossing bound for a supermartingale-based quantity at a threshold proportional to 1/α, and the discussion around Lemma 3 says sequential tests remain valid at stopping times. The paper does not state a conditional Ville inequality for E_{k,n} or justify the cited acceptance rule; its explicit testing example describes rejecting a null when a boundary is crossed. The indexed passages provide section labels but no page numbers. (LLM, conf=0.80)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 52

  1. ARMITAGE, P., MCPHERSON, C. K. and ROWE, B. C. (1969). Repeated significance tests on accumulating data. J. Roy. Statist. Soc. Ser. A 132 235-244. MR0250405 https://doi.org/10.2307/2343787 · DOI
  2. AUDIBERT, J.-Y., MUNOS, R. and SZEPESVÁRI, C. (2009). Exploration-exploitation tradeoff using variance estimates in multi-armed bandits. Theoret. Comput. Sci. 410 1876-1902. MR2514714 https://doi.org/10.1016/j.tcs.2009.01.016 · DOI
  3. AZUMA, K. (1967). Weighted sums of certain dependent random variables. Tohoku Math. J. (2) 19 357-367. MR0221571 https://doi.org/10.2748/tmj/1178243286 · DOI
  4. BALSUBRAMANI, A. (2014). Sharp finite-time iterated-logarithm martingale concentration. arXiv:1405.2639. · arXiv
  5. BALSUBRAMANI, A. and RAMDAS, A. (2016). Sequential nonparametric testing with the law of the iterated logarithm. In Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence. UAI'16 42-51. AUAI Press.
  6. BERCU, B., DELYON, B. and RIO, E. (2015). Concentration Inequalities for Sums and Mar- tingales. SpringerBriefs in Mathematics. Springer, Cham. MR3363542 https://doi.org/10.1007/ 978-3-319-22099-4 · DOI
  7. BERMAN, R., PEKELIS, L., SCOTT, A. and VAN DEN BULTE, C. (2018). p-hacking and false discovery in A/B testing. Technical Report No. 3204791. SSRN.
  8. BOUCHERON, S., LUGOSI, G. and MASSART, P. (2013). Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford Univ. Press, Oxford. With a foreword by Michel Ledoux. MR3185193 https://doi.org/10.1093/acprof:oso/9780199535255.001.0001 · DOI · Paper page
  9. CHERNOFF, H. (1952). A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23 493-507. MR0057518 https://doi.org/10.1214/aoms/1177729330 · DOI
  10. DARLING, D. A. and ROBBINS, H. (1967). Confidence sequences for mean, variance, and median. Proc. Natl. Acad. Sci. USA 58 66-68. MR0215406 https://doi.org/10.1073/pnas.58.1.66 · DOI
  11. DARLING, D. A. and ROBBINS, H. (1967). Iterated logarithm inequalities. Proc. Natl. Acad. Sci. USA 57 1188-1192. MR0211441 https://doi.org/10.1073/pnas.57.5.1188 · DOI
  12. DARLING, D. A. and ROBBINS, H. (1968). Some further remarks on inequalities for sample sums. Proc. Natl. Acad. Sci. USA 60 1175-1182. MR0235604 https://doi.org/10.1073/pnas.60.4.1175 · DOI
  13. DE LA PEÑA, V. H., KLASS, M. J. and LAI, T. L. (2004). Self-normalized processes: Exponential in- equalities, moment bounds and iterated logarithm laws. Ann. Probab. 32 1902-1933. MR2073181 https://doi.org/10.1214/009117904000000397 · DOI
  14. DE LA PEÑA, V. H., KLASS, M. J. and LAI, T. L. (2007). Pseudo-maximization and self-normalized processes. Probab. Surv. 4 172-192. MR2368950 https://doi.org/10.1214/07-PS119 · DOI
  15. DE LA PEÑA, V. H., KLASS, M. J. and LAI, T. L. (2009). Theory and applications of multivariate self- normalized processes. Stochastic Process. Appl. 119 4210-4227. MR2565565 https://doi.org/10.1016/ j.spa.2009.10.003 · DOI
  16. DE LA PEÑA, V. H., LAI, T. L. and SHAO, Q.-M. (2009). Self-Normalized Processes: Limit Theory and Statistical Applications. Probability and Its Applications (New York). Springer, Berlin. MR2488094 https://doi.org/10.1007/978-3-540-85636-8 · DOI
  17. EFRON, B. (1971). Forcing a sequential experiment to be balanced. Biometrika 58 403-417. MR0312660 https://doi.org/10.1093/biomet/58.3.403 · DOI · Paper page
  18. GARIVIER, A. (2013). Informational confidence bounds for self-normalized averages and applications. In 2013 IEEE Information Theory Workshop (ITW) 1-5. IEEE.
  19. GARIVIER, A. and LEONARDI, F. (2011). Context tree selection: A unifying view. Stochastic Process. Appl. 121 2488-2506. MR2832411 https://doi.org/10.1016/j.spa.2011.06.012 · DOI
  20. GITTENS, A. and TROPP, J. A. (2011). Tail bounds for all eigenvalues of a sum of random matrices. ACM Report 2014-02, Caltech.
  21. GRÜNWALD, P., DE HEIDE, R. and KOOLEN, W. (2019). Safe testing. arXiv:1906.07801. · arXiv
  22. HOWARD, S. R., RAMDAS, A., MCAULIFFE, J. and SEKHON, J. (2020). Time-uniform Chernoff bounds via nonnegative supermartingales. Probab. Surv. 17 257-317. MR4100718 https://doi.org/10.1214/ 18-PS321 · DOI
  23. HOWARD, S. R., RAMDAS, A., MCAULIFFE, J. and SEKHON, J. (2021). Supplement to "Time-uniform, nonparametric, nonasymptotic confidence sequences." https://doi.org/10.1214/20-AOS1991SUPP · DOI
  24. JAMIESON, K. and JAIN, L. (2018). A bandit approach to multiple testing with false discovery control. In Proceedings of the 32nd International Conference on Neural Information Processing Systems 3664- 3674.
  25. JAMIESON, K., MALLOY, M., NOWAK, R. and BUBECK, S. (2014). lil' UCB: An optimal exploration algorithm for multi-armed bandits. In Proceedings of the 27th Conference on Learning Theory 35 423-439.
  26. JAMIESON, K. and NOWAK, R. (2014). Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In 48th Annual Conference on Information Sciences and Systems (CISS) 1-6.
  27. JENNISON, C. and TURNBULL, B. W. (2000). Group Sequential Methods with Applications to Clinical Trials. CRC Press/CRC, Boca Raton, FL. MR1710781
  28. JOHARI, R., KOOMEN, P., PEKELIS, L. and WALSH, D. (2017). Peeking at A/B tests: Why it matters, and what to do about it. 1517-1525. ACM Press.
  29. JOHARI, R., PEKELIS, L. and WALSH, D. J. (2015). Always valid inference: Bringing sequential analysis to A/B testing. arXiv preprint arXiv:1512.04922. · arXiv
  30. JØRGENSEN, B. (1997). The Theory of Dispersion Models. Monographs on Statistics and Applied Proba- bility 76. CRC Press, London. MR1462891
  31. KAUFMANN, E. and KOOLEN, W. (2018). Mixture martingales revisited with applications to sequential tests and confidence intervals. arXiv:1811.11419. · arXiv
  32. KOLTCHINSKII, V. and LOUNICI, K. (2017). Concentration inequalities and moment bounds for sample covariance operators. Bernoulli 23 110-133. MR3556768 https://doi.org/10.3150/15-BEJ730 · DOI
  33. KULLDORFF, M., DAVIS, R. L., KOLCZAK, M., LEWIS, E., LIEU, T. and PLATT, R. (2011). A maximized sequential probability ratio test for drug and vaccine safety surveillance. Sequential Anal. 30 58-78. MR2770706 https://doi.org/10.1080/07474946.2011.539924 · DOI
  34. LAI, T. L. (1976). Boundary crossing probabilities for sample sums and confidence sequences. Ann. Probab. 4 299-312. MR0405578 https://doi.org/10.1214/aop/1176996135 · DOI
  35. LORDEN, G. and POLLAK, M. (2005). Nonanticipating estimation applied to sequential analy- sis and changepoint detection. Ann. Statist. 33 1422-1454. MR2195641 https://doi.org/10.1214/ 009053605000000183 · DOI
  36. MAURER, A. and PONTIL, M. (2009). Empirical Bernstein bounds and sample variance penalization. In Proceedings of the Conference on Learning Theory.
  37. MCDIARMID, C. (1998). Concentration. In Probabilistic Methods for Algorithmic Discrete Mathe- matics. Algorithms Combin. 16 195-248. Springer, Berlin. MR1678578 https://doi.org/10.1007/ 978-3-662-12788-9_6 · DOI
  38. ROBBINS, H. (1970). Statistical methods related to the law of the iterated logarithm. Ann. Math. Stat. 41 1397-1409. MR0277063 https://doi.org/10.1214/aoms/1177696786 · DOI
  39. ROBBINS, H. and SIEGMUND, D. (1969). Probability distributions related to the law of the iterated loga- rithm. Proc. Natl. Acad. Sci. USA 62 11-13. MR0242228 https://doi.org/10.1073/pnas.62.1.11 · DOI
  40. ROBBINS, H. and SIEGMUND, D. (1970). Boundary crossing probabilities for the Wiener process and sample sums. Ann. Math. Stat. 41 1410-1429. MR0277059 https://doi.org/10.1214/aoms/1177696787 · DOI
  41. ROBBINS, H. and SIEGMUND, D. (1972). A class of stopping rules for testing parametric hypotheses. In Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ.
  42. RUDELSON, M. (1999). Random vectors in the isotropic position. J. Funct. Anal. 164 60-72. MR1694526 https://doi.org/10.1006/jfan.1998.3384 · DOI
  43. SHAFER, G., SHEN, A., VERESHCHAGIN, N. and VOVK, V. (2011). Test martingales, Bayes factors and p-values. Statist. Sci. 26 84-101. MR2849911 https://doi.org/10.1214/10-STS347 · DOI
  44. SIEGMUND, D. (1978). Estimation following sequential tests. Biometrika 65 341-349. MR0513934 https://doi.org/10.2307/2335213 · DOI
  45. SIEGMUND, D. (1985). Sequential Analysis: Tests and Confidence Intervals. Springer Series in Statistics. Springer, New York. MR0799155 https://doi.org/10.1007/978-1-4757-1862-1 · DOI
  46. TROPP, J. A. (2011). Freedman's inequality for matrix martingales. Electron. Commun. Probab. 16 262- 270. MR2802042 https://doi.org/10.1214/ECP.v16-1624 · DOI
  47. VERSHYNIN, R. (2012). Introduction to the non-asymptotic analysis of random matrices. In Compressed Sensing 210-268. Cambridge Univ. Press, Cambridge. MR2963170
  48. WALD, A. (1945). Sequential tests of statistical hypotheses. Ann. Math. Stat. 16 117-186. MR0013275 https://doi.org/10.1214/aoms/1177731118 · DOI
  49. WALD, A. (1947). Sequential Analysis. Wiley, New York. MR0020764
  50. WHITEHEAD, J. and STRATTON, I. (1983). Group sequential clinical trials with triangular continuation regions. Biometrics 39 227-236. MR0712749 https://doi.org/10.2307/2530822 · DOI
  51. YANG, F., RAMDAS, A., JAMIESON, K. G. and WAINWRIGHT, M. J. (2017). A framework for Multi- A(rmed)/B(andit) testing with online FDR control. In 31st Conference on Neural Information Pro- cessing Systems.
  52. ZHAO, S., ZHOU, E., SABHARWAL, A. and ERMON, S. (2016). Adaptive concentration inequalities for sequential decision problems. In 30th Conference on Neural Information Processing Systems.

Cited by

Sorted by citations

Authors
Howard, S. R., Ramdas, A., McAuliffe, J., & Sekhon, J.
Affiliations
  • University of California, Berkeley (US)
  • Carnegie Mellon University (US)
  • Yale University (US)
Venue
The Annals of Statistics
Publisher
Institute of Mathematical Statistics
Published
2021-04-01
Volume
49
Issue
2
Pages
1055-1080
ISSN
  • 0090-5364 (ISSN-L)
  • 2168-8966
DOI
10.1214/20-aos1991
OpenAlex
W3030671780
Cited by
190
References
3
Citations by year
2026: 48 · 2025: 28 · 2024: 25 · 2023: 24 · 2022: 15 · 2021: 23 · 2020: 19 · 2019: 5 · 2018: 3
FWCI
15.59
Type
journal article
Language
en
Open access
Locations
  • The Annals of Statistics (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • National Science Foundation (1916320)
  • Office of Naval Research (N00014-15-1-2367, N00014-17-1-2176, N00014-17-1, N00014, N00014-17)
Topics
  • Physical Sciences › Mathematics › Statistics and Probability › Statistical Methods and Inference
  • Physical Sciences › Mathematics › Statistics and Probability › Probability and Statistical Research
  • Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
Keywords
confidence sequences, nonparametric statistics, law of the iterated logarithm, sequential probability ratio test, sub-Gaussian distributions, covariance matrix estimation

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review