Source-linked AI summary
Sequential (Quickest) Change Detection: Classical Results and New Directions
Liyan Xie, Shaofeng Zou, Yao Xie, Venugopal V. Veeravalli
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.
Source: §I · p. 1Method
The survey organizes classical results, generalizations, cross-disciplinary directions, applications, and methods for robust, data-efficient, and high-dimensional detection.
Source: §I · p. 1, D. Robust Sequential Change Detection · p. 10, E. Data-efficient Sequential Change… · p. 10Results
The survey shows that sequential change detection includes theoretically optimal procedures and practical advances such as data-efficient Shiryaev methods, sketching, and cybersecurity applications.
Source: 1) Minimax Optimality · p. 5, 2) Bayesian Optimality · p. 5, E. Data-efficient Sequential Change… · p. 11Takeaways & Limitations
Sequential change detection remains an active field whose intersections with other areas generate new research directions and applications.
Source: §VI · pp. 15–16
Abstract
from arXiv · showhide
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.Source: §I · p. 1
- The survey covers standard methods, fundamental results, recent advances, intersections with other fields, modern applications, and open questions.Source: §I · pp. 1–2
- Sequential detection differs from offline change detection because it operates in real time rather than retrospectively.Source: §I · pp. 1–2
- Sequential change detection identifies an unknown distributional change as quickly as possible under false-alarm constraints.Source: A. Problem Definition · p. 2
- A small mean shift from N(0, 1) to N(0.1, 1) at γ = 500 is difficult to see manually, motivating algorithmic detection.Source: A. Problem Definition · p. 2, Figure 1 · p. 2
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.Source: B. Mathematical Preliminaries · pp. 2–3
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.Source: 1) Shewhart Chart · p. 3
- Shewhart maximizes detection probability at the change under false-alarm constraints but can lose information by ignoring past observations.Source: 1) Shewhart Chart · p. 3
2) CUSUM Procedure:
- CUSUM accumulates past log-likelihood evidence and detects changes in drift by comparing exceedance over the past minimum with a threshold.Source: 2) Cumulative Sum (CUSUM) Procedure · p. 3
- CUSUM’s recursive computation enables efficient online implementation, while its maximum-likelihood interpretation estimates the unknown change-point location.Source: 2) Cumulative Sum (CUSUM) Procedure · p. 3
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.Source: 3) Shiryaev-Roberts Procedure · p. 3
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.Source: 1) Minimax Optimality · p. 4, D. Optimality · p. 4
- CUSUM is exactly optimal for Lorden’s formulation and asymptotically optimal for both Lorden’s and Pollak’s formulations.Source: 1) Minimax Optimality · p. 4
- Pollak’s criterion is less pessimistic than Lorden’s because WADD(τ) is at least CADD(τ) for every stopping time.Source: 1) Minimax Optimality · p. 4
- 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.Source: 1) Minimax Optimality · p. 5
- Both CUSUM and SR are asymptotically optimal under Lorden’s and Pollak’s formulations, with FAR decaying exponentially at exponent D(f1||f0).Source: 1) Minimax Optimality · pp. 4–5
- The CUSUM CADD versus −log(FAR) tradeoff has slope approximately 1/D(f1||f0), matching the asymptotic theory.Source: 1) Minimax Optimality · p. 5, Figure 2 · p. 5
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.Source: 2) Bayesian Optimality · p. 5
- The change-point is commonly modeled with a geometric prior because its memorylessness yields a tractable Bayesian formulation and convenient optimal solutions.Source: 2) Bayesian Optimality · p. 5
- The Shiryaev statistic is the posterior probability that the change has occurred, updated recursively and compared with threshold bα.Source: 2) Bayesian Optimality · p. 5
- The Shiryaev algorithm is Bayesian optimal when its threshold is selected to satisfy PFA(τS) = α.Source: 2) Bayesian Optimality · p. 5
- The Shiryaev statistic can be rewritten as a threshold comparison of a scaled likelihood ratio, reducing to the SR statistic when ρ = 0.Source: 2) Bayesian Optimality · p. 6
- A generalized Shewhart chart is Bayesian optimal under a geometric change-point prior and a known prior on the post-change parameter.Source: 2) Bayesian Optimality · p. 6
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.Source: 3) Evaluating the Performance Metrics · p. 6
- CADD and WADD can therefore be evaluated by setting γ = 1 without explicitly taking the supremum.Source: 3) Evaluating the Performance Metrics · p. 6
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.Source: 1) Mixture and Generalized Likelihood… · p. 6
- 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.Source: 1) Mixture and Generalized Likelihood… · p. 6
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.Source: 1) General Minimax Asymptotic Theory · pp. 6–7, A. General Asymptotic Theory for… · p. 6
- 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.Source: 1) General Minimax Asymptotic Theory · pp. 6–7
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.Source: 2) General Bayesian Asymptotic Theory · p. 7
- 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 −ρ)|.Source: 2) General Bayesian Asymptotic Theory · p. 7
- 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 − α.Source: 2) General Bayesian Asymptotic Theory · p. 7
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.Source: B. Change-of-measure to Obtain… · p. 7
- 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.Source: 1) Using Change-of-measure to Analyze… · pp. 7–8
- 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.Source: 1) Using Change-of-measure to Analyze… · pp. 7–8
- 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.Source: 2) Example: Analyzing MMD-based… · p. 8
- 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.Source: 2) Example: Analyzing MMD-based… · p. 8, Figure 3 · p. 8
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.Source: 1) Sequential Change Detection Under… · p. 9
- Transient-dynamics methods model the post-change regime as several phases with distinct data-generating distributions and seek rapid detection during the transient.Source: 1) Sequential Change Detection Under… · p. 9
- D-CUSUM and WD-CUSUM use generalized likelihood statistics that optimize over unknown change-points and transient durations in minimax settings.Source: 1) Sequential Change Detection Under… · p. 9
- Moving-anomaly detection addresses changes persistent across a network but not at any fixed node, where nodewise CUSUM approaches are unsuitable.Source: 2) Sequential Detection of Moving… · p. 9
- 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.Source: 2) Sequential Detection of Moving… · p. 9
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.Source: 4) Decentralized and Asynchronous… · pp. 9–10
- 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.Source: 4) Decentralized and Asynchronous… · p. 10
- 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.Source: D. Robust Sequential Change Detection · p. 10, 1) Robustness to Model Uncertainties · p. 10
- 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.Source: E. Data-efficient Sequential Change… · p. 11
- High-dimensional detection exploits sparsity, low-rankness, shrinkage, and missing-data methods to improve detection or computational efficiency.Source: F. High-dimensional Streaming Data · p. 11, 1) Sparse Change in Multiple Data… · p. 11
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.Source: 2) Subspace Change Detection · p. 11
- Missing-data methods combine subspace tracking with deviations from an evolving submanifold approximation to detect changes when not all entries are observed.Source: 3) Missing Data · p. 11
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.Source: 4) Sketching to Conquer… · p. 11
- Unknown post-change distributions motivate sequential diagnosis and joint estimation-detection procedures that trade detection power against estimation quality.Source: G. Joint Detection and Estimation · pp. 11–12
- Point-process methods cover Poisson, Hawkes, and networked event streams, while neural approaches use density-ratio estimation or online RNN anomaly scores.Source: H. Spatio-temporal Change Detection · p. 12, 1) Density Ratio Estimation · p. 12, 2) Anomaly Detection · p. 12
- Sequential change detection can use alternative delay metrics, including exponential penalties, when linear delay does not match an application’s objective.Source: J. Alternative Performance Metrics · p. 12
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.Source: 3) Online Learning and Change Detection · pp. 12–13
- 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.Source: 4) Tracking Data Dynamics · p. 13
- 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.Source: 5) Active Learning and Change Detection · p. 13
- 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.Source: 6) Detection with Data Privacy · p. 13, 7) Change Detection for Reinforcement… · p. 13, B. Distribution-free Methods · p. 13
- 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.Source: D. Optimization for Change Detection… · p. 14
- 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.Source: §V · p. 14
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.Source: A. Smart Grids · p. 14
- 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.Source: B. Cybersecurity · p. 14
- 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.Source: C. Sensors Networks · pp. 14–15
- 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.Source: D. Wireless Communications · p. 15
- 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.Source: E. Video Processing and Computer Vision · p. 15
- 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.Source: F. Social Networks · p. 15, G. Epidemiology · p. 15
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.Source: §VI · pp. 15–16