The overlap gap property in principal submatrix recovery.
In: Probability Theory & Related Fields, Jg. 181 (2021-12-01), Heft 4, S. 757-814
Online
academicJournal
Zugriff:
We study support recovery for a k × k principal submatrix with elevated mean λ / N , hidden in an N × N symmetric mean zero Gaussian matrix. Here λ > 0 is a universal constant, and we assume k = N ρ for some constant ρ ∈ (0 , 1) . We establish that there exists a constant C > 0 such that the MLE recovers a constant proportion of the hidden submatrix if λ ≥ C 1 ρ log 1 ρ , while such recovery is information theoretically impossible if λ = o ( 1 ρ log 1 ρ ) . The MLE is computationally intractable in general, and in fact, for ρ > 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 ε > 0 and 1 ρ log 1 ρ ≪ λ ≪ 1 ρ 1 / 2 + ε , 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 λ > 1 / ρ , a simple spectral method recovers a constant proportion of the hidden submatrix. [ABSTRACT FROM AUTHOR]
Titel: |
The overlap gap property in principal submatrix recovery.
|
---|---|
Autor/in / Beteiligte Person: | Gamarnik, David ; Jagannath, Aukosh ; Sen, Subhabrata |
Link: | |
Zeitschrift: | Probability Theory & Related Fields, Jg. 181 (2021-12-01), Heft 4, S. 757-814 |
Veröffentlichung: | 2021 |
Medientyp: | academicJournal |
ISSN: | 0178-8051 (print) |
DOI: | 10.1007/s00440-021-01089-7 |
Schlagwort: |
|
Sonstiges: |
|