Precise Error Rates for Computationally Efficient Testing

Abstract

We revisit the fundamental question of simple-versus-simple hypothesis testing with an eye towards computational complexity, as the statistically optimal likelihood ratio test is often computationally intractable in high-dimensional settings. In the classical spiked Wigner model with a general i.i.d. spike prior we show (conditional on a conjecture) that an existing test based on linear spectral statistics achieves the best possible tradeoff curve between type I and type II error rates among all computationally efficient tests, even though there are exponential-time tests that do better. This result is conditional on an appropriate complexity-theoretic conjecture, namely a natural strengthening of the well-established low-degree conjecture. Our result shows that the spectrum is a sufficient statistic for computationally bounded tests (but not for all tests). To our knowledge, our approach gives the first tool for reasoning about the precise asymptotic testing error achievable with efficient computation. The main ingredients required for our hardness result are a sharp bound on the norm of the low-degree likelihood ratio along with (counterintuitively) a positive result on achievability of testing. This strategy appears to be new even in the setting of unbounded computation, in which case it gives an alternate way to analyze the fundamental statistical limits of testing.

v2 is the journal version; v3 contains an update on the status of the main conjecture

References in corpus (27)

• Message Passing Algorithms for Compressed Sensing
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Finite sample approximation results for principal component analysis: a matrix perturbation approach
• The largest eigenvalue of rank one deformation of large Wigner matrices
• The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluctuations
• Asymptotic power of sphericity tests for high-dimensional data
• Central limit theorems for eigenvalues in a spiked population model
• Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
• Fluctuations of the free energy of the spherical Sherrington-Kirkpatrick model
• Computational Barriers to Estimation from Low-Degree Polynomials
• Phase Transitions in Sparse PCA
• Fluctuations of the free energy of the spherical Sherrington-Kirkpatrick model with ferromagnetic interaction
• Fundamental limits of detection in the spiked Wigner model
• Disordered Systems Insights on Computational Hardness
• Optimal hypothesis testing for stochastic block models with growing degrees
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
• The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics
• Counterexamples to the Low-Degree Conjecture
• Equivalence of Approximate Message Passing and Low-Degree Polynomials in Rank-One Matrix Estimation
• Weak Detection in the Spiked Wigner Model with General Rank
• Non-Gaussian Component Analysis via Lattice Basis Reduction
• Weak detection in the spiked Wigner model
• Detection of Signal in the Spiked Rectangular Models
• Global and local CLTs for linear spectral statistics of general sample covariance matrices when the dimension is much larger than the sample size with applications
• Hypothesis testing with low-degree polynomials in the Morris class of exponential families