Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper the authors provide the definition of a coreset for time series clustering for entities generated from a gaussian mixture model and then build a coreset for the same problem.  The coreset is independent of both the number of entities N and the the number of Time stamps T_i for each entity i. They demonstarte the accuracy and efficiency of their coreset by superior empirical perfromance over synthetic data as compared to uniform sampling.
main_review: In this paper the authors provide coreset for time series data generated from GMM with autocorrelations.

Significance: 
 Clustering time series data has become an important problem in ML due to huge amounts of data available over time. For scalabiltiy of clustering, coresets provide a very good option. From this view point this is an interesting and important paper. The theoretical results will be insightful to the coreset community in particular and the overall results are interesting for the ML community in general.

Originality: 
To the best of my knowledge, this is the first paper on coreset for time series data in the unsupervised setting. The defintion of coreset provided by the authors for GMM time series clustering is different from traditional coreset in sense that along with a tuple of entity and time stamp it has two weight functions : one for the entity other for time. 
Though the paper borrows heavily from existing coreset literature for e.g: 1)Feldman Langberg framework for constructing coresets, 2)the idea of introducing f' for the GMM clustering from [23][25] 3)the assumptions from [52,42,35,34] etc. ; I believe the application of these ideas to the setting of time series clustering for e.g bounding the sensitivities, pseudodimension etc. is non trivial. Overall I believe the paper has reasonable novelty.


Quality and  Clarity:
I have not checked the proofs in detail however the proofs look alright. 
However I think the writing specifically the mathematical writing can be improved. There are a lot of variables and symbols used in the paper. It would be useful if some convention is followed for writing these variables. For e.g. vectors in small bold letters, matrices in capital bold letters, scalars in small letters etc. In current state it becomes very difficult while reading and one has to go to and fro to check if a given variable is vector, scalar etc.
I think there are minor typos at the following places: On line 183 eq. 2 should it not be f'(alpha(theta), theta) and not just alpha as a parameter.?
What is P on line 174?
What is tau in the input of algorithm 1 as subscripst of S?

The experiments show very positive results however they are only for synthetic data

Overall I feel this paper has merits that outweigh the flaws and is a good candidate for publication.



limitations_and_societal_impact: The authors have mentioned their restriction to the GMM with autocorrelation as generative model for the time series data as a limitation. 
However the main issue I have is that the experiments are only performed on synthetic data. It would be good if we can have some experiments with real datasets.
Also the only baseline used is uniform sampling. My question is, since the authors address the first part of coreset building procedure as a k-means clustering problem, is it also possible to atleast sample points in the frst part using some existing k-means coreset building procedure and compare with that?

I do not see any major negative societal potential impact of this work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper uses the Feldman Langberg sensitivity framework to compute coresets for time series clustering under a Gaussian Mixture Model.

This imposes additional challenges since there is an instance domain as well as a time domain to approximate. The mixture model introduces covariances and to reflect the time dependence there is an additional autocorrelation introduced on the time domain.

Those covariance and correlation structures are being bounded in order to bound their impact on the sensitivities and after getting rid of all those structures the problem is reduced to a simpler clustering model for which sensitivity bounds are obtained more easily. 

The resulting coresets are assessed empirically on synthetic data.

The writing is very good and the main body provides all information to understand even on a technical level, although the details are in the appendix.

In principle I would tend to accept this paper but knowing the previous literature on GMM as well as a recent coreset work on "panel data" my main impression is that the submission is just a dejavu of those two works.
main_review: My main concern for rejecting this paper is a lack of novelty and significance:

1) The model (with the assumptions imposed to get small coresets) seems inappropriate: When the covariance matrices have constantly bounded condition and the autocorrelation AR(1) is used, then every time series is just a random walk concentrated around their mean. This is very well behaved time series data.

Why is there no comparison or related work for maybe more appropriate time series (polygonal curve) clustering eg under dynamic time-warping or Frechet distance, and where values can oscillate arbitrarily. See for example the recent series of works by K. Buchin or A. Driemel or D. Rhode.

2) Technically there is not more than already seen in the papers [23] where coresets for GMMs (with bounded condition) are developed. Why is the more recent generalization without this bound [25] being dismissed? I would rather deal with more general covariances but loose the log n factor.

