{"id":"17679df7-27ff-42c8-98a8-06fee03dbadb","arxiv_id":"2411.17084","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Adaptive MCMC cannot converge faster than a subgeometric rate dictated by the target tails and worst-case drift, and matching upper bounds hold when adaptation fades quickly.","lead":"New theorems bound how fast adaptive Markov chain Monte Carlo samplers can converge when convergence is slow, or subgeometric. The lower bounds hold for every adaptation strategy, and matching upper bounds appear when adaptation fades fast enough.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The matching lower/upper bound claim after Theorem 10 compares a lower bound at time t with an upper bound at time T_epsilon,t + t; no monotonicity supports this, so the advertised match is not proven.","rationale":"The paper's lower-bound machinery (Theorem 1 and the extension to weak convergence in Theorem 4) appears sound, and the upper-bound strategy in Theorem 10 is a substantial contribution. The weakest point I find is not the verifiability of Definition 7 itself, but the paper's central claim that Theorem 10 approximately matches Theorem 1: the displayed combined inequality applies a time-t lower bound to a total-variation distance evaluated at time T_epsilon,t + t. Because the adaptive marginal need not be monotone in total variation, this step is logically invalid as written. Correcting the time index reveals that the match holds only under additional speed assumptions on G, which are not stated. This is a significant but fixable gap, so the reader's CONDITIONAL verdict is appropriate and does not need to be changed. The reader's weakest_assumption focused on the strength of quantitative diminishing adaptation and the continuity of W in Theorem 4; my concern is adjacent but distinct, hence partial agreement.","tokens_in":18887,"tokens_out":38173,"duration_ms":367939,"concrete_test":"Re-derive the matching paragraph after Theorem 10 with the lower bound evaluated at time T_epsilon,t + t instead of t. For the polynomial case phi(w) = c w^beta and G(t) = t^{-3/2}, compute the two rates: if the corrected lower bound decays as t^{-4q/3} and the upper bound as t^{4/3 - q} with q = 1/(1-beta), then the rates are not comparable, confirming that the matching claim requires an explicit speed condition such as T_epsilon,t = O(t) or G(t) = O(e^{-ct}).","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the paragraph following Theorem 10, the paper displays M_*/H^{-1}_{V(x0)^{2kappa},phi}(t) <= ||A^{(T_epsilon,t+t)}_Q(...) - pi||_TV and calls this a combination of Theorem 1 and Theorem 10. Theorem 1 gives a lower bound evaluated at the marginal time t, but the norm on the right is evaluated at time T_epsilon,t + t. The adaptive marginal is not Markov, and the paper establishes no monotonicity of t -> ||A_Q(t) - pi||_TV. Even for a fixed Markov chain, total variation distance to the stationary law is nonincreasing, so the earlier-time lower bound would not constrain the later-time distance. Thus the displayed matching inequality does not follow as written. If the left side is corrected to M_*/H^{-1}_{V(x0)^{2kappa},phi}(T_epsilon,t + t), the match is not automatic: for example, with G(t) = t^{-3/2} (within the alpha > 1 row of Table 1), T_epsilon,t is of order t^{4/3}, so the corrected lower bound decays like t^{-4q/3} while the Theorem 10 upper bound decays only like t^{4/3 - q} (q = 1/(1-beta)); these rates are not comparable. The theorem needs an explicit condition such as T_epsilon,t = O(t), or a proof that the required G is fast enough, before the central 'approximately matching' claim is justified.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":19184,"tokens_out":17135,"duration_ms":172726,"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":[{"comment":"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.","section":"Section 4, paragraph after Theorem 10"},{"comment":"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.","section":"Section 3, Theorem 4"},{"comment":"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.","section":"Section 3, Example 5"}],"minor_comments":[{"comment":"There is a typographical error: 'Theoerem 10' should read 'Theorem 10'.","section":"Section 4, after Table 1"},{"comment":"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.","section":"Supporting technical results, Proposition 17"},{"comment":"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.","section":"Section 5, Propositions 11 and 12"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Lower bounds first. The paper does something genuinely useful: it proves subgeometric lower bounds for adaptive MCMC that hold uniformly over all adaptation strategies, in both total variation (Theorem 1) and weak Wasserstein distance (Theorem 4). The technique—simultaneous drift plus tail discrepancy—extends Hairer and Douc et al. in a clean way, and the proof of Theorem 1 is straightforward and correct. The weak lower bound has a small statement gap: compact sublevel sets don't imply continuity of W, which the proof silently uses. That's fixable, but it should be stated.\n\nThe upper bounds in Section 4 are a real attempt at a hard problem. Theorem 10 gives an explicit total variation bound under quantitative diminishing adaptation, and the coupling argument is detailed and plausible. I believe the theorem itself probably holds as stated. What does not hold is the advertised \"approximately matching\" claim after Theorem 10. The displayed inequality puts the lower bound from Theorem 1 at time t against the upper bound at time T_{epsilon,t}+t. The adaptive marginal is not Markov, and no monotonicity of TV distance is established. Even for a fixed chain, TV distance to stationarity is nonincreasing, which would go the wrong way. So the displayed match is not proved. With G(t)=t^{-3/2}, T is of order t^{4/3}, and the corrected rates are not comparable. The authors need either to prove T=O(t) under suitable G, or downgrade the claim. This is one gap in the central narrative, not a refutation of the lower bounds.\n\nExample 5 also asserts a tail inequality without justification, and several constants are non-explicit. Those are minor compared to the matching issue.\n\nMy bottom line: the lower bounds are a solid contribution worth citing, and Theorem 10 is a worthwhile upper bound if the matching claim is repaired. The paper deserves a serious referee, but the referee should insist on fixing the comparison after Theorem 10. This is a conditional accept.","headline":"Solid adaptive MCMC lower bounds and a promising upper bound, but the advertised rate matching after Theorem 10 is not actually proven.","tokens_in":19677,"tokens_out":2576,"would_cite":true,"duration_ms":24535,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60J27","60J22","60G07"],"pacs":[],"model":"deepseek-v4-flash","headline":"Adaptive MCMC has a universal slow-convergence floor set by the target's tail and drift.","keywords":["adaptive Metropolis-Hastings","lower bounds for adaptive MCMC","upper bounds for adaptive MCMC","weak convergence of adaptive MCMC","subgeometric convergence","quantitative diminishing adaptation"],"falsifier":"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.","tokens_in":18691,"feed_emoji":"⏳","tokens_out":9589,"duration_ms":85802,"temperature":0.7,"pith_summary":"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.","feed_headline":"Adaptive MCMC hits a slow-convergence floor","feed_subtitle":"New bounds say heavy-tailed targets slow all tuning strategies; fast-diminishing adaptation matches them.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the tail-discrepancy technique for total variation lower bounds (its Theorem 3.6, Corollary 3.7) that Theorem 1 adapts to the adaptive setting.","marker":"[9]"},{"why":"Provides polynomial-rate lower bounds in unbounded Wasserstein distances for Markov processes, the starting point for the weak-convergence lower bound in Theorem 4.","marker":"[17]"},{"why":"Establishes the practical drift conditions and the H/φ calculus for subgeometric rates used throughout the upper-bound arguments and rate computations.","marker":"[4]"},{"why":"Defines adaptive MCMC and the standard diminishing adaptation condition that Definition 7 strengthens with a quantitative decay rate.","marker":"[16]"},{"why":"Provides ergodicity results for adaptive MCMC and the Lipschitz-continuity bounds for Gaussian proposals used to verify quantitative diminishing adaptation.","marker":"[2]"},{"why":"Supplies subgeometric Wasserstein upper bounds and local-coupling arguments that Theorem 10's upper bound builds on.","marker":"[6]"},{"why":"Gives V-subgeometric ergodicity conditions for Metropolis–Hastings used in the random-walk example (Lemma 15).","marker":"[7]"}],"fun_headline_variants":["Adaptive MCMC can't outrun tail-limited convergence","Lower bound proves adaptive MCMC slow floor; fast tuning matches it","Subgeometric speed limit for adaptive MCMC, matched by fast adaptation","Heavy tails set adaptive MCMC pace; quick adaptation approaches it","Adaptive MCMC convergence: lower bound universal, upper matches when fast"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive MCMC can't outrun tail-limited convergence","Lower bound proves adaptive MCMC slow floor; fast tuning matches it","Subgeometric speed limit for adaptive MCMC, matched by fast adaptation","Heavy tails set adaptive MCMC pace; quick adaptation approaches it","Adaptive MCMC convergence: lower bound universal, upper matches when fast"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000262,"raw_usage":{"total_tokens":1540,"prompt_tokens":832,"completion_tokens":708,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":448,"completion_tokens_details":{"reasoning_tokens":617}},"tokens_in":448,"tokens_out":708,"duration_ms":7540,"temperature":1.0,"reasoning_tokens":617,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:33:36.543976+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"How hot can a heat bath get? Communications in Mathematical Physics, 292(1):131–177, 2009","cited_arxiv_id":null,"evidence_quote":"Supplies the tail-discrepancy technique for total variation lower bounds (its Theorem 3.6, Corollary 3.7) that Theorem 1 adapts to the adaptive setting."},{"cited_title":"Roberts and Jeffrey S","cited_arxiv_id":null,"evidence_quote":"Provides polynomial-rate lower bounds in unbounded Wasserstein distances for Markov processes, the starting point for the weak-convergence lower bound in Theorem 4."},{"cited_title":"Practical drift conditions for subgeometric rates of convergence","cited_arxiv_id":null,"evidence_quote":"Establishes the practical drift conditions and the H/φ calculus for subgeometric rates used throughout the upper-bound arguments and rate computations."},{"cited_title":"A framework for adaptive MCMC targeting multimodal distributions","cited_arxiv_id":null,"evidence_quote":"Defines adaptive MCMC and the standard diminishing adaptation condition that Definition 7 strengthens with a quantitative decay rate."},{"cited_title":"On the ergodicity properties of some adaptive MCMC algorithms","cited_arxiv_id":null,"evidence_quote":"Provides ergodicity results for adaptive MCMC and the Lipschitz-continuity bounds for Gaussian proposals used to verify quantitative diminishing adaptation."},{"cited_title":"Subgeometric rates of convergence in Wasserstein distance for Markov chains","cited_arxiv_id":null,"evidence_quote":"Supplies subgeometric Wasserstein upper bounds and local-coupling arguments that Theorem 10's upper bound builds on."},{"cited_title":"V-subgeometric ergodicity for a Hast- ings–Metropolis algorithm","cited_arxiv_id":null,"evidence_quote":"Gives V-subgeometric ergodicity conditions for Metropolis–Hastings used in the random-walk example (Lemma 15)."}],"review_version":1}