# Learning and Generalization with Mixture Data

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 26 references that are in the map.
- First posted on arXiv 29 Apr 2025.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [Learning Mixtures of Linear Regressions with Nearly Optimal Complexity](https://mlsanity.com/paper/1802.07895/) (2018)
- [Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimization](https://mlsanity.com/paper/1608.05749/) (2016)
- [Spectral Experts for Estimating Mixtures of Linear Regressions](https://mlsanity.com/paper/1306.3729/) (2013)
- [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)
- [On Learning Mixture of Linear Regressions in the Non-Realizable Setting](https://mlsanity.com/paper/2205.13166/) (2022)
- [Sample Complexity of Learning Mixtures of Sparse Linear Regressions](https://mlsanity.com/paper/1910.14106/) (2019)
- [Recovery of Sparse Signals from a Mixture of Linear Samples](https://mlsanity.com/paper/2006.16406/) (2020)
- [Recovery of sparse linear classifiers from mixture of responses](https://mlsanity.com/paper/2010.12087/) (2020)

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

- [OctoMed: Data Recipes for State-of-the-Art Multimodal Medical Reasoning](https://mlsanity.com/paper/2511.23269/) (2025)
- [Divide and Predict: An Architecture for Input Space Partitioning and Enhanced Accuracy](https://mlsanity.com/paper/2603.08649/) (2026)

## Abstract (arXiv)

In many, if not most, machine learning applications the training data is naturally heterogeneous (e.g. federated learning, adversarial attacks and domain adaptation in neural net training). Data heterogeneity is identified as one of the major challenges in modern day large-scale learning. A classical way to represent heterogeneous data is via a mixture model. In this paper, we study generalization performance and statistical rates when data is sampled from a mixture distribution. We first characterize the heterogeneity of the mixture in terms of the pairwise total variation distance of the sub-population distributions. Thereafter, as a central theme of this paper, we characterize the range where the mixture may be treated as a single (homogeneous) distribution for learning. In particular, we study the generalization performance under the classical PAC framework and the statistical error rates for parametric (linear regression, mixture of hyperplanes) as well as non-parametric (Lipschitz, convex and H"older-smooth) regression problems. In order to do this, we obtain Rademacher complexity and (local) Gaussian complexity bounds with mixture data, and apply them to get the generalization and convergence rates respectively. We observe that as the (regression) function classes get more complex, the requirement on the pairwise total variation distance gets stringent, which matches our intuition. We also do a finer analysis for the case of mixed linear regression and provide a tight bound on the generalization error in terms of heterogeneity.