Nonparametric Multi Change Point Detection for Markov Chains via Adaptive Clustering

Imon Banerjee, Jiaqi Lei, Sanjay Mehrotra
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:2224-2232, 2026.

Abstract

Offline change point detection tries to detect $\textit{time points}$ of distribution change in a given data sequence; and is now routinely used in signal processing, speech processing, climatology etc. Despite this broad applicability across economics, computer science, and planetary sciences, rigorous, nonparametric techniques for change point detection with non-independent and identically distributed (i.i.d.) datasets has remained elusive. This paper establishes such guarantees by proposing a non-parametric clustering algorithm which can accurately obtain the change points from a given Markovian dataset of length $n$. It does so by bridging together two different components of mathematical statistics; Rademacher complexities of Markov chains, and adaptive clustering via penalisation. Our first result uses recent advances in Rademacher complexities of regenerating Markov chains to derive a Dvoretzky Kiefer Wolfowitz (DKW) type inequality for the empirical distribution of the Markov chain. We then use this to show that an adaptive clustering algorithm recovers the correct change points for a Markovian sequence. We establish the tightness of our rates by showing that they essentially coincide with the best known rates for i.i.d. data. We end the paper by discussing the computational considerations of the problem.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-banerjee26c, title = { Nonparametric Multi Change Point Detection for Markov Chains via Adaptive Clustering }, author = {Banerjee, Imon and Lei, Jiaqi and Mehrotra, Sanjay}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {2224--2232}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/banerjee26c/banerjee26c.pdf}, url = {https://proceedings.mlr.press/v300/banerjee26c.html}, abstract = { Offline change point detection tries to detect $\textit{time points}$ of distribution change in a given data sequence; and is now routinely used in signal processing, speech processing, climatology etc. Despite this broad applicability across economics, computer science, and planetary sciences, rigorous, nonparametric techniques for change point detection with non-independent and identically distributed (i.i.d.) datasets has remained elusive. This paper establishes such guarantees by proposing a non-parametric clustering algorithm which can accurately obtain the change points from a given Markovian dataset of length $n$. It does so by bridging together two different components of mathematical statistics; Rademacher complexities of Markov chains, and adaptive clustering via penalisation. Our first result uses recent advances in Rademacher complexities of regenerating Markov chains to derive a Dvoretzky Kiefer Wolfowitz (DKW) type inequality for the empirical distribution of the Markov chain. We then use this to show that an adaptive clustering algorithm recovers the correct change points for a Markovian sequence. We establish the tightness of our rates by showing that they essentially coincide with the best known rates for i.i.d. data. We end the paper by discussing the computational considerations of the problem. } }
Endnote
%0 Conference Paper %T Nonparametric Multi Change Point Detection for Markov Chains via Adaptive Clustering %A Imon Banerjee %A Jiaqi Lei %A Sanjay Mehrotra %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-banerjee26c %I PMLR %P 2224--2232 %U https://proceedings.mlr.press/v300/banerjee26c.html %V 300 %X Offline change point detection tries to detect $\textit{time points}$ of distribution change in a given data sequence; and is now routinely used in signal processing, speech processing, climatology etc. Despite this broad applicability across economics, computer science, and planetary sciences, rigorous, nonparametric techniques for change point detection with non-independent and identically distributed (i.i.d.) datasets has remained elusive. This paper establishes such guarantees by proposing a non-parametric clustering algorithm which can accurately obtain the change points from a given Markovian dataset of length $n$. It does so by bridging together two different components of mathematical statistics; Rademacher complexities of Markov chains, and adaptive clustering via penalisation. Our first result uses recent advances in Rademacher complexities of regenerating Markov chains to derive a Dvoretzky Kiefer Wolfowitz (DKW) type inequality for the empirical distribution of the Markov chain. We then use this to show that an adaptive clustering algorithm recovers the correct change points for a Markovian sequence. We establish the tightness of our rates by showing that they essentially coincide with the best known rates for i.i.d. data. We end the paper by discussing the computational considerations of the problem.
APA
Banerjee, I., Lei, J. & Mehrotra, S.. (2026). Nonparametric Multi Change Point Detection for Markov Chains via Adaptive Clustering . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:2224-2232 Available from https://proceedings.mlr.press/v300/banerjee26c.html.

Related Material