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

Bandeira et al (The Franz–Parisi (FP) criterion and computational trade-offs in high dimensional statistics Advances in Neural Information Processing Systems 35 33831–44) introduced the FP criterion for characterizing the computational hard phases in statistical detection problems. The FP criterion, based on an annealed version of the celebrated FP potential from statistical physics, was shown to be equivalent to low-degree polynomial lower bounds for Gaussian additive models (GAMs), 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 GAMs, 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 and the SI model–but also yields new SQ lower bounds of independent interest, including for the computational gaps in mixed sparse linear regression (mSLR) and convex truncation.