High-dimensional, multiscale online changepoint detection
- URL: http://arxiv.org/abs/2003.03668v2
- Date: Sat, 10 Oct 2020 15:46:08 GMT
- Title: High-dimensional, multiscale online changepoint detection
- Authors: Yudong Chen, Tengyao Wang and Richard J. Samworth
- Abstract summary: 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.
- Score: 7.502070498889449
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce a new method for high-dimensional, online changepoint detection
in settings where a $p$-variate Gaussian data stream may undergo a change in
mean. The procedure works by performing likelihood ratio tests against simple
alternatives of different scales in each coordinate, and then aggregating test
statistics across scales and coordinates. 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; in
practice, it may even be significantly faster than this. We prove that the
patience, or average run length under the null, of our procedure is at least at
the desired nominal level, and provide guarantees on its response delay under
the alternative that depend on the sparsity of the vector of mean change.
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.
Related papers
- Low-rank extended Kalman filtering for online learning of neural
networks from streaming data [71.97861600347959]
We propose an efficient online approximate Bayesian inference algorithm for estimating the parameters of a nonlinear function from a potentially non-stationary data stream.
The method is based on the extended Kalman filter (EKF), but uses a novel low-rank plus diagonal decomposition of the posterior matrix.
In contrast to methods based on variational inference, our method is fully deterministic, and does not require step-size tuning.
arXiv Detail & Related papers (2023-05-31T03:48:49Z) - A Log-Linear Non-Parametric Online Changepoint Detection Algorithm based
on Functional Pruning [5.202524136984542]
We build a flexible nonparametric approach to detect a change in the distribution of a sequence.
Thanks to functional pruning ideas, NP-FOCuS has a computational cost that is log-linear in the number of observations.
In terms of detection power, NP-FOCuS is seen to outperform current nonparametric online changepoint techniques in a variety of settings.
arXiv Detail & Related papers (2023-02-06T11:50:02Z) - Online Kernel CUSUM for Change-Point Detection [12.383181837411469]
We present a computationally efficient online kernel Cumulative Sum (CUSUM) method for change-point detection.
Our approach exhibits increased sensitivity to small changes compared to existing kernel-based change-point detection methods.
arXiv Detail & Related papers (2022-11-28T05:08:30Z) - 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) - SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
Existing implementations of KRR require that all the data is stored in the main memory.
We propose StreaMRAK - a streaming version of KRR.
We present a showcase study on two synthetic problems and the prediction of the trajectory of a double pendulum.
arXiv Detail & Related papers (2021-08-23T21:03:09Z) - Fast and Robust Online Inference with Stochastic Gradient Descent via
Random Scaling [0.9806910643086042]
We develop a new method of online inference for a vector of parameters estimated by the Polyak-Rtupper averaging procedure of gradient descent algorithms.
Our approach is fully operational with online data and is rigorously underpinned by a functional central limit theorem.
arXiv Detail & Related papers (2021-06-06T15:38:37Z) - Partially Observable Online Change Detection via Smooth-Sparse
Decomposition [16.8028358824706]
We consider online change detection of high dimensional data streams with sparse changes, where only a subset of data streams can be observed at each sensing time point due to limited sensing capacities.
On the one hand, the detection scheme should be able to deal with partially observable data and meanwhile have efficient detection power for sparse changes.
In this paper, we propose a novel detection scheme called CDSSD. In particular, it describes the structure of high dimensional data with sparse changes by smooth-sparse decomposition.
arXiv Detail & Related papers (2020-09-22T16:03:04Z) - 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) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
In this work, we seek to balance the fact that attenuating step-size is required for exact convergence with the fact that constant step-size learns faster in time up to an error.
Rather than fixing the minibatch the step-size at the outset, we propose to allow parameters to evolve adaptively.
arXiv Detail & Related papers (2020-07-02T16:02:02Z) - 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)
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.