Markov Chain Monte Carlo without Evaluating the Target: an Auxiliary Variable Approach

Summary

The paper proposes a unifying auxiliary-variable framework for MCMC algorithms that sample without directly evaluating the unnormalized target. The authors first observe that three seemingly disparate methods — the exchange algorithm (doubly-intractable posteriors), PoissonMH, and TunaMH (tall data) — are instances of a single auxiliary-variable Metropolis–Hastings construction. Building on this, they introduce a meta-algorithm (Algorithm 1) in which one auxiliary variable $\omega_1$ shapes the proposal and a second variable $\omega_2$ estimates the target ratio, with validity established through detailed balance and an involutive-MCMC reinterpretation. From this they derive gradient-informed minibatch samplers: Locally Balanced PoissonMH (Poisson–Barker, Poisson–MALA) and Tuna–SGLD, which pairs an SGLD proposal with a TunaMH-style Poisson-minibatch acceptance step. The conceptual move — combining a cheap proposal and a cheap acceptance test that had been developed separately — is clean and well motivated. Theoretically, a sharpened Bretagnolle–Huber inequality lets the authors compare the auxiliary chain to an idealized Metropolis-within-Gibbs chain and tighten the spectral-gap constants of PoissonMH and TunaMH in some regimes. Empirically, on a truncated Gaussian, robust linear regression, and MNIST logistic regression, the new samplers report large ESS/s gains, and a KS-based check argues they still target the correct distribution. Executed replication confirms the central speed/ranking story: the Poisson methods are consistently the top exact samplers and beat full-batch baselines on ESS/s and MSE-per-second, SGLD shows the expected biased plateau, and the reported minibatch fraction reproduces. The chief limitations are conceptual and evidential: the framework sits close to its acknowledged antecedents (identity-involution special case of Andrieu et al. 2018a; Case 2 $\approx$ Titsias & Papaspiliopoulos 2018), inherits PoissonMH/TunaMH's restrictive bounded/i.i.d. assumptions, and the theory does not quantitatively predict the observed 10–100x speedups. Several headline phrasings ("strictly sharper", "100x over full-batch", resolving SGLD's open problem) overstate what is shown, and the exactness evidence is concentrated in a single, heavily tempered, Gaussian example.

Strengths

• Unifying view. Recognizing that the exchange algorithm, PoissonMH, and TunaMH are one auxiliary-variable procedure gives a genuinely useful lens on a fragmented literature, and the involutive-MCMC reinterpretation supplies a clean validity argument.
• Well-motivated new algorithms. Poisson–Barker, Poisson–MALA, and Tuna–SGLD target a real gap — earlier exact minibatch methods used only random-walk proposals, while gradient samplers (MALA, HMC) needed full-batch gradients — and combine cheap gradient-informed proposals with exact minibatch acceptance.
• Sharpened analyses of existing methods. Propositions 4 and 5 give explicit constant improvements over Zhang & De Sa (2019) and Zhang et al. (2020), exposing the role of the Bretagnolle–Huber inequality via Theorem 1.
• Reproducible speed/ranking story. Executed replication of the truncated-Gaussian experiment confirmed the top-two ranking of Poisson–Barker/Poisson–MALA in all nine rate-by-metric cases, the fold-improvements over baselines, the SGLD biased plateau, and the ~6% minibatch fraction, increasing confidence in the empirical thesis.
• Honest limitations section. Section 6 candidly flags reliance on precomputed bounds, the i.i.d. requirement, and the unexplained magnitude of minibatch speedups.

Weaknesses

