Many high-dimensional statistical inference problems are believed to possess inherent computational hardness. Various frameworks have been proposed to give rigorous evidence for such hardness, including lower bounds against restricted models of computation (such as low-degree functions), as well as methods rooted in statistical physics that are based on free energy landscapes. This paper aims to make a rigorous connection between the seemingly different low-degree and free-energy based approaches. We define a free-energy based criterion for hardness and formally connect it to the well-established notion of low-degree hardness for a broad class of statistical problems, namely all Gaussian additive models and certain models with a sparse planted signal. By leveraging these rigorous connections we are able to: establish that for Gaussian additive models the "algebraic" notion of low-degree hardness implies failure of "geometric" local MCMC algorithms, and provide new low-degree lower bounds for sparse linear regression which seem difficult to prove directly. These results provide both conceptual insights into the connections between different notions of hardness, as well as concrete technical tools such as new methods for proving low-degree lower bounds.
翻译:许多高维统计推论问题被认为具有内在的计算硬性。 已经提出了各种框架,为这种硬性提供有力的证据,包括针对限制性计算模型(如低度函数)的较低界限,以及基于自由能源景观的基于统计物理的方法。 本文旨在将表面上不同的低度和自由能源方法之间建立紧密的联系。 我们为基于硬性定义了一个基于自由能源的标准,并正式将其与一系列广泛的统计问题的既定的低度硬性概念联系起来,即所有高斯添加剂模型和某些带有稀释信号的模型。 通过利用这些严格的连接,我们能够:为高斯添加剂模型确立低度硬性“等”概念意味着“地理”本地MC算法的失败,并为似乎难以直接证明的稀薄线性回归提供新的低度低度下限。 这些结果既提供了对不同硬性概念之间联系的概念的理论洞察力,也提供了具体的技术工具,例如证明低度下限的新方法。