PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal detection of general moment changes: Simultaneous mean and covariance change detection and beyond

Xiaokai Luo, Chenghao Xu, Haotian Xu, Carlos Misael Madrid Padilla, Daren Wang

arXiv:2609.36594v1stat.MEmath.STstat.MLstat.TH

TL;DR

Multiple change points in multivariate time series may involve shifts across moment orders, while higher-order moments are difficult to estimate in high dimensions. The paper uses a unified tensor representation to detect changes through a fixed order p, and its localization rate matches a newly developed minimax lower bound under suitable conditions.

  • Problem

    The paper studies how to detect multiple change points in multivariate time series when distributional shifts can occur across moment orders, including higher-order moments that are difficult to estimate in high dimensions.

    Source: §1 · pp. 1–2, §1.2 · p. 4

  • Method

    A tensor representation combines moment orders in a unified framework to detect changes through a prescribed fixed order p.

    Source: §1.2 · p. 4

  • Results

    The localization rate matches a newly developed minimax lower bound under the paper’s stated regularity conditions.

    Source: §1.2 · p. 4

  • Takeaways & Limitations

    The framework treats mean, covariance, and higher-order moment changes within one change-detection procedure.

    Source: §1.2 · p. 4

    Growing dimension and vanishing jumps are allowed provided segments contain enough observations to estimate higher-order moments accurately.

    Source: §2.2 · p. 8

Abstract

from arXiv · show

We study multiple change-point detection in multivariate time series whose distributions change in a piecewise constant manner. Distributional changes can manifest across different moment orders, from shifts in the mean and covariance to changes in higher-order moments. Higher-order moments capture increasingly rich distributional features but become difficult to estimate in high dimensions. Our tensor representation unifies moments of different orders within a common linear algebraic framework, enabling a new method to detect changes in moments of all orders up to a prescribed fixed order $p$. The resulting procedure accommodates temporal dependence and allows the dimension of the time series to grow with the sample size. Under suitable regularity conditions, the proposed procedure achieves a localization error rate that matches a newly developed minimax lower bound. We further derive limiting distributions under both nonvanishing and vanishing moment jumps and construct asymptotically valid confidence intervals in the vanishing-jump regime. Numerical experiments and real-data analyses demonstrate the method's effectiveness in detecting moment changes and a range of distributional shifts.

1 Introduction

The paper addresses multiple change points in multivariate time series, where shifts can affect moments beyond the mean and covariance. It unifies moment orders in a tensor framework and develops localization and inference guarantees for changes through a fixed order p.

1 Introduction

  • Change-point analysis partitions observations into homogeneous segments and quantifies uncertainty about transition locations.The motivating setting allows the time-series dimension to grow with sample size and temporal dependence in the observations.Source: §1 · pp. 1–2

1.1 Related literature

  • Prior approaches described here target means or covariances, or broader distributional changes under independence; the paper instead treats multiple joint-moment changes under temporal dependence.A closely related mean-and-covariance method focuses on testing under independence and a single change, without a localization rate or location limiting distribution.Source: §1.1 · p. 3

1.2 Contributions

  • The method detects changes jointly across all joint moments through a prescribed fixed order p, extending beyond mean and covariance shifts.Its tensor representation combines information across moment orders in a unified linear algebra framework.Source: §1.2 · p. 4
  • The localization rate matches a newly established minimax lower bound, characterizing the difficulty of locating changes using higher-order moments.The result applies under the paper’s stated regularity conditions.Source: §1.2 · p. 4
  • The paper derives change-point location limits for vanishing and nonvanishing jumps under temporal dependence, and constructs asymptotically valid confidence intervals for vanishing jumps.The contribution quantifies uncertainty in estimated change-point locations.Source: §1.2 · p. 4

2 Change-point localization

The localization procedure first detects candidate changes on seeded intervals, then refines their locations using estimated moment jumps and projection directions. Under stated conditions, the refined localization rate matches a minimax lower bound.

2.1 Preliminary seeded detection

  • The preliminary stage evaluates tensor CUSUM statistics over seeded intervals and uses narrowest-over-threshold selection to initialize change-point locations.The statistic searches the central half of an interval, and its threshold adjusts for interval length, moment order, and temporal dependence.Source: §2.1 · pp. 5–6

2.2 Local refinement

  • The second stage estimates moment jumps and their leading projection directions from preliminary locations, then uses the estimated projection to refine each location.Moment fitting uses the central half of each estimated segment to avoid uncertain boundaries.Source: §2.2 · p. 7
  • The refined localization error for each change point is OP(σ2p/κ2_k), with constants and signal requirements depending on fixed moment order p.The guarantees allow growing dimension and vanishing jump magnitudes when segments are long enough to estimate higher-order moments accurately.Source: §2.2 · p. 8