The submission uses the same techniques as [34] for getting rid of the autocorrelations (of order q, here only q=1 is considered). It is simply by assuming that the correlation is bounded away from 1 and by applying Cauchy-Schwarz. In [34] the two-stage coreset construction for clustering of regressions was one of the novelties but here it is just the same again.

The authors try to sell it as new or different by pointing out the two weighting functions w(i) and w_i(j) which due to non-linearities can't be combined, but in principle it was the same in [34] up to finally defining w(i,j) = w(i) * w_i(j).

another thing that they point out that the component's cost functions are not bounded as in [34] but the bound on the eigenvalues is just the same, noting that the eigenvalues are dominating the costs in the GMM.

3) Even on synthetic data the coresets show only slight improvements over uniform sampling. Since the authors are free to model the data in any way, they could at least simulate one data set that is particularly hard for uniform sampling where coresets show their strength. Currently it looks like if data follows the generating model, sensitivities are pretty uniform. Also, why is there no real-world data comparison? Is there even any real data that can be modeled similarly to the GMM model described here?
limitations_and_societal_impact: no
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper suggests a coreset construction algorithm for a clustering time-series data.

main_review: In this paper, a coreset construction algorithm was provided for clustering time-series data, specifically speaking GMMs.
The coreset was achieved via reduction towards the $k$-means clustering problem. 

In addition, I find it interesting that the paper suggests two different weight functions, one for the entities and one for the time periods whereas for traditional coresets, there is only one weight function that handles the only entities.

I enjoyed reading the paper, however, due to time constraints, I was not able to go over the proofs of the presented theorems.

Comments:
- Line 141, $\Delta_k$ instead of $\Delta^k$.
- $e_{it}$ is not a scalar based on its definition at Line 150. Did you mean to write $e_{it} \in \mathbb{R}^{d}$?
- Why didn't you apply your coreset on real-world panel data? 
- The coreset size depends heavily on the dimension of the data. See the limitation section for elaborated improvements.



limitations_and_societal_impact: 
The authors have addressed the limitations of the paper properly. 
Specifically speaking, the coreset construction algorithm is performed well under a mild boundedness assumption on the covariance matrices of the underlying Gaussians. 

The coreset size on the other hand depends polynomially on the dimension of the instances, i.e., the exponent is $16$. Thus in such cases, when dealing with big data where $d \in \Theta{M}$ or even $d \in \Theta{M^{1/16}}$, then the coreset basically contains $M$ points where $M$ denotes the total number of instances in the dataset. 

Please provide a small discussion regarding the lower bound on the coreset size which is needed for GMMs on time-series data, i.e., "how hard the problem is from a coreset point of view?"
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers the problem of clustering time series data. The authors provide a coreset for this problem, under some assumptions. The coreset size depends polynomially on the number of clusters k, the dimension d, and 1/\varepsilon and the parameters related to the assumption on the data, and requires near-linear time to compute. 
The authors validate their coreset empirically on synthetic data, as compared to a uniform random sample. They show that the coreset: (i) achieves better results can the random sample, and (i) can help accelerate the computational time, relative to the full data, by 1-2 orders of magnitude, with only a small compromise in the accuracy.
main_review: Pros:
- The problem is indeed very interesting and relevant.
- The paper is well organized. 
- The overviews provided are very helpful, as well as the detailed comparison of Theorem 4.3 to the related previous works.
- In overall, I really like the paper and its results.

