PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Guoqing Zhang, Zhaixin Chen

arXiv:2608.15466v1cs.LG

TL;DR

Third-order distributional changes can evade mean- and covariance-based detection, motivating a nonparametric degree-three approach. The paper encodes degree-three density projections as symmetric tensors, proves exact multiple-change recovery and O(κ^-2) refinement for small jumps, and demonstrates scalable performance through d = 200.

  • Problem

    High-dimensional distributions may change in skewness or asymmetric third-order interactions while means and covariances remain fixed, limiting mean- and covariance-based change detection.

  • Method

    The method represents degree-three density projections as symmetric tensors, controls tensor deviations through polynomial-chaos concentration, and localizes changes with seeded shortest intervals and cross-fitted refinement.

  • Results

    O(κ^-2) localization for small jumps matches a Le Cam lower bound, while the seeded estimator proves exact recovery of multiple changes under an explicit signal-to-noise condition.

  • Takeaways & Limitations

    Pure cubic changes can have zero degree-at-most-two projection signal, establishing the scientific need for degree-three structure in this setting.

  • Takeaways & Limitations

    The method is projection-limited, assumes independent observations in its main theorems, and faces computationally hard generic tensor optimization.

Abstract

from arXiv · show

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.

1 Introduction

The paper detects distributional changes invisible to means and covariances by encoding the degree-at-most-three density projection as a symmetric tensor mean. It combines tensor-specific concentration, seeded localization, cross-fitted refinement, and scalable implementations with reproducible high-dimensional evidence.

  • Motivation: Third-order changes can occur in marginal skewness, asymmetric coordinate interactions, or latent factors while means and covariances remain fixed.Mean and covariance CUSUMs have zero population signal for these alternatives.
  • Tensor representation: Degree-at-most-three Legendre coefficients have a canonical symmetric order-three tensor representation whose Frobenius geometry exactly matches projected-density L2 geometry.Each segment tensor is an expectation of a single-observation feature map, turning distributional change detection into structured tensor-mean change detection.
  • Concentration: Tensor-specific deviation bounds use degree-three chaos hypercontractivity, sub-Weibull Bernstein–Orlicz summation, and sphere nets without matrix flattening or matrix Bernstein.The resulting rate has the same two-regime scaling as sharp concentration for simple order-three random tensors.
  • Scalability and evidence: O(nd) prefix sums reduce stochastic complexity from d to log d for coordinate-odeco changes, and experiments remain stable through d = 200.The full tensor is never formed; all three changes are detected in every d = 100 multiple-change replicate across 30 replicates.
  • Localization: The seeded shortest-interval estimator with padded local recentering recovers multiple change locations under an explicit signal-to-noise condition.Its induction proof controls boundary contamination, preserves balanced isolating intervals, and prevents selected shortest seeds from containing two changes.
  • Refinement and lower bound: κ^-2 localization is achieved for small jumps by two-way cross-fitting, while a pure cubic rank-one family supplies a matching lower bound and zero degree-at-most-two signal.The lower-bound family has exactly zero jump in every degree-at-most-two projection coefficient.

2 Degree-three density projection as a symmetric tensor

The paper encodes the degree-at-most-three Legendre density projection as a symmetric order-three feature tensor with exact signal preservation. Tensor contractions avoid materializing the Θ(d^3)-storage representation, reducing access to linear cost in d.

  • Legendre projection: The functions {ψα : |α| ≤3} form an orthonormal basis for the total-degree-at-most-three polynomial subspace, yielding the density projection through its coefficients.For any density f, the constant coefficient satisfies θ0(f) = 1.
  • Symmetric tensor construction: The symmetric tensor basis assigns each degree-three coefficient across all distinct index permutations, with normalization by the square root of their count.The resulting family {Eα : |α| ≤3} is an orthonormal basis of Sym^3(R^(d+1)).
  • Isometric tensorization: The isometric tensorization gives ||A(f) − A(g)||_F = ||P3(f − g)||_L2, so tensor and projected-density jumps have exactly the same signal size.Densities with equal degree-three projections are indistinguishable to methods based only on H3.
  • Implicit computation: Θ(d^3) memory is unnecessary because tensor contractions and mixed gradients can be evaluated in O(d) operations.A rank-r frame objective over n samples therefore costs O(ndr) per iteration rather than O(nd^3) storage.

