| 摘要: |
| 采样是一类基本的计算问题.从一个解空间中依特定概率分布进行随机采样,这一问题在近似计数、概率推断、统计学习等方面都有着诸多重要的应用.在大数据时代,采样问题的分布式算法与分布式计算复杂性受到越来越多的关注.近年来,有一系列的工作对分布式采样理论展开系统性的研究.综述了分布式采样的重要结论,主要包括有严格理论保障的分布式采样算法、采样问题在分布式模型上的计算复杂性以及采样与推断等问题在分布式计算模型中的相互联系. |
| 关键词: 采样 分布式计算 计算复杂性 吉布斯分布 马尔可夫链 |
| DOI：10.13328/j.cnki.jos.006372 |
| 分类号: |
| 基金项目:国家重点研发计划重点专项(2018YFB1003202) |
|
| Survey on Theory of Distributed Sampling |
|
FENG Wei-Ming, YIN Yi-Tong
|
|
State Key Laboratory for Novel Software Technology (Nanjing University), Nanjing 210023, China
|
| Abstract: |
| Sampling is a fundamental class of computational problems. The problem of generating random samples from a solution space according to certain probability distribution has numerous important applications in approximate counting, probability inference, statistical learning, etc. In the big data era, the distributed sampling attracts considerably more attentions. In recent years, there is a line of research works that systematically study the theory of distributed sampling. This study surveys important results on distributed sampling, including distributed sampling algorithms with theoretically provable guarantees, the computational complexity of sampling in the distributed computing model, and the mutual relation between sampling and inference in the distributed computing model. |
| Key words: sampling distributed computing computational complexity Gibbs distributions Markov chain |
