Pith. sign in

REVIEW 4 major objections 4 minor 48 references

Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixtures

T0 review · 4 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that randomly initialized gradient EM converges globally to the ground truth for any well-separated Gaussian mixture model with only logarithmic overparameterization, giving the first global convergence guarantee for…

desk verdict First attempt at a global convergence result for over-parameterized gradient EM beyond m=2, but the advertised polynomial-rate guarantee does not follow from the stated assumptions. read the letter →

arxiv 2506.06584 v1 pith:XF2LFJUY submitted 2025-06-06 cs.LG stat.ML

Mo Zhou , Weihang Xu , Maryam Fazel , Simon S. Du This is my paper
classification cs.LGstat.ML
keywords gradientEMGaussianmixturemodelsover-parameterizationglobalconvergenceHermitepolynomialstensordecompositionidentifiabilityKLdivergence
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that overparameterization removes the main obstruction to learning Gaussian mixtures with EM: with $n = \Omega((1/\pi^*_{\min}) \log m)$ components, randomly initialized gradient EM converges globally to the ground truth for any well-separated $m$-component GMM, whereas exact-parameterized gradient EM provably fails for $m\ge 3$. The formal claim (Theorem 3.1) is that the KL loss drops to any target $\epsilon$ in $O(\sqrt{dn}/(\eta\epsilon_0)) + \mathrm{poly}(d,m,n,1/\pi^*_{\min},1/\lambda_{\min},D_{\max})/(\eta\sqrt{\epsilon})$ iterations, and as $\epsilon\to 0$ each surviving model mean coincides with a ground-truth mean while redundant means are pruned by zero weights. The proof splits into a global phase, which uses Hermite polynomials to force the loss below $\exp(-\Theta(\Delta^2))$, and a local phase, which uses test functions and tensor decomposition to prove identifiability. A finite-sample version achieves the same guarantees with polynomially many fresh samples per iteration. The authors present this as the first global convergence and recovery result for EM or gradient EM beyond the special case $m=2$.

What carries the argument

The argument hangs on a two-stage gradient analysis. During the global phase, the posterior membership functions $\psi_i$ are expanded in Hermite tensors---orthogonal polynomial functions under the Gaussian measure---and the identity $\mathbb{E}_{x\sim\mathcal{N}(\mu,I)}[He_k(x)] = \mu^{\otimes k}$ turns those expansions into moment-like quantities, giving a lower bound on the gradient of the KL loss in terms of the potential $U(\mu) = \sum_{\ell}\sum_{i\in S_\ell}\|\mu_i-\mu^*_\ell\|_2^2$. This drives the loss below $\epsilon_0=\exp(-\Theta(\Delta^2))$. During the local phase, test functions $g_k(x)=\langle He_k(x), v^{\otimes k}\rangle$ convert a KL upper bound into a bound on differences of $k$-th order moment tensors, and a whitening transformation reduces those differences to an orthogonal tensor decomposition whose perturbation analysis yields identifiability of weighted distances, group weights, and average component means. That identifiability then powers the $L^{3/4}$ gradient lower bound used to show convergence to arbitrary $\epsilon$.

What would settle it

Run Algorithm 2 with $n=m\log m$ components on a 3-component isotropic GMM whose means satisfy the stated separation $\Delta = C\sqrt{d}$, and record iterations to reach $L\le\epsilon$ and whether redundant weights vanish; if the loss stalls above $\exp(-\Theta(\Delta^2))$ or the iteration count is far worse than the theorem's bound, the gradient lower bound is wrong. A more targeted check is to evaluate the Hermite lower bound in Lemma E.5 at a parameter point where the loss is just above the threshold and verify it is positive at the claimed scale.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.1: under Assumptions 1, 2, and 3, if the learner uses $n = \Omega((1/\pi^*_{\min})\log m)$ components and a polynomially small step size $\eta$, then with probability at least $1 - 1/\mathrm{poly}(m)$, Algorithm 1 reaches loss $L(\mu,\pi)\le\epsilon$ within $O(\sqrt{dn}/(\eta\epsilon_0)) + \mathrm{poly}(d,m,n,1/\pi^*_{\min},1/\lambda_{\min},D_{\max})/(\eta\sqrt{\epsilon})$ iterations. In the limit $\epsilon\to 0$, for every $i$ either $\mu_i$ equals a ground-truth mean or $\pi_i=0$, so the model distribution equals $p^*$. This is stated as the first global convergence and recovery result for EM or gradient EM beyond the exact-parameterized $m=2$ case. The proof analyzes population gradient EM with near-optimal weight updates, then extends to an online finite-sample version with polynomial sample complexity.

