Sequential (Quickest) Change Detection: Classical Results and New Directions

Liyan Xie; Shaofeng Zou; Yao Xie; Venugopal V. Veeravalli

Source-linked AI summary

Sequential (Quickest) Change Detection: Classical Results and New Directions

Liyan Xie, Shaofeng Zou, Yao Xie, Venugopal V. Veeravalli

arXiv:2104.04186v1Apr 9, 2021math.ST

TL;DR

Sequential change detection addresses how to detect abrupt distributional changes in streaming data quickly while limiting false alarms. The survey synthesizes classical theory and methods, modern extensions, cross-disciplinary directions, applications, and open questions. It presents optimal procedures alongside practical developments for robust, data-efficient, and high-dimensional settings.

Problem
Abrupt changes in streaming data can have serious consequences, creating a need for timely detection under false-alarm constraints.
Method
The survey organizes classical results, generalizations, cross-disciplinary directions, applications, and methods for robust, data-efficient, and high-dimensional detection.
Results
The survey shows that sequential change detection includes theoretically optimal procedures and practical advances such as data-efficient Shiryaev methods, sketching, and cybersecurity applications.
Takeaways & Limitations
Sequential change detection remains an active field whose intersections with other areas generate new research directions and applications.

Abstract

from arXiv · show

Online detection of changes in stochastic systems, referred to as sequential change detection or quickest change detection, is an important research topic in statistics, signal processing, and information theory, and has a wide range of applications. This survey starts with the basics of sequential change detection, and then moves on to generalizations and extensions of sequential change detection theory and methods. We also discuss some new dimensions that emerge at the intersection of sequential change detection with other areas, along with a selection of modern applications and remarks on open questions.

I. INTRODUCTION

Sequential change detection seeks to identify abrupt changes in streaming-data distributions quickly while controlling false alarms. This survey introduces classical foundations, extensions for modern data, applications, and related mathematical tools.

Modern applications challenge classical assumptions through dependence, nonstationarity, high dimensionality, and structured changes.
The survey covers standard methods, fundamental results, recent advances, intersections with other fields, modern applications, and open questions.
Sequential detection differs from offline change detection because it operates in real time rather than retrospectively.
Sequential change detection identifies an unknown distributional change as quickly as possible under false-alarm constraints.
A small mean shift from N(0, 1) to N(0.1, 1) at γ = 500 is difficult to see manually, motivating algorithmic detection.
B. Mathematical Preliminaries: The log-likelihood ratio has negative pre-change drift and positive post-change drift, with KL divergence characterizing the delay–false-alarm tradeoff.

C. Common Sequential Change Detection Procedures

Classical sequential procedures convert likelihood evidence into online alarms using different amounts of temporal information. Shewhart is simple and immediate, whereas CUSUM and SR aggregate past evidence for stronger delay-related performance.

1) Shewhart Chart:: The Shewhart chart compares the current observation or batch log-likelihood ratio with a threshold and is widely used because of its simplicity.
1) Shewhart Chart:: Shewhart maximizes detection probability at the change under false-alarm constraints but can lose information by ignoring past observations.
2) CUSUM Procedure:: CUSUM accumulates past log-likelihood evidence and detects changes in drift by comparing exceedance over the past minimum with a threshold.
2) CUSUM Procedure:: CUSUM’s recursive computation enables efficient online implementation, while its maximum-likelihood interpretation estimates the unknown change-point location.
3) Shiryaev-Roberts Procedure:: The SR procedure replaces CUSUM’s maximum over candidate change-points with a sum of likelihood ratios and also admits recursive computation.

D. Optimality

Sequential change detection balances false alarms against detection delay, with minimax formulations addressing unknown change-points and optimality results characterizing CUSUM, SR, and Shewhart procedures.

1) Minimax Optimality:: The minimax problem optimizes false-alarm rate and detection delay when the change-point is deterministic and unknown, using Lorden’s and Pollak’s criteria.
1) Minimax Optimality:: CUSUM is exactly optimal for Lorden’s formulation and asymptotically optimal for both Lorden’s and Pollak’s formulations.
1) Minimax Optimality:: Pollak’s criterion is less pessimistic than Lorden’s because WADD(τ) is at least CADD(τ) for every stopping time.
1) Minimax Optimality:: The Shewhart chart is optimal for maximizing detection probability at change occurrence subject to false-alarm constraints, and can be uniformly optimal under a monotone likelihood-ratio condition.
1) Minimax Optimality:: Both CUSUM and SR are asymptotically optimal under Lorden’s and Pollak’s formulations, with FAR decaying exponentially at exponent D(f1||f0).
1) Minimax Optimality:: The CUSUM CADD versus −log(FAR) tradeoff has slope approximately 1/D(f1||f0), matching the asymptotic theory.

2) Bayesian Optimality:

In the Bayesian setting, the change-point has a prior distribution and detection minimizes average delay subject to a false-alarm constraint. The Shiryaev procedure uses posterior change probabilities and is Bayesian optimal at the calibrated threshold.

2) Bayesian Optimality:: Bayesian sequential change detection minimizes average detection delay subject to a constraint on the probability of false alarm.
2) Bayesian Optimality:: The change-point is commonly modeled with a geometric prior because its memorylessness yields a tractable Bayesian formulation and convenient optimal solutions.
2) Bayesian Optimality:: The Shiryaev statistic is the posterior probability that the change has occurred, updated recursively and compared with threshold bα.
2) Bayesian Optimality:: The Shiryaev algorithm is Bayesian optimal when its threshold is selected to satisfy PFA(τS) = α.
2) Bayesian Optimality:: The Shiryaev statistic can be rewritten as a threshold comparison of a scaled likelihood ratio, reducing to the SR statistic when ρ = 0.
2) Bayesian Optimality:: A generalized Shewhart chart is Bayesian optimal under a geometric change-point prior and a known prior on the post-change parameter.

3) Evaluating the Performance Metrics:

For CUSUM and SR, the worst change-point in WADD and CADD occurs at time n = 1, simplifying evaluation of these performance metrics.

3) Evaluating the Performance Metrics:: For CUSUM, SR, and some other procedures, the supremum over change-points in WADD and CADD is attained at n = 1.
3) Evaluating the Performance Metrics:: CADD and WADD can therefore be evaluated by setting γ = 1 without explicitly taking the supremum.

E. Other Sequential Change Detection Procedures

Extensions of sequential change detection address unknown post-change distributions and non-i.i.d. observations, while preserving asymptotic performance guarantees under suitable conditions.

Mixture and Generalized Likelihood Ratio (GLR) Statistics: When post-change distributions are unknown, GLR methods estimate the parameter by maximizing likelihood, but their statistics generally cannot be updated recursively.Window-limited GLR methods reduce computational cost and can remain asymptotically optimal in certain cases with carefully chosen window sizes.
Mixture and Generalized Likelihood Ratio (GLR) Statistics: Mixture tests replace maximization over unknown parameters with a weighted average and can be first-order asymptotically optimal for practically any prior.The mixture-CUSUM statistic uses a weight function integrating or summing to 1 over the parameter space.
General Minimax Asymptotic Theory: Non-i.i.d. optimality theory has been extended to settings including regression, GARCH, non-stationary time series, general stochastic models, and hidden Markov models.These developments broaden sequential detection beyond independent observations.
General Minimax Asymptotic Theory: Under regularity conditions, generalized CUSUM for non-i.i.d. data asymptotically achieves Lai’s lower bound when b = | log α|.The generalized procedure replaces ordinary likelihood ratios with conditional likelihood ratios.

2) General Bayesian Asymptotic Theory:

In the Bayesian non-i.i.d. setting, exact Shiryaev solutions are generally difficult, so asymptotic theory characterizes when the algorithm remains optimal under regularity and convergence conditions.

