E-detectors: A Nonparametric Framework for Sequential Change Detection
Volume 2, Issue 2 (2024), pp. 229–260
Pub. online: 1 December 2023
Type: Methodology Article
Open Access
Open Access
Area: Statistical Methodology
Accepted
12 October 2023
12 October 2023
Published
1 December 2023
1 December 2023
Abstract
Sequential change detection is a classical problem with a variety of applications. However, the majority of prior work has been parametric, for example, focusing on exponential families. We develop a fundamentally new and general framework for sequential change detection when the pre- and post-change distributions are nonparametrically specified (and thus composite). Our procedures come with clean, nonasymptotic bounds on the average run length (frequency of false alarms). In certain nonparametric cases (like sub-Gaussian or sub-exponential), we also provide near-optimal bounds on the detection delay following a changepoint. The primary technical tool that we introduce is called an e-detector, which is composed of sums of e-processes—a fundamental generalization of nonnegative supermartingales—that are started at consecutive times. We first introduce simple Shiryaev-Roberts and CUSUM-style e-detectors, and then show how to design their mixtures in order to achieve both statistical and computational efficiency. Our e-detector framework can be instantiated to recover classical likelihood-based procedures for parametric problems, as well as yielding the first change detection method for many nonparametric problems. As a running example, we tackle the problem of detecting changes in the mean of a bounded random variable without i.i.d. assumptions, with an application to tracking the performance of a basketball team over multiple seasons.
References
Chen, Y., Wang, T. and Samworth, R. J. (2022). High-dimensional, multiscale online changepoint detection. Journal of the Royal Statistical Society Series B: Statistical Methodology 84(1) 234–266. https://doi.org/10.1111/rssb.12447. MR4400396
Desobry, F., Davy, M. and Doncarli, C. (2005). An online kernel change detection algorithm. IEEE Transactions on Signal Processing 53(8) 2961–2974. https://doi.org/10.1109/TSP.2005.851098. MR2169647
Durrett, R. (2019) Probability: Theory and Examples 49. Cambridge University Press. https://doi.org/10.1017/9781108591034. MR3930614
Fan, X., Grama, I. and Liu, Q. (2015). Exponential inequalities for martingales with applications. Electronic Journal of Probability 20, 1. https://doi.org/10.1214/EJP.v20-3496. MR3311214
Gangrade, A., Rinaldo, A. and Ramdas, A. (2023). A Sequential Test for Log-Concavity. arXiv preprint arXiv:2301.03542.
Grünwald, P., de Heide, R. and Koolen, W. (2023). Safe testing. Journal of the Royal Statistical Society, Series B. 195 47–63. https://doi.org/10.1016/j.jspi.2017.09.014. MR3760837
Hadjiliadis, O., Zhang, H. and Poor, H. V. (2009). One shot schemes for decentralized quickest change detection. IEEE Transactions on Information Theory 55(7) 3346–3359. https://doi.org/10.1109/TIT.2009.2021311. MR2598025
Honda, J. and Takemura, A. (2015). Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards. Journal of Machine Learning Research 16 3721–3756. MR3450551
Howard, S. R., Ramdas, A., McAuliffe, J. and Sekhon, J. (2020). Time-uniform Chernoff bounds via nonnegative supermartingales. Probability Surveys 17 257–317. https://doi.org/10.1214/18-PS321. MR4100718
Howard, S. R., Ramdas, A., McAuliffe, J. and Sekhon, J. (2021). Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics 49(2) 1055–1080. https://doi.org/10.1214/20-aos1991. MR4255119
Lai, T. L. (1995). Sequential changepoint detection in quality control and dynamical systems. Journal of the Royal Statistical Society: Series B (Methodological) 57(4) 613–644. MR1354072
Lai, T. L. (1998). Information bounds and quick detection of parameter changes in stochastic systems. IEEE Transactions on Information Theory 44(7) 2917–2929. https://doi.org/10.1109/18.737522. MR1672051
Lai, T. L. (2001). Sequential analysis: some classical problems and new challenges. Statistica Sinica 11(2) 303–351. MR1844531
Lorden, G. (1970). On excess over the boundary. The Annals of Mathematical Statistics 41 520–527. https://doi.org/10.1214/aoms/1177697092. MR0254981
Lorden, G. (1971). Procedures for reacting to a change in distribution. The Annals of Mathematical Statistics 42 1897–1908. https://doi.org/10.1214/aoms/1177693055. MR0309251
Manole, T. and Ramdas, A. (2023). Martingale methods for sequential estimation of convex functionals and divergences. IEEE Transactions on Information Theory 69(7) 4641–4658. MR4613565
Mei, Y. (2010). Efficient scalable schemes for monitoring a large number of data streams. Biometrika 97(2) 419–433. https://doi.org/10.1093/biomet/asq010. MR2650748
Moustakides, G. V. (1986). Optimal stopping times for detecting changes in distributions. The Annals of Statistics 14(4) 1379–1387. https://doi.org/10.1214/aos/1176350164. MR0868306
Moustakides, G. V. (2008). Sequential change detection revisited. The Annals of Statistics 36(2) 787–807. https://doi.org/10.1214/009053607000000938. MR2396815
Page, E. S. (1954). Continuous inspection schemes. Biometrika 41(1/2) 100–115. https://doi.org/10.1093/biomet/41.1-2.100. MR0088850
Pollak, M. and Siegmund, D. (1975). Approximations to the expected sample size of certain sequential tests. The Annals of Statistics 3(6) 1267–1282. MR0403114
Pollak, M. (1985). Optimal detection of a change in distribution. The Annals of Statistics 13(1) 206–227. https://doi.org/10.1214/aos/1176346587. MR0773162
Polunchenko, A. S. and Tartakovsky, A. G. (2010). On optimality of the Shiryaev-Roberts procedure for detecting a change in distribution. The Annals of Statistics 38(6) 3445–3457. https://doi.org/10.1214/09-AOS775. MR2766858
Ramdas, A., Ruf, J., Larsson, M. and Koolen, W. (2020). Admissible anytime-valid sequential inference must rely on nonnegative martingales. arXiv preprint arXiv:2009.03167.
Ramdas, A., Ruf, J., Larsson, M. and Koolen, W. M. (2022). Testing exchangeability: Fork-convexity, supermartingales and e-processes. International Journal of Approximate Reasoning. 141 83–109. https://doi.org/10.1016/j.ijar.2021.06.017. MR4364897
Ramdas, A., Grünwald, P., Vovk, V. and Shafer, G. (2023). Game-theoretic statistics and safe anytime-valid inference. Statistical Science 38(4) 576–601. https://doi.org/10.1214/23-sts894. MR4665027
Ritov, Y. (1990). Decision theoretic optimality of the CUSUM procedure. The Annals of Statistics 18(3) 1464–1469. https://doi.org/10.1214/aos/1176347761. MR1062720
Roberts, S. (1966). A comparison of some control chart procedures. Technometrics 8(3) 411–430. https://doi.org/10.2307/1266688. MR0196887
Shafer, G. and Vovk, V. (2019) Game-Theoretic Foundations for Probability and Finance 455. John Wiley & Sons. https://doi.org/10.1002/0471249696. MR1852450
Shekhar, S. and Ramdas, A. (2023). Nonparametric two sample testing by betting. IEEE Transactions on Information Theory. https://doi.org/10.1109/TIT.2023.3305867
Shiryaev, A. N. (1963). On optimum methods in quickest detection problems. Theory of Probability & Its Applications 8(1) 22–46. MR0155708
Siegmund, D. and Venkatraman, E. (1995). Using the generalized likelihood ratio statistic for sequential detection of a change-point. The Annals of Statistics 23 255–271. https://doi.org/10.1214/aos/1176324466. MR1331667
Tartakovsky, A., Nikiforov, I. and Basseville, M. (2014) Sequential Analysis: Hypothesis Testing and Changepoint Detection. CRC Press. MR3241619
Tartakovsky, A. G. (2014). Nearly optimal sequential tests of composite hypotheses revisited. Proceedings of the Steklov Institute of Mathematics 287(1) 268–288. https://doi.org/10.1134/S0081543814080161. MR3484334
Tartakovsky, A. G., Pollak, M. and Polunchenko, A. S. (2012). Third-order Asymptotic Optimality of the Generalized Shiryaev–Roberts Changepoint Detection Procedures. Theory of Probability & Its Applications 56(3) 457–484. https://doi.org/10.4213/tvp4406. MR3136464
Ville, J. (1939). Étude critique de la notion de collectif. Monographies des Probabilités 3 144. MR3533075
Vovk, V. (2021). Testing randomness online. Statistical Science 36(4) 595–611. https://doi.org/10.1214/20-sts817. MR4323055
Vovk, V., Gammerman, A. and Shafer, G. (2005) Algorithmic Learning in a Random World. Springer Science & Business Media. MR2161220
Wang, H. and Ramdas, A. (2023). Catoni-style confidence sequences for heavy-tailed mean estimation. Stochastic Processes and Applications 163 168–202. https://doi.org/10.1016/j.spa.2023.05.007. MR4610125
Wasserman, L., Ramdas, A. and Balakrishnan, S. (2020). Universal inference. Proceedings of the National Academy of Sciences 117(29) 16880–16890. https://doi.org/10.1073/pnas.1922664117. MR4242731
Willsky, A. and Jones, H. (1976). A generalized likelihood ratio approach to the detection and estimation of jumps in linear systems. IEEE Transactions on Automatic Control 21(1) 108–112. https://doi.org/10.1109/tac.1976.1101146. MR0396019
Xie, Y. and Siegmund, D. (2013). Sequential multi-sensor change-point detection. In 2013 Information Theory and Applications Workshop (ITA) 1–20. IEEE. https://doi.org/10.1214/13-AOS1094. MR3099117
Zou, S., Veeravalli, V. V., Li, J. and Towsley, D. (2019). Quickest detection of dynamic events in networks. IEEE Transactions on Information Theory 66(4) 2280–2295. https://doi.org/10.1109/TIT.2019.2948350. MR4087685
