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.
中文速览
统计推断中长期存在一个令人困惑的现象：某个问题在信息量上明明足够、理论上可解，但实际上找不到任何高效算法能在合理时间内给出答案，这就是所谓的"计算-统计鸿沟"（computational-to-statistical gap）。这篇讲义借用统计物理中的两套成熟工具——空腔方法（cavity method）与置信传播（belief propagation）以及复本方法（replica method）——来预测这道鸿沟究竟出现在信噪比的哪个位置，并以"刺突Wigner矩阵"和"随机块模型"社区检测这两个典型问题作为贯穿全文的例子加以阐释。核心思路是：贝叶斯推断的后验分布在数学形式上与统计物理的吉布斯分布完全吻合，于是自旋玻璃理论中分析相变的方法可以直接移植过来，用来判断后验分布是"连通一片"还是"碎裂成孤立簇"，前者意味着高效算法可行，后者则预示着计算上不可逾越的困难。这些启发式方法虽然缺乏严格证明，但其预测已在多个问题上被后续理论工作所验证，因此对于理解为什么某些大规模统计问题"原则上能解、实践中无解"具有重要的指导价值。
原文 arXiv:1803.11132;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1803.11132v2