Statistical guarantees for the EM algorithm: From population to sample-based analysis

By Sivaraman Balakrishnan, Martin J. Wainwright, Bin Yu. arXiv.org, 2014

540 citations recorded by the source corpus.

We develop a general framework for proving rigorous guarantees on the performance of the EM algorithm and a variant known as gradient EM. Our analysis is divided into two parts: a treatment of these algorithms at the population level (in the limit of infinite data), followed by results that apply to updates based on a finite set of samples. First, we characterize the domain of attraction of any global maximizer of the population likelihood. This characterization is based on a novel view of the EM updates as a perturbed form of likelihood ascent, or in parallel, of the gradient EM updates as a perturbed form of standard gradient ascent. Leveraging this characterization, we then provide non-asymptotic guarantees on the EM and gradient EM algorithms when applied to a finite set of samples. We develop consequences of our general theory for three canonical examples of incomplete-data problems: mixture of Gaussians, mixture of regressions, and linear regression with covariates missing completely at random. In each case, our theory guarantees that with a suitable initialization, a relatively small number of EM (or gradient EM) steps will yield (with high probability) an estimate that is within statistical error of the MLE. We provide simulations to confirm this theoretically predicted behavior.

Subfields: Artificial Intelligence, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/b422a2d3ef04399c1d2135d941196613f6255f16

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Spectral Methods Meet EM: A Provably Optimal Algorithm for Crowdsourcing (2014, methodology): “One idea is to improve those lower bounds using the technique from Balakrishnan et al. (2016) discussed in Section 2.”
Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning (2018, background): “, 2018), and structured non-convex problems (Balakrishnan et al., 2014; Chen & Wainwright, 2015; Candes et al., 2015; Zhang et al., 2016).”
Mixture models, robustness, and sum of squares proofs (2017, background): “The works [6, 20, 22, 69] offer some theoretical guarantees for EM, but non-convergence results are a barrier to strong theoretical guarantees [68].”
Non-convex Optimization for Machine Learning (2017, methodology): “THE EM ALGORITHM Definition 5.4 (First Order Stability [Balakrishnan et al., 2017]).”
Robust estimation via robust gradient estimation (2018, background): “Our contributions in this direction are two-fold: building on prior work [18] we provide a general result on the stability of gradient descent for risk minimization, and show that under certain conditions, gradient descent can be quite tolerant to inaccurate gradient estimates.”
A Survey of Optimization Methods From a Machine Learning Perspective (2019, background): “include projection gradient descent [138], [139]; alternating minimization [140]–[142]; expectation maximization algorithm [143], [144]; and stochastic”
Singularity, misspecification and the convergence rate of EM (2018, methodology): “[1] leads to a sub-optimal guarantee for sample EM in the case of balanced mixtures (see Section 2.”
Learning with Bad Training Data via Iterative Trimmed Loss Minimization (2018, methodology): “Alternating minimization type algorithms are used for mixed linear regression with convergence guarantee [YCS14, BWY + 17], in the setting of two mixtures.”
Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems (2015, background): “(38) Here, one has (4− )‖h‖2 in (37) instead of 4‖h‖2 to account for the bias introduced by adaptive trimming, where is small as long as we only throw away a small fraction of data.”
An Efficient Framework for Clustered Federated Learning (2020, background): “In recent years, some progress has been made towards understanding the convergence of EM and AM in the centralized setting (Netrapalli et al., 2013; Daskalakis et al., 2016; Yi et al., 2016; Balakrishnan et al., 2017; Waldspurger, 2018).”
Guaranteed Matrix Completion via Non-Convex Factorization (2014, background): “In a recent work [34] the authors have managed to remove the dependency of the required sample size on (cid”
Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees (2015, background): “It is also worth noting that other types of algorithms for nonconvex problems have also been analyzed, including alternating minimization [37, 32, 34], EM algorithms [4, 63] and power methods [33], various hard-thresholding and singular value projection [36, 53, 38, 9], gradient descent for nonconve”
Functional Gradient Boosting based on Residual Network Perception (2018, methodology): “To remedy the exponential dependence on T of the generalization bound, we introduce the sample-splitting technique which has been used recently to provide statistical guarantee of expectation-maximization algorithms (Balakrishnan et al., 2017; Wang et al., 2015).”