mlsanityData to 7 Oct 2026

Sharp analysis of EM for learning mixtures of pairwise differences

arXiv 2302.10066 ↗First posted 20 Feb 2023math.ST cs.LG stat.MLcited by 1

Not on the map. Why?

Abstract (arXiv)

We consider a symmetric mixture of linear regressions with random samples from the pairwise comparison design, which can be seen as a noisy version of a type of Euclidean distance geometry problem. We analyze the expectation-maximization (EM) algorithm locally around the ground truth and establish that the sequence converges linearly, providing an ℓ_∞-norm guarantee on the estimation error of the iterates. Furthermore, we show that the limit of the EM sequence achieves the sharp rate of estimation in the ℓ2-norm, matching the information-theoretically optimal constant. We also argue through simulation that convergence from a random initialization is much more delicate in this setting, and does not appear to occur in general. Our results show that the EM algorithm can exhibit several unique behaviors when the covariate distribution is suitably structured.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 32 of its 70 references that are in the map. First posted on arXiv 20 Feb 2023.

Builds on

32 of 70 references.

References · 32

  1. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  2. 2014Statistical guarantees for the EM algorithm: From population to sample-based analysiscited by 131
  3. 2020Spectral Methods for Data Science: A Statistical Perspectivecited by 111
  4. 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
  5. 2016Ten Steps of EM Suffice for Mixtures of Two Gaussianscited by 40
  6. 2018Singularity, Misspecification, and the Convergence Rate of EMcited by 38
  7. 2018Learning Mixtures of Linear Regressions with Nearly Optimal Complexitycited by 37
  8. 2017Near-optimal bounds for phase synchronizationcited by 32
  9. 2016Global analysis of Expectation Maximization for mixtures of two Gaussianscited by 31
  10. 2019EM Converges for a Mixture of Many Linear Regressionscited by 27
  11. 2019Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in O(√n) iterationscited by 27
  12. 2019Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Momentscited by 26
20 more
  1. 2018Global Convergence of EM Algorithm for Mixtures of Two Component Linear Regressioncited by 25
  2. 2020On the Minimax Optimality of the EM Algorithm for Learning Two-Component Mixed Linear Regressioncited by 24
  3. 2013Spectral Experts for Estimating Mixtures of Linear Regressionscited by 22
  4. 2016Learning Mixtures of Plackett-Luce Modelscited by 19
  5. 2017Estimating the Coefficients of a Mixture of Two Linear Regressions by Expectation Maximizationcited by 19
  6. 2018Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-rank Matrix Completioncited by 18
  7. 2021Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptroncited by 18
  8. 2021Optimal Full Ranking from Pairwise Comparisonscited by 16
  9. 2021Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspectivecited by 10
  10. 2013Learning Mixtures of Linear Classifierscited by 8
  11. 2022On the identifiability of mixtures of ranking modelscited by 7
  12. 2020Learning Mixtures of Permutations: Groups of Pairwise Comparisons and Combinatorial Method of Momentscited by 6
  13. 2015Bayesian mixture of Plackett-Luce models for partially ranked datacited by 5
  14. 2017Solving Partial Differential Equations on Manifolds From Incomplete Inter-Point Distancecited by 5
  15. 2019Global Convergence of Least Squares EM for Demixing Two Log-Concave Densitiescited by 5
  16. 2020Exact Minimax Estimation for Phase Synchronizationcited by 5
  17. 2020Learning Mixtures of Random Utility Models with Features from Incomplete Preferencescited by 4
  18. 2023Efficient and Accurate Learning of Mixtures of Plackett-Luce Modelscited by 3
  19. 2020An extension of the angular synchronization problem to the heterogeneous settingcited by 2
  20. 2022EM's Convergence in Gaussian Latent Tree Modelscited by 2

Built on by

Cited by year

Citing papers per year: 2023: 1.

1 paper.

  1. 2023Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passingcited by 5