Sequential change‐point detection: Computation versus statistical performance

Haoyun Wang, Yao XieWiley 2023 · DOI

TL;DR

This paper provides a comprehensive tutorial on sequential change-point detection, focusing on the crucial trade-off between computational efficiency and statistical performance. It reviews classic and modern algorithms, highlighting how the demands of large-scale, real-time data necessitate a re-evaluation of traditional approaches.

What Problem Does This Paper Address?

The core problem addressed is the detection of changes in the underlying distribution of streaming data as quickly as possible after the change occurs. While traditional methods have focused on statistical power, the advent of massive, high-dimensional, and complex data streams (e.g., in sensor networks, internet traffic, social media) demands algorithms that are not only statistically robust but also computationally and memory-efficient. This creates a tension between achieving high statistical performance (e.g., low detection delay) and maintaining practical computational feasibility, a trade-off that has been historically underemphasized.

Methods

The paper surveys a range of sequential change-point detection procedures, categorizing them and discussing their strengths and weaknesses concerning the computation-performance trade-off. Key methods discussed include:

  • Classic Parametric Procedures:
    • CUSUM (Cumulative Sum): A popular recursive algorithm that offers constant computation and memory complexity, asymptotically optimal statistical performance, but requires precise knowledge of pre- and post-change distributions.
  • Shiryaev-Roberts (SR) Procedure: Similar to CUSUM, based on log-likelihood ratios, and optimal under certain criteria.
  • Generalized Likelihood Ratio (GLR) Procedure: Handles unknown post-change distributions by searching over possible parameters, but can be computationally intensive.
  • Window-limited GLR: A more efficient version of GLR that uses a sliding window, achieving constant complexity but potentially sacrificing some performance.
  • Shewhart Chart: A simpler approach, often based on scanning windows, which can be adapted for parametric or non-parametric settings but is generally not asymptotically optimal in the same sense as CUSUM.
  • Modern Approaches:
    • Adaptive CUSUM: Adapts the post-change distribution estimation within the CUSUM framework, offering robustness to unknown parameters.
  • E-detectors: A general framework for non-parametric and composite distribution families, providing a way to bound the Average Run Length (ARL).
  • Distribution-free methods: Employ alternative divergence measures (e.g., Maximum Mean Discrepancy - MMD) instead of likelihood ratios to avoid strong distributional assumptions.

The paper also delves into the analytical techniques used for performance evaluation, such as renewal theory and change-of-measure techniques, which are crucial for understanding metrics like Average Run Length (ARL) and Expected Detection Delay (EDD).

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and surveys existing methods rather than presenting new empirical studies on specific datasets.

Key Insights and Ideas

  • The Computation-Performance Trade-off is Paramount: The paper strongly emphasizes that for modern streaming data, the efficiency of an algorithm (computation and memory) is as critical as its statistical accuracy. Ignoring this can render even statistically powerful methods impractical.
  • CUSUM's Simplicity vs. Robustness: CUSUM's recursive nature and constant complexity make it attractive, but its reliance on exact distributional knowledge is a significant limitation in real-world scenarios where distributions are often unknown or misspecified.
  • Non-parametric Methods Offer Robustness at a Cost: While non-parametric approaches (like E-detectors and MMD-based methods) provide greater robustness to distributional assumptions, their theoretical analysis and performance guarantees can be significantly more challenging.
  • Windowing as a Practical Compromise: Sliding window techniques (e.g., Window-limited GLR, Window-limited CUSUM) offer a way to achieve constant computational complexity, but the choice of window size becomes a critical parameter balancing efficiency and performance.
  • Analytical Tools are Key: Techniques like renewal theory and change-of-measure are essential for rigorously analyzing the performance of these algorithms, especially for understanding rare event probabilities relevant to ARL and EDD.

Key Results

The paper doesn't present novel empirical results but rather synthesizes existing knowledge. Key theoretical results highlighted include:

  • Asymptotic Optimality Bounds: The paper discusses theoretical lower bounds for EDD, showing that procedures like CUSUM and GLR can achieve asymptotic optimality under certain conditions.
  • Performance Comparisons: Figure 1 and Table 1 visually and tabularly compare various procedures based on statistical performance, computation/memory complexity, and model robustness (assumptions on post-change distribution). This clearly illustrates that no single method excels in all aspects.
  • Analytical Formulas for Performance Metrics: The paper provides detailed derivations and approximations for ARL and EDD for classic procedures like CUSUM, using renewal theory and Wald's identity.

Limitations and Future Work

  • Focus on Classic Metrics: The paper acknowledges that other performance metrics exist (e.g., Maillard (2019); Yu et al. (2020); Chen et al. (2022)) but are not discussed due to space limitations.
  • EDD Analysis for Non-parametric Methods: The paper notes that EDD analysis for distribution-free methods remains an open question.
  • Machine Learning Approaches: The authors mention that machine learning-based sequential change-point detection, particularly for handling missing data, outliers, and cost-sensitive sampling, is an important direction not covered in detail.
  • Model Robustness vs. Optimality: While non-parametric methods offer robustness, they may not achieve the same theoretical optimality as parametric methods when distributions are known. The paper suggests that matching the theoretical lower bound on EDD with non-parametric methods is challenging, but their robustness is a significant advantage.

Summary updated

Abstract

Abstract Change‐point detection studies the problem of detecting the changes in the underlying distribution of the data stream as soon as possible after the change happens. Modern large‐scale, high‐dimensional, and complex streaming data call for computationally (memory) efficient sequential change‐point detection algorithms that are also statistically powerful. This gives rise to a computation versus statistical power trade‐off, an aspect less emphasized in the past in classic literature. This tutorial takes this new perspective and reviews several sequential change‐point detection procedures, ranging from classic sequential change‐point detection algorithms to more recent non‐parametric procedures that consider computation, memory efficiency, and model robustness in the algorithm design. Our survey also contains classic performance analysis, which provides useful techniques for analyzing new procedures. This article is categorized under: Statistical Models > Time Series Models Algorithms and Computational Methods > Algorithms Data: Types and Structure > Time Series, Stochastic Processes, and Functional Data
BibTeX
@inproceedings{wang2023sequential,
  author = {Haoyun Wang and Yao Xie},
  title = {{Sequential change‐point detection: Computation versus statistical performance}},
  booktitle = {Wiley},
  year = {2023},
  doi = {10.1002/wics.1628},
}
Figure