Online multivariate changepoint detection with type I error control and constant time/memory updates per series. (English) Zbl 1478.62255
Summary: This article presents a simple algorithm for online multivariate changepoint detection of a mean in rare changepoint settings. The algorithm is based on a modified cusum statistic and guarantees control of the type I error on any false discoveries, while featuring \(O(1)\) time and \(O(1)\) memory updates per series as well as a proven detection delay.
MSC:
| 62M10 | Time series, auto-correlation, regression, etc. in statistics (GARCH) |
| 62L10 | Sequential statistical analysis |
| 62G10 | Nonparametric hypothesis testing |
| 62J15 | Paired and multiple comparisons; multiple testing |
| 62P10 | Applications of statistics to biology and medical sciences; meta analysis |
References:
| [1] | Adams, R.; MacKay, D., Bayesian Online Changepoint Detection, 1-7 (2007), arXiv:0710.3742 |
| [2] | Aharoni, E.; Rosset, S., Generalized \(\alpha \)-investing: definitions, optimality results and application to public databases, J. R. Stat. Soc. Ser. B Stat. Methodol., 76, 4, 771-794 (2014) · Zbl 07555463 |
| [3] | Aue, A.; Hörmann, S.; Horváth, L.; Reimherr, M., Break detection in the covariance structure of multivariate time series models, Ann. Stat., 37, 6B, 4046-4087 (2009) · Zbl 1191.62143 |
| [4] | Chan, H., Optimal sequential detection in multi-stream data, Ann. Stat., 45, 6, 2736-2763 (2017) · Zbl 1388.62127 |
| [5] | Chen, Y.; Wang, T.; Samworth, R., ocd: High-Dimensional multiscale online changepoint detection (2020), R-package version 1.1: https://cran.r-project.org/package=ocd |
| [6] | Chen, Y.; Wang, T.; Samworth, R. J., High-Dimensional, Multiscale Online Changepoint Detection, 1-45 (2020), arXiv:2003.03668 |
| [7] | Fisher, R., Statistical Methods for Research Workers (1934), Oliver and Boyd Ltd: Oliver and Boyd Ltd Edinburgh · JFM 60.1162.01 |
| [8] | Foster, D.; Stine, R., \( \alpha \)-Investing: a procedure for sequential control of expected false discoveries, J. R. Stat. Soc. Ser. B Stat. Methodol., 70, 2, 429-444 (2008) · Zbl 1148.62065 |
| [9] | Gandy, A.; Hahn, G., MMCTest - A Safe algorithm for implementing multiple Monte Carlo tests, Scand. J. Stat., 41, 4, 1083-1101 (2014) · Zbl 1305.62270 |
| [10] | Hahn, G., fastOnlineCpt: Online Multivariate changepoint detection (2021), R-package version 1.0: https://cran.r-project.org/package=fastOnlineCpt |
| [11] | Hahn, G.; Fearnhead, P.; Eckley, I., BayesProject: Fast computation of a projection direction for multivariate changepoint detection, Stat. Comput., 30, 1691-1705 (2020) · Zbl 1452.62310 |
| [12] | Höhle, M., Online change-point detection in categorical time series, (Kneib, T.; Tutz, G., Statistical Modelling and Regression Structures (2010), Physica-Verlag), 377-397 |
| [13] | Höhle, M.; Meyer, S.; Paul, M.; Held, L.; Burkom, H.; Correa, T.; Hofmann, M.; Lang, C.; Manitz, J.; Riebler, A.; Bové, D.; Salmon, M.; Schumacher, D.; Steiner, S.; Virtanen, M.; Wei, W.; Wimmer, V., surveillance: Temporal And spatio-temporal modeling and monitoring of epidemic phenomena (2021), R-package version 1.19.1: https://cran.r-project.org/package=surveillance |
| [14] | Horváth, L.; Rice, G., Extensions of some classical methods in change point analysis, TEST, 23, 219-255 (2014) · Zbl 1305.62310 |
| [15] | Javanmard, A.; Montanari, A., Online rules for control of false discovery rate and false discovery exceedance, Ann. Stat., 46, 2, 526-554 (2018) · Zbl 1395.62221 |
| [16] | Knuth, D., The art of computer programming, (Seminumerical Algorithms, vol. 2 (1998), Addison-Wesley: Addison-Wesley Boston) · Zbl 0895.65001 |
| [17] | Matteson, D.; James, N., A nonparametric approach for multiple change point analysis of multivariate data, J. Am. Stat. Assoc., 109, 505, 334-345 (2012) · Zbl 1367.62260 |
| [18] | Mei, Y., Efficient scalable schemes for monitoring a large number of data streams, Biometrika, 97, 2, 419-433 (2010) · Zbl 1406.62088 |
| [19] | Page, E., Continuous inspection scheme, Biometrika, 41, 1/2, 110-115 (1954) · Zbl 0056.38002 |
| [20] | Ranganathan, A., PLISS: labeling places using online changepoint detection, Auton. Robot., 32, 351-368 (2012) |
| [21] | Siegmund, D.; Yakir, B.; Zhang, N., Detecting simultaneous variant intervals in aligned sequences, Ann. Appl. Stat., 5, 2A, 645-668 (2011) · Zbl 1223.62166 |
| [22] | Soh, Y.; Chandrasekaran, V., High-dimensional change-point estimation: Combining filtering with convex optimization, Appl. Comput. Harmon. A, 43, 1, 122-147 (2017) · Zbl 1366.62182 |
| [23] | Tartakovsky, A.; Rozovskii, B.; Blaz̆ek, R.; Kim, H., Detection of intrusions in information systems by sequential change-point methods, Stat. Methodol., 3, 3, 252-293 (2006) · Zbl 1248.94032 |
| [24] | Truong, C.; Oudre, L.; Vayatis, N., Selective review of offline change point detection methods, Signal. Process., 167, Article 107299 pp. (2020) |
| [25] | Wang, T.; Samworth, R., High dimensional change point estimation via sparse projection, J. R. Stat. Soc. Ser. B Stat. Methodol., 80, 1, 57-83 (2017) · Zbl 1439.62199 |
| [26] | Wang, T.; Samworth, R., InspectChangepoint: High-dimensional changepoint estimation via sparse projection (2020), R-package version 1.1: https://cran.r-project.org/package=InspectChangepoint |
| [27] | Welford, B., Note on a method for calculating corrected sums of squares and products, Technometrics, 4, 3, 419-420 (1962) |
| [28] | Xie, Y.; Siegmund, D., Sequential multi-sensor change-point detection, Ann. Stat., 41, 2, 670-692 (2013) · Zbl 1267.62084 |
| [29] | Zhang, N.; Siegmund, D.; Ji, H.; Li, J., Detecting simultaneous changepoints in multiple sequences, Biometrika, 97, 3, 631-645 (2010) · Zbl 1195.62168 |
| [30] | Zhang, J.; Wei, Z.; Yan, Z.; Zhou, M.; Pani, A., Online change-point detection in sparse time series with application to online advertising, IEEE Trans. Syst. Man Cybern. S, 49, 6, 1141-1151 (2019) |
| [31] | Zou, C.; Wang, Z.; Zi, X.; Jiang, W., An efficient online monitoring method for high-dimensional data streams, Technometrics, 57, 3, 374-387 (2015) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
