acceptodds
Under review as a conference paper at ICLR 2027

Nonparametric Multiple Change-Point Detection for Random Objects

Abstract

Change-point analysis for non-Euclidean data has become increasingly important in modern applications, where observations often lie in complex metric spaces rather than vector spaces. We propose a distance profiles-based change-point estimation framework for sequences of objects taking values in general metric spaces, which combines distance profiles with a dynamic programming scheme to enable efficient multiple change-point detection. The proposed method is fully nonparametric, requires minimal tuning, and is applicable as long as pairwise distances between observations are available. We establish a non-asymptotic oracle inequality for our method under mild regularity conditions. Extensive simulation studies demonstrate favorable performance compared to existing approaches. We further illustrate the practical relevance of our method through applications to three representative non-Euclidean datasets, including compositional data, network-valued data, and financial correlation matrices.

Primary area:
learning theory
Keywords:
Nonparametric multiple change point detection, Random objects, Distance profiles

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_6QiHOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes DPDCP, a distance-profile-based framework for detecting multiple distributional change points in sequences of random objects from general metric spaces. It converts the problem into a least-squares segmentation objective based on indicators of pairwise distances, derives computable costs for two empirical weighting schemes (H1 and H2), and uses dynamic programming with a penalty to estimate both the number and locations of change points. The paper also presents a non-asymptotic oracle inequality and evaluates the method on simulated density, network, SPD-matrix, and spherical data, as well as real network, financial-correlation, and electricity-composition sequences. The method is attractive because it works from pairwise distances and avoids a separate kernel-bandwidth selection step. However, the theory assumes independent observations within each segment, the real-data examples do not provide ground-truth change points or systematic baseline comparisons, and the cubic precomputation cost becomes substantial at larger sample sizes.

Critical strengths
  1. The distance-profile formulation provides a unified way to compare distributions of non-Euclidean objects, and the segmentation objective can be optimized globally by dynamic programming rather than through sequential binary segmentation.

  2. The paper derives explicit segment costs for two weighting schemes and provides a finite-sample oracle inequality. Simulations cover several types of random objects and include comparisons with KCP and MCPD.

Critical weaknesses
  1. The theoretical guarantee relies on independence within each true segment, but the real-world sequences are temporally dependent. In particular, the financial correlation matrices use heavily overlapping 60-day rolling windows advanced by only 10 days. The paper does not establish that the theoretical guarantees or empirical conclusions remain valid under this dependence.

  2. The practical validation is not sufficiently conclusive. The real-data case studies have no independent ground truth for the reported change points and do not systematically compare against the baselines used in simulation. The claimed broad applicability is therefore supported mainly by illustrative visual interpretation.

  3. The method requires O(n^3) preprocessing, and reported runtimes at n=5000 are about 506 seconds for H1 and 158 seconds for H2 in the temporal-dependence experiment. This limits the strength of the efficiency claim for long sequences unless approximation or further acceleration is central to the intended use.

Questions for authors
  1. How should DPDCP be used when observations are temporally dependent, as in the rolling-window financial example? Can the authors provide a dependence-aware analysis or clarify which claims remain valid without the segmentwise-i.i.d. assumption?

  2. Can the authors provide quantitative validation of the real-data change points—for example, sensitivity analyses, external event-based evidence, or comparisons with established baselines—and clarify how the penalty is calibrated in these applications?

Reviewer_KgpzOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In the offline setting, this paper studies non-parametric multiple change-point detection for non-Euclidean data. The proposed method is based on the recent tool of distance profiles for random objects, together with dynamic programming techniques. A non-asymmetric oracle inequality is established under some mild regularity conditions. Extensive simulation studies show the favorable performance of the proposed methods compared to some baselines. Experiments on real data show that the proposed method can be applied to three representative non-Euclidean datasets.

Critical strengths
  1. The change point detection method is generally designed for non-Euclidean data structures. The performance on the simulated data is better, and the average runtime is comparable to the baselines.

  2. The theory proves that the proposed method, with a large enough penalty, estimates the segment-wise distance profiles at a near-optimal rate.

Critical weaknesses
  1. The literature review is not complete; some comparisons of related works are not discussed, and the position of this paper in the literature is not clear (Questions 1-2).

  2. Some statements and novelty are overclaimed in some senses (Questions 3-4).

  3. One of my main concerns is that this paper lacks analysis of the performance guarantees for change point detection (Question 5).

Questions for authors
  1. The discussion of related work in the introduction section can be improved. Regarding the discussion of general change point detection methods for non-Euclidean data structures, the paper [R1] should be included since [R1] proposes a method to infer the presence and location of change-points in the distribution of a sequence of independent data taking values in a general metric space. Moreover, since the experimental section includes some data structure on the SPD manifold, some recent works on manifolds [R2] should also be included.

  2. The kernel change point detection method by Arlot et al., 2019 should be more detailed in the introduction section. This is quite close work to the proposed one. Some discussion on comparisons can also be added.

  3. "To the best of our knowledge, this framework is novel in the nonparametric change-point literature. In particular, no analogous nonparametric regression approach exists even for Euclidean data." This is overclaimed because the kernel change-point detection methods of Harchaoui & Cappé, 2007 and Arlot et al., 2019 are exactly this framework.

  4. The novelty is overstated. The method can be regarded as the KCP method of Arlot et al. (2019) with a specific data-dependent kernel and Arlot et al.’s penalty. The comparison with KCP is really a comparison of kernel choices.

  5. The theory only bounds the risk of estimating the distance profiles and provides no guarantees on Type I error control, power, or localization of change points. By contrast, such guarantees are (partially) established in Dubey & Zheng (2026), [R1] and so on.

[R1] P. Dubey and H.-G. Müller. Fréchet change-point detection. Ann. Statist., 48(6), 2020.

[R2] X. Wang, R. A. Borsoi, and C. Richard. Non-parametric online change point detection on Riemannian manifolds. In Proc. ICML, 2024.

Reviewer_jgVTOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper proposes a method for offline multiple change-point detection, to address the challenge of input being non-Euclidean objects. Here, the input is the pairwise distance matrix. The proposed method uses distance profiles, i.e. the distribution of distances from a point to the data, as features of the observations. It then picks the number and locations of the change points by minimizing a least-squares criterion plus a penalty on the number of change points, solved by dynamic programming. Theoretically, they prove an oracle inequality: the error of the selected segmentation is within a constant factor of the best trade-off between error and penalty over all candidate segmentations. Empirically, they compare with 2 baselines, kernel change-point detection and the method of Dubey & Zheng. Three real-world datasets are tested.

Critical strengths
  • I believe the method is easy to implement and apply to many objects, therefore practical.
  • I did not go through all maths, with the help of AI I believe the theoretical analysis is correct.
  • The experiments look reasonably good. Compared with the method of Dubey & Zheng, both H1 and H2 are clearly better in both accuracy and speed. Compared with kernel change-point detection, they are more accurate when the signal is weak on network and covariance matrix data, about the same on distribution data, and somewhat slower.
Critical weaknesses
  • I think for CPD (Change point detection), it is always super important to emphasize if this method is offline or online. I see no such comments throughout the paper. From my own experience, I would expect solid reasons to study offline methods, however, the non-Euclidean objects line of work has been active for a while and I would expect the paper to explain what gap it fills, and I don’t see that.
  • The novelty is overclaimed. As the proposed method is basically a combination of two previous works, one on distance profiles, one on the algorithmic idea of change point detection.
  • The claim of handling non-Euclidean objects is weaker than it sounds. The method takes a pairwise distance matrix as input, so the work of handling non-Euclidean structure is pushed into choosing the metric, which the paper does not study. Once distances are given, there are tons of papers, or general tools to deal with the task. So needing only distances is not what sets this method apart. Also, in the simulations three of the four metrics are Euclidean after a simple transform (quantile functions, graph Laplacians, Cholesky factors). Only the sphere uses a truly non-Euclidean distance, so the “general metric space” claim is not really tested.
  • I would say 2 baselines and 3 real-world datasets are not enough. But as an author myself, I am not a fan of simply being asked to add more experiments. So I won't push hard on this.
Questions for authors

N.A.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.