# Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Aug 2018.

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

- [Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression](https://mlsanity.com/paper/2303.02118/) (2023)
- [Mixed Regression via Approximate Message Passing](https://mlsanity.com/paper/2304.02229/) (2023)
- [Semi-Supervised Sparse Gaussian Classification: Provable Benefits of Unlabeled Data](https://mlsanity.com/paper/2409.03335/) (2024)
- [An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds](https://mlsanity.com/paper/2506.06259/) (2025)
- [Subspace clustering in high-dimensions: Phase transitions & Statistical-to-Computational gap](https://mlsanity.com/paper/2205.13527/) (2022)
- [Sparse Linear Regression when Noises and Covariates are Heavy-Tailed and Contaminated by Outliers](https://mlsanity.com/paper/2408.01336/) (2024)

## Abstract (arXiv)

We study the fundamental tradeoffs between statistical accuracy and computational tractability in the analysis of high dimensional heterogeneous data. As examples, we study sparse Gaussian mixture model, mixture of sparse linear regressions, and sparse phase retrieval model. For these models, we exploit an oracle-based computational model to establish conjecture-free computationally feasible minimax lower bounds, which quantify the minimum signal strength required for the existence of any algorithm that is both computationally tractable and statistically accurate. Our analysis shows that there exist significant gaps between computationally feasible minimax risks and classical ones. These gaps quantify the statistical price we must pay to achieve computational tractability in the presence of data heterogeneity. Our results cover the problems of detection, estimation, support recovery, and clustering, and moreover, resolve several conjectures of Azizyan et al. (2013, 2015); Verzelen and Arias-Castro (2017); Cai et al. (2016). Interestingly, our results reveal a new but counter-intuitive phenomenon in heterogeneous data analysis that more data might lead to less computation complexity.