The Square-Root Law for Subsampled Metropolis–Hastings

Metropolis–Hastings is a sampling algorithm that proposes a move and then accepts or rejects it by comparing the full-data log-likelihood at the old and new parameters. With millions of data points, each comparison means a full pass over the data. One family of methods tries to make the same decision from a small random subset of the data, adding points until a statistical test is confident about which side of the acceptance threshold the full-data value falls on. These methods work well early in a run. Once the chain settles near the posterior mode, though, the subset size grows toward the whole dataset. This is the "equilibrium bottleneck," and so far it has been reported as an empirical failure without an explanation.

This note proposes to explain it with tools from pure-exploration bandits, the theory of how many noisy samples you need to decide a question at a given confidence. Each accept/reject step is a threshold-crossing question: is a population mean above a cutoff? Bandit lower bounds say how many samples any test with error at most $\delta$ needs. The new step is to average that per-question cost over the uniform random threshold that Metropolis–Hastings draws at every step. The prediction is a square-root law: at equilibrium, any test that tries to reproduce the full-data decision needs on the order of $\kappa\sqrt{N\log(1/\delta)}$ data points per step. Here $\kappa$ measures how spread out the per-point log-likelihood ratios are, rescaled by the dataset size $N$. Without a variance-reduction step, $\kappa$ itself grows like $\sqrt{N}$, which recovers the observed bottleneck. With a cheap first-order correction it should stay roughly constant, which predicts genuinely sublinear cost. We will prove a matching lower bound and build a test that attains it. We will then check the law empirically and use it to locate where these decision-copying tests lose to exact methods that change the acceptance rule itself.

Core Claim

Write the Metropolis–Hastings decision as "accept if $x > 0$," where $x = \Lambda - \log u$, $\Lambda$ is the full-data log acceptance ratio, and $u$ is the uniform draw. The data enter $\Lambda$ as a sum $\sum_i \ell_i$ of per-point log-likelihood ratios. Let $\sigma$ be the standard deviation of the $\ell_i$ across the dataset and set $\kappa = N\sigma$.

The fixed-confidence analysis in Optimal Best Arm Identification with Fixed Confidence supplies the per-question cost. That paper proves instance-specific lower bounds of the form characteristic time times $\log(1/\delta)$ and gives the Track-and-Stop algorithm that matches them. Its threshold-crossing generalization in Sample complexity of partition identification using multi-armed bandits covers our case. For a Gaussian-like population, these results imply that resolving the sign of $x$ with error at most $\delta$ takes about $2\kappa^2\log(1/\delta)/x^2$ draws, capped at $N$ because a full pass removes all uncertainty.

Now average over $x$. Near zero, $x$ has density $f_0 = \mathbb{E}[e^{\Lambda}; \Lambda < 0]$, which is of order one whenever the acceptance rate is moderate. Integrating the capped cost against this density gives

$$\mathbb{E}[n] \approx 4 f_0\,\kappa\sqrt{2N\log(1/\delta)},$$

where $n$ is the number of data points examined in one step. The square root comes from the crossover point $|x| \approx \kappa\sqrt{2\log(1/\delta)/N}$, below which the cap at $N$ binds.

Three consequences follow, and each can be checked.

The first is the bottleneck itself. Proposal steps of size about $N^{-1/2}$ give $\sigma \sim N^{-1/2}$, so $\kappa \sim N^{1/2}$ and $\mathbb{E}[n] \sim N$. This explains the behaviour reported for MHSUBLHD, the method from Bardenet et al. that grows the subset until an empirical Bernstein confidence interval clears the threshold.

The second concerns control variates, which subtract a cheap Taylor approximation of each $\ell_i$ around a reference point. A first-order control variate shrinks the residual spread to about $1/N$ in the regular large-data regime, so $\kappa = O(1)$ and cost grows only like $\sqrt{N}$.

