Online jump and kink detection in segmented linear regression: Statistical optimality meets computational efficiency

Abstract

We consider the problem of sequential (online) estimation of a single change point in a piecewise linear regression model under a Gaussian setup. We demonstrate that certain CUSUM-type statistics attain the minimax optimal rates for localizing the change point. Our minimax analysis unveils an interesting phase transition from a jump (discontinuity in function values) to a kink (a change in slope). Specifically, for a jump, the minimax rate is of order $\log (n)/n$ , whereas for a kink it scales as $(\log (n)/n{)}^{1/3}$, given that the sampling rate is of order $1/n$. We further introduce an online algorithm based on these detectors, which optimally identifies both a jump and a kink, and is able to distinguish between them. Notably, the algorithm operates with constant computational complexity and requires only constant memory per incoming sample. Finally, we evaluate the empirical performance of our method on both simulated and real-world data sets. An implementation is available in the R package FLOC on GitHub.

The title has been changed. The implementation in R is available at https://github.com/AnnikaHueselitz/FLOC

References in corpus (7)

• Selective review of offline change point detection methods
• Efficient Computer Network Anomaly Detection by Changepoint Detection Methods
• The Lasso for High-Dimensional Regression with a Possible Change-Point
• On optimality of the Shiryaev-Roberts procedure for detecting a change in distribution
• Seeded Binary Segmentation: A general methodology for fast and optimal change point detection
• Optimal change-point estimation from indirect observations
• A Log-Linear Non-Parametric Online Changepoint Detection Algorithm based on Functional Pruning