Pith. sign in

REVIEW 3 major objections 3 minor 1 cited by

Upper and lower bounds on the subgeometric convergence of adaptive Markov chain Monte Carlo

T0 review · 3 major / 3 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 Adaptive MCMC has a universal slow-convergence floor set by the target's tail and drift.

desk verdict Solid adaptive MCMC lower bounds and a promising upper bound, but the advertised rate matching after Theorem 10 is not actually proven. read the letter →

arxiv 2411.17084 v3 pith:DVFPWOKP submitted 2024-11-26 math.ST stat.TH

Austin Brown , Jeffrey S. Rosenthal This is my paper · ORCID
classification math.STstat.TH MSC 60J2760J2260G07
keywords adaptiveMetropolis-HastingslowerboundsforMCMCupperweakconvergenceofsubgeometricquantitativediminishingadaptation
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 proves that adaptive Markov chain Monte Carlo algorithms, no matter how cleverly the tuning parameters are adapted, cannot converge faster than a subgeometric rate dictated by the target distribution's tail and a simultaneous drift condition on every kernel in the family. The lower bounds hold for any adaptation plan, both in total variation and in weak Wasserstein distance, and they are paired with matching upper bounds when adaptation diminishes sufficiently fast. The result gives a practical benchmark: for heavy-tailed targets, the convergence rate is fundamentally capped, and online tuning cannot break that ceiling. Applications to adaptive Langevin and Metropolis–Hastings samplers illustrate the rates in concrete settings.

What carries the argument

The engine of the argument is the inverse-H function $H_{w_0,\varphi}^{-1}$, built from a concave drift increment $\varphi$: $H_{w_0,\varphi}(w) = \int_{w_0}^{w} dv/\varphi(v)$. This function converts the drift condition into a polynomial, subgeometric, or geometric rate depending on the form of $\varphi$, and both the lower and upper bounds are expressed through it. The lower bound uses a tail-discrepancy argument: Markov's inequality applied to the drift-controlled moment $E[W^\alpha(X_t)]$ shows that the adaptive marginal cannot concentrate enough mass in the target's heavy tail. The upper bound additionally relies on a quantitative diminishing adaptation condition, Definition 7, which requires the kernels to change uniformly in total variation by at most a prescribed $G(t)$ that tends to zero.

What would settle it

Run the adaptive independence sampler of Section 5 with proposal rate restricted to $(\gamma_*,\gamma^*)$ targeting the exponential distribution; Proposition 11 predicts the total variation distance is at least $M_*/(c_* t + 1)^{1/(\gamma_*-1)}$. If a simulation shows the distance decaying faster than $t^{-1/(\gamma_*-1)}$ for large $t$, Theorem 1's lower bound is false.

Watch

Extended reading notes

Core claim

The central discovery is that the subgeometric convergence rate of adaptive MCMC is governed entirely by the pair consisting of the target's tail probability and a simultaneous drift inequality imposed on all admissible kernels. If the target satisfies $\pi(W \ge r) \ge C r^{-\kappa}$ and every kernel obeys $(P_\gamma W^\alpha)(x) - W^\alpha(x) \le \varphi(W^\alpha(x))$ for a concave nondecreasing $\varphi$, then for every adaptation plan the total variation distance between the marginal and the target is bounded below by a rate expressed through the inverse of $H_{w_0,\varphi}(t) = \int_{w_0}^{\cdot} dv/\varphi(v)$. The same lower bound carries over to weak convergence on Euclidean spaces, and under quantitative diminishing adaptation the upper bound matches this rate up to logarithmic factors, showing that the bounds are asymptotically sharp for fast-diminishing adaptation.

Load-bearing premise

The matching upper bounds require quantitative diminishing adaptation: after a burn-in, every kernel change must be uniformly small over all states in total variation, shrinking at a prescribed rate—a stronger condition than the usual diminishing adaptation assumed in adaptive MCMC proofs.

Editorial extensions

