Computational barriers to estimation from low-degree polynomials

DOI10.1214/22-AOS2179MaRDI QIDQ2149001zbMATH OpenFDO

Authors Tselil Schramm, Alexander S. Wein

Publication date 24 June 2022

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

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

zbMATH Keywords

computational complexitylow-degree polynomialsplanted dense subgraphplanted submatrix

Mathematics Subject Classification ID

Bayesian inference (62F15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Computational barriers in minimax submatrix detection
• 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

• A nearly tight sum-of-squares lower bound for the planted clique problem
• Algorithmic thresholds for tensor PCA
• An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model
• Asymptotic mutual information for the balanced binary stochastic block model
• Community detection in dense random networks
• Community detection in sparse random networks
• Computational and statistical boundaries for submatrix localization in a large noisy matrix
• Computational barriers in minimax submatrix detection
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Detection of an anomalous cluster in a network
• Efficient noise-tolerant learning from statistical queries
• Eigenvalues of large sample covariance matrices of spiked population models
• Estimation of low-rank matrices via approximate message passing
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• Finding large average submatrices in high dimensional data
• HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
• Higher criticism for detecting sparse heterogeneous mixtures.
• How to iron out rough landscapes and get optimal performances: averaged gradient descent and its application to tensor PCA
• scientific article; zbMATH DE number 6371535 (Why is no real title available?)
• scientific article; zbMATH DE number 7650426 (Why is no real title available?)
• Incoherence-Optimal Matrix Completion
• Lifting sum-of-squares lower bounds: degree-2 to degree-4
• Limits of local algorithms over sparse random graphs
• Local algorithms for independent sets are half-optimal
• On basing one-way functions on NP-hardness
• On consistency and sparsity for principal components analysis in high dimensions
• On the degree of Boolean functions as real polynomials
• On Worst‐Case to Average‐Case Reductions for NP Problems
• Optimal low-degree hardness of maximum independent set
• Optimality and sub-optimality of PCA. I: Spiked random matrix models
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
• Random-Self-Reducibility of Complete Sets
• Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix
• Sherali-Adams integrality gaps matching the log-density threshold
• Sparse CCA: adaptive estimation and computational barriers
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• Statistical algorithms and a lower bound for detecting planted cliques
• Statistical and computational limits for sparse matrix detection
• Statistical and computational trade-offs in estimation of sparse principal components
• Statistical query lower bounds for tensor PCA
• Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices
• Submatrix localization via message passing
• Suboptimality of local algorithms for a class of max-cut problems
• Sum of squares lower bounds for refuting any CSP
• Tensor SVD: Statistical and Computational Limits
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• 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
• The Lovász theta function for random regular graphs and community detection in the hard regime
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models
• The overlap gap property in principal submatrix recovery
• Walksat Stalls Well Below Satisfiability

Cited in

(30)

• Statistical-computational trade-offs in tensor PCA and related problems via communication complexity
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics
• Computational Barriers to Estimation from Low-Degree Polynomials
• Sum-of-squares lower bounds for densest k-subgraph
• Average-case complexity of tensor decomposition for low-degree polynomials
• Algorithms approaching the threshold for semi-random planted clique
• Matrix denoising: Bayes-optimal estimators via low-degree polynomials
• Pair-matching: link prediction with adaptive queries
• Computational lower bounds for graphon estimation via low-degree polynomials
• Computational and statistical thresholds in multi-layer stochastic block models
• Optimality of approximate message passing for spiked matrix models with rotationally invariant noise
• A computational transition for detecting correlated stochastic block models by low-degree polynomials
• Sparse linear regression when noises and covariates are heavy-tailed and contaminated by outliers
• Low-degree hardness of detection for correlated Erdős-Rényi graphs
• Counting stars is constant-degree optimal for detecting any planted subgraph
• Minimax optimal probability matrix estimation for graphon with spectral decay
• A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation
• Precise error rates for computationally efficient testing
• Low coordinate degree algorithms. I: Universality of computational thresholds for hypothesis testing
• Large-dimensional independent component analysis: statistical optimality and computational tractability
• Equivalence of approximate message passing and low-degree polynomials in rank-one matrix estimation
• Optimal spectral recovery of a planted vector in a subspace
• Detection of dense subhypergraphs by low-degree polynomials
• Random algebraic graphs and their convergence to Erdős-Rényi
• Computational lower bounds for multi-frequency group synchronization
• Approximate independence of permutation mixtures
• Is it easier to count communities than find them?
• Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs
• Seriation of Tœplitz and latent position matrices: optimal rates and computational trade-offs
• An optimized Franz-Parisi criterion and its equivalence with SQ lower bounds

Describes a project that uses

Uses Software

• LAS

This page was built for publication: Computational barriers to estimation from low-degree polynomials

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