Summary
The authors consider offline change point detection for multi-variate data where there could be multiple change points (specifically changes in marginal distributions from one time step to the next). The marginal densities of the underlying generative model are assumed to be smooth (specifically Hölder continuous, which includes Lipschitz continuous functions as a special case). Building on a procedure using binary-segmentation search with kernel density estimation and consistency (Padilla et al (2021)), the authors analogously show consistency of change-point estimators for time-dependent data. Furthermore, the authors derive limiting distributions of the change point estimators, both for the situation where the minimal jump size vanishes and for the situation where it remains constant.
Strengths
- The authors study a challenging problem, non-parametric estimation of multiple changepoints. Many prior works considered independent data and univariate, as well as stronger assumptions on the generative distributions.
- The authors prove consistency and analyze limiting distributions of the estimated change points. (also this is with less knowledge (such as of optimal bandwidths) than Padilla et al (2021))
- The authors include experiments and show its performance against baselines (designed for independent data).
Weaknesses
My main concerns regard writing/presentation and discussion of related works. I list a number of specific points below (many of which, by themselves, are fairly minor; list is not exhaustive).
#### Writing/presentation
- There is no discussion on motivating the time-series model class considered ($\alpha $-mixing sequences of random vectors with unknown marginal distributions), or even mention what types of common parametric classes belong to this class.
- The property of $\alpha $-mixing is never explained formally let alone any discussion on what that implies at a high-level for the time-series. There is a large literature on parametric time-series models – it would be valuable to mention example model classes that satisfy the assumptions here.
- What types of potential applications could this benefit (the time-series of which could plausibly be modeled with this class of models)? Lines 20-24 mention application areas with time-series data, which is fine, but there should be more of a connection made between (some of) those applications and the specific problem considered.
- Algorithm 1 and Section 3
- Provide discussion in the main text about the steps of Alg. 1 and intuition behind the design.
- SBS is mentioned but is not described (a brief high-level description should suffice)
- There is notation used in the algorithm that is not mentioned in Section 3, explain what those are.
- Include discussion about kernel properties in Section 3. Alg 1 uses kernel estimators implicitly in the line with $\tilde{F}$, but up to this point no $\mathcal{K}$ is defined or taken as input, or described in Section 3.
- (minor) Def 1 text $\mathcal{K}$ has not been described (or listed in the def. set up)
- (4) and (5) give some verbal description of what this is doing (i.e. what is the intuition behind how you are improving the estimates, possibly with a line or two about the way(s) in which the MNSBS might give poor(er) estimates that leads to this design). Presumably it has to do with that the choice of interval locations and sizing in MNSBS was using a simple pattern (oblivious to where the estimated change points would be). Now you have ‘naturally defined’ intervals between the estimated change points (so size and location of the intervals are adapted to the initial estimates).
- line 124-125 talk about the choice of weights 9/10 and 1/10.
- line 125 ‘an estimator of $\kappa_k$’ I would suggest to add verbal descriptors for notation to remind the reader, such as ‘an estimator of the jump size $\kappa_k$ at the $k$th change point’ and similarly for other notation. Also, several lines later (to explain differences with prior work) there is mention that it corresponds to the ‘optimal bandwidth’ and ‘ we use $\hat{\kappa}_k$ as bandwidth for the kernel density estimator’ though in line 127 the bandwidth used is $h_1$ which depends on, but is not set equal to, $\hat{\kappa}_k$. A clarification of that part, and a couple sentences shortly after Definition 1 about the bandwidth $h$ to lead the reader to anticipate why $h_1$ in line 127 is good would help.
- while bandwidths are mentioned earlier (Def. 1 for instance) there is no discussion on bandwidth optimality. Padilla et al (2021) have nice discussions regarding the choice of the bandwidth; I would suggest summarizing the key points to give intuition to the reader.
- line 132 ‘smaller interval’ – provide brief intuition about why the intervals here would be smaller than the
#### Experiments
- Include plots of the realizations of the time-series (to give intuition for how hard/easy the task is for those generative models)
- Report the run-times for the proposed method and baselines. With that also briefly describe the platform.
- It would also be valuable to run experiments with independent data, to see whether the proposed method suffers compared to baselines designed for that setting specifically.
#### Related works
- “Random Forests for Change Point Detection” by Londschien et al https://arxiv.org/abs/2205.04997 a multivariate nonparametric
change point detection methods for independent data (with an R package available) – in their experiments, their method generally was similar or better than ECP (the best baseline in your experiments) and had subquadratic time complexity
- There are works non-parametrically estimating the location and size of structural breaks in non-parametric time-series regression models. “Estimating change points in nonparametric time series regression models” by Mohr and Selk (2020) https://doi.org/10.1007/s00362-020-01162-8, “ Nonparametric inference on structural breaks “ by Delgado and Hidalgo (2000) https://doi.org/10.1016/S0304-4076(99)00052-4 among others. Given some (at least superficial) relation in the problem considered and some methodological components collectively in that body of work and the present work, which extends methods and results for non-parametric changepoint detection for independent data (esp. Padilla et al (2021)) to allowing for dependencies, I think some discussion on the how the problems, methods, and results of changepoint detection for non-parametric time-series regression relate would be helpful. Xu et al (2022) is mentioned in lines 181-182, though what the paper actually studied and how it related was not described.
- A (brief) discussion of similarities and differences between the problem considered here and that of (non-parametric) online change point detection would be good.
- One of the main contributions is characterizing the limiting distributions for multiple change point estimates in this non-parametric setting. To my knowledge, that is novel for the specific problem considered. However, similarities/differences in analyses and results (class of distributions that the limiting distribution belongs to) for past works that have investigated limiting distributions of change point estimates in different by related settings are not well-discussed. Unless I overlooked it, the only other work mentioned in the context of identifying limiting distribution of change point estimators is Xu et al (2022) in lines 181-182 and that was brief and implicit.
- There are prior works that studied limit distributions for non-parametric estimators for single change point detection with independent data (as well as works in the parametric setting), although from what I can tell under simpler changes (such as changes in the mean). For example, “The Asymptotic Behavior of Some Nonparametric Change-Point Estimators” by Dumbgen (1991) and Horváth and Kokoszka (1997) "The effect of long-range dependence on change-point estimators." Also “Optimal change-point estimation in time series” by Chan et al. 2021 for limiting distribution of single time-series change point (Bayes) estimators. There is a recent work “On multiple structural breaks in distribution: An empirical characteristic function approach” by Fu et al (2022) that analyzes the limiting distributions for estimates of multiple change point. Also potentially relevant is “The asymptotic distribution of CUSUM estimator based on $\alpha$-mixing sequences” by Gao et al (2022), though the analysis is for univariate non-negative $\alpha$-mixing non-negative random variables.
- Limiting distributions of change point estimates have been studied in the parametric setting. While those results do not diminish the significance of the results in this paper, there should be some mention and preferably a discussion on similarities/differences between the derived distributions.
Questions
#### Questions
- Assumption 3 and Theorem 1. The $\gamma_T$ does not explicitly show up in the Theorem 1 statement – which constants depend on $\gamma_T$? Given the assumption statement is only “arbitrarily slow diverging sequence” that seems to me impressive though almost too mild for anything other than statements about the limit $T \to \infty$
- For the theorems, is $\Delta$ *required* to be growing as a function of $T$? From the assumptions it looks like as long as the jump size is increasing fast enough, we could fix the location of $K$ changepoints and the assumptions would hold. $\kappa$ growing quickly should make detecting change points easier, but would there still need to be some minimum value of $\Delta$?
- Contribution 1 (lines 84-87) – The first major contribution claimed is the development of a novel algorithm and statement “To the best of our knowledge, we are the first to innovatively adapt SBS to a multivariate non-parametric change point model”. From a (perhaps superficial) understanding, the Algorithm 1 proposed here seems to be an incremental adaptation of the procedure proposed in Padilla et al (2021), with the random binary segmentation used in the latter replaced with the recently proposed deterministic binary segmentation method SBS (Kovács et al. (2020)). Perhaps the authors can add more discussion on why that change is not straightforward.
#### Spelling, Grammar, etc.
- Line 98 ‘A … estimators’
- Theorem 2 statement – The formal statement could be shortened and I think easier to read if the notation (eg 188-189, 192- (7)) were introduced and discussed (add simple description of $P_k$’s formula when it is introduced) before the formal theorem statement.
- For theorem 3, maybe $\max_{1\leq k \leq K} \dots$
- line 291 ‘additional additional’
- lines 291-293 – that is great you had further experiments; mention that earlier both in introduction and early on in Section 5.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
It is fine (theoretical contribution)