Load-bearing premise

The load-bearing premise is that the ground-truth means are separated by at least $\Delta = \Omega(\sqrt{d})$ (together with standard boundedness and non-degeneracy conditions); for mixtures with smaller separation, the theorem's cross-term and identifiability arguments no longer apply.

Editorial extensions

If this is right

  • With $n=\Omega((1/\pi^*_{\min})\log m)$ fitted components, random initialization already places at least one component near each true component, so no warm start is needed.
  • The algorithm self-prunes: components that never align with a true mean are not explicitly removed, but their mixing weights converge to zero.
  • The online finite-sample version uses fresh samples each iteration and retains the guarantees, so the result is not a population-only artifact.
  • The theorem extends the known global-convergence regime beyond $m=2$, providing a positive answer to the overparameterization conjecture for gradient EM.
  • In the $\epsilon\to0$ limit, every model mean either equals a ground-truth mean exactly or has zero mixing weight, so the learned density identifies the ground truth.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The threshold $\epsilon_0=\exp(-\Theta(\Delta^2))$ means the stated run time is only polynomial when the separation $\Delta$ is fixed; removing this exponential dependence on $\Delta^2$ is the natural next step.
  • The Hermite/test-function bridge between EM and tensor decomposition may transfer to other overparameterized latent-variable models, where extra components could similarly erase spurious local minima.
  • Because the paper analyzes a two-timescale variant (near-optimal weight updates plus gradient mean updates), a testable open question is whether vanilla EM's full M-step inherits the same global convergence or whether fast weight updates are essential.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper studies population gradient EM with near-optimal weight updates for learning an m-component isotropic Gaussian mixture using an over-parameterized model with n>m components. Under general-position, boundedness, and well-separatedness assumptions, Theorem 3.1 claims that with n=Ω((1/π*_min)log m), random initialization, and sufficiently small step size, gradient EM reaches loss ε in T=O(√(dn)/(ηε0))+poly(d,m,n,1/π*_min,1/λ_min,D_max)/(η√ε) iterations, with recovery of the ground-truth means or pruning of redundant weights as ε→0. The analysis is two-stage: a global phase drives the loss below a threshold ε0=exp(-Θ(Δ²)), and a local phase gives O(1/T²) improvement using Hermite polynomials, test functions, tensor-decomposition identifiability, and gradient-norm lower bounds. A finite-sample version with polynomial sample complexity is also claimed.

Significance. If the main theorem were correct as stated, this would be the first global convergence and recovery result for (gradient) EM for general m-GMMs, and the technical machinery—Hermite expansions of the gradient, test-function lower bounds on KL divergence, and reduction to orthogonal tensor decomposition—would be a valuable bridge between EM analysis and method-of-moments guarantees. The proof contains no fitted parameters or target-dependent assumptions in the derivation of the identifiability and gradient lower bounds, which is a genuine strength. However, the advertised polynomial-rate and polynomial-sample claims are not supported by the stated assumptions; the threshold ε0 is exponentially small in dn, so the global phase is exponential in the problem size. The local-phase theorem as printed also contains a vacuous additive term. These issues affect the central contribution and must be resolved before the claims can be accepted.

