Robust and efficient change point detection using novel multivariate rank-energy GoF test

• URL: http://arxiv.org/abs/2111.00047v1
• Date: Fri, 29 Oct 2021 19:08:57 GMT
• Title: Robust and efficient change point detection using novel multivariate rank-energy GoF test
• Authors: Shoaib Bin Masud
• Abstract summary: We show that directly using Rank Energy (RE) leads to high sensitivity to very small changes in distributions. We propose soft-Rank Energy (sRE) that is based on entropy regularized OT and employ it towards CPD. We discuss the advantages of using sRE over RE and demonstrate that the proposed sRE based CPD outperforms all the existing methods in terms of Area Under the Curve (AUC) and F1-score on real and synthetic data sets.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we use and further develop upon a recently proposed multivariate, distribution-free Goodness-of-Fit (GoF) test based on the theory of Optimal Transport (OT) called the Rank Energy (RE) [1], for non-parametric and unsupervised Change Point Detection (CPD) in multivariate time series data. We show that directly using RE leads to high sensitivity to very small changes in distributions (causing high false alarms) and it requires large sample complexity and huge computational cost. To alleviate these drawbacks, we propose a new GoF test statistic called as soft-Rank Energy (sRE) that is based on entropy regularized OT and employ it towards CPD. We discuss the advantages of using sRE over RE and demonstrate that the proposed sRE based CPD outperforms all the existing methods in terms of Area Under the Curve (AUC) and F1-score on real and synthetic data sets.

Related papers

• Provably accurate adaptive sampling for collocation points in physics-informed neural networks [11.912466054588327]
  Physics-informed Neural Networks (PINN) have emerged as an efficient way to learn surrogate solvers. We introduce a provably accurate sampling method for collocation points based on the Hessian of the PDE residuals.
  arXiv  Detail & Related papers  (2025-04-01T15:45:08Z)
• Policy Gradient with Active Importance Sampling [55.112959067035916]
  Policy gradient (PG) methods significantly benefit from IS, enabling the effective reuse of previously collected samples. However, IS is employed in RL as a passive tool for re-weighting historical samples. We look for the best behavioral policy from which to collect samples to reduce the policy gradient variance.
  arXiv  Detail & Related papers  (2024-05-09T09:08:09Z)
• Provably Efficient Algorithm for Nonstationary Low-Rank MDPs [48.92657638730582]
  We make the first effort to investigate nonstationary RL under episodic low-rank MDPs, where both transition kernels and rewards may vary over time. We propose a parameter-dependent policy optimization algorithm called PORTAL, and further improve PORTAL to its parameter-free version of Ada-PORTAL. For both algorithms, we provide upper bounds on the average dynamic suboptimality gap, which show that as long as the nonstationarity is not significantly large, PORTAL and Ada-PORTAL are sample-efficient and can achieve arbitrarily small average dynamic suboptimality gap with sample complexity.
  arXiv  Detail & Related papers  (2023-08-10T09:52:44Z)
• On Rank Energy Statistics via Optimal Transport: Continuity, Convergence, and Change Point Detection [13.159994710917024]
  We show that the soft rank energy enjoys both fast rates of statistical convergence and robust continuity properties. We quantify the discrepancy between soft rank energy and rank energy in terms of the regularization parameter.
  arXiv  Detail & Related papers  (2023-02-15T22:02:09Z)
• DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over Graphs [54.08445874064361]
  We propose to solve a regularized distributionally robust learning problem in the decentralized setting. By adding a Kullback-Liebler regularization function to the robust min-max optimization problem, the learning problem can be reduced to a modified robust problem. We show that our proposed algorithm can improve the worst distribution test accuracy by up to $10%$.
  arXiv  Detail & Related papers  (2022-08-29T18:01:42Z)
• Determinantal point processes based on orthogonal polynomials for sampling minibatches in SGD [0.0]
  gradient descent (SGD) is a cornerstone of machine learning. default minibatch construction involves uniformly sampling a subset of the desired size. We show how specific DPPs and a string of controlled approximations can lead to gradient estimators with a variance that decays faster with the batchsize than under uniform sampling.
  arXiv  Detail & Related papers  (2021-12-11T15:09:19Z)
• Learning generative models for valid knockoffs using novel multivariate-rank based statistics [12.528602250193206]
  Rank energy (RE) is derived using theoretical results characterizing the optimal maps in the Monge's Optimal Transport (OT) problem. We propose a variant of the RE, dubbed as soft rank energy (sRE), and its kernel variant called as soft rank maximum mean discrepancy (sRMMD) We then use sRMMD to generate deep knockoffs and show via extensive evaluation that it is a novel and effective method to produce valid knockoffs.
  arXiv  Detail & Related papers  (2021-10-29T18:51:19Z)
• Solving Multistage Stochastic Linear Programming via Regularized Linear Decision Rules: An Application to Hydrothermal Dispatch Planning [77.34726150561087]
  We propose a novel regularization scheme for linear decision rules (LDR) based on the AdaSO (adaptive least absolute shrinkage and selection operator) Experiments show that the overfit threat is non-negligible when using the classical non-regularized LDR to solve MSLP. For the LHDP problem, our analysis highlights the following benefits of the proposed framework in comparison to the non-regularized benchmark.
  arXiv  Detail & Related papers  (2021-10-07T02:36:14Z)
• Reparameterized Sampling for Generative Adversarial Networks [71.30132908130581]
  We propose REP-GAN, a novel sampling method that allows general dependent proposals by REizing the Markov chains into the latent space of the generator. Empirically, extensive experiments on synthetic and real datasets demonstrate that our REP-GAN largely improves the sample efficiency and obtains better sample quality simultaneously.
  arXiv  Detail & Related papers  (2021-07-01T10:34:55Z)
• 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)
• Stochastic-Sign SGD for Federated Learning with Theoretical Guarantees [49.91477656517431]
  Quantization-based solvers have been widely adopted in Federated Learning (FL) No existing methods enjoy all the aforementioned properties. We propose an intuitively-simple yet theoretically-simple method based on SIGNSGD to bridge the gap.
  arXiv  Detail & Related papers  (2020-02-25T15:12:15Z)

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.