• Framework novelty is over-signalled. The abstract advertises the unification as a headline contribution, while Section 2 concedes it is the identity-involution special case of Andrieu et al. (2018a) and Case 2 reproduces Titsias & Papaspiliopoulos (2018). The novel elements (tall-data connection, Algorithms 2/3, sharper analyses) should be delineated upstream.
• Overclaimed "open problem" resolution. The introduction frames Tuna–SGLD as resolving SGLD-bias correction in general, but correctness holds only within TunaMH's assumption regime (bounded per-datum energy differences, precomputed $c_i, C, \chi$, i.i.d. data, symmetric $M(\theta,\theta')$).
• "Strictly sharper" TunaMH bound is regime-limited. The new rate dominates Zhang et al.'s only for $\chi$ below a threshold (roughly 23); the practical $\chi = 10^{-5}$ is fine, but "strictly" is an over-claim.
• "100x over full-batch" holds only against the weakest baseline. From Table 2, Poisson–Barker is ~53x MALA, not ~100x; only against HMC-10 do both methods exceed 100x. The baseline should be named.
• Heavily tempered targets. Both synthetic experiments use extreme tempering ($\beta = 10^{-5}$ and $10^{-4}$), flattening the posterior in a way that may systematically favor the proposed samplers; robustness at $\beta$ closer to 1 is not shown.
• Correctness checked only in the easiest setting. The KS check runs solely on the unimodal, light-tailed 20-d Gaussian; the heavier-tailed robust-regression and MNIST posteriors — where a subtle minibatch bias would be hardest to detect — are not checked for exactness.
• No uncertainty on ESS/s and implementation-dependence. Tables give point (Min, Median, Max) with no standard errors despite 100 runs, so near-ties (e.g. Poisson–MALA vs Poisson–Barker) are unadjudicable; and ESS/s conflates mixing with implementation quality (the replication saw absolute ESS/s ~1.7–2.5x the paper's on faster hardware).
• Unanalyzed acceptance cost for Tuna–SGLD. Since $M(\theta,\theta') = \|\theta'-\theta\|_2$, the expected acceptance-minibatch size $\lambda + C\,M(\theta,\theta')$ grows with the SGLD step size, in tension with the low-per-step-cost goal; this trade-off is not studied.
• Missing modern baselines. Comparisons exclude gradient-based minibatch competitors (SGLD-CV) and control-variate exact minibatch MH (Cornish et al., 2019), weakening "significantly outperform existing methods".
• Peskun ordering is a caveat, not a strength. Lemma 1 places the practical chain $\mathrm{P}_{\mathrm{aux}}$ below the analytic chains, so its asymptotic variance is at least that of the idealized chain; this pessimistic direction should be flagged.
• Notation/cross-reference issues. Appendix E/F.3 cite "Algorithm 3" for the TunaMH (Algorithm 6) step; the PoissonMH promise $\phi_i \in [0,M_i]$ conflicts with the $\phi_i$ prescribed in Appendix A (missing upper-bound shift); the $\mathrm{P}_{\theta'\to\theta}$ subscript in the Andrieu comparison, the undefined $\mathbb{P}_{p_{\theta'}}$ in Proposition 3, the $[0,1]$-codomain balancing $a$ in Proposition 10, and the "maximum equals … for both cases" in Appendix F.2 all need tightening.

Reproducibility & code

Code was executed (the shipped Julia repository instantiated cleanly from a pinned Manifest.toml, with only a single benign diagnostic println added). The pipeline itself is high quality; the limiting factor was compute, and the discrepancies below are the honest picture.

• Speed/ranking reproduced. Re-running the shipped ESS/s evaluation on saved truncated-Gaussian trajectories reproduced the top-two ranking of Poisson–Barker/Poisson–MALA in all nine rate-by-metric cases and the fold-improvements over PoissonMH/MALA/Barker/MH; absolute ESS/s were ~1.7–2.5x the paper's, consistent with faster hardware and the wall-clock dependence the paper itself warns about.
• Exactness (KS) not confirmed at scale. The full-scale Gaussian runs were OOM-killed, so KS statistics came only from reduced-length chains; because KS scales like $1/\sqrt{n}$, values inflated ~2–3x (Poisson methods ~0.11–0.16 vs paper 0.05; SGLD ~0.60 vs 0.18) and the "max KS below ~0.05" invariant was not met. The ordering (Poisson methods far below SGLD) still held. This is an environmental limitation, not a paper error, but Table 3 is unverified here.
• Absolute ESS/s tables not exercised. Tables 2, 6, and 7 (robust regression and appendix configs) exceeded the session wall-clock budget and were graded not-attempted; the reduced-scale robust-regression samples nonetheless reproduced the fold-improvement structure.
• MNIST experiments not run. Sections 5.3 and Appendix G.4/G.5 were queued best-effort and never received cores, so the Tuna–SGLD-vs-TunaMH and HMC claims were not checked.
• KS-check burn-in mismatch. eval/ks_gaussian_20d.jl hard-codes absolute per-method burn-ins (e.g. SGLD = 500000) rather than the stated 20% fraction; the replication had to rescale these constants to retain post-burn-in samples.
• Un-seeded run scripts. scripts/run_gaussian_20d.jl and scripts/run_robust_reg.jl set no RNG seed (only the logistic-regression script does), which, with wall-clock ESS/s, makes numeric reproduction machine-dependent.
• HMC-10 vs code default. Table 2 reports HMC-10, but the robust-regression driver defaults to 5 leapfrog steps and labels output "HMC (lf=5)"; a reader must edit the source to reproduce Table 2's HMC row.
• Undocumented pilot tuning and missing plotting scripts. Only final tuned step sizes are hard-coded (pilot iterations/tolerance/cost undocumented), and no aggregation/plotting scripts for Figures 1–4 are shipped.

Recommended Changes

Essential

• Qualify the "strictly sharper" TunaMH claim. State the explicit $\chi$ range in which the new rate dominates Zhang et al.'s, and note the practical $\chi = 10^{-5}$ lies inside it.
• Name the baseline behind "100x over full-batch." Report Poisson–Barker and Poisson–MALA speedups separately against the strongest (MALA) and weakest (HMC-10) full-batch methods.
• Scope the SGLD "open problem" framing. Add a clause in the introduction stating Algorithm 3 solves the correction within TunaMH's assumption regime, matching Section 6.
• Signpost prior work upstream. In the abstract/introduction, state that the meta-procedure is the identity-involution special case of Andrieu et al. (2018a) and that Case 2 corresponds to Titsias & Papaspiliopoulos (2018), so the novel elements are clear.
• Broaden the correctness evidence. Add a KS (or equivalent) check on at least one non-Gaussian target (robust regression and/or MNIST), since exactness is currently demonstrated only on the tempered Gaussian.
• Justify or vary the temperature. Report whether the ESS/s advantages persist at $\beta$ closer to 1, or explain why $\beta = 10^{-5}/10^{-4}$ is the relevant regime.
• Add a derivation of the "proxy depends only on $S$" identity in the main text (or an explicit pointer to the PoissonMH cancellation), since it underpins Algorithm 2's per-step cost.

Essential (reproducibility)

• Align the KS-check burn-in with the paper. Replace the absolute BURNINS constants in eval/ks_gaussian_20d.jl with a 0.2 * n_iter fraction, or document the actual per-method counts in Section 5.4.
• Seed the run scripts. Add Random.seed!(args.seed) to scripts/run_gaussian_20d.jl and scripts/run_robust_reg.jl.
• Fix the HMC-10 mismatch. Expose a --lf_steps flag defaulting to 10 for the robust-regression HMC, or document the required edit.
• Ship plotting scripts and document pilot tuning. Add a plots/ directory reproducing Figures 1–4 and describe the pilot protocol (iterations, tolerance, whether pilot cost enters ESS/s).

Suggested

• Report ESS/s uncertainty. Add standard errors or inter-quartile ranges to the ESS/s tables so near-ties can be assessed.
• Add a modern minibatch baseline (SGLD-CV and/or Cornish et al., 2019) to substantiate "significantly outperform existing methods".
• Analyze the Tuna–SGLD acceptance cost as a function of step size, given $M(\theta,\theta') = \|\theta'-\theta\|_2$.
• Flag the 100- vs 10-run difference between the main tables and Figure 5 / Table 7.
• Add a caveat in Section 4.1 that Lemma 1 places the practical chain below the idealized chains in Peskun order.
• Fix the cross-references and notation. Correct "Algorithm 3" to Algorithm 6 in Appendix E/F.3; state the upper-bound shift making $\phi_i \in [0,M_i]$ in Appendix A; define $\mathbb{P}_{p_{\theta'}}$ in Proposition 3; distinguish the $[0,1]$-valued $a$ in Proposition 10 from the balancing $g$; align the $\mathrm{P}$ subscript in the Andrieu comparison; and reword "The maximum equals … for both cases" as "an upper bound is …".