Computational barriers in minimax submatrix detection

DOI10.1214/14-AOS1300zbMATH Open1328.62354arXiv1309.5914MaRDI QIDQ2352736FDOQ2352736

Yihong Wu, Zongming Ma

Publication date: 6 July 2015

Published in: The Annals of Statistics (Search for Journal in Brave)

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 $poinfty$, if the submatrix size $k=Theta(p^{alpha})$ for any $alphain(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 $alphain(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.

Full work available at URL: https://arxiv.org/abs/1309.5914

Recommendations

• Statistical and computational limits for sparse matrix detection
• Computational and statistical boundaries for submatrix localization in a large noisy matrix
• Optimal detection of sparse principal components in high dimension
• Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices
• Statistical algorithms and a lower bound for detecting planted cliques

zbMATH Keywords

computational complexityhigh-dimensional statisticsasymptotic equivalenceminimax rateplanted cliquesubmatrix detection

Mathematics Subject Classification ID

Hypothesis testing in multivariate analysis (62H15) Minimax procedures in statistical decision theory (62C20)

Cites Work

• Elements of Information Theory
• Title not available (Why is that?)
• Asymptotic methods in statistical decision theory
• Exact matrix completion via convex optimization
• Title not available (Why is that?)
• Hiding cliques for cryptographic security
• Title not available (Why is that?)
• Optimal detection of sparse principal components in high dimension
• Finding Hidden Cliques in Linear Time with High Probability
• Nuclear norm minimization for the planted clique and biclique problems
• Community detection in sparse random networks
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Computational Complexity
• On combinatorial testing problems
• The Existence of Probability Measures with Given Marginals
• Title not available (Why is that?)
• On the dimension and entropy of probability distributions
• Large Cliques Elude the Metropolis Process
• Title not available (Why is that?)
• Public-key cryptography from different assumptions
• Computational and statistical tradeoffs via convex relaxation
• Expected complexity of graph partitioning problems
• On the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrix
• Hidden Cliques and the Certification of the Restricted Isometry Property
• How Hard Is It to Approximate the Best Nash Equilibrium?
• Title not available (Why is that?)
• Finding and certifying a large hidden clique in a semirandom graph
• Statistical algorithms and a lower bound for detecting planted cliques
• Statistical Experiments and Decisions
• Finding large average submatrices in high dimensional data
• Computational barriers in minimax submatrix detection
• Do semidefinite relaxations solve sparse PCA up to the information limit?
• Title not available (Why is that?)
• Energy landscape for large average submatrix detection problems in Gaussian random matrices

Cited In (30)

• Notes on computational-to-statistical gaps: predictions using statistical physics
• A Unifying Tutorial on Approximate Message Passing
• The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising
• Computational barriers in minimax submatrix detection
• Distribution-Free, Size Adaptive Submatrix Detection with Acceleration
• Tensor clustering with planted structures: statistical optimality and computational limits
• Statistical and computational limits for sparse matrix detection
• A sieve stochastic gradient descent estimator for online nonparametric regression in Sobolev ellipsoids
• Cryptography from planted graphs: security with logarithmic-size messages
• Optimal testing for planted satisfiability problems
• Optimal adaptivity of signed-polygon statistics for network testing
• Parallel tempering for the planted clique problem
• Isotonic regression with unknown permutations: statistics, computation and adaptation
• A goodness-of-fit test on the number of biclusters in a relational data matrix
• Computational barriers to estimation from low-degree polynomials
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• Phase transitions for detecting latent geometry in random graphs
• Estimation of Wasserstein distances in the spiked transport model
• ECA: High-Dimensional Elliptical Component Analysis in Non-Gaussian Distributions
• Submatrix localization via message passing
• The overlap gap property in principal submatrix recovery
• Distribution-free detection of a submatrix
• Comment on ``Hypothesis testing by convex optimization
• Computational lower bounds for graphon estimation via low-degree polynomials
• Computational and statistical thresholds in multi-layer stochastic block models
• Hardness self-amplification: simplified, optimized, and unified
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
• Optimal rates of statistical seriation
• Estimation of Monge matrices
• Optimality and sub-optimality of PCA. I: Spiked random matrix models

Uses Software

• LAS

This page was built for publication: Computational barriers in minimax submatrix detection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2352736)