Abstract
Bandeira et al. (2022) introduced the Franz-Parisi (FP) criterion forcharacterizing the computational hard phases in statistical detection problems.The FP criterion, based on an annealed version of the celebrated Franz-Parisipotential from statistical physics, was shown to be equivalent to low-degreepolynomial (LDP) lower bounds for Gaussian additive models, thereby connectingtwo distinct approaches to understanding the computational hardness instatistical inference. In this paper, we propose a refined FP criterion thataims to better capture the geometric ``overlap" structure of statisticalmodels. Our main result establishes that this optimized FP criterion isequivalent to Statistical Query (SQ) lower bounds -- another foundationalframework in computational complexity of statistical inference. Crucially, thisequivalence holds under a mild, verifiable assumption satisfied by a broadclass of statistical models, including Gaussian additive models, planted sparsemodels, as well as non-Gaussian component analysis (NGCA), single-index (SI)models, and convex truncation detection settings. For instance, in the case ofconvex truncation tasks, the assumption is equivalent with the Gaussiancorrelation inequality (Royen, 2014) from convex geometry. In addition to the above, our equivalence not only unifies and simplifies thederivation 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 alsoyields new SQ lower bounds of independent interest, including for thecomputational gaps in mixed sparse linear regression (Arpino et al., 2023) andconvex truncation (De et al., 2023).