Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper studies the change point detection problem. The classical studies in change detection problems are based on the known prior and posterior parameters, i.e., knowing the distribution (parameters) before and after the change points. Recently, people are extending the results to the case where the prior parameter is known and the posterior parameter is unknown (anomaly detection) or with some sampling cost constraints (data-efficient change detection). However, this work proposes an algorithm that generalizes the CUSUM approach to the case where the parameters are unknown. The idea is very interesting and I believe the impact of the algorithm could be of significance given its potential in real-world applications. Besides, I have the following comments.

1) The paper title is for multi-rask problems. However, it seems to me that the proposed algorithm is very general for change detection problem. Except the one subsection in the experiments, I didn't see much connection to multi-task problems.

2) The theoretical results are not very strong. There is no Theorem one can claim for the performance of the proposed algorithm. As the algorithm is an approximation to some optimal approach, one may provide a result in the form of competitive ratio or convergence rate. However, Lemma 3 is only some asymptotic behavior of the loglikelihood.

3) How should one choose the hyperparameters like c and epsilon? Are the results in section 5 tuned by grid search and presented the best one?


review_title: Interesting idea, not very strong results

final_score: rating: 7: Good paper, accept
review_content: *****  Paper's Summary  *****

This paper considers the quickest change detection (QCD) problem where pre-change and post-change distributions are unknown. For such problems, the authors proposed approximate algorithms in MIN-MAX and Bayesian settings. The algorithms run in O(1) and have near-optimal performances. The performance of proposed algorithms is verified using synthetic data and a reinforcement learning environment.


***** Paper's Strengths *****

The proposed algorithms are the approximate methods that have a near-optimal performance for QCD problems with unknown pre-change and post-change distributions. 

The proposed algorithms are scalable and having low detection delays. Further, these algorithms work for a more general class of problems as they do not require restrictive conditions like IID samples, specific distributions, etc. on the problems.

The performance of proposed algorithms is better than existing algorithms. 


***** Paper's Weaknesses ***** 

The proposed algorithms solve an optimization problem (depending on the setting) for minimizing the delay in change point detection. As no deep learning models (or even a variant) is used to solve the change point detection problem considered in the paper, this paper seems to be outside of the ICLR scope.

I find it very difficult to understand the paper in even 2-3 read. The authors need to improve overall writing quality so that it becomes easier to read and understand. 


***** Comments ***** 

Some notations are not defined upfront e.g., Line 2 on Page 3: $S_n^{\theta_0, \theta_1}$ and $B_\alpha$. 


*****  Questions for the Authors  *****

Please comments on how your paper fits the ICLR scope. 


*****   Post Rebuttal  *****

Thank you for your clarifications! After reading the rebuttal and comments of other reviewers, I am increasing my score.  
review_title: Paper is marginally below acceptance threshold

final_score: rating: 7: Good paper, accept
review_content: The author(s) propose a quickest change detection technique under known parameter scenario. They use a Markovian dynamics to generate the pre and post change-point distributions and use a Shirayev test-statistic based on the asymptotic behavior of the optimal delay under know parameters. The proposed methodology is validated on synthetic data and a multitask reinforcement learning example. There are several issues which restricts the paper to reach an optimal level. These are highlighted below

-Heavy dependence on Tartakovsky and Veeravalli (2005) results with known parameters. The contribution in the current paper seems a bit incremental.

-The algorithm 1 looks promising however some of the hyper parameter choices such as c, $B_\alpha$, $\epsilon$ and $N_e$ are not clear.

-For a practitioner which one is better to choose- Shirayev test-statistic or Cusum?

-It was not quite clear to me why does one need both annealing and penalisation? I thought adjusting underestimation/overestimation of ${L_t}^*$ will be sufficient as behavior of pre-changepoint will complement the behavior post change-point.

-Does other choice of entropy based loss functions matter instead of KL divergence or KL divergence is the most natural choice here?

-
review_title: A relevant topic but the paper falls short of acceptance level

final_score: rating: 7: Good paper, accept
review_content: This paper studies the quickest change detection for Markovian data, when both the parameters of pre- and post-change distributions are unknown. The main contribution is a scalable algorithm that sequentially estimates the unknown parameters and plug-in to classical detection schemes to get the stopping rule. A notable feature is that this is a joint estimation and detection framework. And the authors incorporate several tools, like SGD, annealing, penalization, into the detection task, which turns out to have good performance compared with existing benchmarks. 

Overall, this paper is clearly-written and well-organized, and the numerical examples support the claims made in the paper. 

Minor comments: 
1. Usually in classical change-point detection literature, people assume the pre-change distribution is known since it can be estimated from historical (nominal) data, and the framework proposed in this paper can obviously be applied in such a setting as well. Therefore, I think it might be interesting to add one comparison in such setting (i.e., only post-change parameters is unknown and need to estimated). In such a case, the GLR and adaptive methods do not need to learn theta_0 offline and we can have a fair comparison of the performance of learning post-change parameters and also the detection delay. 

2. In Appendix A.1, the introduction to SHIRYAEV Algorithm, it seems that there is a missing \rho in the denominator of the statistics S. The reason is that only under this \rho-scaled version of likelihood-ratio can the recursion in A.1 holds. 

--------- After rebuttal ---------
Thanks to the authors for the response and updated paper. I keep my original score and recommend acceptance for this paper.
review_title: Recommendation to Accept

