{"id":"b14f7a45-7ca3-43df-8ad7-a6ae7362726a","arxiv_id":"2412.01952","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Subsampling in SGLD does not asymptotically reduce the total computation needed for accurate posterior sampling in typical exponential-family models.","lead":"This paper proves lower bounds showing that stochastic gradient Langevin dynamics (SGLD), a subsampling MCMC method, cannot be asymptotically more accurate than full-data Langevin dynamics for a class of exponential-family models. It closes a gap in earlier 'no free lunch' results that applied only to reversible chains, extending the same conclusion to the popular non-reversible SGLD algorithm.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 lower-bounds the sum of errors of two coupled chains targeting different posteriors; it never implies a single SGLD chain is poor, so the abstract's 'any SGLD algorithm will return extremely poor samples' is not entailed.","rationale":"The reader's weakest_assumption identifies Assumption 3, which is a real scope restriction, but it is secondary. For scalar exponential families with monotone R, the upper-half gap in Assumption 3 is actually a very weak condition, since order statistics separate. The larger issue is that the theorem's conclusion is a sum of errors for two different targets, and the abstract overclaims a single-chain no-free-lunch result. Remark 3 is candid about this, but candor does not close the logical gap. The coupling construction and the perturbation lemmas are plausible independent contributions, and I do not see an algebraic error in the proof sketch; the concern is about what the theorem entails. The paper's stated goal is to close the nonreversible gap left by prior work, and the two-chain result may still be a meaningful step, so a conditional acceptance with a required reframing of the abstract is appropriate.","tokens_in":10081,"tokens_out":12671,"duration_ms":350134,"concrete_test":"Use the Gaussian model from Appendix A, choose T_n=0 (permitted by Theorem 1's condition T_n M_n/n→0) and set both chains' starting distribution to p(·|X_n). The theorem's conclusion holds: the second error is ||p-p_ω||≥γ, so the sum lower bound is satisfied, while the SGLD chain's error is exactly 0. This demonstrates that the theorem cannot establish the abstract's single-chain claim. To settle the concern, attempt to derive from the same coupling a lower bound on ||L(Z_T)-p|| for a fixed starting measure independent of the target; if no such bound follows, the headline must be weakened to a two-chain (or average) statement.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing gap is between Theorem 1 and the paper's central claim. Theorem 1 (Section 3.2) proves only that P[||L(Z_T)-p(·|X)||_TV + ||L(˜Z_T)-p_ω(·|X)||_TV ≥ (1-a)γ] → 1, a lower bound on a sum of two different errors. This is compatible with the actual SGLD chain Z having error 0 and all the error residing in the auxiliary chain ˜Z, which targets the artificial weighted posterior p_ω. Remark 3 explicitly allows T=0 and starting at the target, so one of the two errors may be exactly 0. The abstract's statement that 'any SGLD algorithm will return extremely poor samples' is therefore not a consequence of the theorem; the theorem does not lower-bound the error of the chain a user runs. A no-free-lunch result for SGLD needs a lower bound on ||L(Z_T)-p|| alone (under non-degenerate start), and no such inequality is derived. Even granting Assumptions 1-3, the proved statement is a two-chain property, not the advertised single-chain impossibility.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies stochastic gradient Langevin dynamics (SGLD) with minibatch subsampling for exponential-family posterior targets. It constructs a coupling between the SGLD transition kernel and a perturbed kernel whose minibatch distribution is slightly biased toward the upper half of the sorted data; Lemmas 1-3 show that this bias is a valid weighted-model gradient estimator and that it shifts the effective sufficient statistic by an amount controlled by a parameter ω_n, while Lemma 2 (via a Chatterjee-type fluctuation bound) shows the two driving measures are close in total variation. Theorem 1 then proves that, under Assumptions 1 and 3 and the rate conditions T_nM_n/n → 0, ω_n√(M_nT_n) → 0, the sum of the TV errors of the two coupled chains, one targeting p(·|X_n) and the other targeting the ω_n-perturbed posterior, is at least (1−a)γ with probability tending to 1. Theorem 2 states an analogous linear-in-ω_n lower bound in the regime T_nM_n/n → ∞. Section 4 discusses the strength of Assumption 3, the role of pre-computations, and the scope of the negative result.","tokens_in":10318,"tokens_out":23535,"duration_ms":201842,"significance":"If the advertised interpretation were justified, this would be a valuable no-free-lunch result for SGLD, extending the companion paper [JPS23] to a popular nonreversible sampler and complementing [NDH+17]. The paper's strengths are the clean coupling construction (Lemmas 1-3), the explicit and checkable assumptions (Assumptions 1-3), and the candid discussion in Remark 3 and Section 4, including the explicit concession that Assumption 3 is strong and that the verification is carried out only for Gaussian-type models. However, the significance as currently framed is undercut by a load-bearing gap: the formal theorems bound only the sum of the errors of two coupled chains, whereas the abstract and introduction claim that a single user-run SGLD chain returns poor samples. The paper is honest about this gap in Remark 3, so the fix is tractable, but until either a single-chain lower bound or a reframed two-chain instability claim is presented, the contribution is substantially weaker than advertised.","major_comments":[{"comment":"Theorem 1's conclusion lower-bounds the sum ‖L(Z_T^{(n)}) − p(·|X_n)‖_TV + ‖L(Ẑ_T^{(n)}) − p_{ω_n}(·|X_n)‖_TV, i.e., the sum of errors of two coupled chains. As Remark 3 concedes, the hypotheses allow T_n = 0 and the starting distribution of both chains to be the target p(·|X_n); in that case the error of the first (user-run) chain is exactly 0 and the entire lower bound must be carried by the auxiliary chain Ẑ. Consequently, the Abstract's statement that 'any SGLD algorithm will return extremely poor samples' and the Section 1 informal statement of Theorem 1 are not consequences of the theorem. The advertised no-free-lunch conclusion would require a single-chain lower bound under a non-degenerate starting distribution (or a formal minimax statement over starting measures), neither of which appears in the paper. Please either add such a bound or weaken the abstract and introduction to the two-chain 'simultaneous accuracy' claim that the theorem actually proves.","section":"Section 3.2, Theorem 1 and Remark 3; Abstract; Section 1"},{"comment":"The statement of Theorem 2 cites Assumptions 1 and 3 and Equations (6)-(7), but the proof uses inequality (12), which is a linear-in-ω_n lower bound of the type provided by Assumption 2 (not Assumption 1), and the proof invokes 'assumption (11)' at its end while the statement's hypotheses are (6)-(7). The theorem as stated therefore does not give the proof what it needs. In addition, display (13) as printed asserts lim sup_n ω_n^{-1/2}(M_nT_n)^{-1/4} P[(Z_1^{(n)},...,Z_{T_n}^{(n)}) = (Ẑ_1^{(n)},...,Ẑ_{T_n}^{(n)})] ≤ C^{-1}, so the probability of coupled trajectory equality is at most C^{-1}ω_n^{1/2}(M_nT_n)^{1/4}, which tends to 0 under (11); the proof, however, requires the coupled chains to be close, i.e., requires the equality probability to be near 1 (or the failure probability to be a controlled o(1)). Either the displayed event should be the failure event or the rate conditions must be strengthened so that T_n‖μ_{M_n} − ν_{ω_n/n,M_n}‖_TV → 0; with conditions (10)-(11) alone, for example M_n = T_n = n and ω_n = n^{-2}, the equality probability tends to 1 while the claimed upper bound tends to 0, so the displayed inequality cannot hold as stated.","section":"Section 3.3, Theorem 2, display (13)"},{"comment":"The paper itself describes Assumption 3 as 'quite a strong assumption', and the verification of the perturbation assumptions in Appendix A is limited to a Gaussian location model with R(x) = x (plus a near-Gaussian moment criterion). The abstract's 'often fails' and the introduction's 'classical statistical models' are therefore not established for a broad class of models. The theorems require Assumptions 1 and 3 (and, for Theorem 2, presumably Assumption 2), and the paper provides a concrete check only in the Gaussian case. The Discussion's item 1(b) is a reasonable informal argument, but the scope statements in the abstract and introduction should be aligned with the class for which the assumptions are actually verified, or additional examples should be supplied.","section":"Section 4, item 1; Appendix A"}],"minor_comments":[{"comment":"The displayed definition reads |µ(A) − µ(B)| but should read |µ(A) − ν(A)|; the second argument is the measure ν, not a re-use of the set B.","section":"Section 2.1, definition of total variation"},{"comment":"The informal statement of Theorem 1 in the introduction says 'until it has seen each data point at least once on average', but the formal condition is T_nM_n/n → 0, which is strictly before each point has been seen once on average; the boundary case T_nM_n/n = O(1) is not covered. Please align the informal description with the proved regime.","section":"Section 1 and Theorem 1 statement"},{"comment":"The final display of the proof, 'P[∆_n < (1−a)ηω_n + (aηω_n − C^{-1}ω_n^{1/2}(M_nT_n)^{1/4})] = 0', is hard to parse because the 'for all a > 0' clause appears inside the probability statement; rewriting this step with an intermediate variable would improve readability.","section":"Section 3.3, proof of Theorem 2"},{"comment":"The Discussion is candid that Assumption 3 is strong and unverified beyond simple models; consider moving this caveat to the introduction so that the abstract's scope is clear from the outset.","section":"Section 4, item 1"}],"recommendation":"major_revision","confidential_remarks":"The paper is a short companion to [JPS23], and the two-chain limitation is disclosed in Remark 3, which makes the requested revision feasible: either add a single-chain lower bound under non-degenerate starts or reframe the central claim as a simultaneous-accuracy impossibility. The main risk is that after the claims are tempered, the result may be judged a narrower 'instability' theorem rather than a no-free-lunch theorem for SGLD; the editor should weigh whether that revised claim still meets the journal's bar. The citation of the authors' own [JPS23] is contextual and appropriate for a companion note. Please have the authors check the mismatched hypotheses and rates in Theorem 2's statement and proof carefully, as this is currently a correctness gap beyond mere presentation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The coupling idea is clean and the proofs are correct as far as they go, but the abstract sells more than the theorems deliver. The paper proves that for any SGLD run there is a nearby perturbed SGLD run such that at least one of the two is far from its target; it does not prove that the unperturbed chain itself is poor.\n\nWhat's actually new: [JPS23] only handled reversible chains. This note extends the lower-bound program to non-reversible SGLD via a clever coupling of the subsampling randomness. The lemmas are short, the assumptions are stated cleanly, and the Gaussian verification in the appendix is useful. Credit where due: the authors openly flag the two-chain structure in Remark 3, and they are honest that Assumption 3 is only checked for Gaussians.\n\nSoft spots: the advertised 'any SGLD algorithm will return extremely poor samples' is not a consequence of Theorem 1. The theorem bounds the sum of two errors, and one of those chains is constructed by the authors, with a deliberately biased subsampling distribution. It is compatible with the actual chain having zero error. The authors' defense is reasonable but it is an argument about practice, not a theorem. For a no-free-lunch result you really want a lower bound on the single chain's error.\n\nAlso, Assumption 3 is called 'quite weak' in Section 3.1 and 'quite a strong assumption' in Section 4. Minor inconsistency. Theorem 2 also cites Equations (6)-(7) where it should cite (10)-(11).\n\nThese are fixable. The math itself is sound; the issue is the framing. If the abstract and informal statements are toned down to match the theorems, this is a useful short note for the MCMC scaling literature.\n\nRecommendation: send it out. A serious referee can sort out the framing. I'd ask for a revised abstract and a clear statement of what the theorem does and does not imply.","headline":"Clean coupling proof, but the abstract overstates the theorem: the lower bound is for a sum of two coupled chains, not the single chain a user runs.","tokens_in":10874,"tokens_out":2633,"would_cite":true,"duration_ms":23126,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62F15","60J22","65C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"Subsampling cannot asymptotically speed up SGLD: two theorems show the minibatch speedup is canceled by a matching accuracy loss.","keywords":["stochastic gradient Langevin dynamics","subsampling MCMC","Markov chain lower bounds","total variation distance","Bayesian computation","exponential families","nonreversible Markov chains","computational complexity of MCMC"],"falsifier":"For a Gaussian location model, run the original SGLD chain and the coupled biased-minibatch chain in Theorem 1 with short horizon T and small minibatch M satisfying T M / n → 0, computing the sum of their total variation distances from the exact posterior; the theorem predicts this sum stays above (1−a)γ with probability tending to 1, so any parameter setting where it falls below with high probability would refute the claim.","tokens_in":9862,"feed_emoji":"⚖️","tokens_out":5365,"duration_ms":49211,"temperature":0.7,"pith_summary":"This paper tries to establish that stochastic gradient Langevin dynamics (SGLD), a widely used MCMC method that subsamples data at each step, does not actually reduce total computation for typical Bayesian inference problems. The authors prove lower bounds on the error of SGLD: in the short-run regime, the chain cannot produce accurate posterior samples before it has seen each data point at least once on average; in the long-run regime, it cannot beat the full-batch gradient Langevin algorithm by more than a constant factor. If correct, the per-step speedup from subsampling is always offset by a proportional loss in accuracy, so the total work remains asymptotically the same. The paper closes a gap left by earlier work that only covered reversible chains or specific error bounds.","feed_headline":"Subsampling cannot asymptotically speed up SGLD, proofs show","feed_subtitle":"Two theorems bound the error of minibatch Langevin: per-step gains vanish when total computation is counted.","key_machinery":"The central mechanism is a coupling construction on the driving randomness of SGLD. SGLD is written as a forward-mapping chain that at each step samples a minibatch uniformly; the paper replaces that uniform distribution with a slightly biased distribution that is close in total variation but shifts the effective sufficient statistic by a small amount. This gives two Markov chains that are likely to produce identical sample paths, yet target slightly different posteriors. A triangle inequality then forces the sum of their errors to be large, and Assumptions 1 and 2 quantify how the posterior changes under such perturbations. The key quantitative tool is an eta-good condition on the likelihood, which ensures that the biased minibatch actually moves the posterior by a non-vanishing amount.","core_discovery":"The paper proves two theorems about SGLD targeting exponential-family posteriors. Theorem 1 shows that when the number of steps times the minibatch size is much smaller than the dataset size, the sum of the total variation errors of two coupled SGLD chains stays bounded below by a positive constant with probability tending to one: the chain cannot be close to the true posterior and its perturbed counterpart cannot be close to the perturbed posterior simultaneously. Theorem 2 considers the long-run regime where the total number of minibatch draws exceeds the dataset size, and shows the sum of errors is at least proportional to the size of the perturbation, meaning SGLD is not asymptotically more efficient than full-batch Langevin dynamics. Together they imply that the apparent speedup from subsampling is canceled by an accuracy loss, so the total computation is not reduced.","pith_inferences":["Editorial inference: the coupling construction may extend to other nonreversible subsampling chains that use i.i.d. minibatch randomness, so the no-free-lunch conclusion could be more general than SGLD; the paper hints at this but does not prove it there.","Editorial inference: the short-run theorem suggests a practical diagnostic: monitor minibatch coverage, meaning the number of distinct data points seen, rather than iteration count; a chain that has not seen every point once on average should not be trusted.","Editorial inference: the reliance on Assumption 3 leaves an opening; for models with balanced sufficient statistics, where the upper-half average equals the global average, the specific lower bound disappears, so testing heavy-tailed or discrete exponential families would clarify whether the phenomenon is universal."],"forward_implications":["SGLD's per-step speedup from minibatching is offset by a proportional accuracy loss, so total computation does not shrink asymptotically.","In the short-run regime, users should not expect accurate posterior samples until the algorithm has touched every data point at least once on average.","In the long-run regime, SGLD delivers no asymptotic gain over full-batch ULA when matched for equal total compute, for models satisfying the assumptions.","The lower bounds are matched by existing upper bounds, so the conclusion is tight rather than an artifact of loose analysis.","Pre-computation methods that only re-weight samples inherit the negative conclusion, while stronger pre-computations would require new perturbation arguments."],"supporting_citations":[{"why":"Introduced the true-cost analysis of SGLD error bounds; this paper closes the gap left by those bounds.","marker":"[NDH+17]"},{"why":"Companion paper proving no-free-lunch for reversible approximate MCMC chains; current paper extends the result to nonreversible SGLD.","marker":"[JPS23]"},{"why":"Gives effectively matching upper bounds for SGLD error, showing the lower bounds in this paper are tight.","marker":"[DK19]"},{"why":"Supplies the fluctuation lower-bound calculation reused in Lemma 2.","marker":"[Cha19]"},{"why":"Defines stochastic gradient Langevin dynamics, the algorithm represented in Example 1.","marker":"[WT11]"},{"why":"Provides the sharp moment-based total variation bound used in Appendix A.1 to verify Assumption 1.","marker":"[Nis23]"}],"fun_headline_variants":["SGLD minibatching gains cancel out at scale","No free lunch: SGLD subsampling fails asymptotically","Proof: SGLD subsampling yields no asymptotic speedup","Minibatch Langevin gains vanish when total compute counted","Subsampling cannot speed up SGLD asymptotically"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The bounds require Assumption 3, that for data drawn from the model the average of the sufficient-statistic function over the upper half of the sorted sample exceeds its overall average by at least a fixed amount eta with probability tending to 1; the paper calls this 'quite a strong assumption' and verifies it only for Gaussian-type models.","fun_headline_variants_meta":{"raw":{"variants":["SGLD minibatching gains cancel out at scale","No free lunch: SGLD subsampling fails asymptotically","Proof: SGLD subsampling yields no asymptotic speedup","Minibatch Langevin gains vanish when total compute counted","Subsampling cannot speed up SGLD asymptotically"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000264,"raw_usage":{"total_tokens":1570,"prompt_tokens":880,"completion_tokens":690,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":496,"completion_tokens_details":{"reasoning_tokens":607}},"tokens_in":496,"tokens_out":690,"duration_ms":5865,"temperature":1.0,"reasoning_tokens":607,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T00:00:21.065351+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a Gaussian location model, run the original SGLD chain and the coupled biased-minibatch chain in Theorem 1 with short horizon T and small minibatch M satisfying T M / n → 0, computing the sum of their total variation distances from the exact posterior; the theorem predicts this sum stays above (1−a)γ with probability tending to 1, so any parameter setting where it falls below with high probability would refute the claim.","supporting_citations":[],"review_version":1}