Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper studies a problem of detections and localizations of changes using the discrepancies between the Nadaraya-Watson estimator on data before and after a time. The paper develops the methods from scalar output cases to a general settings of outputs using kernel techniques.
To detect and localize the changes in data, a statistical test is proposed.

strengths_and_weaknesses: Strengths:
- The paper is well-written in general. It states the problem clearly, giving solutions for simple tasks then the genel ones.
- The experiment results look interesting and promising. For example, in real world data, the method can detect change points which agree with actual events.

Weakness:
- Lack of discussion or emphasis on the transition from task I to task II. Specifically, it would be better to give an explanation as to why Kolmogorov’s entropy is involved. It might be technical but will provide a sense of directions for readers
- Missing some references of CP detection with Bayesian approaches. I believe the covariate shift would be related to this line of research, especially there is work using kernel maximum mean discrepancy to tackle the covariate shift problems that resembles the approach in this paper.

Reference:
Gretton et al. 2008. Covariate Shift by Kernel Mean Matching. In Dataset Shift in Machine Learning.

questions: - Let’s consider a case $t=1$, obviously ${\hat{f}}(t, \cdot)$ (\hat{f}{-}, sorry Latex does not work here) is a not-so-good estimator because it uses one data point. On the other hand $\hat{f}_{+}(t, \cdot)$ can be a reasonable estimation as it uses $n-1$ data points.  I think the statistical test should rely on presumably perfect estimators. It seems like $\tilde{\Delta}_t$ may not reflect well on the statistical test when there is a big difference in the number of left-side and right-side data. Of course, the variance $c_2(x)/[\rho (1-\rho)]$ can describe this. Do you have any results showing that the method can perform well when $\rho^*$ close $0$  or $1$ (i.e. $0.1$ or $0.9$)? 

- As stated in Remark C.2, I wonder how to pick $c_2(x)$ in practice? It can greatly affect p-values.

limitations:
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper addresses the problem of detecting abrupt changes in the conditional distribution of two (multivariate) random variables, using a finite time indexed data sample. The presented proposal entirely builds on a non-parametric approach. The presented approach is theoretically studied and some consistency results are provided. An empirical validation is also presented with both synthetic and real data sets. 

strengths_and_weaknesses: Strengths:
- The presented approach is quite general and its implementation is simple. It does not assume the existence of a likelihood model, in opposition to many previous proposals. 

- Authors provide a non straightforward theoretical analysis of the consistency of the presented approach. 

- The presented methodology applies to multidimensional problems, which is a problem not widely addressed in the existing literature. 

Weaknesses:
- Some parts of the approach are not derived using well-defined principles. For example, at the beginning of Page 6: “we suggest setting” the tilde delta variable according to some equation whose rationale is not discussed and it is hard to understand. 

- All the theoretical results established in this work are based on complex technical assumptions which are hard to interpret and, in many cases, impossible to verify. 

- A central issue in this kind of problems is “how big” should be the “abrupt change” to be possible for the proposed method to detect it from a finite data sample. This is not explicitly addressed in this work. 

- The computational complexity of the approach makes it impractical for many real-life applications. 

questions: Could you please provide the reasons for the equation defining tilda delta at the beginning of page 6? 

How realistic are the assumptions supporting your theoretical analysis? 

Is Theorem 5.1 of relevance in the context of finite data sets? 

limitations: Mostly yes. The only issue is the set of assumptions made for the theoretical results. See my question about.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper discusses a nonparametric change-point estimation methodology for change-point detection in paired sequence of observations. The author(s) propose a methodology based on kernel smoothing estimator to detect change-point in conditional expectation. Further, they generalized the methodology to change-point detection in conditional distribution via a novel kernel estimator. The asymptotic properties of the estimator has been derived. The synthetic results and real data analysis validate the performance of the proposed estimator.
strengths_and_weaknesses: strengths

(A) A novel change-point detection technique for paired sequence of observations
(B) Smart use of NW eatimator for change in mean detection
(C) novel theoretical results discussing the asymptotic properties of the proposed kernel change-point estimator for change detection in conditional distribution

weaknesses
(A) It wasn't clear in both algorithm 1 and 2 how one should make the choice of h_X or h_Y?
(B) permutation/bootstrap procedure for p-value computation could be computationally quite expensive
(C) standardized version of \hat{Delta}_t is quite close to the CUSUM type statistic applied in change point detection. Some discussion would have been useful there.
questions: Following are my queries for the author(s)
(A) In proposition 1 we require $\Delta\neq 0$, is it possible to have an asymptotic requirement i.e. as sample size n goes to infinity $\Delta$ remain bounded above zero
(B) Are we allowed to have discrete covariates x's in the settings author(s) proposed?
(C) How is the empirical power calculated in the experiments in section 6?
limitations: Yes they adequately addressed the limitations and potential negative societal impact of their work
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper presents a novel approach to detecting change points in conditional distributions, in particular for a setting relevant in machine learning where covariates are drawn iid from a fixed distribution, but the relation to the label changes. The idea is to derive a sequence of differences in conditional distribution, standardize this sequence, and perform a hypothesis test whether a change point exists for the maximum difference in an interval and report his point. For detecting a change in the conditional expectation, the difference of conditional expectation before and after this point is estimated using the kernel-based Nadaraya-Watson estimator. In order to estimate differences in conditional distributions, the paper proposes to generalize the estimator to take into account all pairwise similarities of labels (measured by a suitable kernel). The paper then proves correctness for their approach. The method is empirically evaluated on synthetic data and two real-world use cases.

The paper is sound, the presentation is clear, the method is novel and interesting, and well placed within the literature. I vote for acceptance.
strengths_and_weaknesses: Strengths:
- tackles a problem relevant to the NeurIPS community
- novel and sound method
- solid theoretical analysis

Weakness:
- the real-world use-cases are a bit limited. 
questions: - regarding the UK Stock experiment: there seems to be a second changepoint coinciding with the Brexit vote announcement in February, 2016. Does your method detect this as well?
limitations: The method is currently used to detect a single change point in a time series. It would be great to empirically evaluate whether it can also be used to detect multiple change points (e.g., by a windowing approach), in particular on real-world use cases, e.g., detecting stock market bubbles in stock prices. It would also be great to see whether the method is able to detect less abrubt changes in practice (e.g., by shifting the mean gradually in a short time interval from the initial distribution to the final one).
review_title: null

Meta-review: metareview: This manuscript enjoyed universal recommendation of acceptance from the reviewers after the initial review phase. The reviewers did note several minor issues in these initial reviews, many of which were resolved by insightful responses from the authors. I encourage the authors to edit the manuscript to reflect the insights gained from this interaction when preparing an updated version.
confidence: Certain
Decision: Accept