mlsanityData to 7 Oct 2026

The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics

arXiv 2205.09727 ↗First posted 19 May 2022math.ST cond-mat.stat-mech cs.CCcited by 31

Not on the map. Why?

Abstract (arXiv)

Many high-dimensional statistical inference problems are believed to possess inherent computational hardness. Various frameworks have been proposed to give rigorous evidence for such hardness, including lower bounds against restricted models of computation (such as low-degree functions), as well as methods rooted in statistical physics that are based on free energy landscapes. This paper aims to make a rigorous connection between the seemingly different low-degree and free-energy based approaches. We define a free-energy based criterion for hardness and formally connect it to the well-established notion of low-degree hardness for a broad class of statistical problems, namely all Gaussian additive models and certain models with a sparse planted signal. By leveraging these rigorous connections we are able to: establish that for Gaussian additive models the "algebraic" notion of low-degree hardness implies failure of "geometric" local MCMC algorithms, and provide new low-degree lower bounds for sparse linear regression which seem difficult to prove directly. These results provide both conceptual insights into the connections between different notions of hardness, as well as concrete technical tools such as new methods for proving low-degree lower bounds.

Key facts. Cited by 31 papers in the map (data through 7 Oct 2026). Builds on 37 of its 80 references that are in the map. First posted on arXiv 19 May 2022.

Builds on

37 of 80 references.

References · 37

  1. 2015Statistical physics of inference: Thresholds and algorithmscited by 128
  2. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 82
  3. 2014A statistical model for tensor PCAcited by 72
  4. 2017The power of sum-of-squares for detecting hidden structurescited by 54
  5. 2020Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalentcited by 51
  6. 2020Reducibility and Statistical-Computational Gaps from Secret Leakagecited by 50
  7. 2019Subexponential-Time Algorithms for Sparse PCAcited by 41
  8. 2020Computational Barriers to Estimation from Low-Degree Polynomialscited by 38
  9. 2018Optimality and Sub-optimality of PCA I: Spiked Random Matrix Modelscited by 33
  10. 2019Computational Hardness of Certifying Bounds on Constrained PCA Problemscited by 30
  11. 2017Bayesian estimation from few samples: community detection and related problemscited by 28
  12. 2016Statistical limits of spiked tensor modelscited by 27
25 more
  1. 2016Mutual information for symmetric rank-one matrix estimation: A proof of the replica formulacited by 26
  2. 2018High-dimensional estimation via sum-of-squares proofscited by 25
  3. 2021Lattice-Based Methods Surpass Sum-of-Squares in Clusteringcited by 25
  4. 2013Limits of local algorithms over sparse random graphscited by 23
  5. 2015MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channelcited by 22
  6. 2018Notes on computational-to-statistical gaps: predictions using statistical physicscited by 22
  7. 2014Computational Lower Bounds for Community Detection on Random Graphscited by 21
  8. 2018Fundamental limits of detection in the spiked Wigner modelcited by 18
  9. 2016Information-theoretic thresholds for community detection in sparse networkscited by 17
  10. 2020Optimal Low-Degree Hardness of Maximum Independent Setcited by 16
  11. 2015Phase Transitions in Sparse PCAcited by 15
  12. 2019The Kikuchi Hierarchy and Tensor PCAcited by 15
  13. 2019How to iron out rough landscapes and get optimal performances: Averaged Gradient Descent and its application to tensor PCAcited by 14
  14. 2021The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomialscited by 14
  15. 2021Non-Gaussian Component Analysis via Lattice Basis Reductioncited by 14
  16. 2020Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphscited by 13
  17. 2020Counterexamples to the Low-Degree Conjecturecited by 12
  18. 2021Reconstruction on Trees and Low-Degree Polynomialscited by 10
  19. 2018Glassy nature of the hard phase in inference problemscited by 9
  20. 2019The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Propertycited by 9
  21. 2020Free Energy Wells and Overlap Gap Property in Sparse PCAcited by 9
  22. 2020Hypothesis testing with low-degree polynomials in the Morris class of exponential familiescited by 7
  23. 2022Almost-Linear Planted Cliques Elude the Metropolis Processcited by 7
  24. 2018High Dimensional Linear Regression using Lattice Basis Reductioncited by 5
  25. 2019A greedy anytime algorithm for sparse PCAcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 4; 2023: 8; 2024: 8; 2025: 9; 2026: 2.

31 papers.

Sort:

By area:

  1. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 60
  2. 2023Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspectivecited by 26
  3. 2024Fundamental computational limits of weak learnability in high-dimensional multi-index modelscited by 17
  4. 2022Statistical and Computational Phase Transitions in Group Testingcited by 10
  5. 2024Tensor cumulants for statistical inference on invariant distributionscited by 8
  6. 2023Statistical-Computational Tradeoffs in Mixed Sparse Linear Regressioncited by 7
  7. 2023Detection of Dense Subhypergraphs by Low-Degree Polynomialscited by 7
  8. 2022On free energy barriers in Gaussian priors and failure of cold start MCMC for high-dimensional unimodal distributionscited by 6
  9. 2022Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomialscited by 6
  10. 2023Computational Lower Bounds for Graphon Estimation via Low-degree Polynomialscited by 6
  11. 2024A computational transition for detecting correlated stochastic block models by low-degree polynomialscited by 6
  12. 2025The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Modelscited by 6
19 more
  1. 2025Statistical Advantage of Softmax Attention: Insights from Single-Location Regressioncited by 6
  2. 2022Is it easier to count communities than find them?cited by 4
  3. 2023Detection-Recovery Gap for Planted Dense Cyclescited by 4
  4. 2023Precise Error Rates for Computationally Efficient Testingcited by 4
  5. 2024Spectral Phase Transition and Optimal PCA in Block-Structured Spiked modelscited by 4
  6. 2024Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testingcited by 3
  7. 2024Fundamental limits of Non-Linear Low-Rank Matrix Estimationcited by 2
  8. 2024Low coordinate degree algorithms II: Categorical signals and generalized stochastic block modelscited by 2
  9. 2025Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguitycited by 2
  10. 2025Computational bottlenecks for denoising diffusionscited by 2
  11. 2025An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Boundscited by 1
  12. 2026A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Modelscited by 1
  13. 2023On a Near-Optimal & Efficient Algorithm for the Sparse Pooled Data Problemcited by 0
  14. 2024Low-degree phase transitions for detecting a planted clique in sublinear timecited by 0
  15. 2025A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomialscited by 0
  16. 2025A large deviation view of stationarized fully lifted blirp interpolationcited by 0
  17. 2025A Smooth Computational Transition in Tensor PCAcited by 0
  18. 2025Statistical and computational challenges in rankingcited by 0
  19. 2026Low-degree Lower bounds for clustering in moderate dimensioncited by 0