The Overlap Gap Property in Principal Submatrix Recovery

Abstract

We study support recovery for a $k\times k$ principal submatrix with elevated mean $\lambda /N$, hidden in an $N\times N$ symmetric mean zero Gaussian matrix. Here $\lambda >0$ is a universal constant, and we assume $k=N\rho$ for some constant $\rho \in (0,1)$. We establish that {there exists a constant $C>0$ such that} the MLE recovers a constant proportion of the hidden submatrix if $\lambda \ge C\sqrt{\frac{1}{\rho }\log \frac{1}{\rho }}$, {while such recovery is information theoretically impossible if $\lambda =o(\sqrt{\frac{1}{\rho }\log \frac{1}{\rho }})$}. The MLE is computationally intractable in general, and in fact, for $\rho >0$ sufficiently small, this problem is conjectured to exhibit a \emph{statistical-computational gap}. To provide rigorous evidence for this, we study the likelihood landscape for this problem, and establish that for some $\epsilon >0$ and $\sqrt{\frac{1}{\rho }\log \frac{1}{\rho }}\ll \lambda \ll \frac{1}{{\rho }^{1/2+\epsilon }}$, the problem exhibits a variant of the \emph{Overlap-Gap-Property (OGP)}. As a direct consequence, we establish that a family of local MCMC based algorithms do not achieve optimal recovery. Finally, we establish that for $\lambda >1/\rho$, a simple spectral method recovers a constant proportion of the hidden submatrix.

arXiv comment42 pages, 1 figure

References in corpus (39)

• Clustering of solutions in the random satisfiability problem
• An Extended Variational Principle for the SK Spin-Glass Model
• Computational and Statistical Tradeoffs via Convex Relaxation
• Finding large average submatrices in high dimensional data
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Computational barriers in minimax submatrix detection
• Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• The free energy in a multi-species Sherrington-Kirkpatrick model
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• Equilibrium statistical mechanics of bipartite spin systems
• Local algorithms for independent sets are half-optimal
• The Parisi formula for mixed $p$-spin models
• A statistical model for tensor PCA
• Mutual Information in Rank-One Matrix Estimation
• Algorithmic thresholds for tensor PCA
• Finding One Community in a Sparse Graph
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• A Dynamic Programming Approach to the Parisi Functional
• Suboptimality of local algorithms for a class of max-cut problems
• Computational Barriers to Estimation from Low-Degree Polynomials
• Phase Transitions in Sparse PCA
• Sum-of-Squares Lower Bounds for Sparse PCA
• Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems
• Spectral gap estimates in mean field spin glasses
• Low Temperature Asymptotics in Spherical Mean Field Spin Glasses
• Some Properties of the Phase Diagram for Mixed $p$-Spin Glasses
• Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure
• Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
• Spin Glass Computations and Ruelle's Probability Cascades
• Approximate Ultrametricity for Random Measures and Applications to Spin Glasses
• Walksat stalls well below the satisfiability threshold
• The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
• A connection between MAX $\kappa$-CUT and the inhomogeneous Potts spin glass in the large degree limit
• All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation
• Following the ground-states of full-RSB spherical spin glasses
• Some Exact Results on the Ultrametric Overlap Distribution in Mean Field Spin Glass Models (I)
• Sparse High-Dimensional Linear Regression. Algorithmic Barriers and a Local Search Algorithm
• Universality of Computational Lower Bounds for Submatrix Detection

Cited by in corpus (3)

• Computational Barriers to Estimation from Low-Degree Polynomials
• Optimizing Mean Field Spin Glasses with External Field
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials