To refer to this page use:
|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.|
|Citation:||Wang, Zhaoran, Quanquan Gu, and Han Liu. "On the Statistical Limits of Convex Relaxations." In International Conference on Machine Learning, PMLR 48 (2016):pp. 1368-1377.|
|Pages:||1368 - 1377|
|Type of Material:||Conference Article|
|Journal/Proceeding Title:||Proceedings of The 33rd International Conference on Machine Learning, PMLR|
|Version:||Final published version. Article is made available in OAR by the publisher's permission or policy.|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.