Multi-stream Quickest Change Detection: Foundations and Recent Advances

Multi-stream Quickest Change Detection: A Comprehensive Overview

Introduction and Problem Formulation

Quickest change detection (QCD) is a well-established area of sequential inference aimed at minimizing detection delay when an abrupt change is present in stochastic processes, subject to false alarm constraints. Modern applications feature high-dimensional, multi-sensor environments—such as distributed monitoring, wireless sensor networks, and IoT platforms—where scalability and structural heterogeneity introduce new challenges beyond classical, single-stream formulations.

The reviewed paper situates QCD in multi-stream environments and delineates three principal challenges: (i) unknown high-dimensional post-change parameters, (ii) adaptive sensor sampling under resource constraints, and (iii) adjustments for multiple simultaneous detections. The authors present rigorous foundations and survey algorithmic advances addressing these challenges, with specific focus on statistical optimality and computational tractability.

Classical QCD Fundamentals

In the canonical single-stream QCD setting, the objective is to detect a distributional change from a pre-change density $f_0$ to post-change $f_1$ at unknown time $\nu$. Detection procedures are modeled as stopping times $T$, with performance indices such as average run length (ARL) to false alarm and average detection delay (ADD). Non-Bayesian approaches (Lorden, Pollak) provide minimax or conditional delay criteria, while Bayesian frameworks optimize expected delay with probabilistic false alarm constraints.

Two primary algorithms dominate classical QCD:

• CuSum: Recursively tracks cumulative log-likelihood ratios, offering exact minimax optimality with increasing threshold scale.
• Shiryaev-Roberts (SR): Aggregates likelihood ratios across all potential change points, yielding asymptotic optimality in both minimax and Bayesian settings.

Figure 1: Average detection delay versus change-point $\nu$ and worst-case delay versus log(ARL) for CuSum and SR; demonstrates tradeoffs between detection efficiency and false alarm control, with delay slopes matching reciprocal KL-divergence.

Empirical comparisons reveal that CuSum minimizes worst-case detection delay, while SR and Bayesian Shiryaev procedures can demonstrate superior performance for many $\nu$ when calibrated to identical ARL.

High-dimensional QCD: Unknown Parameters and Sparsity

Transitioning to multi-stream QCD, the data comprises vectors $X_n = [X_n^{(1)}, \ldots, X_n^{(K)}]$ with either independent or correlated structure. The change is parametrized by a (possibly sparse) unknown vector $\theta_1$.

When the affected sensors are represented by a binary $\theta_1$, generalized likelihood ratio (GLR) and mixture procedures asymptotically approach optimality, with the crucial caveat that complexity grows exponentially with $K$. Adaptive windowing and localized SUM-CuSum reduce computation and exploit independence, achieving first-order asymptotic optimality under streamwise changes.

In continuous parameter regimes—such as multivariate Gaussian mean-shifts—GLR delay scales as $f_1$0, introducing substantial overhead for high $f_1$1 [Siegmund, 2008].

Sparse change detection is addressed by thresholding and shrinkage estimation. Notable algorithms include:

• Mixture procedures (XS, Chan, OCD): Hypothesize sparsity and down-weight insignificantly affected streams for improved delay.
• Shrinkage/J-S estimation (WL-CuSum-ML, WL-CuSum-JS): Substitute maximum-likelihood with bias-variance-optimal estimators (e.g., James-Stein), outperforming standard methods in dense regimes [Halme2025QuickestEstimator].

Strong numerical results are reported:

Figure 2: Detection delay performance as a function of the sparsity of change; sparse-regime algorithms dominate for few affected streams, while James-Stein-based WL-CuSum excels as sparsity decreases.

It is asserted that substantial gains over classical GLR are possible, especially when detection procedures are aligned with post-change structure.

Sampling Constraints and Adaptive Sensing

QCD under limited sampling/communication seeks to minimize detection delay subject to only observing a subset of sensors per time instance. Cyclic scanning policies—sampling one or few streams until local CuSum statistics indicate reset or detection—are provably optimal in specific settings (e.g., $f_1$2), while adaptive exploration-based methods outperform myopic selection schemes in high $f_1$3/$f_1$4 ratios, notably with compensation increments for unobserved streams [Xu2025ImpactDetection]. Controlled sensing extends to general action spaces, where adaptive policies are driven by sample-based parameter estimation and Chernoff-rule-inspired action selection [VVV_Controlled].

Bandit and reinforcement learning frameworks—such as RMAB and Bayesian Thompson sampling—offer principled approaches to balancing exploration and exploitation in sensing policy design, though mapping per-action reward structures to QCD objectives remains nontrivial.

Multiple Detectors and False Discovery Rate Control

Applications requiring multiple change-point detections across streams motivate error metrics beyond per-stream ARL, notably false discovery rate (FDR). Sequential extensions of Benjamini-Hochberg procedures provide asymptotic FDR control under both Bayesian and non-Bayesian settings. Theoretical guarantees ensure global FDR is controlled as $f_1$5 [CHEN_ZHANG_POOR_BAYESIAN_JOURNAL]. It is explicitly claimed that controlling FDR non-asymptotically is feasible in the Bayesian setting via a common threshold.

Worst-case FDR control in the non-Bayesian context is shown to substantially increase detection delay, particularly when thresholding becomes aggressive with late-arriving change points. Recent work introduces error-over-patience (EOP) as a performance criterion, relaxing stringent requirements by scaling error with process duration [DANDAPANTHULA].

Alternative metrics, such as false non-discovery rate (FNR), formalize undetected but active streams, inviting further cross-stream performance analysis.

Nonparametric Techniques, Robustness, and Learning

While the bulk of QCD theory and practice relies on parametric models, contemporary use cases necessitate nonparametric, data-driven approaches. Kernel-based statistics (e.g., MMD, scan-B) and empirical likelihood substitutions for classical LR are prominent directions [Wei2026OnlineDetection]. E-detector theory formally generalizes LR-based procedures to nonparametric e-processes.

Robust statistical methods ensure close-to-optimality in nominal conditions and resilience to modeling deviations (e.g., outliers or misspecification) [UNNI_ROBUST, XIE_ROBUST, Hou2025RobustControl]. Semi-parametric strategies blend likelihood-based inference with empirical learning, enhancing reliability without explicit parametric constraints.

Resource-efficient policies employ reinforcement learning, including MAB and POMDP, for dynamic sensor selection and communication rate control, achieving significant savings in computational and energy budgets. Statistical censoring reduces transmission overhead with negligible losses in inference accuracy.

Implications and Future Outlook

Multi-stream QCD models and algorithms provide the foundation for rapid anomaly detection and resilient system design, from infrastructure monitoring to adaptive radio networks. The reviewed advances emphasize the importance of aligning algorithmic structure with application-specific signal heterogeneity, resource limitations, and global error metrics.

Outstanding theoretical challenges include designing optimal or near-optimal procedures for high-dimensional, multi-stream environments with tractable computation and accommodating partial specification or model uncertainty. The development of robust, adaptive, and learning-driven sensing policies under arbitrary dependence and heterogeneity is prioritized. The formulation of practical, stringent multi-criteria performance measures remains an active area of research.

Conclusion

The paper offers an authoritative synthesis of models, methodologies, and recent advances in multi-stream QCD. Balancing statistical optimality, computational feasibility, and operational constraints across high-dimensional, resource-limited, and multi-detection settings is imperative. Future work aims at scalable, robust, and learning-based change detection, with guarantees on global error rates and adaptive resource allocation (2604.18008).