Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers the "gradual change detection problem" i.e., the problem of identifying whether a time series has "shifted" (significantly) in a gradual / long term-ish way.  This is a bit different from the usual changepoint detection problem we are often concerned with in statistics (and to some extent machine learning), where we assume the change is much more abrupt (e.g., we might assume the underlying signal is piecewise constant).

Let the observations $Y_{t,T} := Y_t \sim P$, $t=1,\ldots,T$, for some fixed $T > 0$, and unknown $P$; a key component of the paper is that the authors let the $Y_t$, $t=1,\ldots,T$, take values in an arbitrary metric space.  Then, very roughly speaking, the authors say they are testing:
$$
H_0: P = P_0 \quad \textrm{vs.} \quad \textrm{$H_1:$ there exists some window such that $P = P_0$, and another such that $P \neq P_0$},
$$

where $P_0$ is a null distribution.  Actually, the authors go further and additionally consider the changepoint localization problem, i.e., the problem of identifying the changepoint itself, call it $\rho^*$.

The authors propose (something resembling) a kernelized version of the well-known absolute CUSUM statistic, derive its limit law (giving a Donsker-type theorem), and show that their test is asymptotically powerful.  They also propose two ways to localize $\rho^*$ (one natural estimator, and another estimator seen to be less biased than the natural one).  They give a decent number of simulations with synthetic data, and two experiments with real-data (which is always nice to see), where they measure power and the $\ell_1$ error in identifying $\rho^*$.
main_review: Overall, the paper tackles a very interesting problem.  Below, I raise a few medium-sized issues, as well as one larger issue re: related work (that kind of prevents me from fully endorsing the paper, at least for now).  I break down my review below according to the categories suggested by the NeurIPS reviewer guidelines.

**Originality.**  This seems to be a good place to raise the larger issue I mentioned above re: related work.  As the authors acknowledge in the paper, their proposal is very similar to that of Vogt et al. (2015).  However, to me, it also appears to be very similar to that of Harchaoui et al., 2008, i.e., the method called "KCpA" by the authors (essentially just without the covariance scaling of KCpA).  Therefore, I am a bit confused as to why KCpA performs so poorly in the experiments of Section 5.  Can the authors explain?  The authors mention that "for fairness, we use the same kernel for [their two method(s) as well as KCPA]"; but that actually doesn't seem entirely fair to me, as different methods certainly have different operating characteristics.  At the very least, different bandwidths should probably be used, but I assume this did not happen, either.

On the technical side of the originality question, it seems to me that the proofs largely combine ideas that can already be found in the literature (which is, of course, completely fine).

**Quality.**  Overall, the paper is reasonably thorough and well put together, which I appreciate.  However, here are a few questions / issues that would be nice to see fixed, in any final version of the paper:

* It seems that if allowing the $Y_t$, $t=1,\ldots,T$ to live in a metric space is an important part of the overall contribution, then it would be good to have additional experiments along those lines, e.g., with say strings / text data (?).  (I know you did experiments with graphs, and that is definitely a sensible starting point.)
* You could/should also report/study type 1 error, in your simulations.  That is, of course, an important part of the evaluation of any method.
* How much does setting $\rho^* = 1/3$ in Section 5 matter?
* What if one does not know the value of the upper endpoint of the interval that contains $u$ (i.e., what if the "1" is unknown, in the display below line 48)?
* Section 1: you might want to look into + cite "trend filtering" methods here; they are very related.
* Line 339: maybe a kind of combined method makes sense here, i.e., to get the advantages of both the abrupt and gradual changepoint methods.

**Clarity.**  The paper is well written.

**Significance.**  As I mentioned above, I believe the paper certainly tackles an important (and under-investigated) problem.  It's not totally clear to me (yet) how novel the authors' contributions actually are, though.
limitations_and_societal_impact: The authors were blunt about the fact that their method is not best in all circumstances (they say their method is best suited to high-dimensional gradual change problems).  That was nice to see.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes a new kernel-based nonparametric statistic for detecting gradual changes in the offline setting. Theoretical guarantees are provided for the detection power and localization accuracy.

main_review: The contribution of the kernel-based new detection statistic is incremental and the method is mainly adapted from existing MMD-based methods. As compared with Vogt et al. (2015) where a supreme over a function class needs to be computed, this paper only needs to compute the detection statistic under a chosen kernel function. A natural limitation is that the choice of the kernel function can be very crucial for the good performance of the proposed method. And it would be interesting to provide some numerical studies on how different kernel functions may result in different detection performances.

