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

Summary

This TMLR paper introduces SWCPD, an online change point detection framework for high-dimensional streams built on the Sliced Wasserstein (SW) distance. Sliding windows are compressed into a one-dimensional score through Monte Carlo random projections, replacing cubic Wasserstein or quadratic MMD computations with roughly O(N(wdL + Lw log w)) cost. The authors analyze random slices of the SW statistic and prove (Theorem 3.1) that suitably scaled slices converge to a generalized chi-square law under Gaussian-projection assumptions; an empirically motivated Gamma approximation with method-of-moments estimates then supplies an adaptive (1−q)-quantile threshold for a CUSUM-style cumulative sum. A hierarchical procedure (Algorithms 2-3) attributes detected changes to feature dimensions via high-loss projection directions, validated by iterative feature removal. On synthetic mean-shift data, SWD attributions align better with ground truth (cosine 0.96-0.998) than Integrated Gradients, GradientSHAP, and DeepLIFT once three or more components drift (Table 1). Across MNIST, HAR, HASC, and Occupancy streams, against offline (e-divisive, KCP, ClaSP, OT-CPD) and online (BOCPD, RuLSIF variants, RIO) baselines, SWCPD attains the lowest false positives almost everywhere (e.g., HASC FP 0.09 versus 0.78-14) with competitive AUC and the best HASC detection delay (39), though Covering on HAR (0.56) trails KCP (0.82). Key limitations: the Gamma calibration lacks finite-sample type-I error guarantees; overlapping windows violate the i.i.d. slice assumption; and the headline 'at least 48% average false-positive reduction' is not derived transparently. Code is released.