A Contrastive Approach to Online Change Point Detection

• URL: http://arxiv.org/abs/2206.10143v3
• Date: Mon, 6 Nov 2023 12:11:28 GMT
• Title: A Contrastive Approach to Online Change Point Detection
• Authors: Artur Goldman, Nikita Puchkin, Valeriia Shcherbakova, and Uliana Vinogradova
• Abstract summary: We suggest a novel procedure for online change point detection. Our approach expands an idea of maximizing a discrepancy measure between points from pre-change and post-change distributions. We prove non-asymptotic bounds on the average running length of the procedure and its expected detection delay.
• Score: 4.762323642506733
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We suggest a novel procedure for online change point detection. Our approach expands an idea of maximizing a discrepancy measure between points from pre-change and post-change distributions. This leads to a flexible procedure suitable for both parametric and nonparametric scenarios. We prove non-asymptotic bounds on the average running length of the procedure and its expected detection delay. The efficiency of the algorithm is illustrated with numerical experiments on synthetic and real-world data sets.

Related papers

• Conjugate Bayesian Two-step Change Point Detection for Hawkes Process [3.819329978428786]
  We propose a conjugate Bayesian two-step change point detection method for the Hawkes process. Experiments on both synthetic and real data demonstrate the superior effectiveness and efficiency of our method.
  arXiv  Detail & Related papers  (2024-09-26T07:16:38Z)
• Verification of Geometric Robustness of Neural Networks via Piecewise Linear Approximation and Lipschitz Optimisation [57.10353686244835]
  We address the problem of verifying neural networks against geometric transformations of the input image, including rotation, scaling, shearing, and translation. The proposed method computes provably sound piecewise linear constraints for the pixel values by using sampling and linear approximations in combination with branch-and-bound Lipschitz. We show that our proposed implementation resolves up to 32% more verification cases than present approaches.
  arXiv  Detail & Related papers  (2024-08-23T15:02:09Z)
• Continuous Optimization for Offline Change Point Detection and Estimation [0.0]
  It exploits reformulating the normal mean multiple change point model into a regularized statistical inverse problem enforcing sparsity. The recently developed framework of continuous optimization for best subset selection (COMBSS) is briefly introduced and related to the problem at hand. Supervised and unsupervised perspectives are explored with the latter testing different approaches for the choice of regularization penalty parameters.
  arXiv  Detail & Related papers  (2024-07-03T01:19:59Z)
• SPARE: Symmetrized Point-to-Plane Distance for Robust Non-Rigid Registration [76.40993825836222]
  We propose SPARE, a novel formulation that utilizes a symmetrized point-to-plane distance for robust non-rigid registration. The proposed method greatly improves the accuracy of non-rigid registration problems and maintains relatively high solution efficiency.
  arXiv  Detail & Related papers  (2024-05-30T15:55:04Z)
• Nonparametric Automatic Differentiation Variational Inference with Spline Approximation [7.5620760132717795]
  We develop a nonparametric approximation approach that enables flexible posterior approximation for distributions with complicated structures. Compared with widely-used nonparametrical inference methods, the proposed method is easy to implement and adaptive to various data structures. Experiments demonstrate the efficiency of the proposed method in approximating complex posterior distributions and improving the performance of generative models with incomplete data.
  arXiv  Detail & Related papers  (2024-03-10T20:22:06Z)
• Moreau Envelope ADMM for Decentralized Weakly Convex Optimization [55.2289666758254]
  This paper proposes a proximal variant of the alternating direction method of multipliers (ADMM) for distributed optimization. The results of our numerical experiments indicate that our method is faster and more robust than widely-used approaches.
  arXiv  Detail & Related papers  (2023-08-31T14:16:30Z)
• 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)
• 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)
• 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)
• 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.