An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
computational gapscomputational hardnessconvex geometryconvex truncation detectionfranz-parisi criteriongaussian additive modelsgaussian correlation inequalitygeometric overlap structurelow-degree polynomial boundsmixed sparse linear regressionnon-gaussian component analysisoptimization techniquesplanted sparse modelssingle-index modelsstatistical inferencestatistical query lower bounds
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