General Bayesian Asymptotic Theory: For non-i.i.d. Bayesian observations, exact solutions to the Shiryaev problem are generally difficult to obtain.A recursive posterior expression is available when the changepoint has a geometric distribution, but not for a general prior.
General Bayesian Asymptotic Theory: The prior-tail parameter d distinguishes heavy-tailed changepoints, where d = 0, from exponentially tailed changepoints, where d > 0.For a geometric prior with parameter ρ, d = | log(1 −ρ)|.
General Bayesian Asymptotic Theory: The Shiryaev algorithm is asymptotically optimal for Bayesian detection as α →0 under regularity and additional rate-of-convergence conditions.The stated threshold is bα = 1 − α.

B. Change-of-measure to Obtain Accurate ARL Approximations

Change-of-measure methods approximate rare false-alarm probabilities and convert them into accurate ARL estimates for settings where exact analysis is difficult. For the sequential MMD procedure, the resulting threshold approximation agrees with simulation, especially after skewness correction.

Exact ARL expressions can be difficult for non-i.i.d. observations, GLR statistics, and nonparametric statistics, making simulation costly.
Change-of-measure evaluates rare threshold-crossing events under an alternative measure where they occur more frequently, then converts the probability back using Mill’s ratio.The alternative measure is chosen so the detection statistic’s expectation equals the threshold.
The ARL approximation first analyzes the probability of threshold crossing before a large time m and then relates that probability to the asymptotically exponential stopping-time distribution.For large m, P∞{τ ≤m} is approximated by 1−e^−λ_bm.
The MMD procedure compares a recent test block with reference blocks using an averaged, standardized kernel MMD statistic and stops when it exceeds threshold b.MMD measures distance between distributions; the statistic is small for similar distributions and large otherwise.
Theorem 3’s theoretical threshold for a target ARL is consistent with simulation, especially after skewness correction.The comparison demonstrates high-accuracy ARL approximation and can reduce expensive simulation-based calibration.

C. Non-stationary and Multiple Changes

Sequential change detection is extended to non-stationary and multiple-change settings because classical models assume one stationary post-change distribution. Recent methods address transient phases and anomalies that move across networks rather than persisting at individual nodes.

Classical formulations assume one stationary post-change distribution, an assumption that can be too restrictive for practical applications with richer post-change behavior.
Transient-dynamics methods model the post-change regime as several phases with distinct data-generating distributions and seek rapid detection during the transient.
D-CUSUM and WD-CUSUM use generalized likelihood statistics that optimize over unknown change-points and transient durations in minimax settings.
Moving-anomaly detection addresses changes persistent across a network but not at any fixed node, where nodewise CUSUM approaches are unsuitable.
Hidden-Markov and worst-case approaches model moving anomalies through topology-constrained trajectories or unknown deterministic paths, respectively.The hidden-Markov approach yields a first-order asymptotically optimal windowed GLR algorithm, while the worst-case CUSUM-type procedure is exactly optimal for homogeneous sensors.

3) Multiple Change Detection:

Modern sequential detection must handle distributed, asynchronous, robust, data-efficient, and high-dimensional settings. The surveyed methods adapt local statistics, mixture or shrinkage schemes, robust optimization, and observation control to these constraints.

Distributed detection combines sensor messages at a fusion center, while practical models allow different sensors to observe the change at different times.
For asynchronous or network-propagating changes, methods range from local-CUSUM alarms and summed statistics to procedures targeting a specified number of affected sensors.The S-CUSUM compares the sum of the smallest N−η+1 local CUSUM statistics with a threshold.
Robust sequential detection addresses model mismatch by using uncertainty sets, minimax criteria, and robust CUSUM formulations based on convex optimization.For covariance uncertainty, finding least-favorable distributions can be formulated as a semidefinite program.
Data-efficient Shiryaev detection is asymptotically optimal and, for Gaussian observations, stays within 10% of Shiryaev delay while reducing observation cost by more than 50%.It also substantially outperforms a priori fractional sampling in the reported comparisons.
High-dimensional detection exploits sparsity, low-rankness, shrinkage, and missing-data methods to improve detection or computational efficiency.

2) Subspace Change Detection:

High-dimensional change detection exploits structure in covariance, subspaces, missing observations, and network measurements. Related directions also extend sequential detection to unknown post-change models, point processes, machine learning, and alternative performance criteria.

