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

Abstract

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.

arXiv comment75 pages

References in corpus (21)

• Challenges of Big Data Analysis
• Optimal detection of sparse principal components in high dimension
• Incoherence-Optimal Matrix Completion
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Polynomial Learning of Distribution Families
• A Two-round Variant of EM for Gaussian Mixtures
• Computational barriers in minimax submatrix detection
• Lower bounds on the performance of polynomial-time algorithms for sparse linear regression
• Alternating Minimization for Mixed Linear Regression
• Computational Lower Bounds for Sparse PCA
• Settling the Polynomial Learnability of Mixtures of Gaussians
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• Sparse PCA via Covariance Thresholding
• More data speeds up training time in learning halfspaces over sparse vectors
• High Dimensional Expectation-Maximization Algorithm: Statistical Optimization and Asymptotic Normality
• Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure
• Learning Mixtures of Gaussians in High Dimensions
• Learning Gaussian Mixtures with Arbitrary Separation
• High dimensional Sparse Gaussian Graphical Mixture Model
• Sharp Computational-Statistical Phase Transitions via Oracle Computational Model
• Sparse Bayesian Unsupervised Learning

Cited by in corpus (5)

• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
• Estimation, Confidence Intervals, and Large-Scale Hypotheses Testing for High-Dimensional Mixed Linear Regression
• High-Temperature Structure Detection in Ferromagnets
• Deep Neural Networks Guided Ensemble Learning for Point Estimation