TY - JOUR
T1 - Free Energy Wells and Overlap Gap Property in Sparse PCA
AU - Arous, Gérard Ben
AU - Wein, Alexander S.
AU - Zadik, Ilias
N1 - Funding Information:
A.S.W. is partially supported by NSF grant DMS-1712730 and by the Simons Collaboration on Algorithms and Geometry. I.Z. is supported by a CDS Moore-Sloan postdoctoral fellowship. The authors would like to thank David Gamarnik for helpful comments on an earlier draft of this work. We also thank the anonymous reviewers for their helpful comments.
Publisher Copyright:
© 2020 G.B. Arous, A. S. Wein & I. Zadik.
PY - 2020
Y1 - 2020
N2 - We study a variant of the sparse PCA (principal component analysis) problem in the “hard” regime, where the inference task is possible yet no polynomial-time algorithm is known to exist. Prior work, based on the low-degree likelihood ratio, has conjectured a precise expression for the best possible (sub-exponential) runtime throughout the hard regime. Following instead a statistical physics inspired point of view, we show bounds on the depth of free energy wells for various Gibbs measures naturally associated to the problem. These free energy wells imply hitting time lower bounds that corroborate the low-degree conjecture: we show that a class of natural MCMC (Markov chain Monte Carlo) methods (with worst-case initialization) cannot solve sparse PCA with less than the conjectured runtime. These lower bounds apply to a wide range of values for two tuning parameters: temperature and sparsity misparametrization. Finally, we prove that the Overlap Gap Property (OGP), a structural property that implies failure of certain local search algorithms, holds in a significant part of the hard regime.
AB - We study a variant of the sparse PCA (principal component analysis) problem in the “hard” regime, where the inference task is possible yet no polynomial-time algorithm is known to exist. Prior work, based on the low-degree likelihood ratio, has conjectured a precise expression for the best possible (sub-exponential) runtime throughout the hard regime. Following instead a statistical physics inspired point of view, we show bounds on the depth of free energy wells for various Gibbs measures naturally associated to the problem. These free energy wells imply hitting time lower bounds that corroborate the low-degree conjecture: we show that a class of natural MCMC (Markov chain Monte Carlo) methods (with worst-case initialization) cannot solve sparse PCA with less than the conjectured runtime. These lower bounds apply to a wide range of values for two tuning parameters: temperature and sparsity misparametrization. Finally, we prove that the Overlap Gap Property (OGP), a structural property that implies failure of certain local search algorithms, holds in a significant part of the hard regime.
UR - http://www.scopus.com/inward/record.url?scp=85097971682&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85097971682&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:85097971682
SN - 2640-3498
VL - 125
SP - 479
EP - 482
JO - Proceedings of Machine Learning Research
JF - Proceedings of Machine Learning Research
T2 - 33rd Conference on Learning Theory, COLT 2020
Y2 - 9 July 2020 through 12 July 2020
ER -