mlsanityData to 14 Oct 2026

Notes on computational-to-statistical gaps: predictions using statistical physics

arXiv 1803.11132 ↗First posted 29 Mar 2018stat.ML cs.DS cs.LGcited by 22

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 22 papers in the map (data through 14 Oct 2026). First posted on arXiv 29 Mar 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 6; 2022: 2; 2023: 5; 2024: 7; 2025: 1; 2026: 1.

22 papers.

Sort:

By area:

  1. 2025All Roads Lead to Likelihood: The Value of Reinforcement Learning in Fine-Tuningcited by 59
  2. 2022The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statisticscited by 31
  3. 2023Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspectivecited by 26
  4. 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
  5. 2024Fundamental computational limits of weak learnability in high-dimensional multi-index modelscited by 19
  6. 2021Long Random Matrices and Tensor Unfoldingcited by 10
  7. 2023Injectivity of ReLU networks: perspectives from statistical physicscited by 10
  8. 2023Optimal Algorithms for the Inhomogeneous Spiked Wigner Modelcited by 8
  9. 2021Landscape analysis of an improved power method for tensor decompositioncited by 7
  10. 2021Average-Case Communication Complexity of Statistical Problemscited by 5
  11. 2024Spectral Phase Transition and Optimal PCA in Block-Structured Spiked modelscited by 4
  12. 2023Learning from higher-order statistics, efficiently: hypothesis tests, random features, and neural networkscited by 3
10 more
  1. 2024A Random Matrix Approach to Low-Multilinear-Rank Tensor Approximationcited by 3
  2. 2024Cryptographic Hardness of Score Estimationcited by 3
  3. 2021Bayesian reconstruction of memories stored in neural networks from their connectivitycited by 2
  4. 2021Inferring Hidden Structures in Random Graphscited by 2
  5. 2023Planted Bipartite Graph Detectioncited by 2
  6. 2024Fundamental limits of Non-Linear Low-Rank Matrix Estimationcited by 2
  7. 2026A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Modelscited by 2
  8. 2024Unrolled denoising networks provably learn optimal Bayesian inferencecited by 1
  9. 2022Bayesian Inference with Nonlinear Generative Models: Comments on Secure Learningcited by 0
  10. 2024Dynamic angular synchronization under smoothness constraintscited by 0