Inference in High-Dimensional Online Changepoint Detection

Abstract

We introduce and study two new inferential challenges associated with the sequential detection of change in a high-dimensional mean vector. First, we seek a confidence interval for the changepoint, and second, we estimate the set of indices of coordinates in which the mean changes. We propose an online algorithm that produces an interval with guaranteed nominal coverage, and whose length is, with high probability, of the same order as the average detection delay, up to a logarithmic factor. The corresponding support estimate enjoys control of both false negatives and false positives. Simulations confirm the effectiveness of our methodology, and we also illustrate its applicability on the U.S. excess deaths data from 2017 to 2020. The supplementary material, which contains the proofs of our theoretical results, is available online.

Keywords: Confidence interval; Sequential method; Sparsity; Support estimate.

Fig. 1

Coverage probabilities of the ocd_CI confidence interval as the parameter c, involved in the choice of tuning parameter d₁, varies.

Fig. 2

Support recovery properties of ocd_CI. In the left panel, we plot ROC curves for three different signal shapes and for sparsity levels $s\in \{5,50\}$. The triangles and circles correspond to points on the curves with $d_1=\sqrt{2\hspace{0.17em}\log \hspace{0.17em}(p/\alpha )}$ (with $\alpha =0.05$), and $d_1=\sqrt{2\hspace{0.17em}\log \hspace{0.17em}p}$, respectively. The dotted vertical line corresponds to $\mathbb{P}(\widehat{\mathcal{S}}\subseteq {\mathcal{S}}_{\beta })=1-\alpha$. In the right panel, we plot the proportion of 500 repetitions for which each coordinate belongs to $\widehat{\mathcal{S}}\cup \left\{\widehat{j}\right\}$ with $d_1=\sqrt{2\hspace{0.17em}\log \hspace{0.17em}p}$; here, the s = 20 signals have an inverse square root shape, and are plotted in red; noise coordinates are plotted in black. Other parameters for both panels: p = 100, $\Sigma =I_p,\beta =\vartheta =2,\mathcal{l}=0,a=\tilde{a}=\sqrt{2\hspace{0.17em}\log \hspace{0.17em}p}$.

Fig. 3

Standardized, transformed weekly excess death data from 12 states (including Washington, D.C.). The monitoring period starts from 30 June 2019 (dashed line). The data from the states in the support estimate are shown in red. The confidence interval [March 8, 2020, March 28, 2020] is shown in the light blue shaded region.