Statistical Problems with Planted Structures: Information-Theoretical and Computational Limits
Statistical Problems with Planted Structures: Information-Theoretical and Computational Limits
复制标题
种植结构的统计问题：信息理论和计算限制
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Jiaming Xu
中科院分区：
文献类型：
--
作者：
Yihong Wu;Jiaming Xu
在过去的几年里，来自计算机科学、统计物理学和信息论的见解揭示了在两个不同阈值下的大量高维统计问题中的相变：一个是信息理论（IT）阈值，低于该阈值，观察太嘈杂，因此无论计算成本如何，都不可能推断出地面真值结构;另一个是计算阈值，在该计算阈值之上可以有效地执行推断，即，在时间上是输入大小的多项式。在中间状态下，推理在信息理论上是可能的，但在计算上是困难的。
本文以社区检测和子矩阵检测为例，综述了确定尖锐IT和计算极限的常用技术。对于IT限制，我们讨论的工具，包括分析最大似然估计的第一和第二矩方法，使用率失真理论证明不可能的结果的信息理论方法，以及源自统计物理学的方法，如插值方法。为了研究计算的限制，我们描述了一个共同的配方来构建一个随机的多项式时间约简方案，近似映射的种植集团问题的总变化距离感兴趣的问题的实例。
Over the past few years, insights from computer science, statistical physics, and information theory have revealed phase transitions in a wide array of high-dimensional statistical problems at two distinct thresholds: One is the information-theoretical (IT) threshold below which the observation is too noisy so that inference of the ground truth structure is impossible regardless of the computational cost; the other is the computational threshold above which inference can be performed efficiently, i.e., in time that is polynomial in the input size. In the intermediate regime, inference is information-theoretically possible, but conjectured to be computationally hard.
This article provides a survey of the common techniques for determining the sharp IT and computational limits, using community detection and submatrix detection as illustrating examples. For IT limits, we discuss tools including the first and second moment method for analyzing the maximal likelihood estimator, information-theoretic methods for proving impossibility results using rate-distortion theory, and methods originated from statistical physics such as interpolation method. To investigate computational limits, we describe a common recipe to construct a randomized polynomial-time reduction scheme that approximately maps instances of the planted clique problem to the problem of interest in total variation distance.
登录
查看更多内容
在 O(|E|log*|V|) 时间内恢复超出 KestenâStigum 阈值的隐藏社区
影响因子：
1
作者：
Hajek, Bruce;Wu, Yihong;Xu, Jiaming
通讯作者：
Xu, Jiaming
DOI：
--
发表时间：
2017-09
期刊：
--
影响因子：
--
作者：
Jiaming Xu
通讯作者：
Jiaming Xu
通过消息传递进行子矩阵定位
影响因子：
6
作者：
Hajek, Bruce;Wu, Yihong;Xu, Jiaming
通讯作者：
Xu, Jiaming
尖峰张量模型的统计极限
DOI：
10.1214/19-aihp960
发表时间：
2020
期刊：
Probabilités et Statistiques
影响因子：
--
作者：
Perry, Amelia;Wein, Alexander S.;Bandeira, Afonso S.
通讯作者：
Bandeira, Afonso S.