Online jump and kink detection in segmented linear regression: Statistical optimality meets computational efficiency
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911653443928064 |
|---|---|
| author | Hüselitz, Annika Li, Housen Munk, Axel |
| author_facet | Hüselitz, Annika Li, Housen Munk, Axel |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_05270 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Online jump and kink detection in segmented linear regression: Statistical optimality meets computational efficiency Hüselitz, Annika Li, Housen Munk, Axel Statistics Theory 62L12, 62C20, 62J20 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. |
| title | Online jump and kink detection in segmented linear regression: Statistical optimality meets computational efficiency |
| topic | Statistics Theory 62L12, 62C20, 62J20 |
| url | https://arxiv.org/abs/2503.05270 |