major comments (4)
  1. [Theorem 3.1 and Assumptions 2–3; Theorem 4.2] The claimed polynomial time to reach loss ε is not established. Assumption 2 forces Dmax≥Dmin≥4(λmax/λmin)√(dn)≥4√(dn), and the second term in Assumption 3 then gives Δ≥C√(Dmax√(dn))≥2C√(dn). Hence the threshold ε0=exp(-Θ(Δ²)) in Theorem 4.2 is exp(-Θ(dn)), so the global-phase time T1=O(B/(ηε0)) is η^{-1} exp(Θ(dn)), which is exponential in d and n. The first term in the time bound of Theorem 3.1 is therefore not polynomial, and the sample complexity N in Theorem 3.3, which scales as ε0^{-5}, is also exponential. The statements in the abstract and Theorem 1.1 that gradient EM converges 'at a polynomial rate with polynomial samples' are unsupported by the theorem as written.
  2. [Remark 3] Remark 3 asserts that an 'effective dimension' trick reduces the separation requirement to Δ=Ω(√m) by citing [CSXZ24, §7.3.1], but no proof is given. Even if that reduction were valid, exp(-Θ(Δ²))=exp(-Θ(m)) with n=Θ(mlog m) equals exp(Θ(n/log n)), which is super-polynomial in n and not polynomial in 1/ε. Thus the remark does not rescue the polynomial-rate claim, and it should either be proved or removed from the statement of the main result.
  3. [Theorem 4.7] The local-phase bound as printed, L(µ(t),π(t))≤A²/(η(t-T1))²+A²/ε0, is vacuous for the intended purpose: the additive A²/ε0 term is a positive constant that already exceeds any target ε≤ε0, so the bound cannot imply convergence of the loss to ε. The proof in Appendix C actually derives the stronger estimate L(t)≤1/(η(t-T1)/(2A)+1/√L(T1))², which contains no additive A²/ε0 term. The statement of Theorem 4.7 must be corrected; otherwise the local phase, as stated, does not imply the final convergence claimed in Theorem 3.1.
  4. [Proof of Theorem 4.2 in Appendix E] The proof of Theorem 4.2 squares the gradient lower bound incorrectly. Theorem E.3 yields ∥∇µL∥_F ≥ (c1/B)min{1/d,L²}, so Lemma F.2 gives a loss decrease of at most -(ηc1²/(2B²))min{1/d²,L^4}, not -(η/B)min{1/d,L²} as written in the proof. The subsequent recurrence for 1/L and the bound T1=O(B/(ηε0)) therefore do not follow from the stated gradient lower bound. This is a separate quantitative error from the exponential dependence of ε0, and the global-phase time must be re-derived.
minor comments (4)
  1. [Assumption 2 and Lemma B.4] Assumption 2 is described as 'without loss of generality' and attributed to Lemma B.4, but Lemma B.4 only shows that one can translate the origin so that Dmax≥∥µ*_i∥≥Δ/2. It does not establish the quantitative lower bound 4(λmax/λmin)√(dn) used in Assumption 2; the assumption is a substantive condition, not a normalization.
  2. [Notation] The expression 'Sℓ(δclose) that is δclose-close to µ*_ℓ' in Section 4.3 is informal; the formal definition of Sℓ(δ) appears only in the proof of Theorem B.1. Defining this set in the main text would improve readability.
  3. [Theorem 3.3] The sample-complexity bound is stated with N depending on ε0, but ε0 is not a user-chosen target; the dependence of the total sample complexity on d,n, and m is therefore not transparent. A bound with explicit polynomial dependencies after substituting ε0=exp(-Θ(Δ²)) would clarify the statement, though it would also reveal the exponential dependence noted in the major comments.
  4. [Minor typos] There are several typographical errors, including 'poly(ε)-optimal 2 solution' in Algorithm 1, 'T able 1' in Table 1, and inconsistent notation such as 'δclose-close' and the unused 'Dmin' in a few displayed formulas. These should be cleaned up in revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof derives gradient lower bounds and identifiability from stated assumptions and external results; self-citations are technical, while the exponential-in-Delta^2 global phase is a correctness gap, not a circular reduction.

full rationale

