cs.LGApr 7, 2026

Expectation Maximization (EM) Converges for General Agnostic Mixtures

Authors: Avishek Ghosh

Organizations: Department of Computer Science and Engineering, IIT Bombay, Mumbai, India

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Mixture of linear regression is well studied in statistics and machine learning, where the data points are generated probabilistically using kk linear models. Algorithms like Expectation Maximization (EM) may be used to recover the ground truth regressors for this problem. Recently, in \cite{pal2022learning,ghosh_agnostic} the mixed linear regression problem is studied in the agnostic setting, where no generative model on data is assumed. Rather, given a set of data points, the objective is fit kk lines by minimizing a suitable loss function. It is shown that a modification of EM, namely gradient EM converges exponentially to appropriately defined loss minimizer even in the agnostic setting. In this paper, we study the problem of fitting kk parametric functions to given set of data points. We adhere to the agnostic setup. However, instead of fitting lines equipped with quadratic loss, we consider any arbitrary parametric function fitting equipped with a strongly convex and smooth loss. This framework encompasses a large class of problems including mixed linear regression (regularized), mixed linear classifiers (mixed logistic regression, mixed Support Vector Machines) and mixed generalized linear regression. We propose and analyze gradient EM for this problem and show that with proper initialization and separation condition, the iterates of gradient EM converge exponentially to appropriately defined population loss minimizers with high probability. This shows the effectiveness of EM type algorithm which converges to optimal solution in the non-generative setup beyond mixture of linear regression.

Figures & tables

 θj(t+1)=θj(t)−γn′∑i=1n′p~(θj(t))∇F(xi(t),yi(t);θj(t)),\displaystyle\theta^{(t+1)}_{j}=\theta^{(t)}_{j}-\frac{\gamma}{n^{\prime}}\sum_{i=1}^{n^{\prime}}\tilde{p}(\theta^{(t)}_{j})\nabla F(x_{i}^{(t)},y_{i}^{(t)};\theta^{(t)}_{j}), 
Algorithm 1 Gradient EM
More in this topic

Expectation-Maximization

Expectation-Maximization (EM) fits latent-variable models by alternating hidden-variable inference with parameter updates.

See all 26 papers

Explore similar work

CardsList
Sep 4, 2026

Connecting Score Matching, Maximum Likelihood, and Expectation-Maximization in Mixed Linear Regression

We study variance-preserving diffusion of the response in mixed linear regression (MLR) with unknown mixing weights. Our analysis separates the statistical guarantees of score matching from the loss geometry and optimization signal at a fixed diffusion noise level. The KL divergence links the denoising score matching objective integrated over the diffusion path with the likelihood and a terminal discrepancy. Under mild regularity conditions and terminal schedule, the resulting estimator converges up to the ground truth parameters of MLR, and its scaled error converges to the Gaussian limit of the maximum-likelihood estimator. At a fixed scale of the diffusion noise level, we derive a decomposition linking the score matching loss to cross-entropy and Expectation-Maximization (EM) operators. This decomposition yields an EM-related low-noise gradient expansion with additional correction terms of latent variance. In the high-noise limit, we further characterize gradient descent on this limiting loss under isotropic covariance. Along fixed high signal-to-noise ratio rays, the score matching imbalance gradient and the latent-variance term tend to zero pointwise. Numerical experiments illustrate our theoretical findings and statistical guarantees.

Zhankun Luo, Abolfazl Hashemi

School of Electrical and Computer Engineering Purdue University, West Lafayette, IN, USA

Score MatchingMixed-Effects ModelsStatistical Learning TheoryExpectation-Maximization
AskPDF
May 29, 2026

Local linear convergence of gradient methods for overparameterized Gaussian mixtures

We study the problem of learning Gaussian mixture models under overparameterization. Prior work has shown that while overparameterization is essential for avoiding spurious local optima and enables global recovery of the ground-truth model using the gradient-EM (expectation-maximization) algorithm, it can dramatically slow down the local rate of convergence. Under certain assumptions on the mixture weights, we show that a standard divergence measure minimized by statistical learning procedures possesses a manifold of slow growth on which the well-known Polyak stepsize reduces the loss geometrically, and design a gradient-based method that converges to minimizers at a locally linear rate. Additionally, we show that our method converges to nearly optimal solutions -- up to a natural misspecification threshold -- for mixtures with arbitrary weights. At a high level, the method alternates between several "short" gradient descent steps that approach the manifold and "long" Polyak steps that contract the distance to minimizers. Our results suggest that slow convergence is not an intrinsic challenge of overparameterization, but can be overcome by exploiting the favorable structure of the loss landscape.

Jingxing Wang, Vasileios Charisopoulos, Maryam Fazel

Electrical & Computer Engineering, University of Washington, Seattle, WA · National Institute for Theory and Mathematics in Biology, Chicago, IL · Amazon, Inc.

Gradient DescentGaussian Mixture ModelsConvergence Analysis
AskPDF
Sep 16, 2024

The EM-algorithm and the Method of Moments in Softmax Mixture Models

Softmax Mixture Models (SMMs) are discrete KK-component mixture models for the probabilities of selecting one of pp candidate feature vectors X1,…,Xp∈RLX_1,\ldots,X_p\in\mathbb{R}^L in heterogeneous populations and are widely used in econometrics and scientific applications. Related softmax mixture mechanisms also appear in modern LLM architectures. We provide a theoretical and methodological study of SMMs, focusing on the Expectation-Maximization (EM) algorithm and the Method of Moments (MoM). We show that EM recovers the mixture atoms at the parametric rate, up to logarithmic factors, after O(log⁡N)\mathcal{O}(\log N) iterations, provided atom separation is at least of order log⁡K\log K. This improves on separation conditions in existing analyses of EM for high-dimensional Gaussian mixtures. We also develop MoM procedures for parameter and subspace estimation. Although MoM parameter estimates converge more slowly than EM and can deteriorate with KK, they provide provable warm starts for EM and are useful for small KK. For general KK, we estimate the atom subspace via MoM and recommend running EM from multiple random initializations within this subspace. Finally, as p→∞p\to\infty, we show that SMMs approximate mixtures of exponential tilts of the feature distribution, yielding asymptotic identifiability.

Xin Bing, Florentina Bunea, Jonathan Niles-Weed +1

Department of Statistical Sciences, University of Toronto · Department of Statistics and Data Science, Cornell University · Courant Institute of Mathematical Sciences and Center for Data Science, New York University +1

Expectation-MaximizationDiscrete Choice ModelingStatistical Learning Theory
AskPDF