Online Program Home
  My Program

All Times EDT

Abstract Details

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
Abstract #313038
Title: The Overlap Gap Property in Planted Submatrix Recovery
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.


Authors who are presenting talks have a * after their name.

Back to the full JSM 2020 program