Oracle Lower Bounds for Stochastic Gradient Sampling Algorithms
  We consider the problem of sampling from a strongly log-concave density in
$\mathbb{R}^d$, and prove an information theoretic lower bound on the number of
stochastic gradient queries of the log density needed. Several popular sampling
algorithms (including many Markov chain Monte Carlo methods) operate by using
stochastic gradients of the log density to generate a sample; our results
establish an information theoretic limit for all these algorithms.
  We show that for every algorithm, there exists a well-conditioned strongly
log-concave target density for which the distribution of points generated by
the algorithm would be at least $\varepsilon$ away from the target in total
variation distance if the number of gradient queries is less than
$\Omega(\sigma^2 d/\varepsilon^2)$, where $\sigma^2 d$ is the variance of the
stochastic gradient. Our lower bound follows by combining the ideas of Le Cam
deficiency routinely used in the comparison of statistical experiments along
with standard information theoretic tools used in lower bounding Bayes risk
functions. To the best of our knowledge our results provide the first
nontrivial dimension-dependent lower bound for this problem.
