2021/01/14 by Yi Yu, Yu, Yi, Oscar Hernán Madrid Padilla +5 · 3 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Statistical Process Monitoring #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Statistical Methods and Inference #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2101.05477
openalex publication_date 2021/01/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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., detection delay \begincases \gtrsim log(1/α) \fracmax\r2/n, 1\κ02 n ρ,
\lesssim log(Δ/α) \fracmax\r2/n, log(r)\κ02 n ρ, amp; with NP-hard algorithms,
\lesssim log(Δ/α) (r)/(κ02 n ρ), amp; with polynomial-time algorithms, \endcases where κ0, 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 Δ, 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.