Narrowest-Over-Threshold Detection of Multiple Change-points and Change-point-like Features

• NOT detects unknown numbers and locations of features in signals, including jumps, kinks, discontinuities, and changes in noise variance, extending canonical change-point detection to generalised settings.The method treats feature detection and change-point detection interchangeably when changes occur in a parametric description of the signal or distributional aspects of the noise.Source: §1 · p. 2
• NOT randomly samples intervals, retains those whose single-feature contrasts exceed a threshold, and recursively selects the narrowest retained interval before searching to either side.The narrowest-interval focus makes selected intervals likely to contain at most one feature, enabling the same framework to work across multiple scenarios with minor modifications.Source: §1 · p. 3
• NOT combines low complexity, near-optimal feature-location rates, and interpretable parametric signal estimation between neighbouring detected features.With M subsamples, the procedure has complexity O(MT), typically with M = O(log T) for finitely many change-points, and its full threshold-indexed solution path is typically computed in close-to-linear time.Source: §1 · p. 3
• The framework is modular: users can design specialised contrast functions or select contrasts adaptively from a dictionary for mixed-type feature detection.These extensions are not developed in the paper, but the authors identify user-tailored feature detectors as an important benefit of the methodology.Source: §1 · p. 3
• By localising feature searches, NOT avoids the misleading single-feature fits that cause Binary Segmentation and Wild Binary Segmentation to fail for many generalised change-point problems.For piecewise-linear signals with two true derivative changes, a single global triangular fit can place its change-point between them, whereas NOT can isolate each feature in suitably narrow intervals.Source: §1 · pp. 3–4
• NOT is presented as fast, accurate, easy to code, and easy to extend, with an implementation available in the R package not.The paper also proposes automatic threshold selection via the strengthened Schwarz Information Criterion and develops theoretical consistency and convergence results.Source: §1 · p. 5

2.1 Setup

• The setup permits an unknown, potentially growing number of change-points separating segments whose signal and noise follow a common d-dimensional parametric family, including polynomial segments.Identifiability requires consecutive change-points to be at least d apart; listed cases include piecewise-constant means, continuous or discontinuous piecewise-linear means, and piecewise-constant variance.Source: §2.1 · pp. 5–6
• The framework extends beyond the listed univariate cases to higher-order polynomial signals, multivariate observations, autocovariance changes, and dependent or non-Gaussian noise.For unknown constant variance in Scenarios (S1)–(S3), a differenced-data MAD estimator is robust to signal change-points.Source: §2.1 · pp. 5–6

2.2 Main idea

• NOT randomly samples intervals, computes the maximum single-change-point GLR within each, and recursively splits at the narrowest interval whose statistic exceeds threshold ζT.This localization avoids relying on a fixed interval design and supports reuse of previously drawn intervals during recursion.Source: §2.2 · pp. 6–7

2.3 Log-likelihood ratios and contrast functions

• Under Gaussian noise, contrast functions replace GLRs with inner-product statistics, recovering CUSUM for piecewise-constant means and generalizing it to other change-point scenarios.For continuous piecewise-linear means, orthonormal contrasts are invariant to mean and slope shifts, improving numerical efficiency and stability.Source: §2.3 · pp. 7–8, §2.3.1 · p. 8, §2.3.2 · p. 9

2.4 The NOT algorithm

• The generic NOT algorithm lets users choose a scenario-specific contrast and tunes the threshold ζT and interval count M before recursive detection.Generating all random intervals upfront helps control computational complexity and avoids discarding intervals after detections.Source: §2.4 · pp. 10–11

2.5 Theoretical properties of NOT

