Skip to main content

On the statistical limits of convex relaxations: A case study

Author(s): Wang, Z; Gu, Q; Liu, H

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.
Publication Date: 2016
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.
ISSN: 2640-3498
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.