High-Dimensional Nonparametric Change-Point Detection via Low-Rank Degree-Three Density Projection

Guoqing Zhang; Zhaixin Chen

cs.LGAug 16, 2026

High-Dimensional Nonparametric Change-Point Detection via Low-Rank Degree-Three Density Projection

Authors: Guoqing Zhang, Zhaixin Chen

Organizations: Operations Research Program North Carolina State University Raleigh, NC, USA · H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA, USA

Abstract

Distributional changes can be invisible to means and covariances yet appear in skewness, asymmetric interactions, or other third-order structure. We develop a nonparametric change-point method that retains every degree-at-most-three coefficient of a density while avoiding direct density estimation. For observations in $[-1,1]^d$ , we construct a symmetric order-three Legendre feature tensor $H_3(X)\in\Sym^3(\R^{d+1})$ such that $A(f)=\E_fH_3(X)$ is an exact isometric encoding of the degree-three density projection: $\|A(f)-A(g)\|_{\F}=\|P_3(f-g)\|_{L^2}$ . Instead, fixed tensor contractions are degree-three polynomial chaoses with $ψ_{2/3}$ tails. The two terms have the characteristic order-three tensor scaling and match the powers in sharp concentration results for simple random tensors. For a coordinate-orthogonal specialization, the bound improves to $\sqrt{\log d}$ and enables a prefix-sum implementation in hundreds of dimensions. We derive the exact population tent shape and localization margin, introduce a seeded shortest-interval algorithm with a padded local recentering step, and prove exact recovery by induction: null recursive segments remain inactive, every undetected change retains a balanced isolating interval, and the shortest active seed contains exactly one change before recentering. A two-way cross-fitted scalar refinement attains $O_{\Pp}(κ^{-2})$ localization in the small-jump regime, matching a Le Cam lower bound on a pure cubic family whose degree-two projection jump is exactly zero. Reproducible experiments at $d\in\{20,50,100,200\}$ and a three-change $d=100$ sequence demonstrate the intended high-dimensional regime without materializing a $(d+1)^3$ tensor.

Figures & tables

Polynomial term	Multiset	Permutations	Tensor entry
$1$	$\{0,0,0\}$	$1$	$1$
$a_{j}x_{j}$	$\{0,0,j\}$	$3$	$a_{j}/3$
$b_{j}p_{2}(x_{j})$	$\{0,j,j\}$	$3$	$b_{j}/\sqrt{15}$
$\gamma_{ij}x_{i}x_{j}$	$\{0,i,j\}$	$6$	$\gamma_{ij}/(3\sqrt{6})$
$c_{j}p_{3}(x_{j})$	$\{j,j,j\}$	$1$	$c_{j}/\sqrt{7}$
$\eta_{ij}p_{2}(x_{i})x_{j}$	$\{i,i,j\}$	$3$	$\eta_{ij}/(3\sqrt{5})$

Table 1: Entries of

A(f)

in terms of the conventional unnormalized polynomial coefficients. Every listed value is assigned to all distinct permutations of the indicated multiset.

$d$	$n$	LR-D3 pre.	LR-D3 ref.	all cubic	degree two	mean	runtime (s)
20	1200	34	32	48	462	324	0.009
50	3000	24	42	52	1222	753	0.021
100	6000	37	38	132	2496	2004	0.090
200	12000	34	30	52	5040	3417	0.339

Table 2: Median absolute localization error over

30

replications. Runtime is the mean wall-clock time for computing all listed methods on one replication.

Figure 1: Median single-change localization error. The structured degree-three methods and oracle remain stable as

d

grows, while procedures with zero population signal drift over an

O(n)

range. The unregularized all-cubic score pays for all

d

coordinates.

Figure 2: Population and diagonal-odeco degree-three CUSUM scores for a

d=100

pure cubic change at

400

Figure 3: Preliminary and refined estimates over

30

replications of the

d=100

three-change experiment. Dashed lines mark the true changes.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: At

d=100,n=800

, the unregularized implicit full-tensor score is dominated by tensor noise, while the diagonal-odeco score tracks the population tent. This behavior is consistent with the

d^{3/2}/\sqrt{n}

CUSUM term in Equation 24 .

$d$	$n$	Method	Median	Mean	$q_{0.9}$
20	1200	LR-D3 preliminary	34	88.33	268.4
20	1200	LR-D3 refined	32	81.33	288.6
20	1200	All cubic diagonal	48	119.87	303.6
20	1200	Full degree two	462	420.80	504.0
20	1200	Mean CUSUM	324	319.20	493.2
20	1200	Oracle cubic	30	70.27	251.6

Appendix

Table 3: Median, mean, and

90\%

quantile of absolute localization error over

30

replications.

Explore similar work

Aug 14, 2026cs.LG

