Higher-criticism for sparse multi-stream change-point detection

Tingnan Gong, Alon Kipnis, Yao XiearXiv 2024 · DOI · arXiv

Abstract

We study a statistical procedure based on higher criticism (HC) to address the sparse multi-stream quickest change-point detection problem. Namely, we aim to detect a potential change in the distribution of multiple data streams at some unknown time. If a change occurs, only a few streams are affected, whereas the identity of the affected streams is unknown. The HC-based procedure involves testing for a change point in individual streams and combining multiple tests using higher criticism. Relying on HC thresholding, the procedure also indicates a set of streams suspected to be affected by the change. We provide a theoretical analysis under a sparse heteroscedastic normal change-point model. We establish an information-theoretic detection delay lower bound when individual tests are based on the likelihood ratio or the generalized likelihood ratio statistics and show that the delay of the HC-based method converges in distribution to this bound. In the special case of constant variance, our bound coincides with known results. We demonstrate the effectiveness of the HC-based method compared to other methods in detecting sparse changes through extensive numerical evaluations.

Introduction

Monitoring a single data stream for a sudden change is a foundational statistical problem. However, modern applications—ranging from power grid sensor networks to financial market monitoring—often involve thousands of simultaneous streams. In these scenarios, a change may occur in only a tiny, unknown fraction of the streams. This "needle in a haystack" challenge is known as sparse multi-stream change-point detection.

A recent study by Gong, Kipnis, and Xie introduces a robust framework to address this problem by adapting Higher Criticism (HC) into a sequential detection procedure. Unlike traditional methods that may "wash out" sparse signals with noise from unaffected streams, the HC-based approach aggregates evidence across all streams to achieve optimal detection speed without requiring prior knowledge of the change's sparsity or magnitude.

Methodology: Local Testing and Global Aggregation

The proposed procedure operates in two primary stages:

  1. Local Testing: For each stream at every time step, a local detection statistic is calculated—typically the Cumulative Sum (CUSUM) for known change magnitudes or the Generalized Likelihood Ratio (GLR) for unknown magnitudes. These statistics are then transformed into P-values.
  2. Global Aggregation via Higher Criticism: These P-values are combined using the Higher Criticism (HC) statistic. HC acts as a goodness-of-fit test, identifying an excess of small P-values that indicate a deviation from the null hypothesis (no change). If the HC statistic exceeds a predefined threshold, a global alarm is triggered.
Visualization of the HC statistic over time (a) and its distribution before and after a change point (b).

As shown in Figure 1, the HC statistic ($HC^*$) remains low under the null hypothesis ($H_0$) but spikes significantly following a change point ($H_1$ at $t=2000$). The separation in the distribution of $HC^*$ before and after the change demonstrates its effectiveness as a detection metric.

Theoretical Foundations and Optimal Adaptivity

The researchers provide the first rigorous theoretical treatment of HC in a sequential, heteroscedastic setting where both mean and variance can change. A key contribution is the identification of an information-theoretic "phase transition" boundary. If a signal is too weak or too sparse, detection is mathematically impossible. The HC procedure is shown to be "optimally adaptive," reaching the theoretical speed limit for detection even when the sparsity level and change magnitude are unknown.

Theoretical detection delay $\Delta^*$ across different sparsity levels $\beta$ and signal magnitudes $r$.

Figure 4 illustrates the theoretical detection delay ($\Delta^*$) as a function of sparsity ($\beta$) and signal strength ($r$). The method's ability to maintain low delay across varying parameters highlights its robustness and efficiency.

Numerical Evaluation and Results

The effectiveness of the HC-based method was validated through extensive simulations using synthetic Gaussian data with up to 10,000 streams. Key findings include:

  • Minimal Delay: The detection delay of the HC method converges to the information-theoretic lower bound as the number of streams $N$ increases.
  • Superior Sparse Performance: In sparse settings, the HC method consistently outperformed state-of-the-art competitors, such as Mixture Likelihood Ratio and Fisher’s combination tests, often reducing detection delay by a significant margin.
  • Fault Localization: Because HC identifies which P-values contribute to the statistic's spike, it naturally identifies the specific streams likely affected by the change.

Conclusion and Future Directions

While the HC-based procedure is asymptotically optimal, some challenges remain. For a finite number of streams, there is still a performance gap compared to theoretical limits. Additionally, the current theory assumes independent data streams, whereas real-world streams are often correlated. Future work will focus on adapting HC to handle these dependencies and improving performance for extremely strict false alarm requirements (large Average Run Length).

Summary updated

Abstract

We study a statistical procedure based on higher criticism (HC) to address the sparse multi-stream quickest change-point detection problem. Namely, we aim to detect a potential change in the distribution of multiple data streams at some unknown time. If a change occurs, only a few streams are affected, whereas the identity of the affected streams is unknown. The HC-based procedure involves testing for a change point in individual streams and combining multiple tests using higher criticism. Relying on HC thresholding, the procedure also indicates a set of streams suspected to be affected by the change. We provide a theoretical analysis under a sparse heteroscedastic normal change-point model. We establish an information-theoretic detection delay lower bound when individual tests are based on the likelihood ratio or the generalized likelihood ratio statistics and show that the delay of the HC-based method converges in distribution to this bound. In the special case of constant variance, our bound coincides with known results in (Chan, 2017). We demonstrate the effectiveness of the HC-based method compared to other methods in detecting sparse changes through extensive numerical evaluations.
BibTeX
@misc{gong2024higher,
  author = {Tingnan Gong and Alon Kipnis and Yao Xie},
  title = {{Higher-criticism for sparse multi-stream change-point detection}},
  year = {2024},
  eprint = {2409.15597},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2409.15597},
}

Loading related content...

Figure