Notes on computational-to-statistical gaps: predictions using statistical physics
Afonso S. Bandeira Department of Mathematics and Center for Data Science, Courant Institute of Mathematical Sciences, New York University , Amelia Perry Department of Mathematics, Massachusetts Institute of Technology and Alexander S. Wein Department of Mathematics, Massachusetts Institute of Technology
Abstract
In these notes we describe heuristics to predict computational-to-statistical gaps in certain statistical problems. These are regimes in which the underlying statistical problem is information-theoretically possible although no efficient algorithm exists, rendering the problem essentially unsolvable for large instances. The methods we describe here are based on mature, albeit non-rigorous, tools from statistical physics.
原文 arXiv:1803.11132;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1803.11132v2