Sequential Changepoint Detection via Backward Confidence Sequences

Shubhanshu Shekhar, Aaditya Ramdas
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:30908-30930, 2023.

Abstract

We present a simple reduction from sequential estimation to sequential changepoint detection (SCD). In short, suppose we are interested in detecting changepoints in some parameter or functional $\theta$ of the underlying distribution. We demonstrate that if we can construct a confidence sequence (CS) for $\theta$, then we can also successfully perform SCD for $\theta$. This is accomplished by checking if two CSs — one forwards and the other backwards — ever fail to intersect. Since the literature on CSs has been rapidly evolving recently, the reduction provided in this paper immediately solves several old and new change detection problems. Further, our “backward CS”, constructed by reversing time, is new and potentially of independent interest. We provide strong nonasymptotic guarantees on the frequency of false alarms and detection delay, and demonstrate numerical effectiveness on several problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-shekhar23a, title = {Sequential Changepoint Detection via Backward Confidence Sequences}, author = {Shekhar, Shubhanshu and Ramdas, Aaditya}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {30908--30930}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/shekhar23a/shekhar23a.pdf}, url = {https://proceedings.mlr.press/v202/shekhar23a.html}, abstract = {We present a simple reduction from sequential estimation to sequential changepoint detection (SCD). In short, suppose we are interested in detecting changepoints in some parameter or functional $\theta$ of the underlying distribution. We demonstrate that if we can construct a confidence sequence (CS) for $\theta$, then we can also successfully perform SCD for $\theta$. This is accomplished by checking if two CSs — one forwards and the other backwards — ever fail to intersect. Since the literature on CSs has been rapidly evolving recently, the reduction provided in this paper immediately solves several old and new change detection problems. Further, our “backward CS”, constructed by reversing time, is new and potentially of independent interest. We provide strong nonasymptotic guarantees on the frequency of false alarms and detection delay, and demonstrate numerical effectiveness on several problems.} }
Endnote
%0 Conference Paper %T Sequential Changepoint Detection via Backward Confidence Sequences %A Shubhanshu Shekhar %A Aaditya Ramdas %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-shekhar23a %I PMLR %P 30908--30930 %U https://proceedings.mlr.press/v202/shekhar23a.html %V 202 %X We present a simple reduction from sequential estimation to sequential changepoint detection (SCD). In short, suppose we are interested in detecting changepoints in some parameter or functional $\theta$ of the underlying distribution. We demonstrate that if we can construct a confidence sequence (CS) for $\theta$, then we can also successfully perform SCD for $\theta$. This is accomplished by checking if two CSs — one forwards and the other backwards — ever fail to intersect. Since the literature on CSs has been rapidly evolving recently, the reduction provided in this paper immediately solves several old and new change detection problems. Further, our “backward CS”, constructed by reversing time, is new and potentially of independent interest. We provide strong nonasymptotic guarantees on the frequency of false alarms and detection delay, and demonstrate numerical effectiveness on several problems.
APA
Shekhar, S. & Ramdas, A.. (2023). Sequential Changepoint Detection via Backward Confidence Sequences. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:30908-30930 Available from https://proceedings.mlr.press/v202/shekhar23a.html.

Related Material