E-detectors: a nonparametric framework for sequential change detection
- URL: http://arxiv.org/abs/2203.03532v4
- Date: Sun, 29 Oct 2023 23:35:18 GMT
- Title: E-detectors: a nonparametric framework for sequential change detection
- Authors: Jaehyeok Shin, Aaditya Ramdas, Alessandro Rinaldo
- Abstract summary: 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.
- Score: 86.15115654324488
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sequential change detection is a classical problem with a variety of
applications. However, the majority of prior work has been parametric, for
example, focusing on exponential families. We develop a fundamentally new and
general framework for sequential change detection when the pre- and post-change
distributions are nonparametrically specified (and thus composite). Our
procedures come with clean, nonasymptotic bounds on the average run length
(frequency of false alarms). In certain nonparametric cases (like sub-Gaussian
or sub-exponential), we also provide near-optimal bounds on the detection delay
following a changepoint. The primary technical tool that we introduce is called
an \emph{e-detector}, which is composed of sums of e-processes -- a fundamental
generalization of nonnegative supermartingales -- that are started at
consecutive times. We first introduce simple Shiryaev-Roberts and CUSUM-style
e-detectors, and then show how to design their mixtures in order to achieve
both statistical and computational efficiency. Our e-detector framework can be
instantiated to recover classical likelihood-based procedures for parametric
problems, as well as yielding the first change detection method for many
nonparametric problems. As a running example, we tackle the problem of
detecting changes in the mean of a bounded random variable without i.i.d.
assumptions, with an application to tracking the performance of a basketball
team over multiple seasons.
Related papers
- Causal Discovery-Driven Change Point Detection in Time Series [32.424281626708336]
Change point detection in time series seeks to identify times when the probability distribution of time series changes.
In practical applications, we may be interested only in certain components of the time series, exploring abrupt changes in their distributions.
arXiv Detail & Related papers (2024-07-10T00:54:42Z) - 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) - Graph Spatiotemporal Process for Multivariate Time Series Anomaly
Detection with Missing Values [67.76168547245237]
We introduce a novel framework called GST-Pro, which utilizes a graphtemporal process and anomaly scorer to detect anomalies.
Our experimental results show that the GST-Pro method can effectively detect anomalies in time series data and outperforms state-of-the-art methods.
arXiv Detail & Related papers (2024-01-11T10:10:16Z) - A Quadrature Rule combining Control Variates and Adaptive Importance
Sampling [0.0]
We show that a simple weighted least squares approach can be used to improve the accuracy of Monte Carlo integration estimates.
Our main result is a non-asymptotic bound on the probabilistic error of the procedure.
The good behavior of the method is illustrated empirically on synthetic examples and real-world data for Bayesian linear regression.
arXiv Detail & Related papers (2022-05-24T08:21:45Z) - Gaussian Process Uniform Error Bounds with Unknown Hyperparameters for
Safety-Critical Applications [71.23286211775084]
We introduce robust Gaussian process uniform error bounds in settings with unknown hyper parameters.
Our approach computes a confidence region in the space of hyper parameters, which enables us to obtain a probabilistic upper bound for the model error.
Experiments show that the bound performs significantly better than vanilla and fully Bayesian processes.
arXiv Detail & Related papers (2021-09-06T17:10:01Z) - Optimal Sequential Detection of Signals with Unknown Appearance and
Disappearance Points in Time [64.26593350748401]
The paper addresses a sequential changepoint detection problem, assuming that the duration of change may be finite and unknown.
We focus on a reliable maximin change detection criterion of maximizing the minimal probability of detection in a given time (or space) window.
The FMA algorithm is applied to detecting faint streaks of satellites in optical images.
arXiv Detail & Related papers (2021-02-02T04:58:57Z) - 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) - Online detection of local abrupt changes in high-dimensional Gaussian
graphical models [13.554038901140949]
The problem of identifying change points in high-dimensional Gaussian graphical models (GGMs) in an online fashion is of interest, due to new applications in biology, economics and social sciences.
We develop a novel test to address this problem that is based on the $ell_infty$ norm of the normalized covariance matrix of an appropriately selected portion of incoming data.
arXiv Detail & Related papers (2020-03-16T00:41:34Z) - 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.