I walked the derivation chain and found no step in which a claimed prediction is equivalent to its inputs by construction. Claim 2.1 (gradient EM equals gradient descent on the KL loss) is an algebraic identity proved directly; Theorem E.3 derives the global-phase gradient lower bound from Hermite expansions and the separation assumptions; Theorem B.1 derives identifiability from test-function and tensor-decomposition inequalities using external whitening and orthogonal-decomposition results [AGH+14, HK13]; Theorem 4.7 derives local convergence from the resulting gradient lower bound. Self-citations to [XFD24] and [ZGJ21] are used for a smoothness estimate, a Stein-lemma form of the gradient, and the test-function idea; none of these is cited as the source of the m>=3 global-convergence or recovery conclusion, so they are not load-bearing. I also flag a non-circular correctness concern: Theorem 3.1's first runtime term is O(sqrt(dn)/(eta eps0)) with eps0 = exp(-Theta(Delta^2)) (Theorem 4.2), and Assumptions 2 and 3 together imply Delta = Omega(sqrt(dn)), so as stated T1 is exponential rather than polynomial; Remark 3's effective-dimension reduction to Delta = Omega(sqrt(m)) is cited but unproved. This affects the advertised polynomial-rate claim, but it is an assumption-strength and quantitative-error issue, not a derivation that reduces the theorem to its own inputs.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted to data; the theorem's constants are unspecified but not estimated. The main burden is on the strong separation and boundedness axioms and on the algorithmic variant with convex weight updates.

assumptions (5)
  • domain assumption Ground-truth second moment matrix M*_2 has rank m with eigenvalues in [lambda_min, lambda_max] and lambda_min > 0 (Assumption 1).
    Used for whitening and tensor decomposition in Appendix B; if lambda_min = 0, the orthogonal tensor decomposition step fails.
  • domain assumption Ground-truth means are bounded with D_min >= 4 lambda_max/lambda_min sqrt(dn) and a D_max upper bound (Assumption 2).
    Provides norm bounds used throughout; the paper claims a translation argument makes the lower bound without loss of generality.
  • domain assumption Separation Delta is at least C max{sqrt(log(dnm D_max/(pi*_min lambda_min))), sqrt(D_max sqrt(dn)), sqrt(d/pi*_min)} (Assumption 3).
    Makes cross terms exp(-Theta(Delta^2)) negligible and supports the two-phase proof; it is very strong and ties Delta to d.
  • ad hoc to paper Near-optimal weight updates, i.e., solving min_pi L(pi, mu) to poly(epsilon) first-order optimality each iteration (Algorithm 1).
    This is not the vanilla gradient EM update; the paper claims it is a two-timescale limiting case in Remark 1, but convergence of that limit is not proved.
  • standard math Standard Hermite polynomial orthogonality, Stein's lemma, and the KL-chi-square comparison from NS20 are used without proof.
    These are standard results, but the KL lower bound via homotopy is central to the test-function argument.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixtures." pith.science (2026). https://pith.science/paper/XF2LFJUY

@misc{pith2026250606584,
  author       = {Pith},
  title        = {Pith review of: Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixtures},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XF2LFJUY}},
  note         = {Machine review of arXiv:2506.06584}
}
abstract

Learning Gaussian Mixture Models (GMMs) is a fundamental problem in machine learning, with the Expectation-Maximization (EM) algorithm and its popular variant gradient EM being arguably the most widely used algorithms in practice. In the exact-parameterized setting, where both the ground truth GMM and the learning model have the same number of components $m$, a vast line of work has aimed to establish rigorous recovery guarantees for EM. However, global convergence has only been proven for the case of $m=2$, and EM is known to fail to recover the ground truth when $m\geq 3$. In this paper, we consider the $\textit{over-parameterized}$ setting, where the learning model uses $n>m$ components to fit an $m$-component ground truth GMM. In contrast to the exact-parameterized case, we provide a rigorous global convergence guarantee for gradient EM. Specifically, for any well separated GMMs in general position, we prove that with only mild over-parameterization $n = \Omega(m\log m)$, randomly initialized gradient EM converges globally to the ground truth at a polynomial rate with polynomial samples. Our analysis proceeds in two stages and introduces a suite of novel tools for Gaussian Mixture analysis. We use Hermite polynomials to study the dynamics of gradient EM and employ tensor decomposition to characterize the geometric landscape of the likelihood loss. This is the first global convergence and recovery result for EM or Gradient EM beyond the special case of $m=2$.

