Fast Online Changepoint Detection via Functional Pruning CUSUM Statistics
Gaetano Romano, Idris A. Eckley, Paul Fearnhead, Guillem Rigaill; 24(81):1−36, 2023.
Abstract
The ability to process high-frequency observations with limited computational resources is crucial for modern applications of online changepoint detection. Existing online algorithms for detecting a change in mean often require choosing a moving window or specifying the expected size of change, which limits their power to detect certain types of changes. In this paper, we propose an algorithm called Functional Online CuSUM (FOCuS) that addresses this limitation. FOCuS runs multiple instances of earlier methods simultaneously for all sizes of windows or all possible values for the size of change, thereby improving the detection power. Our theoretical analysis shows that FOCuS has a low computational cost per iteration, which is logarithmic in the number of observations. We demonstrate the practical utility of FOCuS by applying it to various scenarios of changes in mean and achieving state-of-the-art performance in detecting anomalous behavior in computer server data.
[abs]