Network Online Change Point Localization

.We study the following online network change point detection settings: A time series of independent, possibly sparse Bernoulli networks whose distributions might change at an unknown time are observed in a sequential manner, and at each time point, a determination has to be made on whether a change has taken place in the near past. The goal is to detect the change point event (if any has occurred) as quickly as possible, subject to prespecified constraints on the probability or number of false alarms. We propose a CUSUM-based procedure and derive two high-probability upper bounds on its detection delay, i.e., detection delay \(\{ \gtrsim \log(1/\alpha)\frac{1}{\kappa_0^2 n \rho}\); \(\lesssim \log(\Delta/\alpha) \frac{r}{\kappa_0^2 n \rho}\), under a low-rank assumption; \(\lesssim \log(\Delta/\alpha) \frac{\max\{r^2/n, \log(r), 1\}}{\kappa_0^2 n \rho}\), under a block-constancy assumption, where \(\kappa_0, n, \rho, r\), and \(\alpha\) are the normalized jump size, network size, entrywise sparsity, rank sparsity, and overall type I error upper bound. All the model parameters are allowed to vary as \(\Delta\), the unknown change point, diverges. We further establish a minimax lower bound on the detection delay. Under the low-rank assumption and when the rank is of constant order or under the block-constancy assumption when the number of blocks \(r \lesssim \sqrt{n}\), we obtain minimax rates. The above upper bounds are achieved by novel procedures proposed in this paper, designed for quick detection under two different forms of type I error control. The first is based on controlling the overall probability of a false alarm when there are no change points, and the second is based on specifying a lower bound on the expected time of the first false alarm. Extensive experiments show that under different scenarios and the aforementioned forms of type I error control, our proposed approaches well outperform state-of-the-art methods.Keywordsdynamic networksonline change point detectionminimax optimalityMSC codes62C2062L99