Label consistency in overfitted generalized $k$-means
Authors: Linfan Zhang
Arash A Amini
Venue: NeurIPS 2021 Poster (2021)
Keywords: clustering
k-means
label consistency
manifold clustering
overfitting

Abstract: We provide theoretical guarantees for label consistency in generalized $k$-means problems, with an emphasis on the overfitted case where the number of clusters used by the algorithm is more than the ground truth. We provide conditions under which the estimated labels are close to a refinement of the true cluster labels. We consider both exact and approximate recovery of the labels. Our results hold for any constant-factor approximation to the $k$-means problem. The results are also model-free and only based on bounds on the maximum or average distance of the data points to the true cluster centers. These centers themselves are loosely defined and can be taken to be any set of points for which the aforementioned distances can be controlled. We show the usefulness of the results with applications to some manifold clustering problems.

Label consistency in overfitted generalized k-mmans
Linfan Zhang
Arash A. Amini Department of Statistics University of California, Los Angeles Los Angeles, CA 90095 aaamini @uclu. edu
Department of Statistics University of California, Los Angeles
Los Angeles, CA 90095 linf www.a..claa..oa.aaaaaooa.aa.aaaa ucla edu
Abstract
We provide theoretical guarantees for label consistency in generalized k-means problems, with an emphasis on the overfitted case where the number of clusters used by the algorithm is more than the ground truth. We provide conditions under which the estimated labels are close to a refinement of the true cluster labels. We consider both exact and approximate recovery of the labels. Our results hold for approximation to the k-means problem. The results are also
any constant- model-free and only based bounds the maximum average distance of the data points to the true cluster centers. These centers themselves are loosely defined and can be taken be any set of points for which the aforementioned distances can be controlled. We show the usefulness of the results with applications to some manifold clustering problems.
Introduction
Consider the problem of clustering data points sampled according to some probability measure from normed space X' with norm ||x. In the ideal setting, the generalized k-means clustering minimizes the population cost function
Q(E:u) = ( min
|| (ell)dd((z)) 1/P
(1)
ISESL
where & = (fi...., (1) E X is a set of L vectors in X, for some fixed integer L. In practical data analysis, we are given a sample f.1...., vn drawn from μ and solve an empirical version of (I). namely,
1/P
@(E) = Q(::P,)) =
min SSL
|x
Eellxx)
(2)
Here, Pn, :- , sz; is the empirical measure associated with the sample and 8, is the point mass measure at x. The minimizer of Q(-) over X is denoted as f (EI,...,EL) and each point x; is assigned a cluster label E; := argmin, |:: - Eellæ-
Meanwhile. we assume that each data point 2; also has a true cluster label 2; [K] := (1...., K} which is determined solely by an unknown lata-generating process. These true labels are not necessarily related the optimal solutions of (I) (2). To distinguish the two, we refer to the clustering induced by (z,) as the true clustering, while a clustering that minimizes the generalized k-means cost function (2). i.e., the clustering induced by (2,), is referred to an optimal k-means clustering. In this paper, we consider the label consistency problem, that is, how close the labels (2;) estimated by k-means clustering are the true labels (z:). Note that we allow the number of k-means clusters L to be different from the true number of clusters K.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In the above formulation, the case where p= 2, X' RR and ||- IIx is the Euclidean norm leads to the classical and widely used k-means problem. Much of the theoretical analysis of h-means has been performed in this case. Early work has focused on how close the optimization problems based on the empirical and ideal cost functions 2 and [] are to each other, where the closeness is measured in terms of the recovered centers (i.e., 5 and () or the optimal value of the objective function.
Such consistency results are proved, for the global minimizers of ( in the early work of [2 [29] and also in 30 from the vector quantization perspective. These classical results do not directly apply to the performance of the k-means in practice, mainly because solving (2) is hard and approximation methods are usually applied to deal with it. Also, considcrations of the label consistency problem are absent from this line of work since no true clustering. external to the k-means problem, is assumed to exist.
More recently, there has been more interest in the consistency of practical k-means algorithms 14 as well as the label consistency problem. Lu and Zhou [21] obtain sharp bounds on the label consis- tency of the Lloyd's algorithm 200 under sub- Gaussian mixture model. Semidefinite programming (SDP) relaxation is another popular technique for deriving polynomial-time approximations to the k-means problem (88) Its label consistency has been studied when data is generated from the stochas-
tie ball model 10,, , sub-Gaussian mixtures [25] g 91. the Stochastic Block Model (SBM) [9]
and general models [18]. Convex clustering is another relaxation method whose label consistency has been discussed in [34 (7 II 31]. The literature on community detection in SBM, a network clustering problem, is also mainly focused on label consistency and inspires
work here; see
33 for a review of those results. For label consistency in kernel spectral clustering, see [2].
In this paper, we study the label consistency of approximate solutions of the generalized k-means problem 2 when L 2 K. Our focus will be on the overfitted case where L > K. This is often relevant in practice since the data-generating process may have natural number of clusters K that is unknown a priori. An example the sub-Gaussian mixture with K components. More interesting examples are given in Section 3] All the aforementioned works on label consistency exclusively consider the correctly-fitted case I. = K. We show that when the data-generating process admits a set of centers that satisfy certain separation conditions, estimated labels with L > K clusters, are close to a refinement of the true labels. These bounds reduce to the label consistency criteria for L = K, but have no counterpart in the literature for L > K.
where it is shown to improve the approximation factor Overfitting in k-means is considered in 32 23
(see Assumption [ b)) of certain polynomial time k-means algorithms. Analysis of the approximation factor concerned with how close one can get to the optimal value of the k-means objective function. In contrast, we are concerned with the label recovering problem and not directly concerned with how well the objective function approximated. Our work also aligned with the recent trend of beyond worst case analysis of the NP-hard problems G where the performance of the algorithms are considered assuming that there are some meaningful structures in the data (c.g., true clusters). We refer to Remark D for more detailed comparison with this literature.
Our results are algorithm free in the sense that they apply to any algorithm that achieves a constant- factor approximation to the optimal objective. They are also model-free in the sense that we do not make any explicit assumption on the data- generatnn process. This important in practice, since many common data models, such as Gabb-aassian mixtures, are often too simplified to capture real clustering problems. We provide examples of more complicated data models Section 3 and show how our general results can provide new insights for these models. Since k- k-means clustering often appears as building block in many sophisticated clustering algorithms, we believe our results will be of broad interest in understanding the performance of clustering algorithms in overfitted settings.
Notation. Q(E: 14) is only dependent on the of values among the coordinates of E. Although we view E as a vector (for which the order of elements matter), with some abuse of notation, we view ((::p) as a set function (mapping 2xx R) that is only sensitive to the set of values represented by ç. This justifies using the the same symbol for the function irrespective of the number of coordinates of c. i... the number of clusters. The reason to keep & as an (ordered) vector is to make the cluster labels well-defined. For simplicity, let || || = x|. For the case where X C Rd,, one often takes ||-|| || to be the Euclidean norm, but our results are valid for any norm on Rdd and more broadly any normed space X.
2

---

We also the (optimal) matching distances between elements of two vectors viewed sets. Definition 2. For & E X and 5" * define the too and Ep optimal matching distances as 2 Main Results
We first state assumptions about the k-means clustering algorithm.
Assumption 1. Consider an algorithm for the generalized k-means problem 2 referred to as ALG(p) hereafter, and let ELL)) X and ((K) XK be its estimated centers when applied with L and K clusters, respectively. Let L 2 K. Assume that ALG(p) has the following properties, for all imput sequences (I:):
(a) Efficiency: The Voronoi cell of every estimated center 2 contains at least one of (æi).
(b) k-approximation: (((1K)) S K. min (E), and similarly with K replaced by L.
Efficiency can be achieved by substituting centers whose Voronoi cells have an empty intersection with {aa). by those having the opposite property. For k-approximation, the factor y can depend on the number of clusters K (or L). For example, the k-means++ algorithm has K Ollog K), with high probability over the initialization [3]. However, there are also constant-facee approximation algorithms for k-means where x = ((1) independent of K (or L) [24 with local search, k-means++ can achieve constant-factor approximation 16 In addition, ξ-
15 For example,
approximation is not required for all inputs. That is, we are not concerned with the worst-case approximation factor. The in Assumption [[b) is the approximation factor of the algorithm on the specific data under consideration. enough for an algorithm to achieve good approximation only on the data of interest.
For some of the results, Assumption Tb) can be replaced with the following modified version: (b)) k-approximation only for clusters plus a mononoticity assumption: Q(E(4) < ((3())). Mononoticity is also reasonable requirement and obviously true for the exact k-means solutions.
Next, we extend the definition of the misclassification rate the overfitted case. Definition 1. The (generalized) misclassification rate between two label vectors [K] and E [L]", with S L, is
Miss(z, 2) min Σ i=1
11 + w(:)),
where the minimization ranges over all surjective maps w [L] + [K].
When L K, surjective map is necessarily bijection and the above becomes the usual definition of misclassification rate when the number of clusters is correctly identified. In this case, Miss(2, 2) 0 means that there one-to-one correspondence between the estimated and true clusters. The generalized definition above allows us to extend this notion of exact recovery to the case L > K. In particular, Miss( z, 8) = 0 when L K, if and only if is refinement of z. To see this, note that Miss(z, 2, ?) 0 implies the existence of map w [4] + [K] such that w(2)) = for all This in turn is equivalent to: 2, 2r = 2; = 2y', which is the refinement relation for the associated clusters. In general, Miss(2, 2, 2) is small if 2 is close to refinement of 2.
K
(K) <21I²) 1/2
doc = min max [|(o(k) Ekll, dp(S.E")= min 1<k5
where o: [K] + [L] ranges over all injective maps.
For K dx is an upper bound on the Hausdorff distance between the sets. Obviously, we have doo < dp for any 1.
2.1 Distance to true centers
Let (2) [K]* be given set of true labels for the data points (zx) In addition, our results are stated in terms of a set of vectors Ç* ((
K which refer to as the "true centers".

---

Throughout, e* will be only vaguely specified. The only requirement on 5* is that together with the observed data points (xx) and the true labels (z:), they satisfy the deviation bounds in each theorem,
e.g., max <isa ||=; $z. S vn in Theorem 1 etc. Let 75. = >i=1 1 1( = k) /n be the proportion
of observed data points true cluster and let Tiin = ming TT-
We let f be a solution of the k-means algorithm with - K centers and let 2, E argmin, || Edll be the corresponding estimated labels. Our first result provides guarantees for exact label recovery, in the extended sense of recovering a refinement of the true partition when K and the exact partition when I. K.
Theorem 1 (Exact recovery). Consider a vector (true) centers 5* E X and labels (zi) E [K] Pick 7, 8, such that maxigisn ||: E,
S 1}, and
min 11E2 (R. Negh
-2 2 8. Neghtt
Consider algorithm ALG(p) for problem satisfying Assumption ! and let (2:) E [L]" and
Č XL be the estimated labels and centers of ALG(p) applied with the L 2 K. Then,
5
> 2
+
+
Miss(2, 2) 0. dx(E,5t)
(1 + K)M
(4)
7
1/p
"min
1/p
When L = K, the assertion Miss = means that there is permutation a on [K] such that o (2,) = 2; for all that is, we have the exact recovery of labels (=:) in the classical sense. When L K, Theorem guarantees the exact recovery of a refinement of the true labels (z:).
Example (Stochastic Ball Model). Assume that data are generated from the stochastic ball model considered in [26]. where 2; = -r,, with sampled independently from a distribution supported on the unit ball in Rd Here, {4x k=1 C Rd are fixed set of centers. Clearly, we take ? 1 in Theorem I Then, any k-approximate k-means algorithm achieves exact recovery when ò > + 2(1 + x)) Timi for L K. In the overfitted case, when ò 4 2(1 + k)/ / /Tmin the estimated label vector is an exact refinement of the true labels (zi).
In the above example, although it is intuitively clear that for sufficiently large 6, the solution of the k-means problem should achieve exact label recovery (in the extended sense), Theorem [ alllows us to provide a provable guarantee for any constant-factor approximation, with an explicit bound on the separation parameter 8.
We now turn to approximate recovery where the misclassification rate is small.
Theorem 2 (Approximate Recovery). Consider a vector of (true) centers e E x and labels (z)) E [K]". Pick e, 5 > O such that (1) E. ||,; - E |P) S, and 33 holds. Consider an algorithmm ALG for problem ( satisfying Assumption and let (24)== E [1 and & E XL be
the estimated labels and centers of ALG applied with the K. Then, for any c> 2,
(1 + K)C
Miss(z, < K(1 + K(1+))( x))c( d,((.et) S
R)) 1/p T Tin
(5)
1/p
π min
The key difference between Theorems and is the bounds assumed on the deviations Dj = ||z; - ll In). Theorem assumes a bound on the maximum distance to true centers, max, D,, while Theorem assumes a bound on an average distance, (2 Σ, 1/p,/, leading to a more relaxed condition.
Theorem 2 provides an upper bound on the misclassification rate when a certain separation condition is satisfied. To simplify, consider the case K σ 2 and take 2.1. Then, Theorem implies the following: For every B > O, there exists constant eg (3, mmin) > such that if
6/c 2 c1 Mmia),
then any 2- k-means algorithm will have Miss < B to the target labels. The next proposition shows that condition (6) is sharp up constants.
Proposition 1. There exists family of datasets ((r,, x))) with K = 2 balanced true clusters
(i.e., Amin 1/2) and parameterized by true center separation ò and (1) Σi ||
5%, 2

---

have that with with the following property: Given any constant 3 (0,1/2), there exists a constant c2( > 0, such that if 6/E C2(3), then any 2-factor k-means approximation algorithm with L clusters has misclassification rate satisfying 2 B S Miss S S. Moreover, any 2-factor k-means approximation algorithm with setting.
clusters will recover a perfect refinement of the original clusters in the above
The proof of Proposition can be found in the Supplementary Material. This proposition shows that if the separation condition 6 is reversed, one can force the performance of any k-means algorithm to be arbitrarily close to that of random guessing. The true centers in Proposition aare the natural centers implied by the k-means cost function for the true labels, that is, E 2,
x; { k} for
2. One can take e1 (33, miin) = 6.3 m1x 2/ and e2 (3) sin(tan (v 3/44))
for the constants in (6) and Proposition [
Remark 1. The separation condition (6) is related to the distribution stability introduced in (5)
Roughly speaking distribution stability plus the following property implies our condition:
(D1) For every pair of distinct clusters Cj and C3 with centers E and Ee there is point & E Ce such that || 1u--a Et s ||şa 1-
That is, every cluster Ct has points which closer than ç to the centers of other clusters. This property is quite mild and one expects it to hold with high probability if the distribution of the points have positive density w.r.t. the (fllldimeensional) Lebesgue measure in a ball around the center. The above seems to suggest that distribution stability is slightly weaker than our condition ( However, in the presence of (D1), we can also significantly relax distribution stability arrive at our condition, the details of which are provided in the Supplementary Material, In this sense, these two notions are closely related but not directly comparable, i.e., neither is weaker than the other in general.
mixtures). Let us assume that the data is generated from a K -ocomponent nub-Gaussian mixture model r, = E, + dd11/2m, where w: = (W:.,.... Wid) E RRd is zero mean sub-Gaussian noise vector with sub-Gaussian parameter os, and z; E [K] is the latent label of the ith observation. This is an extension of the sub-Gau nab-Gausiinn mixture model considered in (7]. Determining whether ( is actually the solution of the population problem (I) is, itself, challenging and the answer may depend on the exact distribution of [w,}. Nevertheless, our results allow us to treat (EZ) as the true centers. Below we sketch how Theorem 2 applies in this case. The details of the arguments, including the exact definition of a sub-Gaussian vector are provided in the Supplementary Material. Let 0 max = max; and set a² := there is numerical constant C > O such that a², < Co Then, one can show that
Example 2
wulll and a² := 1. Ei a². Assume that
1 E 11 20²) S -oinnn!/on =: Pn.
for some numerical constant C O. Taking 8² = 2n, and p 2 in Theorem 2 probability at least 1 Pri
82 (1 [1+N) x222
Miss(z, S 2K(1 + x) an 2
262
#min
where 5 is as in and 2. In general problem, Gn. max and d all can vary with In order to have label consistency for an ALG(2) algorithm, it enough to have 0,/6 = o(1) and na//o/ /o
The consistency here is based on the extended Definition and includes the overfitted case which a refinement of the true labels is consistently recovered. We note that the model in this example includes very general Gaussian mixture model as a special case, namely the case Wi ~ N [N, Σ,) where the covariance matrices Σ, E Rdxd are allowed to vary with each data point. In this case, one take maxx maxigisn [Eillop where || llop denotes the operator norm, and a² Σ tr.))/dd.
2.2 Distance to fake centers
We now extend Theorem allow for "fake" centers 2 and the corresponding labels ( These can be constructed to reduce the required distance to the data points (æ,).
5

---

Theorem 3 (Approximate Recovery, II). For aixed L 2 K, consider vector of constructed centers & E X constructed labels ă = (5.) E [L]" and true labels (zi) E [K]" Assume that ž is a refinement of 2, i.e. there is w [L] + [K] such that ((z;) = 2, for all i E [n]. Pick E, > 0
such that
b -2,11P 1/8
c;
min tr ((6) * ((ba)
15 Eea ll 2 8
Consider an algorithm p..G(p) for problem Q satisfying Assumption | and let (2:) E [T]] be
the estimated label vector of ALG(p) applied with L clusters. Then, for any 2,
6
n)C
Miss(2, 3) < K(1 + x)) (5))
(8)
1/P
7 min
The advantage of Theorem is that when the desired number of clusters L increases, the bound on the misclassification rate can go down: In some applications, by carefully constructing the fake centers E. we can make smaller as L increases, while roughly maintaining the minimum separation among fake centers associated with the true clusters. If successful, this implies that refinement of the true clustering can be achieved even when is hard to recover the true clustering itself. In the following section, we show how this strategy can be applied to some manifold clustering problems.
3 The case for overfitting
We now illustrate applications of Theorem in settings where it is hard to recover true clusters, based on the ideal K, but it is possible to obtain accurate refinements by overfitting. The idea is to consider clusters that look like submanifolds of Rd
3.1 Mixture of curves
We say that random variable has (p, σ) sub-Gaussian curve distribution if 7(1) where t IR has lub-Gaussian distribution with parameter and 7 E R is locally p-Lipschitz map. ie.. (t) - (s)]l S plt s| for all t, E IR such that |t - S /.
Proposition 2. Assume that (I;)²_1 are independent draws from a K --oomponent mixture of (p. a) sub-Gaussias curve distributions. That is, 2; =11, (ta) where 2, [K], t; ~ Qz, independently across i, each Q2 is a sub- nub-Gaussian distribution on IR with parameter a, and each 7t is locally p-Lipschitz. Let Cs be the support of the distribution of (() where t ~ Qu. Assume that
min *ECa, yECg
|| 14-wo vll 28>0, for all le + k'.
1 Then, there exist a constant C C(K, p, such that any ALG(2) satisfying Assumption applied with Ln S Coglog clusters recovers a perfect refinement of z with probability 2 -nn
The significance of this result is that one recovers perfect refinement with the number of partitions L, o(n). It is trivial to obtain a perfect refinement with L,, n. but not so with Ln/r /n - This is especially the case since one can achieve quite complex cluster configurations with the model in Proposition
2 for some of which applying k-means with clusters will have a misclassification rate bounded away from zero. Section 3.3 provides some such examples where the true cluster centers coincide, causing any k-means algorithm applied with the true K to incur a substantial error. See also Supplementary Material for discussion of whether L,, O(vn log n) can be improved.
Various extensions of Proposition are are possible. We have the following extension the noisy setting. Corollary 1. Assume that the data is given by y = x, + L W. for E [r]] where (a:) are as given in Proposition 2 and are Sab-Gaussian noise vectors as in Example 2 Then, under the same assumptions as in Proposition 2 ALG(2) applied with Ln < CV achieves misclassification rate S K (ān/ + with probability 2 1 - Pm- n where o, and pn, are defined in Example 2
Corollary I shows that one can achieve consistent clustering (in the generalized sense) with L,, o(n) clusters assuming that the noise-to-signal ratio / - and na aee//onn o -> oe; the same conditions needed in the sub-Gaussian mixture example. Again, this result is significant since even in the noiseless case (ā,, = 0), consistent recovery is not possible with I. = K for some mixtures of curve models.

---

10.5
(a) Noisy (I. = 4, =3
(b) Noisy
(c) Noiseless
Figure Line-circle model: (a) Scatter plot for the noisy version. The colors show the L = estimated clusters by k-means. (b) and (c) show the (generalized) misclassification rate versus 6, the radius of the circle, in the noisy and noiseless versions of the model.
3.2 Mixture of higher-order submanifolds
A version of Proposition 2 can be stated for higher- dimensooaaa version of the mixture-of-curee model, we consider generalized k-means problems with p We say that random variable has a (p,0, o, r) sub-Gaussian manifold distribution if x = (t) where / E R. has sub-Gaussian distribution with parameter and 7 R" + _2d is locally p-Lipschitz map. i.e., (f)(t) (s)] <
pllt s|| for all t, s R' such that ||t - =|| s.
Proposition 3. Assume that (x,)²=1 are independent draws from a K K-component mixture of sub- Gaussian manifold distributions, with parameters (p, o, rk) (,k) [K]. and let r max,e(K] Tk-
Let C2 be the support of the distribution of the kth component. Assume that
min x ECR, yEC₁
||. ||-- vll 2 2 O, for all k: + k.
Then, there exist constant C C(K, such that any AL.G(p) satisfying Assumption 7 applied with In C/n ((nn///oogn) n)" clusters recovers perfect refinement with probability 2 n- In particular, for p > T, we have perfect refinement recovery with L,, = o(n) clusters, with high probability.
is also possible to extend the results to more general distributions on submanifolds via a notion of stochastic covering numbers. For random vector with distribution Pę on submanifold C C Rd. let Ngc(e) (e) be the smallest integer for which, there is a high probability e-cover of x, that is, finite subset N c C such that P(minyEN || - yll I =) 2 1 - n We state generalization of Proposition 3 to this setting in the Supplementary Material.
3.3 Numerical experiments
We first consider the (noiseless) line-circle model in R an example of mixture-of-curves. This model has two clusters: (1) The uniform distribution on the circumference of circle in the æz-plane, centred the origin, and (2) standard Gaussian distribution on the y axis. The minimum separation between the two clusters is the radius of the circle. We also consider the noisy version of this model where we add N (0, 13). We sample data points with equal probability from the two clusters. is nearly impossible for the k-means to correctly label these two clusters when L = since the centers of the two clusters coincide. Figure shows the scatter plot of the data simulated from the noisy line-circle model, with noise level 0.1, for better illustration. Different colors are used to label data points based on the output of k-means clustering with L 4, and this demonstrates that each estimated cluster is subset of true cluster.
3000 and å = 3. Here, the noise level is set low
The result aligns with Theorem 3 Although, the true centers coincide (with the origin) when I, by increasing L,, we can create fake centers on the line and the circle to have separation close to and thus get small missclassificatiin rate. The other two panels Figure [ show the average missclassification rate over 32 repetitions versus ö, for both the noiseless and noisy (a 1) line-circle
7

---

Average Misclassifcclion Rate
Average Misclessifiiation Rale
10
10
0.4
0.3
0.0
delta
de ta
(a) Noisy
(b) Noiseless
Figure model: The (generalized) misclassification rate versus 6, the distance the
Gaussian center to the line, in the (a) noisy and (b) noiseless versions of the model.
Aveinge Miscassfficttonn Rate
Average Misclassificaoo Rate
1=10
0.2
0.1
delta
delta
(a) True clusters (noiseless)
(b) Noisy
(c) Noiseless
Figure 3: Circle-torus model: (a) Scatter plot for noiseless version. Colors are used to separate two true clusters. (b) and (c) show the (generalized) misclassification rate versus 6, the radius of the circle, the noisy and noiseless versions of the model.
model. Both show that the misclassification rate negatively associated with å and when L Similar results are shown for the circle-torus model in Figure 3 Details of this model are discussed the Supplementary Material.
Figure 2 shows the results for a One--Gussian mixture model: x, E + 13/2 w, E RR2 where S 8) and E = (0, 0), w; (0, 12), Σ, /2 and Σg diag(o", 0). Here, we have 3000 data points with equal probability from the two clusters. We also consider its noisy version by setting all the zero elements in Σg to 0.7, which makes the model general Gaussian mixture. Figure 2 shows the average missclassification rate over 32 repetitions for different L.. The results are consistent with Theorem 3 showing that as increases, the misclassification rate decreases.
set 5 and sampled
Proofs
Let us first recall a fact from functional analysis. Consider the space functions f [n] + X' and let us equip [rx] with the uniform probability measure v,. Then, from the theory of Babbesgue-Bochene spaces, [lf (f [[ II du (P defines proper norm on this function space, turning into a Banach space ()). In particular, the triangle inequality holds for this norm. Note that
Ilf = (: Ei_ l() 119, We will frequently invoke the triangle inequality (V),
Let n² == Σe Tg = Ei= dez, be the empirical measure associated with {E2, J. Recalling definition ① of the population cost function, have, for any & E 2
1 min || EelP.
Q'E:"()= =
min 1 ISSL
E
(9)
SESL
k=

---

We start with three lemmas that are proved in the Supplementary Material:
Lemma 1. Let ALG(p) be k-means algorithm satisfying Assumption [b') and let & be its outpu 1
for L clusters. Furthermore, assume (1 Eim1 ||
Ex, [1)) I s. Then Q(E: - (1 + x)e. Lemma (Curvature). For every & C X² and 5" X with L 2 K.
Q(5:)() 2 a Tmin (p (p((,5") 2)
Lemma 3. Assume that maxi || S% S n and doc (e, 5*) S 7- When I= K, ifō > 27 2n, there exists a bijective function w : [K] + [K] scatiffing w(2)) = 2i, Vi E [n]. When L > K, if 5 > 27 + 4n, there exists surjective function w [L] + [K] satisfying w(z)) Fi vi [n].
Proof Theorem 7 and 2
As ( E =1 1104- 11))// & maxisisn 1|=;- -2, s n. combining Lemmal 1
we have
(g(E,, 2) ut)
(1 + x))
1/p
1/p
min
Fmin
By the condition on 8 in we have 8/2 > (1 + /
min-
Then, (E. S Ed(E.E") y
(1 + k)n/T -ip which also makes the assumption in Lemma result follows from Lemma 3
that 6 > 27 + 4m valid. Finally, the
Proof of Theorem 2 The argument is similar to one that has appeared in recent literature 17 12 From the proof of Lemma (in the Supplementary Material), we have
Q(E:u)) S Σ I12. - GG 1/p S S + K)E.
By Lemma 2
(2>(5, ^ 2) S Q(E,r²)
(1 + R)E
1/p
1/p
F min
min
By the separation assumption in 8/2 > (1 + /
1/p Hence dp(E,5") S (1 K)E/ k)]/////ll) min Let
1/p
Cs- = (i : 24 k}. |Cxl Tkk, and set Th = {i Cs || E S 8/c). Letting Sa = Cs \ Tk. we obtain
n
|S / < Σ |1tt E,, 1 S Σ
|5 E S nn + K)PEP.
SESx
Therefore,
|Sx|
n(1 + PP
<
< 1.
Th
54.0p
The last inequality is by assumption 5 > (1 + k)CC/ / 1/p
Hence, Ta is not empty. Furthermore, we
min
argue that if i E Ta and j E Te for l # l, i.e 2, # Ej. then o, + 2z. Assume otherwise, that is, 2 Zn. Then
1S
Eill
<
1152 E + 1152 E S 28/c < 6
causing contradiction.
Let La- = (2: i E T and L = - La. Define a function w: L + [K] by setting w(t) k for all E L and k E [K]. By the property of {T&} shown above, Lx, k E [K] are disjoint and nonempty sets. This implies that is well-defined and surjective. Extend to a surjective w : [L] + [K] by arbitrarily defining it for [L] \ L. Note that 2 E Ls implies 2, = k. It follows that w22)) 2, for all 2, L, and
1
Σ 1=1
(2: + (2:))
& n C
K
S&
K(1 + PRPPPP
7
50
k=1
The result follows.

---

Proof of Theorem 3 By assumption, a-approximation holds for both K and L clusters. Then,
2 v K Tma. where Qun
== min Q(E). SE
Since Q ni Ei=
||;;-
εx 1/) Se, c, by the triangle inequality in L ())
-
IK - -G. 1/8
-
1
Σ
cل - 1x,11)) 1/8 +
1
Σ
n
||.
1/8 Ex.11))
- (1 K)E.
12 ==1
1=1
Tk = IkE.. - Ea.ll s 8/c} and S = Cs \ Tk. Then,
|S < Σ
IÉ:x - Es, 11 - ==1
1 S 1n(1+ x)Pe..
SESu
Therefore,
|
n(1 + K
T2k
The last incquality is by assumption
min Hence Ty is not empty. Next we argue that if E Tk. T/ for lo * i.e. 24 # 2j. then 2, # 2j. Assume otherwise, that is 2, 2j. Since
2 (1 + 1)CE n 1/p
2 is a refinement of 2, 2, + 2j implics 2, + Σg and (2,) # (22)). By the triangle inequality,
I6:
Ex, =
Ic..
Ea 1[s,, E || s 25/c <
causing a contradiction. The rest of the proof follows that of Theorem 2
Proof of Proposition Let my be the mean of Qu. Then, P([t, mz > t) S 2e 12 Let
M v 602 log n. By union bound, with probability 1- 2n we have It, mm,, S. M for all E [ra]. We can cover the set [-M, MM] C R. with L' = M/s I-D balls of radius E. (Without loss of generality, we assume that L'' an integer for simplicity.) Let T (TI....,TZZ . one such cover and note that my + T is an E-cover of m& + M. MI. Let n : R - (m² +T) be the projection from
onto m2 T. Then, 11,, - 7z, (T (t.))ll S plt, nz. (f:) S pe, assuming that E S 1/p.
Let 2/. == argmingre(1]] 144 - (m2, + ) so that n2, (4:) = m22 + TzT. Then let L, KL' and fix bijection o [Lm]] + [K] [L'] and define the labels ă o (zz, 24). Also consider the map wo : [K] x [L'] + [K] given by wo (k;, f¹) = and set == wi a o which is a surjective map from [Lm]] to [K] satisfying (2x) = 2g. For l E [Ln] with ((() (k, f)), define & 7h (m + Te ). Then, we have E.,- =2, (m., Tx() Yz, (T2, (t+)), hence the above argument gives ( Ez. S pe. It is also clear that the the separation condition 7 is satisfied since by construction if ((G) * ((2) with ((t)
* 12 hence E and E.2 lie on different manifolds (on Ck2 and Chy). ). It follows that conclusion (8) of 3Theoremmhhor holds for p 2 and, say, e = 3 but with 8 replaced with pe, Take & = (c1 / T1) for constant é₁ to be determined. Let C2 3p(1 + /O. As long as 7M (22/c1)², the separation condition in (8) is satisfied and we have Miss(2, 2) < K(c2/ / ) /n. Hence, as long as ei VKeg, we will have Miss(2,3) < 1/n which implies Miss(2, 2) = 0. We also need to satisfy e < 1/p that is e₁ 2 p/Vn. Taking c = VK2 + p satisfies all the required constraints on C1- The required number of clusters is
(ki, E) and 2(22) = (22 b2), then k
Ln = KL' = KM/E S 3Koc1 v logn,
which proves the result with C= 3Kac,. Note that since c2/c1 < and nin 2 1, the condition Wimi (c2/c1)² )2 is automatically satisfied. The proof is complete.
Acknowledgments and Disclosure of Funding
This work was supported by the NSF CAREER grant DMS-1945667 We thank the referees for their helpful comments that lead to the improvement of the paper.
10

---

References
[1] Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1):6446 6531,, 2017.
[2] Arash A Amini and Zahra S Razace. Concentration of kernel matrices with application kernel spectral clustering. The Annals of Statistics, 49(1):31--556 2021.
[3] David Arthur and Sergei Vassilvitskii. k-means++: The advantages of careful seeding. Technical report, Stanford, 2006.
[4] Pranjal Awasthi, Afonso S Bandeira, Moses Charikar, Ravishankar Krishnaswamy, Soledad Villar, and Rachel Ward. Relax, no need to round: Integrality of clustering formulations. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 191-200, 2015.
[5] Pranjal Awasthi, Avrim Blum, and Or Sheffet. Stability yields ptas for k-median and k-means clustering. In 2010 IEEE 51 Annual Symposium Foundations of Computer Science, pages 309-318, IEEE, 2010.
[6] Vincent Cohen-Addad and Chris Schwiegelshohn. On the local structure of stable clustering instances. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 49-60. IEEE, 2017.
[7] Noureddine EI Karoui. On information plus noise kernel random matrices. The Annals of Statistics, 38(5)3191-32166 2010.
[8] Yingjie Fei and Yudong Chen. Hidden integrality of sdp relaxations for sub-gaussian mixture models. In Conference On Learning Theory, pages 1931-1965. PMLR, 2018.
[9] Christophe Giraud and Nicolas Verzelen. Partial recovery bounds for clustering with the relaxed k-means. Mathematical Statistics and Learning. 1(3):317-374, 2019.
[10] Takayuki Iguchi, Dustin G Mixon, Jesse Peterson, and Soledad Villar. Probably certifiably correct k-means clustering. Mathematical Programming, 165(2):605-642, 2017.
[11] Tao Jiang, Stephen Vavasis. and Chen Wen Zhai Recovery of mixture of gaussians by sum-of-norms clustering. Journal of Machine Learning Research, 21(225):1-16, 2020.
[12] Jiashun Jin. Fast community detection by score. Annals of Statistics, 43(1):57-893 2015.
[13] Tapas Kanungo, David M Mount, Nathan S Netanyahu, Christine D Piatko, Ruth Silverman, and Angela Y Wu. A local search approximation algorithm for k-means clustering. Computational Geometry, 28(2-3):89 112, 2004.
[14] Mieczyslaw A Klopotek. On the consistency of k-means++ algorithm. Fundamenta Informati- cae, 172(4):3611377, 2020.
[15] Amit Kumar, Yogish Sabharwal, and Sandeep Sen. simple linear time (1+/spl epsiv/)- approximation algorithm for k-means clustering in any dimensions. In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 454 462. IEEE, 2004.
[16] Silvio Lattanzi and Christian Sohler. A better k-means++ algorithm via local search. In International Conference Machine Learning, pages 8662-3671. PMLR, 2019.
[17] Jing Lei and Alessandro Rinaldo. Consistency of spectral clustering in stochastic block models. Annals of Statistics, 43(1):215-2311 2015.
[18] Xiaodong Li, Yang Li, Shuyang Ling, Thomas Strohmer, and Ke Wei. When do birds of feather flock together? k-means, proximity, and conic programming. Mathematical Programming, 179(1):2953341 2020.
[19] Tamás Linder. Learning-theonr theoretic methods in vector quantization. Principles of nonparamet- ric learning, pages 163-210. Springer, 2002.

---

[20] Stuart Lloyd. Least squares quantization in pem. IEEE transactions on information theory, 28(2):129-133 1177 1982.
[21] Yu and Harrison Zhou. Statistical and computational guarantees of lloyd's algorithm and its variants. arXiv preprint arXiv: 1612.0209 2016.
[22] James MacQueen. Some methods for classification and analysis of multivariate observations. In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, volume 1, pages 281-297. Oakland, CA, USA, 1967.
[23] Konstantin Makarychev, Aravind Reddy, and Liren Shan. Improved guarantees for k-means++ and k-means++ parallel. Advances in Neural Information Processing Systems, 33, 2020.
[24] Jini Matoušek. On approximate geometric k-clustering. Discrete & Computational Geometry, 24(1):61-84, 2000.
[25] Dustin Mixon, Soledad Villar, and Rachel Ward. Clustering subgaussian mixtures with k-means. In 2016 IEEE Information Theory Workshop (ITW), pages 21 211-215. IEEE, 2016.
[26] Abhinav Nellore and Rachel Ward. Recovery guarantees for exemplar-based clustering. Infor- mation and Computation, 155:165-180 2015.
[27] Ashkan Panahi, Devdatt Dubhashi, Fredrik D Johansson, and Chiranjib Bhattacharyya. Cluster- ing by sum of norms: Stochastic incremental algorithm, convergence and cluster recovery. In International conference machine learning, pages 2769-2777. PMLR, 2017.
[28] Jiming Peng and Yu Wei. Approximating k-means-type clustering via semidefinite programming.
SIAM journal on optimization, 18(1):186-205, 2007.
[29] David Pollard. Strong consistency of k-means clustering. The Annals of Statistics, pages 135-140, 1981.
[30] David Pollard. Quantization and the method of k-means. IEEE Transactions on Information theory, 28(2):199-205, 1982.
[31] Defeng Sun, Kim-Chuan Toh, and Yancheng Yuan. Convex clustering: model, theoretical guarantee and efficient algorithm. Journal of Machine Learning Research, 22(9):1-32, 2021.
[32] Dennis Wei. A constant-factor bi-criteria approximation guarantee for k-means++. Advances in Neural Information Processing Systems, 29:604-612. 2016.
[33] Zhixin Zhou and Arash Amini. Analysis of spectral clustering algorithms for community detection: the general bipartite setting. The Journal of Machine Learning Research, 20(1):1774- 1820, 2019.
[34] Changbo Zhu, Huan Xu, Chenlei Leng, and Shuicheng Yan. Convex optimization procedure for clustering: Theoretical revisit. Advances in Neural Information Processing Systems, 27:1619- 1627, 2014.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section I
(c) Did you discuss any potential negative societal impacts your work? [N/A] Our work is theoretical and does not have direct societal impacts. Considering the page limit, we focused on presenting theoretical results.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
12

---

(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof' of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material URL.?? [Yes] See the supplemental material.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [N/A] We did do data training.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] Error bars included in the plots.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Computing details are in the supplemental material.
4. If you using existing assets (c.g., code, data, models) curating/releusing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material as URL? [Yes] See the supplemental material.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "slif_-BB1P8", "reviewer": "Reviewer_8yKF", "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.\n\nThe 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.\n\nPer 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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**[Strength]**\nThe 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.  \n\n**[Weakness]**\nI 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$.\n\n--------\n# Acknowledgement of author response [Sep 2]\n-------\nI 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.\n\nOverall, 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.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "lg5bJYdjT5a", "reviewer": "Reviewer_wtkZ", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nI 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.\n\nNow 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not necessary for this submission.", "review_text": "", "extra_scores": {"ethical_concerns": "Not necessary for this submission.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "KyscsV4nYlz", "reviewer": "Reviewer_nGs4", "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$.\n\nThe main contributions are:\n\n1. 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.\n\n2. The results are model-free, but strongly depend on the maximum or average distance of the points to true cluster center.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nI have a few comments/questions (in a random order).\n\n1.  Assumption 1: \n\na. 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.\n\nb. 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?\n\nc. 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.\n\n2. 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)? \n\n3. 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. \n\n4. The sentence following equation 4 is vague. Can you add more details on how the Theorem shows whatever is written there?\n\n5.  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. \n\n6. 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. \n\n7. 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. \n\n8. You mention a few times in the paper that you proofs are non-trivial. I think that these statements should be removed.\n\n9. 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.  \n\n10. 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<...$.\n\nConclusion:\n\nWhile 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.\n\nTypos:\n\n8. In the proof of Theorem 1 it should be $+4\\eta$ and not $+4\\epsilon$.\n\n9. When you bound the cardinality of $S_k$ in the proof of Theorem 2 it should be a strict inequality $<1$. \n\n10. \"We now extend Theorem 3\" should be \"We now extend Theorem 2\".\n\n11. \"Have properties in Assumption 1\"  should be \"Have the properties in Assumption 1\".\n\n12. \"value the cost function\" should be \"value of the cost function\"..", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "48"}, "extra_text": {}}, {"review_id": "8Az3HSZCn9F", "reviewer": "Reviewer_j782", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n\nIn 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).\n\nSome 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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5-6 hours"}, "extra_text": {}}]

Author rebuttal:

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)