{"id":"f7541a9f-0fd8-4985-9e4b-d976094f024f","arxiv_id":"1908.02910","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A mini-batch Metropolis-Hastings algorithm has an approximately tempered stationary distribution, provably preserves posterior modes, and pairs with a reversible stochastic-gradient proposal for high-dimensional neural network training.","lead":"The authors propose a Metropolis-Hastings sampling algorithm that evaluates only a small random batch of data at each step, so it scales to large datasets. The resulting sampler targets an approximately tempered posterior, preserves the modes of the original target, and is paired with a reversible stochastic-gradient proposal for neural-network training.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Assumption 6 (Eq. 9) is the load-bearing premise for the RSGLD acceptance-probability guarantee, and for random mini-batches it is typically violated because gradient noise does not shrink with ε; Proposition 1's forward/backward ratio conclusions are therefore not established.","rationale":"The reader and I converge on the same load-bearing weakness. The stationary-distribution and mode-preservation half of the paper (Theorems 1-2) is supported by a coherent concentration argument, and I see no internal contradiction there. The RSGLD acceptance-probability half, however, rests on Assumption 6, which is not a consequence of the earlier assumptions and is contradicted by elementary statistics of random mini-batches: for iid data the batch-gradient discrepancy is O_p(1/sqrt(m)) and does not vanish with ε. Because the proof of Proposition 1 explicitly uses Assumption 6 to expand g_J(θ') around g_I(θ) in Eqs. (42)-(45), the claimed lower bound on acceptance probability lacks support in realistic settings. This warrants a conditional rather than a full accept; it does not warrant rejection, since the theoretical results on tempered stationarity appear sound and the empirical claims, while not code-verified, are plausible. I therefore recommend keeping the reader's CONDITIONAL verdict unchanged.","tokens_in":23638,"tokens_out":9153,"duration_ms":103184,"concrete_test":"On the MNIST network of §3.2 (or a d-dimensional Gaussian model), fix a trained parameter θ with nonzero gradient, choose ε = 0.1 and m = 100, and draw 200 independent pairs of mini-batches. Compute R = ||g_J(θ) - g_I(θ)||_2 / (ε ||g_I(θ)||_2); if the median R exceeds a constant (e.g., > 1), Assumption 6 is violated in exactly the regime used by Proposition 1. Then simulate RSGLD forward and backward moves from θ and compute the exact proposal ratio in Eq. (37) with the sampled batches, and compare whether forward ratios exceed 1 and backward ratios are near 0 as predicted. If the empirical ratios disagree with the two cases of Proposition 1, the acceptance guarantee does not hold for the implemented algorithm.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 1's conclusion that RSGLD maintains reasonable acceptance probabilities depends on Eqs. (42)-(46) through Assumption 6: for every θ and any two batches I and J, ||g_J(θ)-g_I(θ)||_2 = O(ε ||g_I(θ)||_2). With I and J drawn uniformly from all m-subsets, the typical difference between two mini-batch gradients is of order σ_θ sqrt(1/m - 1/n), independent of the learning rate ε, so the assumption holds only in the exceptional regime where signal dominates noise by a factor of order 1/ε. It is not a mild regularity condition, and it is not derived from Assumptions 1-5. The assumption is also internally fragile: in Case 2, where ||g_I(θ)|| = 0, it forces every batch to have exactly zero gradient at θ, which is not true at a generic point reached by the sampler. Since the proof of Proposition 1 explicitly uses this assumption to expand g_J(θ') around g_I(θ), the claimed forward ratio > 1 and backward ratio = o_P(1) are unsupported when Assumption 6 fails. Theorems 1-2 on the tempered stationary distribution are separate and appear internally consistent; the gap is specific to the RSGLD acceptance-probability analysis.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":23950,"tokens_out":17373,"duration_ms":176567,"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":[{"comment":"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":"Section 2.3, Eq. (9) and Proposition 1"},{"comment":"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.","section":"Section 2.3, Proposition 1, Case 2"},{"comment":"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.","section":"Appendix A, proof of Theorem 1, inequality (26)"}],"minor_comments":[{"comment":"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.","section":"Appendix A, proof of Theorem 2"},{"comment":"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":"Algorithm 1"},{"comment":"The notation π_T is used in Theorem 2 before it is defined; please define π_T(θ) ∝ π(θ)^{1/T} immediately before the theorem statement.","section":"Section 2.2, Theorem 2"},{"comment":"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.","section":"Figure 1(a)"}],"recommendation":"major_revision","confidential_remarks":"The RSGLD acceptance-probability analysis is the main obstacle. If Assumption 6 can be replaced with a realistic mini-batch concentration condition, or if Proposition 1 is narrowed to a setting where the assumption is actually satisfied, the paper would be publishable; the MHBT theory alone is a solid contribution. I would not require new experiments, but the theoretical claim in the abstract about 'reasonable acceptance probabilities' must be repaired."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Both the reader and the stress-test note are on target. The genuinely new content is the augmented-variable construction that turns mini-batch MH into a reversible chain with a tempered stationary distribution. Theorems 1 and 2 on mode preservation and KL closeness to the tempered posterior are proven with real concentration arguments and look internally consistent. That is a solid contribution to scalable MCMC and to using MCMC for optimization.\n\nThe soft spot is exactly where the stress-test puts it: Proposition 1, the claim that RSGLD has reasonable acceptance probabilities, depends on Assumption 6, which says that at every theta any two mini-batch gradients differ by O(epsilon ||g_I||). For random mini-batches, the typical difference is O_p(1/sqrt(m)) and does not shrink with the learning rate. This is not a mild regularity condition; it is a strong signal-dominates-noise condition. The assumption also has an odd consequence: if one batch has zero gradient, all batches must have zero gradient at that theta, which fails at generic points. So the forward/backward ratio conclusions are not established as stated. I agree with the reader that this is the main gap.\n\nThe experiments are useful—the MNIST and CIFAR results suggest the tempering effect helps stability at large learning rates—but without code it is hard to assess how sensitive the method is to the beta-annealing schedule. That is a minor issue compared to Assumption 6.\n\nThe paper deserves a serious referee. The MHBT framework alone is worth publishing, and the RSGLD idea is worth discussing even if the current proof does not hold. A referee should push the authors to either replace Assumption 6 with a realistic condition (e.g., gradient noise of order O_p(1/sqrt(m))) or provide an empirical justification for the regime in which it holds. If that is fixed, this could be a strong paper; as written, the acceptance-probability guarantee should be treated with caution.","headline":"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.","tokens_in":24446,"tokens_out":3344,"would_cite":true,"duration_ms":35847,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62F15","60J22","65C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"A mini-batch Metropolis-Hastings sampler yields an approximately tempered stationary distribution while provably preserving the target's well-separated modes.","keywords":["mini-batch Metropolis-Hastings","tempered posterior","stochastic gradient Langevin dynamics","reversible proposal","mode preservation","neural network training","large-scale MCMC"],"falsifier":"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.","tokens_in":23432,"feed_emoji":"🎲","tokens_out":12590,"duration_ms":130423,"temperature":0.7,"pith_summary":"Metropolis-Hastings forces a full pass over the data at every step, which makes it impractical for large data sets. This paper proposes MHBT, which evaluates the likelihood on a random mini-batch instead, and shows the resulting chain has a known stationary distribution: approximately the posterior raised to temperature $T = n/c_n$, multiplied by a bias factor that shrinks as the data size grows. The paper proves that this invariant distribution is close to the tempered posterior in KL divergence and that, with high probability, it keeps a local maximum near every well-separated mode of the original posterior. For high dimensions it adds the RSGLD proposal, a stochastic-gradient move with forward and backward directions, and proves it can keep Metropolis acceptance probabilities from collapsing when gradient information is strong. If these claims hold, MCMC can serve as a scalable global-optimization tool, and the experiments on Gaussian mixtures and neural networks support that use.","feed_headline":"Mini-batch MH samples a tempered posterior, preserving target modes","feed_subtitle":"A reversible stochastic-gradient proposal keeps MH acceptance high and improves neural-net accuracy at large learning rates.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the pseudo-marginal alternative that this paper contrasts with, motivating the goal of mini-batching MH without unbiased likelihood estimators.","marker":"[3]"},{"why":"Notes the connection between tempering and subsample variance that MHBT formalizes into a theorem.","marker":"[5]"},{"why":"Heuristic mini-batch tempered MCMC sampler using augmented variables that this paper extends with theory.","marker":"[18]"},{"why":"Provides the MALA gradient proposal whose dimension-dependent learning-rate restriction RSGLD seeks to remove.","marker":"[26]"},{"why":"Documents the $d^{-1/4}n^{-1}$ scaling required for acceptance probabilities in Hamiltonian/MALA samplers, the baseline RSGLD is compared against.","marker":"[21]"},{"why":"Introduces SGLD, the base proposal that RSGLD modifies, and supplies the two-component mixture example used in the experiments.","marker":"[31]"},{"why":"Gives the large-learning-rate trajectory perspective used to interpret why stability at large $\\epsilon$ is valuable for deep-network training.","marker":"[32]"}],"fun_headline_variants":["Mini-batch MH preserves modes, samples tempered posterior","Reversible SGLD proposal keeps MH alive in mini-batch setting","Mini-batch MCMC: tempered target, mode preservation","Stochastic-gradient proposal makes mini-batch MH practical"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Mini-batch MH preserves modes, samples tempered posterior","Reversible SGLD proposal keeps MH alive in mini-batch setting","Mini-batch MCMC: tempered target, mode preservation","Stochastic-gradient proposal makes mini-batch MH practical"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000232,"raw_usage":{"total_tokens":1548,"prompt_tokens":1065,"completion_tokens":483,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":681,"completion_tokens_details":{"reasoning_tokens":415}},"tokens_in":681,"tokens_out":483,"duration_ms":5463,"temperature":1.0,"reasoning_tokens":415,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:30:37.397687+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"The pseudo-marginal approach for efficient monte carlo computations","cited_arxiv_id":null,"evidence_quote":"Defines the pseudo-marginal alternative that this paper contrasts with, motivating the goal of mini-batching MH without unbiased likelihood estimators."},{"cited_title":"Exponential convergence of langevin distributions and their discrete approximations","cited_arxiv_id":null,"evidence_quote":"Provides the MALA gradient proposal whose dimension-dependent learning-rate restriction RSGLD seeks to remove."},{"cited_title":"Bayesian learning via stochastic gradient Langevin dynamics","cited_arxiv_id":null,"evidence_quote":"Introduces SGLD, the base proposal that RSGLD modifies, and supplies the two-component mixture example used in the experiments."}],"review_version":1}