Post-detection inference for sequential changepoint localization

Aytijhya Saha, Aaditya Ramdas · 2025

Read Post-detection inference for sequential changepoint localization by Aytijhya Saha, Aaditya Ramdas (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-06096.txt.

Introduction

Aytijhya Saha and Aaditya Ramdas tackle a basic question in sequential data watching: once an alarm says a change has happened, how precisely can we say when it happened? Detectors can run under many rules and stop at data-dependent times, which breaks standard confidence methods. Their framework builds confidence sets for the change point using only the data seen up to the alarm.

The method makes no assumptions about the data's form after the change, the kind of observations, or the detector used. Its guarantees hold exactly, not just for huge samples. Extensions cover uncertainty before the change and the size of the jump in cleaner settings. Simulations show the sets are reasonably narrow in practice.

Catalog record

CREATORAytijhya Saha, Aaditya Ramdas
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE147 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-06096

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Post-detection inference for sequential changepoint localization Aytijhya Saha, Aaditya Ramdas Abstract This paper addresses a fundamental but largely unexplored challenge in sequential changepoint analysis: conducting inference following a detected change. We develop a very general framework to construct confidence sets for the unknown changepoint using only the data observed up to a data-dependent stopping time at which an arbitrary sequential detection algorithm declares a change. Our framework is nonparametric, making no assumption on the composite post-change class, the observation space, or the sequential detection procedure used, and is nonasymptotically valid. We also extend it to handle composite pre-change classes under a suitable assumption, and also derive confidence sets for the change magnitude in parametric settings. We provide theoretical guarantees on the width of the confidence intervals. Extensive simulations demonstrate that the produced sets have reasonable size, and slightly conservative coverage. In summary, we present the first general method for sequential changepoint localization, which is theoretically sound and broadly applicable in practice. 1 Introduction Consider the following general problem of sequential change analysis in an arbitrary space \mathcal{X} (which could be the Euclidean space \mathbb{R}^{d} , or images, or anything else). A sequence of \mathcal{X} -valued observations {\bf X}=X_{1},X_{2},\cdots arrives sequentially, such that for some unknown time T\in\mathbb{N}\cup\{\infty\} (the changepoint), X_{1},X_{2},\cdots,X_{T-1}\stackrel{{\scriptstyle}}{{\sim}}F_{0}\penalty\ \text{ and }\penalty\ X_{T},X_{T+1},\cdots\stackrel{{\scriptstyle}}{{\sim}}F_{1}, (1) for some F_{0} in a pre-change class \mathcal{P}_{0} and F_{1} in a post-change class \mathcal{P}_{1} , where \mathcal{P}_{0} and \mathcal{P}_{1} denote some non-intersecting classes of probability distributions. Initially, we shall assume all observations to be independent, although our methodology later extends to handling dependent data as well. Suppose the user has already decided to use a sequential changepoint detection algorithm \mathcal{A} for this task, which is a mapping from the data sequence \bf X to a stopping time 1 1 1 While sequential change detection methods are commonly described solely by stopping times, we describe them by algorithms \mathcal{A} because our method will feed in simulated (synthetically generated) data sequences \bf X^{\prime} into \mathcal{A} ; we find it easier to describe our methodology when making \mathcal{A} explicit. \tau=\mathcal{A}({\bf X}) at which it raises an alarm that a change may have previously occurred. When \mathcal{A} raises an alarm at time \tau , we do not know if it is a false alarm, and if it is not, then we only know that there has been some possible change before \tau , but not when that change occurred. Our aim here is to construct confidence sets for the unknown changepoint T after stopping at \tau , assuming only black-box access to \mathcal{A} (and ideally no further assumptions or restrictions). By “black-box”, we mean that we can run \mathcal{A} on any input data sequences we like, but we do not require any further insight into its inner workings. The fact that we do not require knowledge of internal details of \mathcal{A} is a particularly important feature; it implies that our changepoint localization method can wrap around any existing workflow for changepoint detection — it could be employed both with simple classical statistical algorithms (like CUSUM), and also with complex modern pipelines in the information technology industry that may involve heuristic machine learning algorithms (to deal with complex data types). For instance, rapid shifts in public sentiment often occur on online platforms: a product failure may trigger a sudden surge of negative reviews, or a major event may abruptly alter the tone of social-media discussions. Detecting when such a shift occurs is vital for understanding emerging issues, tracing public reactions to events, or monitoring product reputation in real time. To illustrate the relevance of our methodology in such settings, we conduct an experiment using the Stanford Sentiment Treebank (SST-2) dataset [ 34 ] , simulating a stream of text reviews whose sentiment abruptly transitions from predominantly positive to predominantly negative. Accurately localizing the changepoint is important: it can help investigate why the change may have occurred. As an initial goal, one may hope to obtain a set \mathcal{C}\subseteq\{1,\dots,\tau\} such that \mathbb{P}_{F_{0},T,F_{1}}(T\in\mathcal{C})\geq 1-\alpha, (2) where \mathbb{P}_{F_{0},T,F_{1}} is the data distribution in ( 1 ), i.e. having the true changepoint at T . But this goal is harder to achieve than may initally appear; we elaborate below. There are two classes of algorithms \mathcal{A} in the literature: (i) algorithms with probability of false alarm (PFA) bounded by \delta<1 ; we call these “bounded PFA” for short, and (ii) algorithms with PFA equal to one, but have a bounded average run length to false alarm (ARL2FA, or just ARL for short); we call these “bounded ARL”. Since algorithms with bounded ARL have PFA equal to one, false detections occur with a nontrivial frequency. But the flipside is that bounded ARL algorithms typically have smaller detection delay than bounded PFA algorithms. Typically, detection delays of bounded ARL algorithms can be bounded by quantities independent of the changepoint T , but this guarantee is impossible to achieve with bounded PFA algorithms. In this paper, we remain agnostic to the choice of \mathcal{A} . For algorithms with a bounded ARL, we prove that no set \mathcal{C} can satisfy guarantee ( 2 ) (for algorithms with bounded PFA, we show how to achieve ( 2 ) in the Supplementary Section F). This impossibility result (which we prove formally later) intuitively holds because it is meaningless to ask for coverage if the algorithm stopped before the changepoint; indeed, on the event \{\tau<T\} , we have no information to rule out the possibility that T=\infty , and thus the only way to cover T is to output the set of all natural numbers \mathbb{N} . Thus, an arguably more sensible goal is to have \mathbb{P}_{F_{0},T,F_{1}}(T\in\mathcal{C}\mid\tau\geq T)\geq 1-\alpha, (3) meaning that \mathcal{C} only needs to cover if algorithm \mathcal{A} only stops after the true changepoint T . This definition has been considered by, for example, [ 6 ] and [ 45 , 42 ] , who achieved it (in a certain asymptotic sense) in much more restricted settings than the current investigation. The aforesaid impossibility result no longer applies to the new goal ( 3 ). It is important to note that we do not prescribe which \mathcal{A} to use in which situation, but simply enable post-hoc inference on T for any user-chosen \mathcal{A} . One can view our techniques as providing a wrapper to convert \mathcal{A} from producing only a stopping time \tau to also producing a confidence set for T As we survey below, there is a rich literature on designing change detection algorithms \mathcal{A} , but a substantial paucity of inference methodology for localizing the change after detection; our focus is on the latter goal, assuming the user has chosen a suitable algorithm \mathcal{A} for detection. While inference for T is intrinsically interesting and important, a side benefit of confidence sets for T is that one can use these to derive post-hoc confidence sets for unknown parameters of F_{0} and F_{1} . To clarify, suppose \mathcal{P}_{i}=\{F_{\theta}\}_{\theta\in\Theta_{i}};i=0,1 . Our method that delivers ( 3 ) also delivers confidence sets \mathcal{C}^{\prime}\subseteq\Theta_{0}\times\Theta_{1} such that \mathbb{P}_{\theta_{0},T,\theta_{1}}((\theta_{0},\theta_{1})\in\mathcal{C}^{\prime}\mid\tau\geq T)\geq 1-\alpha,\forall\theta_{0}\in\Theta_{0},\theta_{1}\in\Theta_{1}, where \mathbb{P}_{\theta_{0},T,\theta_{1}} is the distribution of the sequence X_{1},\dots,X_{T-1}\stackrel{{\scriptstyle}}{{\sim}}F_{\theta_{0}} , X_{T},X_{T+1},\dots\stackrel{{\scriptstyle}}{{\sim}}F_{\theta_{1}} . We stress that our confidence sets do not rely on asymptotics and are valid in finite samples. 1.1 Related work

Read the complete text