Statistical Limits of Convex Relaxations
arXiv:1503.01442
Abstract
Many high dimensional sparse learning problems are formulated as nonconvex optimization. A popular approach to solve these nonconvex optimization problems is through convex relaxations such as linear and semidefinite programming. In this paper, we study the statistical limits of convex relaxations. Particularly, we consider two problems: Mean estimation for sparse principal submatrix and edge probability estimation for stochastic block model. We exploit the sum-of-squares relaxation hierarchy to sharply characterize the limits of a broad class of convex relaxations. Our result shows statistical optimality needs to be compromised for achieving computational tractability using convex relaxations. Compared with existing results on computational lower bounds for statistical problems, which consider general polynomial-time algorithms and rely on computational hardness hypotheses on problems like planted clique detection, our theory focuses on a broad class of convex relaxations and does not rely on unproven hypotheses.
arXiv comment22 pages
References in corpus (16)
- Community detection in graphs
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Optimal detection of sparse principal components in high dimension
- Computational and Statistical Tradeoffs via Convex Relaxation
- Finding large average submatrices in high dimensional data
- Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
- Stochastic Block Models and Reconstruction
- Computational barriers in minimax submatrix detection
- Detection of a sparse submatrix of a high-dimensional noisy matrix
- Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph
- Sum-of-squares proofs and the quest toward optimal algorithms
- 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
- Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems
- Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique