A non-parametric clustering algorithm which can accurately obtain the change points from a given Markovian dataset of length $n$ is proposed by bridging together two different components of mathematical statistics; Rademacher complexities of Markov chains, and adaptive clustering via penalisation.
Abstract
Offline change point detection tries to detect 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.
High-dimensional analogue: H\"older-Gauss-approximations, which can be (roughly) interpreted as the Gaussian approximation for a H\"older-norm of the high-dimensional partial sum process of the high-dimensional partial sum process is presented.
Patrick Bastian, Daria Tieplova, Nina Dörnemann et al.· 0 citations
SCAN is introduced, an offline method for detecting multiple distributional change-points in long, serially dependent univariate time series and achieves higher covering and F1-scores than competing methods across mean and joint mean-variance shifts, particularly under serial dependence.
Ashoka Prabashwara, P. Menéndez, Liam Hodgkinson et al.· 0 citations
We develop bootstrap-assisted robust binary segmentation (BARBS), a recursive binary segmentation method for multiple change point detection under general nonstationary temporal dynamics. A novel Gaussian multiplier bootstrap for the CUSUM statistics is proposed, offering robustness to complex dependence structures. Th...
We develop a framework for simultaneous change-point inference of high-dimensional functional time series. The observations are modeled as temporally dependent vectors whose coordinates take values in possibly different separable Hilbert spaces, thereby covering a broad class of functional data. Heterogeneous mean chan...
High-dimensional distributions can change without altering means or covariances, while the number of affected coordinates is often unknown. We propose nonparametric procedures that address both challenges through standardized rank comparisons of marginal distributions. Sum and maximum scans target dense and sparse chan...
We study nonparametric multiple change-point detection for high-dimensional sequences, aiming to identify time points at which the underlying distribution changes. While many existing methods perform well when change-points are well-separated, their performance can deteriorate when structural breaks are densely cluster...
Jinhyeok Park, Hyeyoung Maeng, Ho-Seung Song· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.