3 Tensor CUSUMs and low-rank scores

The method detects changes in degree-three density projections through tensor CUSUMs scored by a stable low-rank variational criterion. Under bounded densities and orthogonally decomposable projected jumps, the population signal peaks uniquely at the change point with an exact linear localization margin.

  • Model and assumptions: Projected jumps are D_k = A_k − A_{k−1}, with minimum magnitude κ = min_k ||D_k||_F and minimum spacing Δ = min_k(η_k − η_{k−1}).The observations are independent and piecewise distributed according to densities f_k between ordered change points η_k.
  • Model and assumptions: Each nonzero projected jump has an orthogonal decomposition with rank at most r, while bounded densities transfer degree-three polynomial moments to the segment laws.Approximate orthogonal decompositions are handled by adding the residual Frobenius norm to the deterministic error.
  • Low-rank scores: The symmetric orthogonal-decomposition score preserves the Frobenius norm of every odeco jump of rank at most r and remains stable under arbitrary tensor perturbations.This variational score avoids the potentially ill-posed best rank-r CP approximation for generic tensors.
  • Population signal: For an interval containing one change, the population CUSUM signal has a unique maximum at the change point, with peak height η(t)κ for an odeco rank-r jump.The exact tent-shaped population signal is obtained from the piecewise-linear expectation across the change.
  • Population signal: The squared margin grows linearly away from the change as (t − s)κ^2 for t > η, providing the engine for localization bounds.The corresponding margin on the other side is given by the symmetric population expression.

4 Tensor deviation inequalities

The section develops direct injective-norm concentration for degree-three tensor chaoses, avoiding flattening and its artificial d^2 dimension. It also gives an exact diagonal specialization with lower √log d dependence and an O(nd) prefix-sum implementation.

  • Full tensor bounds: Direct injective-norm control replaces matrix Bernstein and tensor flattening, preserving odeco geometry without introducing an artificial dimension of order d^2.The full tensor is handled through its injective norm rather than a coordinatewise or flattened representation.
  • Full tensor bounds: Fixed contractions have ψ2/3 tails and order-three chaos moment growth with exponent 3/2.The dimension-free bound follows from polynomial-chaos hypercontractivity and the degree-three isometry.
  • Full tensor bounds: The weighted tensor Bernstein bound separates Gaussian-process and single-sample order-three scales, with N and effective-dimension powers matching sharp simple-tensor concentration.The result applies to independent, not necessarily identically distributed observations with densities bounded by L.
  • Diagonal specialization: For coordinate-odeco jumps, the diagonal scan is exact and obtains a substantially smaller noise level through Hoeffding’s inequality.The diagonal entries reduce to ϕ3(Xj), and the resulting score equals the full odeco score at the population tensor.
  • Diagonal specialization: O(nd) construction and O(d) per-candidate evaluation using d prefix sums, together with √log d dependence, enable the high-dimensional experiments.The diagonal method avoids materializing the full tensor and is particularly useful when N is proportional to d.
  • Comparison of bounds: The full and diagonal bounds serve different regimes: the former handles arbitrary odeco directions, while the latter is exact for coordinate-odeco jumps.At d = 100 and n = 800, the unregularized full-tensor score is dominated by the d^3/2/√n regime, whereas the diagonal score follows the population tent.

5 Localization and multiple change points

The section establishes one-change localization from a tent-shaped population margin under uniform score error, then extends it to exact multiple-change recovery using seeded intervals and padded recentering. An induction shows inactive null segments, active isolating seeds for every undetected change, and localization within prescribed radii.

  • One-change localization: Theorem 5.1 localizes a single change whenever the candidate set contains it and the score error is uniformly bounded.The proof compares a squared margin at least ακ2|t −η| with empirical score loss at most 2εm.
  • Seeded detection: Seed intervals use multiscale half-overlap geometry, with candidates restricted to interval central halves and every sufficiently interior change covered by a balanced length-h seed.At layer j, intervals have length ℓj = min(2^jh, n), starts separated by floor(ℓj/2), and seeds retain distance at least h/4 from both endpoints.
  • Padded recentering: A shortest active length-h seed is padded by g = h/8 before a local scan, restoring balance when the true change lies outside the seed’s central half.The padded interval is clipped to the current recursive segment before maximizing the score.
  • Induction proof: The induction maintains consistency because null recursive segments stay inactive, every undetected change retains an active isolating seed, and the shortest active seed contains exactly one change before recentering.Padding keeps that interval below the minimum spacing and places the change at least h/8 from both endpoints, preserving the induction hypothesis.