Figures

Figures reproduced from arXiv: 2506.06584 by the authors.

Figure 1
Figure 1. Experiments: using n = 5, 10, and 15 Gaussians to learn a 5-GMM. Left: Dynamics of likelihood loss L, exact-parameterization v.s. over-parameterization; Middle: Exact-parameterized gradient EM converges to spurious local minima; Right: Global convergence trajectory of over-parameterized gradient EM. 4 Proof sketch: 2-stage analysis We provide a sketch of the proof, which follows a two-stage analysis: global converge… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

48 extracted references · 45 canonical work pages

  1. [1]

    Joseph Anderson, Mikhail Belkin, Navin Goyal, Luis Rademacher, and James R. Voss. The more, the merrier: the blessing of dimensionality for learning large gaussian mixtures. In Proceedings of 27th Conference on Learning Theory ( COLT ), Barcelona, Spain , volume 35, pages 1135--1164. JMLR.org, 2014

    work page 2014

  2. [2]

    Kakade, and Matus Telgarsky

    Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M. Kakade, and Matus Telgarsky. Tensor decompositions for learning latent variable models. Journal of Machine Learning Research , 15(80):2773--2832, 2014

    work page 2014

  3. [3]

    Learning time-scales in two-layers neural networks

    Rapha \"e l Berthier, Andrea Montanari, and Kangjie Zhou. Learning time-scales in two-layers neural networks. Foundations of Computational Mathematics , pages 1--84, 2024

    work page 2024

  4. [4]

    Stochastic approximation: a dynamical systems viewpoint , volume 9

    Vivek S Borkar. Stochastic approximation: a dynamical systems viewpoint , volume 9. Springer, 2008

    work page 2008

  5. [5]

    Ultra-fast feature learning for the training of two-layer neural networks in the two-timescale regime

    Rapha \"e l Barboni, Gabriel Peyr \'e , and Fran c ois-Xavier Vialard. Ultra-fast feature learning for the training of two-layer neural networks in the two-timescale regime. arXiv preprint arXiv:2504.18208 , 2025

    arXiv 2025

  6. [6]

    Mirror descent and nonlinear projected subgradient methods for convex optimization

    Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters , 31(3):167--175, 2003

    work page 2003

  7. [7]

    Wainwright, and Bin Yu

    Sivaraman Balakrishnan, Martin J. Wainwright, and Bin Yu. Statistical guarantees for the em algorithm: From population to sample-based analysis. The Annals of Statistics , 45(1):77--120, 2017

    work page 2017

  8. [8]

    Extreme ratio between spectral and frobenius norms of nonnegative tensors

    Shengyu Cao, Simai He, Zhening Li, and Zhen Wang. Extreme ratio between spectral and frobenius norms of nonnegative tensors. SIAM Journal on Matrix Analysis and Applications , 44(2):919--944, 2023

    work page 2023

