Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems

Abstract

Given a large data matrix $A\in {\mathbb{R}}^{n\times n}$, we consider the problem of determining whether its entries are i.i.d. with some known marginal distribution $A_{ij}\sim P_0$, or instead $A$ contains a principal submatrix $A_{\mathsf{Q},\mathsf{Q}}$ whose entries have marginal distribution $A_{ij}\sim P_1\ne P_0$. As a special case, the hidden (or planted) clique problem requires to find a planted clique in an otherwise uniformly random graph. Assuming unbounded computational resources, this hypothesis testing problem is statistically solvable provided $|\mathsf{Q}|\ge C\log n$ for a suitable constant $C$. However, despite substantial effort, no polynomial time algorithm is known that succeeds with high probability when $|\mathsf{Q}|=o(\sqrt{n})$. Recently Meka and Wigderson \cite{meka2013association}, proposed a method to establish lower bounds within the Sum of Squares (SOS) semidefinite hierarchy. Here we consider the degree-$4$ SOS relaxation, and study the construction of \cite{meka2013association} to prove that SOS fails unless $k\ge C{n}^{1/3}/\log n$. An argument presented by Barak implies that this lower bound cannot be substantially improved unless the witness construction is changed in the proof. Our proof uses the moments method to bound the spectrum of a certain random association scheme, i.e. a symmetric random matrix whose rows and columns are indexed by the edges of an Erdös-Renyi random graph.

arXiv comment40 pages, 1 table, conference

References in corpus (7)

• 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
• Sum-of-squares proofs and the quest toward optimal algorithms
• Computational Lower Bounds for Community Detection on Random Graphs
• Simultaneously Structured Models with Application to Sparse and Low-rank Matrices
• Statistical Algorithms and a Lower Bound for Detecting Planted Clique

Cited by in corpus (11)

• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Semidefinite Programs for Exact Recovery of a Hidden Community
• Sum-of-squares lower bounds for planted clique
• The Overlap Gap Property in Principal Submatrix Recovery
• Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
• Sharp Computational-Statistical Phase Transitions via Oracle Computational Model
• Computational and Statistical Tradeoffs in Learning to Rank
• Recovering a Hidden Community Beyond the Kesten-Stigum Threshold in $O(|E|{\log }^{\ast }|V|)$ Time
• Statistical Limits of Convex Relaxations
• Hidden Hamiltonian Cycle Recovery via Linear Programming
• How Well Do Local Algorithms Solve Semidefinite Programs?