If this is right

  • Any adaptive MCMC scheme whose kernel family satisfies the simultaneous subgeometric drift and whose target has polynomial tail decay must have a total variation convergence rate no faster than the polynomial rate fixed by the drift and tail, regardless of adaptation strategy.
  • The same lower-bound rate holds in weak Wasserstein distance on Euclidean state spaces, so the slow convergence is intrinsic and not an artifact of the total variation metric.
  • If adaptation diminishes according to quantitative diminishing adaptation (uniform kernel-change control), the upper bound matches the lower bound's rate up to logarithmic factors, making the subgeometric rate asymptotically exact.
  • For the adaptive unadjusted Langevin algorithm targeting a Student-$t$ distribution, the weak convergence rate is lower-bounded by a polynomial of order $(1+t)^{v+d-2}$; for adaptive random-walk Metropolis on Weibull-type targets, the lower bound is $\exp(-c\,t^{m/(2-m)})$.
  • The independence-sampler example shows that restricting tuning parameters to a compact set does not escape the lower-bound rate when the proposal tails are constrained to be lighter than the target's tail.

Reading between the lines

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

  • Editorial: because the lower bounds hold uniformly over all adaptation plans, they imply that for heavy-tailed targets the convergence bottleneck is the (drift, tail) pair itself; no online tuning strategy can eliminate it.
  • Editorial: the quantitative diminishing adaptation condition (Definition 7) is meaningfully stronger than the standard diminishing adaptation used in most adaptive MCMC theory; when it cannot be verified, the matching upper bound should not be expected to hold automatically.
  • Editorial: the tail-discrepancy technique likely extends to continuous-time adaptive processes or to other distances such as $f$-divergences, where analogous subgeometric floors may appear.
  • Editorial: practical safeguards like restricting adaptation to a compact parameter set do not by themselves improve the convergence rate for heavy-tailed targets; the limiting rate is already fixed by the target's tail and the drift family.
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 / 3 minor

Summary. The paper develops quantitative lower bounds on the total-variation and weak (bounded-Lipschitz/Wasserstein) convergence of adaptive MCMC under arbitrary adaptation plans, assuming a simultaneous concave drift inequality for the Markov family and a polynomial tail lower bound on the target. It then proves a subgeometric upper bound under a quantitative diminishing adaptation condition, a simultaneous subgeometric drift condition, and a simultaneous local contraction condition, and it applies the results to an adaptive unadjusted Langevin algorithm, an adaptive independence sampler, and adaptive random-walk Metropolis. The central advertised conclusion is that, when adaptation diminishes quickly enough, the upper bound can approximately match the subgeometric lower bound.

Significance. If the claims hold, the lower bounds are a useful addition to the adaptive MCMC literature: Theorem 1 has an elementary proof and gives explicit constants, and Theorem 10 is a substantial quantitative extension of subgeometric upper-bound techniques to adaptive chains. The applications are well chosen and illustrate the type of rates one can expect. I found no circularity: the lower bounds follow from the stated drift and tail assumptions, and the upper bounds use standard subgeometric coupling arguments. The main qualifications are that some load-bearing assumptions are missing from Theorem 4, the matching claim after Theorem 10 is not justified as written, and one displayed application rate in Example 5 is based on an incorrect tail estimate.