• Under Scenario (S1), NOT consistently detects all change-points with M = O(log T) random intervals and total computational cost O(T log T).The theory is developed under infill asymptotics and also provides localization guarantees for the estimated change-points.Source: §2.5 · pp. 11–12
• The detection difficulty in Scenario (S2) is characterized by δ_T^3/2 in the general increasing-change-point setting, while the corresponding key quantity in Scenario (S1) permits the minimax-threshold rate √log T.Chan and Walther (2013) identify √log T as the smallest rate permitting minimax change-point detection; NOT's rate loses only a logarithmic factor relative to O_p(1).Source: §2.5 · p. 12
• For finitely many change-points with δ_T ∼ T, NOT consistently estimates all change-points using M = O(log T) random intervals at total cost O(T log T).Source: §2.5 · p. 12
• In Scenario (S2), NOT achieves O_p(T^2/3(log T)^1/3), improving to O_p(T^1/2(log T)^1/2) under additional assumptions and a more restrictive ζ_T choice.The baseline rate differs from Raimondo (1998)'s O_p(T^2/3) by only a logarithmic factor.Source: §2.5 · p. 12
• Unlike NOT, WBS fails to estimate change-points consistently in Scenario (S2).Source: §2.5 · p. 12

3.1 Motivation

• NOT’s threshold choice is reframed as model selection because each threshold yields a candidate model, motivating information-criterion selection along the solution path.The theoretically suitable threshold can depend on unobserved quantities or be difficult to derive in general settings.Source: §3.1 · pp. 12–13

3.2 The NOT solution path algorithm

• Algorithm 2 computes the entire threshold-indexed solution path efficiently by iteratively reusing information from neighboring candidate solutions.The path changes only at discrete threshold values, so naive threshold grids may miss solutions and repeated Algorithm 1 applications are inefficient.Source: §3.2 · p. 13

3.3 Choice of ζT via the strengthened Schwarz Information Criterion (sSIC)

• The selected model minimizes the strengthened Schwarz Information Criterion (sSIC), computed from maximum-likelihood segment parameters and the total number of estimated parameters.The tuning parameter α satisfies α ≥ 1; α = 1 recovers the Schwarz Information Criterion, while other criteria could also be used after constructing the path.Source: §3.3 · pp. 13–14

3.4 Theoretical properties of NOT with the sSIC

• Theoretical results justify NOT with sSIC for Scenarios (S1) and (S2) when the number of change-points is fixed and their spacings are large, eliminating the need to supply a threshold.The corresponding guarantees use α > 1 and the scenario-specific contrast functions in Theorems 3 and 4.Source: §3.4 · p. 14

3.5 Computational complexity

• O(MT) is the typical computational complexity of both Algorithms 1 and 2, while Algorithm 2 also requires O(MT) memory.The interval computations are independent and can be parallelized; Figure 3 provides practical evidence of linear scaling in T and M.Source: §3.5 · p. 15, Figure 3 · p. 15

3.6.1 Choice of M

• For datasets with thousands of observations, the authors recommend M = 10000, while signals expected to contain many change-points may require larger M.With M = 10000, Algorithm 1 averaged no more than 2 seconds across the Section 5 examples using one CPU core.Source: §3.6.1 · pp. 15–16

3.6.2 Early stopping for NOT with the sSIC

• When the expected number of change-points is moderate, computing sSIC only for solutions with at most qmax = 25 estimated change-points provides computational gains without adversely impacting performance.Solutions at very small thresholds contain many estimated change-points and are unlikely to minimize sSIC.Source: §3.6.2 · p. 16

4.1 NOT with dependent noise

• Under stationary short-memory Gaussian noise, NOT retains the conclusions of Theorems 1 and 2 in Scenarios (S1) and (S2), with different constants.The dependence condition includes processes whose autocorrelations are absolutely summable, and the class includes ARMA models.Source: §4.1 · p. 16
• For dependent-noise signals, NOT’s smallest permitted threshold depends linearly on σ0(P∞k=−∞|ρk|)1/2, while application requires estimating residuals εt, σ0, and this dependence-scale quantity.A wavelet-based method is reported to estimate residuals, with the Haar transform appropriate in Scenario (S1) and transforms annihilating linear functions appropriate in Scenarios (S2) and (S3).Source: §4.1 · pp. 16–17

4.2 Extension of NOT to heavy-tailed noise

• NOT is relatively robust to noise misspecification, giving reasonable estimates under non-Gaussian noise even when Gaussian contrast functions are used.Performance of the heavy-tail extension combined with Algorithm 2 and sSIC is illustrated in Section 5.Source: §4.2 · p. 17
• For heavy-tailed noise, NOT can use a contrast that assigns interval residuals to ±1 labels, producing a light-tailed two-point distribution before applying the contrast.The construction uses residuals from fitting a no-change-point curve, with sample medians potentially preferable for some noise distributions.Source: §4.2 · p. 17

