TY - JOUR

T1 - A constant-per-iteration likelihood ratio test for online changepoint detection for exponential family models

AU - Ward, Kes

AU - Romano, Gaetano

AU - Eckley, Idris

AU - Fearnhead, Paul

PY - 2024/3/19

Y1 - 2024/3/19

N2 - Online changepoint detection algorithms that are based on (generalised) likelihood-ratio tests have been shown to have excellent statistical properties. However, a simple online implementation is computationally infeasible as, at time T, it involves considering O(T) possible locations for the change. Recently, the FOCuS algorithm has been introduced for detecting changes in mean in Gaussian data that decreases the per-iteration cost to $$O(\log T)$$. This is possible by using pruning ideas, which reduce the set of changepoint locations that need to be considered at time T to approximately $$\log T$$. We show that if one wishes to perform the likelihood ratio test for a different one-parameter exponential family model, then exactly the same pruning rule can be used, and again one need only consider approximately $$\log T$$locations at iteration T. Furthermore, we show how we can adaptively perform the maximisation step of the algorithm so that we need only maximise the test statistic over a small subset of these possible locations. Empirical results show that the resulting online algorithm, which can detect changes under a wide range of models, has a constant-per-iteration cost on average.

AB - Online changepoint detection algorithms that are based on (generalised) likelihood-ratio tests have been shown to have excellent statistical properties. However, a simple online implementation is computationally infeasible as, at time T, it involves considering O(T) possible locations for the change. Recently, the FOCuS algorithm has been introduced for detecting changes in mean in Gaussian data that decreases the per-iteration cost to $$O(\log T)$$. This is possible by using pruning ideas, which reduce the set of changepoint locations that need to be considered at time T to approximately $$\log T$$. We show that if one wishes to perform the likelihood ratio test for a different one-parameter exponential family model, then exactly the same pruning rule can be used, and again one need only consider approximately $$\log T$$locations at iteration T. Furthermore, we show how we can adaptively perform the maximisation step of the algorithm so that we need only maximise the test statistic over a small subset of these possible locations. Empirical results show that the resulting online algorithm, which can detect changes under a wide range of models, has a constant-per-iteration cost on average.

KW - Online changepoint

KW - Real-time analysis

KW - Ex-FOCuS

KW - Time series

U2 - 10.1007/s11222-024-10416-6

DO - 10.1007/s11222-024-10416-6

M3 - Journal article

VL - 34

JO - Statistics and Computing

JF - Statistics and Computing

SN - 0960-3174

IS - 3

M1 - 99

ER -