Computational barriers in minimax submatrix detection

Abstract

This paper studies the minimax detection of a small submatrix of elevated mean in a large matrix contaminated by additive Gaussian noise. To investigate the tradeoff between statistical performance and computational cost from a complexity-theoretic perspective, we consider a sequence of discretized models which are asymptotically equivalent to the Gaussian model. Under the hypothesis that the planted clique detection problem cannot be solved in randomized polynomial time when the clique size is of smaller order than the square root of the graph size, the following phase transition phenomenon is established: when the size of the large matrix $p\to \infty$, if the submatrix size $k=\Theta (p^{\alpha })$ for any $\alpha \in (0,2/3)$, computational complexity constraints can incur a severe penalty on the statistical performance in the sense that any randomized polynomial-time test is minimax suboptimal by a polynomial factor in $p$; if $k=\Theta (p^{\alpha })$ for any $\alpha \in (2/3,1)$, minimax optimal detection can be attained within constant factors in linear time. Using Schatten norm loss as a representative example, we show that the hardness of attaining the minimax estimation rate can crucially depend on the loss function. Implications on the hardness of support recovery are also obtained.

Published at http://dx.doi.org/10.1214/14-AOS1300 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (4)

• Finding large average submatrices in high dimensional data
• Finding Hidden Cliques of Size \sqrt{N/e} in Nearly Linear Time
• Volume Ratio, Sparsity, and Minimaxity under Unitarily Invariant Norms
• Hidden cliques and the certification of the restricted isometry property

Cited by in corpus (49)

• Statistical physics of inference: Thresholds and algorithms
• Incoherence-Optimal Matrix Completion
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
• Lower bounds on the performance of polynomial-time algorithms for sparse linear regression
• Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
• Message-passing algorithms for synchronization problems over compact groups
• Statistical and computational trade-offs in estimation of sparse principal components
• Sparse CCA: Adaptive Estimation and Computational Barriers
• Computational Barriers to Estimation from Low-Degree Polynomials
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• Sparse PCA via Covariance Thresholding
• Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems
• Computational Lower Bounds for Community Detection on Random Graphs
• Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Semidefinite Programs for Exact Recovery of a Hidden Community
• Average-case Hardness of RIP Certification
• Submatrix localization via message passing
• Nearest Neighbors for Matrix Estimation Interpreted as Blind Regression for Latent Variable Model
• Parallel Tempering for the planted clique problem
• The Overlap Gap Property in Principal Submatrix Recovery
• Universality of Computational Lower Bounds for Submatrix Detection
• Phase Transitions for High Dimensional Clustering and Related Problems
• Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval
• Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit
• Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
• Sharp Computational-Statistical Phase Transitions via Oracle Computational Model
• Information Limits for Recovering a Hidden Community
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
• Optimal link prediction with matrix logistic regression
• Information Recovery from Pairwise Measurements
• High-Temperature Structure Detection in Ferromagnets
• Finding Planted Cliques in Sublinear Time
• Lattice partition recovery with dyadic CART
• Statistical Limits of Convex Relaxations
• Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation
• Tensor SVD: Statistical and Computational Limits
• A Multiscale Scan Statistic for Adaptive Submatrix Localization
• Distribution-Free, Size Adaptive Submatrix Detection with Acceleration
• Sparse Anomaly Detection Across Referentials: A Rank-Based Higher Criticism Approach
• Quantifying and Reducing Bias in Maximum Likelihood Estimation of Structured Anomalies
• Resource Allocation for Statistical Estimation
• Logspace Reducibility From Secret Leakage Planted Clique
• Low-Rank Principal Eigenmatrix Analysis
• Distribution-free Detection of a Submatrix
• Random Subgraph Detection Using Queries
• Detection of Planted Solutions for Flat Satisfiability Problems