5.1 Settings

• Simulations cover seven signal models, including piecewise-quadratic signals, under Gaussian, Laplace, Student-t5, and correlated Gaussian AR(1) noise.The study uses i.i.d. N(0,1), i.i.d. N(0,2), scaled Laplace, scaled Student-t5, and stationary Gaussian AR(1) noise with ϕ = 0.3.Source: §5.1 · pp. 17–18

5.2 Estimators

• NOT uses scenario-specific contrasts with sSIC, while comparisons include numerous CRAN change-point methods and trend filtering; B&P and TF require substantial computational resources.The simulation uses M = 10000 intervals and qmax = 25; B&P is the slowest method considered.Source: §5.2 · pp. 18–19

5.3 Results

• NOT is among the most competitive methods for estimating change-point numbers, locations, and signals, while remaining fast and relatively robust to correlated or heavy-tailed noise.Its speed is particularly advantageous in Scenarios (S2), (S3), and (S5).Source: Table 1 · p. 20, Table 2 · p. 21, §5.3 · p. 22

5.4 More on model misspecification and model selection

• Under signal misspecification, NOT0 overestimates change-points, NOT2 may recover their number at high signal-to-noise ratios but can underfit at lower ratios, and NOT1 often has lower MSE and location error.Despite misspecification, NOT estimates can remain close to the true signal, and sSIC empirically selects the correct polynomial order especially at high signal-to-noise ratios.Source: §5.4 · pp. 22–23

6.1 Temperature anomalies

• For temperature anomalies, NOT models gradual changes using a piecewise-linear trend with slope change-points, applying contrast (2.6) and SIC to select the model.The data span monthly anomalies from January 1880 to June 2016, defined relative to the 1951–1980 seasonal baseline.Source: §6.1 · pp. 23–24
• For GISS temperature anomalies, NOT identifies 8 change-points, including dates near previously reported changes around 1910, 1945, and 1976.The analysis also finds local deviations during 1901–1915 and 1935–1946, a long upward trend from December 1946, and an increasing slope after May 2015.Source: §6.1 · p. 24

6.2 UK House Price Index

• For monthly HPI percentage changes in Hackney, Newham, and Tower Hamlets, all in East London, NOT uses contrast (2.8), M = 10000 intervals, and an SIC-minimising threshold.NOT estimates two change-points for all three boroughs, around March 2008 and September 2009; estimated standard deviations are much larger during that period.Source: §6.2 · pp. 25–26
• NOT detects only a few UK house-price change-points, including common changes around March 2008 and September 2009, whereas TGUH estimates at least 10 per series.The larger estimated standard deviations during 2008–2009 suggest heightened market volatility and support Scenario (S4) over Scenario (S1).Source: §6.2 · pp. 25–26

Online supplementary materials for ‘Narrowest-Over-Threshold Detection of Multiple Changepoints and Change-point-like Features’

• The supplement organizes additional material into computational details and the NOT solution path, simulation models, further simulations, and an oil-price data example.Source: Online supplementary materials for… · p. 27

A Simulation models

• The simulations cover piecewise-constant, piecewise-linear, mixed, variance-changing, piecewise-quadratic, and misspecified signals across scenarios S1–S5.Models include teeth, blocks, wave1, wave2, mix, vol, quad, and smile configurations with specified change-points and noise levels.Source: A Simulation models · p. 27
• Additional models test mixed jump-and-slope changes, simultaneous mean and variance changes, quadratic signals, and NOT under misspecification.These include the mix, vol, quad, and smile signals with their specified change-point structures.Source: A Simulation models · pp. 27–28

B.1 Computing contrast functions in a linear time

• For every scenario, all contrast values over a fixed interval can be computed in time linear in the number of observations by recursively updating the required inner products.The resulting collection {C_b: b=s,…,e−1} costs O(e−s+1).Source: §B.1 · p. 28

B.2 Details of the NOT solution path algorithm

