Toward Global Convergence of Gradient EM for Over-Paramterized Gaussian Mixture Models
Authors: Weihang Xu
Maryam Fazel
Simon Shaolei Du
Venue: NeurIPS 2024 poster (2024)
Keywords: over-parameterization
global convergence
non-convex optimization
Primary area: learning_theory
TL;DR: We give the first global convergence of gradient EM for over-parameterized Gaussian mixture models when the ground truth is single Gaussian.

Abstract: We study the gradient Expectation-Maximization (EM) algorithm for Gaussian Mixture Models (GMM) in the over-parameterized setting, where a general GMM with $n>1$ components learns from data that are generated by a single ground truth Gaussian distribution. 
While results for the special case of 2-Gaussian mixtures are well-known, a general global convergence analysis for arbitrary $n$ remains unresolved and faces several new technical barriers since the convergence becomes sub-linear and non-monotonic. To address these challenges, we construct a novel likelihood-based convergence analysis framework and rigorously prove that gradient EM converges globally with a sublinear rate $O(1/\sqrt{t})$. This is the first global convergence result for Gaussian mixtures with more than $2$ components. The sublinear convergence rate is due to the algorithmic nature of learning over-parameterized GMM with gradient EM. We also identify a new emerging technical challenge for learning general over-parameterized GMM: the existence of bad local regions that can trap gradient EM for an exponential number of steps.

Toward Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixture Models
Weihang Xu University of Washington xuwh@cs washington, edu
Maryam Fazel University of Washington mf azel edu
Simon S. Du University of Washington ssduêcs washington edu
Abstract
We study the gradient Dnpectation-MMxxiizaalie (EM) algorithm for Gaussian Mixture Models (GMM) in the over parameterized setting, where a general GMM with > components learns from data that are generated by a single ground truth Gaussian distribution. While results for the special case of 2- 2-Gaussian mixtures are well-known, general global convergence analysis for arbitrary n remains unresolved and faces several new technical barriers since the convergence becomes sub-linear and non-monotonic. To address these challenges, we construct a novel likelihoodd-bal
convergence analysis framework and rigorously prove that gradient EM converges globally with sublinear rate O (f). This is the first global convergence result for Gaussian mixtures with more than components. The sublinear convergence rate is due to the algorithmic nature of learning over- parameterized GMM with gradient EM. We also identify new emerging technical challenge for learning general parameterrie GMM: the existence of bad local regions that can trap gradient EM for an exponential number of steps.
1 Introduction
Learning Gaussian Mixture Models (GMM) is a fundamental problem in machine learning with broad applications. In this problem, data generated from a mixture of n > 2 ground truth Gaussians are observed without the label (the index of component Gaussian that data is sampled from), and the goal is retrieve the maximum likelihood estimation of Gaussian components. The Expectation Maximization (EM) algorithm is arguably the most widely-usee algorithm for this problem. Each iteration of the EM algorithm consists of two steps. In the expectation (E) step, it computes the posterior probability of unobserved mixture membership label according to the current parameterized model. In the maximization (M) step, computes the maximizer of the Q function, which the likelihood with respect to posterior estimation of the hidden label computed in the E step.
Gradient EM, as popular variant of EM, is often used in practice when the maximization step of EM is costly or even intractable. It replaces the M step of EM with taking one gradient step on the Q function. Learning Gaussian Mixture Models with EM/gradient EM is an important and widely-studied problem. Starting from the seminal work [Balakrishnan et al., 2014]. a flurry of work Daskalakis et al. [2017], Xu al. [2016], Dwivedi et al. [2018a]. Kwon and Caramanis [2020], Dwivedi et al. [2019] have studied the convergence guarantee for EM/gradient EM in various settings. However, these works either only prove local convergence, or consider the special case of 2-Gaussian mixtures. A general global convergence analysis of EM/gradient EM on n-Gaussiia mixtures still remains unresolved. Jin et [2016] is notable negative result in this regard, where the authors show that on GMM with n 2 3 components, randomly initialized EM will get trapped in a spurious local minimum with high probability.
Over- parameteeiee Gaussian Mixture Models. Motivated by the negative results, a line of work considers the per-parameterized setting where the model uses more Gaussian components than
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the ground truth GMM, in the hope that it might help the global convergence of EM and bypass the negative result. In such werrparameterize regime, the best that people know so far is from [Dwivedi et al., 2018b]. This work proves global convergence of 2-Gaussian mixtures on one single Gaussian ground truth. The authors also show that EM has a unique sub-linear convergence rate in this paramettaaee setting (compared with the linear convergence rate in the ssact-parameterized setting [Balakrishnan et al., 2014]). This motivates the following natural open question:
Can we prove global convergence of the EM/gradient EM algorithm on general n-- n-Gaussian mixtures in the over-parameterized regime?
In this paper, we take a significant step towards answering this question. Our main contributions can be summarized as follows:
We prove global convergence of the gradient EM algorithm for learning general n-compooent GMM on one single ground truth Gaussian distribution. This is, to the best our knowledge, the first global convergence proof for general n-component GMM. Our convergence rate is sub-linear, reflecting an inherent nature of over peer-paramteriieed GMM (see Remark 3 for details).
We propose a new analysis framework that utilizes the likelihood function for proving convergence of gradient EM. Our new framework tackles several emerging technical barriers for global analysis of general GMM.
We also identify a new geometric property of gradient EM for learning general n-component GMM: There exists bad initialization regions that traps gradient EM for exponentially long, resulting in an inevitable exponential factor in the convergence rate of gradient EM.
1.1 Gaussian Mixture Model (GMM)
We consider the canonical Gaussian Mixture Models with weights π = ( TT) EE TI = 1), means μ = [4T] ....,
.......,,.... p..) ) and unit covariance matrices Ia in d-dimensional space. Following a widely-studied setting [Balakrishnan et al., 2014. Yan et al., 2017, Daskalakis et al., 2017]. we set the weights π and covariances Ta in student GMM as fixed, and the means (μ1 Pn as trainable parameters. We use GMM(μ) to denote the GMM model parameterized by μa, which can
be described with probability density function (PDF) Pp. Rd R20
| pill3
||
(1(
Σ
ToO( Ia)
Σ (2m)) iE(n)
d/2 exp
VE(N)
where 6011u, Σ) is the PDF of N E),
Tn 1, 0, Vi
[n]]
1.2 Gradient EM algorithm
The EM algorithm is one of the most popular algorithms for retrieving the maximum likelihood estimator (MLE) on latent variable models. In general, EM and gradient EM address the following problem: given a joint distribution py- (ar, y) of random variables 2; y parameterized by j observing only the distribution of z, but not the latent variable the goal of EM and gradient EM is to retrieve the maximum likelihood estimator
jAMLE arg max log (r))
The focus of this paper is the non-convex optimization analysis, so we consider using population gradient EM algorithm to learn GMM (1), where the observed variable is x E R. and latent variable the index of membership Gaussian GMM. We follow the standard teacher-student setting where a student model GMM(μ) with n 2 2 Gaussian components learns from data generated from a ground truth teacher model GMM( We consider the over-parameterized setting where the ground truth model GMM(H") ) is a single Gaussian distribution N(4" Ia), namely μ²' = (1 then further assume w.l.o.g. that μr" O. Our problem could be seen strict generalization of Dwivedi et al. [2018b], where they studied using mixture model of two Gaussians with symmetric means (they set constraint μ12 - learn one single Gaussian.
11" DT.. We
At time step = 0, 2, 2,..... given with parameters p(()) = (11 (1) ,...,Pn( (1) TT. population gradient EM updates μ via the following two steps

---

E step: for each E [n)], compute the membership weight function dy R 7 R defined as
|
exp
(+)l)((t)) Pr[i[z]
EnE(n) TA exp
||z (0112
M step: Define (()) as (()) = Bg-A((0.L))
Σ (x(()/(()) | 1s/13
Gradient EM with step size 1j > 0 performs the following update:
14(t + 1) = (t( - 7 vu. ((p(t))(((t = pa(t) (000)--Eeaswwe 7. (z) - x)].
(3)
The membership weight function - (1: (z. represents the posterior probability of data point being sampled from the 1th Gaussian of GMM(H). For ease of notation, we sometimes simply write (1((2)11)) (4) (z) when the choice of μ4 is obvious.
1.3 Loss function of gradient EM
Since the task of gradient EM is to find the MLE over ground truth distribution Pμr, we can define the MIE loss function for gradient EM as
Pk- (x) )}
Pm
(()) = DxL I1pp)) -E
log
The loss C is the Heilbbcck-Leiblee (KI.) divergence between the ground truth GMM and the student model GMM. Since finding MLE is equivalent to minimizing the KL. divergence between model and the ground truth, the goal of gradient EM is equivalent to finding the global minimum of loss L. In other words, proving that gradient EM finds the MLE is equivalent with proving the convergence of to O. However, we are going to present another reason why loss function L is important, for is also closely related to the dynamics of gradient EM.
Gradient EM gradient descent on L. We present the following important observation. The proof is deferred to appendix.
Fact For any μ. VQ(ulu) VL))).
Fact states that the gradient of Q function that gradient EM optimizes in each iteration identical to the gradient of loss function C. This observation is very useful since it implies that gradient EM equivalent to gradient descent (GD) algorithm on This observation is not new discovery of ours but actually a wide-spread folklore (see [Jin et al., 2016]). However, our new contribution is to observe Fact is very helpful for analyzing gradient EM, and to construct a new convergence analysis framework for gradient EM based on it.
1.4 Notation
In this paper, we adopt the following notational conventions. We denote (1,2...., with [n]] E R denotes the parameter vector of GMM obtained by concatenating Gaussian mean vectors p together. For any vector μ4, p(t) denotes its value at time step i, sometimes we omit this iteration number / when its choice is clear and simply abbreviate uu()) as μ.. We define a shorthand of expectation taken over the ground truth GMM E as E,[-] For any vector v * O, we use = v/|lu|l to denote the normalization of We define (with slight abuse of notation) imax == arg max (I] as the index of μ4 with the maximum norm, and Amax : |||6 max {l]ma]] | as the maximum norm of μę. In particular, Amax (t) max ( [1/a (1)l,, (1ll--.))ll,, Similarly, Tmin = minggin] n. and Tmax == maxie[n] n, denotes the minimal and maximal Hi, respectively. We Vn, L to denote the gradient of μ4 on L, and _T.....
VL (V,, L ..... V,., L) denotes the collection of all gradients. Finally we define potential
function U Rnd + R for GMM(H) as
U(p)= Σ 11
iE|m]
3

---