2.3 Minimax lower bound

  • The refined rate matches a newly established minimax lower bound for the stated class of independent observations.The lower-bound result considers fixed p and, under its stated conditions, κ no greater than a constant multiple of σp.Source: §2.3 · pp. 8–9

3 Limiting distributions and confidence intervals

The section derives change-point location limits for nonvanishing and vanishing moment jumps under temporal dependence, then uses the vanishing-jump limit to construct data-driven confidence intervals.

3.3 Confidence intervals

  • For vanishing jumps, the authors construct data-driven confidence intervals for change-point locations with asymptotically valid coverage.The procedure estimates the jump magnitude from projected moment averages on adjacent fitting intervals and estimates long-run variances using Bartlett estimators that account for temporal dependence.Source: §3 · p. 9, §3.3 · pp. 11–12

3.1 The nonvanishing regime

  • The nonvanishing-regime limit theory uses a continuity condition that ensures uniqueness of the limiting random-walk minimizer.Theorem 4 concerns the refined estimator; the stated conditions include a density condition for the local process.Source: §3.1 · pp. 9–10

3.2 The vanishing regime

  • In the vanishing-jump regime, the refined estimator’s rescaled localization error converges in distribution to the minimizer of a two-sided Brownian motion with drift.The result is stated under the assumptions of Theorem 5.Source: §3.2 · p. 10

4 Simulation and real data example

The experiments compare Tensor with methods for mean, covariance, and broader distributional changes across simulated settings and two Nasdaq-100 stock panels. Tensor recovers changes accurately in simulations, while real-data estimates align with market disruptions even when competing methods return different dates.

4 Simulation and real data example

  • The method is compared with CPWZ, changeAUC, a mean-change binary segmentation method, and MNSBS, using competitors’ default or paper-recommended tuning procedures.CPWZ targets joint mean and covariance changes, changeAUC uses a classifier, and MNSBS uses nonparametric density estimation with seeded binary segmentation.Source: §4 · p. 12, §4.1 · p. 12

4.2 Hausdorff distance

  • The Hausdorff distance compares true and estimated change-point sets without requiring equal counts and is reported in observation-index units.For empty outputs, the simulation implementation uses a finite convention.Source: §4.2 · p. 13

4.3 Simulation studies

  • Across 100 repetitions, simulations used D = 100 and stationary AR(1) sequences, with settings covering single and multiple changes.The scenarios include variance, skewness, mean, and scale changes, as well as unequal jump sizes and spacings.Source: §4.3 · p. 13
  • Tensor recovered the correct number of changes in all 100 repetitions per setting and had the lowest refined mean Hausdorff distances; in R2 and R3, these were 7.15 and 10.95 versus CPWZ’s 343.62 and 49.95.In R4 and R5, Tensor’s mean distances were 1.82 and 1.00, and competing methods had larger localization errors and less reliable change counts.Source: §4.3 · pp. 13–14, Table 1 · p. 14
  • Simulation-calibrated 95% Tensor intervals had empirical coverage of 95% in R4 and 96% in R5 at each change point, conditional on estimating two changes.Figures 1 and 2 show intervals from the first ten repetitions in R4 and R5, respectively.Source: §4.3 · p. 14, Table 2 · p. 14, Figure 1 · p. 14

4.4 Real data analysis

  • For both Nasdaq-100 panels, tuning selected p = 2 and τ = 16; refinement moved the 2008 estimate to September 15 and placed the 2020 estimate on February 21.The 2008 date matches the Lehman Brothers bankruptcy filing, while the 2020 estimate aligns with the onset of the market reversal associated with COVID-19’s international spread.Source: §4.4 · p. 15
  • MNSBS and changeAUC estimates also indicate changing market behavior during the 2008 crisis and early COVID-19 disruption, although their exact dates differ from Tensor’s.The panels contain 58 stocks over 988 observations in 2007–2010 and 59 stocks over 1,258 observations in 2018–2022.Source: §4.4 · pp. 15–16

A Proofs for Section 2.1

The proof establishes that the seeded-interval selection and pruning procedure returns exactly one distinct estimate for each true change. Its argument combines significant-interval detection with induction over selected changes and an ordering guarantee.

Detection on isolating intervals

  • Every significant interval contains an interior true change, because an interval with no interior change has zero population CUSUM and its statistic falls below threshold.The proof applies this fact to isolating intervals to ensure a true change is available at each selection step.Source: A Proofs for Section 2.1 · pp. 19–20

Selection and pruning

  • Induction shows that each selected shortest active interval yields a distinct matched change, while pruning removes intervals containing already matched changes.The selected intervals are pairwise disjoint because each selection removes all overlapping intervals.Source: A Proofs for Section 2.1 · pp. 20–21

