Achieving Optimal Clustering in Gaussian Mixture Models with Anisotropic Covariance Structures
Authors: Xin Chen
Anderson Ye Zhang
Venue: NeurIPS 2024 oral (2024)
Keywords: Minimax rates
Mixture model
Lloyd’s algoirhtm
Clustering
Primary area: learning_theory
TL;DR: We study clustering in anisotropic Gaussian Mixture Models by establishing minimax bounds and introducing a variant of Lloyd’s algorithm that achieves the minimax optimality provably.

Abstract: We study clustering under anisotropic Gaussian Mixture Models (GMMs), where covariance matrices from different clusters are unknown and are not necessarily the identity matrix. We analyze two anisotropic scenarios: homogeneous, with identical covariance matrices, and heterogeneous, with distinct matrices per cluster. For these models, we derive minimax lower bounds that illustrate the critical influence of covariance structures on clustering accuracy. To solve the clustering problem, we consider a variant of Lloyd's algorithm, adapted to estimate and utilize covariance information iteratively. We prove that the adjusted algorithm not only achieves the minimax optimality but also converges within a logarithmic number of iterations, thus bridging the gap between theoretical guarantees and practical efficiency.

Achieving Optimal Clustering in Gaussian Mixture Models with Anisotropic Covariance Structures
Xin Chen
Anderson Ye Zhang University of Pennsylvani ayzewharton upenn. edu
Princeton University xc5557@princeton..
Abstract
We study clustering under anisotropic Gaussian Mixture Models (GMMs), where covariance matrices from different clusters are unknown and not necessarily the identity matrix. We analyze two anisotropic scenarios: homogeneous, with identical covariance matrices, and heterogeneous, with distinct matrices per cluster. For these models, we derive minimax lower bounds that illustrate the critical influence of covariance structures clustering accuracy. To solve the clustering problem, we consider variant of Lloyd's algorithm, adapted to estimate and utilize covariance information iteratively. We prove that the adjusted algorithm achieves the minimax optimality but also converges within a logarithmic number of iterations, thus bridging the gap between theoretical guarantees and practical efficiency.
only
Introduction
Clustering is a fundamentally important task in statistics and machine learning 7 2). The most widely recognized and extensively studied model for clustering is the Gaussian Mixture Model (GMM) [7 19), which is formulated as
Y, = 0² + Cj, where Ej ind NOO, Vj e [n].
Here Y (Yi...., Xn) are the observations with n being the sample size. We define the set [n]
Assume & is the known number of clusters. Let [0")ae[h) represent the unknown centers, and Σ denote the corresponding unknown covariance matrices. Define =" E [4]" as the cluster assignment vector, where the j-th data point is assigned to. The goal is to recover 2* from Y. For any estimator 2, its clustering performance is measured by the misclustering error rate h(2, 2*), which will be introduced later in (4).
each index j E [n]]. the value of = specifies which cluster
There has been increasing interest in theoretical and algorithmic analysis clustering under GMMs. In scenario where GMM is isotropic, meaning that all covariance matrices {Er} are equal to the identity matrix, [5] obtained the minimax rate for clustering, which takes the form of exp(-(1 + (11)) | 1)1))//)) with respect to the misclustering error rate. A diverse range of methods has been explored in the context of the isotropic setting. Among these, Lloyd's algorithm [13] stands out as a particularly effective clustering algorithm, renowned for its extensive success myriad of disciplines. [15] S establish computational and statistical guarantees for the Lloyd's algorithm. Specifically, they showed it achieves the minimax optimal rates after a few iterations provided with some decent initialization. Another popular approach to clustering especially for high dimensional data is the spectral clustering 21 [8 20), which is an umbrella term for clustering after a dimension reduction through a spectral decomposition. [4 proves the spectral clustering also achieves the optimality under the isotropic GMM. Semidefinite programming (SDP)
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

