Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies the problem of clustering samples generated from multiple Gaussian mixtures with possibly non-identical and non-isotropic covariance matrices. The authors start with a mixed integer program (MIP) take the standard semidefinite program (SDP) relaxation approach. They first consider an oracle model, in which the covariances are known. For this oracle model the paper provides the sample complexity bound for exact recovery using SDP. Next the authors propose an iterative algorithm, which updates the estimated covariances and solves the new SDPs iteratively. Some real-world experiments are provided as well.
strength_and_weaknesses: - The MIP - SDP relaxation is very standard (see e.g. [1]).

- The authors highlight multiple times in the paper, that the technical novelty comes from extending the isotropic Gaussian covariances, to a more general setting where there is no such uniform and identical assumption. To me this sounds technically incremental, because the whole SDP framework stays the same, and it only requires some changes about the concentration inequalities. But I think this could also due to writing. Could the authors elaborate on this? Specifically, what are the technical novelties in the oracle LA-SDP analysis?

- Do the authors know whether the SDP relaxation is tight or not? More specifically, if the sample complexity condition in Theorem 2 is violated, are we immediately in a regime such that exact recovery is guaranteed to fail with large probability (information-theoretic lower bound)? Or we have something statistically possible but cannot be solved efficiently by any algorithm (computational lower bound)?  

- Theorem 2: Can the authors provide some example settings, in which the sample complexity condition is fulfilled or not fulfilled? In other words, how should we interpret the sample complexity requirement?

- Is there any convergence rate guarantee on the iterative algorithm iLA-SDP, or is it purely heuristical? It is known that solving a single SDP is very time consuming (O(n^6) if I remember correctly), not to mention solving SDPs iteratively.

- Experiments: Do these datasets follow the rate condition in Theorem 2, or they only serve to show the effectiveness of the proposed algorithm in practice?



References:
- [1] Amini, Arash A., and Elizaveta Levina. "On semidefinite relaxations for the block model." The Annals of Statistics 46.1 (2018): 149-179.
clarity,_quality,_novelty_and_reproducibility: The writing is clear and easy to follow for most parts. Since this is mainly a theoretic work, it will be great if the authors could highlight their technical contributions, which seem unclear / lacking in the current shape.
summary_of_the_review: In the rebuttal it will be great if the authors could highlight their technical contributions, which seem unclear / lacking in the current shape.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper extends an SDP relaxation for k-means clustering (Gaussian mixture modeling) from isotropic clusters (with identical scaled identity covariances) to non-isotropic clusters, where each cluster can have its own covariance matrix.  When these cluster covariances are unknown (which is most often the case) the paper proposes an iterative EM-like algorithm which alternates between covariance estimation with known cluster-labels, and SDP-relaxed model-based clustering with known covariances.  Limited simulations show improvements w.r.t. k-means, EM and hierarchical clustering.
strength_and_weaknesses: Strengths:  The paper proposes an interesting SDP relaxation for model-based clustering with known covariance matrices, and extends the information theoretic analysis from the isotropic case.  In the usual case where within-cluster covariances are now known,  the paper proposes an iterative approach which alternates between covariance estimation with known clusters, and SDP-relaxad covariance estimation with known covariances.  The approach is limited to small data (timing and computational complexity is not discussed in the paper, but SDP is very expensive and the largest simulation has 1000 data-points) -- but perhaps there could be critical small-data problems where any gains in clustering quality could be worth the computational cost.  The appendix mentions that it may be possible to extend the method to large data (larger dimensions, and more samples) -- but it's unclear how valuable/practical that is -- and it uses standard ideas like sub-sampling. 

Weaknesses:
1) Computational complexity or timing is not discussed in the paper (which should definitely be addressed) -- and it's likely very high.  The authors mention SDP solvers to be O(N^3.5), and the relevant dimension N seems to be n*K  where n is data-points and K is the number of clusters. So it's useful at best for very small scale problems. When covariances are unknown -- the method is iterative, solving many such SDPs, and no information is provided of how many iterations are typically needed until progress slows down. It's worth reporting the timing of the proposed method and contrast with standard k-mean + k-means++ / EM -- to know the price to pay for the clustering accuracy improvements.  

2) In the common case of unknown covariances -- the method appears more akin to EM, which the authors aim to avoid in the first place.  (There's discussion of why it still may be better than EM -- but it's not very convincing -- definitely the elegance of one-shot SDP is lost). Convergence or rates are no longer guaranteed. Also in practice the method uses a lot of other clustering methods (sometimes HC is used for initialization, and spectral-clustering and k-means are used for post-processing non-integral partitioning solutions) -- so it seems quite sensitive to initialization.  So while it's discussed as a clean one-step SDP relaxation -- in practice it's quite complex and uses various heuristics. 

3) Experiments do show an improvement -- but they are on the weaker side, and important details are not provided.  Did you use k-means++ initialization for k-means, and something like that for EM?  What is the computational cost of your method w.r.t. alternatives?  If k-means runs say 1000 times faster -- you could probably use this budget for random restarts, some more accurate heuristic initialization schemes -- how would it compare then?  Other common clustering methods (e.g. spectral clustering are not evaluated), even though they're used in post-processing of SDP solutions.  In figure 4 -- the bulk of the box-plot for LA-SDP is in-line with other methods,  but it has a small set of outliers which do better -- this seems an artifact of this specific problem, and perhaps better initialization for k-means could find these configurations. Ideally more than 2 datasets would be used.  Mis-clustering error is not defined in the body of the paper.  Also some discussion in the short experimental section is confusing. You subsample clusters to keep them 'balanced' -- but there's a discussion of 'highly unbalanced'...  
3-a) "Perturbation percentage of initaliation" is not defined. 
3-b) Also why do you need graphical Lasso when you have 4 attributes?  Plain sample covariance should work very well even with relatively few samples that you have. 

4) Insufficient scholarship.  It's unclear where exactly the SDP k-means method was proposed -- the main citation is from 2021, but it seems to have a much longer history, including other earlier paper analyzing its performance, and many relevant references are missing. If there are many qualitatively different SDP relaxations -- then they should be mentioned and contrasted, otherwise key papers introducing and analyzing the method should also be mentioned.  Or does your paper propose a new isotropic SDP? 
* Iguchi, Takayuki, et al. "On the tightness of an SDP relaxation of k-means.", 2015. 
* Moses Charikar, Rachel Ward, Awasthi, Pranjal, et al. "Relax, no need to round: Integrality of clustering formulations." Proc. Conference on Innovations in Theoretical Computer Science. 2015.

5) The paper claims that profiling out the cluster-centers (i.e. not keeping them explicit) is a major advantage.  It's a key step in the SDP formulation, but once you have a (soft) cluster assignment -- cluster centers are trivially computed, why is it so important?

 6) Term "profiled-out" commonly used in the paper is never defined -- setting nuisance parameters to their maximum-likelihood values (rather than being integrated out).  












clarity,_quality,_novelty_and_reproducibility: The paper is generally well written.  The extension of the SDP-relaxation to the model-based clustering case seems novel.  Scholarship is a bit on the weaker side, and important references are missing.    The paper is mostly of theoretical interest, as the method seems very expensive compared to competition.  Experiments are on the weaker side, and it's unclear if the competition k-means, EM e.t.c. were given all the standard options (e.g. k-means++ init,  or random restarts) to reach their potential -- given that they're significantly cheaper. 
summary_of_the_review: Interesting extension of SDP clustering and its analysis to the model-based clustering setting with non-isotropic covariances.  The proposal is likely only of theoretical interest, as the computational cost is very high.  Also in the practical setting of unknown covariances the method looses its convex-relaxation elegance, and starts looking more like EM that it tries to replace, requiring various heuristics.  Scholarship, and experiments need improvement.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper extends an SDP approach for Gaussian mixture models clustering by introducing cluster labels as model parameters.
strength_and_weaknesses: Strength
======

- The paper is well written, except for the references/citation style. It's really hard to find the papers that you cited in the main manuscript in the References section as citations are done with last name, e.g., (Balakrishnan et al 2017) but in the Reference section they start with the author's first name, e.g., "Sivaraman Balakrishnan, Martin J. Wainwright..."
- The idea of optimizing cluster labels, while not novel (see, e.g., "Discrete Optimal Graph Clustering" by
Yudong Han et al), is interesting.

Weaknesses
=========

- Experiments with real data are very limited and do not consider classical methods for clustering such as Spectral Clustering.

Minor comments
=============

- This sentence: "Another popular clustering method is the classic expectation-maximization (EM) algorithm" does not make sense. EM is not a clustering method. EM is an iterative algorithm for finding local minima of (generally) maximum likelihood problems.
clarity,_quality,_novelty_and_reproducibility: The paper reads well and clear, however, novelty is limited and so is reproducibility as the authors have not shared code for the experiments.
summary_of_the_review: The idea of the paper is interesting, but the lack of experimental results with popular and successful clustering methods diminishes the paper's overall contribution to the community.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes an SDP applied for clustering in a heterogeneous data setting. As reviewers mentioned, there are many such SDP ideas in the literature so the novelty was found to be somewhat limited. There are a number of good ideas behind the approach as mentioned by some reviewers, but unfortunately many issues remained that did not sufficiently convince any reviewers to vote for acceptance. In particular, there is some agreement that the empirical aspects may be the weakest part of this paper, and should be worked on in preparing for a stronger future submission.
justification_for_why_not_higher_score: There are no positive votes for acceptance, and though the author response is appreciated, the work would benefit from further review after substantial revisions 
justification_for_why_not_lower_score: na
Decision: Reject