Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio

2019/07/26 by Kunisky, Dmitriy, Wein, Alexander S., Bandeira, Afonso S. · 13 citations
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.1907.11636

Abstract

These notes survey and explore an emerging method, which we call the low-degree method, for predicting and understanding statistical-versus-computational tradeoffs in high-dimensional inference problems. In short, the method posits that a certain quantity -- the second moment of the low-degree likelihood ratio -- gives insight into how much computational time is required to solve a given hypothesis testing problem, which can in turn be used to predict the computational hardness of a variety of statistical inference tasks. While this method originated in the study of the sum-of-squares (SoS) hierarchy of convex programs, we present a self-contained introduction that does not require knowledge of SoS. In addition to showing how to carry out predictions using the method, we include a discussion investigating both rigorous and conjectural consequences of these predictions. These notes include some new results, simplified proofs, and refined conjectures. For instance, we point out a formal connection between spectral methods and the low-degree likelihood ratio, and we give a sharp low-degree lower bound against subexponential-time algorithms for tensor PCA.

Cited by

• Statistical and computational challenges in ranking
• Improved Pseudorandom Codes from Permuted Puzzles
• Phase Transition for Stochastic Block Model with more than √(n) Communities (II)
• Spectrally indistinguishable pseudorandom graphs
• PTF Testing Lower Bounds for Non-Gaussian Component Analysis
• Near-Optimal Tensor PCA via Normalized Stochastic Gradient Ascent with Overparameterization
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination
• Computational and statistical lower bounds for low-rank estimation under general inhomogeneous noise
• Agnostic Product Mixed State Tomography via Robust Statistics
• Optimality and computational barriers in variable selection under dependence
• Random Matrices, Intrinsic Freeness, and Sharp Non-Asymptotic Inequalities
• Phase Transition for Stochastic Block Model with more than √(n) Communities
• A Smooth Computational Transition in Tensor PCA

Related

• Counterexamples to the Low-Degree Conjecture
• The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics
• Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
• Computational Complexity of Statistics: New Insights from Low-Degree Polynomials