• Algorithm 2 computes the entire threshold-indexed NOT solution path by representing each fixed-threshold solution as a recursively constructed binary tree.Each node stores the detected location, interval, maximum contrast, and left and right child nodes for subsequent detections.Source: §B.2 · p. 29
• When the threshold increases, the existing tree is reused: only branches containing nodes whose contrasts fall below the new threshold are reconstructed, rather than rebuilding from scratch.Source: §B.2 · p. 29
• The solution path has worst-case complexity O(MK_N), but consecutive trees usually differ little, making the practical complexity approximately O(MT).For one threshold, binary-tree construction costs at most O(MK_ζT), where K_ζT is the tree height.Source: §B.2 · p. 29

• For any ζ_T ∈ (0.08, 0.83), Algorithm 1 selects an interval containing exactly one change-point, yielding a contrast maximum close to a true change-point.It selects either [225, 450] or [500, 750], despite the longest interval’s maximum occurring far from both true change-points.Source: §B.3 · p. 31
• When an interval contains two change-points, its large contrast maximum can lie far from both, whereas intervals containing one change-point peak near the change-point.Figure 8 contrasts these misleading multi-change-point maxima with the narrowest-over-threshold estimate.Source: §B.3 · p. 31, Figure 8 · p. 31
• Algorithm 2 builds a binary tree by selecting the maximum-contrast root, restricting branches to specified subintervals, and updating the threshold to ensure subsequent tree updates.In the example, the smallest-contrast node sets the threshold to ζ(2) T = 0.03; that node is removed, and a replacement node is inserted.Source: §B.3 · p. 31
• The fourth solution along Algorithm 2’s path contains exactly two nodes close to the true change-points before the tree ultimately shrinks to NULL.Figure 9 displays the first four segmentation trees and their contrast-based node updates.Source: §B.3 · pp. 31–32, Figure 9 · p. 32

Additional simulation results

• Tables 5–7 summarise additional simulation results for three different noise distributions.These results complement those presented in Section 5.Source: C Additional simulation results · p. 32

Noise distributions

• The considered noise settings include i.i.d. Laplace(0, 2^-1/2) errors and zero-mean unit-variance Gaussian AR(1) errors with ϕ = 0.3.Source: C Additional simulation results · p. 32

Data and methodology

• NOT analyzes OPEC daily log-returns from 2003–2016 using a contrast designed to detect changes in both mean and volatility, compared with NMCD.The analysis uses Algorithm 2 with M = 10000 and qmax = 25; NMCD is implemented with the same maximum number of change-points.Source: D Additional real data example: OPEC… · pp. 32, 36

Change-point results

• Both NOT and NMCD detect 7 change-points, with nearby locations for 6 of 7 features detected by NOT.NMCD misses a change-point near 29 April 2003, whereas it identifies two change-points in early 2016 and NOT identifies one; exact detections are listed in Table 8.Source: D Additional real data example: OPEC… · p. 36, Table 8 · p. 36

Diagnostic assessment

• Little autocorrelation in squared residuals suggests that the mean-and-volatility change-point scenario fits the oil-price data reasonably well.The diagnostic uses residuals standardized within each detected segment.Source: D Additional real data example: OPEC… · p. 36

E.1.1 The piecewise-constant case

• The piecewise-constant proofs characterize the contrast around an interval containing one change-point, using the minimum distance to the interval boundaries and the jump size.The contrast increases toward the change-point from either side, and Lemmas 2–4 provide corresponding lower and displacement bounds.Source: §E.1.1 · pp. 37–38
• For piecewise-constant signals, the contrast is maximized at the true change-point because it increases before the change-point and decreases afterward.This monotonicity is used to establish the lower bound based on the left and right distances from the change-point to the interval endpoints.Source: §E.1.1 · p. 37
• The piecewise-constant analysis also treats intervals spanning neighboring changes, providing lemmas for contrasts and candidate locations when more than one change-point may lie in the wider interval.The supporting lemmas specify intervals whose subranges contain successive change-points and compare the contrast at the true location with displaced candidates.Source: §E.1.1 · p. 38

E.1.2 The piecewise-linear continuous case