is also used for clustering by exploiting its low-rank structure, and its statistical properties have been studied in literature. for example, [5].
Despite the numerous compelling findings, most existing research primarily focuses on isotropic GMMs. The understanding of clustering in anisotropic context, where the covariance matrices are not constrained to be identity matrices, remains relatively limited. Some studies, including [5 5 16
I 24]. present results for sub-Gaussian mixture models, wherein the errors Ej are assumed to follow some jub-Gaussian distributions with the variance proxy o². At first glance, it might appear that these results encompass the anisotropic case. as distributions of the form {N(0, ([0,, [a))aE(H) are indeed sub- Gaussinn distributions. However, from minimax perspective, the least favorable scenario among all Guu-Gaussian distributions with variance proxy d² thus the most challenging for clustering-is when the errors are distributed as ((0 I² Therefore, the minimax rate for clustering under the sub- Gabb-aassiin mixture model essentially equals the one under the isotropic GMM, and methods like Lloyd's s algorithm, which require no covariance matrix information, can be optemall As a result, the aforementioned findings primarily pertain to isotropic GMMs.
A few studies have explored the direction of clustering under anisotropic GMMs. 3 presents a polynomial-time clustering algorithm that provably performs well when Gaussian distributions well-separated by hyperplanes. This idea is further developed in [11], which extends the approach to allow overlapping Gaussians, albeit only in two-cluster scenarios. [22] proposes a novel method for clustering under a balanced mixture of two elliptical distributions. They establish a provable upper bound on their clustering performance. Nevertheless, the fundamental limit of clustering under anisotropic GMMs, and whether a polynomial-time procedure can achieve it, remains unknown.
In this paper, investigate the clustering task under two anisotropic GMMs. In Model 1, all covariance matrices are equal (i.e., homogeneous) to some unknown matrix E.. Model 2 offers more flexibility, with covariance matrices that unknown and not necessarily identical (i.e., heterogeneous). The contribution of this paper is two-fold, summarized as follows:
Our first contribution is on the minimax rates. We obtain minimax lower bounds for clustering under anisotropic GMMs with respect to the misclustering error rate. We show they take the form of
inf sup Eh(2, 2 cxp (11 + o(1) (signal-to-noise ratio) ) $
where the signal-to- tois ratio under Model is equal to mi (0 - 0g -
The signal-to-noise ratio for Model 2 is more intricate and will be introduced in Section 3 For both models, we can see the minimax rates depend not only on the centers but also on the covariance matrices. This is different from the isotropic case, whose signal-to-noise ratio is ming |00 0,1|- Our results precisely capture the role that covariance matrices play in the clustering problem. This shows that covariance matrices impact the fundamental limits of the clustering problem through complex interactions with the centers, especially in Model 2. We obtain the minimax lower bounds by drawing connections with Linear Discriminant Analysis (LDA) 6 and Quadratic Discriminant Analysis (QDA).
Our second and more important contribution is on the computational side. We give a computationally feasible procedure and rate-optimal algorithm for the anisotropic GMM. Lloyd's algorithm, developed for the isotropic case, is no longer optimal as only considers distances among centers 3 We study an adjusted Lloyd's algorithm which estimates the covariance matrices in each iteration and adjusts the clusters accordingly. It can also be seen as hard EM algorithm [4] Here, we modify the E-step of the soft EM by implementing a maximization step that directly assigns data points to clusters, rather than calculating probabilities. As an iterative algorithm, we demonstrate that it achieves the minimax lower bound within logn iterations. This offers both statistical and computational guarantees, serving as valuable guidance for practitioners. Specifically, if we let (()) denote the output of the algorithm after t iterations, it holds with high probability that
h(2(0) =²) S exp ((1 + o(1)) (signal-to- -oo-nil-t--ooie ratio)
8
for all 1. 2 log n. The algorithm can be initialized using popular methods like spectral clustering Lloyd's algorithm. In our numerical studies, we demonstrate that our algorithm

---

Notation. For any matrix X E Rdxdd, we denote (X)) as its smallest eigenvalue and Xa(X) as addition, we denote |X] as its operator norm. For any two vectors u, u of the same dimension, we denote (u, v) = u² their inner product. For any positive integer d, we denote la as the d x identity matrix. We denote N (u, Σ) as the normal distribution with mean j and covariance matrix E. We denote II { the indicator function. For two positíve sequences {an,) independent of significantly improves over the two aforementioned methods under anisotropic GMMs, and matches the optimal exponent specified in the minimax lower bound.
Paper Organization. The remaining paper is organized as follows. In Section 2 we study Model I where the covariance matrices are unknown but homogeneous. In Section 3 we consider Model where covariance matrices are unknown and heterogeneous. For both cases, we establish the minimax lower bound for the clustering and give computationally feasible and rate-optimal procedure. In Section 4 we provide numerical comparison with other popular methods. Proofs are included in the supplement.
its largest eigenvalue.
and [b On bn and an = Obb,)) both mean an S Cb,, for some constant 0.
n. We also write On = o(bx) or bu. oo when lim sup, Oz b.
GMM with Unknown but Homogeneous Covariance Matrices
2.1
Model
We first consider the GMM where the covariance matrices different clusters are unknown but are assumed be equal each other. Then the data-generating process can be displayed follows:
Yj= 07 + C, where Cj ind ((O,, E²), E [n].
Model 1:
Throughout the paper, we call Model I for simplicity and to distinguish from different and more complicated one that will be introduced in Section 3 The goal is to recover the underlying cluster assignment vector 2². If E were known, then I can be converted into an isotropic GMM by
linear transformation (E However, the unknown nature of Σ* makes clustering under this model more challenging than under isotropic GMMs.
Signal-to-noise Ratio. Define the signal-to-noise ratio
SNR
min [1 - -;) ||.
(2)
abb
which is a function of all the centers {0") [Eja] and the covariance matrix Σ", As we will show later Theorem 2.1, SNR captures the difficulty of the clustering problem and determines the minimax rate. We defer the geometric interpretation of SNR until after presenting Theorem 2.2
A quantity closely related SNR is the minimum distance among the centers. Define A
A min a.
||0r - 0,
Then we can see SNR and A are of the same order if all eigenvalues the covariance matrix Vn are assumed to be constants. If is further assumed to be o² then SNR equals A/o. As result, in 15 8 [4] where the isotropic GMMs are studied, A/o plays the role of signal-to-noise ratio and appears in their rates. Since (2) represents direct generalization, we refer to it as the signal-to-noise ratio for Model 1.
Loss Function. To measure the clustering performance, consider the following loss function. For any 2, 2" E [k]", we define
((2,z") min
NEW
where v (w) a bijection from [k] to [k]]. Here, the minimum taken over all permutations of [k] to address the identifiability issues of the labels 1.2....,k: k. The loss function measures the

---

proportion of coordinates where and 2" differ, modulo any permutation of label symbols. Thus, it referred to as the misclustering error rate in this paper. Another loss that will be used is {(2, 2*) defined as
((2, (1222))= = Σ 0 0
(5)
It measures the clustering performance of considering the distances among the true centers. It is related to h(2, =*) as h(2,, =*) I 2/)/ and provides more information than (22,z)). We will mainly use E(2, 2*) in the technical analysis but will present results using h(2, 2*) which is more interpretable.
2.2 Minimax Lower Bound
We first establish the minimax lower bound for the clustering problem under Model 1.
Theorem 2.1. Under the assumption
SNR
+ DC, we have
Vlog
inf sup Eh(2,2") 2 exp (11+ o(1)) SNR²
(6)
If SNR = (1) instead, we have inf E Eh(2,2") 2 c for some constant c >> 0.
Theorem 2.1 allows the cluster numbers l to grow with and shows that SNR + oo is necessary condition to have consistent clustering. If k is constant, then SNR - oc also sufficient condition. Theorem 2.1 holds for any arbitrary configurations of {0")ee]s and Σ", with the minimax lower bound depending on these through SNR. The parameter space is only for 2 while {0r Jeea]] and Σ* held fixed. Hence, (6) can be interpreted as case-specifie result, precisely capturing the explicit dependence of the minimax rates on [0a) [E[M] and Σ*
Theorem 2.1 is closely related to the LDA. If there only two clusters with known centers and covariance matrix, then estimating each 23 becomes exactly the task of the LDA: we aim to determine from which of two normal distributions, each with different mean but the same covariance matrix, the observation Y, is generated. In fact, this approach is also how Theorem 2.1 is proved: We first reduce the estimation problem of z" two-point hypothesis testing for each individual 2J. The error of these tests analyzed Lemma A.1 using the LDA, and we then aggregate all these testing errors together.
9=1
NI(I''-''1 -0,1.
3
4=
N 16 x²)
(8, x)
SRAIZ
N L)
?
-2
2
-2
4
Figure 1: A geometric interpretation of SNR.
With the help of Lemma A.1 we have geometric interpretation of SNR. In the left panel of Figure | we have two normal distributions N (0;, "*) and (O Σ that X follows. The black line represents the optimal testing procedure displayed in Lemma A.I dividing the space into two half-spaces.
To calculate the testing error, two normal distributions become isotropic: (0 La) and (V((())-(()))))))) the right panel. Then the distance between the two centers is [|(E")=Z((0 03) and the distance
make the transformation X' (E*)-à -á( 0i) so that the
0j), La) as displayed in
from center to the black curve is half of that. Then, the probability that La) falls within the

---

grayed area equals exp( of o())) (02- 01)11/8)))) according to Gaussian tail probability.
|| is the effective distance between the two centers of N (01, 2n) and (0 Σn) for the clustering problem, taking into account the geometry of the covariance matrix. Since have multiple clusters, SNR defined in (2) can be interpreted the minimum effective distance among the centers {6r ]e considering the anisotropic structure of Σ". This measure captures the intrinsic difficulty of the clustering problem.
As result, |1(=*) (02 0i)l
2.3 Rate-Optimal Adaptive Procedure
In this section, we give a computationally feasible and rate-optimal procedure for clustering under Model I. Summarized in Algorithm [] it variant of Lloyd's algorithm. Starting with an initial setup. it iteratively updates the estimates of the centers {0") [e)ae]j]] (in (7)), the covariance matrix Σ (in (8) and the cluster assignment vector 2 (in (9). This algorithm differs from Lloyd's algorithm in that the latter is designed for isotropic GMMs and does not incorporate the covariance matrix update outlined (8) Furthermore, (9) updates the estimation of 2j using argmin [,, )T, instead. To differentiate clearly, we refer the classic form as the vanilla Lloyd's ss algorithm and our modified version, which accommodates the unknown and anisotropic covariance matrix, as the adjusted Lloyd's 's algorithm.
Algorithm| T can also be interpreted as a hard EM algorithm. When applying Expectation Maxi- hag [k] and Σ', while the E step estimates 2". It turns out the updates on the parameters ( (8) are identical to those in the EM's M step. However, the update of 2" in Algorithm differs from that in the EM. Instead of computing conditional expectation typical of the E step, the algorithm performs maximization in (9). As result, Algorithm effectively consists solely of M steps for both parameters and =², characterizing it hard EM algorithm.
mization (EM) to Model 1, the M step estimates the parameters {#7)ae
Algorithm 1: Adjusted Lloyd's Algorithm for Model 1.
Input: Data Y, number of clusters k, an initialization (0)), number of iterations T. Output: 2(2")
for t= ,,..., do
Update the centers:
((() Eje(n YłT { (t-1) ( =
Va [k).
(7)
EsE(n I 11 (t-1) =
Update the covariance matrix:
E(1) Eoerh EyEn((Y - ol 8 (t-1)
(8)
n
Update the cluster assignment vector:
(0) argmin((y - -000) - -09),, Vj E
(9)
aC(R]
In Theorem 2.2
we give computational and statistical guarantee of Algorithm 1 We show that starting from decent initialization, within log n iterations, Algorithm [ achieves the error rate exp( ( + SNRR /8) which matches the minimax lower bound given in Theorem 2.1 As result, Algorithm is rate-optimal procedure. In addition, the algorithm is fully adaptive to the the number of clusters, as commonly assumed in clustering literature [15 8 14. The theorem also shows that the number iterations needed to achieve the optimal rate is at most log n, providing implementation guidance to practitioners.
unknown { [0"]ae(k)) and Σ*. The sole piece of information presumed be known
5

---

ind Theorem 2.2. Assume &o = (1), d Olyn), and min 2Ø=1 = - 2 on for some
constant > 0. Assume SNR
and (((²")/\((")) O(1). For Algorithm
| suppose
20)) satisfies ((210, x²) o(n) with probability at least 1,. Then with probability al least
1 - exp( (SN--SR), we huve
h(2")), ,- & exp ((1+ SNR²
for all t logn.
We make the following remarks the assumptions of Theorem 2.2
When & is constant, the assumption that SNR - oo is necessary condition for consistent recovery 2 as outlined the minimax lower bound presented in Theorem 2.1 The assumption on Σ" ensures that the covariance matrix is conditiooi. The dimensionality d is assumed to be O(vn), a stronger assumption than in [1]] 8 [4], where d = (n) is sufficient. This is because, unlike these studies, work
requires estimating the covariance matrix E' and controlling the estimation error | E*|]-
Theorem 2.2 needs a decent initialization 20) in the sense that it is sufficiently close to the ground truth such that ((=(")=z") on)). This is because our theoretical analysis requires the initialization being within specific proximity to the true parameters. The requirement can be fulfilled by simple procedures. An example is the vanilla Lloyd's algorithm whose performance is studied in Though [ 8 are for isotropic GMMs, their results can be extended sub-Gaussian mixture models with nearly identical proof. Since 6 are sub-Gaut Gaussaasiin random variables with
15 [.
proxy variance (E"),, [8] implies the vanilla Lloyd's algorithm output satisfies ((2,2*) I n exp(-(1+ (()AA)(((A(((E))) with probability at least exp(- A/VA(((==>)) -n under the assumption that /²/(22(kd/1 + ))* -> oc. Then we have ((2,z*) o(n) with high
probability under the assumptions of Theorem 2.2 and hence it can be used as an initialization for the algorithm.
GMM with Unknown and Heterogeneous Covariance Matrices
3.1
Model
In this section, we study the GMM where the covariance matrices of each cluster are unknown and not necessarily equal to each other. The data-generation process can be displayed as follows,
Model 2:
Y 0g + Eej where ~ NO 1i E [n].
(10)
We refer to this Model 2 throughout the paper to distinguish it from Model discussed in Section 2 The key difference between (TO) and (T) is that here we have distinct covariance matrices
(E)) ae for each cluster, instead of single shared Σ". We use the same loss function defined in
Signal-to-noise Ratio.
The signal-to-noiss ratio for Model is defined follows. We use the notation SNR' to distinguish from the SNR used for Model 1. Compared to SNR, SNR' is much more complicated and does not have explicit formula. We first define set Ba,b C Rdd for any a, E [k] such that + b:
1 + (>
Bagb
x R2d
:x
- - 0g) + 2
la)
S - 10, - 07,
2 1 1 -0)) + log E
log Eij
We then define SNR 2 min Ba, || and
SNR'
min a.be(k)a
SNR'
(11)
The form SNR' closely connected to the testing error of the QDA, which we will give in
Lemma 3.1 The interpretation of the SNR', particularly from geometric perspective, will be

---

deferred until after the presentation of Lemmal 3.1 Here let us consider few special cases where we are able to simplify SNR': (1) When N Σ" for
[k]. by simple algebra, we have SNR., = l1(0= 03)"=*"" || for any a, b E [k] such that a + b. Hence, SNR' = SNR and Model effectively reduces to Model (2) When Σ = o. for any E [k] where 01, .1....;0k > 0 are large ob). From these examples, can see SNR' determined by both the centers {0a) [[]j]]]]] and the covariance matrices {aa]k)([]-
constants, we have SNR,, b. SNR, both close 2 1
3.2 Minimax Lower Bound
We first establish the minimax lower bound for the clustering problem under Model 2.
Theorem 3.1. Assume d = (11 and baX,, (d(E))/A((Ei) O(). Under the assumption
SNR' Vlog
> oc, we have
SNR
inf sup Eh(2,=*) 2 exp - -(1+ o(1)) ='E(M""
8
If SNR' = (1) instead, we have inf; sup=+E/k]- Eh(2, 2*) 2 c for some some constant >> 0.
Although the statement of Theorem 3.1 appears similar to that of Theorem 2.1 the two minimax lower bounds differ due to the varying dependencies of the centers and covariance matrices on SNR' versus SNR. Using the same argument as in Section 2.2 the minimax lower bound established in Theorem c.osely relates to the QDA between two normal distributions with different means and different covariance matrices.
Lemma 3,1 (Testing Error for the QDA). Consider two hypotheses Ho X ~ NN Ef) and HI,
N (65 M3) Define a testing procedure
Φ = log Σil + (xr 01) 01)
01) 2 log Σ3 + (x ())) -x 05)}.
Then we have inf (PH. ( = 1) PH (6= 0)) FE. (o = 1) + PE, (o = 0) Assume = O()) and max,, (1,22) da >a(E;) /1 (EE) = 0(1. min {SNR SNR } DC, have
inf (F,, - 1) + PH, (6 = 0)) 2 exp - -(1+ ((1) min {SNR',2, SNK2, 1²)
8
Otherwise, inf (P n, (6 = 1) + PH, ( = 0)) 2 e for some constant c > O.
9=1
NOE -Q)) 1E
==
(8), xZ)
2
N66, z)
N10.
S
Figure 2: geometric interpretation of SNR'.
provides a geometric interpretation of SNR'. In the left panel of Figure 2 we have two normal distributions (0; Σi) and A0005, Eg) from which can generated, and the black curve represents the optimal testing procedure ń, as detailed in Lemma 3.1 Since Σ; is not necessarily equal to 25 the black curve not necessarily straight line. If H, is true, the probability that X is incorrectly classified occurs when X falls into the gray represented by PHo (ó 1). To
Lemma 3.1
7

---

calculate this, we transform X to === = - standardizing the first distribution. Then, as displayed in the right panel of Figure 2 the two distributions become NO, La) and (V((() (0)
01), (ET) (21) )), and the optimal testing procedure becomes I (X' B1,2). As result, in the right panel of Figure 2 B1,2 represents the space colored by gray. and the black curve is its boundary. Then PH. (Ø
is equal (O Ia) B 22,)). Under the assumption and bE (1.22) Aa aa(22)/>
O(1) = ((1), in Lemma C.10 we can show (0, La) E B1,2) =
As a result, SNR' can be interpreted as the minimum effective distance among the centers {0- (aek)) considering the anisotropic and heterogeneous structure (>aJ and it captures the intrinsic difficulty of the clustering problem under Model 2.
exp(-(1+ + o (1)))NNR
3.3 Optimal Adaptive Procedure
In this section, give a computationally feasible and rate-optimal procedure for clustering under
Model 2. Similar to Algorithm | Algorithm| 2 is a variant of Lloyd's algorithm, adjusted to accommodate unknown and heterogeneous covariance matrices. It can also be interpreted hard EM algorithm under Model 2. Algorithm 2 differs from Algorithm in (13) and (14), as now there are & covariance matrices instead of common one.
Algorithm 2: Adjusted Lloyd's Algorithm for Model 2.
Input: Data Y, number of clusters k, an initialization (0),, number of iterations T.. Output: 2(?)
for t= = do Update the centers:
e(() Eje(n) Yj1 { (t-1) 32 = =a
Va [k]]
(12)
Ejeni I 112//-11
Update the covariance matrices:
D0t1 Ejem - 0000 )Y, - -0(')TT 1)
23
Va [k)
(13)
Eje(n] ((0/ (t-1) (((1-1) aj
Update the cluster assignment vector:
argmin(Y, - 0 020) -((0) log [2
Vj E [m].
(14)
aE(A)
In Theorem 3.2, we give computational and statistical guarantee for Algorithm 2 We demonstrate that, with proper initialization, Algorithm 2 accheves the minimax lower bound within log iterations. The assumptions needed in Theorem 3.2 are similar to those in Theorem 2.2 except that we require stronger assumptions on the dimensionality d since now we have &t (instead of one) covariance matrices to be estimated. In addition, by assuming max, Aa(E))/ /2 (EE) O(1), we ensure not only that each of the ie covariance matrices is well-conditioned but also that they are comparable to one another.
Theorem 3.2. Assume ho -1), d O(1), and min (M) ΣØ= 1f2] a}
for some
constant a > 0. Assume SNR' + co and max, be(k) (EE)/A>( = O(1). For Algorithm 2 suppose 20) satisfies ((2(0), 2²) = o(n) with probability at least 1 Then with probability at
least 1 17 5n -xp(p -NR'), we have
h22()) 2²) - exp - -(1+ ((
SNR'2)
for all t t logn.
The vanilla Lloyd's 's'sas algorithm can be used as the initialization for Algorithm This because Model 2 is also nub-Gaussian mixture model. By the same argument as in Scction 2.3 the output of the

---

vanilla Lloyd's algorithm satisfies 2(2, = o(n) with high probability under the assumptions of Theorem 3.2
We conclude this section with a time complexity analysis of Algorithm 2 Compared to the vanilla Lloyd's algorithm, method introduces additional computational overhead due the need for computing the inverse and determinant of covariance matrices. Specifically, the time complexity of Algorithm 2 is OnkkdT'). In contrast, the vanilla Lloyd's algorithm has lower time complexity of O ) The increase in complexity stems from matrix operations in d dimensions, as both matrix inversion and determinant computation scale as O(d)).
Numerical Studies
In this section, compare the performance of our methods with other popular clustering methods on synthetic and real datasets under different settings.
Model 1. The first simulation is designed for the GMM with unknown but bomogeneous covariance matrices (i.e., Model 1). We independently generate n 1200 samples with dimension d = 50 from k = 30 clusters. Each cluster has 40 samples. We Σ- U AU, where A is 50 50 diagonal matrix with diagonal elements selected from 0.5 to 8 with equal space and U is a randomly generated
orthogonal matrix. The centers {0*) eejn] are orthogonal to each other with |
|0%ol|
We consider four popular clustering methods: (1) the spectral clustering method in 14] (denoted as
"spectral"), (2) the vanilla Lloyd's 's algorithm in (15] (denoted "vanilla Lloyd"), (3) Algorithm
initialized by the spectral clustering (denoted as "spectral + Alg 1*"), and (4) Algorithm [ jinitialized
by the vanilla Lloyd (denoted as "vanilla Lloyd + Alg 1""). The comparison presented in the left panel of Figure
Model We also compare the performances of four methods (spectral, vanilla Lloyd, spectral + Alg 2, and vanilla Lloyd Alg 2) for the GMM with unknown and heterogeneous covariance matrices (i.e., Model 2). this case, we take n = 1200,
9. We set ΣG = Ta and Σ; = A2. diagonal matrix where the first diagonal entry is 0.5 and the remaining entries are 5. We set the cluster sizes to 900 and 300, respectively. To simplify the calculation of SNR', we set 07 = 0 and 05 5e1, with e being the vector that has a in its first entry and Os elsewhere. The comparison is presented in the right panel of Figure
2,
method
method
loglonaa)
spockl
epectall
Loy!
soochal A
spectal (Aly
Loyd A
Itaraton
Figure 3: Left: Performance of Algorithm I compared with other methods under Model Right: Performance of Algorithm compared with other methods under Model 2.
In Figure 3 the z-axis is the number of iterations and the y-axis the logarithm the misclustering error rate, i.e., log(h). Each of the curves plotted is average of 100 independent trials. We can see both Algorithm T and Algorithm [ outperform the spectral clustering and the vanilla Lloyd's algorithm significantly. Additionally, the dashed lines in the left and right panels represent the optimal exponents -SNR2/S /8 and "NNR /8 of the minimax bounds, respectively. It is observed that both Algorithm | and Algorithm meet these benchmarks after three iterations. This justifies the conclusion that both algorithms are rate-optimal.

---

Real Data. To further demonstrate the effectiveness of our methods, we conduct experiments using the Mishion-MNNITT dataset [23]. In the first analysis, we use a total of 12,000 28 x 28 grayscale images, consisting of 6,000 images each from the T-shirt/top class and the Trouser class. The left panel of Figure gives a visualization of the data points using their first two principal components, showing the anisotropic and heterogeneous covariance structures. Since a large number of pixels have zero across most images, we apply PCA to reduce dimensionality from 784 to 50 by retaining the top 50 principal components. Our Algorithm achieves misclustering error of 5.71%, outperforming the vanilla Lloyd's s algorithm, which has an error of 8.24%. In the second analysis, we incorporate an additional class, the Ankle boot class, increasing the total to 18,000 images across three classes. Following the same preprocessing steps, the visualization of the dataset's 's structure in the right panel of Figure 4 again confirms the presence of anisotropic and heterogeneous covariances. Here, Algorithm 2 achieves an error 3.97%, an improvement over the 5.64% error rate observed with the vanilla Lloyd's algorithm.
Figure 4: Visualization of the MNIIST dataset using the first two principal components. The data points are color-coded to indicate class membership: Red represents the T-shirt/top class, green denotes the Trouser class, and blue signifies the Ankle boot class. This illustration shows the existence of anisotropic and heterogeneous covariance structures.
5
Conclusion
This paper focuses on clustering methods and theory for GMMs, with anisotropic covariance struc- tures, presenting new minimax bounds and adjusted Lloyd's algorithm tailored for varying covariance structures. Our theoretical and empirical analyses demonstrate the algorithm's 's ability to achieve optimality within logarithmic number of iterations. Despite these advances, our results have some limitations that are worth addressing in future work:
1. High--Dmeensionl Settings: Current results are restricted to dimensions d growing rate slower than ni, specifically ( as stated Theorem 2.2 Section 3 further requires stronger assumption d (1). These constraints stem from technical challenges in estimating covariance matrices accurately and in controlling matrix determinant. Adopting sophisticated analytical tools could potentially relax these bounds to d Onn). In scenarios where d exceeds n, the misclustering error deviates from the simpler exponential decay observed under isotropic GMMs, as shown in [16]. This suggests that our model might also exhibit similar complexities, warranting further exploration into the technique used in [16] for potential extensions.
2. Ill-Conditioned Covariance Structures: Our analysis relies on the assumption of well- conditioned covariance matrices, where max,,bejkk Aa(=))/ (22)) = O(1). This con- helps manage the estimation
dition is crucial for the current analytical framework, errors of covariance matrices and their inverses. While more advanced techniques may allow for a relaxation of this assumption, handling ill-conditioned or degenerate covariance matrices remains challenging, particularly due to the difficulty of working with matrix inverses in such cases. While minimax lower bounds suggest that clustering still possible even when the covariance matrix is degenerate, it raises computational challenges for our current algorithms. This highlights the need for developing new algorithms that can function effectively under less restrictive conditions.
10

---

References
[1] Emmanuel Abbe, Jianqing Fan, and Kaizheng Wang. An ep theory of PCA and spectral clustering. The Annals of Statisties, 50(4):2359-23855 2022.
[2] Christopher M Bishop. Pattern recognition and machine learning. springer, 2006.
[3] S Charles Brubaker and Santosh S Vempala. Isotropic PCA and affine-invariant clustering. In Building Bridges, pages 241-281. Springer, 2008
[4] Arthur Dempster, Nan Laird, and Donald B Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B (Methodological), 39(1):1-22, 1977.
[5] Yingjee Fei and Yudong Chen. Hidden integrality of SDP relaxations for aab-Gaussian mixture models. In Conference On Learning Theory, pages 1931-1965. PMLR, 2018.
[6] Ronald A Fisher. The use of multiple measurements in taxonomic problems. Annals of eugenics, 7(2): 179-188 1936.
[7] Jerome Friedman, Trevor Hastie, and Robert Tibshirani. The elements of statistical learning. volume 1. Springer series in statistics New York, 2001.
[8] Chao Gao and Anderson Y Zhang. Iterative algorithm for discrete structure recovery. The Annals of Statisties, 50(2): 1066-10446, 2022.
[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] Daniel Hsu, Sham Kakade, Tong Zhang, et al. A tail inequality for quadratic forms of subgaus- sian random vectors. Electronic Communications in Probability, 17, 2012.
[11] Adam Tauman Kalai, Ankur Moitra, and Gregory Valiant. Efficiently learning mixtures of two Gaussians. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 553-562, 2010.
[12] Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. The Annals of Statistics, pages 1302-1338, 2000.
[13] Stuart Lloyd. Least squares quantization in PCM. IEEE transactions on information theory, 28(2):129-137, 1982.
[14] Matthias Löffler, Anderson Zhang, and Harrison Zhou. Optimality of spectral clustering in the Gaussian mixture model. The Annals of Statistics, 49(5):2506-2533 2021.
[15] Yu Lu and Harrison H Zhou. Statistical and computational guarantees of Lloyd's algorithm and its variants. arXiv preprint arXiv: 1612.02099, 2016
[16] Mohamed Ndaoud. Sharp optimal recovery in the two component Gaussian mixture model. The Annals of Statistics, 50(4):209-21166, 2022.
[17] Karl Pearson. Contributions to the mathematical theory of evolution. Philosophical Transactions of the Royal Society of London. A, 185:71-110, 1894.
[18] Daniel A Spielman and Shang-Hua Teng. Spectral partitioning works: Planar graphs and finite element meshes. In Proceedings of 37th Conference on Foundations of Computer Science, pages 96-105. IEEE, 1996.
[19] Michael Titterington, Adrian FM Smith, and Udi Makov. Statistical analysis of finite mixture distributions. Wiley,, 1985.
[20] S. Vempala and G. Wang. A spectral algorithm for learning mixture models. J. Comput. Syst. Sci., 68(4))841-86,, 2004.
[21] Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4)3995-416 2007.
11

---

[22] Kaizheng Wang, Yuling Yan, and Mateo Diaz. Efficient clustering for stretched mixtures: Landscape and optimality. Advances Neural Information Processing Systems, 33:21309- 21320, 2020.
[23] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. 2017.
[24] Anderson Zhang and Harrison H Zhou. Leave-one-out singular subspace perturbation analysis for spectral clustering. arXiv preprint arXiv: 14855, 2022.
12

---

The appendices are organized as follows. Appendix is dedicated to proving the results in Section
2 To be more specific, we prove the lower bound, Theorem 2.1 in Appendix [A.] and the upper bound, Theorem 2.2 in Appendix A.2 For the upper bound proof, we first give high-level idea in Appendix 1 followed by a detailed proof in Appendix A.2.2 Appendix [amudixBBjnne includes proofs of the
results in Section 3 the proof of the lower bound. Theorem 3.1, in Appendix [B.1] and the proof of
the upper bound, Theorem 3.2 is in Appendix B.2
We include all technical lemmas and their proofs
in Appendix C
A Proofs in Section 2
A.1 Proofs for the Lower Bound
In the following lemma, we give a sharp and explicit formula for the testing error of the LDA. Here we have two normal distributions (o Σ²) and NN00; E*) and an observation X that is generated from one of them. We are interested in estimating from which distribution the ob- servation is drawn. By the Neyman-Pearson lemma, it is known that the likelihood ratio test I [2(03 - (>*) - 2 05" (2"") - 01 (=0)) is the optimal testing procedure. Then by using the Gaussian tail probability, we are able to obtain the optimal testing error, with its lower bound given in Lemma A.1
Lemma A.1 (Testing Error for the LDA). Consider two hypotheses Ho X ~ Noii, E*) and Hh X ~ ((25 Σ²) Define a testing procedure
Φ = I (2 07) (E") 2 657 (E*)- 07'
Then inf & (Fro ( PM (Ō 0)) = PF, ( = + (0 0) If] (E*) +1
we have
inf(PPno (6 1) + PEL, (ō =]) 2 exp -(1 -(1+0(1)) -1) $113
8
Otherwise, inf 3 (P n. ف = 1) + Pu, ( = 0)) 2 e for some constant c <> 0.
Proof. Note that & is the likelihood ratio test. By the Neyman- lemma, it is the optimal procedure. That is, (PF,, ( = Pa, ( = 0)) = PE, (o = 1)+Pa, (o 0) Lete (0,, By Gaussian tail probability, we have
PH. (Ø) = 1) + PH, (Ø = 0) = P(2(0; - 10000"7""00000000000000000000"30
+ P - "3 (10)
22( -09
+c)
0 (--)
1 [(83 (E)) -1
2P <>
|100 - 07) -1) ()))())))))))))> 11
C 1, 10:5 (
$1 exp
8
for some constant C >>0 0. The proof is complete.
Proof Theorem 2./
We adopt the idea from 155] Without loss of generality, assume the minimum
in 2 is achieved at a 1. b-b=2 2 so that SNR
= (0) 63)²' (E*)-11 -1 07). Consider an arbitrary E [k)" such that { E [m] : E, a}l 2 - st2 for any [k]. Then for each E [k]. we can
choose a subset of (i E [m] : 2 = a) with cardinality [ Sk denoted by Ta. Let T Usel To-
Then we can define a parameter space
Z = {x E [k]" 2 = 24 for all i E T and = E (1,2)
Notice that for any + ã E Z, we have E 1 + 2) < _
मे and 1 ET H()(z))) + conclude
2.
) > मे
for any permutation s' [k]. Thus
h(2, 2)
I( # 2,) for all 2 E 2.
1-1
13

---

We notice that
inf sup (2)(2,2)) = E[K]
2 inf sup (2((2,
E
2 inf
Eh(2,z")
Σ 2'
P.. (2; 2.).
Z
ET
for = 1. Then we can see Z 2 Z2 and 2 Z- 0. What is more, there exists a one-to-one mapping f(-) between 21 and Z2, such that for any = E 21, we have f(z) E Z2 with [f()]]] = 2j for any j # i and two-point testing probe and then apply Lemma A.1 We first consider the case that SNR + Co. We have
Now consider fixed i E T Define Z, {z
[f(=)]: 2. Hence, we can reduce the problem
inf Z
Σ (2 2))= = inf E0ZZ
Σ E
(P
+ 1) + P ((z)) # 2))
21
Z
2
(nf (2, + 1) + F. f(x) (2: # 2))
2
2
2
-(1 + 17) SNR²
exp
2
SNR²
exp
- + 1))
2
8
for some = o(1). Here the second inequality is due to Lemma A.1 Then,
[79
SNR²
1
exp ((11 (-11+)) + (1)
SNR²
inf sup 2h(2,2") 2 =(((""
exp
((1 + 17)
2n
8
16k
8
exp -(1 11+ SNR
for some other r/ o(1), where SNR? /log ks
oc.
The proof for the case SNR = 0(1) similar and hence is omitted here.
A.2 Proofs for the Upper Bound
A.2.1
High-level Idea
In this section, we provide high-level idea for the proof of Theorem 2.2 The detailed proof is technical and given later in Appendix [A.2.2]
The key idea for establishing the statistical guarantees of Algorithm | an iterative algorithm, is to perform "one-step" analysis 8 That is, assume have estimation for =". Then we can apply (7) (8). and (9) on z obtain (=))=))a(()) Σ(z), and (22) sequentially, which all depend on refined estimate of 2* We will first build the connection between
Thus, ((2) be f(2, with {(ā(z), =*) as in Lemma A.2 which informally states that under certain conditions, with high probability, we have
((8(2), S Eideal + _ [(,
holds for any 2 E [k]] such that {(2, 2*) is small. Here Exteat (0) refers to the ideal error, which
eventually leads to the upper bound in Theorem 2.2 Lemma A.2 tells 2(-) has "contraction" property. That is, after one iteration of 7 and E(ā(2), I is at most a half of É(z, 2*), up to an additive term (idea
To establish Lemma A.2 we decompose the loss ((E()), into several errors according to the difference in their behaviors. Next, will introduce several conditions (Conditions I under
14

---

which we demonstrate that these errors are either negligible, well-controlled by { >²), or connected
to (6) Once Lemma A.2 established, we will show in Lemma A.3 that the connection can be extended to multiple iterations, under two more conditions (Conditions 4 5 Lemma A.3 states
informally that, under certain conditions and with high probability, we have
((2 =²" S Eideal (6) + [((x(t11)
1 2
1) ,,2")
1. This implies {(=(0, 2*) ) is eventually most (ideal0), up some constant factor. Last, we will show all these conditions hold with high probability. Although the algorithmic guarantees in Lemma A.2 and LemmalA.3 are established with respect the ((..-) -) loss, we will use the relationship between ((:;)) and 6(., -) to convert this result to one involving l((,-). -). Hence, we prove Theorem
for all 2
2.2
A.2.2 Detailed Proofs In the statement of Theorem 2.2 the covariance matrix E* is assumed to satisfy \d(E")/A((E')
=
O(1). Without loss of generality,
replace it by assuming E" satisfies
Amin S A1(EE)= S >a(E") S Amax
(15)
where Amin Amax > are two constants. This is due to the following simple argument using the scaling properties of normal distributions. Let {Y,} be some dataset generated according to Model I with parameters {0"] [e]k)()) Σ", and 2². The assumption \A()))\A((E) = O(1) is equivalent to assuming there exist some constants Amin- Amax > 0 and some quantity a > O that may depend on n such that o I > (E*) < >a(E*) S Amaxe? By performing a scaling transformation, we obtain another dataset Y Yj/o. Note that: 1) {Y7} can be seen as generated from Model I with parameters [0///]<E[3 Σ* /0², and =², 2) Clustering
{Y₃} is equivalent clustering on (Y,). 3) By the definition in 2 the SNRs that are associated with the data-generating processes of (Y))
and { } are exactly equal to each other. 4) We have Amin I (E* /0²) S >a(E" /o") S Xmax-
Thus, for the remainder of this section, we assume that 115 holds without any loss of generality.
In the proof, we will mainly use the loss E(:;-) for convenience. Recall A is defined as the minimum distance among centers in 3.. We have
((2,=')
1(2,, 2*) S
(16)
n4²
The algorithmic guarantees Lemma A.2 and Lemma A.3 are established with respect to the E(, ))
loss. Eventually, we will use (16) to convert it into a result with respect to h(.,)) .) in the proof of
Theorem 2.2
Error Decomposition for the One-step Analysis: Consider an arbitrary z E [6]] Apply
8
and 9 on to obtain (dn(z))aE[M) {==) and á(z):
(z) Eiein YjI (zz a}
Va E [k]
Eje(n [2 a}}
{(2) = Euelh E Ejetal (Y, - -a(()))(y, - (z) = =a}
25(:) -argmin(, (z)))) -V, 0a), Vj E [m].
aE(R]
For simplicity. we denote 2 as shorthand for 2(2). Let j E [n] be an arbitrary index with =j = a. According to (9) =j will be incorrectly estimated after one iteration in if a * argming [N] (Y₁
0x(2)) (8(=)) - (=)). Therefore, it important to analyze the event
(Y, (z)2), (E(=)) -(Y;) db(2))) < (Y, - (z),, (E())) -
(17)
for any b E [k] {a). Note that Y, = 0g + +ez. After some rearrangements, we can see 17 is
equivalent to
(c, ($(=")) - (0,()") Oo(=")))
< 2
10- - 0, (Σ*)-1 (0) 0))) + + (,) H,
15

---

where
by(a,b,)) [(0b)))-((((((()0000000-0--0--10 (S()) (Q.(2) 0a(=))))
+ (S(())())(((((+))))))))))) 0a(")))
1
Gj(a,b,2)
2 10 (S(s)) (x())) 2 10 0.(=)), (E(=)))) (x())))
+ 2 10 (=()), - (=()))) -
2 10- do(="), (,(="),(()))))))))) (E(==)) - (z(z))))
10 (F(:))) (.())))
2 10: ((=)),((()))))))))))())))))))))) (2(=))) ()())))
10 (x(=), (E(=)) (=())))) 2 10 0,(=') (I(==)) '00 0s((")))
1
b, =-
2 10 (x(²)) ($(()))) '00 - 0o(2")) ))} + 2 00 - 0 ($(=")) - '(0 - 02))
1
1
2 10t % (0- 0,)) + 2 10 0% ( -00 - 0,))
1
2 (02 (2))), (E(=*)) ())))
In the above decomposition, the expression (e,, (0x(=))) - < -
% (Er - 0g)) does not involve 2. Roughly speaking. it corresponds to the event that 2j will be incorrectly estimated in 2(="). This is considered the main part of (77 and will contribute to Sideal. The difference between (17) and the main term is expressed through the terms Fj, Gj, Hy: F3 includes terms related to noise Ey. illustrating the impact of measurement noise; Gy covers estimation
errors for cluster centers (0) 10--0.. 0_ (2")) and covariance matrices (É(2) E(²")), showing the effect of the parameter estimation inaccuracies; H, contains all other terms from additional error sources. Readers can refer to 8 for more information about the decomposition.
Conditions and Guarantees for One-step Analysis. We continue to analyze the event 17 We first define quantity independent of 2, which we refer to the ideal error:
Sideal (d) = 5=1 bE(
100;
0/ (e,, (S())))) ((0(==='')00))))) 0o(2))))
- 2
10 0,, (5-) - -8h)) }.
When 5 0, it is determined by the main term in 17). namely (cj,
0b(="))) S
1 (0) - 0% (E-) (0: ())). Roughly speaking, Erdeal (0) relates the performance of ((="). Due to the presence of the terms Fy. Gj, H, in the decomposition of (17). what appears in the analysis of
(7) is Eitem(() instead of Eiteat (0) where hopefully 8 > 0 is some small number.
To establish the guarantee for one-step analysis, we next give several conditions on the error terms F3 (o. b; 2), Gy by z) and (a, b; z).
Condition 1. Assume that
[H b, =)1 (2:((..0" }ST) JEIN bE(K)(a3) 10 07, (274) -1 -0;)
5
max
max
max.
<
4
holds with probability at least tn for some T, 7,611 m > 0.
Condition 2. Assume that
F5 b, 2)2 11100 0
82
max [x:((,0" (ST)
max DEBREE
(0 07 ( )((
128
holds with probability at least - Th2 for some T, 8, n2 > 0.
16

---

Condition 3. Assume that
Gz(zj,b, b,,]
5
max max (==() b (0=; - 07 (22) (0%, - -0,) 8
max
holds with probability at least Lemma A.2. Assumes Conditions 7 fordfor some T, 6, 1/1 12, 11, > O. We then have
n/ for some 6, 173 > 0.
1
P (((2,2)) S (ddear(6) + 2 [(2 ( for any & [1]"* such that 2(,,2)) ST)
2 1 17.
where 1) = Ei=1 9/s-
Proof. Consider any E [n]] such that 23 a. We notice that for any b E [k] such that 6 + a.
[{ = b} s - (())) (Y, - 0s(=))) s (Y, - (E)=) -Y; - (=)))) }
= 2 - -,(==))))===))) ))))))))
- 10g - 03 (x - -06) + F, - - (o()))) 5 --2 1-6 5
$ 1
s s ff(e, (
2 10:: 02 (8) - -061
+1(0 6 10 0g (8') (8)- - 0()) s F,(2), b, G,( b)) + (3 (0);
$ Su les, (5((2)) (0,;)))))0(())))) - 0o()"))) S 1-5 10:- - 0g (29 10,- - -061
+1 +1{8 0 10: 08 (20)- 10: - 08)) S b12)
1-5 5
2 10-; (E9) - -071) }
s 1 (e), (D(x")) -0))0-((0 (0,g (2*) - 0o(2"))) S
(z) b, x)²
80 87 (E+) 10
where the second inequality comes from Conditions and Note that we can multiply [ = b} on both sides of the above display and the inequality still holds. Hence,
1
{2 b} S (c., ($())))) (0 (z*) - {)())))) -
10
0% (E*) - 0%))
2
(4,) b, 2)
8% (E+)-111 10 -0;))2 188, 3 b).
82 80;
Thus, we have
((2,2))
Σ
Σ
00 -0:0 1|2
11 [8, = b}
J=1 be [a]
< Eideal (8) +
Σ
Σ
005 03
2
[824 = b}
61F 2)²
8 (0 0% (2*) 10;; 120)-1(0;;- 0z
j=1
{=33
< Eideat (8) + Σ
005 - 0%-
2
61F 22
max
De
bE(
80 23
0g - -2
1=1
< Eideal (8) + ((2,2))
2
which implies Lemma A.2
Here the last inequality uses Condition 2
17

---

Conditions and Guarantees for Multiple Iterations. In the above, we establish a statistical guarantee for the one-step analysis. Now we will extend the result multiple iterations. That is, starting from some initialization 200), we will characterize how the losses ((2(0), 2²), ((2(1)
((2(2) ,="), .... decay. We impose conditions on Éidenl (6) and the initialization z(0) Condition 4. Assume that
3r
Eideal (6)
holds with probability at least TI for some T, 6, 1/1 > O.
Finally, we need a condition on the initialization.
Condition 5. Assume that
((2(0) --²) S
holds with probability at least 17s for some т, 77s >
With these conditions satisfied, we can give a lemma that shows the convergence of our algorithm.
Lemma A.3. Assume Conditions 7 hold for some T, 5, 71, 72, 78, 7/,, 77 0. We then have
((219, S Eideat (6) + 2
f(2 ((2(t-1),z))
for all t 2 1, with probability at least 1 - v). where = Σi= 1/-
Proof. By Conditions
S and a mathematical induction argument, we can easily conclude
t(z(0, 2*) S T for any
0. Thus, Lemma A.3 is a direct extension of Lemma A.2
Results for the Conditions and Proof of Theorem 2.2
Recall the defini-
tion of A in (3) Recall that in (15) we assume Amin & >x"))) < >a(EE) < Amax for two constants
Aminy Amax Hence we have of the same order as SNR. Specifically, we have
1 A SNR
A.
(18)
Amax
Vmmin
Hence the assumption SNR - oo in the statement of Theorem 2.2 is equivalently A oc. Next, we give two hutt-high-probability lemmas. The first lemma is for Conditions [3 providing upper bounds for the quantities involved in these conditions, showing that ō can be taken some o(1) term. The second lemma shows that for any 5 = o(1), (() is upper bounded by the desired minimax rate multiplied by the sample size n.
Lemma A.4. Under the sume conditions as in Theorem 2.2 for any constant C' > 0, there exists some constant C > only depending on a and such that
|H,(=j,b, b,
k(d + logn)
max (eS(c.2")STJJEl bE(g)) (0;; 07, (E* 10 0g)3
max
max
S SCV
(19)
71
max
max
(2 b,) - 1011
S CkB
T
+
d2
(x:E(x,0*) (S, j=1
be [()))) (0 - 03 (2' - (())2(((,2*)
(03;
n1
2
nd3
(20)
GGy(2, b,2)
T
dvF
max max JE( bE(A)((3)) (0:; (8,(())) - 0,))
max
Ck
n
A
n
n
(21)
with probability at least 1 - n -C' As a result, Conditions 3 hold for some 8 = o(1).
38 hold with probability at least 1 - n CC", In the remaining proof, we will work on the event these inequalities hold. Denote
Proof. Under the conditions of Theorem 2.2 the inequalities
33
18

---

(x) = EX ((()))()-0,()))) Eze( 1zz==a}
and Σy = Σ" for any a E [R]]
Then we have the
equivalence
شーー M[z a} (Ca - M%).
-(=))
--"
a=1
Hence, we can use the results from Lemma and Lemma C.8
By 43 and
44
we have
k(d - log n)
- =
and
Σ j=1 U2z = a} (2)
Σド= H2j = a} Ea(z")
->(=))\(=")11
Σ
n
n
k
122 a}
k
و== (I
12
= a}
1125 = =a))=
ا=
(Ea(2) E((²))
+
Σ
E0 (2*)
n
72
a=1
*vnl(2,2*) 2*)
k =((2,2))
kd
k
-
[(2,22)
+
(2,
nd
71
nA
n
k //l(2,, 2*
k
kd
+ ((2,2"))
nA ((2z2"))
n
By the assumption that kd = O(vT),
A + 00
and r = o(n//k), we have [|5(=²) - 11.
k
E(=*)| o(1). which implies (0]=="))==[|1((((((())
< 1. Thus, have
k(d k(d+logg)
(22)
and similarly
= * =((,22)) kvnl(z,,2) 2*) kd nd nA
VE(2,
(23)
Now we start to prove
19
21
Let = -1 (a,b,)) + r2.3) (1, b, z) + 10.00 (a, b,2) where
r (a,b)))) (2:()))))) - ()) (e,, (Z(=)) - -Oa(=")))
((s()))) -f(==)) ((()))))),
==
-6)),,
(o(z"))) + (eg - - -
Notice that
(eg, b, 2) 2 1/
(zg,
max be (M(()))) 00 0g (E*) ( (0 01))²((2,,*) 2*)
(5 (()())))) - ($(x))) -1 (00 - 07))
1103 0:1 2(2 2*)
j=1
2
(G, (G.))) -1 ($(2²)) (00 -07)
[ = a)
10: 0, 2| (22 2*)
b= aE (+)) f=1
[(({(=)) - ($x(=)) (((="))>>((83) (0 : 0,71?
Σ
Σ [zz = ateje
10 0ī 12 x*)
b= aE [A]
3 3 T + 2
RAI
19

---

23 and the fact that 2(2,2") I and kd = O(vn) for the last inequal- ity. Here the second to last inequality is due to the following argument: for any w E Rd. we have Σ, Key, w)1 Eg w' eje w w (;,, ) I | ||0 L3 E From (41 have [M) 110a (z(2))l o(1) under the assumption kd O(v By the similar analysis in p (a, 2), we have
where we use 34
F ( (z) b, 2)² 10:; - 11
d
Σ max (E()) 10 0g (E*) 1-(0)1100 10;; 00))²((2,,2)
A
n
Similarly, we have
19 (1) (zg, b, 2) 1010 01
max
BE (M (0=; - 0, (E*) -0;; 0,))2((2,*))
Σ
( - 111
Euz -zzz=afef5}
10 - (2 x*)
b=1 aE (|V0))
A3
A
where we use (4) and the fact that (i(=)) -1 has bounded operator norm. Combining these terms
together, we obtain 20
Next, for
19 by we have
(0 (z))), (I(=)))- (6(=)))) + (0: - -,, (1(())) -b))
10g 0o()"), (2("")))²00 (00 - (o(x"))) + 2| ds(z"), (2(x))) 0231
k(d + logn)
k(d + log n)
10-- - 01
n
and
k(d + logn)
100 - 0o(22)) (E()))) - - 0a(2")))
n
By
22 we have
k(d + log n)
1- (0% - 6% (E(()))) (0: 0))) + (0 - 0,, (E*) - 0113 =
100 - -2
Using the results above we can get 19)
b, 2) which has four terms. For Finally we are going to establish (1T) Recall the definition of G3 (a, the third and fourth terms, we have
| - 10- (z), (i(()) -(: - -o(=))) + 10- 0,((a)), (2(=)) -0===(<=") ))X 3 [10x(=) - (f()))(² + [10,(z) - 0x(=")) |1100= - -0,1l
and
| (0= 0o(2))) - 0g(()))))))))))))))))))) (1(="))~~ -0:-00)))00000()))))
0.(2))) - (0-
1 110: -
We can easily verify that the other two terms smaller than the above two terms. Then, by using
and 233 we have
GG,(2 b, 2)
0g, (2+) 10
10'; 02))
[00(2) (0(2²) )12 + [10)()) 06(2*) )
11110:
0g + 100; 11
|6
0, 2|
kJ
k
T
kd
n
A
n
n
20