major comments (3)
  1. [Section 4, paragraph after Theorem 10] The displayed inequality combining Theorem 1 and Theorem 10 is not established as written. Theorem 1 gives a lower bound on ||A^{(t)}_Q - pi||_TV, while the right-hand side of the displayed chain bounds ||A^{(T_{epsilon,t}+t)}_Q - pi||_TV. The adaptive marginal A_Q is not Markov, and the paper proves no monotonicity of t -> ||A^{(t)}_Q - pi||_TV; for a fixed Markov chain total variation distance to stationarity is nonincreasing, but that fact does not apply here. Correcting the left side to time T_{epsilon,t}+t gives M_*/H^{-1}_{V(x0)^{2kappa},phi}(T_{epsilon,t}+t), and with G(t)=t^{-3/2} (allowed in the alpha>1 row of Table 1) T_{epsilon,t} is of order t^{4/3}; the corrected lower bound then decays like t^{-4q/3} while the Theorem 10 upper bound is of order t^{4/3-q}, where q=1/(1-beta). These rates do not match without a further condition. An explicit condition such as T_{epsilon,t}=O(t), or a direct lower bound evaluated at the same time with a comparable H^{-1} argument, is needed before the 'approximately matching' claim is justified.
  2. [Section 3, Theorem 4] Theorem 4 assumes only that W is Borel and has compact sublevel sets, but the proof invokes continuity and uniform continuity of W on K={x: W(x)<=r}. Compact sublevel sets imply lower semicontinuity, not continuity; for example, W(x)=1+|x| for x != 0 and W(0)=0 on R has compact sublevel sets but is not continuous at 0. Since the existence of delta_epsilon with W(x)>=(1-epsilon)r on the delta_epsilon-neighborhood of T depends on uniform continuity of W, a continuity assumption on W, or a separate argument using only lower semicontinuity, is load-bearing and must be added to the theorem statement and used in the proof.
  3. [Section 3, Example 5] The asserted tail lower bound pi(W >= r) >= C r^{-(1-2/(v+d))} is incorrect. For the Student-t target with W(x)=(1+||x||^2)^{(v+d)/2}, the tail behaves as pi(W>=r) ~ c r^{-v/(v+d)} as r goes to infinity; for d=v=1, for instance, this is r^{-1/2}, whereas the claimed exponent is 0. The subsequent conclusion that Theorem 4 yields a lower bound of order (1+t)^{-(v+d-2)} is therefore not supported and should be recomputed with the correct tail exponent.
minor comments (3)
  1. [Section 4, after Table 1] There is a typographical error: 'Theoerem 10' should read 'Theorem 10'.
  2. [Supporting technical results, Proposition 17] The proof states that 'Phi(U) is open for every open set U subset T' as a consequence of continuity of Phi; continuity alone does not imply openness. The intended conclusion is standard and can be obtained by applying the Kuratowski-Ryll-Nardzewski measurable selection theorem to the compact-valued correspondence (mu,nu) -> optimal couplings, so the argument should be restated along those lines.
  3. [Section 5, Propositions 11 and 12] The parameter interval is written as (gamma_*, gamma_*) with both endpoints printed identically, which makes the formulas for c_* and for the dependence on the two endpoints difficult to read; please use distinct notation such as gamma_L and gamma_U, or gamma_* and gamma^* throughout the section.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation is self-contained; lower and upper bounds follow from explicitly stated tail, drift, coupling, and diminishing-adaptation assumptions.

full rationale

The paper's derivation chain is self-contained in the relevant sense. Theorem 1 derives the total-variation lower bound from the stated tail condition (2), the simultaneous drift inequality (3), Markov's inequality, and an induction over the inverse function H^{-1}; no fitted quantity or target conclusion enters as an input. Theorem 4 extends the same argument to the Wasserstein distance via Strassen's theorem and compact level sets, again without assuming the result. The upper bound in Theorem 10 is proved by coupling the adaptive process to a finite-adaptation process and bounding the two resulting terms using the quantitative diminishing adaptation condition (7), the simultaneous subgeometric drift condition (8), the simultaneous local contraction condition (9), and standard subgeometric estimates attributed to Douc, Fort, Moulines, and Soulier. These are assumptions, not fitted parameters, and the applications in Sections 5 and 6 verify the required drift and tail conditions by direct calculation, for example through identities (12) and (13). I found no step where a parameter is fitted to a subset of data and then renamed a prediction, and no load-bearing argument whose premise is equivalent by construction to its conclusion. The self-citations, such as the reference to Roberts and Rosenthal for the usual diminishing adaptation condition, are contextual and are not the engine of the proof. A possible concern in the paragraph following Theorem 10 is that the displayed 'approximately matching' inequality compares a lower bound at time t with an upper bound at time T_{epsilon,t}+t without an explicit monotonicity argument; that is a correctness or quantitative-matching issue, not circularity, so it does not affect the circularity score.

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

The lower-bound results cost only tail and uniform drift assumptions; the matching upper bounds cost strong uniform invariancy, drift, local contraction, and quantitative diminishing adaptation. No constants are fitted to data and no physical or computational entities are invented, so the ledger is dominated by domain assumptions.

assumptions (5)
  • domain assumption Target tail lower bound: pi(W >= r) >= C r^{-kappa} for all r > 0 (Eq. (2)).
    Used in Theorems 1, 4, and 6 to create a discrepancy between the target tail and the drift-controlled process tail; not derived inside the paper.
  • domain assumption Simultaneous subgeometric drift: (P_gamma W^alpha)(x) - W^alpha(x) <= phi(W^alpha(x)) for every tuning parameter gamma (Eq. (3)).
    This uniform-in-gamma bound is what lets the lower bounds hold for every adaptation plan Q; for upper bounds, a similar simultaneous drift (8) is assumed.
  • domain assumption For Theorem 10: each kernel leaves pi invariant, simultaneous local contraction (9), and quantitative diminishing adaptation (7).
    The upper bound is conditional on these three uniform assumptions plus the prescribed rate of decay of G(t); they are stated as assumptions, not proved.
  • domain assumption Implicit continuity of W and closed level sets {W >= r} in Theorem 4.
    The theorem states compact sublevel sets, but the proof says 'Since W is continuous'; applications use continuous W, but this condition is not listed in the theorem statement.
  • standard math Standard results: Jensen and Markov inequalities, Strassen's theorem, inverse-function properties of H_{w0,phi}, and coupling and drift lemmas from Douc et al. (2004) and Jarner-Tweedie (2001).
    Used inside the proofs of Theorems 1, 4, and 10; treated as black boxes with citations.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Upper and lower bounds on the subgeometric convergence of adaptive Markov chain Monte Carlo." pith.science (2026). https://pith.science/paper/DVFPWOKP

@misc{pith2026241117084,
  author       = {Pith},
  title        = {Pith review of: Upper and lower bounds on the subgeometric convergence of adaptive Markov chain Monte Carlo},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DVFPWOKP}},
  note         = {Machine review of arXiv:2411.17084}
}
read the original abstract

We investigate lower bounds on the subgeometric convergence of adaptive Markov chain Monte Carlo under any adaptation strategy. In particular, we prove general lower bounds in total variation and on the weak convergence rate under general adaptation plans. If the adaptation diminishes sufficiently fast, we also develop comparable convergence rate upper bounds that are capable of approximately matching the convergence rate in the subgeometric lower bound. These results provide insight into the optimal design of adaptation strategies and also limitations on the convergence behavior of adaptive Markov chain Monte Carlo. Applications to an adaptive unadjusted Langevin algorithm as well as adaptive Metropolis-Hastings with independent proposals and random-walk proposals are explored.

Figures

Figures reproduced from arXiv: 2411.17084 by the authors.

Figure 1
Figure 1. The diagram illustrates intuition for a discrepancy between the set [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Aligning Large Vision-Language Models at Test Time: A Trajectory-Guided Structured Sampling Approach

    cs.CL 2026-08 conditional novelty 6.0 of 10

    Sampling from a sharpened, vision-calibrated target during decoding improves frozen LVLM reasoning accuracy by 2-3 points on five benchmarks, but multiplies token cost by 15-24.

Reference graph

Works this paper leans on

22 extracted references · 21 canonical work pages · cited by 1 Pith paper

  1. [1]

    Atchad´ e

    Christophe Andrieu and Yves F. Atchad´ e. On the efficieny of adaptive MCMC algorithms. Electronic Communications in Probability , 12:336–349, 2007. doi: 10. 1214/ECP.v12-1320

    work page 2007

  2. [2]

    On the ergodicity properties of some adaptive MCMC algorithms

    Christophe Andrieu and ´Eric Moulines. On the ergodicity properties of some adaptive MCMC algorithms. The Annals of Applied Probability , 16(3):1462–1505, 2006. 32

    work page 2006

  3. [3]

    Subexponential lower bounds for f-ergodic Markov processes

    Miha Breˇ sar and Aleksandar Mijatovi´ c. Subexponential lower bounds for f-ergodic Markov processes. Probability Theory and Related Fields , pages 1–58, 2024

    work page 2024

  4. [4]

    Practical drift conditions for subgeometric rates of convergence

    Randal Douc, Gersende Fort, Eric Moulines, and Philippe Soulier. Practical drift conditions for subgeometric rates of convergence. The Annals of Applied Probability, 14(3):1353–1377, 2004

    work page 2004

  5. [5]

    Real analysis and probability

    Richard M Dudley. Real analysis and probability . Chapman and Hall/CRC, 2018

    2018

  6. [6]

    Subgeometric rates of convergence in Wasserstein distance for Markov chains

    Alain Durmus, Gersende Fort, and ´Eric Moulines. Subgeometric rates of convergence in Wasserstein distance for Markov chains. Annales de l’Institut Henri Poincar´ e, Probabilit´ es et Statistiques, 52(4):1799–1822, 2016

    work page 2016

  7. [7]

    V-subgeometric ergodicity for a Hast- ings–Metropolis algorithm

    Gersende Fort and Eric Moulines. V-subgeometric ergodicity for a Hast- ings–Metropolis algorithm. Statistics and Probability Letters , 49(4):401–410, 2000

    work page 2000

  8. [8]

    An adaptive Metropolis algorithm

    Heikki Haario, Eero Saksman, and Johanna Tamminen. An adaptive Metropolis algorithm. Bernoulli, 7(2):223–242, 2001

    work page 2001

Show all 22 references
  1. [9]

    How hot can a heat bath get? Communications in Mathematical Physics, 292(1):131–177, 2009

    Martin Hairer. How hot can a heat bath get? Communications in Mathematical Physics, 292(1):131–177, 2009

    2009

  2. [10]

    S. F. Jarner and R. L. Tweedie. Locally contracting iterated functions and stability of Markov chains. Journal of Applied Probability , 38(2):494–507, 2001

    2001

  3. [11]

    Jarner and Gareth O

    Søren F. Jarner and Gareth O. Roberts. Polynomial convergence rates of Markov chains. The Annals of Applied Probability , 12(1):224–247, 2002

    2002

  4. [12]

    Metropolis–Hastings algorithms with acceptance ratios of nearly

    Kengo Kamatani. Metropolis–Hastings algorithms with acceptance ratios of nearly

  5. [13]

    Annals of the Institute of Statistical Mathematics , 61(4):949–967, 2009

    2009

  6. [14]

    Kuratowski and C

    K. Kuratowski and C. Ryll-Nardzewski. A general theorem on selectors. Bul- letin de l’Acad´ emie Polonaise des Sciences. S´ erie des Sciences Math´ ematiques, As- tronomiques et Physiques , 13:397–403, 1965

    1965

  7. [15]

    An invitation to adaptive Markov chain Monte Carlo convergence theory, 2024

    Pietari Laitinen and Matti Vihola. An invitation to adaptive Markov chain Monte Carlo convergence theory, 2024. 33

    2024

  8. [16]

    A framework for adaptive MCMC targeting multimodal distributions

    Emilia Pompe, Chris Holmes, and Krzysztof Latuszynski. A framework for adaptive MCMC targeting multimodal distributions. The Annals of Statistics , 48(5):2930– 2952, 2020

    2020

  9. [17]

    Roberts and Jeffrey S

    Gareth O. Roberts and Jeffrey S. Rosenthal. Coupling and ergodicity of adaptive Markov chain Monte Carlo algorithms. Journal of Applied Probability , 44(2):458– 475, 2007

    2007

  10. [18]

    Subexponential upper and lower bounds in Wasserstein distance for Markov processes

    Nikola Sandri´ c, Ari Arapostathis, and Guodong Pang. Subexponential upper and lower bounds in Wasserstein distance for Markov processes. Applied Mathematics & Optimization, 85(3):37, May 2022

    2022

  11. [19]

    Schmidler and Dawn B

    Scott C. Schmidler and Dawn B. Woodard. Lower bounds on the convergence rates of adaptive MCMC methods. Tech. rep., Duke Univ. , 2011

    2011

  12. [20]

    Strassen

    V. Strassen. The existence of probability measures with given marginals. The Annals of Mathematical Statistics , 36(2):423–439, 1965

    1965

  13. [21]

    Topics in Optimal Transportation

    C´ edric Villani. Topics in Optimal Transportation . Providence, RI: Amer. Math. Soc., 2003

    2003

  14. [22]

    Berlin: Springer, 2009

    C´ edric Villani.Optimal Transport: Old and New . Berlin: Springer, 2009. 34

    2009

Pith tools

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