Optimal network online change point localisation
From MaRDI portal
Abstract: 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., [ mbox{detection delay} �egin{cases} gtrsim log(1/alpha) frac{max{r^2/n, , 1}}{kappa_0^2 n
ho},\ lesssim log(Delta/alpha) frac{max{r^2/n, , log(r)}}{kappa_0^2 n
ho}, & mbox{with NP-hard algorithms},\ lesssim log(Delta/alpha) frac{r}{kappa_0^2 n
ho}, & mbox{with polynomial-time algorithms}, end{cases} ] where 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 , 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.
This page was built for publication: Optimal network online change point localisation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q97728)