Termination and ordering

  • The algorithm terminates after exactly K selections, and sorting the recorded points preserves their true order on the uniform-control event.The event has probability at least 1 − n^-5.Source: A Proofs for Section 2.1 · pp. 19, 21

B.1 Leading jump direction estimation

The proof ensures that preliminary estimates yield fitting intervals and refinement windows around individual changes, then establishes simultaneous accuracy and control of the estimated leading jump directions. These results rely on the stated spacing and direction-separation conditions.

Fitting intervals and refinement windows

  • When the minimum spacing is at least 256 and preliminary localization holds, each fitting interval lies within its true segment and each refinement window contains exactly one change.The fitting intervals have length at least 7∆min/16.Source: §B.1 · pp. 21–23

Simultaneous preliminary accuracy

  • Uniform empirical-moment bounds apply simultaneously to the data-selected fitting intervals, yielding the moment-control events needed for each refinement window.The proof combines the interval length bound, the selected constant in the uniform bound, and the window inclusions.Source: §B.1 · p. 23

Direction accuracy for local refinement

  • Under Assumptions 3 and 7, the estimated leading jump directions satisfy the direction-accuracy bound on the refinement event.The proof invokes the direction result with the adjacent population and fitted tensors, using the separation condition in Assumption 7.Source: §B.1 · p. 24

B.2 Proof of the refinement guarantee

The proof converts a large localization error into a boundary-crossing event and bounds that event using moment and probability inequalities. A union bound across changes then completes the refinement guarantee.

Proof setup

  • On the preliminary and refinement events, the proof uses population and fitted tensors, aligned directions, and centered forward and backward sums around each change.The argument treats leftward and rightward localization errors symmetrically.Source: §B.2 · pp. 24–25

Localization error implies a boundary crossing

  • If κ² times the localization error divided by σp² is at least M, the minimizing property of the refined estimate implies a boundary crossing.The proof bounds the crossing probabilities using moment inequalities and Markov’s inequality.Source: §B.2 · pp. 25–26

Probability bound

  • Bounding both crossing events and taking a union bound over the changes completes the probability argument for the refinement result.The proof absorbs a factor of 2 into the constant before the union bound.Source: §B.2 · p. 27

C Proof for Section 2.3

The proof constructs two change-point laws whose moment tensors agree below order p but differ at order p, then uses a two-point testing argument to establish a matching localization lower bound.

C Proof for Section 2.3

  • The proof places the change point at two locations h indices apart and converts the resulting testing error into localization risk.Only indices ∆+1 through ∆+h have different marginals under the two laws.Source: C Proof for Section 2.3 · pp. 27, 30, 31
  • The two Gaussian-mixture regimes share components but perturb their weights with opposite signs to create the moment jump.The construction embeds Z as X=(Z,0,...,0) in both regimes.Source: C Proof for Section 2.3 · p. 28
  • For 0<κ≤c0σ^p, the construction sets θ≤1/4 and verifies that the resulting alternatives belong to the stated model class.The class-membership verification applies for all sufficiently large n.Source: C Proof for Section 2.3 · pp. 28, 30
  • All moment differences below order p vanish, while the order-p tensor differs by κ at the entry indexed by (2,...,2).The differing entry corresponds to the coordinate Z.Source: C Proof for Section 2.3 · p. 29
  • 1/4 is a lower bound on the probability of error at least (β_p/4)σ^(2p)/κ^2 for every estimator under at least one alternative.This matches the localization scale in Theorem 2.Source: C Proof for Section 2.3 · p. 31

D Proofs for Section 3

The proofs control the fitted jump directions and establish a uniform approximation of the fitted local criterion by its oracle counterpart under the stated assumptions.

D Proofs for Section 3

  • The fitted direction approaches the population direction on the uniform empirical-moment event, with radius ρ_n,k=C_ν ε_n/κ_k.The stated limits hold uniformly over the fixed set of changes.Source: D Proofs for Section 3 · p. 32

D.1 Uniform oracle approximation

  • Lemma D.1 establishes uniform oracle equivalence for p≥2 and fixed K under Assumptions 1, 3, and 7, using the estimator and tuning in Theorem 2.Source: §D.1 · p. 32
  • The proof bounds the fitted criterion uniformly over a deterministic ball around the population direction before applying its moment bounds.On the uniform event, admissible local shifts remain inside the adjacent true regimes.Source: §D.1 · pp. 32–33

D.2 Nonvanishing-jump limit

For nonvanishing jumps, the proof obtains compact-set convergence of the local fitted criterion to a limiting process and establishes that its minimizer is finite and unique.