1.5 Technical overview
Here we provide a brief summary the major technical barriers for our global convergence analysis and our techniques for overcoming them.
New likelihood- based analysis framework. The traditional convergence analysis for EM/gradient EM in previous works Balakrishnan et al. [2014], Yan et al. [2017]. Kwon and Caramanis [2020] proceeds by showing the distance between the model and the ground truth GMM in the parameter space contracts linearly in every iteration. This type of approach meets new challenges in the over-parameterized n-Gaussian mixture setting since the convergence both sub-linear and non- monotonic. To address these problems, we propose a new likelihood- framework: instead of proving the convergence of parameters, our analysis proceeds by showing the likelihood loss function L converges to O. The new analysis framework is more flexible and allows us to overcome the aforementioned technical barriers.
convergence analysis
Gradient lower bound. The first step of our global convergence analysis constructs a gradient lower bound. Using some algebraic transformation techniques, we convert the gradient projection (C(u), (1) into the expected norm square of random vector (b(x). (See Section (4) for the full definition). Although lower bounding the expectation of sb very challenging, our key idea that the gradient of &p has very nice properties and can be easily lower bounded, allowing us to establish the gradient lower bound.
Local smoothness and regularity condition. After obtaining the gradient lower bound, the missing component of the proof is a smoothness condition of the loss function L. Since proving the smoothness of L is hard in general, we define and prove weaker notion of local smoothness, which suffices to prove our result. In addition, we design and use an auxiliary function U to show that gradient EM trajectory satisfies the locality required by our smoothness lemma.
2 Related work
2.1 2-Gaussian mixtures
There is vast literature studying the convergence of EM/gradient EM on 2-component GMM. The initial batch of results proves convergence within infinitesimally small local region [Xu and Jordan, 1996, Ma et al., 2000]. Balakrishnan et al. [2014] proves for the first time convergence of EM and gradient EM within non-infinitesimal local region. Among the later works on the same problem, Klusowski and Brinda [2016] improves the basin of convergence guarantee, Daskalakis et al. [2017], Xu et al. [2016] proves the global convergence for 2-Gaussian mixtures. These works focused on the exact- saauttpprrmmeteizzation scenario where the number of student mixtures is the same as that of the ground truth. More recently, Wu and Zhou [2019] proves global convergence of 2-component GMM without any separation condition. Their result can be viewed as a convergence result in the wwerpparaeetrrized setting where the student model has two Gaussians and the ground truth is single Gaussian. On the other hand, their setting is more restricted than ours because they require the means of two Gaussians in the student model be symmetric around the ground truth mean. Weinberger and Bresler [2021] extends the convergence guarantee to the case of unbalanced weights. Another line of work Dwivedi al. [2018b, 2019, 201 2018a] studies the wwer-paaameterized setting of using 2- Gaussian mixture to learn single Gaussian and proves global convergence of EM. Our result extends this type of analysis to the general case of n-Gaussian mixtures, which requires significantly different techniques. We note that going beyond Gaussian mixture models, there are also works studying EM algorithms for other mixture models such as a mixture of linear regression Kwon et al. [2019].
2.2 N-Gaussian mixtures
Another line of results focuses on the general case of Gaussian mixtures. Jin al. [2016] provides a counter-example showing that EM does not converge globally for n. > 2 (in the xxact-parameterized case). Dasgupta and Schulman [2000] prove that variant of EM converges to MLE in two rounds for n-GMM. Their result relies on modification of the EM algorithm and is not comparable with ours. [Chen et al., 2023] analyzes the structure of local minima in the likelihood function of GMM. However, their result is purely geometric and does not provide any convergence guarantee.

---

A series of paper Yan et al. [2017], Zhao et al. [2018], Kwon and Caramanis [2020], Segol and Nadler follow the framework proposed by Balakrishnan al. [2014] to prove the local convergence EM for n-GMM. While their result applies to the more general n-Gaussian mixture ground truth setting. their framework only provides local convergence guarantee and cannot be directly applied to our setting.
2.3 Slowdown due to over-parameterization
This paper gives an O (1/vI) bound for fitting over-parameterized Gaussian mixture models to a single Gaussian. Recall that to learn single Gaussian, if one's student model is also a single Gaussian, then one can obtain an exp(- (())) rate because the loss is strongly convex. This slowdown effect due to over parameterrizaiinn has been observed for Gaussian mixtures in Dwivedi et al. [2018a], Wu and Zhou [2019], but has also been observed in other learning problems, such as learning a two-layer neural network Xu and Du [2023], Richert et al. [2022] and matrix sensing problems [Xiong et al., 2023, Zhang et al., 2021, Zhuo et al., 2021].
3
Main results
In this section, we present our main theoretical result, which consists of two parts: In Section 3.1 we present our global convergence analysis of gradient EM, in Section 3.2 we prove that an exponentially small factor in our convergence bound is inevitable and cannot be removed. All omitted proof' are deferred to the appendix.
3.1 Global convergence of gradient EM
We first present our main result, which states that gradient EM converges to MLE globally.
Theorem (Main result). Consider training a student n-component GMM initialized from (0(0)
(0) (..)) TT to learn a coole-commpoeet ground truth GMM ( Ia) with population
gradient EM algorithm. If the step size satisfies 1j S SSO converges globally with rate
n2 exp( (up(-8U(())))) (0)) min
Pemaz (0) Mimax (0))² ).
then gradient EM
((P(I) S
VAL
where 7 = 12 1exp(-16U 160 minn (1++ dn)y
E RRR. Recall that Pmax (0) = max max (O)Il,.. Ia, (0)I)
and (0) Eve(n) (0) are two initialization constants.
Remark 3. Without over-parameterization. for learning a single Gaussian, one can obtain a linear convergence exp(-S2 (t)). We would like to note that the sub-linear convergence rate guarantee of gradient EM stated in Theorem 2 (L(p(t))
O(1/v//ll) ()) due the inherent nature of the algorithm. Dwivedi et al. [2018b] studied the special case of using Gaussian mixtures with symmelric means to learn single Gaussian and proved that EM has sublinear convergence rale when the weights Ti are equal. Since Theorem 2 studies the more general case of Gaussian mixtures, this type of subexponential convergence rate the best than we can hope for.
Remark 4. The convergence rate in Theorem 2 has a factor exponentially small in the initialization scale (7
(0(())66))) We would like stress that this is again due algorithmic nature of the problem rather than the limitation of analysis. In Section 3.2, we prove that there exists bad regions with exponentially small gradients that when initialized from such region, gradient EM gets trapped locally for exp(S((U(O)) number of steps. Therefore, a convergence speed guarantee exponentially small U (0) is inevitable and cannot be improved.
Remark 5. Theorem 2 is fundamentally differrnt from convergence analysis for EM/gradient EM in previous works Yan et al. [2017], Dwivedi et al. [2019]. Balakrishnan et al. [2014] which proved monotonic linear contraction of parameter distance p|((t) - 1l But our result also implies global convergence since loss function L converging 0) is equivalent to convergence of gradient EM to MLE.
The convergence result in Theorem 2 is for population gradient EM, but it also implies global convergence for sample-based gradient EM as the sample size tends to infinity. For a similar reduction from population EM to sample EM, see Section 2.2 of [Xu et al., 2016).
Remark 6.
5

---

3.2 Necessity of exponentially small factor in convergence rate
In this section we prove that factor exponentially small in initialization scale (())())(U()))) is inevitable in the global convergence rate guarantee of gradient EM. Particularly, we show the existence bad regions such that initialization from this region traps gradient EM for exponentially long time before final convergence. Our result is the following theorem.
Theorem 7 (Existence of bad initialization region). For any n 2 3. define p( =
(iT (0),...,,4,, (0)) as follows: 11 (0) 12 ( 12y -2ydde,, (3(() =.... Un (0) = 0, where e is a standard unit vector. Then population gradient EM initialized with means (0) and equal weights T
1/n will be trapped in a bad local region around (a( for
exponentially long time
30n ed exp(@(U(())).
301
More rigorously, for any < S1ST, [ni] such that
[|x(())] 2 10vd.
Theorem 7 states that, when initialized from some bad points (0),, after exp(O(U(O))) number of time steps, gradient EM will still stay in this local region and remain 10yd d distance away from the global minimum μ = Therefore an exponentially small factor convergence rate is inevitable.
Remark 8. Theorem eliminates the possibility of proving any polynomial convergence rate of gradient EM from arbitrary initialization. However, it is still possible to prove that, with some specific smart initialization schemes, gradient EM avoids the bad regions stated in Theorem 7 and enjoys polynomial convergence rate. We leave this as an interesting open question for future analysis.
Proof overview
In this section, we provide technical overview of the proof in our main result (Theorem 2 and Theorem 7).
4.1 Difficulties of a global convergence proof and our new analysis framework
Proving the global convergence of gradient EM for general r--aausian mixture is highly nontrivial. While there have been many previous works [Balakrishnan et al., 2014, Yan et al., 2017, Dwivedi et al., 2018b] studying either local convergence or the special case of 2-Gaussian mixtures, they all focus on showing the contraction parametric error. Namely, their proof proceeds by showing the distance between the model parameter and the ground truth contracts, usually by fixed linear ratio, in each iteration of the algorithm. However, this kind of approach faces various challenges for our general problem where the convergence is both sublinear and non-monooniic. Since the convergence rate is sublinear (see Remark 3), showing a linear contraction per iteration is no longer possible. Since the convergence is non-monotonicl, also cannot show strictly decreasing parametric distance.
To address these challenges, we propose new convergence analysis framework for gradient EM by proving the convergence of likelihood C instead of the convergence of parameters μ. There several benefits for considering the convergence from the perspective of MLE loss L. Firstly, naturally addresses the problem of non-monotonic and sub-linear convergence since we only need to show decreases as the algorithm updates. Also, since gradient EM is equivalent with running gradient descent loss function L (see Section 1.3), apply techniques from the optimization theory of gradient descent to facilitate our analysis.
4.2 Proof ideas for Theorem 2
We first briefly outline our proof of Theorem 2.
Proof roadmap. Our proof of Theorem consists of three steps. Firstly, we prove gradient lower bound for L (Theorem 12). Then we prove that the MLE C is locally smooth (Theorem 13). Finally,
'To see this, consider n = 2, μ1 = 0, = (1, O, .,.,,....01 .TT then the norm of strictly increases after one iteration.

---

we combine the gradient lower bound and the smoothness condition to prove the global convergence of L with mathematical induction.
Step 1: Gradient lower bound.
Our first step aims to show that the gradient norm of C(u) is lower bounded by the distance of μ to the ground truth. To do this, we need a few preliminary results. Inspired by Chen et al. [2023], we use Stein's s identity [Stein, 1981] to perform an algebraic transformation of the gradient. Recalling the definition of vo in (2), we have the following lemma.
Lemma 9, For any GMM( i [n], the gradient of Q satisfies
V Vu = Pm:Q(ulp) = Ex (i(x)
Σ
(
The gradient expression above is equivalent with the form (3), but is easier to manipulate. Using the transformed gradient in Lemma 9, we have the following corollary.
Corollary 10. Define vector ())( Eigio (x())) For any GMM(p), the projection of the gradient of V C(s) onto satisfies
Σ (() E. ( 3Eim]
(VL()) = -VV)))a) (V
Corollary 9 is important since it converts the projection of gradient VL(u) onto fe to the expected norm square of vector n. Since lower bound of the gradient projection implics lower bound of
the gradient, we only need construct lower bound for (VL(u), u) = E, 1 ||
Since
(x) is always non-negative, we already know that the gradient projection is non-negative. But lower bounding E.
is still highly nontrivial since the expression of vp is complicated ( |"]
and hard to handle. However, key observation is that, although i itself is hard to bound, its gradient has nice properties and can be handled gracefully:
Vabp(())
Σ (1())))()((4 15)00- 15) (.j(())
(5)
The gradient (5) is nicely-behaved. One immediately from (5) that the matrix V V (x) is positive-semi Sestive-semi-definite and its eigenvalues can be directly bounded. To utilize these properties, we use the following algebraic trick to convert the task of lower bounding v itself into the task of lower bounding its gradient.
E (1) (x) - E, [(__) ||]|| Vuh (tr))adt -.
(6)
Recall that = See detailed derivation in (23). Using (5), combined with the properties of Varbya (2r), we can obtain the following lemma (Recall that U Eiejo [Ipx|[P.):
|
Lemma 11. For any GMM( we have
exp (-8U)
Eg [+0]]()))]]]]]] 2 40000d(1 2pmax Vdj
Σ
1zll?
(.jE(m)
top of Lemma 11, we can easily lower bound the gradient projection in the following lemma, finishing the first step of our proof.
7

---

Lemma 12 (Gradient projection lower bound). For any GMM(p) we have
exp (-8U) Tinn
( = Ex
(d(1 [1 + Mmax v dd2 Pinax
Step 2: Local smoothness.
To construct global convergence analysis for gradient-based methods, after obtaining a gradient lower bound, we still need to prove the smoothness of loss L. (Recall that global smoothness of function means that there exists constant C' such that fx1)) V (22))l S C'|æ11 -|ll,, Vx,, x2.) However, proving the smoothness for C in general is very challenging since the membership function t cannot be bounded when μ unbounded. To address this issue, prove that L is locally smooth, i.e., the smoothness between two points μ and j is satisfied both || and || μ'll are upper bounded. Our result is the following theorem.
Theorem 13 (Local smoothness of loss function). At any two points μ (Nī ...... MTT and 1 ((1) 81) ..... (Jin + 6n) )T)
1
||6.1| S max {6d, 211
E [n],
then the loss function C satisfies the following smoothness property: for any E [n]] we have
[V + C(u vn.C(u)) S 1MMaa (30V 31
4fmmax )1 | +
|
kE[m)
Step 3: putting everything together.
Given the gradient lower bound and the smoothness condition, we still need to resolve two remaining problems. The first one is that the gradient lower bound in Lemma 12 is given in terms of μ,, which we need to convert to a lower bound in terms of L(4). For this we need the following upper bound of L.
Theorem 14 (Loss function upper bound). The loss function can be upper bounded
((p)
Σ iE(m]
|ps 1
Munax
2
The second problem is that our local smoothness theorem requires 4s to bounded, therefore we need to show a regularity condition that for each i, (t(() stays in a bounded region during gradient EM updates. This mentioned in Section 4.1. To establish such regularity condition, we use the potential function. U to solve this problem. We prove that U remains bounded along the gradient EM trajectory, implying each fa; remains well-behaved. With this regularity condition, combined with the previous two steps, we finish the proof of Theorem 2 via mathematical induction.
easy to prove for each individual μl; due to the same mon-ooooooic issue
4.3 Proof ideas for Theorem
Proving Theorem 7 is much simpler. The idea is natural: we found that there exists some bad regions where the gradient L is exponentially small, characterized by the following lemma.
Lemma
15 (Gradient norm upper bound). For any satisfying [| [|elll
2
d0 [|sa]..... ...., ||w < Vd, the gradient of L at be upper bounded as
II [V, C(p) < 2(1|esll + + || + 2exp((dd)(llall + (lp22)), Vi e [n].
Utilizing Lemma 15, we can prove Theorem 7 by showing that initialization from these bad regions will get trapped for exponentially long, since the gradient norm exponentially small. The full proof can be found in Appendix B.2.

---

Peremwer Dastence
10
10
Farations
Berations
Berations
Figure Left: Sublinear convergence the likelihood loss C. Middle: Sublinear convergence the parametric distance iie(n TellA:- je" I between student GMM and the ground truth. Right: Impact of different mixing weights the convergence speed.
Gradient Norm
Avenage Statissical
ex101
O//-119
Linear Regression: 8(1 1.20)
4430
dimonsion
Semole Size
Figure 2: Left: Gradient norm ([)) in the counter-example Theorem 7 decreases exponentially fast w.r.t dimension d. Right: The statistical error (blue line) approximately scales as ~ n -1/4 with sample size n.
Experiments
In this section we experimentally explore the behavior of gradient EM on GMMs.
Convergence rates. We choose the experimental setting of d 5, 1) 0.7. We use n 2, 10 Gaus- sian mixtures to learn data generated from one single ground truth Gaussian distribution N(,² Ia). respectively. Since closed form expression of the population gradient intractable, we approximate the gradient step via Monte Carlo method, with sample size 3.5 x 10 The mixing weights of student GMM are randomly sampled from a standard Dirichlet distribution and set as fixed during gradient EM update. The covariances of all component Gaussians are set as the identity matrix. We recorded the convergence of likelihood function (estimated also by Monte Carlo method on fresh samples each iteration) and parametric distance Eiejn] Ti Ti|lm μ² l|a along gradient FM trajectory. The results are reported in Figure (left and middle panel). Both the likelihood L and the parametric distance converges sub-linearly.
Weight configurations. We train 3-component GMM with 3-different weight configurations and report runs each configuration in Figure (right). Blue: 3. Orange: (g. 3 2). Green:
1
( 1 3). More evenly distributed weights result in faster convergence.
Initialization geometry. We empirically study the bad initialization point (0) described in Theorem 7 by plotting the gradient norm at (x(0) w.r.t. different dimension d in Figure 2 (left). As theoretically analyzed, the gradient norm V (()(()) at (0) decreases exponentially in dimension d.
Statistical rates. The statistical rate for EM/gradient EM is another interesting research problem, which we observe empirically in Figure 2 (right). We run gradient FM on 5-component GMM with equal weights. x-axis: number of training samples, y-axis: parametric error after convergence. For each sample size, we run 50 times and report the average. The statistical errors are reported in the blue line. The red line (function (1/4)) and green line (linear regression output fitting blue points) are references. The trajectory approximately follows the law accuracy x n 1/4 While [Wu and Zhou, 2019] rigorously proves the asymptotic statistical rate of Ö(n -1/4) for the special
TT prevent numerical underflow issues, change the constant 12 in (0) to 2.

---

case of 2-GMMs, our experiments imply that the same rate might also apply to the general case of multi-component GMMs.
Conclusion
This paper gives the first global convergence of gradient EM for over- peeepaaraettri Gaussian mixture models when the ground truth is a single Gaussian, and rate is sublinear which is exponentially slower than the rate in the panetttaraettiizaiionn case. One fundamental open problem is study when one can obtain global convergence of EM or gradient EM for Gaussian mixture models when the ground truth has multiple components. The ikelihhoddbasee convergence framework proposed in this paper might be an helpful tool towards solving this general problem.
Acknowledgements This work was supported in part by the following grants: NSF TRIPODS
II-DMS 26231660, NSF CCF 2212261,, NSF CCF 2007036, NSF AF 2312775, NSF IIS 21 2110170, NSF DMS 2134106, NSF IIS 2143493, and NSF IIS 2229881.
References
Sivaraman Balakrishnan, Martin J. Wainwright, and Bin Yu. Statistical guarantees for the algorithm: From population to sample-based based analysis, 2014.
Constantinos Daskalakis, Christos Tzamos, and Manolis Zampetakis. Ten steps of em suffice for mixtures of two gaussians. Satyen Kale and Ohad Shamir, editors, Proceedings of the 2017 Con- ference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 704- 710. PMLR, 07-10 Jul 2017. URL https://proceedings mlr ptwps/v65/ https//ssaaaaaiiaaaaaaa html.
Ji Xu, Daniel J. Hsu, and Arian Maleki. Global analysis of expectation maximization for mix- tures of two gaussians. Neural Information Processing Systems, 2016. URL https: // semnaniccannt
Org/CorpusID. 6310792.
Raaz Dwivedi, Nhat Ho, Koulik Khamaru, Martin J. Wainwright, and Michael I. Jordan. Theoretical guarantees for em under misspecified gaussian mixture models. In Neural Information Processing Systems, 2018a. URL Utt.ttps:: www.h:tp/s/aaaee //api. semanti cscholar semanticscholar org Carrporruusi ID: 54062377.
Jeongyeol Kwon and Constantine Caramanis. The em algorithm gives oample-optimality for learning mixtures of well well-separated gaussians. In Conference on Learning Theory, pages 2425-22252 24887 PMLR, 2020.
Raaz Dwivedi, Nhat Ho, Koulik Khamaru, Martin J. Wainwright, Michael I. Jordan, and Bin Yu. Sharp analysis of expectation maximization for weakly identifiable models. In International Conference on Artificial Intelligence and Statistics, 2019. URL https: /api wee.mnticscoolla......... org/ CorpusID:216036378
Chi Jin, Yuchen Zhang, Sivaraman Balakrishnan, Martin Wainwright, and Michael Jor- dan. Local maxima in the likelihood of gaussian mixture models: Structural results and algorithmic consequences. In Neural Information Processing Systems, 2016. URL https: laaapp.ssmaatiicccoooooo
org/ Brrg/CorpusID-. : 3200184.
Raaz Dwivedi, Nhat Ho, Koulik Khamaru, Michael Jordan, Martin J. Wainwright, and Bin Yu. Singularity, misspecification and the convergence rate em. The Annals of Statistics, 2018b. URL /ttts://api.. semanti cscholar... wemanticscholar.coommm wwt..aaa.......roorroaaaaaaaaeee org.CoorpusD::88577333
Bowei Yan, Mingzhang Yin, and Purnamrita Sarkar. Convergence of gradient
multi-component
mixture of gaussians. Advances in Newral Information Processing Systems, 30, 2017.
Lei Xu and Michael Jordan. On convergence properties of the em algorithm for gaussian mixtures. Neural computation, 8(1):129-151, 1996.
Jinwen Ma, Lei Xu, and Michael Jordan. Asymptotic convergence rate of the em algorithm for gaussian mixtures. Neural Computation, 12(12):2881-200) 2000.
10

---

Jason M. Klusowski and W. D. Brinda. Statistical guarantees for estimating the centers of a two- component gaussian mixture by em. arXiv: Machine Learning, 2016. URL https://api.
semanticscholar arg/CorpusID:Beee 885114444
Yihong Wu and Harrison H. Zhou. Randomly initialized em algorithm for two-component gaussian mixture achieves near optimality in o(yn) iterations, 2019.
Nir Weinberger and Guy Bresler. The em algorithm is adaptively-optimal for unbalanced sym- metric gaussian mixtures. J. Mach. Learn. Res., 23: 23:103:1-103:79 2021. URL https: seaaiiismantccscholla. www.ollarrrrrrooooooooooo
ID: 232404093.
Jeongyeol Kwon, Wei Qian, Constantine Caramanis, Yudong Chen, and Damek Davis. Global convergence of the em algorithm for mixtures two component linear regression. Conference on Learning Theory, pages 2055 21 10. PMLR, 2019.
Sanjoy Dasgupta and Leonard J. Schulman. A two-round variant of em for gaussian mixtures. In Proceedings of the 16th Conference on Uncertainty Artificial Intelligence, UAI '00, page 152-159, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc. ISBN 1558607099,
Yudong Chen, Dogyoon Song, Xumei Xi, and Yuqian Zhang. Local minima structures in gaussian mixture models, 2023.
Ruofei Zhao, Yuanzhi Li, and Yuekai Sun. Statistical convergence of the em algorithm on gaussian mixture models. arXiv preprint arXiv:1810.04009 2018.
Nimrod Segol and Boaz Nadler. Improved convergence guarantees for learning gaussian mixture models by EM and gradient EM. URL http://arxxi..ooo wttpa//ss..aaaeeeeaaaeeee...eeet 00575.
Weihang Xu and Simon Du. Over-parameterization exponentially slows down gradient descent for learning single neuron. In The Thirty Sixth Annual Conference on Learning Theory, pages 1155-1198, PMLR, 2023.
Fredericke Richert, Roman Worschech, and Bernd Rosenow, Soft mode in the dynamics of over- realizable online learning for soft committee machines. Physical Review E, 105(5): 2022.
Nuoya Xiong, Lijun Ding, and Simon Du. How over-parameeerrizaion slows down gradient descent in matrix sensing: The curses of symmetry and initialization. arXiv preprint arX1v:2310.01769, 2023.
Jialun Zhang, Salar Fattahi, and Richard Zhang. Preconditioned gradient descent for over- parameterized nonconvex matrix factorization. Advances in Neural Information Processing Systems, 34:5985 2021.
Jiacheng Zhuo, Jeongyeol Kwon, Nhat Ho, and Constantine Caramanis. On the computational and statistical complexity of wee-pparametrrized matrix sensing. arXiv preprint arXiv:2102.02756, 2021.
Charles M. Stein. Estimation of the Mean of a Multivariate Normal Distribution. The Annals of Statistics, 9(6): 135 1151, 1981. doi: 10.12144as// URL https://dol: org/10. 10. 2214/aos/117634565
Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018.

---

A Missing Proofs and Auxiliary lemmas
Proof of Fact is well known that (see Section of Wu and Zhou [2019])
((1|p) = Ea-pa- [ (z)) - DKL (xa()p(()=))plpp (-1x)) (-)x(
where Pa (-1z) denotes the distribution hidden variable (in our case of GMM the index of Gaussian component) conditioned on and H denotes information entropy.
Since 2t μ is global minimum of DKL (p (a)))pp (+|z)), have (P
0. Also VH (pp((())) = 0 since H (-()) is constant. Therefore
VQ(ulu)) Evwn, (V (lg(pp VL(u).
The proof of Lemma uses ideas from Theorem of Chen et al. [2023] and relies Stein's identity, which is given by the following lemma.
Lemma (Stein [1981]. For Ni, a² Ia) and differentiable function g Rd -> R. we have
Eig(x)(x μ) o'E(V=g(a)))
if the nwo expectations in the above identity exist.
Now we are ready to prove Lemma 9. Lemma 9, For any GMM(H), E [n]] the gradient of Q satisfies
C()) V. Q((()) Er (x(x)
(z(())
kE(m]
Proof. Applying Stein's identity (Lemma 16), for each E [n] we have
V Q(()p) Eg=~((o,ra) (1bx(x) - =x]]
-Eg~N(0,r)) [d)( pr E [x)(a)]]
EE [+(()) in Vo
Recall that
||0-
T.. exp
(1( Pr[j|æ]]
Exe(m) T exp
2
The gradient V (x) could be calculated as V (x)
||0
M4x 112
(-1ke
||
mill
Σ exp
T. exp
(ms x)
Eke[pn) TA exp
(- [|
2
2
kE|nl
m. exp (_11o-pull?
11:l1?
| - 14x 12
(#x - -x) )
T exp
2
2
kE[N]
=b)(1) -x) -x)- -+)(x)) Σ
(1: xx)
kE(m)
=xx x) [x(xx) Σ (z))
kE[m]
= -v((()) - Σ (x(x))
kElm
(8)
12

---

note that we used ExE(n) vz(x²) 1.
Then we have
vA Qu(p)) Ez [x)((2) p4
Ei [o))
]
Es [t)(())] pn
E. (1(()) pi Σ
Ex
xbr(ax)
Σ
kEjnl
AE(N
Proof of Corollary 10.
(v =
Σ TE(m)
( Q())))))))
= Σ
Es
wi((r)
Σ
sha
(2))se
xE(ri)
REim)
27
||
Σ E EEin] kE(n]
Ex (4) E..
Σ
Ex
kE(M)
Lemma 17. For any constant e satisfying 0 < c S 1
3d we have
E (exp (c][=[[)) < + 5v
Proof. Note that (0, (exp (c[[=||)] (c) is the moment-generatin function of ||^|]- To upper bound the value of a moment generating function at c, we use Lagrange's Mean Value Theorem:
Mi (c) = (0) Mise (E)c,
(9)
where & E [0, Note that M (0) 1, So the remaining task is to bound Mi (E). We bound this expectation using truncation method as:
M' (E)
E,
[||=||| exp(E [=[])] s E, |||||| exp(c|[=[]]]
||=|
[x=] 4/2 exp
||ق||| exp(c||<
dx
EE
A (x][eexp(((=]))(2mm)) d/2 exp
||:0||
dx
Hells
2
+ *
||0|||||| exp(cl<=])) 4/2 exp
||
dr
(10)
2
|
2
< eexp(c)(2T) 4/2V,
11m//1 ||=]|( -d/2
4/2 exp
[c||z]|
dæ
2
||
I exp(c) d//2 +
[[
d/2 exp
|||=|||
dæ,
2
where Va
4/2 rça/241f
is the volume of dddimensional unit sphere.
13

---

Since ||-|||
=
c||er||
||]|
2
S
3d
|0
||]|
10-1/ 1/22))
10-
have
||
1
[[0]((2T))
dd/2 exp
2/2
c||/=||
dæ
|||121
1 ||-1121
(0]1(22))-))
d/2 exp
||
2
2d
dæ
2
1 11v 2
2d
(-11x)
|1s/112) )
2d
d
1121((27)
d/2 exp
dy
2d
-
2
2d -
2d
d+1
(oy-A(( [lv]l]
2d
2d
d+1
v
/2r
4+1
2
2d -
r
< 4vd,
d+1
where we used
2d
< 4 and the log convexity of Gamma function at the last line. Plugging
2d-1
this back to (10), wc get
||:|| dx
Mi exp(c)(2T) +
(2xx)
4/2 exp (cl|ar|
|1
(11)
< exp(1 (3d(1 (2T) 4/2 4vd
S 5vd.
Plugging (11) into (9), we obtain the final bound
Eg [exp (2 || (I))))) Maaa (c) (1 M Min 5v
Lemma 18. Recall that U = Eve(n) l|mil 1. For any fixed x E Rd, x # and any we have
2
Tieyy exp (-4U) (1 exp (-4pmaxl|aa [/ 2p ||0|||
Proof.
|1tx-=u1 12
exp
(tx)
Ekejal Thk exp
|| ||
n
Ene(n) Th exp (1 mil1 ||( 12))
m
Exe(al Th exp (1 (1111 mill - |1,e - p4:: (1
(12)
Exe(n) The exp (1 (2lx pt 1kks 14 (ba))
Ene(n) Thk exp (1 (2||tz] + 2pmaxx 2pmax
= n. exp (-2pmax (||xx] + pmax))
14

---

Therefore
(i(tr)
1=-1 Te exp (- (-Apmax (||tz]) | + Mmmxx) dt
= oxp (- Appmax) 2 { cxp ( 441maxx ( dt
(13)
1=0
2/1 ||||| T: exp (-4U) (1 exp (-4/max [x]]))
B Proofs for Section 3 and 4
B.1 Prools for global convergence analysis
Theorem 13. At any two points = (R] .?)
pT) and + = =((1 +1)) ..... (Hm + TT,
1
|| S max {6d, 2||
E [n],
then the loss function C satisfies the following smoothness property: for any E [n]] we have
V p. +5, C(u 8) - v,,((H=) S mmx (30v d + 4/mmax) )1 6:1l + Σ ||
(14)
kE[m)
Proof. Note that
(1-
||6,112
exp
11o:
exp exp (=16 (Ix)())) exp
exp
(z
Mss 8,)
2
2
exp
2
||6.112
<exp [[]]] + [Ix exp
2
Therefore ( μ + 8) can be bounded
(- ||--(u++5]])
m. exp
Exe(n) Th exp
(un +
exp
exp (1 ([]]==]] + || ()) exp
[6:,112
exp (2 |1 + (|xI (=(p))))
Eke(o) Te exp
|1m 1 2
exp (- |15 ([a=]] + [Ix exp
||8.11
2
(15)
Similarly, we have
[[x-([+;+8;]]]
M, exp
(x(2/p +
ΣkEIni The exp
|| +64)
(- ||=-pell" exp (-1 (-116:]1([1==]] + [[x= exp (-
(-162 ||6.1l
mi exp
exp((22|6,|[[
|l (x(p))).
Eke(o) Th exp (- [lx-pell1)) exp (1165 + (lal)) cxp (- (-11611) 116:112)
(16)
15

---

Recall that by Lemma we have p/,((H) Es (((((l))) ExE(H sra(ala))u)) so
# f(u + 6) vu((1i)
Ex
(1 1 +6) Σ
M + (mm + 6k)
E.r
Ue (x)lp) Σ
ah (2)
RE(n]
kE(n]
Ex
41 6) 8)6x
RE(m]
+ Ex
(1b((1) 00 5) (=l (=)))))))))
AE(nn]
(17)
< En
60 +
kE(M)
+
E
8) (x) Bealll (1
kE[m]
1
||
+
E
5) v4 (x)))) [exl
kE/n]
kE(N)
Σ
||&
+
E. (exp (2] + || 1l
kEjN]
kE[M]
where the last incquality is because th, t/k Σ 1 and applying (15) and (16).
The remaining task is to bound Eg [exp [|(I=] + (lx+l))) 1]. Since 2||6/|| S Lemma 17 bound it as
1 3d
we can use
Eg [exp [I(I|I + (l)l))) - -x)]_=))2] [exp (2] || [))]
< (1xp(2] (1 10 ( = cxp(2))6 (1]) 1 + 10v/||5, exp(2 ||
< <||66|111 + 10 exp(1) s (30v + 11
(18)
where we used exp(1 + x) S 1 2x, Vz E [0, 1] at the last line. Plugging this back to (17), we get
peto, C(p + 8) Vp.((m))
| Σ
Eg /exp (2]1& + (pslD))
1] |axl
kE(n]
kE|n]
|| +
(30V + 1104
(19)
kE|ni
kE
1//mx
(30 d 4m 1|
Σ
||
kE[m]
Theorem 14, The loss function can be upper bounded as
C(p) <
n3
|4
2
sE(m]
16

---

Proof. Since the logarithm function is concave, by Jensen's inequality we have
Pyu (x)
C(u) = DXL (PM- [1pp) = --E Ex
log
Pas
(x)
Σ; Te exp
2
-r
log
||=||=
exp
2
||
Ix- 2
exp
< --Eg
E
Ti log
10
exp
2
1|/1112
27
Σ
T
(I,
2
Σ VE(x]
Ti
111112
Mmmax
2
2
Lemma 12. For any GM) have
[epp( (-80) T
(V)Q(u))) 1)) E,11
d(1 + Mmax v d)) Pmax
Proof. Consider two cases:
Case 1. There exists &t [ni] such that ||4e Mimnel we have
Myya
Then by Lemma 19 and Lemma 11
2
exp SU)
Ex [1))1 2
Σ
Tol - 1gil?
40000d(1 + 2//maxx v vaz
exp(-80 (-SU)
Tmin
2
Memax
40000d(1 + 2/ v dyz
8
exp (-8U) 22
2560000d(1 + 2pmax v dyz Mmax
Case2. For Ak E [n]. || Mell < 2
Then by Lemma 20 we have E, (x))1 2
t 2 D(exp(-8ummxx)ee Winaa 2 M(exp(-UU)) ( > S (xpp(-8Ummmn
dmm+s vdya Mmnax) (since
= < Vz).
Lemma 19. For any GMM(11), if there exists is E [re] such that || - Mimae
Mmus 2
then we have
Σ
nे TetyllAs - psll? 2 8
Tiin
mmax
KJEN
Proof. By Cauchy-Schii Scchhar inequality, we have ||a|12 + |1b112 2 1 bll so for Vi [m]] we have
Σ JE(m]
Ty f1 - 22 2 Timax ||w - Mimase 1|2 Tullp4 - 12
Tmin
[1 Mimax) (M4 mx)l1
Tmin 11 Plmax 1|2
2
Therefore
nom - 11
11311
Tmin || Mimax 11 Tmin pmaxe
2
iE[m]
JE[n]
[n]
where the last inequality is because || Mimon
Hmax and E, T3 = 1.

---

Lemma 20. For any GMM(p), if Ak E [nd] we have P
Mell <
Mmux, then
Ep [1 2 P
Proof. For any [n], by Cauchy-Schwarz Schwarz inequality we have
(1iks (Mk:Himax) (Hitmax
(11imax
[(xe) Mimmax)
||
11?
(yoa Mk Mimaar
(20)
2 1
||
pel | 2 Minax
where the last inequality is because | pkll < Hmass Note that (20) implies (1kk. Fimax)
2
Mmaxx so for Vx E Rd we have
(x)0) =
Σ AE(M)
the (4k
2
Σ
the (b) Himax
(xx( (ee Pimaxd Mmuxx
kE(m]
(21)
where we used Eke(n) v/x(()) = at the last inequality.
Lemma 11. For any GM we have
2
exp (-8U)
E,
(x))P)
Σ
M4
40000d(1 2pmmxx v dd2
(.jE[m)
Proof. The key idea is to consider the gradient of sb. which can be calculated as
V. (x) Σn, (OV)(E))
E (1))))
Σ (1()) Σ ((())))))))
LjE[m]
(22)
Σ
(=))))) - TT)
(milu (x)) 1
Σ
u³)T + ps ))
Σ
(1()))s - 15)44- - T
where we used (8) in the second identity.
18

---

By Cauchy-Schwarr Schwarz inequality, we have ||a|12 + ||b] 2 b bll?, which implies
Ex
[1)5(())))1
E.
(x)) +
(2(()) (- /|?
2 Ex
(1)))) (-2), 27
E.
( 0t ( (1x) x))
(23)
F.r
( x. V Fdd
27
E.
27
Ex
||r||| xx" T Vap (tr)
where we used Be 2 (tx) (tar)) at the second to last identity. Careful readers might notice
that the term (J=_ ||>||| - " (Lr) not well-defined when 0, but we can still calculate its expectation over the whole probability space since the integration is only singular on zero-measure set.
For each x + 0, by (22) we have
F V'V
(ta)) - 1), J.
Σ
So
Ex
1
2
E,
||0||| Σ (LLt)))((())(( - x)
16
(.E(()
27 (o(()))
(uu - 5/ ["' ----
Ex
||||||
Σ
16
{.jE(m)
2
1
Eg
||س|||
Σ
(us - 2)
Te exp (-4U) (1 exp ( (-4pmaxll |==|||
16
2pmaax |z||
(.jE(1)
27
exp (-UU)
exp ( Aprmax [
Ex
Σ
M1. x)
64
Amax
exp (-8U)
exp (
4-4mmxx [|]l)
]
Σ
(Mi M1 xx Dr
n,m
64
Mmax
(24)
where we used Lemma 18 at the fourth line and Cauchy-Schward inequality at the last line.
The last step is to lower bound E [(4 - My. x)² (1 exp (44pmax [[=]))) /Mmax] Since x is sam- pled from.N (0, La), which is spherically symmetric, we know that the two random variables { ||>|||
19

---

are independent. Therefore
exp ( 4pmax [=|]]
1 exp (- 41mmx x
Ex (Ms My. x)²
Er [(e Mg. x) E
Pmax
Jmax
(25)
For the first term in (25), we have Ez [e - ,y و} symmetrically distributed. By norm norm-concentration inequality of Gaussian [Dasgupta and Schulman, bounded
l| My |12 since is spherically
2000] we know that Pr ||>||
vdl
2 1/50, vd. The second term (25) can be therefore lower
exp (- 4/mmxx |+
vd
1 exp
-44mmax
L
1 exp 2pmaxx Vdl
Eg
2 Pr
||=|||
Umax
Pmax
50pmax
(26)
Plugging (26) into (25); get
exp (- [-4paax]] | [x])
1 exp
-2
E (u= 1),,x)²
11/112.
(27)
Mmax
50d
Now can plug (27) into (24) and get
2 4max |srl])
Eg (x))1
exp -U))
Σ
Ex
(ms
uy x)²
exp (
64
Pmax
22 Vdl
exp exp (-8U)
exp
T;
114s 14l1
64
50d
(JEEn)
(28)
2
exp (-8U)
Σ
1+2pmax
1114 11y112
64
30d
(.jEm)
exp (-8U)
Σ (.jE(m)
Tot - 11yl2
40000d(1 + 2pmaax vdj2
where we used the inequality Vt 2 0,e-5 1+t at the second last line.
Theorem 2. Consider training a student n-component GMM initialized from p(00)
(T.())T,...,,, (O()))))))))) to learn a single-component ground truth GMM Ia) with popula- tion gradient EM algorithm. the step size satisfies n SO EM converges globally with rate
exp(- (0))))
then gradient
ndd2 Pinaa (0) + (0))a
C(u(t)) S
Vxt
where 7 52 nexp( (00
E RR. Recall that Prnax (0) max max (0)II, -.., ||,, (0)l)
(1+ dn)
and U()) (i(m) || [2
two initialization constants.
Proof. We use mathematical induction prove Theorem 2, by proving the following two conditions inductively:
U(t) < (0))
Σ KE(T)
[|)) Vt.
(29)
(2(2(1) 2 7t + (²(2())) Vt.
(30)
20

---

Note that (30) directly implies the theorem, now we just need to prove (29) and (30) together. The induction base for is trivial. Now suppose the conditions hold for time step consider t ++ 1. By induction hypothesis (29) we have [f)]l S Mmax(1) S vTlpmax()) (0), Vt.
Proof of (30). Since Q(Q(u))) = vuC(H), apply classical analysis of gradient descent [Nesterov et al., 2018] as
C(u(t+ 1)) - C(u(t))
= =(m(t) - -
(VL(u(t) - (VE(u(t)ss) (VCC((())) ds
(VE(M()) + S (VC(H()) VC(U(1) (VVEE((())) ds
V +1 L' (VC(H(t)) -C((() - VnVC((())) vC(U(t)) ds
(31)
Note that the gradient norm can upper bounded as
IV Nvz(((((() Exr
(x(x)) Σ (b)(
S Ex
(a(())
Σ kE(m]
(x(()) [(x(
kE(m]
Σ [|u((t)) (nt(t)= S 1M (0).
Then for any E [0, 1], we have ||STV (. ((p(t)))l S xpmpmmaxx0) S max 6d
So we can
apply Theorem 13 and get
| n. ((u(t)) Vn. o.
S M/xaxx (3) + 4/mmax (0)
Σ (m,
kE(m)
Therefore for Vs E 10.
(VC(H(t) VL(M(t) - sTVC((((t)), vC(u(t))
| ((,(t) C(,(( S -. C(u(t))
kc(m)
Σ
M2mmaxx 11 (t)anx) + 4 ((((()))+ Σ kE(n)
V un C(((t)))) [VMF(((())
VE(N)
11/mmxx (1) 4/ (1)) + n² (L(M(())
4n² (max (0)2 30300/nn 3/2 umax (0) + n²) [[
s 20m adm ( (0) + 1) vL(u(t)))
(32)
Plugging (32) into (31), since 7) S 0
we have
Vdr (0)) 10)+1)
=- (, ()) --)VV((((0)
(33)
21

---

By Lemma 12 we can lower bound the gradient norm as
[V 2 (V((((t) (())
20 ( exx(( (U (2L(a(t))3/2 5
(V(()(t):)1())
exp
(t)
x min
Mmmax (t)
[t((t]]
1P
nd([1 + Mmax (t)vd)3
Theorem 14
exp (-8U(1)) min
exp (-pU--U (0)) _ x
(3/2((2(())
ndd(1 + Mmax (t)
Ind[1 + Mmax (0) dn)
(34)
Combining (34) and (33), we have
[(u(t+1)) S ((m(t)) -( (E((H(()) c(m(t)) - nexp (1) o Mi
(x((t)))
dl + Mmax (0) (n)
(35)
Note that the above inequality implies L(u(t + 1)) & L(u(t)), therefore
(C(n(t)) D(p(t 1)))((((()) + C(u + 1)))
(2 1)) (²(((t))
(=(((t))((((((tt))
(L(n(1)) - C(u(l + ())((((())
(35)
nexp (-16U(0) m
Ω
n2d2(1 Mmax (0) dr)) =7
(*((tt))
On the other hand, by induction hypothesis we have c²(((()) 2 yt + (²()())) combined with the above inequality, we have 2(n((t+TT) Z Z + 2 7tt + proof of (30).
1
1
1)+ +)
(())) which finishes the
Proof of (29). The dynamics of potential function U can be calculated as
U(p(t+11) +1) Σ ||, (t + 1)11
iE(m]
Σ [1)=(() V, Q(m())m(0)) EE|D
((((()) - 11 Σ
(t,(1), V ((HC))(())) + +n² Σ
V. ((H())MM)
(36)
iE(m)
(E(m)
Corollary 10 U(p(t)) - E (2)))
+n² Σ
V ((H()))()))
sE(m
J2
By induction hypothesis, the first term J can be bounded by Lemma as
Tn > S/l ( (exp (-x((-)(()) 2 / (1) 1752
exp (-SU(0) 2
(²((()). (37)
d(1 + Pmax (mmxx(()) (1)
n²d(1 + Mmax (0) (0)/)
22

---

The second term 12 is a perturbation term that can be upper bounded by Lemma 9 as
1 1==1 12 Σ
VV p. (((()))))))
Σ
vi(x)) Σ (x(2))a(t)
2 Eg
(1( Σ (a(T))((())
vE[m]
kE(ml
17
Eg
(1(()) Σ
vx(x)) (t)l
<c(n)
kE(M)
2
I 11
Eg
Σ ((())R((O))
Σ (1))
(38)
kE[n)
AE(m]
keiml
S 1² Σ Ex
Σ
oe (1)
Ex
(1))
kE(M)
[m(
((()))(())
jE(mi AE[N]
Σ (oe((o) }
< {()U((())
Σ sb((tr)
KE(M)
AE(m
-t)((a(t)
where we use triangle inequality twice at the second and third line, and Cauchy-Schwaar inequality twice at the fourth and fifth line.
Putting (38), (37) and (36) together, we get
cxp (-8U(0)) 2iin nddd(1 Mmax (0) +
U(u(t + +1) S ((((t)) 1752
+ (((((((t))
Consider two cases: a). If ((0) < U(m(t)) S U(),, then
2
U(u(t + 1)) U(H(t)) nU(((t)) (2) exp (-88(0) 2
U(u(t)) m1)
n²dd1 + Umax (0)
{U(((t)) - (((((t))
exp exp(-8U(()) 2
22" Mmaxx (0) -1) s zU(H(t)) S mp
n
n=2d11 Xmax (0) n2)2
note that we used S 0
(0)() Tmm a2d((1+ (0) vnd)
n
1 (0).
2
b). If (u((t) < (0), then U U(u(t + 1)) < (1 + ()())((()))) < 20((()) (0))
Since (29) holds in both cases, our proof is done.
B.2 Proofs for Section 3.2
|| |l S Vd, the gradient of C at Lemma 15. For any μe satisfying || || 2 10vd, [|a]], can be upper bounded as
|| C(m)) 2(1eaal| +... + [|, II) + 2 exxp(cd)(laall + (12211)) Vi [n].
23

---

Proof. Recall that the gradient has the form p(,((H) Er [dh((x) Exe(m vn (2))
hence its
norm can be upper bounded
((p)ll S Es
v1(2) Σ (x()ll kE/m]
Ex
(x) ||
||]|||
S 2vd
+ +E
Σ AE(M]
(x))l |||||| > 2vd
Pr
||0|||
2vd
kE(m)
(39)
For any | I 2 and 2, have exp(-|<x 11:l5/2) exp(-(1xx] p4 /
/2)
exp( (9)/) while for i E (1,2), exp( 1 2 S exp(- - (xp(-((1/4]] | /2)
= sep(-3dd). Since (x) exp(- || -1,111~-111 /22) we have
exp( | 1s
exp( -3dd)
||]|| x 2vd + vx(x))
S <exp(- (5d), Vi (1,2).
11 12/)
(ap(-9d/2)
Therefore the first term in (36) can be bounded as Ex Exe(m) tha (x)]| |||||| 22vd - (1|pz|| +
...+ |l)))))) + exp(- exp(-25d) ( [|
+ l|
On the other hand, by tail bound of the norm of Gaussian vectors (see Lemma 8 of (Yan et al., 2017))
we have Pr
|| > 2/d I exp(-dd.. Putting everything together, (39) can be further bounded as
V C(4)]1 S (a1lal) + ... + || + exp((25d))(lep [|22]) + exp(-
Σ <E(m)
l|
$ 2(1|usll +... [|mm]]) 2exx((d)) (|p21))
Theorem 7. For any n 2 3, define (x( (N] (O)((O)).. (O).... V., ( (0)) as follows: jal (0)
12vdes, (2) = -12 (.()) = pn (0) O, where e is a standard unit vector. Then population gradient EM initialized with means (0) and equal weights Tı
nT 1/n
will be trupped in bud local region around (x(0) for exponentially long time T 30
exp(O(U(O))), More rigorously, for any < S T, Di E [n]] such that
30n
[|x(())] 2 10vd,
Proof. We prove the following statement inductively: VO T: (1) + (2(()) = (a)( = =... -... mn(() =
(40)
Vi, -1)((1)) - (x()) S nl((60vd de -.
(41)
(40) states that during the gradient EM update, μ4 will keep stationary at while the symmetry between 22 .2..... Mn, will be preserved.
The induction base is trivial. Now suppose (41), (40) holds for 0, 1, .,...,4 we prove the case for L+ 1. Proof of (40). Due to the induction hypothesis, one can see from direct calculation that Va, we have (x))(((t)) cb((=r((((t) for i 3...., n, and ti (z)((t)) ز (2(-)/(((t).
24

---

Consequently for vi > 2 we have
Vn (((((( - Ex (((()
Σ (a(eela())aa(())
E. (1
kC[N]
1 Ez (1000000000000000000000000000000 mx(() = 0.
1 -E
(2))
Similarly, for ,4,, 142 we have
Ve, ((((t)) = Es (2(()((t)) Σ (e(e)l(()))na(t)
= =E, (x + (2)))22
kE|N]
E, [ xx) (122 (- + 1 x [2)]
EE W22 - (12))- + +1 (-x))=)] = ((t))((tt).
This combined with the induction hypothesis implies μ2 + 1)= -1z 1), (40) is proved.
Proof of (41).
- p4; (0) S nt (60 S 1077-600// So Vi {1, 2), (1)] = (l 2 < 15 Then by Lemma 15, Vi E [m] we have
By induction hypothesis, we have Vi, (t,
s 2vd.
[[)))((((t)] - |10
II) s 4 (exp(_d)-15vd = 600 de
note that here we used ps(() =... Pm (t) = 0. Therefore by the induction hypothesis we have [| ( - (0)l & ntt . (60 de de + 7/ v,.,(((((())
nt + 1). (60Vde (41) is proven.
By (41), v0 < 1 < T. for 1,2 we have || (4)ll 2 [m]( llv((() (4)))) 2 12 pe 9) 2 12vd 2vd 10vd. Our proof is done.
25

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See the summary of main contributions in Section I and main results in Section
3.
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 the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation 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: As a theoretical work, the major assumptions and limitations of our results are presented the introduction part of Section 1.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a 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 (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on 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 on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 to address problems of privacy and faimesss.
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?
26

---

Answer: [Yes]
Justification: The settings and assumptions are introduced in Section 1. The complete proof of all theorems are provided in the Appendix.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced 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 to 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:
We give the details of our synthetic experiments.
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, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a 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 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 reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
27

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: We only run a small-scale experiment to verify an optimization phenomenon in our theory.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
www.ubmmiisiooooioiy...........e for more details. httie//ggiide//oeeeeuuuune
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.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:
/ //nips.aa cttpssscccppccccccccpcccccccccct c/guidgs /
CoodeSubmis ssi aasionPoiccy for more details.
The authors should provide instructions 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 reproducible, they proposed method and baselines. only subset of experiments 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 in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We give the details about our synthetic experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or 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: This paper focuses on the optimization aspect. Our experiment shows the optimization phenomenon synthetic data, and do not study the statistical aspect.
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, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
28

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
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 enror 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 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 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: Our experiment only shows the phenomenon on small-scale synthetic data, so we did not record the computation resource used.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 or failed experiments that NeurlPS Code of Ethics https: http:::///euuiiie http//nnurrrp.peee hwtpc//pbbbcc..eccccccceeeeeeele
didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the
Answer: [Yes]
Justification:
We conform, in every respect, with the NeurlPS Code of Ethics.
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: [Yes]
Justification: This is a theoretical work. It societal impact lies within its potential pratical applications.
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.
29

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to 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 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 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 intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are 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 ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This is a theoretical work and has no such risks.
Guidelines:
The answer NA means that the paper poses no 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 to 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. Licenses 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:
This is theoretical work and does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.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 package should be provided. For popular datasets, paperswi twwode..ooo..... com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
30

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
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:
As theoretical work, does not release such new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part 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 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. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We do involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information 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 the main paper.
According the NeurIPS Code of Ethics, 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We do not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 NeurIPS 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.
31


Reviews:
[{"review_id": "pTgLGsoIvx", "reviewer": "Reviewer_6yVv", "summary": "The paper considers fitting a single Gaussian with multiple-component Gaussian mixture models (GMM) through the Gradient EM algorithm. While the two balanced over-specified Gaussian setting has been widely studied in the previous work, generalizing it to multiple-component GMM requires significant algebraic efforts. The entirety of the paper is to show the $1/\\sqrt{t}$ convergence rate of the population EM algorithm. In particular, the paper characterizes the explicit convergence rate of $1/\\sqrt{T}$ with constants exponential in the number of components, the phenomenon that coincides with the exponential lower bound for the parameter estimation of general GMMs with no separation.", "questions": "-\tMaybe authors can elaborate on how their results can imply learning k-GMM with small separations?\n\n-\tIn Theorem 7, there is no restriction on the step size $\\eta$. I believe that the lower bound should also be able to tell that $\\eta$ cannot be set too large.\n\n-\tWhy only on the gradient EM? Can the analysis in the paper imply some convergence rates of the standard EM algorithm as well? I think it would make the paper much stronger if it could show that the same results hold for standard EM.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "-\tExtending some existing two-component results to general multiple-component GMM is non-trivial and significant. The paper nicely characterizes the convergence rate that captures some important properties of learning GMM that can be achieved by GMM. \n\n-\tThe paper is well-written, emphasizing important aspects of the results and well-contrasting their techniques to existing results. \n\n-\tProof sketch is nicely written to help readers understand their key results.", "weaknesses": "-\tWhile the lower bound result (Theorem 7) is a nice addition to the literature, I believe that the gap between this lower bound and the upper bound is large, since the upper bound is exponentially slow in the number of components. \n\n-\tOne important result from two specified GMM is the $n^{-1/4}$ (n is the number of samples here) statistical rate after convergence. I would like to see $n^{-1/2k}$ style results in general k-component GMM settings. At least, the authors should have discussed this aspect of previous work and contrasted the implications to k-GMM settings. \n\n-\tThe experiment would have been nicer if the final statistical rates were compared.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review. We answer each of your questions below.\n\n> The gap between this lower bound and the upper bound is large.\n\nThank you for pointing out this problem. In the initial version we didn't optimize the exponent. Indeed, we can obtain significantly refined results which removes this gap between upper and lower bounds. The improved bounds are as follows:\n\n- [Upper bound] Consider training a student $n$-component GMM initialized from ${\\mu}(0) = (\\mu_1(0)^{\\top},\\ldots, \\mu_n(0)^{\\top})^{\\top}$ to learn a single-component ground truth GMM $\\mathcal{N}(0, I_d)$ with population gradient EM algorithm. If the step size satisfies $\\eta \\leq O\\left(\\frac{\\exp\\left(-8U(0)\\right)\\pi_{\\min}^2}{n^2d^2(\\frac{1}{\\mu_{\\max}(0)}+\\mu_{\\max}(0))^2}\\right)$, then gradient EM converges globally with rate $$\\mathcal{L}(\\mu(t))\\leq \\frac{1}{\\sqrt{\\gamma t}},$$ where  $\\gamma = \\Omega\\left(\\frac{\\eta\\exp\\left(-16U(0)\\right)\\pi_{\\min}^4}{n^2d^2(1+\\mu_{\\max}(0){\\sqrt{dn}})^4}\\right)\\in \\mathrm{R}^+$. Recall that $\\mu_{\\max}(0)=\\max\\{\\|\\mu_1(0)\\|,\\ldots, \\|\\mu_n(0)\\|\\}$ and $U(0)=\\sum_{i\\in[n]}\\|\\mu_i(0)\\|^2$.\n\n- [Lower Bound] For any $n\\geq 3$, there exists initialization points such that, when initialized from, population gradient EM will be trapped in a bad local region around it for exponentially long time $T=\\frac{1}{30\\eta}\\exp(\\Theta(U(0)))$ as: $0\\leq t\\leq T$, $\\exists i\\in[n]$ such that $$ \\|\\mu_i(t)\\|\\geq 10\\sqrt{d}. $$\n\nBoth the improved lower and upper bounds are tighter than original versions since $n\\mu_{\\max}^2\\geq U\\geq \\mu_{\\max}^2$. Most importantly, the improved exponential factors of $\\exp(\\Theta(U(0)))$ in the two bounds now exactly matches, eliminating the noted large gap. Our key idea is to use $U=\\sum_{i\\in[n]} \\|\\mu_i\\|^2$ (which captures information on all Gaussian means) instead of $\\mu_{\\max}=\\max_i\\{\\|\\mu_i\\|\\}$ (which reflects only  the maximum Gaussian mean) to construct our convergence rate bounds, resulting in a more fine-grained analysis and tighter bounds. We also constructed a better counter-example: ${\\mu}_1(0)=12\\sqrt{d}e_1, {\\mu}_2(0)=-12\\sqrt{d}e_1, \\mu_3(0)=\\cdots=\\mu_n(0)=0$, where $e_1$ is a standard unit vector. This new construction applies to all $n\\geq 3$ (while the original one requires $n$ being odd) and implies a tighter lower bound.\n\nWith this idea, we are happy to present the **optimal** exponential factor of the convergence rate (up to a constant), which we believe might be of independent interests to future study.\n\n> Statistical rate for 2-GMM is $n^{-1/4}$. I would like to see $n^{-1/2k}$ style results in general k-component GMM settings. The authors should have discussed this.\n\n\nWe agree that statistical rates for learning GMM is an important topic. However, our focus is not on this problem since we aim to study *optimization rates* rather than statistical rates of gradient EM. \nYet we are aware that there is a long line of work on this topic. The statistical rate of $n^{-1/4}$ you noted is studied in [1] and [4]. To the best of our knowledge, the same rate for general k-GMM remains an interesting open problem and $n^{-1/2k}$ is a nice conjecture. However, our new experiments suggest that the rate seems to be still $n^{-1/4}$ for general k-GMM. (See response to the next question.) We will add these discussions and our experimental findings into the revised version.\n\n> The experiment would have been nicer if the final statistical rates were compared.\n\nThanks for the suggestion! We have added a new experiment on this. See the global author rebuttal to all reviewers (figure 1 in attached pdf) for details. The empirical statistical rate for k-GMM is close to $n^{-1/4}$. \n\n> Maybe authors can elaborate on how their results can imply learning k-GMM with small separations?\n\nThanks for noting this topic. Our results immediately imply that the convergence rate for learning general k-GMM with small separations will be sub-linear, since a single Gaussian is a special case of k-GMM with no separation. So the linear-contraction style analysis (such as in [2])  for well-separated GMM no longer works in this regime, and we believe our likelihood-based  framework can be helpful. We will add more corresponding discussions in the revised version.\n\n\n\n> In Theorem 7, there is no restriction on the step size.\n\nTheorem 7 applies to any positive step size $\\eta$. It punishes large step sizes as $T$ scales with $1/\\eta$, so the time that gradient EM gets trapped shortens as the step size increases. As long as the step size is polynomially large $\\eta =poly(n,d)$, gradient EM gets trapped in the bad region for exponentially long time as $T\\geq \\frac{1}{poly(n,d)}\\exp(\\Theta(U(0)))$.\n \n \n> Why only on the gradient EM? Can the analysis in the paper imply some convergence rates of the standard EM algorithm as well?\n\nWhile gradient EM is equivalent with gradient descent on the likelihood function $\\mathcal{L}$, standard EM can also be seen as a gradient descent-like algorithm on $\\mathcal{L}$ with a coordinate-dependent step size $1/\\mathrm{E}_x[\\psi_i(x)]$. (See further discussions in [3]). We believe our method is also useful for standard EM. We will add more discussions on extensions to standard EM in the revised version. \n\n\n\nReferences:\n- [1]. Yihong Wu and Harrison H. Zhou. Randomly initialized em algorithm for two-component gaussian mixture achieves near optimality in $O(\\sqrt{n})$ iterations, 2019.\n- [2]. Bowei Yan, Mingzhang Yin, and Purnamrita Sarkar. Convergence of gradient em on multi-component mixture of gaussians. Advances in Neural Information Processing Systems, 30, 2017.\n- [3]. Yudong Chen, Dogyoon Song, Xumei Xi, and Yuqian Zhang. Local minima structures in gaussian mixture models. IEEE Transactions on Information Theory, 2024.\n- [4]. Raaz Dwivedi, Nhat Ho, Koulik Khamaru, Michael I. Jordan, Martin J. Wainwright, and Bin Yu. Singularity, misspecification and the convergence rate of em. The Annals of Statistics, 2018.", "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": "am4YAV6doi", "reviewer": "Reviewer_DCG2", "summary": "The paper focuses on the setting of a Gaussian Mixture Model with several summands and an input vector produced by one Gaussian distribution, where it employs the Expectation-Maximization rule to infer the model's parameters. Since the problem of having arbitrary number of summands has been unsolved, the paper provides an innovative scheme which includes the computation of the likelihood function and shows that the EM algorithm converges with sublinear complexity. \n\nThe authors also show that there exist neighborhoods of slow convergence rates.", "questions": "NA.", "limitations": "NA.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The paper is well written, the theorems, lemmata and algorithmic steps are described gradually.\n- From a first overview of the literature, the result about global convergence seems novel. \n- Across section 4, there is intuition and remarks provided about the necessity of the steps.", "weaknesses": "- The experimental evaluation is used as a proof of concept and thus is limited. The authors could have (potentially) experimented with several datasets, with varying weights in the GMM, and try to benchmark their algorithm to compare the emergent convergence rates.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review and positive comment! We have addressed your question below.\n\n> The experimental evaluation is used as a proof of concept and thus is limited. The authors could have (potentially) experimented with several datasets, with varying weights in the GMM, and try to benchmark their algorithm to compare the emergent convergence rates.\n\nWe note that our primary goal is to rigorously study the optimization convergence rate in a controlled setting and therefore we focus on synthetic experiments to carefully examine the phenomena and corroborate our theoretical findings. \nWe also added more experiments in the rebuttal PDF (attached to the global author rebuttal for all reviewers) to verify our theoretical results:\n- Impact of mixtures weights on the convergence speed (Figure 2 Right of uploaded pdf.) We test $3$ different weight configurations of $3$-component GMM: $(\\frac{1}{3}, \\frac{1}{3}, \\frac{1}{3})$. $(\\frac{1}{6}, \\frac{1}{3}, \\frac{1}{2})$,$(\\frac{1}{20}, \\frac{1}{5}, \\frac{3}{4})$. $4$ runs of each configuration are recorded, with different random initialization. Results show that the convergence is faster when the weights are more evenly distributed: the equally distributed weights of $(\\frac{1}{3}, \\frac{1}{3}, \\frac{1}{3})$ converges with the fastest rate, while $(\\frac{1}{20}, \\frac{1}{5}, \\frac{3}{4})$ converges the slowest.\n- Impact of initialization on the convergence speed (Figure 2 Left of uploaded pdf): We report the gradient norm in the bad initialization region constructed as counter-examples in Theorem 7. Empirically the gradient norm exponentially decreases in dimension $d$. This supports our theoretical findings that bad initialization causes exponentially slow convergence.", "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": "Q83DuxxS9R", "reviewer": "Reviewer_DbMw", "summary": "This paper talks about the gradient-EM algorithm for over-parameterized GMM. The paper mostly shows the GLOBAL convergence and its rate when using this model to learn a single Gaussian.", "questions": "Besides the weakness above, I also have following questions:\n4. If you only learn the single normal, how is the algorithm compared with Dwivedi et al. 2019 or just 2-GMM? Is it necessary to use more? Is it overfitting so the performance seems better?\n5. I don’t get why the paper introduces Fact 1. It seems obvious. \n6. The mean is convergent to 0 (true) instead of the MLE.", "limitations": "Besides above, \n7. the citation format is not uniform.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "I believe any non-convex global convergence optimization problem is valuable. It is an extension of Dwivedi et al. 2019.", "weaknesses": "1. The over-parametrized model may have severe overfitting problem. \n2. The based distribution is quite easy: a single normal, with known variance. In the paper, the covariance is fixed as the identity, which simplifies the problem in a deep way. Actually for symmetric 2-GMM, there are already faster algorithms to learn both mean and cov. \n3. I feel confused about the consistency and convergence in the paper. In Line 96, the convergence of KL divergence also contains the convergence of MLE, ie consistency. The convergence to the MLE is another loss function. Also in Remark 6, the convergence when sample size to infinity seems more easily ensured by WLLN.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed review! We have addressed your questions below.\n\n> The over-parametrized model may have severe overfitting problem.\n\nWe believe this is a misunderstanding. The aim of this paper is not to propose a new algorithm/model, but to understand the convergence behavior of the widely-used EM/gradient EM algorithm. The motivation for studying the over-parameterized regime is well-known as many have conjectured it might facilitate global convergence (see [1], [2]). Since we are considering population gradient EM, there is no overfitting in our problem setting and we leave the study of generalization theory of GMM to future works.\n\n> The based distribution is quite easy: a single normal, with known variance. \n\nThis paper aims to rigorously study the optimization phenamenon in a cannonical setting.\nWe agree that the base distribution is simple. However, when the learning model has more than one mixtures, the learning dynamics becomes significantly complex.\nIn fact, even the further simplified setting where the learning model has only 2 mixtures and the based distribution is a single normal, the analysis in Dwivedi et al. 2019. is technically very complicated. \nThe known co-variance assumption is also a standard setting widely-adopted in existing literature ([1], [2], [3]). \n\n\n> Actually for symmetric 2-GMM, there are already faster algorithms to learn both mean and cov.\n\nAgain, our goal is not to design a new algorithm for learning GMM, but to understand the behavior of the widely-used EM/gradient EM algorithm. While there might be specifically designed algorithms achieving better performance for some special cases such as symmetric 2-GMM, we aim to study gradient EM as one of the most popular existing algorithms for learning general k-component GMM. We will ensure this point comes across more clearly in the final version.\n\n> I feel confused about the consistency and convergence in the paper. In Line 96, the convergence of KL divergence also contains the convergence of MLE, ie consistency. The convergence to the MLE is another loss function.\n\nWhile MLE and KL divergences are two different loss functions, optimizing them are actually equivalent due to the following well-known fact:\n\n$D_{KL}(p(x|\\mu^*)||p(x|\\mu))=-\\mathrm{E}_{x\\sim p(x|\\mu^*)}\\left[\\log\\left(\\frac{p(x|\\mu)}{p(x|\\mu^*)}\\right)\\right]$\n\n$=-\\mathrm{E}_{x\\sim p(x|\\mu^*)}[\\log({p(x|\\mu)})]$\n\n$\\quad +\\mathrm{E}_{x\\sim p(x|\\mu^*)}[\\log({p(x|\\mu^*)})].$\n\nSince the second term above is a constant that does not depend on $\\mu$, minimizing KL is equivalent with maximizing the first term, which is just MLE. Note that this is a general fact that applies to any MLE problem, not just EM or GMM.\n\n> If you only learn the single normal, how is the algorithm compared with Dwivedi et al. 2019 or just 2-GMM? Is it necessary to use more? Is it overfitting so the performance seems better?\n\nAgain, since we are considering population EM, there is no overfitting in this problem. Our algorithm is an extension of Dwivedi et al. 2019 and our main goal is not to argue that k-GMM is better or worse than 2-GMM, but to extend the previous theoretical understanding of 2-GMM to the general k-component case.\n\n> I don’t get why the paper introduces Fact 1. It seems obvious.\n\nFact 1 implies that gradient EM is just running gradient descent on the likelihood function, an observation allowing us to introduce theoretical tools from gradient descent theory to facilitate our analysis.\n\n>  The mean is convergent to 0 (true) instead of the MLE.\n\nSince the algorithm is run on population data, there is no overfitting and the ground truth 0 is just the MLE solution. \n\n> Citation format is not uniform.\n\nThanks for pointing it out. We will also organize our citation style and make it uniform in the revised version.\n\nReferences:\n- [1]. Yudong Chen, Dogyoon Song, Xumei Xi, and Yuqian Zhang. Local minima structures in gaussian mixture models. IEEE Transactions on Information Theory, 2024.\n- [2]. Chi Jin, Yuchen Zhang, Sivaraman Balakrishnan, Martin J. Wainwright, and Michael I. Jordan. Local maxima in the likelihood of gaussian mixture models: Structural results and algorithmic consequences. In Neural Information Processing Systems, 2016.\n- [3]. Sivaraman Balakrishnan, Martin J. Wainwright, and Bin Yu. Statistical guarantees for the em algorithm: From population to sample-based analysis, 2014.", "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": "6LkxBEXYgp", "reviewer": "Reviewer_JsCq", "summary": "The paper studies the convergence of EM for learning mixtures of Gaussians.  Specifically, they consider a simplified setting where the Gaussians are in $d$-dimensions and all have covariance $I_d$.  They consider an overparameterized version of the problem where they parametrize the mixture they are trying to learn by a mixture of $n$ Gaussians with means $\\mu_1, \\dots , \\mu_n$ and the ground truth distribution generating the data just consists of a single Gaussian $N(\\mu^* , I_d)$.  The paper analyzes the dynamics of gradient EM for this problem.  The main result of the paper is proving that for this overparametrized variant, gradient EM converges to the true distribution at a rate of $1/\\sqrt{t}$ with additional constants depending exponentially on the distance between the initialized means and the true mean, which they show is necessary.\n\nThere has been a long line of work on understanding the convergence of EM or gradient EM for learning mixtures of Gaussians.  Without overparametrization, provable convergence is known for mixtures of two Gaussians and it is also known that convergence fails in general for mixtures of three or more components.  For overparamterized settings, a previous work [Dwivedi et. al. 2018] shows that if we parametrize a mixture of two Gaussians and try to learn a ground truth distribution consisting of a single Gaussian, then EM converges at a $1/\\sqrt{t}$ rate (as long as the mixing weights are set to be different).  This is in contrast to when we parametrize with only a single Gaussian and EM converges exponentially fast.  The results of the current paper can be seen as generalizing the results of [Dwivedi et. al. 2018] to more than two components.  The paper empirically validates their theoretical results with experiments on simple synthetic datasets.", "questions": ".", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper makes progress on a well-studied problem of understanding convergence of EM for learning GMMs.  They give the first global convergence results for mixtures with more than two components.\n\nThe paper overcomes nontrivial technical barriers to extend previous results to more than two components.", "weaknesses": "The results of the paper only work when the ground truth is \"trivial\" i.e. a single Gaussian.\n\nThe results are qualitatively similar to previous work on overparametrized mixtures of two Gaussians.  The contributions of the paper are mostly technical and it is a bit difficult to find a nice conceptual takeaway \\--- the previous work for two components already showed that overparametrization can lead to drastically slower convergence.  It would be much more exciting and novel, say, if we could prove something when the ground truth were not just a single Gaussian.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive review. We have addressed your concern below.\n\n> The results of the paper only work when the ground truth is \"trivial\" i.e. a single Gaussian.\n\nWe agree that the single Gaussian ground truth is a simpler case compared to the most general problem. But our setting is nonetheless highly-nontrivial and technically challenging. In fact, even the 2-GMM problem is quite difficult with a large number of previous works (see section 2.1 for details), and our result serves as an important step towards generalizing the 2-GMM analysis to the general k-GMM learning problem.\n\n> The results are qualitatively similar to previous work on overparametrized mixtures of two Gaussians. The contributions of the paper are mostly technical and it is a bit difficult to find a nice conceptual takeaway.\n\nOur result is fundamentally different from previous works like [Dwivedi et. al. 2018]  since the mechanisms for learning general k-component GMM and 2-component GMM are different. [Dwivedi et. al. 2018] only considers 2-component GMM with *symmetric* means, and their **sub-linear convergence only happens when the mixture weights are exactly  equal (both weights being exactly $1/2$)**. On the other hand, our result applies to general GMM with arbitrary weights and asymmetric means. While the phenomenon of slow convergence observed in [Dwivedi et. al. 2018] depends on their specific setting of equal weights and symmetric means, our paper describes the general convergence behavior of k-component GMM.\n\nAnother conceptual takeaway of our result, as stressed in the paper (see Section 4.1), is that one should consider the likelihood convergence rather than parametric convergence for GMM learning problem. One of our major novelty is the brand new likelihood-based framework, while previous works are mostly standard algebraic computations of the parametric convergence.", "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 appreciate all the reviewers for their detailed and positive feedbacks. In the uploaded pdf file, we add several experiments:

- Experiment of statistical rates, for questions of Reviewer 6yVv (Figure 1).
- Impact of initialization on the convergence speed, for questions of Reviewer DCG2 (Figure 2, left).
- Impact of GMM mixture weights on the convergence speed, for questions of Reviewer DCG2 (Figure 2, right).

Please refer to the pdf for experimental setups and outcomes.

We have also improved our theorems, closing the gap between our upper bound and lower bound of convergence rates. This addresses the question of reviewer 6yVv. Please refer to our response to reviewer 6yVv for details.

We welcome and are happy to answer any further questions from reviewers.

Meta-review: As stated in the abstract, the paper's focus is the gradient expectation-maximization algorithm for Gaussian mixture models in the overparametrized regime: the authors consider the convergence properties of the problem when a single Gaussian is fitted by a mixture, showing that the considered algorithm converges globally with sublinear rate. The paper collected a positive consensus due to its clarity and novelty. Despite the apparent simplicity of the set-up, the extension of results already available in the literature to the case of generic Gaussian mixture is interesting, as it requires the introduction and application of nontrivial technical steps for the study of the non-convex optimization dynamics of the algorithm. I therefore recommend the acceptance of the manuscript.
Decision: Accept (poster)