REVIEW 3 major objections 4 minor 33 references
Mini-batch Metropolis-Hastings MCMC with Reversible SGLD Proposal
T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read A mini-batch Metropolis-Hastings sampler yields an approximately tempered stationary distribution while provably preserving the target's well-separated modes.
desk verdict Genuinely useful tempered mini-batch MH framework with solid stationary-distribution analysis, but the RSGLD acceptance-probability proof rests on an implausible gradient-noise assumption. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the augmented target $\tilde{\pi}(\theta,\tau) \propto e^{c_n \hat{\mu}_{I(\tau)}(\theta)} \nu_{m,n}(\tau)$, where $\tau$ selects a uniform mini-batch of size $m$; the marginal identity $\tilde{\pi}(\theta) \propto \pi(\theta)^{1/T} \mathbb{E}_I[e^{c_n(\hat{\mu}_I(\theta)-\mu(\theta))}]$ is what turns a computational shortcut into a characterized tempered target. The second engine is the RSGLD proposal $q_I(\theta\to\theta') = \tfrac12 \phi(\theta'-\theta-\epsilon\hat{g}_I(\theta); \tfrac{2\epsilon}{n^2}I_d) + \tfrac12 \phi(\theta'-\theta+\epsilon\hat{g}_I(\theta); \tfrac{2\epsilon\beta^2}{n^2}I_d)$, whose asymmetric backward noise is responsible for proposal ratios above 1 in strong-gradient regions and near 1 in flat regions. The theorems are carried by uniform concentration inequalities for the log-likelihood and a U-statistic bound on the bias factor.
What would settle it
At a fixed parameter value $\theta$ during training, draw many independent mini-batches of the same size and measure the ratio $\lVert\hat{g}_J(\theta)-\hat{g}_I(\theta)\rVert_2 / \lVert\hat{g}_I(\theta)\rVert_2$ for decreasing learning rates $\epsilon$. If the typical ratio stays near $1/\sqrt{m}$ instead of shrinking linearly with $\epsilon$, Assumption 6 fails and the stated acceptance-probability analysis does not apply.
Extended reading notes
Core claim
At the center of the paper is the observation that substituting a mini-batch into the Metropolis ratio is not an uncontrolled approximation. Treating the batch index $\tau$ as an auxiliary variable and running MH on the augmented pair $(\theta,\tau)$ gives a reversible chain with target $\tilde{\pi}(\theta,\tau) \propto e^{c_n \hat{\mu}_{I(\tau)}(\theta)} \nu_{m,n}(\tau)$, and marginalizing over $\tau$ yields $\tilde{\pi}(\theta) \propto \pi(\theta)^{1/T} \mathbb{E}_I[e^{c_n(\hat{\mu}_I(\theta)-\mu(\theta))}]$, with $T = n/c_n$. Theorem 1 proves that with high probability the bias factor is uniformly close to 1 on a compact set, so the mini-batch stationary distribution has a local maximum in a shrinking neighborhood of every well-separated local mode of the population log-likelihood; Theorem 2 bounds the KL divergence between $\tilde{\pi}$ and the tempered posterior $\pi^{1/T}$. On the proposal side, RSGLD flips a coin between $\theta + \epsilon \hat{g}_I(\theta) + \sqrt{2\epsilon/n}\,Z$ and $\theta - \epsilon \hat{g}_I(\theta) + \sqrt{2\epsilon/n}\,\beta Z$. Proposition 1 shows the forward move has proposal ratio above 1 where gradients dominate the noise, the backward move is rejected with high probability, and flat regions behave like random walks. The experiments indicate the tempered chain travels between separated mixture modes and, on MNIST and CIFAR-10, trains networks with better test accuracy and greater stability at large learning rates than SGD or SGLD.
Load-bearing premise
The load-bearing premise is Assumption 6 (Section 2.3, Equation (9)): for every parameter value, any two mini-batches must give gradients that differ by no more than $O(\epsilon)$ times the gradient size, so mini-batch disagreement vanishes with the learning rate. With independently drawn batches the disagreement is typically $O_p(1/\sqrt{m})$ and does not shrink with $\epsilon$, so if that is the right description of real batches, Proposition 1's guarantee of reasonable acceptance probabilities is not established.
Editorial extensions
If this is right
- A user can run Metropolis-Hastings on data too large for full likelihood evaluations and still know the invariant distribution: a tempered posterior with controlled bias, rather than an unknown perturbed target.
- Because the stationary distribution provably retains well-separated modes of the original posterior, sampling can hop between modes and still land near the true posterior's optima, which is useful for global optimization.
- The RSGLD proposal removes the main obstacle to MH-corrected stochastic-gradient sampling: acceptance probabilities need no longer force the learning rate to shrink like $d^{-1/4}n^{-1}$ when gradients are informative and batches agree closely.
- In flat regions of the loss surface the proposal reduces to a random walk, so the sampler keeps exploring even where gradients vanish.
- The reported neural-network results imply that at large learning rates, where SGD and SGLD frequently diverge, an MH-corrected stochastic-gradient sampler stays stable and often reaches lower test error.
Reading between the lines
- An extension the paper leaves implicit: if Assumption 6 is violated, as happens when random batches disagree by about $1/\sqrt{m}$ rather than by $O(\epsilon)$, the stationary distribution may still look tempered empirically, but the KL bound and acceptance guarantee would need re-derivation; one check is to compare MHBT samples directly with $\pi^{1/T}$ while recording batch-gradient disagreement
- The consistently rejected backward move suggests RSGLD is best viewed as an annealed descent sampler with occasional corrective rejection, rather than as a symmetric reversible sampler; an ablation that disables the backward direction would show how much of the accuracy gain comes from the reversal itself.
- Because $T = n/c_n$ is explicit, the method gives a constructive temperature knob: users could schedule $c_n$ during training to anneal, tuning the amount of tempering for global optimization.
- The verification of Assumptions 1 and 2 for exponential-family mixtures, linear regression, and fully connected networks with bounded spectral norms suggests the same mini-batch tempering mechanism is portable to other smooth likelihood classes, including convolutional architectures, whenever similar concentration bounds hold.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes MHBT (mini-batch Metropolis-Hastings with batch tempering), an MH algorithm that replaces the full-data log-likelihood ratio with a ratio based on two random mini-batches. By augmenting the state with the batch indicator τ, the authors show that the chain has an invariant distribution \tildeπ(θ,τ) ∝ e^{c_n \hat μ_{I(τ)}(θ)} ν(τ); marginalizing over τ gives \tildeπ(θ) proportional to the tempered posterior π(θ)^{1/T} times a bias factor. Theorem 1 states that, with high probability, \tildeπ preserves well-separated local modes of the population log-likelihood, and Theorem 2 bounds the KL divergence between \tildeπ and the tempered posterior. For high-dimensional problems, the paper introduces RSGLD, a proposal that randomly moves in the positive or negative mini-batch gradient direction with different Gaussian noise scales, and Proposition 1 claims that this proposal yields favorable proposal ratios. Experiments on low-dimensional models and on MNIST and CIFAR-10 neural-network training compare MHBT/RSGLD with SGD and SGLD.
Significance. If the main results hold, the paper makes a useful contribution: the augmented-variable construction gives a clean derivation of a mini-batch MH algorithm whose stationary distribution is an approximate tempered posterior, avoiding the unbiased-estimator requirements of pseudo-marginal methods. The mode-preservation and KL-bound theorems are nontrivial and the proofs in Appendix A are detailed. The RSGLD proposal is a plausible way to make stochastic-gradient proposals amenable to MH correction. However, the acceptance-probability guarantee for RSGLD rests on Assumption 6, which is not satisfied by ordinary random mini-batching in the regime where the algorithm is used; until this is fixed, the paper's high-dimensional proposal claim is not established. The MHBT analysis itself appears largely sound and could stand as a contribution on its own.
major comments (3)
- [Section 2.3, Eq. (9) and Proposition 1] Assumption 6 is load-bearing for the RSGLD acceptance-probability analysis and is not a mild regularity condition. For random mini-batches of size m, the typical difference between two independent batch gradients is of order σ_θ sqrt(1/m - 1/n), which is independent of the learning rate ε; Assumption 6 requires this difference to be O(ε ||g_I(θ)||_2). The assumption is not derived from Assumptions 1-5, and it is used essentially in Eqs. (42)-(46) of Appendix D to control g_J(θ') - g_I(θ). Consequently, Proposition 1's conclusions about forward and backward acceptance behavior are not established for the algorithm as implemented in the neural-network experiments. Please replace Assumption 6 with a condition that is compatible with random mini-batching (for example, a high-probability bound with the correct √m scaling) or explicitly restrict the proposition to a different proposal construction.
- [Section 2.3, Proposition 1, Case 2] The flat-region analysis assumes ||g_I(θ)||_2 = 0. Under Assumption 6 this forces g_J(θ) = 0 for every batch J, because the right-hand side of Eq. (9) is then exactly zero. This is not true at a generic point where a single mini-batch gradient vanishes, so the Case 2 statement rests on an internally fragile premise. The case should be reformulated for small gradients with explicit relative error rates rather than exact zeros.
- [Appendix A, proof of Theorem 1, inequality (26)] The proof states that Assumption 3 implies μ_{θ0} - μ_θ ≥ ε0 ||θ - θ0||_2 on a neighborhood of a stationary point. This is false: at a stationary point with negative definite Hessian, the decrease is quadratic in ||θ - θ0||_2. The subsequent proof uses δ_n^2 (e.g., the term ε0 δ_n^2 in Eq. (30)), so the intended inequality is presumably μ_{θ0} - μ_θ ≥ ε0 ||θ - θ0||_2^2. As written, the proof of Theorem 1 is not valid; please correct the statement of the inequality and the surrounding argument.
minor comments (4)
- [Appendix A, proof of Theorem 2] The proof begins with 'Further suppose Assumption 5 holds', but Theorem 2 is stated under Assumptions 1, 2, and 4, and Assumption 5 is not used in the KL argument. This appears to be a typo.
- [Algorithm 1] Algorithm 1 lists only the likelihood ratio in the acceptance probability; the uniform-prior assumption from footnote 1 should be stated in the algorithm caption, and the extension to general priors should be made explicit.
- [Section 2.2, Theorem 2] The notation π_T is used in Theorem 2 before it is defined; please define π_T(θ) ∝ π(θ)^{1/T} immediately before the theorem statement.
- [Figure 1(a)] The text describes the largest learning rate achieving average acceptance probability at least 0.5 and 0.1, but the figure caption does not indicate which curve corresponds to which threshold; please clarify.
Circularity Check
No significant circularity: the tempered stationary distribution follows explicitly from the constructed augmented target, and the main theorems are proved from stated assumptions without relying on load-bearing self-citation.
full rationale
The paper's central derivation is self-contained. The augmented target in Eq. (1), \tilde{\pi}(\theta,\tau) \propto e^{c_n \hat{\mu}_{I(\tau)}(\theta)} \nu_{m,n}(\tau), is defined directly, and marginalizing over \tau yields Eq. (3), which is exactly a tempered posterior times the bias factor involving the average of e^{c_n(\hat{\mu}_I(\theta)-\mu(\theta))}. The paper does not hide this algebraic identity: it says 'in this sense, the mini-batch stationary distribution is approximately a tempered version of the posterior, up to a bias term.' The genuinely substantive claims—mode preservation in Theorem 1 and KL closeness to the tempered posterior in Theorem 2—are proved from Assumptions 1-4 through Lemmas 3-4, and those proofs are given in Appendix A. The RSGLD acceptance-probability analysis in Proposition 1 is also derived from explicit assumptions (Assumptions 5 and 6) with a detailed proof in Appendix D; it is not obtained by renaming a fitted quantity or by importing a conclusion from a cited source. The self-citations in the paper, such as [18], are used only to acknowledge and contrast related prior work, not as the foundation for the new theorems. The main weakness, Assumption 6, is that mini-batch gradient disagreement is assumed to be O(\epsilon) in the learning rate; for random mini-batches this may be unrealistic, and if it fails the Proposition 1 conclusions are unsupported. That is a correctness and robustness concern, not a circularity: the claimed result does not reduce to its input by definition, by a fitted parameter renamed as a prediction, or by a self-citation chain.
Assumptions & free parameters
free parameters (5)
- temperature scaling constant c_n =
20 in low-dimensional experiments; 100 for MNIST and CIFAR-10 (also tested 50 and 200)
- mini-batch size m =
1000 in low-dimensional experiments; 100 in neural-network experiments
- proposal learning rate epsilon =
Grid searched from 0.01 to 0.6 for MNIST and 0.005 to 0.04 for CIFAR-10
- backward-move noise scale beta =
Started large, decreased by 5% when acceptance exceeded 0.7, increased by 5% when below 0.2; stabilized near 1
- random-walk step size delta =
Chosen so average acceptance probability is around 0.3 in low-dimensional experiments
assumptions (8)
- domain assumption Assumption 1: log likelihood is Lipschitz in a transform T(x) with exponential moments
- domain assumption Assumption 2: log likelihood is Lipschitz in theta with exponentially integrable constant M(X)
- domain assumption Assumption 3: population log likelihood is twice continuously differentiable with a well-separated local optimum
- domain assumption Assumption 4: the parameter space Theta is compact
- domain assumption Assumption 5: Hessians of mini-batch gradients have uniformly bounded operator norm
- ad hoc to paper Assumption 6: all batches give gradients that differ by O(epsilon ||g_I(theta)||_2)
- domain assumption Assumption 9: activation functions are bounded and Lipschitz, and the product of network weight operator norms is bounded
- standard math U-statistic concentration and Chernoff-type inequalities
Cite this review
Pith. "Pith review of Mini-batch Metropolis-Hastings MCMC with Reversible SGLD Proposal." pith.science (2026). https://pith.science/paper/EL3HN7BW
@misc{pith2026190802910,
author = {Pith},
title = {Pith review of: Mini-batch Metropolis-Hastings MCMC with Reversible SGLD Proposal},
year = {2026},
howpublished = {\url{https://pith.science/paper/EL3HN7BW}},
note = {Machine review of arXiv:1908.02910}
}
read the original abstract
Traditional MCMC algorithms are computationally intensive and do not scale well to large data. In particular, the Metropolis-Hastings (MH) algorithm requires passing over the entire dataset to evaluate the likelihood ratio in each iteration. We propose a general framework for performing MH-MCMC using mini-batches of the whole dataset and show that this gives rise to approximately a tempered stationary distribution. We prove that the algorithm preserves the modes of the original target distribution and derive an error bound on the approximation with mild assumptions on the likelihood. To further extend the utility of the algorithm to high dimensional settings, we construct a proposal with forward and reverse moves using stochastic gradient and show that the construction leads to reasonable acceptance probabilities. We demonstrate the performance of our algorithm in both low dimensional models and high dimensional neural network applications. Particularly in the latter case, compared to popular optimization methods, our method is more robust to the choice of learning rate and improves testing accuracy.
Figures
Reference graph
Works this paper leans on
-
[1]
Distributed delayed stochastic optimization
Alekh Agarwal and John C Duchi. Distributed delayed stochastic optimization. In Advances in Neural Information Processing Systems , pages 873–881, 2011. 29
work page 2011
-
[2]
Bayesian posterior sampling via stochastic gradient Fisher scoring
Sungjin Ahn, Anoop Korattikara, and Max Welling. Bayesian posterior sampling via stochastic gradient Fisher scoring. arXiv preprint arXiv:1206.6380 , 2012
arXiv 2012
-
[3]
The pseudo-marginal approach for efficient monte carlo computations
Christophe Andrieu, Gareth O Roberts, et al. The pseudo-marginal approach for efficient monte carlo computations. The Annals of Statistics , 37(2):697–725, 2009
work page 2009
-
[4]
Towards scaling up Markov chain Monte Carlo: an adaptive subsampling approach
R´ emi Bardenet, Arnaud Doucet, and Chris Holmes. Towards scaling up Markov chain Monte Carlo: an adaptive subsampling approach. In Proceedings of the 31st International Conference on Machine Learning (ICML-14) , pages 405–413, 2014
work page 2014
-
[5]
On Markov chain Monte Carlo methods for tall data
R´ emi Bardenet, Arnaud Doucet, and Chris Holmes. On Markov chain Monte Carlo methods for tall data. arXiv preprint arXiv:1505.02827 , 2015
arXiv 2015
-
[6]
Spectrally-normalized margin bounds for neural networks
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normalized margin bounds for neural networks. In Advances in Neural Information Processing Systems , pages 6240–6249, 2017
work page 2017
-
[7]
The zig-zag process and super- efficient sampling for bayesian analysis of big data
Joris Bierkens, Paul Fearnhead, Gareth Roberts, et al. The zig-zag process and super- efficient sampling for bayesian analysis of big data. The Annals of Statistics , 47(3):1288– 1320, 2019
work page 2019
-
[8]
Variational inference: A review for statisticians
David M Blei, Alp Kucukelbir, and Jon D McAuliffe. Variational inference: A review for statisticians. Journal of the American Statistical Association , (just-accepted), 2017
work page 2017
Show all 33 references
-
[9]
An efficient minibatch acceptance test for Metropolis-Hastings
Haoyu Chen, Daniel Seita, Xinlei Pan, and John Canny. An efficient minibatch acceptance test for Metropolis-Hastings. arXiv preprint arXiv:1610.06848 , 2016
2016 arXiv
-
[10]
Stochastic gradient hamiltonian monte carlo
Tianqi Chen, Emily Fox, and Carlos Guestrin. Stochastic gradient hamiltonian monte carlo. In International Conference on Machine Learning , pages 1683–1691, 2014
2014
-
[11]
Minibatch gibbs sampling on large graphical models
Christopher De Sa, Vincent Chen, and Wing Wong. Minibatch gibbs sampling on large graphical models. arXiv preprint arXiv:1806.06086 , 2018
2018 arXiv
-
[12]
An instability in variational inference for topic models
Behrooz Ghorbani, Hamid Javadi, and Andrea Montanari. An instability in variational inference for topic models. arXiv preprint arXiv:1802.00568 , 2018
2018 arXiv
-
[13]
On nonnegative unbiased estimators
Pierre E Jacob and Alexandre H Thiery. On nonnegative unbiased estimators. The Annals of Statistics , 43(2):769–784, 2015
2015
-
[14]
Adam: A method for stochastic optimization
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014
2014 arXiv
-
[15]
Austerity in MCMC land: Cutting the Metropolis-Hastings budget
Anoop Korattikara, Yutian Chen, and Max Welling. Austerity in MCMC land: Cutting the Metropolis-Hastings budget. In Proceedings of the 31st International Conference on Machine Learning (ICML-14), pages 181–189, 2014
2014
-
[16]
Learning multiple layers of features from tiny images
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009. 30
2009
-
[17]
Preconditioned stochastic gradient langevin dynamics for deep neural networks
Chunyuan Li, Changyou Chen, David E Carlson, and Lawrence Carin. Preconditioned stochastic gradient langevin dynamics for deep neural networks. In AAAI, volume 2, page 4, 2016
2016
-
[18]
Mini-batch tempered mcmc
Dangna Li and Wing H Wong. Mini-batch tempered mcmc. arXiv preprint arXiv:1707.09705, 2017
2017 arXiv
-
[19]
Firefly Monte Carlo: Exact MCMC with subsets of data
Dougal Maclaurin and Ryan P Adams. Firefly Monte Carlo: Exact MCMC with subsets of data. In UAI, pages 543–552, 2014
2014
-
[20]
Mean field for the stochastic blockmodel: Optimization landscape and convergence issues
Soumendu Sundar Mukherjee, Purnamrita Sarkar, YX Rachel Wang, and Bowei Yan. Mean field for the stochastic blockmodel: Optimization landscape and convergence issues. In Advances in Neural Information Processing Systems , pages 10717–10727, 2018
2018
-
[21]
Mcmc using hamiltonian dynamics
Radford M Neal et al. Mcmc using hamiltonian dynamics. Handbook of markov chain monte carlo, 2(11):2, 2011
2011
-
[22]
Asymptotically exact, embarrassingly parallel mcmc
Willie Neiswanger, Chong Wang, and Eric Xing. Asymptotically exact, embarrassingly parallel mcmc. In UAI, 2013
2013
-
[23]
Speeding up mcmc by efficient data subsampling
Matias Quiroz, Robert Kohn, Mattias Villani, and Minh-Ngoc Tran. Speeding up mcmc by efficient data subsampling. Journal of the American Statistical Association , pages 1–13, 2018
2018
-
[24]
Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis. arXiv preprint arXiv:1702.03849, 2017
2017 arXiv
-
[25]
A stochastic approximation method
Herbert Robbins and Sutton Monro. A stochastic approximation method. In Herbert Robbins Selected Papers, pages 102–109. Springer, 1985
1985
-
[26]
Exponential convergence of langevin distributions and their discrete approximations
Gareth O Roberts, Richard L Tweedie, et al. Exponential convergence of langevin distributions and their discrete approximations. Bernoulli, 2(4):341–363, 1996
1996
-
[27]
Bayes and big data: The consensus monte carlo algorithm
Steven L Scott, Alexander W Blocker, Fernando V Bonassi, Hugh A Chipman, Edward I George, and Robert E McCulloch. Bayes and big data: The consensus monte carlo algorithm. International Journal of Management Science and Engineering Management , 11(2):78–88, 2016
2016
-
[28]
Consistency and fluctua- tions for stochastic gradient langevin dynamics
Yee Whye Teh, Alexandre H Thiery, and Sebastian J Vollmer. Consistency and fluctua- tions for stochastic gradient langevin dynamics. Journal of Machine Learning Research , 17:1–33, 2016
2016
-
[29]
Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26–31, 2012
2012
-
[30]
Parallelizing mcmc via weierstrass sampler
Xiangyu Wang and David B Dunson. Parallelizing mcmc via weierstrass sampler. arXiv preprint arXiv:1312.4605, 2013. 31
2013 arXiv
-
[31]
Bayesian learning via stochastic gradient Langevin dynamics
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient Langevin dynamics. In Proceedings of the 28th International Conference on Machine Learning (ICML-11), pages 681–688, 2011
2011
-
[32]
A walk with sgd
Chen Xing, Devansh Arpit, Christos Tsirigotis, and Yoshua Bengio. A walk with sgd. arXiv preprint arXiv:1802.08770 , 2018
2018 arXiv
-
[33]
Langevin dynamics with continuous tempering for training deep neural networks
Nanyang Ye, Zhanxing Zhu, and Rafal K Mantiuk. Langevin dynamics with continuous tempering for training deep neural networks. arXiv preprint arXiv:1703.04379 , 2017. 32
2017 arXiv
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.