---

Lemma A.5. With the same conditions as in Theorem 2.2 for any d = o(1), we have
Sideat (6) exe (-11+ ((1)) SNR²
8
with probability at least 1 1 --- - -exp(-SNRR
Proof. Under the conditions of Theorem 2.2 the inequalities (3 38 hold with probability least
1 nn-C" In the remaining proof, we will work the event these inequalities hold. Recall the definition of Sideal. We can write
10:; - -681 (Ex=)))))) -0,6))~0((''')) 0o(=)))) S - 1-8
Sideal (6) = Σ
2 10=;
0% (E") - 0b))
1=1 De [K]{{2}}
10 - 00111 - - 0b,) s
1 8 8
10 - (E") (0 - -0311
2
1=1 be [k]
8
Σ
100 0,11:1
(e), (()())))) (2-)) - -(,) S
10 - 0% (2-2)-((033
100 - -0;1)
6
BE bE(l))))})
8
Σ
100 0,11:0
(e (E(=)) (00)))))00000)))) ((, -0;)) S
10 0% (E*) 100; - 00))
100 0,1121 { (Sxx(()))))) 02)) S 0 0g (E") 02)}
8
+ Σ Σ
j=1 bE(
= M1 + M2 + M3 + M4.
where 6= = 8, is some sequence to be chosen later. We bound the four terms sequentially. Suppose
Ej 1/2")//22,, where wy ind (N La). By
we know
8 6Amax
M2 S Σ Σ
100 0,11-1
10
B11 S Amax 11
-661
1=1 bE (x({}))
Σ
Σ
1003 0.111
C8110
-081ly V + log n
n
S ||0l||
1=1 (x())
Σ Σ
100
0; C8:110
17 + logn
2d < ||w5|12 - 2d
j=1 bE(M(E))
where C' is constant which may vary from line by line. Recall that kd O minazt 110
- co, and A/k - co by assumption. Let - = o()). Using the x² tail probability in Lemma we have for any + b E [k).
10;, 0811 exp (-C89100; - 0,11 VT) S n nxep ((1 + (1))
SNR?
E. Σ Σ
8
j=1 [=
We can obtain similar bounds on M3 and M4 by using the inequality
For Mj, the Gaussian tail bound leads to
(eg (2 - 00)) 5 1
8-8
8
(0 0% (2*) (0: -0:10;) 03)3 }
PP
2
pf (1zz,
180)-1/2(02) - -r,) <
1-
8 3
s - 02 (E*) - -03)
2
(1 8 8 0 0,, (E*) (E0) - 07))
< exp
8
21

---

Thus,
11
(- (1
5)2
EM Σ E
10:; 0811 exp
10a (2*) "---'"000 081)
j=1 DEINI\t23)
SNR?)
nexp - -11+
8
Overall, have Lidiall 3 n exp ((11 + o(1) SNR-
By the Markov's inequality, have
P(Eitea( 2 Eideaa exp(SNR)) S exp(-SNR).
In other words, with probability least 1 exp(-SNNR) we have
SNR* 8
Sidcal (5,) S (ECideal exp(SNR) & nxp -(1 -(1+
Proof of Theorem 2.2 By Lemmas A.3
A.5
we have that Conditions 1 are satisfied with
probability at least I n2
exp
SNR
Then applying Lemma A.3 we have
SNR? 8
{(= x nexp
(-(1+
1 ((>(tt1), ,²*), for all / 2 1.
By 16 and since there exists constant C' such that A CSNR, we can conclude
SNR²
M221), 2- S exp (11++
+2-1, for all 12
8
Notice that h(s,)) takes value the set (j/n should be negligible long 2 o(n-1) Thus, we claim
[m] U {0)}. the term 2-t in the above inequality
1220), & exp -(1 ((1))
SNR?
8 ) for 2 log n.
B Proofs in Section
B.1 Proofs for the Lower Bound
Proof of Lemma 3.7 The Neyman-Pearsee lemma tells us the likelihood ratio test Φ is the optimal procedure. Following the proof of Lemma A.1 we have
Pro (0 1) PH, (Øb 0) P(e E B1,2) + Ple B2.1)
1 1+ o SNR + exp
(- 1+ + SNR
2 exp
8
8
where the last inequality is by Lemma C.10
Proof of Theorem 3.7 The proof is identical to the proof of Theorem 2.1 and omitted here.
B.2 Proofs for the Upper Bound
We adopt similar proof idea as in Section 2 for Model 1. We first present error decomposition for the one-step analysis for Algorithm 2
Lemma B. we show the loss decays after a one-step iteration under Conditions 6 11 Then Lemma B.2 we extend the result to multiple iterations, Finally, we show that all the conditions are satisfied with high
under two extra Conditions probability and thus prove Theorem 3.2
13
22

---

In the statement of Theorem
3.2 we assume be(K) A1 = (11 for the covariance
matrices (M Without loss of generality, we can replace it by assuming {_a jeekk) satisfy
Amin S min A1 (Ex) S max >a S Xmax
(24)
kk
aE[k]
where Amiu: Amax O are two constants. This is due to the scaling properties of the normal distributions. The reasoning is the same as that (15) for Model and is omitted here. For the remainder of this section, we will assume that 24 holds for the covariance matrices.
Error Decomposition for the One-step Analysis: Consider arbitrary 2 E [A]]. Apply 12
and 140 on = to obtain (0)()))nE()) (e)(2)) and (()):
(a(2)= = ΣyE(n] {2) = a}
ΣjE(m 1(23 = =a}
(x) Ejetn((y (V3 (a( - (,())) = =a}
Va [k],
Eje( 12)=
2t(t)
(=))) aE(k]
'YY -d(()) + log [z),,,, Vj E [n].
For simplicity, denote 2 as shorthand for 8(2). Let j [n] be an arbitrary index with 2j According to (14). 23 will be incorrectly estimated after one iteration in if & [
(.(=)) (Y3 - (z())) + log [E())). That is, it important to analyze the event
(Y, - 0o(=), (Ea(=)) '(Y, - (o())) - log [Ex( S (v, - 0=(),, (E)())) (Y; - 0n(z))) + log [a(())
(25)
for any e [k] \ {a}. After some rearrangements,, (e, (Es(22))) (0= ()))))) - (E,, (z))
see 25 is equivalent to
(0 (=()))))
1
2 10 ((E6()))) - (E)()"))~"){s) log E
log [ا]]]
2
1
s 2 (0% 0% (Et) - 07))
+ F3 (3, b. + (j(a, + +ojaabaa-(jjaaaaaaa(aa++++++++ (( L,, b,2),
where
= (s,
- - -1,_ 0,(²)))
-0a(=")))
Ye ((E (8,((" (a()))),
b,(,, (g. ((E.())) ($6()*)) + 1 (0 ((fa())) (((x)))))))))
b,(a,b,))=
2 (0: (=),,, (2)())) - 10: (x))) -
1
1 10 0x(2)), (())
'0: - (,()")))
2
+ 2 10 0.(3"), (f.( d,(=")))
2 10 0.(2²) ($.( - 0a(z")))
10 (.))), (26(2)) (0: do(2)))
2 1 0(2)), (2:(2)) (s()))))
1
1
10 (x))), (f((=))-1(0)) - 0o(='))) + =0:00000000 0x(z"), (fa()*)) (0 ()))))
H,(a,
2 10- d,(="), (Zs(=")) -00 (b(=))))
1
2 (0: 0f (Es(z") -100 03))
1
10 or ($6(z") ))- (0:- 0()) + 1
10: 0% (2)) 10: -0,)
2
2
+
10) (x()), (0: - 6a(2")))
2
23

---

Kz(a,b,2) = =2 2110g [x) - log EE (=*)))
2 (log [x)( - log [=x(=*))) )),
Lg(a,b, b, z) - -2((0g E (=")] - log [= 2 (log |²x((")) log |
Among these terms, Fj, GJ, H are nearly identical to their counterparts in Section A.2.2 with E())
replaced by [x) or Ex),). There are three extra terms not appearing in Section A.2.2 Qj is quadratic term of Cj and K,, Inj are terms involving matrix determinants.
Conditions and Guarantees for One-step Analysis. To establish the guarantee for the one-step analysis, we first give several conditions on the error terms. Condition 6. Assume that
(2) b, 2)
8
max max max (2:((a,z )TT JE (E(
(0;; 0% (2%)
-0'; 01)
12
holds with probability at least 1 - tn for some T, 6, m > 0. Condition 7. Assume that
E2 b, 2) 2) 0,11
82
E
max (2:0(2,>" 1ST bEIH)()E) (0 8% (Σg) 18;; ((())
288
holds with probability at least 72 for some T, 8, m2 > 0.
Condition 8. Assume that
[G, b, =)1
max max (adE(a,e' (T) JE ((()))) (0=; 0g, (2i) -00; 0,))
max
5
12
holds with probability at least Condition 9. Assume that
7a3 for some T, 7,6,11 1/3 > 0.
25(2g, b, 2) 2) - 1:
8²
max (2:E(2,2
max DE(M) (0;; 0% (21) 1(0 2()))((2)2)))
$
288
holds with probability at least 1 Na for some T, 8, 71 > 0. Condition 10. Assume that
Kj Ky(#). b, b,2 10;0 0
82
max (a:0(e.2") (ST DE(M)(EE) (0 0% (Ei) -00; - 0,))2((z,2))
max
288
holds with probability at least 176 for some T, 8, 175 > 0.
Condition 11. Assume that
(1, b.
max max max (s:E(2,>") ( JEIN bEMMiaa
(0 0g, (2i) 10;; 0,))
5
12
holds with probability at least 116 for some T, 6, 116 > 0.
We next define a quantity referred to as the ideal error.
Eidcal (8) = Σ
10 - 12 ($o()))) 0o((2)))) - -ey, (Ea(2))) - (x(()))
1=1 {xgg)
)(s)) log Ex + log Ez < 1 8 (0) 0% (Ei) - - 0,11
+ 2 (eg,
2
2
Lemma B.1. Assumes Conditions 6 17
hold for some T, 8, ......, 76 > 0. We then have
P (((,,=²) (8d 2 2) for any [K]" such that f(z,z)) S
where 11 = 2im1 Th.
Proof. The proof of this lemma is quite similar to the proof of Lemma A.2 The additional terms Qj and K, can handled in the same way as F, while I,j can handled similarly to H,. We omit the details here.
D
24

---

Conditions and Guarantees for Multiple Iterations. In the above, we establish a statistical guarantee for the one-step analysis. Now we will extend the result multiple iterations. That is, starting from some initialization 200), we will characterize how the losses ((2(0), 2²), ((2(1) ((2(2) ;=)),, ,=").... .... decay. We impose conditions on Éidenl (d) and the initialization 2(0)
Condition 12. Assume that
Eideal (0) S
2 holds with probability at least 1J for some T, T,6, 5, 17 > Finally, we need a condition on the initialization. Condition 13. Assume that
((x(0, xz") S T
holds with probability at least 1 - 778 for some T, > 0.
With these conditions satisfied, we can give a lemma that shows the convergence of our algorithm.
Lemma B.2, Assumes Conditions 13 hold for some T, Ö, M....., Ms O. We then have
(( (*) x²) S Eiden( (6) + (( .2")
1
2
for all t I, with probability least 1 17, where 1l Σ t/.
Proof. The proof of this lemma is the same as the proof of Lemma
With-high-probabilit Results for the Conditions and Proof of Theorem 3.2
Lemma B.3 and
Lemma B.4 are the counterparts of Lemmas [A.4 and AA.5 in Appendix [A.2.2 Recall that (24 is assumed. By Lemma C.10 we have A is of the same order as SNR', which will play a similar role as
(88 in Section A.2.2
Lemma B.3 and Lemma B. 4 are counterparts of Lemmas A.4 and A.5 in Section A.2.2 The first
lemma is for Conditions
providing upper bounds for the quantities involved in these conditions, showing that ō can be taken as some (11) term. The second lemma shows that for any 5 = o())
Eldeal (8) is upper bounded by the desired minimax rate multiplied by the sample size n.
Lemma B.3. Under the same conditions as in Theorem 3.2 for any constant C' > 0, there exists
some constant C >> 0 only depending on a, C², Amin, Amax such that
|H5(2} b,
k(d + log n)
max [2:f(>,²*)51] JE(n) BE
max
max
S CV
(26)
( 07, (Et)
-0;)
23
Fy(2),b, b, 2)11 - 1711
1
d²
S SCk3
(2:8(2,2*)S1
max
bE(g))(3)) (0 0g (E;) (2:))=1(0;; 03 ((())(((2))))
max
A
nAz
(27)
max max max
[G,(2}, b, 2)
CCk
T
+
1
T
dvT
(*:((*.;*)<T) je(n bE(l)(1;) (0) - 0% (E1) - - -0:)
10
n
A
n
A
(28)
Q5(23,b, 2 1
< CC" 1.da2
T
1
d
(a:l(e, (r)
max
be (()(g) (0;; 0g, (2;() 0)))2(( 2,
max
A
+
A
(29)
K, b,),,6,))91003 13
1.2
1
d
max
max
$ SC"
(x:1(2,**)
bE(l)())) (0; (2;)) 8, 2)))
A2
1
A
n
(30)
[L5(2J,b, b, 2)1
d
k(d + logn)
(2:f(2,2") jE(m) (E(()((3)) (0'; 6% (Σt) (8
max max max
-0,)
S
C
A
n
(31)
with probability at least 1 - n - 1
nd. As result, Conditions 6 11 hold for some 6 = o(1).
25

---

Proof. Under the conditions of Theorem
3.2. the inequalities (3 38
hold with probability at least
1 - n In the remaining proof, we will work the event these inequalities hold. Hence, we can
use the results from Lemma C.7 and
Using the same arguments as in the proof of Lemma A.4
we can get (26) (2 and 28
As for (29 we first use Lemma C.2 to have 2j-1
||e S 3nd with probability at least 4/
Then, have
Q5(z3, 2))
1111
b,). (=, 2*)
max DE(R) (R) (#5) (0;g 0g
0g))2((z,
maX [1(Ea(=))
(Ea(("))
|e;il*
A20(2,z*)
j=1
d
1
d²
A
A
n
where the last inequality is due to (53) and the fact that {(2, 2*)
T.
Next for 30 notice that by A₂ (E
43 and SNR' 0o, have for any 1 S i S d.
Amin S
2ama and
(2) Ea(2*)11
[a(()) E2(2)112
log(1 [ + max
log(1 - max <
aE
d (x))
[E(R]
X (Ea()))
Thus by Weyl's inequality, we know
log I (z)l log [za()))
max
[k(
log | (=) (=a()))
max < [k]
d
[$a(2) Ea 112
log(1 maX
Ae(Ein )i(E(((2))
i=1
(=(=)) 2I
[$a(2)) - 32(2")12
max
{²(55((=))
log
+ max
1=1
aE(k)
(xx
max.e(A)
(.. Xx (x)))
<d| E (z) (z"))22
(32)
where the last inequality is due to the fact that Xx(E((2))) is at the constant rate, [(aa())
Ea (2 (1) and the inequality log(1 + 2) S x for any 0. (32 yields to the inequality
K,(=3, b, 2) 1 1/
" d max
[Ex - (2-)))
Σ
max be ( 10 - 0g (27)) ((2,))(
A2((2,2")
j=1
2
d2
2
7
n 2
Finally for 31 by 43 and the similar argument 32
can get
k(d + logn)
max log [za)))) [[=]]] - log |21
3 dv
which implies 31
We complete the proof.
Lemma B.4. With the same conditions as Theorem
3.2 for any sequence 8n = o(1), we have
-(1+ SNR²
Eideal (8n) S nnep
with probability at least 1 - n -C' - -exp(-SNi
26

---

Proof. Under the conditions of Theorem 3.2. the inequalities (3 13 hold with probability at least
1 - n -nn In the remaining proof, we will work on the event these inequalities hold. Similar to the
proof of Lemma A.5 we have decomposition Sideal S > i= M, where
Mi Σ
10: 08 [s] (ts (ez, (28) (0)))000--- -66) + (e,, ((2)))1 - ))}z)
j= be (+]{;;))
1-
8 8
log -وng + 2 log ا 5
10
02 (2%) (00))~0003 - 0.))
2
the main term and
M2
|0;; 03 (((
08)) S
8
(0'
0 (E)) -1 10 - 08))
10
j=1 be [A][=])
M3 Σ
Σ
|0:; 8% 1 [f[ 11s,, leg, fe/=(-(ee.
(E:g()"))) (() - 0,)(2")))) S
5
10
(6 ( 08.)
10
M4 = Σ
Σ
105 05 "el/i((eex (0))))))) 01)1 5
10 - (2%) (20)))((0))))))))))))))))
²00; - 06)1 }
10
1=1 be (M]())))
M5 Σ
n
Σ
|o: (((= S
8
10
0%. (E:) -(00 - -0%)
10
j=1 bE (M]((t)))
Ms Σ
Σ (E(A)
0% -1)) (E -
10 18: 0 - 0%)))
Using the same arguments as the proof of Lemma A.5 we can choose some = 5, = o(1) which is slowly diverging to zero satisfying
SNR for 2, 3,
((1+
E., S nexp
As for Ms. by
(33 have
Ms < Σ
10;; 05| bE()
Σ
16121/
C8 0;
10
log [|w,
n
where C' is constant and wy (0, Ia). Since there exists some constant C' such that SNR' < C" A, we can choose appropriate 8 = o(1) such that
EM, <
Σ Σ
0 05 p
c8
n 00; - 85 1 log n
S ||w;|1?
1=1 (
((1+
SNR
< nexp
8
27

---

Ms is essentially the same with M2 and can be proved similarly. Finally for M1, using Lemma C.10 we have
P
- 08)) + 2 (e):
1 - 5
log الرزع + 2
log |Σك v
2 (0 03. (2i) (5,)))(00
- 0%))
=P
(ws, (2:;) )a (2%)) (0 0%:)
+ 2 (w) (E:)) )
/ (2))
( ) la)wy}
1
1 - 8
log |ン +
log زニg v
(0 6% (,;) (0,)))(03 (02; -06)
2
SNR' 2j bb
$ exp
-(1 - o(1))
8
Then we have
SNR
EM1 S n exp
-(1+ o(1)
8
Using the Markov's inequality we complete the proof of Lemma B.4
Proof of Theorem 3.2 By Lemmas B.2 B.4 we can obtain the result by arguments used in the proof
of Theorem 2.2 and hence the proof omitted here.
C Technical Lemmas
In this section, we present and prove technical lemmas used in this paper. Lemmas C. and C.2 are about x2 distributions. Appendix C.1 gives various upper bounds needed in the proofs of Appendix Appendix C.2 is devoted to the calculation related SNR'.
Lemma C.1. For any x > 0, we have
P(x d+2v + 2x) se
P - Se
Proof. These results are Lemma of 12
Lemma C.2. Let W. sid for any i [n] where n, are positive integers. Then we have
4
w? 2 3nd
nd
nd(d + 2) + 4) + 6). Then have Var (En, W?) Snd(d + 2) 3). Then obtain the desired result by Chebyshev's 's inequality.
Proof. We have E Σn
Di= W = nd(d + 2) and E EL W
C.1 With-Hiigh-Pobbabiitty Bounds
Lemma C.3. For any z [k]" and ks E [n], consider independent vectors E, N 23, for any j E [n)). Assume there exists constant Amax 0 such that | || S Amaxfor any [k]. Then, for
28

---

any constant C' > 0, there exists some constant C 0 only depending on C², Amax such that
Σ Mzj a}e;
CCV d log n.
(33)
[E[
v Dド= M2z = a}
max dE(k] d + Σド=1 [12] = }}
Σ [13 = ateje
cC,
(34)
j=1
max
Σ JET
S Cvd+ni
(35)
TC(a
max max (E|A] [c
Σ
9
SC,
(36)
[T + En Ef M22 a})
JET
with probability at least 1 C², We have used the convention that 0/0 0.
Proof. Note that Cj is sub-uuuuuu GabbGaassiinn with parameter Amax which is constant. The inequalities (33
and (35) are respectively Lemmas A.4, A.1 in [15]. The inequality (34) is a slight extension of Lemma A.2 in [15]. This extension follows from standard union bound argument. The proof of
(36) is identical to that of (35).
Lemma C.4. Consider the same assumptions as in Lemma C.3
Assume additionally
min Σÿ=1 H22 a} 2 for some constant >> 0 and kid+log m2
o(1). Then, for
any constant C' > there exists some constant C only depending on a, O", Amax such that
kid logn)
max aE[A]
Σラ L1zj = a} j=1
Σ
M2z = aaeee] -Ea SCV Ex
(37)
n
with probability at least 72 CC"
Proof. Note that we have Cj Σd3 Ml where nj 3d NO, Ia) for any j E [m]. Since max, |E S
Amax, we have
max [E(k]
n 2zzz = a} j=1
12 ateee] - 22 S Amax max aE(k]
ES 1221 a} j=1
Σ
123 = a)m;n, La
Define
Qu Σラ 1/25 a} I(2 a3nm,; Ia-
Take 5d-1 Ey Rdd ||y|| 1) and N = fui,-.. N. is an c-ooerrnng of 5d In particular, we pick 6 < 1. then N. < gd. By the definition of the -coveringg we have
1
|1Qall 1-
max
[u:2 2 i=1...,,MM
10 Qa4%
2e 1=1, 1.... |N.]
For any & E No.
T Qa
Σラ 12 = =a} Σ
1|]== a) n3 1).
29

---

Denote = Ei=1 = a}. Then ΣØ= H2z a.tennnz ~ Xa. Using Lemma have
C.1 we
P(max aelk]
1all 2t) S
P(IQaal 2t)
I.N.1
P(IoTQ0r Qovil 2 2122)
1=
2 2exp
{
na min [2] + d log
Since log+logn) o(1) and na 2 an/k where is constant, can take / C" a
k(d++ng m)
for
some large constant C and the proof is complete.
Lemma C.5. Consider the same assumptions as in Lemma C.3 Then, for any s o(n) and for any constant C > 0, there exists some constant C >> O only depending on C², Amax such that
max Sa log (T) + min(1, VITIjd
Σ Eje
SC,
(38)
TC
JET
with probability at least
C² We have used the convention that 0/0 = 0.
Proof. Consider any a E [s] and a fixed T' C [m]] such that [T' = a. Similar to the proof of Lemma
C.4. we can take Sd-1 = {y E Rd |ly|| = 1} and its c-covering N. with < 1 Then have
1 and |Ne| s 9d.
11 Σ JET
sup Σ w TuTTe e2, S 2 max [(wTe,) |||||=1
WEN,
JET
JET
Note that w C//V///// Vimaxx is sub-Gaussian random variable with parameter 1. By the tail probability result for quadratic forms sub-Gaussian random vectors [10, for any fixed w E Ne, we have
[WTTe)}2 Σ (w e,) 2 Amax (a (a+ 2Vat + 2t) s exp(-t). JET
I
Since a = o(n), there exists a constant Co such that 2a < Coa S. We can take t = Ö(alog a +d)
with Ö 16
Co then 2Vaa 2/ & (a log 2 + d). Thus,
P
Σ T JET
12 2
C (a log
- +d) d) s exp (- E n
n
d))
4
a
Hence, we have
IP
Σ
C log + d)
(a
n
s 9d
exp
Ö(a log + td))
a
jET
As result,
max TS
[T' log a + d
Σ
2 C
5
max
n Σ cje 2 Cla log +
-
a
JET
a=1
jeT
71
max IP
Σ
E5e T 2 C(a log n + +d)
a=l
jET
11
gd exp
Č(alog - + +d)
a=
30

---

Since a log is an increasing function when E [1, s) and a log =u 2 log 2 log choice of Ö 3 + C", that C 16C" + 4Co + 48, can yield the desired result.
Finally, to allow [T] O, we note that d v min(1, vd The proof is complete.
Lemma C.6. For any x" [Re] and & [n], assume min Ej= Me] a} 2 and
nA²) x( then ((2,2*) o
=0]
max
2ド=1 1[zz = =a S 2.
(39)
aE M
Proof. For any E [k]" such that ((z, 2*) = o(n) and any [k], we have
[z)==0
2
Σ [(} = a} Σ
j=1
j=1
a
[(12 = 2(2,2*)
Σ
A
an
(40)
2k
which implies
EJ=1 122 = =3
Σ= 1/2 = [ + EJ 122 + 23)
2
Ej 11zz = =a}
Σー a
an/2k
S
j=l [12==
= a}
2.
Thus, we obtain (39
In the following lemma, going to analyze estimation errors of the centers and covariance matrices under the anisotropic GMMs. For any 2 E [k]] and for any 2 E [k), recall the definitions
(a(2)= ΣjE(n) Y = a}
Ejem I [2 = a} Va E [R]]
E2(2) Eje(n) (Y, (x)))) (z(2)) a}
Ya [k]].
EjEn (2)==a)
Lemma C.7. For any 2" E [K]" and k E [n], consider independent vectors Y, = 0z + Ej where
9j NO, E for any j E [n]. Assume there exist constants Amin; Amax > such that Amin S ( S (x)) Amax any a E [k), and constant a: >> 0 Oucch that min Σラ=1 1125
a} 2 K Assume k(d+log = o(1) and A - Assume (3)- 38 hold. Then for any o(n)
and for any constant Cº O. there exists some constant C that
0 Onlly depending a, Amaxi C' such
k(d + logn)
max ae
(z()))
-8;
0% SC
(41)
max aElk
[b((s) 0a(x*) 0
nA ((2, ((2,2")+
k
ddd+n
V((e,z*)
(42)
nA
kidd + logn)
max [E(R]]
[ia()²)) 27/ 5 sVV
(43)
max
[z(2)) - (()=)));((=')) c
t E((,, +
ky nl(22,2))
kd
(2,222)
(44)
(E(M]
nd
nA
for all z such that ((2,z") S T.
31

---

Proof. Using 33 we obtain 41 By the same argument of (118) in [8]. we can obtain 42 By 33
and 37 and we can obtain (43 In the remaining proof, we will establish (53)
Since k(d+log m) n will be decomposed into several terms. We notice that
(1), we have |Ê (2")] = for any a E [k]. The difference (x) E. (2*)
|Ea())) - Ex((') (1
- S + S2,
(45)
where
S =
1
Σ
a
122 = a} (0ss (o))-o(())(Ks - 0a(3))) - (Y, - -0,(=)))))x -
|
Σ 21 = a}
j=1
and
So = $>=1( aa a)
1
1
- -
= a} ΣTs}]
1=1
Also, we notice that
S1 S 11 + L2 + L3.
(46)
where
n
[(z = = a) 01)- - 0a(=))² - (V, - -oa(=')) (000))(50(660 )o(="))²) >1
j=1 12 = a} j=1
1[2,= = a, a - - (oc0))(x-B00CC 8.(O))/
L2 =
|= H2g = a} j=1
Σ
1zzz a, -0
La =
Σラ 12 = }}
j=1
For L1, we have
1
n
L 1
Σ j= 12g = a} f=1
1
Σ
[z = a)((; - 0,(23) -
-0)0)((())=00=))))")))) 0,(="))²'
+2
Σラ 1/2 = =a
j=1
3 |la(c)) - 0a(=t)/ 1²
Σラ= "
1125 a}
+ +100-- - (oa=Ba())]] ||| (a(33) - 0a(2*)
Eド= I23 = a}
> Hzg a}
5= 11 = =a
v
+ [00(s) 01(33)|
Σ113
"
12g = 2 = ate,
(47)
1 a
j=1
By 36
39
40
we have uniformly for any E [k).
1
Σ
M(2 = ==
3
5= 12g = 2 = a}
d + Σ [(2== = a}
a
E 1|zz- = a}
jj=1 11 =a
j=1
j=1
11
(48)
Since max [Ba((*) - 0:1| = =o(1). by 39
and 48). we have uniformly for
any a E (k).
1 4 [b((2) 6a(2")) |||
1 n
k
e(2,22)+
+
kvd+n d n Ve(2,2*).
(49)
nd
32

---

To bound L2, we first give the following simple fact. For any positive integer m and any {u, belm) (U))se(m) E R we have ll || + By)(u, + +,)' s 2 21 u,u7
2|1 j oy ||. Hence, for L2, we have the following decomposition
L2 S 2R1 + 2R2,
(50)
where
Ttz = 0, a)(Y - 02) - -
R1
Σラ= 1(2 = a}
j=1
R₂
1
Σ
11
122 2, + a0 - ( {2(3))²
Σ Eソ H2g = a}
Since [a)
Σ j==1 1125 23
2] # aa -
{( we have
A
プラ 1zg = 2,23 # a}
R₂ S |0: - 0u(3)
ΣE= 1|2z= =
> (11(((3) 0a(x*) 1| + |o(+")) - 0: oal')) kl(z,2)) 2²)
(51)
nA²
By 38 and the fact that maX
Σ/= 1 a, 2 + #a} s =(a,"")
we also have
A=
R1 s 2
Σ
T(2}= a. 2 * (0) - 10 - 03/98
E==1 112j = a}
,=1
+
Σ
112 a, + atcØE
Σラ H22 = a} j=1
E}=1 1/25 = a, * a 10:: 87, 11
< 2
2
Σ j=1
12 = a, =] # a}ezE/
E5=1 [1 = a)
E5=1 [1 = a)
k)(2,2*)
1(2,2)) A
n log
E(2,2-) + dv
(2,22)) 3²
n
n/k
We are going to simplify the above bounds for R1, R2. Under the assumption that A(d+log x) o(1), A/k + oo, and 2(2,2") S T = o(n). we have max [10_(2) 0x(2"))) )1 = o(1),
k((z.=") Also we have max [10) 0i1l o(1), and k((z,z") o(1). Hence R₂ . nA²
nd²
xl(z,z")
n k kV((2z2*))
2(2,2*) ((2,2t)
log
na² kvnl(22,2*)
log
nA²
E(2,2*)
nA
A
nA
where in the last inequality, we use the fact that z(log(n/x)) is increasing function of when 0 < x = =(n). Then,
L2 1 kVne(z,z*)
+ kd nA V((2,22).
+ [(2222))
nA
Since Lg is similar to Lg. by
(46 we have uniformly for any a E [k]]
< k x
kdd
S
n + E((2,2 2) + nA Ve(2,2t).
(52)
To bound Sz. by (70) in 8 we have uniformly for any a E [k],
Σ 11 a) - Ei= T| = a)
| 1|
k ((2,z")
S2
- n A
====
33

---

A md
where we use (43). have
Since
3
by 45)
and the facts that ((,,t) ST =o())
A3
max aE[k]
Ea(z) - En(2")|
h xvne(z,=*)
+ [(2,z))
+ nA v((,22))
kd
nA
Lemma C.8. Under the same assumption as in Lemma C.7 if additionally we assume kd = (vyn) and r o(n/k), there exists some constant C' > 0 only depending on a, Amins Amax, C" such that
- sc c n
[) + \Vnl(z,,
kd
max <C(A]
(((222))
(53)
nA
nd
Proof. By (3 we have max [| I1, [ ||
= 1. By
44
we also have
max [k]
E (3)] (a [2(a(2)) -1 = Hence,
max aE[k]
(Eia())) (Sa(2"))
mmx (2))))) [i(()) - Ei((2)) ||| aE(k]
[ x*
k [[2 2²) + kd
n v {( z(2
(54)
nd
n
C.2 Calculation Related to SNR'
In the following lemmas, we study properties of (SNR2, 2, Jogts. Consider any pair a + b [k]. Let
n NO, Ia) and Ea.b = 0g 0z. Define
(o) = x E Rdd ERR
-
+ ""0 E0 (Zi))
(E%))
-1 la))
$ 2 aab
=T
(E)) Ea.b
+ log |
log !
2
2
x E Rd
||0|| 2 2 x (Σ = ) ((E))
- ))((()=
(x x-
+ log (2%)) 22 (2:)
$1 - - (2))) - EE,
for any 8 E R. Then (8) C (o") for any 8' < 6. In addition, we define
SNR (
min ||-||
and (o,)(5) pn (o)) Recall the definitions of BaG and SNR',, in Section
3 Then it is special case of Ba,(()) and (, with 5 0. That is, we have Ba, Bu and SNR',, SNR',,
To understand these quantities, we first study a canonical setting that can be later applied to establish Lemma C.10
Lemma C.9. Consider any 0 Rdd \ {0} and any E Rdddd that is positive semi-definite. Let
Amaxy Amin > 0 be the largest and smallest eigenvalue of E, respectively. For any I E R, define
D(t) = {xr e Rd ||>||2 2 (x - -)- (x 0) +t).
and s(t) = min ||=|||- Then the following hold:
* Under the assumption that 11011 /(8Amax) < <t< < 11011 /8, have
||0|| / (maxx22, 2 2Amax )) < s(t) < (1 minf v Amin/ 88, 1/2)) ||0|].
34

---

If also satisfies - |1011 />max <t < [1011 /8, we have
t' --t
|s(t') s()] S Amax 2 min V Amin/ /8, 1/2] |11|
If is further assumed to satisfy min{ Amina/ 88 1/2} ||@l| 2 2Xmax and ||0|| 2 Amin minf / mim//8,11 1/2], there exists a d-dimensional ball H(1) E Rd with 32 radius (Amin/88 /8) min( / /mmnn/ (imin/8,1i 1/2] such that H())
D(1) and | S
(Amin/ /8) min| V Amin/ /8, 1/2] + Xmax + s(t) for all x E (t).
Proof. First, we check whether each of the following two points is contained in (tt) or not, under the assumption - |1012 /Amax <<< 11012
. When x 0, we have (x - 15 - 0) +1 |101] / /Amax + t > 0. Hence, 0 & D(t).
When æ = 0, we have |10|2 > t. Hence, 0 E D(t).
As a result, (t)) is non-empty, s(t) is well defined, and 0 < s(t) < 101 Next, we consider a few more points to sharpen upper and lower bounds on stt) under the assumption - |00 /88maxx < t < |10|| /8.
For any x that satisfies ||>||| < ||0|| consequently, (x ")²' 'x - 0) + 2 /0)ll/2)/muu + t = ||0] [1@ll/((Aunn)) /(4Amaxx + t.
we have || 0| 2 ||0|| /2 and
Under the assumption that t > - |00|] /88Amax), we can verify that ||0 /44Amax) + +1>
|00|* /(8Ammx) 2 (1101 / max (2, 2/ 2Xmmmxx 2 ||=:| Hence, such x & D(I).
When x = (1 - min / Amin 88 1/2])0, we have || 2 |1011/2 and (x - 0) (x 0) + t V ||0| (minf / Amin /8, 1/23)² /Amin + t |1011 / /max(8, 49,,4im } + t. Under
the assumption that < [[0] /8, we have [101]2 / mmxxxxf 4Amin + < |101 /8 t S |0|| /4 < ||=|| 1 Hence, such x E D(t).
As result, we have (max/ 2Xmax)) stt) < (1 min / Amin 88 1/2)) 1101|
Define a ball S() = {a E Rd: || S r²) and define S2(r; = (w E R2: (x (x- -0 x0- 0) S p²-t) to be the part of Rd that inside the corresponding ellipsoid. Then we have s(t) min >
S:S, (r) n (r: * 0}. By the definition and bounds of st) and the convexity of (s(()) and (2(s(t); t), we must have (s(()) n (s((::)
1, meaning that S (s(t)) and (z() touch
each other externally at one point. This implies st)) can be obtained by the following process: We let (i)) and (2) grow by increasing r, starting from O. The first time they touch each other, we stop and the value of is exactly s(t).
Denote y(() E IR such that (v(()) (i()()) (2((()) Then we must have v(1) (=()((); By the first conclusion, we have
l1v(() - 0|| 2 ||0|| ||x(O]| = ||O|| - s() 2 min (VAmin// 1/2) |10]]
[Iv(() - 01l < |10|| + ||x(1]] = ||O|| + s()) < 2 ||0||
In addition, we have
2t (tt)-== (v(t) - (((t)-9)Tx-1(0 (y(t) 0) 2 l1a(() - 011 /Amax 2 (min Amin// /8, 1/2} [101))/Am Amaxx
Now we are going to prove the second conclusion of the lemma. Without loss of generality, assume I < L'. Then we have D()) プ D(L') and x(() S s('). We are going to establish a lower bound for s()). First by definition of s((", we have (s((())) n S2(s(());
Since S t', we have (2(stt));t) S2(s(t");t)) We have Si (s((t) n (s(tt))) + 6. From here we can also see
35

---

s(t) S stt'). Now consider any x E )2(s(t));t). It satisfies -x- 'x - 0) = (t) t. Then
we have
(v (v((()
((1)) (a- (5-0) Σ-1 (v=(()) 11 ((()) t
((t)) - (x -00 = = - t',
meaning that 0 +
( x( (x - 0) E {2(s(((); Hence,
| 2 0 + (t) - t' (x
0 + (t)) +'
(2 -t (x 8)
(2(() -
0 (2) - 4
(2) 1 (x 0)
(t t¹
11 011
(2(1)
x²(()) - (2(1) -
min (x(()))
|B8||
max
||x 011
(E()((()))))
Since |S (s(tt)) 1, we have min = Since (x-0)-5--16
0) X || 0l1 have || 011 s Aumax ( (1') t). Hence,
(2) -1
| 2 s(t')
1- (1-V
V
((t))+
(22xx - t)
s(')') V ss2(t)) -t (t)
11-1 (82(1)) -+ V82(11) -1 11
=s(')) VAmax
2 s(t') VAmax 22(2(11) -
As a result, for any r < {(1)) Amax Amax, 1'-t we have (1())s = 0 and consequently 2
Si(r) n S2(1;t) = 0. As a result, s(t) 2 s(t)) Vmmax d'-t
2/(2(1)-e' Since we have shown s²((')
t' 2 (min ( / Amiin/8111111 1/2 |101)) ///max we have s(t) 2 s(')) Amax 2 min! / / 1/231111
For the third conclusion of the lemma, recall the definition of y(t). Under the assumption that min{ //mia/ /,, 1/2} ||@] 2dmax, we have [lv(t) 0|| Amax > 0 and \max/ Ama)/ A|| s 1/2.
Denote yt(t)= = 0 +
liv(r) e|l (llv(() - A1l - Amaa)). Then
x(t)
l/ (t) 01 I llv(t) 011 x 2 1011.
Il (t) 01 (1 Amax/ / [1v(() 01) (lv(()) 01
y(1) -
(lv(t) D'()) [lv(t) A1| Amax = A.
36

---

Consequently,
(v'(t) -0)- - 0) (v((t (v(() 0)
Amax
2 (u(t) - 1) 0) (v(() - 3) 8)
(tx((t) 011
Amax
Amax
[1y(t) 81 (u(1) 0)² ))())((())) 0)
(lv(t) 811
Amax
(t) 811 (u(() -)0-'=- ()y())((((t) $)
Amax
(tv(t) 011 (Iy(t) 011 Xini
$ - (lv(t) 01
min { V Amin / 1/2) |10||
Denote (t) to be the ball centered at y1(1) with radius (Amin/8) min( mnin(yAmin/Aa /8, 1/23. Then for
any (t), we have
(x 0x - - -)(()))) 0)' (v(()
(v'(1) -
(v(() - ()(=--((()-00)
S - (00-0)">-'(''0 (1)-0)) 0) + 2X 21 min || - 5/ (l/ 011 + X || 50 (1)1
(u(t) - -) (v(() 00)
< min! V Amin/ 8, 1/2] |0|| + 2 || 5/ (1)] (t) - 01l + - 1 1/)0
minf V Amiu/ 8, 1/2] ||0|| + 4x ||> - s/ (t) ||0| + Xmin || 3/ (+))
min / Amin 88 1/2 ||||| + Amin (min / Amin/ /8, 1/2))²
64
00,
where the last inequality holds under the assumption ||0]| 2 Amin min / /..in/.. (tt) C (2(s(t);t) and consequently (tt) C D(t). On the other hand, for any E (t), we have
1/2). Hence,
32
||>||| S ||I - s/ (1)l + (l) - v(O)l + [1(())]
S (Amin/ 8) mint Aminn/ /8, 1/2) + Amax + s(1).
The proof is complete.
Lemma C.10. Assume d 0(). Consider any a + b [k). Assume there exist constants Aminy Ama such that O < Amin I (Ej) I >a(E)) S >max for any j E {a, b). Then SNR' a.b and || are of the same order. When SNR,,, = 01), we have (0,)(0) 2 cffor some constant > 0.
When SNR 2,b - we have
1 + o(1) 0
(0) 2 exp
SNR
8
for any 8 = o(1), we have
1 o(1)
Pa.l() < exp
SNR"? 2
8
Proof. Recall the setting stated Lemma C.9
By the definition of Ban we can take 0 ( Σ = (2 - n [M - and t = log (2:)) -2:)) such that B.
D(t). Due d ((1 and 24), we have that all eigenvalues of Σ are constants and that
log (EX) - - is also constant. Consequently, t is constant. In addition, ||0]] is of the same order | l.
37

---

When | is constant, ||@]] is constant, then SNR",, 6 must be a constant as well. This is because (tt) is the set of points where one density is greater equal to another. Then D(t) is non-empty as both densities have integral 1. Hence, s(t) must finite, meaning SNR is constant. In this case, we have (0) P(n D(t) being constant as well.
When ||S,aol + oo, we have ||0]| - oo. Since all the assumptions needed in Lemma C.9 are satisfied, by its first conclusion, we have s(t) being of the same order ||0]], and consequently being of the same order as || As result, SNR,,, and || are of the same order. In addition, (t) exists and its radius is some constant e₁ > 0. Hence, its volume is V where Va denoted as the volume of d-dimensional unit ball. In addition, for any x Hl),, we have ||a|||| I x()) + = SNR,,, + for some constant > 0. Recall 1j ~ N(0, Ia). Then we have
(0,)(0) 2 P(1 E H())) 2 Vaa min xEM(() V(2T) exp (-2 ||=/||
2 VVa
1 exp
SNR /2 + call²)
/2T)d
+ 0())
SNR"3.
2 exp
8
Now let us consider (d, where d = o(1). We can take 0, Mا same as before, but let t log (E))))))(E3))- 5= (Iz) -' Then we have t' = o(1) |1o| Hence, by Lemma C.9
we have
SNR'' SNR' = (1((t) - s(t') = |t 1'l
o(1) ||l|| o(1)SNR',,
||0||
Hence,
1 - ||=]|3
(o, PP E Bo,((0))
max me aeB,,b(d)
exp
((
1 exp
(8) ||x/|?
min
(2
SNR (0)
V(2r)d
exp
- o(1)
exp
8
38

---

NeurIPS Paper Checklist
Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope?
Question:
Answer:[Yes Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
39

---

Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
40

---

Answer: [No]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https guwdes/ddeeeeee Cooeeeoodeesssseeeeee 7/nips.com /ttp://bbb///iiiiee/eeee/eaaaaaa wwwssnnnnccccyyc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Experiment results averaged. Error bars were inappropriate from visual standpoint.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
41

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer:[No]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:pppp./aacr.....o//////////a
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
The paper carried out foundational and theoretical analysis on clustering which has no direct social impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
42

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
43

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
44


Reviews:
[{"review_id": "KIshrkGx2F", "reviewer": "Reviewer_M7TA", "summary": "The paper provides a minimax lower bound of misclustering error rate for clustering under the anisotropic GMM. Then, the paper designs an adjusted Lloyd's algorithm which can obtain the minimax lower bound within log(n) iterations. The paper also conducts some experiments to show the performance of the proposed method.", "questions": "Please see above.", "limitations": "The paper claimed the limitations.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper tackles a more difficult setting of GMM, i.e., anisotropic GMM. The paper provides the bound of the misclustering error rate in this setting and designs a rate-optimal algorithm, the adjusted Lloyd's algorithm. \n\n2. The paper is theoretically sound and solid.", "weaknesses": "1. My major concern is about its experiments. The paper only conducts experiments on synthetic data sets. In machine learning community, we often care more about the performance on the real-world data sets.\n\n2. In Algorithm 2, it needs to compute the inverse and determinant of the covariance matrices, which seems time-consuming. Could you give the time complexity analysis and experiments on how much the overhead has increased compared to the vanilla Lloyd's algorithm?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your valuable comments and remarks.\n\n> My major concern is about its experiments.\n\nThank you for your comment. We plan to include a new experiment in the final version of our paper using a real dataset from the Fashion-MNIST collection. This experiment will focus on the clustering of two classes, T-shirt/top and Trouser, each comprising 6000 images. Numerical results show that Algorithm 2 achieves a misclustering error rate of 5.7%, which outperforms the vanilla Lloyd’s algorithm (8%). This addition will provide a more comprehensive evaluation of our methods, highlighting their effectiveness in practical scenarios.\n\n> In Algorithm 2, it needs to compute the inverse and determinant of the covariance matrices\n\nThanks for the comment. You are correct in noting that it incurs additional computational overhead due to the necessity of computing the inverse and determinant of covariance matrices. The time complexity of Algorithm 2 is $O(nkd^3T)$, where $n$ is the number of points, $d$ is the dimensionality of each data point, $k$ is the number of clusters, and $T$ is the number of iterations. This contrasts with the vanilla Lloyd's algorithm, which has a lower time complexity of $O(nkdT)$. The increased complexity is primarily due to the matrix operations in $d$ dimensions, which scale as $O(d^3)$ for matrix inversion and determinant computation. To provide a clearer perspective on the performance impact, our experiments show that at a dimensionality of 5, Algorithm 2 requires approximately twice the computation time of the vanilla Lloyd’s algorithm. This ratio increases to approximately 14 when the dimensionality is increased to 100. In the final version of the paper, we will include a detailed time complexity analysis and experimental results to illustrate how the overhead scales with increased dimensionality.", "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": "", "extra_scores": {}}, {"review_id": "k6d20rzjZ9", "reviewer": "Reviewer_yjVp", "summary": "This paper analyzes the minimax error rate in clustering anisotropic Gaussian mixture models. The authors establish a universal lower bound in two different models: different means, same covariance matrix (resp., different means, different covariance matrix) for every cluster and different covariance. For both models, they prove that a simple iterative algorithm (a variant of Lloyd's) attains the minimax rate.", "questions": "* Is the assumption SNR / log k \\gg 1 needed? It seems to appear in the lower bound because of the choice of the space \\mathcal{Z}. Would a more refined analysis delete this assumption? (By this comment, I am specifically referring to the paragraph \"If our goal is only to obtain a lower bound ... there exists a much simpler way\" in [1].) I am not sure if this assumption is needed in the upper bound (for example Lemma A.5 for the ideal error does not seem to require it?). \n\n* Line 42 the sentence: 'From a minimax perspective, the least favorable scenario among all sub-Gaussian distributions with variance proxy \\sigma^2—and thus the most challenging for clustering—is when the errors are distributed as N (0, \\sigma^2 I)\". Does it mean that the SNR obtained in Model 2 is always larger than the SNR of Model 1 (with the same centres \\theta_a but all covariances equal to, say, \\Sigma_1)? \n\n* I am not sure how to obtain the second to last inequality of the inequations starting line 473. I get that Cauchy-Schwarz is applied, but it leads to something slightly different (more precisely, I don't know how to obtain the $\\|| \\sum_{a} 1(z_j = a) \\epsilon_j \\epsilon_j^T \\||$ as Cauchy-Schwarz gives $\\|| \\epsilon_j \\||$. I may miss a simple one-liner showing that $ \\sum_{a} 1(z_j = a)  \\|| \\epsilon_j \\|| = \\|| \\sum_{a} 1(z_j = a) \\epsilon_j \\epsilon_j^T \\||$ . \n\n* I do not understand the last statement \"Future work will explore broader covariance structures and refine these methods to further bridge theoretical robustness with computational feasibility in complex clustering scenarios.\" For the first part of the sentence, I believe Model 2 already encompasses the broadest covariance structure (besides some assumptions of \\Sigma^* being well-conditioned). For the second part, if the authors mean robustness to noise, they should cite recent work addressing this in isotropic Gaussian mixture models (for example [1,2]). \n\nRef: \n\n[1]  Anderson Y. Zhang. Harrison H. Zhou. \"Minimax rates of community detection in stochastic block models.\" Ann. Statist. 44 (5) 2252 - 2280, October 2016. https://doi.org/10.1214/15-AOS1428\n\n[2] Liu, Allen, and Ankur Moitra. \"Robustly learning general mixtures of Gaussians.\" Journal of the ACM 70.3 (2023): 1-53.\n\n[3] Patel, D., Shen, H., Bhamidi, S., Liu, Y., & Pipiras, V. (2023). Consistency of Lloyd's Algorithm Under Perturbations. arXiv preprint arXiv:2309.00578.", "limitations": "* Albeit this is already a long and dense paper, I would have enjoyed a section motivating anisotropic mixture models in real-data examples. For example: standard Lloyd versus Algorithm 1 versus Algorithm 2. I believe Algorithm 2 obtains a higher accuracy in large data sets, but may not in smaller data sets (where the estimation of the covariance) may lead to less reliable predictions. Having (even heuristics) guidelines on which algorithm one should use depending on the data set size is important. \n\n* While I went quite far down the proof, I found them hard to read. Appendix C is just a dump of technical Lemmas over 17 (!!) pages with no structure. Come on, this is not really serious...", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Strong paper. The technical proofs are impressive and the results quite general with a minimum amount of assumptions (clusters all not too small, dimension O(\\sqrt(n)), covariances well conditioned; the only strong assumption is over the initialisation).", "weaknesses": "* The paper misses some high-level intuition, and several proofs are tough to parse. For example, the error decomposition with the terms F, G, H etc appears mysterious and a bit out of nowhere. While the ideal error has a natural explanation (at least when delta = 0), I did not find it properly mentioned. For example, line 435 embodies exactly my feeling while reading the proofs: \"We next define a quantity that refers to as the ideal error\"; yes this quantity is important, yet I do not tell explicitly why and I leave the reader to understand himself why this is indeed an ideal error. \n\n* The interpretation of the minimax rate for model 2 is quite complex. Because it involves hypothesis testing, one should naively expect to find the Chernoff information. Quick computations show that the Chernoff information between N( $\\theta_1, \\Sigma$ ) and N( $\\theta_2, \\Sigma$ ) equals  $ 1 / 8 \\times \\|| \\theta_1 - \\theta_2 \\||^2_{\\Sigma}$  and indeed recovers the minimax rate of Model 1. Expression is more complex for Model 2. That could help interpret the quantity SNR' (which is not truly a signal-to-noise ratio, as it is hard from the expression of SNR'_{ab} to find where is the signal, the noise and the ratio...). \n\n* The assumption on the loss of the initialisation is quite strong (\\hat z^{(0)} should already be a consistent estimator). Especially, the authors consider spectral clustering, which does not scale as well as iterative methods such as Lloyd's. Moreover, spectral clustering is rate-optimal in an isotropic mixture model. A natural question is: what happens if one takes the best over 10 runs over random initialisation \\hat z^{(0)} (or something more clever such as k-means++)? Numerical simulations could show whether a strong condition on the initialisation is indeed needed or not. In particular, Paper [1] had weaker conditions on the initialisation (but stronger conditions on everything else). \n\n* In large dimensions (say d >> n), the lower bound derived here cannot be attained by algorithms agnostic on the model parameters. While this is obviously out of the scope of the paper, the authors should mention it more clearly (key reference 14 is a bit diluted in the intro, other recent work such as [2], albeit posterior to the author's submission, could also appear).  \n\n[1] Lu, Y., & Zhou, H. H. (2016). Statistical and computational guarantees of Lloyd's algorithm and its variants. arXiv preprint arXiv:1612.02099.\n\n[2] Even, B., Giraud, C., & Verzelen, N. (2024). Computation-information gap in high-dimensional clustering. arXiv preprint arXiv:2402.18378.\n\n\nMinor comments:\n* line 377: \"where we use k = O(1)\". No, you use SNR / log k >> 1.\n* Typo in line 189: the with probability 1-exp(-0.08) should be 1-exp(-0.08n) according to [12, Proposition D.1]. This typo appears several times (Corollary 2.1, 3.1 at least) and is important to correct. \n* line 290: I assume the log is in basis 10. \n* Line 641: typo in the ref.\n* Line 661: I don't think the SE(a,b) is properly defined (namely, a proper definition to explain what the a and b in SE(a,b) exactly stands for).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your valuable comments and remarks.\n\n> The paper misses some high-level intuition, and several proofs are tough to parse.\n\nThanks for pointing this out. In the final version, we will enhance our discussion to better articulate the derivation and significance of key terms. The \"ideal error\" is defined as the error remaining after one algorithm iteration with known ground truth $z^*$. It represents the minimum error under ideal conditions. The actual error emerges when iterating from an estimation $z$, with the difference between actual and ideal errors expressed through the terms $F$, $G$, and $H$:\n$F$ includes terms related to noise $\\epsilon_j$, illustrating the impact of measurement noise.\n$G$ covers estimation errors for cluster centers ($\\hat{\\theta}_a(z) - \\hat{\\theta}_a(z^*)$) and covariance matrices ($\\hat{\\Sigma}(z) - \\hat{\\Sigma}(z^*)$), showing the effect of parameter estimation inaccuracies.\n$H$ contains all other terms from additional error sources.\n\n> The interpretation of the minimax rate for model 2 is quite complex.\n\nThanks for the suggestion. We will include connections with Chernoff information in the final version to clarify the understanding of the minimax rate. Regarding SNR', although it diverges from the traditional signal-to-noise ratio, we use this term as it extends the classical definition $ \\frac{||\\theta_1^* - \\theta_2^*||^2}{\\sigma^2}$ in the context of isotropic Gaussian noise.\n\n> The assumption on the loss of the initialization is quite strong\n\nWe acknowledge that this assumption appears strong; it is primarily driven by technical challenges encountered in our analytical framework.\n\n> In large dimensions (say d >> n), the lower bound derived here cannot be attained\n\nYou are correct that our paper does not cover the large dimensional case. In the final version, we will add more comments and references to make it clearer.\n\n> Minor comments\n\nThank you and we will correct them in the final version.\n\n> Is the assumption SNR / log k \\gg 1 needed?\n\nThank you for the question. On one hand, this condition helps simplify the complexity for establishing the lower bound. As noted in the literature you referenced, a more refined analysis might allow us to relax this assumption to simply $\\text{SNR} \\gg 1$. On the other hand, this condition is essential to establish a matching upper bound. The ideal error analysis does not explicitly require this assumption; however, it becomes necessary when considering the aggregate impact of errors $F$, $G$, and $H$. These components introduce multiple factors of $k$ that appear before the desired exponential term, and the assumption ensures that these factors remain negligible.\n\n> Line 42 the sentence:\n\nThank you for the question. To address it, consider a simpler case with two Gaussian distributions: whether the SNR calculated from $N(\\theta^*_1, \\Sigma^*_1)$ and $N(\\theta^*_2, \\Sigma^*_2)$ is always larger than that from $N(\\theta^*_1, \\Sigma^*_1)$ and $N(\\theta^*_2, \\Sigma^*_1)$. In this case, the answer to your question is not necessarily yes, as demonstrated by the following counterexample. When $\\theta^*_1=(0,0)$, $\\theta^*_2=(1,0)$, $\\Sigma^*_1 = I_2$ and $\\Sigma^*_2$ is a diagonal matrix with 2 in its (1,1) entry and 1 in its (2,2) entry, one can verify SNR is not larger. In fact, the effect of replacing $\\Sigma^*_2$ with $\\Sigma^*_1$ on SNR depends on the shapes of $\\Sigma^*_1$ and $\\Sigma^*_2$ and the direction of $\\theta^*_2 - \\theta^*_1$. This is different from the sub-Gaussian setting. The rationale why $N(0, \\sigma^2 I_d)$ leads to the smallest SNR among sub-Gaussian distributions with variance proxy $\\sigma^2$ is that it is flatter in all directions compared to any other sub-Gaussian distribution.\n\n> I am not sure how to obtain the second to last inequality of the inequations starting line 473. \n\nThe inequality does not result directly from Cauchy-Schwarz. Instead, it first formulates a quadratic form and then upper bounds it by the operator norm of the matrix. Let $x$ be a vector. The inequality is essentially about showing $\\sum_j |\\epsilon_j^Tx|^2$ can be upper bounded by $||x||^2 ||\\sum_j \\epsilon_j \\epsilon_j^T||$. This can be proved by\n$\\sum_j |\\epsilon_j^Tx|^2 = \\sum_j (x^T\\epsilon_j)(\\epsilon_j^T x) = \\sum_j x^T(\\epsilon_j \\epsilon_j^T)x = x^T(\\sum_j \\epsilon_j \\epsilon_j^T)x \\leq ||x||^2 ||\\sum_j \\epsilon_j \\epsilon_j^T||$. In the final version, we will add this intermediate argument.\n\n> I do not understand the last statement \n\nThanks for the feedback. We agree it needs clarification. Our intent was to indicate a potential relaxation of the well-conditioned assumption on the covariance matrices' condition numbers. In the final version we will make it clearer.\n\n> Albeit this is already a long and dense paper, I would have enjoyed a section\n\nThank you for your suggestion. In the final version of the manuscript, we will incorporate a new section dedicated to evaluating the performance of the algorithms on real datasets. This section will also include practical guidelines for practitioners on selecting the most suitable algorithm. \n\n> While I went quite far down the proof, I found them hard to read. \n\nThanks for the comment. In the final version, we will add more details to make the proof more accessible. For example, in Appendix C, we will give an overview of lemmas to be proved.", "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": "", "extra_scores": {}}, {"review_id": "BapUjatVn6", "reviewer": "Reviewer_LL3K", "summary": "This paper states an hard-association EM algorithm for Gaussian mixture estimation, where the Gaussian components can be different and anisotropic. They also state theoretic bounds of the misclustering error rate.", "questions": "What about individual weights (mixing proportions) of the Gaussian components? E.g. from line 271, must the 30 clusters each have 1200/30=40 samples?", "limitations": "Limitations are stated but maybe should be summarized in a dedicated section.\n- \"decent\" initial guess required. What does that mean? Were you able to reliably get the rate-optimal result without taking into account prior knowledge about the ground truth? At least state the qualitative dependencies, like \"decent\" initial guesses are more restricted for lower SNR / overlapping components, fewer samples, higher dimensions, more components etc.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Originality: The theoretical association bound for different and anisotropic clustering is novel.\n\nQuality: Contribution is technically sound. Claims are very well supported by theoretical analysis and also some experimental results. Methods used are appropriate. It is a complete piece of work.\n\nClarity: Submission is clearly written and well organized. It adequately informs the reader and states the proposed algorithms in concise form to be easily reproduced.\n\nSignificance: Key contribution to the community are the theorems and very detailed and elaborate proofs about the error rate that can theoretically achieved in anisotropic clustering. Overcoming the constraint of isotropic components (or anisotropic but identical components) is a major step.", "weaknesses": "Originality: A related work is \"Frisch, Hanebeck, Gaussian Mixture Estimation from Weighted Samples\" (not telling you to include this, just check if it's relevant; its soft-EM algorithm may be similar to your hard-EM).\n\nSuggestions:\n- in Line 108 give some inutition about the loss function, e.g. \"ratio of mis-associations\".\n- mention that Model 1 is equivalent to isotropic components in linearly transformed space with root of covariance (if that's correct)\nTypos:\n- line 102 displayed as follow*s*\n- line 136: \"Figure 1\" should be in same line, use \\sim or cleveref package\n- line 150 computational*ly* feasible\n- Theorem (and elsewhere): too big whitespace in \"exp (\". Use \"exp\\!(\" or \\mathopen{}, \\mathclose{} instead.\n- SNR has a non-math font in formulas and is sometimes italic and sometimes not\n- References: check capitalization, e.g. [11] PCM etc. I recommend:\n\\usepackage[style=numeric-verb, maxbibnames=20, sorting=none, eprint=false]{biblatex}", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your valuable comments and remarks.\n\n> Originality: A related work is\n\nThank you for pointing this out. Our hard-EM algorithm indeed shares similarities with the soft one. Specifically, our algorithm modifies the E-step of the soft-EM by implementing a maximization step that hard assigns data points to clusters instead of calculating probabilities. We will make this clearer in the final version of the paper.\n\n> Suggestions:\n\nThank you for pointing these out. We will surely address them in the final version.\n\n> What about individual weights (mixing proportions) of the Gaussian components?\n\nIn our numerical study, we initially opted for equal cluster sizes for simplicity, but our model and analysis are fully capable of accommodating variable cluster sizes. To better demonstrate the flexibility and applicability of our approach, we will have a variety of cluster sizes in the numerical settings in the final version of the paper.\n\n> \"decent\" initial guess required\n\nThank you for the question. In our manuscript, the term 'decent initial guess' refers to the need for initial cluster centers to be sufficiently close to the ground truth so that our algorithm achieves the rate-optimal result. It is due to that our theoretical analysis requires the initialization being within a specific proximity to the true parameters. In the final version of our paper, following your suggestion, we will explicitly detail the dependencies to provide a clearer understanding of when and how our algorithm can be expected to perform optimally.", "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": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank all reviewers for their detailed and insightful comments. Each reviewer has provided valuable feedback from different perspectives. In recognition of this, we respond to each reviewer's comments individually to ensure that all concerns and suggestions are thoroughly addressed.

Meta-review: The paper presents a detailed theoretical analysis of the performance of clustering solutions arising from a modified variant of Lloyd's algorithm for data arising from Gaussian Mixture Models (GMMs) with anisotropic and potentially differing covariance matrix/matrices. Such results are scarce in the clustering literature and the reviewers unanimously appreciate the theoretical contributions. Limitations identified by the reviewers include a lack of experimental results on real data sets and a lack of intuitive discussion of the theory, but the authors have committed to including experiment(s) on real data in a revised version, and to enhance the readability/accessibility of the theoretical content.
Decision: Accept (oral)