High-dimensional nonparametric changepoint detection via low-rank degree-two density projection

Detecting distributional changes in high dimension is difficult when neither the pre-change nor post-change density is parametrically specified. We introduce a representation-based approach that retains all degree-at-most-two density information while replacing density estimation by matrix mean estimation. For observations in

[-1,1]^d

, a symmetric feature matrix

H_2(X)\in\R^{(d+1)\times(d+1)}

is constructed so that

M(f)=\E_f H_2(X)

is an isometric encoding of the degree-two orthogonal projection of the density. We scan matrix CUSUMs after rank-

r

truncation, exploiting the low rank of the projected jump rather than sparsity of individual coordinates. The resulting \LRD{} estimator has a tent-shaped population objective and a nonasymptotic operator-norm analysis whose leading stochastic term scales as

\sqrt{rd\log(nd)}

. For multiple changes, we give a seeded narrowest-over-threshold procedure and prove exact recovery by an induction that preserves an isolating interval for every undetected change. A cross-fitted scalar refinement learns the changing low-rank direction on one fold and localizes on the other, attaining

\widetilde O_{\Pp}(κ^{-2})

error; a matching Le Cam lower bound shows optimality up to logarithms. A geometrically

β

-mixing extension follows from a dependent matrix Bernstein inequality. Experiments with ambient dimension up to

200

, a three-change

d=100

sequence, and a

128

-feature human-activity benchmark show that the method remains computationally practical and accurately detects pure dependence changes that are invisible to mean CUSUMs.

Guoqing Zhang, Zhaixin Chen

Operations Research Program North Carolina State University Raleigh, NC, USA · H. Milton Stewart School of ISyE Georgia Institute of Technology Atlanta, GA, USA

Distribution Shift Detection Change-Point Detection

Ask PDF

Feb 14, 2026stat.ML

Locally Private Parametric Methods for Change-Point Detection

We study parametric change-point detection under local differential privacy, focusing on the offline localization of a single change point in a sequence of independent observations.~In the non-private setting, we derive improved finite-sample accuracy guarantees for a generalized likelihood-ratio estimator using martingale methods.~We establish finite-sample minimax lower bounds in both the non-private and locally private settings, showing that localization accuracy is fundamentally limited by the Chernoff information between the pre- and post-change distributions.~Guided by this, we design locally private CPD algorithms based on aggregated randomized response and binary mechanisms, which maximize the Chernoff information between the induced output distributions in low- and high-privacy regimes, respectively, and derive their finite-sample guarantees. Together, our upper and lower bounds quantify the statistical cost of privacy in change-point localization.~As part of our analysis, we also show that strong data processing inequality coefficients of Rényi divergence and Jeffreys--Rényi divergence of order infinity can be computed by restricting to pairs of input distributions with a common support of at most two symbols.~We corroborate our results through empirical evaluation on synthetic data.

Anuj Kumar Yadav, Cemre Cadir, Yanina Y. Shkel +1

School of Computer and Communication Sciences, École Polytechnique Fédérale de Lausanne (EPFL), Vaud, Switzerland.

Change-Point Detection Differential Privacy Minimax Estimation

Ask PDF

Sep 21, 2026cs.LG

High-Dimensional Online Change Point Detection with Adaptive Thresholding and Interpretability

Change point detection (CPD) identifies abrupt and significant changes in sequential data, with applications in human activity recognition, financial markets, cybersecurity, manufacturing, and autonomous systems. Traditional CPD methods often face computational challenges in high-dimensional settings and typically provide limited explanations for detected changes, which can restrict their practical usability. This paper introduces a CPD framework that improves scalability and interpretability by leveraging the Sliced Wasserstein (SW) distance. Our contributions are fourfold: (1) we transform multivariate sequential data into one-dimensional scores using the SW distance, making the resulting representation compatible with existing CPD methods; (2) we analyze the distributional behavior of random slices of the SW distance and show that, under suitable assumptions, they can be approximated by a Gamma distribution, providing a principled basis for threshold calibration; (3) we propose a self-adapting online CPD algorithm that combines this SW-based score with an adaptive quantile-based threshold; (4) we introduce a model-specific framework for generating contrastive explanations for annotated change points. Empirically, our method reduces false positives by at least

48\%

on average compared with popular online and offline CPD baselines, while maintaining competitive or superior detection performance. Code is available at https://github.com/jsve96/SWCPD_Code. At the same time, it produces interpretable change-point annotations, making it practical for deployment in high-stakes applications.

Sven Jacob, Bardh Prenkaj, Weijia Shao +1

Federal Institute for Occupational Safety and Health, Dresden · Technical University of Munich, Munich Center for Machine Learning · Sapienza University of Rome

Change-Point Detection Sliced Wasserstein Distance

Ask PDF