Reducing sequential change detection to sequential estimation

• URL: http://arxiv.org/abs/2309.09111v2
• Date: Sat, 25 Nov 2023 02:00:35 GMT
• Title: Reducing sequential change detection to sequential estimation
• Authors: Shubhanshu Shekhar and Aaditya Ramdas
• Abstract summary: We describe a simple reduction from sequential change detection to sequential estimation using confidence sequences. We prove that the average run length is at least $1/alpha$, resulting in a change detection scheme with minimal structural assumptions.
• Score: 42.460619457560334
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of sequential change detection, where the goal is to design a scheme for detecting any changes in a parameter or functional $\theta$ of the data stream distribution that has small detection delay, but guarantees control on the frequency of false alarms in the absence of changes. In this paper, we describe a simple reduction from sequential change detection to sequential estimation using confidence sequences: we begin a new $(1-\alpha)$-confidence sequence at each time step, and proclaim a change when the intersection of all active confidence sequences becomes empty. We prove that the average run length is at least $1/\alpha$, resulting in a change detection scheme with minimal structural assumptions~(thus allowing for possibly dependent observations, and nonparametric distribution classes), but strong guarantees. Our approach bears an interesting parallel with the reduction from change detection to sequential testing of Lorden (1971) and the e-detector of Shin et al. (2022).

Related papers

• Online Change Points Detection for Linear Dynamical Systems with Finite Sample Guarantees [1.6026317505839445]
  We study the online change point detection problem for linear dynamical systems with unknown dynamics. We develop a data-dependent threshold that can be used in our test that allows one to achieve a pre-specified upper bound on the probability of making a false alarm.
  arXiv  Detail & Related papers  (2023-11-30T18:08:16Z)
• Cal-DETR: Calibrated Detection Transformer [67.75361289429013]
  We propose a mechanism for calibrated detection transformers (Cal-DETR), particularly for Deformable-DETR, UP-DETR and DINO. We develop an uncertainty-guided logit modulation mechanism that leverages the uncertainty to modulate the class logits. Results corroborate the effectiveness of Cal-DETR against the competing train-time methods in calibrating both in-domain and out-domain detections.
  arXiv  Detail & Related papers  (2023-11-06T22:13:10Z)
• Sequential change detection via backward confidence sequences [40.79325752924537]
  We present a simple reduction from sequential estimation to sequential changepoint detection. We provide strong nonasymptotic guarantees on the frequency of false alarms and detection delay.
  arXiv  Detail & Related papers  (2023-02-06T03:03:24Z)
• E-detectors: a nonparametric framework for sequential change detection [86.15115654324488]
  We develop a fundamentally new and general framework for sequential change detection. Our procedures come with clean, nonasymptotic bounds on the average run length. We show how to design their mixtures in order to achieve both statistical and computational efficiency.
  arXiv  Detail & Related papers  (2022-03-07T17:25:02Z)
• Bandit Quickest Changepoint Detection [55.855465482260165]
  Continuous monitoring of every sensor can be expensive due to resource constraints. We derive an information-theoretic lower bound on the detection delay for a general class of finitely parameterized probability distributions. We propose a computationally efficient online sensing scheme, which seamlessly balances the need for exploration of different sensing options with exploitation of querying informative actions.
  arXiv  Detail & Related papers  (2021-07-22T07:25:35Z)
• Change Point Detection in Time Series Data using Autoencoders with a Time-Invariant Representation [69.34035527763916]
  Change point detection (CPD) aims to locate abrupt property changes in time series data. Recent CPD methods demonstrated the potential of using deep learning techniques, but often lack the ability to identify more subtle changes in the autocorrelation statistics of the signal. We employ an autoencoder-based methodology with a novel loss function, through which the used autoencoders learn a partially time-invariant representation that is tailored for CPD.
  arXiv  Detail & Related papers  (2020-08-21T15:03:21Z)
• Optimal Change-Point Detection with Training Sequences in the Large and Moderate Deviations Regimes [72.68201611113673]
  This paper investigates a novel offline change-point detection problem from an information-theoretic perspective. We assume that the knowledge of the underlying pre- and post-change distributions are not known and can only be learned from the training sequences which are available.
  arXiv  Detail & Related papers  (2020-03-13T23:39:40Z)
• High-dimensional, multiscale online changepoint detection [7.502070498889449]
  We introduce a new method for high-dimensional, online changepoint detection in settings where a $p$- Gaussian data stream may undergo a change in mean. The algorithm is online in the sense that both its storage requirements and worst-case computational complexity per new observation are independent of the number of previous observations. Simulations confirm the practical effectiveness of our proposal, which is implemented in the R package 'ocd', and we also demonstrate its utility on a seismology data set.
  arXiv  Detail & Related papers  (2020-03-07T21:54:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.