# A Constant-per-Iteration Likelihood Ratio Test for Online Changepoint Detection for Exponential Family Models

arXiv: https://arxiv.org/abs/2302.04743 · HTML: https://mlsanity.com/paper/2302.04743/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 41 references that are in the map.
- First posted on arXiv 9 Feb 2023.

## Builds on (most cited first, 12 of 12)

- [Challenges and Opportunities in Edge Computing](https://mlsanity.com/paper/1609.01967/) (2016)
- [Multiple-change-point detection for high dimensional time series via sparsified binary segmentation](https://mlsanity.com/paper/1611.08639/) (2016)
- [High-dimensional, multiscale online changepoint detection](https://mlsanity.com/paper/2003.03668/) (2020)
- [NEWMA: a new method for scalable model-free online change-point detection](https://mlsanity.com/paper/1805.08061/) (2018)
- [Fast Online Changepoint Detection via Functional Pruning CUSUM statistics](https://mlsanity.com/paper/2110.08205/) (2021)
- [A Log-Linear Non-Parametric Online Changepoint Detection Algorithm based on Functional Pruning](https://mlsanity.com/paper/2302.02718/) (2023)
- [Detecting Abrupt Changes in the Presence of Local Fluctuations and Autocorrelated Noise](https://mlsanity.com/paper/2005.01379/) (2020)
- [Virtual Machine Warmup Blows Hot and Cold](https://mlsanity.com/paper/1602.00602/) (2016)
- [Sequential change-point detection in high-dimensional Gaussian graphical models](https://mlsanity.com/paper/1806.07870/) (2018)
- [A computationally efficient, high-dimensional multiple changepoint procedure with application to global terrorism incidence](https://mlsanity.com/paper/2011.03599/) (2020)
- [Changepoint detection in non-exchangeable data](https://mlsanity.com/paper/2111.05054/) (2021)
- [Multiple change point detection under serial dependence: Wild contrast maximisation and gappy Schwarz algorithm](https://mlsanity.com/paper/2011.13884/) (2020)

## Built on by (most cited first, 2 of 2)

- [Predictive maintenance solution for industrial systems -- an unsupervised approach based on log periodic power law](https://mlsanity.com/paper/2408.05231/) (2024)
- [An Efficient Likelihood Ratio Test for Online Changepoint Detection in the Presence of Autocorrelation](https://mlsanity.com/paper/2607.16106/) (2026)

## Abstract (arXiv)

Online changepoint detection algorithms that are based on 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.