Markov chain Monte Carlo methods are often deemed too computationally
intensive to be of any practical use for big data applications, and in
particular for inference on datasets containing a large number $n$ of
individual data points, also known as tall datasets. In scenarios where data
are assumed independent, various approaches to scale up the Metropolis-Hastings
algorithm in a Bayesian inference context have been recently proposed in
machine learning and computational statistics. These approaches can be grouped
into two categories: divide-and-conquer approaches and, subsampling-based
algorithms. The aims of this article are as follows. First, we present a
comprehensive review of the existing literature, commenting on the underlying
assumptions and theoretical guarantees of each method. Second, by leveraging
our understanding of these limitations, we propose an original
subsampling-based approach which samples from a distribution provably close to
the posterior distribution of interest, yet can require less than $O(n)$ data
point likelihood evaluations at each iteration for certain statistical models
in favourable scenarios. Finally, we have only been able so far to propose
subsampling-based methods which display good performance in scenarios where the
Bernstein-von Mises approximation of the target posterior distribution is
excellent. It remains an open challenge to develop such methods in scenarios
where the Bernstein-von Mises approximation is poor.

本文综述了最近在机器学习和计算统计学领域提出的两类解决元数据分析中基于独立假设的马尔科夫链蒙特卡罗方法的方法：分而治之的方法和基于子采样的算法，并提出了一种新颖的基于子采样的方法，并在某些统计模型的有利情况下，每次迭代可以要求少于 $O (n)$ 数量级的数据点似然性评估，然而，在目标后验分布的 Bernstein-von Mises 逼近存在缺陷的情况下，我们目前只能提出能在基于子采样的方法中表现良好的方法，而在其他情况下这仍然是一个未解决的挑战。