Univariate mean change point detection: penalization, CUSUM and optimality

Abstract: The problem of univariate mean change point detection and localization based on a sequence of

n

independent observations with piecewise constant means has been intensively studied for more than half century, and serves as a blueprint for change point problems in more complex settings. We provide a complete characterization of this classical problem in a general framework in which the upper bound

s i g m a^{2}

on the noise variance, the minimal spacing

D e l t a

between two consecutive change points and the minimal magnitude

k a p p a

of the changes, are allowed to vary with

n

. We first show that consistent localization of the change points, when the signal-to-noise ratio

f r a c k a p p a s q r t D e l t a s i g m a < s q r t l o g (n)

, is impossible. In contrast, when

f r a c k a p p a s q r t D e l t a s i g m a

diverges with

n

at the rate of at least

s q r t l o g (n)

, we demonstrate that two computationally-efficient change point estimators, one based on the solution to an

e l l_{0}

-penalized least squares problem and the other on the popular wild binary segmentation algorithm, are both consistent and achieve a localization rate of the order

f r a c s i g m a^{2} k a p p a^{2} l o g (n)

. We further show that such rate is minimax optimal, up to a

l o g (n)

term.

Review text

Let \(X_1,\dots, X_n\) be independent sub-Gaussian random variables with continuous densities such that \(\mathbb{E}X_i=f_i\) and \(\max\limits_{i\in\{1,\dots,n\}}\|X_i-f_i\|\leqslant \sigma\), where \(\| \cdot\|\) denotes the Orlicz norm. Let \(\{\eta_0,\dots,\eta_K\}\subset\{1,\dots,n\}\) be a collection of change points such that \(1\leqslant\eta_0<\eta_1<\dots<\eta_K\leqslant n<\eta_{K+1}=n+1\) and \[ f_t\neq f_{t-1}\ \Leftrightarrow \ t\in\{\eta_1,\dots,\eta_K\}. \] Denote \(\min\limits_{k\in\{1,\dots,K+1\}}(\eta_k-\eta_{k-1})=\Delta\) and \(\min\limits_{k\in\{1,\dots,K\}}|f_{\eta_k}-f_{\eta_{k-1}}|=\kappa\). The model under consideration is completely defined by the sample size \(n\), the upper bound of fluctuation \(\sigma\), the minimal spacing between two consecutive change points \(\Delta\) and the lower bound of the jump size \(\kappa\). The authors of the paper consider the consistency of the change point estimators \(\{\widehat{\eta}_1< \dots <\widehat{\eta}_{\widehat{K}}\}\) such that \[ \widehat{K}=K,\ \max\limits_{k\in\{1,\dots,\widehat{K}\}}|\widehat{\eta}_k-\eta_k|\leqslant \varepsilon=\varepsilon(n), \] where the localization rate \(\varepsilon/\Delta\rightarrow 0\), as \(n\rightarrow\infty\), with probability close to the unit.

Recommendations

Cites work

Cited in

(36)

Describes a project that uses

Uses Software

wbs

This page was built for publication: Univariate mean change point detection: penalization, CUSUM and optimality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2180083)