• In the continuous piecewise-linear case, the contrast is maximized at the kink because the signal restricted to the interval cannot lie in the candidate-kink basis span when b ≠ τj.The proof projects the signal onto the piecewise-linear, slope, and constant bases and decomposes the squared contrast accordingly.Source: §E.1.2 · p. 39
• For piecewise-linear signals, the proofs derive lower and upper bounds for the contrast using the interval length, distances to the kink, and the slope-change magnitude.The bounds use ηL, ηR, and l = ηL + ηR + 1, together with repeated applications of Lemma 1 and an inequality controlling the resulting products.Source: §E.1.2 · pp. 39–40
• Lemma 7 quantifies how the piecewise-linear contrast decreases when the candidate kink is displaced from the true kink, with separate treatments on either side by symmetry.The proof exploits symmetry in the distances ηL and ρ and bounds the relevant product using the interval geometry.Source: §E.1.2 · pp. 39–41
• Lemma 8 gives a local lower bound for candidates within half the shorter side-distance of the true kink, in terms of the slope-change magnitude.The constants are explicitly noted as non-sharp because the lemma is used only to establish rate-type results.Source: §E.1.2 · pp. 39, 41, 42

E.2 Proof of Theorem 1

• The proof reduces noisy change-point estimation to noiseless lemmas by controlling contrast deviations uniformly over all candidate intervals and split points.Bonferroni control in Step One supplies the required uniform bound.Source: §E.2 · p. 42

Step Two.

• Step Two controls the normalized difference between competing noisy contrasts and their noiseless counterparts, yielding the basis for location-rate analysis.For fixed endpoints, candidate selection depends only on the difference between the two contrasts.Source: §E.2 · p. 42, Step Two · p. 43

Step Three.

• With sufficiently large M, the random interval set contains a well-separated interval around every change-point, while narrowest-over-threshold selection prevents multiple change-points from entering the selected interval.The construction requires sufficiently large T so the relevant intervals contain integer endpoints.Source: §E.2 · p. 42, Step Three · p. 44, Step Four · p. 45

Step Five.

• After all change-points are detected, every remaining candidate interval either contains none or has change-points too close to its boundaries to exceed the threshold.Consequently, the NOT algorithm terminates and detects no additional change-points.Source: §E.2 · p. 43, Step Five · p. 46

Step One.

• The Bonferroni threshold λ_T = √(8 log T) is sufficient for consistency and rate results, although its constant is not sharp.The proof points to D¨umbgen and Spokoiny (2001) and Rufibach and Walther (2010) for possible improvements.Source: Step One · p. 43

Step Three.

• For each selected interval containing one change-point, the estimated location satisfies |b* − τ_j|(Δf_j)^2 ≤ C_3 log T.This follows by excluding candidate locations farther than the stated rate from τ_j.Source: Step Four · pp. 45–46, Step Five · p. 46

Step Five.

• The algorithm detects each change-point without duplicating detections before all q change-points are found, using the localization bound and interval separation.The proof tracks the remaining segments after each detected point and shows the detection condition persists where needed.Source: Step Five · p. 46

E.3 Proof of Theorem 2

• Theorem 2 is proved by adapting the five-step structure used for Theorem 1, with the established result implying (2.10).The proof is explicitly organized in analogy with Theorem 1.Source: §E.3 · p. 46

Step One and Step Two

• The first two steps define the relevant events and bound their complement probabilities using arguments from Theorem 1.The supplied proof fragment introduces two events and invokes the corresponding earlier arguments.Source: Step One and Step Two · p. 47

Step Three

• Step Three assumes AT, BT, and DM T and establishes the needed probability bound, while leaving constants unrefined because the proof targets the rate.The constants are stated but could be further refined; the proof prioritizes establishing the rate.Source: Step Three · p. 47

Step Four

• Step Four shows that the selected interval contains exactly one changepoint and localizes its estimator to |b*−τj| ≤ C3(∆f_j)^−2/3(log T)^1/3.The argument establishes the localization bound by ruling out candidate locations farther than the target error ǫT.Source: Step Four · p. 48

Step Five

• Step Five applies the preceding event-based arguments recursively, ensuring each segment containing a changepoint satisfies the detection condition.The initial interval satisfies (E.9), and the construction continues across segments containing remaining changepoints.Source: Step Five · p. 48
• Each detected changepoint is not detected twice before all q changepoints are found, as guaranteed by Lemma 5 and event AT.The proof excludes intervals near an already detected changepoint from producing a duplicate detection.Source: Step Five · p. 48
• After all changepoints are detected, the proof restricts attention to remaining eligible intervals and concludes that the algorithm terminates without further detections.The termination conclusion follows after invoking Lemma 6 within AT.Source: Step Five · p. 49

