A Fast Algorithm for Maximum Likelihood Estimation of Mixture Proportions Using Sequential Quadratic Programming

Abstract

Maximum likelihood estimation of mixture proportions has a long history, and continues to play an important role in modern statistics, including in development of nonparametric empirical Bayes methods. Maximum likelihood of mixture proportions has traditionally been solved using the expectation maximization (EM) algorithm, but recent work by Koenker and Mizera shows that modern convex optimization techniques—in particular, interior point methods—are substantially faster and more accurate than EM. Here, we develop a new solution based on sequential quadratic programming (SQP). It is substantially faster than the interior point method, and just as accurate. Our approach combines several ideas: first, it solves a reformulation of the original problem; second, it uses an SQP approach to make the best use of the expensive gradient and Hessian computations; third, the SQP iterations are implemented using an active set method to exploit the sparse nature of the quadratic subproblems; fourth, it uses accurate low-rank approximations for more efficient gradient and Hessian computations. We illustrate the benefits of the SQP approach in experiments on synthetic datasets and a large genetic association dataset. In large datasets ($n\approx {10}^6$ observations, $m\approx {10}^3$ mixture components), our implementation achieves at least 100-fold reduction in runtime compared with a state-of-the-art interior point solver. Our methods are implemented in Julia and in an R package available on CRAN (https://CRAN.R-project.org/package=mixsqp). Supplementary materials for this article are available online.

Keywords:

• Active set methods
• Convex optimization
• Mixture models
• Nonparametric empirical Bayes
• Rank-revealing QR decomposition
• Sequential quadratic programming

Supplementary Materials

Accompanying source code and data: Example datasets, source code including Jupyter notebooks, and instructions for running code (mixsqp.zip).

Note

Notes

1 minConF_SPG.m was retrieved from https://www.cs.ubc.ca/spider/schmidtm/Software/minConf.html.

Additional information

Funding

Also, preprint ANL/MCS-P9073-0618, Argonne National Laboratory. This material was based upon work supported by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research (ASCR) under contract DE-AC02-06CH11347. We acknowledge partial NSF funding through awards FP061151-01-PR and CNS-1545046 to MA, and support from NIH grant HG002585 and a grant from the Gordon and Betty Moore Foundation to MS. We thank the staff of the University of Chicago Research Computing Center for providing high-performance computing resources used to implement some of the numerical experiments. We thank Joe Marcus for his help in processing the GIANT data, and other members of the Stephens lab for feedback on the methods and software.