# EM for Mixture of Linear Regression with Clustered Data

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 46 references that are in the map.
- First posted on arXiv 22 Aug 2023.

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

- [Benchmarking Neural Network Robustness to Common Corruptions and Perturbations](https://mlsanity.com/paper/1903.12261/) (2019)
- [DeepXplore: Automated Whitebox Testing of Deep Learning Systems](https://mlsanity.com/paper/1705.06640/) (2017)
- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018)
- [Ten Steps of EM Suffice for Mixtures of Two Gaussians](https://mlsanity.com/paper/1609.00368/) (2016)
- [Learning Mixtures of Linear Regressions with Nearly Optimal Complexity](https://mlsanity.com/paper/1802.07895/) (2018)
- [Global analysis of Expectation Maximization for mixtures of two Gaussians](https://mlsanity.com/paper/1608.07630/) (2016)
- [EM Converges for a Mixture of Many Linear Regressions](https://mlsanity.com/paper/1905.12106/) (2019)
- [Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in O(√n) iterations](https://mlsanity.com/paper/1908.10935/) (2019)
- [Model-Based Robust Deep Learning: Generalizing to Natural, Out-of-Distribution Data](https://mlsanity.com/paper/2005.10247/) (2020)
- [Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimization](https://mlsanity.com/paper/1608.05749/) (2016)
- [Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments](https://mlsanity.com/paper/1912.07629/) (2019)
- [Global Convergence of EM Algorithm for Mixtures of Two Component Linear Regression](https://mlsanity.com/paper/1810.05752/) (2018)
- [On the Minimax Optimality of the EM Algorithm for Learning Two-Component Mixed Linear Regression](https://mlsanity.com/paper/2006.02601/) (2020)
- [Regularized EM Algorithms: A Unified Framework and Statistical Guarantees](https://mlsanity.com/paper/1511.08551/) (2015)
- [Estimating the Coefficients of a Mixture of Two Linear Regressions by Expectation Maximization](https://mlsanity.com/paper/1704.08231/) (2017)
- [Alternating Minimization Converges Super-Linearly for Mixed Linear Regression](https://mlsanity.com/paper/2004.10914/) (2020)
- [A Wasserstein Minimax Framework for Mixed Linear Regression](https://mlsanity.com/paper/2106.07537/) (2021)

## Built on by (most cited first, 1 of 1)

- [Fast convergence of a Federated Expectation-Maximization Algorithm](https://mlsanity.com/paper/2408.05819/) (2024)

## Abstract (arXiv)

Modern data-driven and distributed learning frameworks deal with diverse massive data generated by clients spread across heterogeneous environments. Indeed, data heterogeneity is a major bottleneck in scaling up many distributed learning paradigms. In many settings however, heterogeneous data may be generated in clusters with shared structures, as is the case in several applications such as federated learning where a common latent variable governs the distribution of all the samples generated by a client. It is therefore natural to ask how the underlying clustered structures in distributed data can be exploited to improve learning schemes. In this paper, we tackle this question in the special case of estimating d-dimensional parameters of a two-component mixture of linear regressions problem where each of m nodes generates n samples with a shared latent variable. We employ the well-known Expectation-Maximization (EM) method to estimate the maximum likelihood parameters from m batches of dependent samples each containing n measurements. Discarding the clustered structure in the mixture model, EM is known to require O(log(mn/d)) iterations to reach the statistical accuracy of O(√d/(mn)). In contrast, we show that if initialized properly, EM on the structured data requires only O(1) iterations to reach the same statistical accuracy, as long as m grows up as eo(n). Our analysis establishes and combines novel asymptotic optimization and generalization guarantees for population and empirical EM with dependent samples, which may be of independent interest.