# Online Heavy-tailed Change-point detection

arXiv: https://arxiv.org/abs/2306.09548 · HTML: https://mlsanity.com/paper/2306.09548/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 62 references that are in the map.
- First posted on arXiv 15 Jun 2023.

## Builds on (most cited first, 22 of 22)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [A Unifying Review of Deep and Shallow Anomaly Detection](https://mlsanity.com/paper/2009.11732/) (2020)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping](https://mlsanity.com/paper/2005.10785/) (2020)
- [Outlier Robust Mean Estimation with Subgaussian Rates via Stability](https://mlsanity.com/paper/2007.15618/) (2020)
- [Network Lasso: Clustering and Optimization in Large Graphs](https://mlsanity.com/paper/1507.00280/) (2015)
- [Robust subgaussian estimation of a mean vector in nearly linear time](https://mlsanity.com/paper/1906.03058/) (2019)
- [Streaming Algorithms for High-Dimensional Robust Statistics](https://mlsanity.com/paper/2204.12399/) (2022)
- [Catoni-style confidence sequences for heavy-tailed mean estimation](https://mlsanity.com/paper/2202.01250/) (2022)
- [Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond](https://mlsanity.com/paper/1912.11071/) (2019)
- [Multiscale Change-Point Inference](https://mlsanity.com/paper/1301.7212/) (2013)
- [Optimal Mean Estimation without a Variance](https://mlsanity.com/paper/2011.12433/) (2020)
- [Bregman Deviations of Generic Exponential Families](https://mlsanity.com/paper/2201.07306/) (2022)
- [Optimal nonparametric multivariate change point detection and localization](https://mlsanity.com/paper/1910.13289/) (2019)
- [Heavy-tailed Streaming Statistical Estimation](https://mlsanity.com/paper/2108.11483/) (2021)
- [Huber-Robust Confidence Sequences](https://mlsanity.com/paper/2301.09573/) (2023)
- [Change Point Detection in Correlation Networks](https://mlsanity.com/paper/1410.0761/) (2014)
- [Adversarially robust change point detection](https://mlsanity.com/paper/2105.10417/) (2021)
- [Change-point detection in panel data via double CUSUM statistic](https://mlsanity.com/paper/1611.08631/) (2016)
- [Offline Change Detection under Contamination](https://mlsanity.com/paper/2206.11214/) (2022)
- [Sequential change detection via backward confidence sequences](https://mlsanity.com/paper/2302.02544/) (2023)

## Abstract (arXiv)

We study algorithms for online change-point detection (OCPD), where samples that are potentially heavy-tailed, are presented one at a time and a change in the underlying mean must be detected as early as possible. We present an algorithm based on clipped Stochastic Gradient Descent (SGD), that works even if we only assume that the second moment of the data generating process is bounded. We derive guarantees on worst-case, finite-sample false-positive rate (FPR) over the family of all distributions with bounded second moment. Thus, our method is the first OCPD algorithm that guarantees finite-sample FPR, even if the data is high dimensional and the underlying distributions are heavy-tailed. The technical contribution of our paper is to show that clipped-SGD can estimate the mean of a random vector and simultaneously provide confidence bounds at all confidence values. We combine this robust estimate with a union bound argument and construct a sequential change-point algorithm with finite-sample FPR guarantees. We show empirically that our algorithm works well in a variety of situations, whether the underlying data are heavy-tailed, light-tailed, high dimensional or discrete. No other algorithm achieves bounded FPR theoretically or empirically, over all settings we study simultaneously.