The main contribution is theoretical characterizations of the detection power and estimation accuracy of the change-point. However, this paper does not provide explicit results regarding the tradeoff between the false alarm rate and detection/localization accuracy, which can be of more interest for change detection problems. Therefore the theoretical results seem a bit limited.

For the numerical results and especially the real data examples, the author only provides the detected change-point, which makes it a bit hard to judge the performance. Maybe it would be more convincing if the author could compare with other detection methods.

This paper mainly focus the offline change detection with only one change-point. It would be interesting to discuss possible extensions to the case with multiple change-points and to the online detection setting.

Minor issues:
Line 320: the eq(3) referred here is not an estimator used in Vogt et al. (2015).
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Paper proposed a kernel-based method to detect/localize graduate changing points in time series data. Paper claims flexibility compared to the existing methods and targeted some issues raised in the literature. Paper provides theoretical analysis and simulations / real data analysis to support the proposed method.
main_review: Paper has some strong points
- Careful analysis showing statistical guarantee of the methods and the comparison of the existing method is carefully carried out.
- The proposed method has wide range of the potential applications due to its non-parametric nature
- Author addressed the positive bias issue and proposed solutions

In general a good piece of theoretical work that could shed lights on future methodology development. Paper provided interesting angle to tackle the problem and analyse the theoretical properties. 

Some points of improvement:
- Line 56: $[x]$ is usually representing $\{1,2,\ldots,x\}$ instead of the integer part. Use $\lfloor x \rfloor$ instead on this.
- Line 111: sum of Gaussian is a Gaussian. I think you are saying sum of standard Gaussian squares.
- Thm4.10: we have convergence on the scale of 0 to 1, and this is time compressed, meaning all the time is divided by T. When T increases, is the convergence still holds true? E.g. when there is a sample on each integer time, will the following hold
$$
\rho^* - \hat{\rho} = o(1/T)
$$
This will ensure that the localization going close the place of change. At lease you don't want the  $T(\rho^* - \hat{\rho}) \to \infty$ happen, which you may be far off eventually while still converging in the 0,1 scale.
- Even if this is a non-parametric method, the kernel choice is still depending on some structure assumptions. Can we have comparison between kernel choices (e.g. inner product on $\mathbb{R}^n$ versus general Gaussian kernel) so that we can get some insights on how the kernel choice affect the output?
limitations_and_societal_impact: This is a theoretical piece of work. I don't think this question apply.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes methods for change detection and change point identification based on (kernel) nonparametric statistics. The detection problem is solved by deriving the asymptotic distribution of the nonparametric test statistics. For localization, two change point estimators are proposed. The proposed methods are evaluated on a small number of synthetic and real datasets and compared to conventional ones.
main_review: I have the following comments and suggestions:

The dependence on the eigenstructure of the kernel operator is clearly described, but from the practical viewpoint, more attention should be paid to kernel selection and kernel bandwidth selection.

The computational complexity for calculating the proposed statistics should be explicitly stated.

Possible extension to (nearly) online change point detection, and to multiple change-point detection should be mentioned.

Line 256, (i) linear change,
"\mu_1(u) = I(1/3 <= u <= 2/3) ( 3u - 3)"
This should be
"\mu_1(u) = I(1/3 <= u <= 2/3) ( 3u - 1)"


--- After reading the authors' response
I read the author's reply and it basically resolved my questions. I understand it is not straightforward to extend the method to online/multiple CP detection. My questions are relatively minor or something which should have been clearly stated from the beginning, so I keep my score unchanged after reading the author's reply.
limitations_and_societal_impact: N/A
review_title: null

Meta-review: As mentioned by the reviewers the paper tackles an exciting problem. The authors are also very knowledgeable on the topic, and the proposal sounds interesting. However, the paper requires a bit more work in order to be accepted at a top conference or journal. Here are a few suggestions for a future submission of the paper:

1. A proper and detailed comparison with the existing work seems to be required. Given that there are strong similarities between this proposal and other proposals such as MMD-Based methods and KCpA. This comparison should not happen in the authors' response and should be an important part of the paper. Also, intuitive explanations on why the authors think their proposal outperforms existing statistics could be a nice addition to the paper. Providing tables that compare different proposals in terms of computational complexity, ease of calculating asymptotic distribution, accuracy, ... can be a useful addition to the paper as well. 

2. Please provide a fair and convincing set of simulations by exploring the choice of the kernel and the impact of the bandwidth of the kernel on both the authors' proposal and KCpA. 

Hope the authors find the reviews helpful. 

Decision: Accept (Poster)