Meta-review: The paper treats a relevant and challenging problem in sequential learning scenarios -- how to detect distributional change over time when the pre- and post-change distributions are not known up to certainty. All reviewers more or less acknowledge that the paper presents a new approach towards solving this inference problem, where the high level idea is to approximately learn the pre- and post-change distribution parameters online using gradient descent and then apply well-known tests for change detection (e.g., the Shiryaev or CUSUM rules) with these assumed to be the pre- and post-change parameters.

However, beyond the concerns expressed by the reviewers, my finding after going through the manuscript myself is that the presentation of the paper's results leaves a lot to be desired in terms of clarity of exposition, comprehensiveness of performance benchmarking and comparison to existing approaches. Despite some of the reviwers' scores being revised upwards, the overall evaluation of the paper according to me is not adequate to merit acceptance, as per the concerns listed below. 

1. There are two settings assumed in the paper (beginning of Sec. 2): (a) a completely Bayesian one, with the pre- and post-change distributional parameters drawn from a prior \cal{F} and the change time lambda drawn from a prior pi, and (b) a minmax one, where everything is the same as in (a) except that there is no prior over the change time lambda. However, it is not at all clear, in the algorithm design of the paper, where the prior \cal{F} over the distributions is used in computing (or approximating) conditional probabilities such as P[lambda | v_alpha = n].

2. There seem to be meaningless (or ill-defined) expressions in the paper's crucial portion motivating the algorithm design, such as P(X_t ~ f_{theta_0} | v_alpha = n), P(X_t ~ f_{theta_1} | v_alpha = n). It is hard to understand what the event "X_t ~ f_{theta_0}" even means -- I find it impossible to relate it to a sample path property. This leads me to question the validity of the technical development in the paper.

3. Another undefined term is "r-quickly" in eq. (4); I had to dig through the classical work of Lai, and Tartakovsky-Veeravalli to get a formal definition for this term. This is not to be expected of a paper that attempts to develop a new change point detection procedure from scratch, especially to an audience (ICLR) that may largely be unfamiliar with classicalt change detection theory. 

4. There are several technical statements made without adequate formal proof, e.g., "Given the optimal stopping time \nu, it's possible to evaluate the posterior distribution of the change point P(lambda=t | v_alpha=n), which in turn is a good classifier of the pre and post change observation". What the precise meaning of the term "classifier" is, what its "goodness" is, and how exactly it is related to the posterior distribution of lambda given the value of v_alpha, is formally not spelt out for a paper that largely uses formal probability language to develop its main results.

5. While I understand that the final algorithm to detect the change involves several approximations and heuristics along the way, which may very well be intuitively appealing, I do not understand (even after repeated passes over the submission) several key aspects -- a concern also expressed by Reviewer 3. Why is it reasonable to assume that the conditional distribution of the change time lambda given the algorithm's stop time v_alpha would be logistic, and with the specific parameters mu and s given in the section "Distribution Approximation"? Moreover, it is hard to discern from the crucial Section 3.2 why the functions f_0^n, f_1^n should be useful in practice as proxies to the actual expected log likelihood ratios under the true parameters -- despite Lemma 2 showing that they converge to the true expectations (again, the sense in which this convergence occurs is omitted leading to imprecision in the statement), the rates as a function of n, t_2 may be slow. I agree in this regard with the same concern voiced by Reviewer 1, and do not see a satisfactory explanation to it in the paper's discussion.

6. Comparison to literature. Contrary to the general picture painted in the paper about the lack of sufficient investigation of the "unknown pre and post change parameter" case, there does seem to be a rigorous body of work existing in this line that is not discussed in the manuscript. For instance, "SEQUENTIAL CHANGE-POINT DETECTION WHEN THE PRE- AND POST-CHANGE PARAMETERS ARE UNKNOWN", Lai and Xing, 2009, and "A BAYESIAN APPROACH TO SEQUENTIAL SURVEILLANCE IN EXPONENTIAL FAMILIES", Lai-Liu-Xing, 2009, are both works that address this very setting and in a comprehensive manner with theoretical guarantees. What the current manuscript does, in the context of both these works, is highly unclear. Is it trying to suggest an approximate way of computing the natural posterior distribution of the change time lambda given all data up to now, using the proxy P(lambda | v_alpha = n), or using a completely different approach altogether, is not adequately discussed at all, which makes the motivating arguments for the algorithm vague.

7. Finally, but in no lesser measure, the Experimental Results section features a rather narrow set of (two) scenarios for which it presents numerics. For a paper that claims to demonstrate "experimental results (over a wide variety of settings)" [from the author response], this is quite telling as it renders the argument in favor of the paper's approach quite weak. Here again, for the first (synthetic) setting, I do not understand the relevance of the neural network adopted to fix the parameters of a Gaussian distribution. Moreover, the reported distributions of the "regretted detection delay" seem to be quite wide for all the approaches compared (unknown params, adaptive, GLR), precluding a reasonable comparison of their performance. The author(s) would do well to expand the scope of both synthetic and non-synthetic experiments to show the validity of their approach, and in each case carry out many more independent trials than just 500 for more accurate benchmarks.

I do note that more experimental results have been reported in the appendix, but I would presume that they have more value being in the main body after the algorithm design is explained in a more succinct and clearer manner. This can only come about by a significant rewriting and reorganizing of the paper, which I am confident the author(s) can carry out in order to make this into a much stronger submission. I wish the author(s) good luck on this, and hope to see the strengths of this new approach brought out in a more impactful manner in the next revision.

Decision: Reject