Notes on computational-to-statistical gaps: predictions using statistical physics
From MaRDI portal
Abstract: In these notes we describe heuristics to predict computational-to-statistical gaps in certain statistical problems. These are regimes in which the underlying statistical problem is information-theoretically possible although no efficient algorithm exists, rendering the problem essentially unsolvable for large instances. The methods we describe here are based on mature, albeit non-rigorous, tools from statistical physics. These notes are based on a lecture series given by the authors at the Courant Institute of Mathematical Sciences in New York City, on May 16th, 2017.
Recommendations
- Random instances of problems in NP -- algorithms and statistical physics
- The committee machine: computational to statistical gaps in learning a two-layers neural network
- Phase Transitions in Combinatorial Optimization Problems
- Statistical physics and network optimization problems
- Statistical mechanics methods and phase transitions in optimization problems
Cites work
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 1303602 (Why is no real title available?)
- scientific article; zbMATH DE number 1489808 (Why is no real title available?)
- A Limit Theorem for Multidimensional Galton-Watson Processes
- A nearly tight sum-of-squares lower bound for the planted clique problem
- A proof of the block model threshold conjecture
- An approach to obtaining global extremums in polynomial mathematical programming problems
- An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model
- Angular synchronization by eigenvectors and semidefinite programming
- Asymptotic mutual information for the balanced binary stochastic block model
- Belief propagation, robust reconstruction and optimal recovery of block models
- Community detection and stochastic block models: recent developments
- Community detection thresholds and the weak Ramanujan property
- Computational barriers in minimax submatrix detection
- Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms
- Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
- Dictionary learning and tensor decomposition via the sum-of-squares method
- 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
- Fundamental limits of symmetric low-rank matrix estimation
- Fusion, propagation, and structuring in belief networks
- Global optimization with polynomials and the problem of moments
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Information, Physics, and Computation
- Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization
- Message-passing algorithms for synchronization problems over compact groups
- Noisy tensor completion via the sum-of-squares hierarchy
- Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
- On the Shannon capacity of a graph
- On the optimization landscape of tensor decompositions
- On the power of unique 2-prover 1-round games
- Optimal detection of sparse principal components in high dimension
- Optimality and sub-optimality of PCA. I: Spiked random matrix models
- Phase transitions in semidefinite relaxations
- Proof of the achievability conjectures for the general stochastic block model
- Random Fields and Geometry
- Random matrices and complexity of spin glasses
- Reducibility among combinatorial problems
- Rounding sum-of-squares relaxations
- Spectral redemption in clustering sparse networks
- State evolution for general approximate message passing algorithms, with applications to spatial coupling
- Statistical Physics of Spin Glasses and Information Processing
- Statistical limits of spiked tensor models
- Sum-of-squares proofs and the quest toward optimal algorithms
- The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
- The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
- The Lovász theta function for random regular graphs and community detection in the hard regime
Cited in
(12)- Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
- Algorithmic obstructions in the random number partitioning problem
- Statistical-computational trade-offs in tensor PCA and related problems via communication complexity
- Computing the partition function of the Sherrington-Kirkpatrick model is hard on average
- Long random matrices and tensor unfolding
- An extension of the angular synchronization problem to the heterogeneous setting
- The landscape of the planted clique problem: dense subgraphs and the overlap gap property
- A polynomial-time approximation scheme for the maximal overlap of two independent Erdős-Rényi graphs
- Estimation of Wasserstein distances in the spiked transport model
- The committee machine: computational to statistical gaps in learning a two-layers neural network
- Computational statistical physics. Lecture notes, Guwahati SERC school, India, December 1--21, 2008. Invited lectures
- Fundamental barriers to high-dimensional regression with convex penalties
This page was built for publication: Notes on computational-to-statistical gaps: predictions using statistical physics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1729830)
