Free Energy Wells and Overlap Gap Property in Sparse PCA

DOI10.1002/CPA.22083MaRDI QIDQ6074556zbMATH OpenOpenAlexFDO

Authors Gerard Ben Arous, Alexander S. Wein, Ilias Zadik

Publication date 12 October 2023

Published in Communications on Pure and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.10689

Mathematics Subject Classification ID

Computer science (68-XX) Statistical mechanics, structure of matter (82-XX)

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.

Cites work

• A nearly tight sum-of-squares lower bound for the planted clique problem
• Algorithmic thresholds for tensor PCA
• Bounding flows for spherical spin glass dynamics
• Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization
• Large Cliques Elude the Metropolis Process
• Limits of local algorithms over sparse random graphs
• Local algorithms for independent sets are half-optimal
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• On consistency and sparsity for principal components analysis in high dimensions
• On the distribution of the largest eigenvalue in principal components analysis
• On the solution-space geometry of random constraint satisfaction problems
• Optimal detection of sparse principal components in high dimension
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
• Sparse PCA via covariance thresholding
• Sparse PCA: optimal rates and adaptive estimation
• Statistical and computational trade-offs in estimation of sparse principal components
• Suboptimality of local algorithms for a class of max-cut problems
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• The largest eigenvalue of rank one deformation of large Wigner matrices
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models
• The overlap gap property in principal submatrix recovery
• The planted matching problem: sharp threshold and infinite-order phase transition
• Walksat Stalls Well Below Satisfiability

Cited in

(4)

• Average-case complexity of tensor decomposition for low-degree polynomials
• The landscape of the planted clique problem: dense subgraphs and the overlap gap property
• On the MCMC performance in Bernoulli group testing and the random max-set cover problem
• An optimized Franz-Parisi criterion and its equivalence with SQ lower bounds

This page was built for publication: Free Energy Wells and Overlap Gap Property in Sparse PCA

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074556)