Cons:
- The contributions paragraph is very high-level, and lacks the important details (e.g., coreset size, actual computation time, etc.).
- The coreset obtains an additive error of epsilon times f', where f' is a different cost function. This relation should be investigated more thoroughly, both in theory and in the conducted experiments.
- While the analysis and proofs are indeed deep and non-trivial, the novelty of the results is not fully clear; It is unclear if this is the first coreset for such time-series data, and unclear whether existing works, which handle the same cost function but with static data, can be easily adapted to the case of time series data. This concern arises since, eventually, the provided coreset for time series data is basically a union between a coreset for entity level data (ignoring the time-series data for each entity), and a separate coreset for each entity. Hence, one might think that the novelty of the paper lies mostly in the successful decoupling of the time-series problem into two sub-problems with static data. I would recommend that the authors add a "hardness" paragraph that discusses this topic.
- The hardness of computing a coreset for time series clustering is not discussed. Is there a provable lower bound for the coreset size? This can better justify the coreset sizes obtained in the paper.
- The problem seems, in some sense, related to the problem of clustering input sets, or clustering shapes, as e.g., 
(i) “Sets Clustering”, Jubran et al.
(ii) "k-Means Clustering of Lines for Big Data", Merom and Feldman.
(iii) Works that handle probabilistic databases (for example "Smallest enclosing ball for probabilistic data" by Munteanu et al.
Establishing a connection to those problems seems very relevant.
- Regarding the experiments: 
(i) how was the optimization problem solved on the full data? was it done similarly to the EM solution applied on the coreset?
(ii) It seems a bit strange that the the proposed coreset achieves a 2x-8x acceleration in solving Problem 3.1 compared to the uniform sampling, as the random sample is computed much faster, and is of the same size as the corese. Can the authors elaborate on this?
(iii) The dimension d tested was only d=2 (probably due to the large dependency, in theory, on d).
However, as the theory in most coreset papers is far too pessimistic, it would be interesting to see this effect in practice for d>2. 


Other detailed comments:
- There are some typos / writing issues / undefined variables. For example: 
(i) In the definition of the input set X, the subscript of the first element x_{i1} of every Xi does not have a comma, while the last element x_{i,Ti} does have a comma. It should be consistent. Also, Xi is said to be a subset of R^{Ti x d}. However, as Xi is not a set, the "\subset" should be replaced with "\in", and it should be R^{d\times Ti} as there are Ti columns and d rows in Xi.
(ii) The argmax in Line 37: it is unclear over what set are we maximizing the expression.
(iii) Line 38: missing closing bracket.
(iv) Line 80: "where objective" -> "where the objective".
(v) Line 91: "compared to uniform", sentence not complete.
(vi) Line 174: If i'm not missing anything, then P is undefined (should be P_X). Similarly in Definition 3.3.
(vii) Line 182: Extra closing bracket.
- The organization of the column titles in Table 1 are very confusing. I would recommend either spacing the titles more, or placing some vertical dividers in between unrelated columns.
- An illustration figure to demonstrate the "GMM clustering with time series data" problem (even for d=2) would be very appreciated.

I am willing to re-evaluate my score after addressing the above concerns.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose a novel coreset construction framework for the problem of clustering multivariate time series. To my knowledge, this is the first construction of coresets in this setting. The framework, as well as the proof scheme, is close to the work in [45], in which Lucic et al. studied the problem of coreset constructions for the MLE task under the GMM model. 

Here, the authors add to the GMM model a temporality and thus an additional autocorrelation in the underlying model. The proof's scheme is similar to that of [45] in the sense that they also reduce the GMM time series clustering problem to a $k$-means clustering problem (and then use more classical results for $k$-means from the state-of-the-art).
main_review: The additional temporal dimension compared to GMMs makes the coreset algorithm and the proofs of the theorems more involved. Given the information provided in the proof sketches (I did not read the supplementary material), I did not find any error in the reasoning or computation; but I could not guarantee that there are no errors.

The idea of first sampling entities, and then a subset of time periods for each selected entities is quite natural. The way I see it, the first stage of the algorithm is very close to the work in [45], with a k-means++ based routine to estimate upper bounds of the k-means' sensitivity. Then, the second part of the algorithm (selecting time periods for each sampled entity) is close to the work in [34]. This work is a mix of ideas from [45] and [34].

I am frustrated by the experimental section in which you only compare your work with uniform sampling. 
- What if you keep all entities but sample only time? What if you keep all time periods but sample only entities? 
- What if you forget the time in your time series and directly apply the algorithm from [45]? What gain do you truly get with your approach?
limitations_and_societal_impact: NA
review_title: null

Meta-review: 
The paper suggests a coreset for clustering in the context of signals.
Indeed, there are too few coresets in this very active area.
There were concern regarding experimental results and novelty that the authors should address in the final version.
In addition, there are few coresets for signals that the authors should cite in the final version:

https://papers.nips.cc/paper/5581-coresets-for-k-segmentation-of-streaming-data
https://dl.acm.org/doi/abs/10.1145/2814569

Decision: Accept (Spotlight)