Free Energy Wells and Overlap Gap Property in Sparse PCA

Gérard Ben Arous, Alexander S. Wein, Ilias Zadik
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:479-482, 2020.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-ben-arous20a, title = {Free Energy Wells and Overlap Gap Property in Sparse PCA}, author = {Ben Arous, G\'erard and Wein, Alexander S. and Zadik, Ilias}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {479--482}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/ben-arous20a/ben-arous20a.pdf}, url = {https://proceedings.mlr.press/v125/ben-arous20a.html}, abstract = { 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.} }
Endnote
%0 Conference Paper %T Free Energy Wells and Overlap Gap Property in Sparse PCA %A Gérard Ben Arous %A Alexander S. Wein %A Ilias Zadik %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-ben-arous20a %I PMLR %P 479--482 %U https://proceedings.mlr.press/v125/ben-arous20a.html %V 125 %X 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.
APA
Ben Arous, G., Wein, A.S. & Zadik, I.. (2020). Free Energy Wells and Overlap Gap Property in Sparse PCA. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:479-482 Available from https://proceedings.mlr.press/v125/ben-arous20a.html.

Related Material