The monotonicity of the Franz-Parisi potential is equivalent with Low-degree MMSE lower bounds

• URL: http://arxiv.org/abs/2603.20070v1
• Date: Fri, 20 Mar 2026 15:53:34 GMT
• Title: The monotonicity of the Franz-Parisi potential is equivalent with Low-degree MMSE lower bounds
• Abstract summary: We show that the power of low-degree estimations is equivalent to the monotonicity of the FP potential for a broad family of additive models.<n>Our results imply that the limits of these models are directly implied by the monotonicity of the annealed FP potential.
• Score: 5.6738617521792145
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Over the last decades, two distinct approaches have been instrumental to our understanding of the computational complexity of statistical estimation. The statistical physics literature predicts algorithmic hardness through local stability and monotonicity properties of the Franz--Parisi (FP) potential \cite{franz1995recipes,franz1997phase}, while the mathematically rigorous literature characterizes hardness via the limitations of restricted algorithmic classes, most notably low-degree polynomial estimators \cite{hopkins2017efficient}. For many inference models, these two perspectives yield strikingly consistent predictions, giving rise to a long-standing open problem of establishing a precise mathematical relationship between them. In this work, we show that for estimation problems the power of low-degree polynomials is equivalent to the monotonicity of the annealed FP potential for a broad family of Gaussian additive models (GAMs) with signal-to-noise ratio $λ$. In particular, subject to a low-degree conjecture for GAMs, our results imply that the polynomial-time limits of these models are directly implied by the monotonicity of the annealed FP potential, in conceptual agreement with predictions from the physics literature dating back to the 1990s.

Related papers

• Asymptotic breakdown point analysis of the minimum density power divergence estimator under independent non-homogeneous setups [2.449909275410287]
  The minimum density power divergence estimator (MDPDE) has gained significant attention in the literature of robust inference.<n>It has been successfully applied in various setups, including the case of independent and non-homogeneous (INH) observations.<n>No general result is known about the global reliability or the breakdown behavior of this estimator under the INH setup.
  arXiv  Detail & Related papers  (2025-08-17T16:33:58Z)
• Computational Complexity of Statistics: New Insights from Low-Degree Polynomials [57.377943721487966]
  This is a survey on the use of low-degrees to predict and explain the apparent statistical-computational tradeoffs in a variety of average-case computational problems.
  arXiv  Detail & Related papers  (2025-06-12T14:35:26Z)
• An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds [24.13557931882888]
  We optimize the Franz-Parisi criterion for characterizing the computational hard phases in statistical detection problems.<n>This equivalence holds under a mild assumption satisfied by a broad class of statistical models.<n>Our equivalence unifies and simplifies the derivation of several known SQ lower bounds.
  arXiv  Detail & Related papers  (2025-06-06T17:39:32Z)
• Hyperscaling of Fidelity and Operator Estimations in the Critical Manifold [0.0]
  We show that ground-state expectation values of observables supported on slow momentum modes can be approximated by their averages on the fixed-point theories to which the QFTs flow.<n>Our results allow for a clear identification of cases in which one can replace a QFT by its scale-invariant limit in the calculation of expectation values.
  arXiv  Detail & Related papers  (2025-05-21T14:20:54Z)
• Algebraic and Statistical Properties of the Ordinary Least Squares Interpolator [3.4320157633663064]
  We provide results for the minimum $ell$-norm OLS interpolator. We present statistical results such as an extension of the Gauss-Markov theorem. We conduct simulations that further explore the properties of the OLS interpolator.
  arXiv  Detail & Related papers  (2023-09-27T16:41:10Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  We propose algorithms with high-probability convergence results under less restrictive assumptions. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes in optimization.
  arXiv  Detail & Related papers  (2023-02-02T10:37:23Z)
• The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics [73.1090889521313]
  This paper aims to make a rigorous connection between the 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. Results provide both conceptual insights into the connections between different notions of hardness, as well as concrete technical tools.
  arXiv  Detail & Related papers  (2022-05-19T17:39:29Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• Divergence Frontiers for Generative Models: Sample Complexity, Quantization Level, and Frontier Integral [58.434753643798224]
  Divergence frontiers have been proposed as an evaluation framework for generative models. We establish non-asymptotic bounds on the sample complexity of the plug-in estimator of divergence frontiers. We also augment the divergence frontier framework by investigating the statistical performance of smoothed distribution estimators.
  arXiv  Detail & Related papers  (2021-06-15T06:26:25Z)
• Free Energy Wells and Overlap Gap Property in Sparse PCA [81.64027805404483]
  We study a variant of the sparse PCA (principal component analysis) problem in the "hard" regime. We show bounds on the depth of free energy wells for various Gibbs measures naturally associated to the problem. We prove that the Overlap Gap Property (OGP) holds in a significant part of the hard regime.
  arXiv  Detail & Related papers  (2020-06-18T17:18:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.