  This paper introduces a framework for speeding up Bayesian inference
conducted in presence of large datasets. We design a Markov chain whose
transition kernel uses an (unknown) fraction of (fixed size) of the available
data that is randomly refreshed throughout the algorithm. Inspired by the
Approximate Bayesian Computation (ABC) literature, the subsampling process is
guided by the fidelity to the observed data, as measured by summary statistics.
The resulting algorithm, Informed Sub-Sampling MCMC (ISS-MCMC), is a generic
and flexible approach which, contrary to existing scalable methodologies,
preserves the simplicity of the Metropolis-Hastings algorithm. Even though
exactness is lost, i.e. the chain distribution approximates the posterior, we
study and quantify theoretically this bias and show on a diverse set of
examples that it yields excellent performances when the computational budget is
limited. If available and cheap to compute, we show that setting the summary
statistics as the maximum likelihood estimator is supported by theoretical
arguments.
