Sum-of-Squares Lower Bounds for Sparse PCA
This paper establishes a statistical versus computational trade-off for solving a basic high-dimensional machine learning problem via a basic convex relaxation method. Specifically, we consider the Sparse Principal Component Analysis (Sparse PCA) problem, and the family of Sum-of-Squares (SoS, aka Lasserre/Parillo) convex relaxations. It was well known that in large dimension p, a planted k-sparse unit vector can be in principle detected using only n ≈ k log p (Gaussian or Bernoulli) samples, but all efficient (polynomial time) algorithms known require n ≈ k 2 samples. It was also known that this quadratic gap cannot be improved by the the most basic semi-definite (SDP, aka spectral) relaxation, equivalent to a degree-2 SoS algorithms. Here we prove that also degree-4 SoS algorithms cannot improve this quadratic gap. This average-case lower bound adds to the small collection of hardness results in machine learning for this powerful family of convex relaxation algorithms. Moreover, our design of moments (or "pseudo-expectations") for this lower bound is quite different than previous lower bounds. Establishing lower bounds for higher degree SoS algorithms for remains a challenging problem.
Paper 997 - Sum-of-Squares Lower Bounds for Sparse PCA ======================================================The authors explore the statistical-computational trade-off in the Sparse PCAproblem within the Sum-Of-Squares convex relaxation hierarchy.Their worknicely complements many recent papers in the literature on this subject and ismost directly related to the paper by Krauthgamer, Nadler, and Vilenchik (2015). The results of KNV (2015) can be interpreted as a negative result for the SoSdegree-2 relaxation.This paper provides analogous results for the degree-4 SoS relaxation: showing that the optimal value of the the program is large with high probability, and hence prone to false rejection, and that its output isweakly correlated with the true.This paper is closer to the COLT community,but the results are very good and the paper is well-written.It should beaccepted into NIPS.I only have a few typographical corrections:page 3, line 140: "even to" -> "even" page 3, line 145: "An very" -> "A very" page 5, line 234: "once can" -> "one can" page 6, line 299: "above as ." -> "above." page 6, line 310: "Rigollet's" -> "Berthet and Rigollet's"