Computational barriers in minimax submatrix detection

DOI10.1214/14-AOS1300MaRDI QIDQ2352736zbMATH OpenFDO

Authors Zongming Ma, Yihong Wu

Publication date 6 July 2015

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

Full work available at URL https://arxiv.org/abs/1309.5914, https://projecteuclid.org/euclid.aos/1431695639

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)

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.

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

Cites work

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

Cited in

(32)

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

Describes a project that uses

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)