The overlap gap property in principal submatrix recovery

• 成果类型: Article
• 署名作者: Gamarnik, David; Jagannath, Aukosh; Sen, Subhabrata
• 署名单位: Massachusetts Institute of Technology (MIT); University of Waterloo; University of Waterloo; Harvard University
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-021-01089-7
• 发表日期: 2021
• 页码: 757-814
• 关键词: local algorithms; free-energy; sparse submatrix; parisi formula; spin; ultrametricity; localization; thresholds; tradeoffs; models

摘要

We study support recovery for a k x k principal submatrix with elevated mean lambda/N, hidden in an N x N symmetric mean zero Gaussian matrix. Here lambda > 0 is a universal constant, and we assume k = N rho for some constant rho is an element of (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 >= C root 1/rho log 1/rho, while such recovery is information theoretically impossible if lambda = o(root 1/rho log 1/rho). The MLE is computationally intractable in general, and in fact, for rho > 0 sufficiently small, this problem is conjectured to exhibit a 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 root 1/rho log 1/rho << lambda << 1/rho(1/2+epsilon), the problem exhibits a variant of the 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.