6 Cross-fitted refinement and minimax localization

Cross-fitted scalar refinement sharpens localization to the classical κ^-2 scale after an isolating interval and changing direction are available. A rank-one cubic family with no degree-at-most-two projection jump establishes that this small-jump rate is minimax-order optimal.

  • Cross-fitted refinement: O_P(κ^-2) localization is attained in the small-jump regime under pilot-alignment and anchor-accuracy conditions.The refined estimator is simultaneous across changes with conditional and unconditional probability guarantees under the stated assumptions.
  • Cross-fitted refinement: Parity-split pilot and held-out folds construct a direction-independent scalar cubic feature for refinement.The method estimates a frame on one fold and applies its scalar contraction to the held-out sequence.
  • Cross-fitted refinement: The median of two fold-specific refinements and the preliminary estimate protects against one unstable fold while retaining the theoretical rate.Outer anchor blocks estimate segment means, and held-out residual sums of squares determine each refinement.
  • Minimax localization: Every degree-at-most-two coefficient matches the uniform density in a rank-one cubic family, while the degree-three encoding jumps by θ.The family’s jump size is |θ|, making lower-order segment-mean CUSUMs population-insensitive.
  • Minimax localization: h ≍ κ^-2 separates two change locations with Kullback–Leibler divergence O(hκ^2), yielding a Le Cam lower bound and minimax-order localization.The lower-bound construction applies in the small-jump regime with sufficiently large spacing.

7 Experiments

Experiments across dimensions 20–200 show that LR-D3 reliably detects pure cubic changes while mean and degree-two methods lack population signal. A d=100 multiple-change sequence recovers all three changes in every replication with small Hausdorff error.

  • Experimental signal: Every mean and degree-two coefficient remains unchanged in the pure cubic family, while the degree-three jump has Frobenius norm ∥θ+ − θ−∥2.Thus the experiment isolates third-order signal from lower-order population signal.
  • Single-change experiments: For d ∈ {20, 50, 100, 200}, LR-D3 is evaluated against cubic, degree-two, degree-one/two, mean-CUSUM, and oracle baselines over 30 replications.The design sets n = 60d, η = n/2, θ− = 0, and θ+ = 0.34e1.
  • Single-change experiments: The oracle and preliminary LR-D3 medians coincide at d ≥50, indicating reliable selection of the changing coordinate.Refinement improves medians at d = 20 and d = 200, is comparable at d = 100, and is less favorable at d = 50.
  • Score validation: At d = 100 and n = 800, empirical and exact population degree-three scores both peak close to the true change.The unregularized full-tensor optimization has much larger noise at this sample size.
  • Multiple-change experiment: In the d = 100 multiple-change experiment, the estimated number of changes equals three in every run across 30 replications.True changes are (2400, 4800, 7200), with median Hausdorff errors of 27 and 28 for preliminary and refined estimates, respectively.

8 Discussion and limitations

The degree-three projection supplies exact finite-dimensional geometry but incurs genuine tensor, computational, and projection limitations. The paper also documents reproducibility practices and cautions against causal or broader interpretations of detected changes.

  • Tensor complexity: The full injective-norm theorem shows that sample size merely proportional to d may be insufficient because the d^3/2/N term can dominate.Coordinate odeco structure, a known dictionary, or a small directional sketch can reduce this complexity; the experiments use the coordinate-odeco specialization.
  • Statistical and computational limitations: The method has zero population signal when P3(f1 − f0) = 0 and is mainly proved for independent observations.A geometric β-mixing extension uses blocking but incurs logarithmic block factors.
  • Statistical and computational limitations: Generic tensor injective-norm optimization is nonconvex and computationally hard, while practical odeco power methods and implicit Stiefel optimization lack global-maximizer guarantees.These methods are practical only under favorable structure.
  • Reproducibility: The source archive provides exact code, requirements, raw CSV results, threshold calibration, figure data, and regeneration commands without requiring external datasets.The tensor is evaluated implicitly, and the code includes a Monte Carlo check of Equation (7).
  • Broader impact and ethics: Practitioners should calibrate false-alarm rates and should not interpret detected projection changes as causal evidence, since the polynomial projection may miss changes outside the retained degree.The work is methodological and uses synthetic data.

A Proofs for the degree-three representation … E.1 Seed geometry

The proofs establish the degree-three tensor representation, its implicit contractions and score properties, and the concentration tools for polynomial-chaos tensor statistics. They then derive the population CUSUM geometry and a balanced seed construction supporting multi-change localization.

  • A Proofs for the degree-three representation: Orthonormal tensor and polynomial bases, together with Parseval’s identity, show that the degree-three tensor representation preserves the L2 norm of the corresponding density projection.For B = Σ bαEα, tensor contraction equals the matching polynomial expansion, and orthonormality under µ gives the squared coefficient norm.
  • A.1 Verification of the entry table; A.2 Derivation of the implicit contraction: The entry table assigns θα/√qα to each distinct permutation, while the implicit contraction expands into seven multi-index types and reduces pair and triple sums using elementary symmetric-polynomial identities.These calculations verify the coordinatewise tensor entries and provide an implicit contraction without explicitly forming the full tensor.
  • B Tensor score properties: The tensor score equals the Frobenius norm for sufficiently low-rank odeco tensors and is stable under perturbations through the injective norm; approximate odeco jumps add a √r∥R∥inj error.The approximate-odeco result replaces the jump size by ∥Dod∥F and adds the corresponding approximation term to εm.
  • C Proof of the tensor deviation inequality; C.1 Polynomial-chaos moment input: Degree-at-most-three Legendre contractions are sub-Weibull polynomial chaoses with ψ2/3 moment growth, enabling concentration for tensor-score statistics.Product-ensemble hypercontractivity tensorizes across independent coordinates, and centering changes the Lq norm by at most a factor two.
  • C.2 Weighted scalar concentration: The weighted scalar concentration bound has two necessary terms for general ψ2/3 summands, and a net over tensor-product directions transfers fixed-direction bounds to the injective norm.The proof uses a 1/8-net of Sp−1 with at most 17p points in each factor and a telescoping approximation argument.
  • D Population geometry and the one-change theorem; D.1 Population CUSUM calculation: The population CUSUM has a tent-shaped mean contrast: on either side of η, its mean difference is proportional to the jump tensor D with coefficient (e−η)/(e−t) or its symmetric counterpart.The squared-score gap grows linearly with distance from η, while null intervals have zero population score and one-change intervals have signal at least ακ√m.
  • E Full induction proof for multiple changes; E.1 Seed geometry: A balanced isolating seed exists whenever a change η in a recursive segment (a,c] is at least 3h/4 from both boundaries.Half-overlap length-h intervals start h/2 apart, and one of the two intervals overlapping η has endpoint distances at least h/4 while remaining inside the segment.

E.2 Boundary contamination

The proof controls inherited boundary contamination so change-free intervals remain inactive while intervals containing an undetected change remain detectable. A shortest active seed then contains exactly one change, and padded recentering preserves balance and localization through recursive recovery.

  • Inductive activity: Change-free seeded and terminal intervals remain inactive because boundary contamination contributes at most a fixed multiple of εh, below τ.This rules out duplicate or false detections when C0 is sufficiently large.
  • Inductive activity: Every segment containing an undetected change is active: an isolating seed of length h has population score at least κk h/4, exceeding τ after empirical error.The seed contains no other true change because h < ∆.
  • Seed selection: The shortest active seed has length exactly h and contains exactly one true change, since no seeded interval is shorter and h < ∆.Step 1 excludes the possibility that the selected seed is change-free.
  • Padded localization: Padding by g = h/8 yields balance at least 1/10, excludes other changes because 5h/4 ≤15∆/16 < ∆, and gives |bηk −ηk| ≤Rk.The padded candidate range contains the isolated change, enabling Theorem 5.1.
  • Induction closure: With Rk ≤h/8 < ∆/2 and h ≤3∆/4, recursive splitting preserves the 3h/4 boundary margin and the contamination form for child segments.After K steps, no undetected change remains and exactly K estimates are returned.

