The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics

Understand

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.