###### tags: `one-offs` `sampling` `mcmc` `subsampling`
# Minibatch Markov Chain Monte Carlo
**Overview**: In this note, I informally review some aspects of the class of algorithms which combine standard Markov Chain Monte Carlo (MCMC) methodologies with minibatching techniques.
## Introduction
Markov Chain Monte Carlo (MCMC) is an algorithmic framework for approximately sampling from probability measures to which we only have limited access. For example, Random Walk Metropolis only requires pointwise access to the density of the target measure, up to a normalising constant. The Metropolis-Adjusted Langevin Algorithm and Hamiltonian Monte Carlo assume the same access, as well as pointwise access to the gradient of the logarithm of this density. MCMC algorithms differ in what form of access to the target they assume, and how they process that information. These 'modes of access' are often referred to as *oracles*.
As in many numerical endeavours, there are tradeoffs involved in the design of MCMC algorithms. For example, even when relatively strong oracles are available in principle, they may be quite computationally expensive to implement. As such, it is of interest to synthesise new oracles which are in some sense weaker, but cheaper.
## Minibatching Oracles
Going forward, we will assume that the density of the target measure admits some factorisation into individual components, i.e.
\begin{align}
\pi (\mathrm{d} x) = \mu (\mathrm{d} x) \cdot \prod_{i \in [N]} \psi_i (x),
\end{align}
where $\mu$ is some simple reference measure, and each $\psi_i$ is individually inexpensive to evaluate. For $B \subseteq [N]$, it will be useful to abbreviate $\psi_B (x) = \prod_{i \in B} \psi_i (x)$, and for $B = [N]$, we can simply write $\Psi(x)$.
In standard MCMC algorithms, proposal moves and accept-reject decisions are made on the basis of $\Psi$. In Minibatch MCMC, these operations are made on the basis of $\psi_B$ for 'minibatches' $B$ which satisfy $|B| \ll N$.
### Proposals
Langevin Monte Carlo is based around the idea of constructing a Markov chain whose dynamics emulate the Overdamped Langevin Diffusion,
\begin{align}
\mathrm{d} X_t = \nabla_x \log \left( \frac{\mathrm{d} \pi}{\mathrm{d} \lambda} \right) (x) \, \mathrm{d} t + \sqrt{2} \, \mathrm{d} W.
\end{align}
where $\lambda$ denotes Lebesgue measure. Assuming that $\mu = \lambda$, the drift term of this SDE then has the form
\begin{align}
\nabla_x \log \left( \frac{\mathrm{d} \pi}{\mathrm{d} \lambda} \right) (x) &= \nabla_x \log \left( \prod_{i \in [N]} \psi_i (x) \right) \\
&= \sum_{i \in [N]} \nabla_x \log \psi_i (x).
\end{align}
When $N$ is large, it is natural to approximate this term by subsampling, i.e.
\begin{align}
\sum_{i \in [N]} \nabla_x \log \psi_i (x) &\approx \frac{N}{|B|} \cdot \sum_{i \in B} \nabla_x \log \psi_i (x),
\end{align}
which allows for approximate proposals to be generated at a greatly-reduced cost. These approximations are typically relatively easy to analyse, as they are unbiased at the level of the gradient. This proposal thus corresponds roughly to inflating the diffusivity of the underlying process, by a factor which depends on both the minibatch size and the discretisation step-size. It bears mentioning that modifying the process will typically impact its equilibrium properties, and this impact is not always easy to assess a priori.
Similar ideas are naturally adapted to other proposal schemes based on simulation of stochastic processes which involve gradient information, with similar associated risks.
### Accept-Reject Decisions
In Metropolis-Hastings algorithms, proposed moves are evaluated on the basis of a so-called acceptance probability, which typically requires computing ratio of the density of $\pi$ at both the current location $x$ to the density at the proposed new location $x^{'}$. As with proposals, this can be prohibitively expensive for large $N$, and so various works have considered reduced-cost approximations. The simplest such approach would be to approximate
\begin{align}
\Psi(y) / \Psi (x) \approx \psi_B (y) / \psi_B (x)
\end{align}
for some $B \subseteq [N]$. While similarly natural, the analysis of this approximation is more challenging, due to the presence of additional nonlinearity involved in converting this ratio into a binary accept-reject decision.
There are also methods which grow the set $B$ adaptively until the accept-reject decision can be made with sufficient confidence; one can imagine that such approaches are yet more challenging to analyse.
Additionally, there are refined analyses which tend to suggest that in order to control the bias induced by the additional stochasticity, this ratio should be penalised by an additional factor which explicitly accounts for the noisiness of the ratio estimator. So, at some level, it appears that there is something qualitatively different about using minibatching to approximate proposal moves and accept-reject decisions.
### Other Forms of Minibatching
There are forms of MCMC which do not use gradient-based proposalsm and which do not involve accept-reject decisions, e.g. Gibbs sampling. Minibatching techniques can still be used in these settings, but tend to involve more case-specific analyses. As such, I do not discuss them further at present.
## Costs and Tradeoffs
Without serious care, typical minibatching MCMC methods will not admit the desired invariant measure, even when some form of accept-reject filter is incorporated. As such, it is relatively common to cast the accept-reject step aside entirely, enabling a much simpler mathematical analysis, while perhaps further inflating the error of the method.
Typically, for a given minibatch size $|B|$ and desired error tolerance $\varepsilon$, theory suggest that one can find a discretisation step-size $h$ such that the process converges to an invariant measure $\hat{\pi}_{h, B}$ which is $\varepsilon$-close to $\pi$ in some distance of interest. I do not have a good sense for how relevant such existence results are in practice, or how they have been used to inform practical implementations of such methods.
A separate approach is to run coupled copies of the process with different minibatch sizes and step-sizes, and use the difference between the processes as a coarse estimator of the error relative to the full-batch, perfectly-discretised process. This is related to methods like Multilevel Monte Carlo.
## Outlook
Minibatch methods occupy an interesting place in the landscape of MCMC algorithms. It appears that they are able to offer affordable solutions to certain sampling-related problems, but perhaps not exactly the problems with which people have historically been concerned.
Roughly speaking, conventional MCMC research focuses carefully on ensuring convergence to the desired invariant measure, and prefers to sidestep approximations which induce a bias where possible. It seems that satisfactorily achieving these goals with minibatching methods is not so straightforward, despite substantial efforts.
In contrast, as solutions to statistical problems, things may be more positive than the MCMC perspective suggests. For context, it is well-understood that when using stochastic gradient methods for parameter estimation, it is only really interesting to solve the optimisation problem to within an error which matches the statistical error involved with the ideal estimator; high-accuracy estimators do not actually improve the situation so much, at least at the statistical level. One hopes that for minibatching MCMC methods, there may be a similar story to tell.
It also appears relatively clear that whether biased or otherwise, these methods are practically interesting, and will be used. If 'exact' methods are simply not feasible, but inexact, cheap methods are feasible, it is difficult to recommend the former class. As such, it seems inevitably relevant for theorists characterise and control these biases, as pertains to practical estimation problems.

Overview: In this note, I log some basic observations about diffusion-based generative models.

8/14/2023Overview: In this note, I describe some aspects of hierarchical structure in MCMC algorithms, and how they can be of theoretical and practical relevance.

8/9/2023Overview: In this note, I discuss a recurrent question which can be used to generate research questions about methods of all sorts. I then discuss a specific instance of how this question has proved fruitful in the theory of optimisation algorithms. Methods and Approximations A nice story is that when Brad Efron derived the bootstrap, it was done in service of the question “What is the jackknife an approximation to?”. I can't help but agree that there's something quite exciting about research questions which have this same character of ''What is (this existing thing) an approximation to?''. One bonus tilt on this which I appreciate is that there can be multiple levels of approximation, and hence many answers to the same question. One well-known example is gradient descent, which can be viewed as an approximation to the proximal point method, which can then itself be viewed as an approximation to a gradient flow. There are probably even more stops along the way here. In this case, there is even the perspective that from the perspective of mathematical theory, there may be at least as much to be gained by stopping off at the proximal point interpretation, as there is from the gradient flow perspective. My experience is that generalist applied mathematicians get to grips with the gradient flow quickly, but optimisation theorists can squeeze more out of the PPM formulation. There is thus some hint that using this 'intermediate' approximation can be particularly insightful in its own right. It would be interesting to collect more examples with this character.

5/22/2023Overview: In this note, I prove Hoeffding's inequality from the perspectives of martingales and convex ordering. The Basic Construction Let $-\infty<a<x<b<\infty$, and define a random variable $M$ with law $M\left(x;a,b\right)$ by \begin{align} M=\begin{cases} a & \text{w.p. }\frac{b-x}{b-a}\ b & \text{w.p. }\frac{x-a}{b-a}. \end{cases}

5/22/2023
Published on ** HackMD**