D.2 Nonvanishing-jump limit

  • The projected pth powers are uniformly integrable even when D grows, supporting the finite-dimensional convergence used in the limit argument.Source: §D.2 · p. 34
  • The limiting process tends to +∞, so its global minimum is finite; the proof also rules out ties and establishes a unique minimizer r*.Source: §D.2 · p. 35
  • With fixed σ and κ_k→κ*_k>0, the local fitted criterion converges to L_k on every compact subset of the integer index set.The proof uses uniform oracle equivalence and the stated projected finite-dimensional convergence.Source: §D.2 · p. 35
  • The estimator's centered criterion is tight, and the proof applies the argmax theorem to its negative to obtain the minimizer limit.Source: §D.2 · p. 35

D.3 Vanishing-jump limit

This section develops the vanishing-jump change-point limit and confidence-interval argument, including variance estimation and the concentration and uniform empirical-moment and CUSUM bounds under dependence that support it.

D.3 Vanishing-jump limit

  • The projected noise processes converge jointly on compact intervals to independent Brownian motions with their respective long-run standard deviations.The two-sided invariance principle holds under the conditions of Theorem 5.Source: §D.3 · pp. 36–38
  • The scaled change-point error converges to the unique finite minimizer of a limit criterion with drift |u| and two-sided Brownian noise.The criterion converges on compact intervals, and its limit has a unique finite minimizer almost surely.Source: §D.3 · pp. 39–40

D.4 Variance estimation and confidence intervals

  • The Bartlett estimators of the projected long-run variances are consistent under the conditions of Theorem 5.The proof accounts for the selected fitting interval and estimated direction, which use the same observations as the variance estimates.Source: §D.4 · p. 40
  • Plug-in Brownian quantiles, combined with the vanishing-jump limit, yield confidence intervals with asymptotic coverage.The quantiles evaluated at the estimated variance scales converge to those at the population scales.Source: §D.4 · p. 44
  • The limiting event has boundary probability zero, and the excluded probability is o(1), completing the stated claim.The passage attributes the vanishing excluded probability to Step 1.Source: §D.4 · p. 44

E.1 Uniform empirical-moment and tensor CUSUM bounds

  • Tensor-product variables are centered, have uniformly bounded ψ2/p norms, and inherit exponentially decaying α-mixing coefficients.The stated norm bound is Cpσp; the mixing coefficients are at most b0 exp(−b1ℓγ) for 1 ≤ℓ< n.Source: §E.1 · p. 46
  • Theorem 7 states uniform empirical-moment and tensor CUSUM bounds over all nonempty intervals under Assumption 1 for fixed p ≥2.The theorem specifies constants depending only on p, γ, b0, and b1.Source: §E.1 · p. 48

E.2 Results on seeded intervals

Appendix E.2 gives size properties for the seeded interval collection and establishes that, when changes are sufficiently separated, each change has an isolating seeded interval.

E.2 Results on seeded intervals

  • Lemma E.4 concerns the size of the seeded interval collection across dyadic scales, and removing duplicate intervals can only decrease both quantities.The proof recalls the dyadic scale set and seeded intervals at each scale.Source: §E.2 · p. 49
  • When Δmin ≥ 256, each change has a seeded interval containing it and no other change.The neighboring changes are at least Δmin away; the construction selects a dyadic scale no larger than Δmin/16.Source: §E.2 · p. 50
  • The construction selects a dyadic scale and a grid interval whose central half contains the change, then checks that the interval belongs to the finite seeded collection.The chosen scale is the largest dyadic length at most Δmin/16.Source: §E.2 · p. 50

E.3 Estimating the most significant projection direction

The section bounds error in the estimated most significant projection direction under a separation condition, then develops maximal bounds for projected moment sums under temporal dependence.

E.3 Estimating the most significant projection direction

  • For an orthogonal symmetric CP decomposition with positive weight gap Δ, the separation condition holds with r0 = 1 and c0 = Δ/(2 |λ1|).The leading projection direction is identifiable under this eigengap-type condition.Source: §E.3 · pp. 50–51
  • Under the separation condition, the maximizing direction error is bounded by pε/(c0κ).The theorem applies the perturbation result to the difference between the population tensors and their symmetric estimators.Source: §E.3 · pp. 53–54

E.4 Maximal bounds for projected moment sums

  • The fourth-moment maximal bound applies to centered variables bounded in L8 under the stated α-mixing condition, including independence when γ = ∞.Its proof combines fourth-moment interval-sum bounds with a dyadic decomposition of prefixes.Source: §E.4 · pp. 54–55
  • Under Assumption 1 and fixed p, maximal bounds control projected moment sums uniformly over directions near a fixed ν for forward or reverse lists.The bound's constant depends only on p and the fixed mixing parameters.Source: §E.4 · pp. 54–55
Loading 2609.36594v1…