Window-Limited CUSUM for Sequential Change Detection

Liyan Xie, George V. Moustakides, Yao Xie

TL;DR

This paper introduces the Window-Limited CUSUM (WLCUSUM), a novel sequential change detection algorithm that efficiently estimates unknown post-change parameters using a sliding window. WLCUSUM achieves first-order asymptotic optimality with significantly lower computational complexity than existing methods, making it more practical for real-world applications.

What Problem Does This Paper Address?

Online changepoint detection is crucial in many fields, aiming to detect shifts in data distributions as quickly as possible while minimizing false alarms. A common challenge arises when the post-change distribution is known in form but its parameters are unknown. Traditional CUSUM tests require these parameters to be known. While methods like the Generalized Likelihood Ratio (GLR) test exist for this scenario, they are computationally demanding due to per-sample recomputations. Existing window-limited GLR approaches reduce complexity but still require substantial computation. This paper addresses the need for a computationally efficient and asymptotically optimal method for detecting changes when post-change parameters are unknown.

Methods

The core contribution is the Window-Limited CUSUM (WLCUSUM). It adapts the classic CUSUM test by incorporating a sliding window-based consistent estimate of the unknown post-change parameters into the CUSUM statistic's updating formula. This differs from existing window-limited GLR methods that recompute the entire statistic. The WLCUSUM statistic is updated recursively, preserving the computational efficiency of the original CUSUM.

Key aspects of the method include:

  • Sliding Window Estimation: A window of size w is used to estimate the post-change parameters. The choice of w is critical and is analyzed for optimal performance.
  • Recursive Update: The WLCUSUM statistic is updated incrementally, similar to the standard CUSUM, making it computationally efficient.
  • Asymptotic Optimality: The paper proves that WLCUSUM achieves first-order asymptotic optimality, meaning its detection delay approaches the theoretical minimum as the average run length requirement grows.
  • Parallel Variant: A parallel WLCUSUM is proposed, running multiple WLCUSUMs with different window sizes simultaneously. This approach offers robustness and practical implementation advantages, especially when the optimal window size is unknown.

Datasets

The paper does not introduce new datasets. Instead, it uses simulated data for evaluation. The simulations are based on:

  • Univariate Normal Mean-Shift: Data generated from a normal distribution with a shift in the mean.
  • Multivariate Normal Mean-Shift: Similar to the univariate case but with higher dimensional parameter spaces.
  • Different Parametric Families: Scenarios where the pre-change distribution (Laplace) and post-change distribution (Normal) do not belong to the same family.

Key Insights and Ideas

  • Bridging the Gap: WLCUSUM effectively bridges the gap between the computationally simple but parameter-dependent CUSUM and the computationally intensive but parameter-agnostic GLR.
  • Window Size is Key: The choice of the sliding window size w is crucial for achieving both asymptotic optimality and computational efficiency. The paper provides theoretical guidance on selecting w.
  • Computational Efficiency: The recursive update mechanism is a major advantage, leading to significantly lower computational complexity compared to window-limited GLR, especially for larger window sizes.
  • Parallelism for Robustness: The parallel WLCUSUM variant offers a practical solution when the optimal window size is hard to determine, providing robust performance without requiring prior specification.
  • Asymptotic Optimality Achieved: Despite using an estimate, WLCUSUM achieves first-order asymptotic optimality, matching the theoretical performance of ideal detectors under large average run length constraints.

Key Results

  • First-Order Asymptotic Optimality: WLCUSUM is proven to be first-order asymptotically optimal. This means its detection delay converges to the optimal rate as the average run length (γ) goes to infinity.
  • Computational Complexity: WLCUSUM has a computational complexity of O(w) per update, while the parallel version is O(W) (where W is the maximum window size). This is significantly lower than the O(w²) complexity of the window-limited GLR.
  • Performance Comparison: Simulations show that WLCUSUM and its parallel variant perform comparably to or better than window-limited GLR, especially in more challenging detection scenarios, while being much more computationally efficient. The exact CUSUM (when parameters are known) generally performs best but is not applicable when parameters are unknown.
  • Optimal Window Size: The paper derives an optimal window size of w = Θ(√log γ) for achieving the best asymptotic performance.

Limitations and Future Work

  • Assumptions on Estimator: The theoretical analysis relies on certain assumptions about the estimator (e.g., unbiasedness, covariance properties). While these are met by common estimators like MLE, the analysis might need adjustments for other types of estimators.
  • Pre-change and Post-change Distribution Separation: The analysis assumes that the pre-change distribution is "a known distance away" from the post-change distribution sets. Addressing cases where these distributions are very close or identical would require significant modifications.
  • Future Research Directions:
    • More Efficient Estimators: Exploring "one-sample update" estimators, such as stochastic gradient descent, for potentially faster online estimation.
  • Relaxing Distribution Constraints: Investigating scenarios where the pre-change distribution is not strictly known or is closer to the post-change distribution.
  • Joint Detection and Estimation: Extending the framework to jointly optimize detection and estimation tasks, where estimation is not just auxiliary.

Summary updated

Abstract

We study the parametric online changepoint detection problem, where the underlying distribution of the streaming data changes from a known distribution to an alternative that is of a known parametric form but with unknown parameters. We propose a joint detection/estimation scheme, which we call Window-Limited CUSUM, that combines the cumulative sum (CUSUM) test with a sliding window-based consistent estimate of the post-change parameters. We characterize the optimal choice of the window size and show that the Window-Limited CUSUM enjoys first-order asymptotic optimality as average run length approaches infinity under the optimal choice of window length. Compared to existing schemes with similar asymptotic optimality properties, our test can be much faster computed because it can recursively update the CUSUM statistic by employing the estimate of the post-change parameters. A parallel variant is also proposed that facilitates the practical implementation of the test. Numerical simulations corroborate our theoretical findings.
BibTeX
@article{xie2023window,
  author = {Liyan Xie and George V. Moustakides and Yao Xie},
  title = {{Window-Limited CUSUM for Sequential Change Detection}},
  journal = {IEEE Trans. Information Theory},
  year = {2023},
  url = {https://openreview.net/forum?id=EP2TQFM1cm},
}
Figure