We study support recovery for a $k \times k$ principal submatrix with
elevated mean $\lambda/N$, hidden in an $N\times N$ symmetric mean zero
Gaussian matrix. Here $\lambda>0$ is a universal constant, and we assume $k = N
\rho$ for some constant $\rho \in (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 {\geq C} \sqrt{\frac{1}{\rho} \log \frac{1}{\rho}}$,
{while such recovery is information theoretically impossible if $\lambda = o(
\sqrt{\frac{1}{\rho} \log \frac{1}{\rho}} )$}. The MLE is computationally
intractable in general, and in fact, for $\rho>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 $\sqrt{\frac{1}{\rho}
\log \frac{1}{\rho} } \ll \lambda \ll \frac{1}{\rho^{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/\rho$, a simple spectral method recovers a constant proportion of the hidden
submatrix.

研究 $k	imes k$ 主子矩阵的支持恢复以及 MLE 和谱方法在支持恢复中的应用，并证明在统计计算间隙存在的情况下，局部 MCMC 算法无法达到最佳恢复效果。

主子矩阵恢复中的重叠间隔性质

The Overlap Gap Property in Principal Submatrix Recovery

In the general submatrix detection problem, the task is to detect the
presence of a small $k \times k$ submatrix with entries sampled from a
distribution $\mathcal{P}$ in an $n \times n$ matrix of samples from
$\mathcal{Q}$. This formulation includes a number of well-studied problems,
such as biclustering when $\mathcal{P}$ and $\mathcal{Q}$ are Gaussians and the
planted dense subgraph formulation of community detection when the submatrix is
a principal minor and $\mathcal{P}$ and $\mathcal{Q}$ are Bernoulli random
variables. These problems all seem to exhibit a universal phenomenon: there is
a statistical-computational gap depending on $\mathcal{P}$ and $\mathcal{Q}$
between the minimum $k$ at which this task can be solved and the minimum $k$ at
which it can be solved in polynomial time. Our main result is to tightly
characterize this computational barrier as a tradeoff between $k$ and the KL
divergences between $\mathcal{P}$ and $\mathcal{Q}$ through average-case
reductions from the planted clique conjecture. These computational lower bounds
hold given mild assumptions on $\mathcal{P}$ and $\mathcal{Q}$ arising
naturally from classical binary hypothesis testing. Our results recover and
generalize the planted clique lower bounds for Gaussian biclustering in Ma-Wu
(2015) and Brennan et al. (2018) and for the sparse and general regimes of
planted dense subgraph in Hajek et al. (2015) and Brennan et al. (2018). This
yields the first universality principle for computational lower bounds obtained
through average-case reductions.

研究总结了在不同分布情况下计算复杂性与 KL 散度之间的统计分层次关系，揭示了计算下界中的普适性原理。