High-Dimensional Change Point Detection using Graph Spanning Ratio
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918278132137984 |
|---|---|
| author | Sun, Yang-Wen Papagiannouli, Katerina Spokoiny, Vladimir |
| author_facet | Sun, Yang-Wen Papagiannouli, Katerina Spokoiny, Vladimir |
| contents | Inspired by graph-based methodologies, we introduce a novel graph-spanning algorithm designed to identify changes in both offline and online data across low to high dimensions. This versatile approach is applicable to Euclidean and graph-structured data with unknown distributions, while maintaining control over error probabilities. Theoretically, we demonstrate that the algorithm achieves high detection power when the magnitude of the change surpasses the lower bound of the minimax separation rate, which scales on the order of $\sqrt{nd}$. Our method outperforms other techniques in terms of accuracy for both Gaussian and non-Gaussian data. Notably, it maintains strong detection power even with small observation windows, making it particularly effective for online environments where timely and precise change detection is critical. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_07541 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | High-Dimensional Change Point Detection using Graph Spanning Ratio Sun, Yang-Wen Papagiannouli, Katerina Spokoiny, Vladimir Machine Learning Methodology (stat.ME) Inspired by graph-based methodologies, we introduce a novel graph-spanning algorithm designed to identify changes in both offline and online data across low to high dimensions. This versatile approach is applicable to Euclidean and graph-structured data with unknown distributions, while maintaining control over error probabilities. Theoretically, we demonstrate that the algorithm achieves high detection power when the magnitude of the change surpasses the lower bound of the minimax separation rate, which scales on the order of $\sqrt{nd}$. Our method outperforms other techniques in terms of accuracy for both Gaussian and non-Gaussian data. Notably, it maintains strong detection power even with small observation windows, making it particularly effective for online environments where timely and precise change detection is critical. |
| title | High-Dimensional Change Point Detection using Graph Spanning Ratio |
| topic | Machine Learning Methodology (stat.ME) |
| url | https://arxiv.org/abs/2512.07541 |