An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds

• URL: http://arxiv.org/abs/2506.06259v1
• Date: Fri, 06 Jun 2025 17:39:32 GMT
• Title: An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
• Abstract summary: 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.
• Score: 24.13557931882888
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bandeira et al. (2022) introduced the Franz-Parisi (FP) criterion for characterizing the computational hard phases in statistical detection problems. The FP criterion, based on an annealed version of the celebrated Franz-Parisi potential from statistical physics, was shown to be equivalent to low-degree polynomial (LDP) lower bounds for Gaussian additive models, thereby connecting two distinct approaches to understanding the computational hardness in statistical inference. In this paper, we propose a refined FP criterion that aims to better capture the geometric ``overlap" structure of statistical models. Our main result establishes that this optimized FP criterion is equivalent to Statistical Query (SQ) lower bounds -- another foundational framework in computational complexity of statistical inference. Crucially, this equivalence holds under a mild, verifiable assumption satisfied by a broad class of statistical models, including Gaussian additive models, planted sparse models, as well as non-Gaussian component analysis (NGCA), single-index (SI) models, and convex truncation detection settings. For instance, in the case of convex truncation tasks, the assumption is equivalent with the Gaussian correlation inequality (Royen, 2014) from convex geometry. In addition to the above, our equivalence not only unifies and simplifies the derivation of several known SQ lower bounds -- such as for the NGCA model (Diakonikolas et al., 2017) and the SI model (Damian et al., 2024) -- but also yields new SQ lower bounds of independent interest, including for the computational gaps in mixed sparse linear regression (Arpino et al., 2023) and convex truncation (De et al., 2023).

Related papers

• A Spectral Framework for Closed-Form Relative Density Estimation [0.554780083433538]
  We propose a closed-form spectral framework for relative log-density estimation in linearly parameterized probabilistic models.<n>We derive an explicit spectral formula based only on first- and second-order feature moments, yielding closed-form estimators of both divergences and log-density potentials for fixed features.
  arXiv  Detail & Related papers  (2026-05-11T14:51:17Z)
• The monotonicity of the Franz-Parisi potential is equivalent with Low-degree MMSE lower bounds [5.6738617521792145]
  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.
  arXiv  Detail & Related papers  (2026-03-20T15:53:34Z)
• Generative and Nonparametric Approaches for Conditional Distribution Estimation: Methods, Perspectives, and Comparative Evaluations [2.0236506875465863]
  This article reviews and compares several representative approaches spanning classical nonparametric methods and modern generative models.<n>The performance metrics used for the estimated conditional distribution include the mean-squared errors of conditional mean and standard deviation.
  arXiv  Detail & Related papers  (2026-01-30T07:10:36Z)
• Estimating Ising Models in Total Variation Distance [23.343281561400033]
  We consider the problem of estimating Ising models over $n$ variables in Total Variation (TV) distance, given $l$ independent samples from the model.<n>Our main contribution is a unified analysis of the Maximum Pseudo-Likelihood Estorimator (MPLE) for two general classes of Ising models.<n>Our results yield optimal or near-time algorithms and optimal or near-time sample complexity guarantees in a variety of settings.
  arXiv  Detail & Related papers  (2025-11-26T03:15:41Z)
• T-Rex: Fitting a Robust Factor Model via Expectation-Maximization [0.0]
  We propose a novel expectation-maximization (EM) algorithm for robustly fitting statistical factor models.<n>Our approach is based on Tyler's M-estimator of the scatter matrix for an elliptical distribution.<n>We present numerical experiments on both synthetic and real examples.
  arXiv  Detail & Related papers  (2025-05-17T18:53:06Z)
• Identification and Estimation of Simultaneous Equation Models Using Higher-Order Cumulant Restrictions [9.10992754495906]
  Identifying structural parameters in linear simultaneous equation models is a fundamental challenge in economics and related fields.<n>We show that under any diagonal higher-cumulant condition, the structural parameter matrix can be identified by solving an eigenvector problem.<n>Our framework offers a transparent way to test for it, all within the same higher-orderity setting employed by earlier studies.
  arXiv  Detail & Related papers  (2025-01-12T11:27:39Z)
• Transition of $α$-mixing in Random Iterations with Applications in Queuing Theory [0.0]
  We show the transfer of mixing properties from the exogenous regressor to the response via coupling arguments.<n>We also study Markov chains in random environments with drift and minorization conditions, even under non-stationary environments.
  arXiv  Detail & Related papers  (2024-10-07T14:13:37Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• State and parameter learning with PaRIS particle Gibbs [11.290331898505594]
  Non-linear state-space models are ubiquitous in statistical machine learning. PaRIS is a sequential Monte Carlo technique allowing for efficient online approximation of expectations of additive functionals. We design a novel additive smoothing algorithm, the Parisian particle Gibbs PPG sampler, which can be viewed as a PaRIS algorithm driven by conditional SMC moves.
  arXiv  Detail & Related papers  (2023-01-02T23:27:33Z)
• 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)
• A non-asymptotic model selection in block-diagonal mixture of polynomial experts models [1.491109220586182]
  We introduce a penalized maximum likelihood selection criterion to estimate the unknown conditional density of a regression model. We provide a strong theoretical guarantee, including a finite-sample oracle satisfied by the penalized maximum likelihood with a Jensen-Kullback-Leibler type loss.
  arXiv  Detail & Related papers  (2021-04-18T21:32:20Z)
• Probabilistic Circuits for Variational Inference in Discrete Graphical Models [101.28528515775842]
  Inference in discrete graphical models with variational methods is difficult. Many sampling-based methods have been proposed for estimating Evidence Lower Bound (ELBO) We propose a new approach that leverages the tractability of probabilistic circuit models, such as Sum Product Networks (SPN) We show that selective-SPNs are suitable as an expressive variational distribution, and prove that when the log-density of the target model is aweighted the corresponding ELBO can be computed analytically.
  arXiv  Detail & Related papers  (2020-10-22T05:04:38Z)
• Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
  We develop a framework that yields statistical accuracy based on interplay between the deterministic convergence rate of the algorithm at the population level, and its degree of (instability) when applied to an empirical object based on $n$ samples. We provide applications of our general results to several concrete classes of models, including Gaussian mixture estimation, non-linear regression models, and informative non-response models.
  arXiv  Detail & Related papers  (2020-05-22T22:30:52Z)
• An Optimal Statistical and Computational Framework for Generalized Tensor Estimation [10.899518267165666]
  This paper describes a flexible framework for low-rank tensor estimation problems. It includes many important instances from applications in computational imaging, genomics, and network analysis.
  arXiv  Detail & Related papers  (2020-02-26T01:54:35Z)

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.