Skip to main content

On the statistical limits of convex relaxations: A case study

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

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1bg5j
Full metadata record
DC FieldValueLanguage
dc.contributor.authorWang, Z-
dc.contributor.authorGu, Q-
dc.contributor.authorLiu, H-
dc.date.accessioned2021-10-11T14:16:52Z-
dc.date.available2021-10-11T14:16:52Z-
dc.date.issued2016en_US
dc.identifier.citationWang, 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.en_US
dc.identifier.issn2640-3498-
dc.identifier.urihttp://proceedings.mlr.press/v48/wangc16.html-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1bg5j-
dc.description.abstractMany 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.en_US
dc.format.extent1368 - 1377en_US
dc.language.isoen_USen_US
dc.relation.ispartofProceedings of The 33rd International Conference on Machine Learning, PMLRen_US
dc.rightsFinal published version. Article is made available in OAR by the publisher's permission or policy.en_US
dc.titleOn the statistical limits of convex relaxations: A case studyen_US
dc.typeConference Articleen_US
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
LimitsConvexRelationsCaseStudy.pdf467.26 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.