The Overlap Gap Property in Planted Submatrix Recovery

• Activity Number: 174 - Statistical Optimality in High-Dimensional Models and Tradeoffs with Computational Complexity, Privacy and Communication Constraints
• Type: Contributed
• Date/Time: Tuesday, August 4, 2020 : 10:00 AM to 2:00 PM
• Sponsor: IMS
• Author(s): Subhabrata Sen* and David Gamarnik and Aukosh Jagannath
• Companies: Harvard University and Massachusetts Institute of Technology and University of Waterloo
• Keywords: submatrix recovery; overlap gap; statistical-computational gap

Abstract

We study support recovery for a principal submatrix with elevated mean, hidden in a symmetric Gaussian matrix. We characterize the minimum signal strength necessary for the success of the Maximum Likelihood Estimate(MLE). The MLE is computationally intractable in general, and in fact, this problem is conjectured to exhibit a statistical-computational gap. To provide some evidence in favor of this conjecture, we analyze the restricted likelihood function of this problem, and establish that it exhibits the ``Overlap Gap Property" (OGP). As a consequence, we establish that a family of Markov Chain based algorithms are statistically sub-optimal. Finally, we establish that for large signal strength, a simple spectral method recovers the underlying matrix.