The Overlap Gap Property in Principal Submatrix Recovery

DOI10.1007/S00440-021-01089-7MaRDI QIDQ6324231arXivFDO

Authors David Gamarnik, Aukosh Jagannath, Subhabrata Sen

Publication date 26 August 2019

Published in arXiv

Full work available at URL https://doi.org/10.1007/S00440-021-01089-7

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Factor analysis and principal components; correspondence analysis (62H25) Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)

arXiv classification

cs.CCmath.PRmath.STstat.TH

Abstract: We study support recovery for a $kimesk$ principal submatrix with elevated mean $lambda/N$, hidden in an $NimesN$ symmetric mean zero Gaussian matrix. Here $lambda>0$ is a universal constant, and we assume $k=Nho$ for some constant $hoin(0,1)$. We establish that {there exists a constant $C>0$ such that} the MLE recovers a constant proportion of the hidden submatrix if $lambdageqCsqrtfrac1hologfrac1ho$, {while such recovery is information theoretically impossible if $lambda=o(sqrtfrac1hologfrac1ho)$}. The MLE is computationally intractable in general, and in fact, for $ho>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 $varepsilon>0$ and $sqrtfrac1hologfrac1holllambdallfrac1h{o}^{1/2+varepsilon}$, 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/ho$, a simple spectral method recovers a constant proportion of the hidden submatrix.

This page was built for publication: The Overlap Gap Property in Principal Submatrix Recovery

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