标题： 一种优化的弗朗茨-帕拉西判据及其与 SQ 下界等价性 显示英文标题

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

摘要： 班德里亚等人（2022年）引入了弗朗茨-帕里西（FP）准则，用于表征统计检测问题中的计算困难相位。该FP准则基于统计物理中著名的弗朗茨-帕里西势能的退火版本，被证明与高斯加性模型的低次多项式（LDP）下界等价，从而连接了两种理解统计推断中计算难度的不同方法。本文中，我们提出了一种改进的FP准则，旨在更好地捕捉统计模型的几何“重叠”结构。我们的主要结果表明，这种优化后的FP准则等价于统计查询（SQ）下界——这是统计推断计算复杂性中的另一个基础框架。关键在于，这一等价性在满足广泛统计模型类的一个温和且可验证的假设下成立，包括高斯加性模型、稀疏植入模型以及非高斯成分分析（NGCA）、单指标（SI）模型和凸截断检测设置。例如，在凸截断任务的情况下，该假设等价于凸几何中的高斯相关不等式（罗伊恩，2014年）。除了上述内容外，我们的等价性不仅统一并简化了多个已知SQ下界的推导——例如对于NGCA模型（迪亚科尼科拉斯等人，2017年）和SI模型（达米安等人，2024年）——还产生了新的独立有趣的SQ下界，包括混合稀疏线性回归（阿尔皮诺等人，2023年）和凸截断（德等人，2023年）中的计算差距。 显示英文摘要

摘要： 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).