Sharp analysis of EM for learning mixtures of pairwise differences

2023/02/20 by Abhishek Dhawan, Cheng Mao, Dhawan, Abhishek +3
Computer Science · Decision Sciences · #Advanced Statistical Process Monitoring #Bayesian Methods and Mixture Models #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.2302.10066

openalex publication_date 2023/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 ℓ₂-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.

Related

• Ten Steps of EM Suffice for Mixtures of Two Gaussians
• EM Converges for a Mixture of Many Linear Regressions
• Estimating the Coefficients of a Mixture of Two Linear Regressions by Expectation Maximization
• Singularity, Misspecification, and the Convergence Rate of EM
• Statistical Convergence of the EM Algorithm on Gaussian Mixture Models