# Sublinear Variational Optimization of Gaussian Mixture Models with Millions to Billions of Parameters

arXiv: https://arxiv.org/abs/2501.12299 · HTML: https://mlsanity.com/paper/2501.12299/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 63 references that are in the map.
- First posted on arXiv 21 Jan 2025.

## Builds on (most cited first, 15 of 15)

- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [HuBERT: Self-Supervised Speech Representation Learning by Masked Prediction of Hidden Units](https://mlsanity.com/paper/2106.07447/) (2021)
- [EVA: Exploring the Limits of Masked Visual Representation Learning at Scale](https://mlsanity.com/paper/2211.07636/) (2022)
- [Stable and low-precision training for large-scale vision-language models](https://mlsanity.com/paper/2304.13013/) (2023)
- [On GANs and GMMs](https://mlsanity.com/paper/1805.12462/) (2018)
- [Training Gaussian Mixture Models at Scale via Coresets](https://mlsanity.com/paper/1703.08110/) (2017)
- [PCA Reduced Gaussian Mixture Models with Applications in Superresolution](https://mlsanity.com/paper/2009.07520/) (2020)
- [k-means as a variational EM approximation of Gaussian mixture models](https://mlsanity.com/paper/1704.04812/) (2017)
- [Large Scale Clustering with Variational EM for Gaussian Mixture Models](https://mlsanity.com/paper/1810.00803/) (2018)
- [Evolutionary Variational Optimization of Generative Models](https://mlsanity.com/paper/2012.12294/) (2020)
- [A sampling-based approach for efficient clustering in large datasets](https://mlsanity.com/paper/2112.14793/) (2021)
- [Truncated Variational Expectation Maximization](https://mlsanity.com/paper/1610.03113/) (2016)
- [GP-select: Accelerating EM using adaptive subspace preselection](https://mlsanity.com/paper/1412.3411/) (2014)
- [Neural Simpletrons - Minimalistic Directed Generative Networks for Learning with Few Labels](https://mlsanity.com/paper/1506.08448/) (2015)

## Abstract (arXiv)

Gaussian Mixture Models (GMMs) range among the most frequently used models in machine learning. However, training large, general GMMs becomes computationally prohibitive for data sets that have many data points N of high-dimensionality D. For GMMs with arbitrary covariances, we here derive a highly efficient variational approximation, which is then integrated with mixtures of factor analyzers (MFAs). For GMMs with C components, our proposed algorithm substantially reduces runtime complexity from O(NCD2) per iteration to a complexity scaling linearly with D and sublinearly with NC. In numerical experiments, we first validate that the complexity reduction results in a sublinear scaling for the entire GMM optimization process. Second, we show on large-scale benchmarks that the sublinear algorithm results in speed-ups of an order-of-magnitude compared to the state-of-the-art. Third, as a proof of concept, we finally train GMMs with over 10 billion parameters on about 100 million images, observing training times of less than nine hours on a single state-of-the-art CPU. Finally, and fourth, we demonstrate the effectiveness of large-scale GMMs on the task of zero-shot image denoising, where sublinear training results in state-of-the-art denoising times while competitive denoising performance is maintained.