Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval
This work addresses fundamental computational barriers in machine learning for analyzing heterogeneous data, which is incremental as it builds on prior conjectures to provide rigorous lower bounds.
The paper tackles the tradeoffs between statistical accuracy and computational tractability in high-dimensional heterogeneous data analysis, such as sparse Gaussian mixture models and phase retrieval, by establishing computationally feasible minimax lower bounds that reveal significant gaps compared to classical bounds, quantifying the statistical price for computational tractability.
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.