Universality of Computational Lower Bounds for Submatrix Detection

Abstract

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.

arXiv comment46 pages, accepted for presentation at Conference on Learning Theory (COLT) 2019

References in corpus (13)

• Optimal detection of sparse principal components in high dimension
• Incoherence-Optimal Matrix Completion
• Finding large average submatrices in high dimensional data
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Computational barriers in minimax submatrix detection
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• On combinatorial testing problems
• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
• Mutual Information in Rank-One Matrix Estimation
• Finding One Community in a Sparse Graph
• Asymptotic Mutual Information for the Two-Groups Stochastic Block Model
• Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness
• Everywhere-Sparse Spanners via Dense Subgraphs

Cited by in corpus (6)

• Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness
• The Overlap Gap Property in Principal Submatrix Recovery
• Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
• Quantifying and Reducing Bias in Maximum Likelihood Estimation of Structured Anomalies
• Random Subgraph Detection Using Queries
• Logspace Reducibility From Secret Leakage Planted Clique