The third is that tightening $\delta$ is cheap. Cost grows only with $\sqrt{\log(1/\delta)}$, so per-step error can be made very small at little extra expense.

The claimed lower bound applies to every method whose goal is to reproduce the full-data decision with probability $1-\delta$. That includes Austerity in MCMC Land, which uses a sequential t-test, as well as MHSUBLHD. Exact methods such as TunaMH and MH-SS avoid the bound because they never try to reproduce that decision. They replace it with a different, factorized acceptance rule that has the same stationary distribution. This is the cleanest available account of why MH-SS can use about 10 points per iteration while adaptive-subset tests stall. It also turns "decision-copying versus exact" into a quantitative comparison rather than an anecdotal one.

Research Program

The theoretical part has two pieces. The first is to prove the lower bound for a single step. We will use the change-of-measure argument from Garivier and Kaufmann, adapted to sampling without replacement from a finite population. The adaptation needs an alternative population whose mean lies on the other side of the threshold and which agrees with the observed points, and it must make the $\min(N,\cdot)$ cap precise. We will then integrate the bound over the law of $x$ at stationarity. The second piece is a matching upper bound for our test, together with a total-variation bias bound on the stationary distribution in the style of Bardenet et al., expressed as a function of $\delta$. Constant factors may not match exactly; the target is matching rates in $N$, $\kappa$ and $\delta$.

The algorithm, which we call Tracking-Test Metropolis–Hastings, combines three pieces.

The first piece is a first-order control variate around a running reference point, to bring $\kappa$ down. It needs only per-point gradients, not the Hessians or analytic remainder bounds that MH-SS requires.

The second piece is the stopping rule. Bardenet's doubling schedule pays a union-bound penalty because it checks a confidence interval at each doubling. We replace it with an anytime generalized likelihood ratio stopping rule, the Chernoff-type rule used in Track-and-Stop, which can be checked after every batch without that penalty. Batches are sized geometrically, following the phased schedule of The Batch Complexity of Bandit Pure Exploration. That paper shows logarithmically many rounds suffice without losing sample optimality, which matters on vectorized hardware.

The third piece is stratification. We partition the data into strata, for example by clustering features or per-point gradient norms. Points are drawn across strata in proportions that track the optimal allocation for the half-space crossing question, estimated from previous MH steps.

That last choice makes the method stateful: it carries information from earlier iterations into the current one. TunaMH's optimality result is explicitly limited to stateless algorithms, so this is where a stateful method could legitimately do better. We are honest about how much the bandit allocation adds. For near-Gaussian residuals, the optimal allocation reduces to classical Neyman allocation, in which each stratum's share is proportional to its size times its standard deviation. A difference should appear only for skewed or heavy-tailed residuals, where the KL-based allocation departs from Neyman. We therefore treat stratification as a secondary ingredient and test it with a direct ablation.

Baselines

The naive reference is full-data Metropolis–Hastings with the same proposal. MH-SS reports 0.003 effective samples per second for standard MH on HEPMASS. We will rerun it on our hardware rather than reuse that figure.

The strongest decision-copying competitor is MHSUBLHD. It reports using 1% to 10% of the data during burn-in and up to 3x faster convergence than standard MH on covtype.binary. We run it with the same per-step $\delta$, the same proposal, and, as a separate arm, the same control variate. That separate arm isolates our stopping rule and allocation from the variance reduction, since otherwise a win could simply come from the control variate.

Austere MH, run at a matched nominal error level, is the cheap heuristic competitor.

The strongest overall competitor is MH-SS. On HEPMASS it reports an effective sample size per second of 46.07 for its second-order variant, and about 10 data points per iteration on Poisson regression. We run it from the authors' setup, counting its MAP search and Hessian cost in wall-clock time.

For models where MH-SS's analytic bounds are unavailable, the exact competitors are TunaMH and Poisson-MALA/Poisson-Barker from Markov Chain Monte Carlo without Evaluating the Target. The latter report 1.37 to 7.12 times the performance of PoissonMH on robust linear regression with $n = 200{,}000$. We give them the Lipschitz bounds their papers use. Every method receives the same proposal-scale tuning budget: a grid over step size, scored by effective samples per second on a held-out pilot run.

We will run two ablations. In the first, our test uses uniform rather than stratified draws, which isolates the allocation. In the second, our test uses Bardenet's doubling-plus-union-bound rule instead of the anytime stopping rule, which isolates the stopping rule.

What counts as winning depends on the regime. Among decision-copying tests, we count a win as lower mean $n$ per step at equilibrium together with no larger Kolmogorov–Smirnov or total-variation error against a long full-data reference chain. Against exact methods, we count a win as higher effective samples per second on non-GLM models, without claiming a win on GLMs.

Why not just…?

Why not just use SGLD and skip the accept/reject step? Stochastic-gradient Langevin dynamics (Welling & Teh) uses mini-batch gradients and no acceptance test. The TunaMH paper proves that inexact mini-batch methods can carry arbitrarily large asymptotic bias. Yuan and Wang report that SGLD fails Kolmogorov–Smirnov correctness checks that their corrected Tuna-SGLD passes. We include SGLD in the bias table only as a reference.

Why not just use the Austere t-test, which is simpler? If the square-root law holds, the t-test pays the same rate, because it is also a decision-copying test. Its advantage is therefore at most a constant factor, and it buys that constant with bias. Bardenet et al. show that bias appears under skewed, lognormal-type likelihood contributions. Our 2D lognormal experiment measures that tradeoff directly.

Why not just use Neyman-stratified sampling with Bardenet's test? This is the most serious threat to the stratification ingredient. It is exactly our uniform-versus-stratified ablation, with an anytime rule added. If it matches our full method, we will report that the bandit-derived allocation adds nothing beyond classical stratification. The contribution would then reduce to the lower bound, the square-root law, and the stopping rule, which still explain and partly fix the bottleneck. We expect a difference to appear only on heavy-tailed robust regression.

Why not just use MH-SS, which already uses about 10 points per step? On GLMs it likely beats any decision-copying test, and the square-root law predicts exactly that. The open question is whether bound-free tests are competitive where the remainder bounds MH-SS needs cannot be derived, and the HEPMASS-versus-robust-regression comparison settles where the crossover lies. Full-data GPU evaluation remains the practical default at moderate $N$. We report wall-clock crossover points against it as well.

Proposed Experiments

The decisive check is a scaling plot. We subsample covtype.binary (581,012 points) and robust Student-t linear regression at sizes from $10^4$ to the largest available. At each size we run chains to stationarity, record the mean $n$ per step, and fit the log-log slope. The theory predicts a slope near 1 without the control variate and near 1/2 with it. We will also compare the fitted intercept against $4f_0\kappa\sqrt{2\log(1/\delta)}$, with $f_0$ and $\kappa$ estimated from the chain. A slope near 1 even with the control variate would falsify the central claim.

A second check sweeps $\delta$ from $10^{-2}$ to $10^{-8}$. Cost should grow like $\sqrt{\log(1/\delta)}$, while total-variation error against a long full-data chain should fall in line with the bias bound.

The method comparison then reports effective samples per second, mean subsample size, and Kolmogorov–Smirnov error on four problems. These are HEPMASS logistic regression, where MH-SS is strongest; robust linear regression up to $n = 200{,}000$, where exact methods need Lipschitz bounds; Bardenet's $10^7$-point 2D lognormal problem, a stress test for skewed per-point contributions; and the 20-dimensional truncated Gaussian mixture, a multimodal target on which single-mode Taylor expansions fail. We also vary model dimension on synthetic logistic regression, to measure how $\kappa$ grows with $d$. That is the main unknown, and it will show whether the square-root regime survives beyond a few dozen parameters.