On the Statistical Limits of Convex Relaxations
Authors: Zhaoran Wang, Quanquan Gu, Han Liu
ICML 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 polynomialtime 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. |
| Researcher Affiliation | Academia | Zhaoran Wang ZHAORAN@PRINCETON.EDU Princeton University, NJ 08544 USA Quanquan Gu QG5W@VIRGINIA.EDU University of Virginia, VA 22904 USA Han Liu HANLIU@PRINCETON.EDU Princeton University, NJ 08544 USA |
| Pseudocode | No | The paper presents mathematical formulations and describes computational procedures but does not include any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of open-source code. |
| Open Datasets | No | The paper discusses theoretical 'statistical models' and 'distribution families' (e.g., 'P(s,d)') but it does not refer to actual public datasets used in experiments, nor does it provide any links or citations for data access. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments, thus no dataset split information (including validation splits) is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe any experiments that would require software dependency information. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details or hyperparameters. |