Pith. sign in

REVIEW 3 major objections 4 minor 18 references

No Free Lunch for Stochastic Gradient Langevin Dynamics

T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Subsampling cannot asymptotically speed up SGLD: two theorems show the minibatch speedup is canceled by a matching accuracy loss.

desk verdict 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. read the letter →

arxiv 2412.01952 v1 pith:OJR7TOYO submitted 2024-12-02 stat.CO

Natesh S. Pillai , Aaron Smith , Azeem Zaman This is my paper · ORCID
classification stat.CO MSC 62F1560J2265C40
keywords stochasticgradientLangevindynamicssubsamplingMCMCMarkovchainlowerboundstotalvariationdistanceBayesiancomputationexponentialfamiliesnonreversiblechainscomputationalcomplexityof
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [Section 3.2, Theorem 1 and Remark 3; Abstract; Section 1] 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.
  2. [Section 3.3, Theorem 2, display (13)] 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.
  3. [Section 4, item 1; Appendix A] 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.
minor comments (4)
  1. [Section 2.1, definition of total variation] 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.
  2. [Section 1 and Theorem 1 statement] 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.
  3. [Section 3.3, proof of Theorem 2] 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.
  4. [Section 4, item 1] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: The main theorems follow from stated assumptions and external coupling/perturbation bounds; self-citations are contextual and not load-bearing.

full rationale

The paper's central results, Theorems 1 and 2, are conditional lower bounds whose proofs are built from the coupling construction in Lemma 2 (borrowing a calculation from the external reference [Cha19]), the weighted-gradient identity in Lemma 1, the sufficient-statistic perturbation calculation in Lemma 3, and the perturbation Assumptions 1-3. The target-distribution separation (Inequalities (8) and (12)) is not assumed but derived from Assumptions 1 and 3 combined with Lemma 3, and the sample-path closeness (Inequalities (9) and (13)) is derived from Lemma 2. The only self-citations ([JPS23], [RSQ24]) are used for motivation, context, and discussion of extensions; they are not invoked in the proofs of Theorem 1 or 2. The appendices verify Assumptions 1 and 2 using external results ([Nis23], [Pol05]). There are no fitted parameters, no normalization choices that force the stated quantities by definition, and no uniqueness claims imported from the authors' prior work. The paper explicitly acknowledges in Remark 3 that Theorem 1 bounds a sum of errors of two chains rather than a single chain, and that one of the errors may be zero; this is a limitation in the strength of the advertised claim, but it is an inferential gap, not circularity. The admitted strength of Assumption 3 is also a scope limitation, not a circular step. Overall, the derivation chain is self-contained given the stated assumptions and external benchmarks, so the circularity score is minimal.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The central claim depends on a set of asymptotic sequences (omega_n, M_n, T_n) chosen to satisfy rate conditions, and on three perturbation assumptions (1-3) that are plausible but only verified for Gaussian models. No new physical or conceptual entities are introduced.

free parameters (3)
  • omega_n (perturbation size) = asymptotic sequence
    Controls the size of the perturbation to the subsampling distribution and hence the change in the sufficient statistic; the lower bounds in Theorems 1 and 2 scale with omega_n. It is chosen by hand to satisfy the rate conditions (7) and (11).
  • M_n (minibatch size) = asymptotic sequence
    Number of data points examined per SGLD step; chosen to satisfy T_n M_n / n -> 0 (Theorem 1) or -> infinity (Theorem 2).
  • T_n (number of steps) = asymptotic sequence
    Run length of the Markov chain; chosen to place the analysis in the short-run or long-run regime.
assumptions (5)
  • domain assumption Assumption 1: posterior sensitivity to large perturbations (delta_n >> 1/sqrt(n)) yields TV distance at least gamma in the limit.
    Invoked in Theorem 1 to assert that the true and perturbed posteriors are far apart; verified only for Gaussian models in Appendix A.1.
  • domain assumption Assumption 2: posterior sensitivity to small perturbations is linear, TV distance at least gamma times delta_n.
    Invoked in Theorem 2 for the long-run regime; verified for Gaussians in Appendix A.2.
  • domain assumption Assumption 3 (eta-good likelihoods): for data from the model, the upper-half mean of R(X) exceeds the overall mean by at least eta > 0 with probability tending to 1.
    Used to ensure the perturbed sufficient statistic is actually changed by the skewed subsampling; the authors themselves call it 'quite a strong assumption' in Section 4.
  • domain assumption The likelihood has the exponential family form p(x|theta) = h(x) exp(theta R(x) - A(theta)) with scalar x, and the parameter space is Polish.
    The entire analysis is restricted to this model class; the coupling and perturbation calculations use this specific form.
  • standard math Chatterjee's method for total variation bounds on functions of binomials (Chatterjee 2019) is correct.
    Used in the proof of Lemma 2 to bound the TV distance between the uniform and perturbed subsampling distributions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of No Free Lunch for Stochastic Gradient Langevin Dynamics." pith.science (2026). https://pith.science/paper/OJR7TOYO

@misc{pith2026241201952,
  author       = {Pith},
  title        = {Pith review of: No Free Lunch for Stochastic Gradient Langevin Dynamics},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OJR7TOYO}},
  note         = {Machine review of arXiv:2412.01952}
}
read the original abstract

As sample sizes grow, scalability has become a central concern in the development of Markov chain Monte Carlo (MCMC) methods. One general approach to this problem, exemplified by the popular stochastic gradient Langevin dynamics (SGLD) algorithm, is to use a small random subsample of the data at every time step. This paper, building on recent work such as \cite{nagapetyan2017true,JohndrowJamesE2020NFLf}, shows that this approach often fails: while decreasing the sample size increases the speed of each MCMC step, for typical datasets this is balanced by a matching decrease in accuracy. This result complements recent work such as \cite{nagapetyan2017true} (which came to the same conclusion, but analyzed only specific upper bounds on errors rather than actual errors) and \cite{JohndrowJamesE2020NFLf} (which did not analyze nonreversible algorithms and allowed for logarithmic improvements).

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 15 canonical work pages

  1. [1]

    The pseudo-marginal approach for efficient M onte C arlo computations

    Christophe Andrieu and Gareth O Roberts. The pseudo-marginal approach for efficient M onte C arlo computations. The Annals of Statistics , 37(2):697--725, 2009

    work page 2009

  2. [2]

    On M arkov chain M onte C arlo methods for tall data

    R\' e mi Bardenet, Arnaud Doucet, and Chris Holmes. On M arkov chain M onte C arlo methods for tall data. J. Mach. Learn. Res. , 18(1):1515–1557, jan 2017

    work page 2017

  3. [3]

    Bayesian coreset construction via greedy iterative geodesic ascent

    Trevor Campbell and Tamara Broderick. Bayesian coreset construction via greedy iterative geodesic ascent. arXiv 1802.01737 , 2018

    arXiv 2018

  4. [4]

    Stochastic gradient H amiltonian M onte C arlo

    Tianqi Chen, Emily B Fox, and Carlos Guestrin. Stochastic gradient H amiltonian M onte C arlo. In ICML'14 , page II–1683–II–1691. JMLR.org, 2014

    work page 2014

  5. [5]

    A general method for lower bounds on fluctuations of random variables

    Sourav Chatterjee. A general method for lower bounds on fluctuations of random variables. The Annals of Probability , 47(4):2140--2171, 2019

    work page 2019

  6. [6]

    Bayesian inference via sparse H amiltonian flows

    Naitong Chen, Zuheng Xu, and Trevor Campbell. Bayesian inference via sparse H amiltonian flows. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems , volume 35, pages 20876--20888. Curran Associates, Inc., 2022

    work page 2022

  7. [7]

    Dalalyan and Avetik Karagulyan

    Arnak S. Dalalyan and Avetik Karagulyan. User-friendly guarantees for the L angevin M onte C arlo with inaccurate gradient. Stochastic Processes and their Applications , 129(12):5278–5311, December 2019

    work page 2019

  8. [8]

    Minibatch G ibbs sampling on large graphical models

    Chris De Sa, Vincent Chen, and Wing Wong. Minibatch G ibbs sampling on large graphical models. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning , volume 80 of Proceedings of Machine Learning Research , pages 1165--1173. PMLR, 10--15 Jul 2018

    work page 2018

Show all 18 references
  1. [9]

    No free lunch for approximate MCMC

    James E Johndrow, Natesh S Pillai, and Aaron Smith. No free lunch for approximate MCMC . arXiv:2010.12514 , 2023+

    2010 arXiv

  2. [10]

    Austerity in MCMC land: Cutting the M etropolis- H astings budget

    Anoop Korattikara, Yutian Chen, and Max Welling. Austerity in MCMC land: Cutting the M etropolis- H astings budget. In Proceedings of the 31st International Conference on Machine Learning (ICML-14) , pages 181--189, 2014

    2014

  3. [11]

    The true cost of stochastic gradient L angevin dynamics

    Tigran Nagapetyan, Andrew B Duncan, Leonard Hasenclever, Sebastian J Vollmer, Lukasz Szpruch, and Konstantinos Zygalakis. The true cost of stochastic gradient L angevin dynamics. arXiv preprint arXiv:1706.02692 , 2017

    2017 arXiv

  4. [12]

    Lower bounds for the total variation distance given means and variances of distributions

    Tomohiro Nishiyama. Lower bounds for the total variation distance given means and variances of distributions. arXiv:2212.05820 , 2023+

    2023 arXiv

  5. [13]

    D. Pollard. Asymptotia, 2005

    2005

  6. [14]

    Subsampling MCMC - an introduction for the survey statistician

    Matias Quiroz, Mattias Villani, Robert Kohn, Minh-Ngoc Tran, and Khue-Dung Dang. Subsampling MCMC - an introduction for the survey statistician. Sankhya A , 80:1--37, 12 2018

    2018

  7. [15]

    Speeding up MCMC by efficient data subsampling

    Matias Quiroz, Mattias Villani, and Robert Kohn. Speeding up MCMC by efficient data subsampling. Journal of the American Statistical Association , 114(526):831--843, 2019

    2019

  8. [16]

    Perturbation theory for M arkov chains via W asserstein distance

    Daniel Rudolf and Nikolaus Schweizer. Perturbation theory for M arkov chains via W asserstein distance. Bernoulli , 24, 03 2015

    2015

  9. [17]

    Perturbations of M arkov chains, 2024

    Daniel Rudolf, Aaron Smith, and Matias Quiroz. Perturbations of M arkov chains, 2024

    2024

  10. [18]

    Bayesian learning via stochastic gradient L angevin dynamics

    Max Welling and Yee Whye Teh. Bayesian learning via stochastic gradient L angevin dynamics. In Proceedings of the 28th International Conference on International Conference on Machine Learning , ICML'11, page 681–688, Madison, WI, USA, 2011. Omnipress

    2011

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.