Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents a multivariate singular spectrum analysis to perform change point detection. A spatio-temporal model is introduced to model the dynamics and CUSUM statistic was used to perform online change point detection. The experiment results showed the effectiveness of the proposed method.
main_review: Strengths:
* This paper is well organized.
* Change point detection is an interesting problem to investigate.
* Both theoretical and empirical justifications are provided for the proposed technique.

Weaknesses:
* It is not clear how the derived upper bounds are helpful for practical CPD.
* More discussions about the results are necessary.

Overall, the proposed multivariate singular spectrum analysis is innovative and technically sound. The following are a few questions:

It is not clear how the derived theoretical performance guarantee is related to performance improvement. Further explanations and discussions are necessary.

In Table 1, it is not clear why performance improvement is limited on Yahoo but very significant on Occupancy, Mixed, and Frequency.

Why is the variance of the proposed mSSA relatively large on several datasets in Table 2 and Table 3?

What’s the length of those time series datasets?

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The article presents a change point detection (CPD) method for multivariate data. The proposed methodology operates by monitoring the space generated by segments of the data and then assesses how this space varies. A sound theoretical treatment and convincing experiments are reported as well. 

main_review: The paper is dense in notation and definitions that are needed to present the contribution, however, the authors present them in a very clear manner. Among the positive points of this work I would like to mention the fact that the proposed method is nonparametric, meaning that no model is imposed to the data, and also online, meaning that CPD is performed as observations arrive by evaluating the CUSUM statistic. The proposed method is multivariate and exploits across-channel relationships, a necessary feature for real-world applications. The ideas presented in the paper are also supported on a theoretical analysis, a discussion on the optimal hyperparameters and two sets of experiments. 

I have the following criticisms

- The proposed method is for discrete-time observations, in the spirit of classical digital-signal processing techniques. This is undesirable for real-world scenarios for which the observations are asynchronous or there are (regions of) missing data. I know this paper targets another particular setting, but I suggest the authors refer to that case. 

- The noise model, and the randomness, associated to the approach may be overly simple. Recently, there has been Gaussian process based CPD methods, which despite having several drawbacks are very capable in modelling complex trajectories. This proposed method, however, only considers a fixed structure with iid noise, which might be unable to detect changes in the form of, e.g., the distribution of the noise or the covariance of successive values of f_0(t). 

- As the proposed method focuses on monitoring the distance of new points wrt the span of the previous data, how would the method behave for a nonstationary signal which changes very gradually and there is no changepoint per se but rather a continuous model evolution.


particular comments: 

l111: denotes -> denote
l191: why is that choice for L recommended? Please elaborate
Table2:Summery -> Summary


limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the online change-point detection for multivariate time series and proposes a new cusum-like detection statistic based on singular spectrum analysis. Theoretical approximations for the ARL and EDD are provided. This paper also validates the performance of the proposed method using a variety of synthetic and real data sets.
main_review: The main contribution of this paper is the proposed detection statistic for online change detection, together with theoretical analysis on two major performance metrics: the average run length when there is no change, and the average detection delay. 
The basic idea in this paper is to first use historical data to estimate the nominal subspace of the Page matrix, then under the assumption that the change will affect the corresponding subspace, the change can be detected by monitoring the deviation of the sequential observations with respect to the nominal subspace. 

The construction of the detection statistic is only of incremental contribution since the deviation of the observation with a referenced subspace has been used in previous literature for change detection, and the construction and properties of the Page matrix are also known. However, this paper also provides a complete theoretical analysis on ARL_0 and ARL_1 which matches with classical results for iid data, and these theoretical results seem to be relatively new.

