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

Annika H\"uselitz; Axel Munk; Housen Li

arxiv: 2503.05270 · v2 · submitted 2025-03-07 · 🧮 math.ST · stat.TH

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

Annika H\"uselitz , Housen Li , Axel Munk This is my paper

Pith reviewed 2026-05-23 01:21 UTC · model grok-4.3

classification 🧮 math.ST stat.TH

keywords change point detectionCUSUM statisticspiecewise linear regressiononline estimationminimax ratesjump detectionkink detection

0 comments

The pith

CUSUM-type statistics attain minimax optimal rates of log(n)/n for jumps and (log(n)/n)^{1/3} for kinks in online piecewise linear regression.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that certain CUSUM-type statistics achieve the minimax optimal localization rates for a single change point in a piecewise linear regression model observed sequentially under Gaussian noise. A phase transition appears between a jump discontinuity, localized at rate log(n)/n, and a kink (slope change), localized at the slower rate (log(n)/n)^{1/3}. An online algorithm built on these detectors identifies the change, distinguishes its type, and runs with constant computation and constant memory per new sample.

Core claim

In the Gaussian piecewise linear regression model with exactly one change point and sampling rate of order 1/n, certain CUSUM-type statistics attain the minimax optimal rates for localizing the change point: order log(n)/n for a jump and (log(n)/n)^{1/3} for a kink. The online algorithm based on these detectors optimally identifies both a jump and a kink, distinguishes between them, and operates with constant computational complexity and constant memory per incoming sample.

What carries the argument

CUSUM-type statistics for jump and kink detection that are adapted to the online segmented linear regression setting.

If this is right

The algorithm distinguishes jumps from kinks at the optimal rates.
Detection and localization remain statistically optimal while using only constant time and memory per new observation.
The method applies directly to streaming data arriving at rate 1/n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same detectors could be tested on data with multiple change points to see how far the single-change analysis extends before rates degrade.
The phase transition between jump and kink rates suggests analogous transitions may appear in higher-order polynomial segments.

Load-bearing premise

The observations follow a piecewise linear regression model with exactly one change point under i.i.d. Gaussian noise.

What would settle it

Empirical localization error for a kink that fails to scale as (log n / n)^{1/3} in large-n Gaussian simulations with a single slope change.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives minimax rates for online single-change detection in piecewise linear regression, with a phase transition between jump and kink, plus a constant-time constant-memory algorithm that detects and classifies both.

read the letter

The main point is that certain CUSUM-type statistics reach the minimax localization rates under the single-change piecewise-linear Gaussian model: log(n)/n for a jump and (log n / n)^{1/3} for a kink, and the authors pair this with an online algorithm that matches those rates while using O(1) time and memory per sample and correctly labels the type of change. That combination of explicit phase transition and practical efficiency is the concrete addition beyond standard CUSUM extensions. The rates line up with known offline results in this setting, and shipping an R package (FLOC) lets others check the implementation directly. The analysis stays scoped to exactly one change point, i.i.d. Gaussian noise, and design points at rate 1/n, so the claims do not overreach the stated model. The empirical checks on simulated and real data add a practical check, even if the abstract does not report specific error metrics. One soft spot is the single-change assumption itself; real streaming series often have multiple breaks, and the paper does not indicate how the procedure would degrade or be adapted. The constant-memory claim is attractive but rests on the full maintenance of the detectors, which would need the proofs to confirm no hidden factors appear. Minor implementation details like how the jump/kink distinction is thresholded in finite samples are also left for the full text. This work is aimed at researchers already working on sequential change-point methods or streaming nonparametric regression. A reader focused on linear trend monitoring or online detection would find the rates and the algorithm useful. The paper shows coherent engagement with the CUSUM and minimax literature without internal contradictions, so it deserves a serious referee even if revisions are needed on extensions or finite-sample behavior.

Referee Report

0 major / 3 minor

Summary. The paper considers sequential (online) estimation of a single change point in a piecewise linear regression model under i.i.d. Gaussian noise with design points at rate 1/n. It claims that certain CUSUM-type statistics attain the minimax optimal localization rates of order log(n)/n for a jump and (log(n)/n)^{1/3} for a kink, and introduces an online algorithm based on these detectors that identifies the change point, distinguishes jump from kink, and runs with constant time and memory per sample. The claims are supported by a minimax analysis and empirical evaluation on simulated and real data, with an R package implementation noted.

Significance. If the minimax rates and the online algorithm's correctness hold, the work is significant for bridging statistical optimality with computational efficiency in online change-point detection for regression models. The phase transition between jump and kink rates is a notable contribution, and the constant-complexity streaming procedure addresses a practical gap. The explicit scoping to the single-change-point Gaussian model and the availability of an implementation strengthen the paper's utility.

minor comments (3)

[Abstract] Abstract: the statement that the algorithm 'optimally identifies both a jump and a kink' should be qualified by the single-change-point assumption stated later in the model setup, to avoid implying robustness to multiple changes.
The abstract mentions evaluation on 'real-world data sets' but provides no details on the datasets or performance metrics; this should be expanded in the main text or a dedicated section for reproducibility.
Notation for the sampling rate 'of order 1/n' is used without an explicit definition of the design points X_i; a brief clarification in the model section would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, recognition of the phase transition between jump and kink rates, and the recommendation for minor revision. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's central claims rest on a minimax analysis deriving localization rates for jumps and kinks under an explicitly stated single-change-point piecewise-linear Gaussian model, followed by construction of an online detector that attains those rates. No step reduces a claimed prediction or optimality result to a fitted quantity defined from the same data, nor does any load-bearing premise collapse to a self-citation whose content is unverified within the paper. The derivation chain is self-contained against the model assumptions and does not invoke uniqueness theorems or ansatzes imported from the authors' prior work in a circular manner.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard single-change-point piecewise-linear Gaussian model with fixed sampling rate 1/n; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract beyond this modeling framework.

axioms (2)

domain assumption Data generated from piecewise linear regression with exactly one change point and i.i.d. Gaussian noise
Stated in the abstract as the setup for the minimax analysis and algorithm.
domain assumption Sampling rate of order 1/n
Used to express the localization rates in terms of n.

pith-pipeline@v0.9.0 · 5718 in / 1479 out tokens · 29465 ms · 2026-05-23T01:21:15.181836+00:00 · methodology

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

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)