E.4 Proof of Theorem 3

• The sSIC proof is divided into three parts: a candidate-model argument, change-point-number consistency, and location-error control.The criterion uses the estimated noise variance and estimated number of change-points for each candidate on the NOT solution path.Source: §E.4 · p. 49

Part I. About a particular model candidate on the NOT solution path

• With arbitrarily high probability, the NOT solution path contains a candidate estimating q change-points within C′ log T of their true locations.The proof conditions on the event that this good candidate exists and uses it throughout the analysis.Source: Part I. About a particular model… · pp. 49, 54

Part II. Estimation of the number of change-points

• For NOT with the sSIC, the proof establishes that the probability of selecting fewer than q change-points satisfies P (ˆq < q) →0 as T →∞.Source: Part II. Estimation of the number of… · p. 50
• Consequently, NOT with sSIC consistently estimates the number of change-points, with P(ˆq = q) → 1 as T →∞.The result combines the vanishing probabilities of underestimation and overestimation.Source: Part II. Estimation of the number of… · pp. 50–51
• The proof also shows that sSIC does not select too many change-points: P(ˆq > q) → 0 as T →∞.For overfitted candidates, the argument constructs a saturated oracle containing both estimated and true change-points and controls the resulting variance and criterion terms.Source: Part II. Estimation of the number of… · pp. 50–51

Part III. Estimation of the change-point locations

• After establishing ˆq = q, the location proof compares the selected model with a near-saturated oracle replacing a true change-point by locations C log T away on either side.The construction exploits local constancy around the change-point and its nonzero jump size.Source: Part III. Estimation of the… · p. 51
• The selected change-point locations satisfy max_j=1,...,q |ˆτ_j − τ_j| ≤ C log T with probability tending to one.Thus, after sSIC selects the correct number, all estimated locations achieve the required logarithmic localization rate.Source: Part III. Estimation of the… · p. 52

E.5 Proof of Theorem 4

• Theorem 4’s proof strengthens the kink-detection and location-convergence arguments under finitely many kinks separated by O(T).It verifies Theorem 2’s conditions and modifies Step Four to obtain the sharper location rate |b*−τ_j| ≤ ε_T for sufficiently large T.Source: §E.5 · pp. 52–54

Part I. About a particular model candidate on the NOT solution path

• A good candidate on the NOT solution path has the correct number of kinks and uniformly controlled location error with arbitrarily high probability.The proof constructs a piecewise-linear comparison signal and bounds its approximation error before controlling the estimated noise variance.Source: Part I. About a particular model… · pp. 49, 54

Part II. Estimation of the number of change-points

• The sSIC estimator consistently selects the true number of change-points by showing that both underfitting and overfitting probabilities vanish.The two cases are handled separately: omitted kinks incur a residual-fit penalty, whereas extra kinks are outweighed by the sSIC complexity penalty.Source: Part II. Estimation of the number of… · pp. 50, 55, 56

Part III. Estimation of the change-point locations

• After correct model-size selection, each estimated change-point lies within a δ_T/6 neighborhood of its true location and is locally unique.The argument compares the selected candidate with near-saturated oracle models and derives a contradiction if a true kink is poorly localized.Source: Part III. Estimation of the… · p. 56

E.6 Proof of Corollary 1

• For Corollary 1, the proof assumes unit noise variance and incorporates serial dependence through the finite autocorrelation sum P.The dependent-error argument modifies the proof of Theorem 1 rather than changing its overall structure.Source: §E.6 · p. 57

Step One and Two

• The autocorrelation matrix has largest eigenvalue bounded above by P, uniformly in T, providing the variance control needed for the dependent-noise bounds.This bound follows from symmetry, operator-norm inequalities, and the absolute summability of the autocorrelation function.Source: Step One and Two · p. 57

Step Three, Four and Five

• The remaining proof steps proceed by changing constants, and the proof of Corollary 2 is stated to be analogous to Corollary 1.The latter proof is omitted for brevity.Source: Step Three, Four and Five · p. 58