An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
Siyu Chen, Theodor Misiakiewicz, Ilias Zadik, Peiyuan Zhang
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, non-Gaussian component analysis, single-index models, and convex truncation detection. On top of the above, our equivalence not only unifies and simplifies the derivation of several known SQ lower bounds, but also yields new SQ-lower bounds of independent interest.