Sequential change detection via backward confidence sequences

• URL: http://arxiv.org/abs/2302.02544v1
• Date: Mon, 6 Feb 2023 03:03:24 GMT
• Title: Sequential change detection via backward confidence sequences
• Authors: Shubhanshu Shekhar, Aaditya Ramdas
• Abstract summary: 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.
• Score: 40.79325752924537
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a simple reduction from sequential estimation to sequential changepoint detection (SCD). In short, suppose we are interested in detecting changepoints in some parameter or functional $\theta$ of the underlying distribution. We demonstrate that if we can construct a confidence sequence (CS) for $\theta$, then we can also successfully perform SCD for $\theta$. This is accomplished by checking if two CSs -- one forwards and the other backwards -- ever fail to intersect. Since the literature on CSs has been rapidly evolving recently, the reduction provided in this paper immediately solves several old and new change detection problems. Further, our "backward CS", constructed by reversing time, is new and potentially of independent interest. We provide strong nonasymptotic guarantees on the frequency of false alarms and detection delay, and demonstrate numerical effectiveness on several problems.

Related papers

• From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
  We analyze the forgetting, i.e., loss on previously seen tasks, after $k$ iterations.<n>We develop novel last-iterate upper bounds in the realizable least squares setup.<n>We prove for the first time that randomization alone, with no task repetition, can prevent catastrophic in sufficiently long task sequences.
  arXiv  Detail & Related papers  (2025-04-06T18:39:45Z)
• Post-detection inference for sequential changepoint localization [29.43493007296859]
  We study the problem of localizing the changepoint using only the data observed up to a data-dependent stopping time. We first construct confidence sets for the unknown changepoint when pre- and post-change distributions are assumed to be known. We then extend our framework to composite pre- and post-change scenarios.
  arXiv  Detail & Related papers  (2025-02-10T02:01:30Z)
• Quickest Change Detection with Confusing Change [26.769246781414545]
  This work studies a QCD problem where the change is either a bad change, which we aim to detect, or a confusing change, which is not of our interest. We propose novel CuSum-based detection procedures, S-CuSum and J-CuSum, leveraging two CuSum statistics. For both S-CuSum and J-CuSum, we provide analytical performance guarantees and validate them by numerical results.
  arXiv  Detail & Related papers  (2024-05-01T20:10:06Z)
• Reducing sequential change detection to sequential estimation [42.460619457560334]
  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.
  arXiv  Detail & Related papers  (2023-09-16T23:48:47Z)
• Discounted Thompson Sampling for Non-Stationary Bandit Problems [13.656518163592349]
  Non-stationary multi-armed bandit (NS-MAB) problems have recently received significant attention. We propose Discounted Thompson Sampling (DS-TS) with Gaussian priors to address both non-stationary settings. Our algorithm passively adapts to changes by incorporating a discounted factor into Thompson Sampling.
  arXiv  Detail & Related papers  (2023-05-18T05:29:52Z)
• Sequential Gradient Descent and Quasi-Newton's Method for Change-Point Analysis [0.348097307252416]
  One common approach to detecting change-points is minimizing a cost function over possible numbers and locations of change-points. This paper introduces a new sequential method (SE) that can be coupled with gradient descent (SeGD) and quasi-Newton's method (SeN) to find the cost value effectively.
  arXiv  Detail & Related papers  (2022-10-21T20:30:26Z)
• 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)
• Optimal network online change point localisation [73.93301212629231]
  We study the problem of online network change point detection. In this setting, a collection of independent Bernoulli networks is collected sequentially, and the underlying change point occurs. The goal is to detect the change point as quickly as possible, if it exists, subject to a constraint on the number or probability of false alarms.
  arXiv  Detail & Related papers  (2021-01-14T07:24:39Z)
• 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)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  This paper analyzes the trajectories of gradient descent (SGD) We show that SGD avoids saddle points/manifolds with $1$ for strict step-size policies.
  arXiv  Detail & Related papers  (2020-06-19T14:11:26Z)
• 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.