This paper may still be improved in the following directions. 
First, it would be interesting to list some key constants (those C's) in Theorem 4.2 and Theorem 4.1 -- then we may obtain a more clear relationship between ARL_1 and ARL_0 and compare with the theoretical lower bound (the optimal detection performance).
Second, in the numerical results, the author spent a lot of space comparing the F1 score for different algorithms. Since this is an online algorithm, maybe the detection delay (and the trade-off between ARL_0 and ARL_1 as shown in Figure 3) would be more interesting to present. For example, instead of showing the trade-off curves for different N values, it would be more interesting to compare the trade-off curves for different algorithms.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies change-point detection in time-series using a combination multi-variate singular spectrum analysis (SSA) and CUSUM.   While multi-variate SSA and CUSUM are established techniques, the contribution of the paper is to (a) analyze the online CPD setting with a dependent (non-iid) timeseries. (b) Conduct rigorous analysis of the tradeoff of detection delay vs. false-alarm within the MSSA model.  (c) The exact version of MSSA is a bit different from the classical one. 
main_review: The papers takes a fresh look at applying classical techniques MSSA and CUSUM to change-point detection.   While the combination of SSA and CUSUM has already been proposed for CPD (as cited in ref [30], Moskvina and Zhigljavsky, 2003),  and MSSA itself has been proposed a decade ago (e.g. 2013 -- also Zhigljavsky et al) -- the main contribution of this paper is a formal theoretical analysis, and a detailed numerical evaluation. 

The paper is mostly clearly written (some caveats below), and I believe the style of analysis (using concentration inequalities, and the distribution of subspace angles and matrix singular values) is a contribution to the SSA / CPD literature.  I would prefer the paper to be more upfront about what's new and what has been done before, and novelty:  in the appendix there's a good description of the existing literature, and the contribution that this paper makes.  I'd suggest moving a few sentences into the main paper.  The main paper itself is a bit cryptic and lacks references (e.g.  ref for early MSSA would be good). 

I'm not clear that the evaluation is as strong as it could be -- how were the baselines chosen?  Is using the norm of multivariate time-series and furnishing to univariate CPD a good baseline?  Can you maybe run univariate CPD on each time-series  and do some sort of a voting -- that may have more of a chance at detecting richer classes of changes? Other than that, experiments seem to have been done thoughtfully. 

The setting in the introduction could be made clearer (it's clear by the end of the paper -- but confusing at the start):  
1) You mention f0 and f1 on page 2.   Are you detecting a change from f0 to f1 when both are known,  or do you only know f0, and declare a change when you're sufficiently far from f0?  
2) Page 3 -- let H(t) -- be the random variable equal to the accepted hypothesis at time t.   This is too informal -- you're not 'accepting' a hypothesis H0 vs H1 -- but trying to reject H0?   
3) The description of detecting slow-moving changes vs.  abrupt changes can be made clearer as well.  It seems that the shift-downward constant is related to the baseline slow-moving rate of change. Can you make this clear. 
4) What is a 'valid' CUSUM detection score?  Is it bad to have an 'invalid' score? What does it mean?
5) I was happy to see that in addition to bounds on ARL0 and ARL1, the paper analyzes when these are not vacuous. Also happy to see various suggested heuristics choices for various parameters. Sign of practical mindset. 
6) Why did you chose the particular 4 methods?  Are these representative of state-of-the-art?   Picking the norm of multivariate time-series and using univariate CPD methods seems like a rather suboptimal approach. 
7) The tradeoff of ARL0 vs ARL1 changes dramatically w.r.t number of time-series.  Is the subspace distance as a function of N somhow normalized?  It sounds like higher dimensional problems are simply much easier 
(subspace angle after the change is much larger in higher dimensions). 

Additional comments: 
[1] Minor:  notation Gamma^alpha -- this is just a constant, but suggests some power law w.r.t. alpha.  same for Gamma^w. 
[2] You use [1] as the ref for MSSA -- how is it different from earlier MSSAs that you describe in appendix? (add a comment + ref in main paper)  . 
[3] Property 2.2. The language makes it confusing as to whether it's an assumption or implication. 
[4] For finite sums of harmonics, low-degree polys, and exp-functions Page matrix is low-rank.  Comment on rank vs. num terms?  In general for your data-sets in the experimental section, what rank did you end up choosing (for default / best params)? 


limitations_and_societal_impact: I'm not aware of societal impact of this work.
review_title: null

Meta-review: 
The paper studies sequential change-point detection using a combination multi-variate singular spectrum analysis (SSA) and CUSUM.  The paper presents a novel analysis of the online CPD setting with a dependent (non-i.i.d.) sequence and characterizing the tradeoff of detection delay vs. false-alarm. Extensive numerical results validate the performance of the algorithm. 
Decision: Accept (Poster)