The overlap gap property in principal submatrix recovery

DOI10.1007/s00440-021-01089-7OpenAlexW3204144240MaRDI QIDQ2067659

Subhabrata Sen, Aukosh Jagannath, David Gamarnik

Publication date: 18 January 2022

Published in: Probability Theory and Related Fields (Search for Journal in Brave)

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

zbMATH Keywords

spin glassesoverlap gap propertysubmatrix recovery

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (4)

Computational barriers to estimation from low-degree polynomials ⋮ Free Energy Wells and Overlap Gap Property in Sparse PCA ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Optimizing mean field spin glasses with external field

Uses Software

• LAS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some properties of the phase diagram for mixed \(p\)-spin glasses
• Low temperature asymptotics of spherical mean field spin glasses
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• Parisi formula for the ground state energy in the mixed \(p\)-spin model
• Algorithmic thresholds for tensor PCA
• Spin glass computations and Ruelle's probability cascades
• Finding one community in a sparse graph
• Finding large average submatrices in high dimensional data
• MAX \(\kappa\)-cut and the inhomogeneous Potts spin Glass
• Spectral gap estimates in mean field spin glasses
• Sparse CCA: adaptive estimation and computational barriers
• Fundamental limits of symmetric low-rank matrix estimation
• Free energy in the Potts spin Glass
• Free energy in the mixed \(p\)-spin models with vector spins
• The Parisi ultrametricity conjecture
• Finding a large submatrix of a Gaussian random matrix
• Local algorithms for independent sets are half-optimal
• On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model
• The algorithmic hardness threshold for continuous random energy models
• Computational barriers in minimax submatrix detection
• Energy landscape for large average submatrix detection problems in Gaussian random matrices
• Computational and statistical boundaries for submatrix localization in a large noisy matrix
• Suboptimality of local algorithms for a class of max-cut problems
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• The Parisi formula for mixed \(p\)-spin models
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
• Statistical thresholds for tensor PCA
• Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix
• A dynamic programming approach to the Parisi functional
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Sum-of-squares Lower Bounds for Planted Clique
• Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem
• Approximate Ultrametricity for Random Measures and Applications to Spin Glasses
• Equilibrium statistical mechanics of bipartite spin systems
• Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
• On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique
• Community Detection and Stochastic Block Models
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
• Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization
• The Sherrington-Kirkpatrick Model
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• Following the Ground States of <scp>Full‐RSB</scp> Spherical Spin Glasses
• The SK Model Is Infinite Step Replica Symmetry Breaking at Zero Temperature
• Optimization of the Sherrington--Kirkpatrick Hamiltonian
• Computational and statistical tradeoffs via convex relaxation
• Walksat Stalls Well Below Satisfiability
• On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank One Perturbations of Gaussian Tensors
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• On the solution‐space geometry of random constraint satisfaction problems
• Mean Field Models for Spin Glasses
• The free energy in a multi-species Sherrington-Kirkpatrick model

This page was built for publication: The overlap gap property in principal submatrix recovery