Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proves exact and approximate recovery guarantees for the generalized $k$-means problem under some (natural) assumptions on the data points. These guarantees hold for any constant factor approximation algorithms for the problem and their results are valid not only for the case when $k$ is correctly specified, but also when $k$ is over estimated, which make their results more relevant for practical applications.
main_review: The paper is well written, clear, and interesting to read. The "refinement" idea they introduce for studying label consistency in the overfitted case is very natural and quite interesting. I am surprised it hasn't been studied in any prior work. The generalized $k$-means problem studied by the paper encompasses the classic $k$-means and $k$-median problems, which are obviously of interest to members of the NeurIPS community.  Most prior work has focused on the value achieved by the optimization function but in practice, what is more relevant is the recovery error i.e. how close are the labels assigned to the true labels, which is studied in this paper.
limitations_and_societal_impact: As mentioned by the authors, the work is mainly theoretical in nature and does not have any potential negative societal impact.

In page 2, just below part (b) of the assumption, it is stated that reference [2], which is $k$-means++ achieves constant approximation. But $k$-means++ is an $O(\log k)$ approximation algorithm. Please correct this. There are (of course) several other constant factor approximation algorithms which you can choose to cite. I would also suggest looking at the paper "Clustering under Approximation Stability" by Balcan, Blum, and Gupta (JACM 2013). They also study the recovery error for k-means and k-medians problems and I think it is quite related to your work. There has also been some prior work on overfitted clustering, which you study in the paper, for instance: Wei (NIPS 2016) and Makarychev, Reddy, Shan (NeurIPS 2020).

Some minor typos: In the line just above definition 1, misclassification is misspelled as "misclassiciation". Towards the end of the second paragraph of section 3.3, "in the in the Supplementary Material".
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers the problem of recovering (sub)clusters with respect to the k-means objective, assuming that the centers satisfy certain separations. Specifically, the authors show that when running an algorithm with more than k centers, the subclusters are consistent with the target k-clustering.
main_review: I think that the authors raise an interesting question. While recovering a target clustering $C_k$ may be hard for a given value of k, recovering a clustering $C_L$ with $L>k$ centers such that the target clustering $C_k$ could be recovered from $C_L$ is an interesting way of modeling data compression in an (exact) recovery setting in a way that, for example, coresets would not be able to.

I initially misunderstood what the author's assumptions were. Now it is clearer that their separation results are related to (but slightly stronger than) distribution stability introduced by Awasthi Blum and Sheffet in FOCS 2010. Showing certain recovery notions under these assumptions has been studied in Cohen-Addad Schwiegelshohn (FOCS 2017) and for the related notion of spectral separability introduced by Kumar Kannan (FOCS 2010) and Awasthi Sheffet (APPROX 2012), but I believe that the results here are not obviously weaker than what is achieved in those reference and the idea of recovering a solution with more centers has certainly not been studied in the aforementioned resutls.

Now that I also understood the lower bound (and the assumptions), I also think that the example given by the authors where their algorithm provides a separation is a compelling one. Overall, after the rebuttal my impression is a lot more positive and I believe the paper could be accepted.
limitations_and_societal_impact: Not necessary for this submission.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers the problem of label recovery from data clustering. Generally speaking, these two tasks are unrelated: the label recovery is a supervised learning problem, where each data point has a unknonwn true label, and the goal is to infer the label for each data point; while the clustering problem is to group data together to minimize the generalized $k$-means cost (i.e., replace $\ell_2$-error with $\ell_p$-error in traditional $k$-means), which usually has nothing to do with labelings. Although the former task also induces a clustering (in which data points with the same label belongs to the same cluster), it can be a very bad solution for the later task, and vice versa. To distinguish, for a given data set, we say a clustering is a **true clustering** if it recovers the unknown labeling (up to permutations); while we say it is an **optimal $k$-means clustering** if it solves the second task, i.e., minimizes the generalized $k$-means cost function.

The paper shows that, when the *true clustering* satisfy certain regularity conditions, it can be recovered (up to "refinement") by (an $O(1)$ approximation to) the \emph{optimal $k$-means clustering}. The paper defines a **refinement** of labeling $z\in[K]^n$ to be another labeling $\tilde{z}\in[L]^n$ together with a mapping $\omega:[L]\mapsto[K]$, such that $\omega(\tilde{z}_i)=z_i$ for all $i\in[n]$. Intuitively one can think of this as breaking the *true clusters* further into multiple smaller clusters.

Per my understanding the main result can be summarized as follows. When the true clustering is itself a good clustering with respect to the generalized $K$-means cost (Theorem 1 and 2), or if the true clustering can be broken into $L>K$ smaller clusters which have small $L$-means cost (Theorem 3), then an $O(1)$-approximation for the optimal $L$-means clustering is also a good approximation for the true clustering, in the sense that it approximately induces a refinement of the true labeling. 
main_review: **[Strength]**
The paper proposes an interesting metric of classification error in the overfitted case, which seems to be the first to do so (I'm not familiar with literatures on this particular problem, though). The paper also gave rigorous analysis on the conditions when a refinement can be recovered. I like the applications given in section 3: The paper shows that when the true clustering is induced by some smooth manifold, a not-to-large $L=O(\sqrt{n\log n})$ is sufficient to recover a refinement of the true labeling.  

**[Weakness]**
I don't have time to check the proofs in detail, but the main result is intuitively unsurprising: the regularity condition is essentially assuming that the labeling induces a clustering that's good w.r.t. the $k$-means cost. Furthermore, the authors also assume the true clusters (or its refinement) are well-separated. With such assumptions it's really not surprising that a good $k$-means clustering also approximates the true clustering well. Furthermore, I'm wondering what's the dependence of $L$ in all the bounds obtained: when $L=n$ it trivially recover a refinement of the true labeling, even if the well-separation condition does not hold. It would be good to show that we don't need too large $L$ to achieve small labeling error. (I'm not sure if it's possible though, maybe it requires stronger assumptions). Besides, in practice the separation parameter $\delta$ is usually unknown and untrollable, while $L$ is something we can specify. So I believe it's better to at least have some experiment on realworld data sets showing the effect of $L$.

--------
# Acknowledgement of author response [Sep 2]
-------
I have read the author response and am satisfied with it. But I do think the authors should revise the paper in their post-rebuttal version: (1) Clarify the difference between the two clustering tasks involved: one is inferring the labels, and the other is minimizing certain cost function. (2) Discuss the relation between their assumption with the "distribution stability" mentioned by Reviewer wtkZ.

Overall, I have a positive feeling on their submission, and this has not changed after seeing their rebuttal, thus I'm increasing my score to 7. But I have to admit that I'm not familiar with the techniques or the literatures, so I don't have very high confidence in my score.


limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the problem of label consistency in the generalized k-means problem in an overfit situation where the number of clusters $L$ used by a given clustering algorithm is more than the ground truth $K$.

The main contributions are:

1. Theoretical guarantees the above problem, under certain assumptions on the clustering algorithm, for both  exact and approximate label recovery. To the best of my knowledge, this is the first result in the context of the k-means problem.

2. The results are model-free, but strongly depend on the maximum or average distance of the points to true cluster center.


main_review: I found the paper decently written. The introduction is comprehensive, the setup and the learning problem are clear. I read all the proofs in the main body of the paper and the supplementary material, and everything looks correct and standard. 

I have a few comments/questions (in a random order).

1.  Assumption 1: 

a. In Assumption (1b) is it clear that both $K$ and $L$ can be associated with the same \kappa? Obviously $\kappa$ can be taken to be the maximum between those approximation constants.

b. You are claiming that some of your results hold with assumption (1b') which you claim ( in page 4) to be a relaxation. As far as I could follow, Theorems 1 and 2, in fact, are proved using Assumption (1a) and (1b'), and so in the statements of Theorem 1 and 2, I do not understand why you are referring to Assumption 1? Then, right before Subsection 2.2 you are mentioning that you can relax part (b) of Assumption 1. This is a bit confusing. More importantly, I do not understand in what sense (1b') is a relaxation of (1b). It seems as though that neither conditions follow from each other. For example, if we assume that (1b) holds, why this implies that (1b') is satisfied as well? Vice-versa, if (1b') holds, while it might seem that (1b) should hold, it does not becasue you won't be able to obtain the right hand side guarantee for the constant approximation for $L$. Am I missing something?

c. It would be much more clear if you provide a complete statement of Lemmas 1-3, mentioning which assumptions are needed? For example, in Lemma 1 you use Assumption (1b'), in Lemma 2 you use Assumptions (1a) and (1b'), etc.

2. Necessary conditions:  while the sufficient condition in Theorems 1 and 2 are nice, it is difficult to appreciate those results since it is not clear at this point whether whatever you obtained is anything close to what is necessary. What is the difficulty with deriving lower bounds (even simple/loose ones)? 

3. Can you point out "typical" values of the parameters such as $\eta$, $\delta$, $epsilon$, etc.? If those are fixed, then fine, but what if those parameters depend on $K$ and $n$? For example, if $\delta$ is relatively small with n, then your bounds are sometimes not informative. 

4. The sentence following equation 4 is vague. Can you add more details on how the Theorem shows whatever is written there?

5.  You are mentioning that condition (4) can be relaxed from "+4" to "+2". Unless I am missing something, this seems like a negligible improvement, and I do not see the point of mentioning this. 

6. In Theorem 2, if $\epsilon$ is large enough then you can get to zero misclassification error using Theorem 1. Therefore, you can at least have a slightly better bound there. 

7. The motivation, result, and the sentence following (7), surrounding Theorem 3 are not clear and vague. It would be great if you could clarify some of the details there. 

8. You mention a few times in the paper that you proofs are non-trivial. I think that these statements should be removed.

9. In Theorem 2 you say "Then, for any c > 2". What is the benefit of have this $c$, and not just using $c=2$. This is the only condition that is needed for the proof, and this is the "best" value for $c$ both in terms of the misclassification error and the separation condition.  

10. In some sense, the theorems statements seems incomplete in the sense that it is not clear what happens when the margin condition is reversed, namely, can you say something meaningful to what happens when $0<\delta<...$.

Conclusion:

While I do believe that the setup and the questions asked in this paper are interesting and important I find the theoretical results quite weak. Currently the paper presents some "upper bounds" which are difficult to appreciate due to luck of some kind of "lower bounds" to compare with. The dependency of Theorem 1 and 2 on the various parameters is quite strong and it is not clear at all whether this dependency is inherent. Furthermore, in terms of technical contribution, I found the proofs quite straightforward (certainly not non-trivial). Therefore, I my current recommendation is 5.

Typos:

8. In the proof of Theorem 1 it should be $+4\eta$ and not $+4\epsilon$.

9. When you bound the cardinality of $S_k$ in the proof of Theorem 2 it should be a strict inequality $<1$. 

10. "We now extend Theorem 3" should be "We now extend Theorem 2".

11. "Have properties in Assumption 1"  should be "Have the properties in Assumption 1".

12. "value the cost function" should be "value of the cost function"..
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: This paper shows that in certain settings, overparameterized k-means can recovery a refinement of the true clusters even when recovering the true clusters themselves is impossible. The reviewers agree that this is a novel observation that broadens the applicability of k-means and our understanding of when performance guarantees can be obtained. The paper is also timely and adds to the recent literature on overspecified models. 

The reviewers also point out several weaknesses of this work:
- The assumptions, in particular the separation condition, appear strong. While the authors promise to add a lower bound in their response, the lower bound does not reflect dependence on the dimension. 
- The conclusion seems unsurprising under their assumptions, and the analysis involves standard techniques.

The paper can be made stronger by incorporating several suggestions from the reviewers, including
- Adding a lower bound.
- Clarifying the difference between the two clustering tasks involved.
- Discussion of the relation between their assumption with "distribution stability" (mentioned by Reviewer wtkZ), as well as with the assumptions made in prior work on Gaussian mixture models.

Decision: Accept (Poster)