Timezone: »

 
Poster
The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics
Afonso S Bandeira · Ahmed El Alaoui · Samuel Hopkins · Tselil Schramm · Alexander S Wein · Ilias Zadik

Wed Nov 30 02:00 PM -- 04:00 PM (PST) @ Hall J #930
in Poster Session 4 »

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.

Keywords: low-degree likelihood ratio · Information-computation gaps · sparse regression · statistical physics · MCMC methods

Author Information

Afonso S Bandeira (ETH Zurich)
Ahmed El Alaoui (Stanford University)
Samuel Hopkins (Massachusetts Institute of Technology)
Tselil Schramm (Stanford University)
Alexander S Wein (University of California, Davis)
Ilias Zadik (MIT)

I am a CDS Moore-Sloan (postdoctoral) fellow at the Center for Data Science of NYU and a member of it's Math and Data (MaD) group. I received my PhD on September 2019 from MIT , where I was advised by David Gamarnik. My research lies broadly in the interface of high dimensional statistics, the theory of machine learning and applied probability.

More from the Same Authors