F Proofs for cross-fitted refinement · F.1 A scalar localization lemma

The proofs establish a scalar least-squares localization lemma under sub-Weibull errors and use it to justify cross-fitted refinement via fixed anchor estimates, held-out independence, and fold-wise union bounds.

  • F Proofs for cross-fitted refinement: Lemma 6.1 decomposes the tensor estimate as bC = aD + E, then defines the frame-score maximizer bU and bV through Equation (38).
  • F Proofs for cross-fitted refinement: The assumed inequality is used directly to obtain Equation (40).
  • F.1 A scalar localization lemma: Lemma F.1 considers independent scalar observations with means µL and µR separated by δµ = |µR − µL| > 0.
  • F.1 A scalar localization lemma: The localization estimator minimizes residual sums of squares using fixed anchor means, assuming centered ψ2/3 errors and anchor accuracy within δµ/8.
  • F.1 A scalar localization lemma: For candidates t > η, the proof writes the exact objective increment using h = t − η, the estimated jump bδ, and post-change observations Zi = µR + ξi.
  • F.1 A scalar localization lemma: On the anchor event, both deterministic factors lie between 3δµ/4 and 5δµ/4, yielding a controlled positive deterministic contribution.
  • F.1 A scalar localization lemma: Maximal partial-sum control follows from the same sub-Weibull inequality, using martingale structure together with Doob’s Lq and Markov’s inequalities.
  • F.1 A scalar localization lemma: Theorem 6.2 conditions on pilot and anchor data, applies Lemma F.1 to independent held-out observations with δµ = |⟨Dk, bV⟩| ≥ κk/2, and combines fold estimates by a union bound and median.

G Proof of the minimax lower bound … I.4 Implementation details

The appendices establish the κ^-2 minimax localization lower bound, extend tensor deviation control to geometrically beta-mixing data, and document computational checks, stress tests, localization summaries, and implementation details. The experiments include a d = 100, n = 800 full-tensor stress curve and a Monte Carlo isometry check with 250,000 samples in d = 8.

  • G Proof of the minimax lower bound: The lower-bound construction preserves all density coefficients of total degree at most two while producing tensor jump θe⊗3.Nonnegativity and normalization follow from |θϕ3(x1)| ≤ 1/2 and Eµϕ3 = 0.
  • G Proof of the minimax lower bound: h = ⌊c0/κ2⌋ makes the product-law divergence at most 2hκ2, yielding the κ^-2 localization lower bound via Pinsker’s inequality and Le Cam’s lemma.The constant c0 is chosen sufficiently small.
  • H Geometrically beta-mixing extension: Geometric beta-mixing is handled by partitioning CUSUM intervals into blocks, separating odd and even blocks, and applying Berbee coupling.The coupling failure probability is controlled by choosing the block length q according to the mixing rate and target δ.
  • H Geometrically beta-mixing extension: The mixing extension inflates the independent balanced-CUSUM rate by at most √q in the Gaussian term and q in the third-order term.The result holds with probability at least 1 − 2δ, with ρ = 3p log 17 + log(C/δ).
  • I.1 Full-tensor stress curve: At d = 100 and n = 800, the unregularized implicit full-tensor score is dominated by tensor noise, whereas the diagonal-odeco score tracks the population tent.The observed behavior is consistent with the d3/2/√n CUSUM term in Equation (24).
  • I.2 Monte Carlo isometry check: 250,000 uniform samples at d = 8 were used to numerically check the isometry for random unit vectors u, v ∈ R9.The passage explicitly notes that this is a numerical check rather than part of the proof.
  • I.3 Complete single-change summaries: Table 3 reports median, mean, and 90% quantile absolute localization errors over 30 replications.These are the summary statistics for the complete single-change experiments.
  • I.4 Implementation details: The implementation computes one prefix sum of ϕ3(Xij) per coordinate, then evaluates candidate CUSUMs by vector operations and selects the largest r absolute coordinates.The full degree-two baseline uses compact prefix matrices at candidate locations, while the representative full-tensor curve uses PyTorch, implicit contractions, Adam, and QR projection.
Loading 2608.15466v1…