2) Subspace Change Detection:: Subspace-CUSUM sequentially estimates an unknown post-change subspace in spiked covariance models and uses it to form a likelihood-ratio statistic.
2) Subspace Change Detection:: Missing-data methods combine subspace tracking with deviations from an evolving submanifold approximation to detect changes when not all entries are observed.
4) Sketching to Conquer High-dimensionality:: Sketching reduces high-dimensional observations to a small number of linear projections, enabling GLR detection with characterized performance and sketch requirements.In power networks, topology-constrained sketches represent aggregate measurements of edges or nodes for mean-shift detection.
Unknown post-change distributions motivate sequential diagnosis and joint estimation-detection procedures that trade detection power against estimation quality.
Point-process methods cover Poisson, Hawkes, and networked event streams, while neural approaches use density-ratio estimation or online RNN anomaly scores.
Sequential change detection can use alternative delay metrics, including exponential penalties, when linear delay does not match an application’s objective.

3) Online Learning and Change Detection:

Online learning and optimization extend sequential change detection to settings with unknown distributions, costly data acquisition, dynamic environments, and computational constraints. These directions include recursive updating, adaptive sampling, privacy-aware testing, reinforcement-learning integration, distribution-free statistics, and optimization-based guarantees.

Online implementations address nonrecursive procedures by updating unknown post-change parameters as new data arrive.Online mirror descent-based GLR and Bayesian computing are described as approaches to this implementation challenge.
Tracking can be combined with detection to handle normal data dynamics without mislabeling them as change-points.Solar flare detection is given as an example involving sparse changes in dynamically evolving high-dimensional data.
Active change-point detection adaptively selects the next input when observations are expensive to acquire.The setting is motivated by applications such as material science and seafloor-depth recovery.
Recent intersections include privacy-aware detection, reinforcement learning in changing environments, distribution-free tests, and dynamic multi-armed bandits.Change detection can trigger reinforcement-learning transitions and address piece-wise-stationary reward distributions, while nonparametric methods avoid explicit distributional assumptions.
Optimization-based approaches target computational efficiency and theoretical guarantees for estimating change-points in univariate and multivariate data.Examples include penalized least squares, dynamic programming, network binary segmentation, and filtered-derivative methods.
Sequential change detection originated in industrial process monitoring and now spans modern applications across multiple domains.The survey frames statistical process control as an early application while connecting sequential detection to newer online-learning directions.

A. Smart Grids

Sequential change detection supports monitoring across smart grids, sensor networks, communications, vision, social systems, and public health. The survey highlights domain-specific models and structured signals, including covariance changes, low-rank seismic structure, spatial-temporal dependence, and sparse solar-flare changes.

A. Smart Grids: Smart-grid methods monitor covariance or likelihood changes in synchronized power measurements for line outages, voltage quality, photovoltaic systems, and cyberattacks.The surveyed applications include decentralized detection and level-triggered sampling in grid monitoring.
Cybersecurity is a natural sequential-detection application because attacks alter network-traffic distributions and require real-time identification.Examples include denial-of-service, worm-based, port-scanning, and man-in-the-middle attacks.
Sensor-network applications cover seismic events, water safety, contamination, traffic anomalies, and distributed sensor faults.Methods exploit waveform-similarity low-rank structure, water-related spatial-temporal correlation, and correlated traffic anomalies.
Wireless-communication applications include user-activity detection, cognitive-radio spectrum opportunities, and low-probability-of-detection communication.These tasks apply sequential detection to changing channel activity or communication behavior.
Computer vision and video processing use sequential methods for scene, street-view, and video-sequence changes.The cited examples include pixel-based weightless neural networks and multi-image comparisons.
Social-network and public-health applications seek early detection of collective shocks, social stress, epidemics, and disease-related changes.Examples include network Hawkes processes and Bayesian or modified-CUSUM procedures for epidemic surveillance.
VI. CONCLUSIONS: The survey concludes by covering theoretically optimal and practical procedures, applications, and research directions created through intersections with other fields.Its stated goal is to summarize past and recent advances in sequential change detection.