Show all 48 references
  1. [9]

    Local minima structures in gaussian mixture models

    Yudong Chen, Dogyoon Song, Xumei Xi, and Yuqian Zhang. Local minima structures in gaussian mixture models. IEEE Transactions on Information Theory , 2024

    2024

  2. [10]

    Learning mixtures of gaussians

    Sanjoy Dasgupta. Learning mixtures of gaussians. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039) , pages 634--644. IEEE, 1999

    1999

  3. [11]

    Singularity, misspecification and the convergence rate of EM

    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

    2018

  4. [12]

    Wainwright, and Michael I

    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 , 2018

    2018

  5. [13]

    Wainwright, Michael I

    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

    2019

  6. [14]

    Maximum likelihood from incomplete data via the em algorithm

    Arthur P Dempster, Nan M Laird, and Donald B Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the royal statistical society: series B (methodological) , 39(1):1--22, 1977

    1977

  7. [15]

    Schulman

    Sanjoy Dasgupta and Leonard J. Schulman. A two-round variant of EM for gaussian mixtures. In Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence , UAI '00, page 152–159, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc

    2000

  8. [16]

    Ten steps of EM suffice for mixtures of two gaussians

    Constantinos Daskalakis, Christos Tzamos, and Manolis Zampetakis. Ten steps of EM suffice for mixtures of two gaussians. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 2017 Conference on Learning Theory , volume 65 of Proceedings of Machine Learning Research , pag...

    2017

  9. [17]

    A kernel two-sample test

    Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Sch \"o lkopf, and Alexander Smola. A kernel two-sample test. The Journal of Machine Learning Research , 13(1):723--773, 2012

    2012

  10. [18]

    Learning mixtures of gaussians in high dimensions

    Rong Ge, Qingqing Huang, and Sham M Kakade. Learning mixtures of gaussians in high dimensions. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing , pages 761--770, 2015

    2015

  11. [19]

    Learning mixtures of spherical gaussians: moment methods and spectral decompositions

    Daniel Hsu and Sham M Kakade. Learning mixtures of spherical gaussians: moment methods and spectral decompositions. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science , pages 11--20, 2013

    2013

  12. [20]

    Mixture models, robustness, and sum of squares proofs

    Samuel B Hopkins and Jerry Li. Mixture models, robustness, and sum of squares proofs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages 1021--1034, 2018

    2018

  13. [21]

    Revisiting frank-wolfe: Projection-free sparse convex optimization

    Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In International conference on machine learning , pages 427--435. PMLR, 2013

    2013

  14. [22]

    Local maxima in the likelihood of gaussian mixture models: Structural results and algorithmic consequences

    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

    2016

  15. [23]

    Robust learning of mixtures of gaussians

    Daniel M Kane. Robust learning of mixtures of gaussians. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1246--1258. SIAM, 2021

    2021

  16. [24]

    The EM algorithm gives sample-optimality for learning mixtures of well-separated gaussians

    Jeongyeol Kwon and Constantine Caramanis. The EM algorithm gives sample-optimality for learning mixtures of well-separated gaussians. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory , volume 125 of Proceedings of Machi...

    2020

  17. [25]

    Efficiently learning mixtures of two gaussians

    Adam Tauman Kalai, Ankur Moitra, and Gregory Valiant. Efficiently learning mixtures of two gaussians. In Proceedings of the forty-second ACM symposium on Theory of computing , pages 553--562, 2010

    2010

  18. [26]

    Robust moment estimation and improved clustering via sum of squares

    Pravesh K Kothari, Jacob Steinhardt, and David Steurer. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages 1035--1046, 2018

    2018

  19. [27]

    Homotopy analysis method in nonlinear differential equations , volume 153

    Shijun Liao. Homotopy analysis method in nonlinear differential equations , volume 153. Springer, 2012

    2012

  20. [28]

    Clustering mixtures with almost optimal separation in polynomial time

    Allen Liu and Jerry Li. Clustering mixtures with almost optimal separation in polynomial time. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 1248--1261, 2022

    2022

  21. [29]

    Robustly learning general mixtures of gaussians

    Allen Liu and Ankur Moitra. Robustly learning general mixtures of gaussians. Journal of the ACM , 70(3):1--53, 2023

    2023

  22. [30]

    On orthogonal tensors and best rank-one approximation ratio

    Zhening Li, Yuji Nakatsukasa, Tasuku Soma, and Andr \'e Uschmajew. On orthogonal tensors and best rank-one approximation ratio. SIAM Journal on Matrix Analysis and Applications , 39(1):400--425, 2018

    2018

  23. [31]

    Leveraging the two-timescale regime to demonstrate convergence of neural networks

    Pierre Marion and Rapha \"e l Berthier. Leveraging the two-timescale regime to demonstrate convergence of neural networks. Advances in Neural Information Processing Systems , 36:64996--65029, 2023

    2023

  24. [32]

    On relations between the relative entropy and 2-divergence, generalizations and applications

    Tomohiro Nishiyama and Igal Sason. On relations between the relative entropy and 2-divergence, generalizations and applications. Entropy , 22(5):563, 2020

    2020

  25. [33]

    Primer on monotone operator methods

    Ernest K Ryu and Stephen Boyd. Primer on monotone operator methods. Appl. comput. math , 15(1):3--43, 2016

    2016

  26. [34]

    On learning mixtures of well-separated gaussians

    Oded Regev and Aravindan Vijayaraghavan. On learning mixtures of well-separated gaussians. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 85--96. IEEE, 2017

    2017

  27. [35]

    Improved convergence guarantees for learning gaussian mixture models by em and gradient em

    Nimrod Segol and Boaz Nadler. Improved convergence guarantees for learning gaussian mixture models by em and gradient em. Electronic journal of statistics , 15(2):4510--4544, 2021

    2021

  28. [36]

    Estimation of the mean of a multivariate normal distribution

    Charles M Stein. Estimation of the mean of a multivariate normal distribution. The Annals of Statistics , pages 1135--1151, 1981

    1981

  29. [37]

    Mean-field analysis on two-layer neural networks from a kernel perspective

    Shokichi Takakura and Taiji Suzuki. Mean-field analysis on two-layer neural networks from a kernel perspective. In Forty-first International Conference on Machine Learning , 2024

    2024

  30. [38]

    The EM algorithm is adaptively-optimal for unbalanced symmetric gaussian mixtures

    Nir Weinberger and Guy Bresler. The EM algorithm is adaptively-optimal for unbalanced symmetric gaussian mixtures. J. Mach. Learn. Res. , 23:103:1--103:79, 2021

    2021

  31. [39]

    On the convergence properties of the em algorithm

    CF Jeff Wu. On the convergence properties of the em algorithm. The Annals of statistics , pages 95--103, 1983

    1983

  32. [40]

    Randomly initialized EM algorithm for two-component gaussian mixture achieves near optimality in o( n ) iterations

    Yihong Wu and Harrison H Zhou. Randomly initialized EM algorithm for two-component gaussian mixture achieves near optimality in o( n ) iterations. Mathematical Statistics and Learning , 4(3), 2021

    2021

  33. [41]

    Over-parameterization exponentially slows down gradient descent for learning a single neuron

    Weihang Xu and Simon Du. Over-parameterization exponentially slows down gradient descent for learning a single neuron. In The Thirty Sixth Annual Conference on Learning Theory , pages 1155--1198. PMLR, 2023

    2023

  34. [42]

    Toward global convergence of gradient EM for over-paramterized gaussian mixture models

    Weihang Xu, Maryam Fazel, and Simon Shaolei Du. Toward global convergence of gradient EM for over-paramterized gaussian mixture models. In The Thirty-eighth Annual Conference on Neural Information Processing Systems , 2024

    2024

  35. [43]

    Hsu, and Arian Maleki

    Ji Xu, Daniel J. Hsu, and Arian Maleki. Global analysis of expectation maximization for mixtures of two gaussians. In Neural Information Processing Systems , 2016

    2016

  36. [44]

    On convergence properties of the EM algorithm for gaussian mixtures

    Lei Xu and Michael I Jordan. On convergence properties of the EM algorithm for gaussian mixtures. Neural computation , 8(1):129--151, 1996

    1996

  37. [45]

    Convergence of gradient em on multi-component mixture of gaussians

    Bowei Yan, Mingzhang Yin, and Purnamrita Sarkar. Convergence of gradient em on multi-component mixture of gaussians. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems , vol...

    2017

  38. [46]

    How does gradient descent learn features --- a local analysis for regularized two-layer neural networks

    Mo Zhou and Rong Ge. How does gradient descent learn features --- a local analysis for regularized two-layer neural networks. In The Thirty-eighth Annual Conference on Neural Information Processing Systems , 2024

    2024

  39. [47]

    A local convergence theory for mildly over-parameterized two-layer neural network

    Mo Zhou, Rong Ge, and Chi Jin. A local convergence theory for mildly over-parameterized two-layer neural network. In Conference on Learning Theory , pages 4577--4632. PMLR, 2021

    2021

  40. [48]

    Statistical convergence of the em algorithm on gaussian mixture models

    Ruofei Zhao, Yuanzhi Li, and Yuekai Sun. Statistical convergence of the em algorithm on gaussian mixture models. Electronic Journal of Statistics , 14:632--660, 2020

    2020

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.