Sharp Computational-Statistical Phase Transitions via Oracle Computational Model

Abstract

We study the fundamental tradeoffs between computational tractability and statistical accuracy for a general family of hypothesis testing problems with combinatorial structures. Based upon an oracle model of computation, which captures the interactions between algorithms and data, we establish a general lower bound that explicitly connects the minimum testing risk under computational budget constraints with the intrinsic probabilistic and combinatorial structures of statistical problems. This lower bound mirrors the classical statistical lower bound by Le Cam (1986) and allows us to quantify the optimal statistical performance achievable given limited computational budgets in a systematic fashion. Under this unified framework, we sharply characterize the statistical-computational phase transition for two testing problems, namely, normal mean detection and sparse principal component detection. For normal mean detection, we consider two combinatorial structures, namely, sparse set and perfect matching. For these problems we identify significant gaps between the optimal statistical accuracy that is achievable under computational tractability constraints and the classical statistical lower bounds. Compared with existing works on computational lower bounds for statistical problems, which consider general polynomial-time algorithms on Turing machines, and rely on computational hardness hypotheses on problems like planted clique detection, we focus on the oracle computational model, which covers a broad range of popular algorithms, and do not rely on unproven hypotheses. Moreover, our result provides an intuitive and concrete interpretation for the intrinsic computational intractability of high-dimensional statistical problems. One byproduct of our result is a lower bound for a strict generalization of the matrix permanent problem, which is of independent interest.

57 pages, 4 figures

References in corpus (17)

• Optimal detection of sparse principal components in high dimension
• Truncated Power Method for Sparse Eigenvalue Problems
• Incoherence-Optimal Matrix Completion
• Computational and Statistical Tradeoffs via Convex Relaxation
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Higher Criticism for Large-Scale Inference, Especially for Rare and Weak Effects
• Computational barriers in minimax submatrix detection
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Searching for a trail of evidence in a maze
• On combinatorial testing problems
• Lower bounds on the performance of polynomial-time algorithms for sparse linear regression
• Computational Lower Bounds for Sparse PCA
• Sparse CCA: Adaptive Estimation and Computational Barriers
• Sparse PCA via Covariance Thresholding
• Sum-of-Squares Lower Bounds for Sparse PCA
• Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems
• High Dimensional Expectation-Maximization Algorithm: Statistical Optimization and Asymptotic Normality

Cited by in corpus (4)

• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
• Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval
• Statistical Query Lower Bounds for Tensor PCA
• High-Temperature Structure Detection in Ferromagnets