Optimal network online change point localisation

We study the problem of online network change point detection. In this setting, a collection of independent Bernoulli networks is collected sequentially, and the underlying distributions change when a change point occurs. The goal is to detect the change point as quickly as possible, if it exists, subject to a constraint on the number or probability of false alarms. In this paper, on the detection delay, we establish a minimax lower bound and two upper bounds based on NP-hard algorithms and polynomial-time algorithms, i.e., [ mboxdetection delay begincases gtrsim log(1/α) fracmaxr2/n, , 1kappa02 n ρ, lesssim log(Delta/α) fracmaxr2/n, , log(r)kappa02 n ρ, & mboxwith NP-hard algorithms, lesssim log(Delta/α) fracrkappa02 n ρ, & mboxwith polynomial-time algorithms, endcases ] where kappa0, n, ρ, r and α are the normalised jump size, network size, entrywise sparsity, rank sparsity and the overall Type-I error upper bound. All the model parameters are allowed to vary as Delta, the location of the change point, diverges. The polynomial-time algorithms are novel procedures that we propose 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 outperform state-of-the-art methods.