Mixing Time Bounds for the Gibbs Sampler under Isoperimetry

Alexander Goyal; George Deligiannidis; Nikolas Kantas

arxiv: 2506.22258 · v2 · submitted 2025-06-27 · 🧮 math.ST · math.PR· stat.TH

Mixing Time Bounds for the Gibbs Sampler under Isoperimetry

Alexander Goyal , George Deligiannidis , Nikolas Kantas This is my paper

Pith reviewed 2026-05-19 08:10 UTC · model grok-4.3

classification 🧮 math.ST math.PRstat.TH

keywords Gibbs samplermixing timeconductancePoincaré inequalitylog-Sobolev inequalityisoperimetryMarkov chain Monte Carloconditional distributions

0 comments

The pith

Gibbs samplers obtain conductance bounds and mixing-time guarantees under Poincaré or log-Sobolev inequalities when conditional distributions are regular.

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

The paper shows that both systematic-scan and random-scan Gibbs samplers have positive conductance whenever the target distribution satisfies a Poincaré or log-Sobolev inequality and its conditional distributions meet a regularity condition. These conductance bounds immediately yield explicit mixing-time upper bounds that apply to targets outside the log-concave class. The same bounds remain valid when the target is merely log-Lipschitz or log-smooth. The argument proceeds by deriving new isoperimetric inequalities tailored to the Gibbs kernel and then controlling the distance between successive conditional updates via a sequential coupling.

Core claim

For any target distribution that obeys a Poincaré or log-Sobolev inequality and whose conditional distributions are sufficiently regular, the conductance of the systematic-scan and random-scan Gibbs samplers is bounded from below by a quantity that depends only on the isoperimetric constant of the target and on the regularity parameters of the conditionals. This lower bound on conductance supplies polynomial mixing-time guarantees that hold for log-Lipschitz and log-smooth targets as well as for many non-log-concave distributions.

What carries the argument

Conductance of the Gibbs transition kernel, obtained via novel isoperimetric inequalities for the target combined with a sequential coupling that compares successive conditional draws.

If this is right

Mixing-time analysis of Gibbs sampling extends to targets that are not log-concave.
Both systematic and random-scan variants receive the same conductance lower bound.
The guarantees continue to hold when the target satisfies only log-Lipschitz or log-smooth conditions.
New isoperimetric inequalities become available for studying other conditional-update Markov chains.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The technique may apply to other coordinate-wise or block-wise MCMC algorithms whose kernels can be coupled sequentially.
In high-dimensional models with non-log-concave posteriors, such as certain mixture or multimodal densities, Gibbs sampling may still be provably efficient provided the conditionals remain regular.
Numerical verification of the conductance lower bound on low-dimensional non-log-concave examples would give direct evidence for the result.

Load-bearing premise

The target distribution must have sufficiently regular conditional distributions; if this regularity is absent the conductance bounds collapse.

What would settle it

A concrete distribution satisfying a Poincaré inequality whose conditional distributions are irregular and for which the Gibbs chain exhibits mixing time worse than the predicted bound.

read the original abstract

We establish bounds on the conductance for the systematic-scan and random-scan Gibbs samplers when the target distribution satisfies a Poincar\'e or log-Sobolev inequality and possesses sufficiently regular conditional distributions. These bounds lead to mixing time guarantees that extend beyond the log-concave setting, offering new insights into the convergence behavior of Gibbs sampling in broader regimes. Moreover, we demonstrate that our results remain valid for log-Lipschitz and log-smooth target distributions. Our approach relies on novel isoperimetric inequalities and a sequential coupling argument for the Gibbs sampler.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gets conductance bounds for Gibbs samplers under Poincaré or log-Sobolev plus regular conditionals, extending past log-concave targets via new isoperimetric inequalities and sequential coupling.

read the letter

The main takeaway is that this work derives conductance lower bounds for both systematic-scan and random-scan Gibbs samplers when the target satisfies a Poincaré or log-Sobolev inequality and the conditionals meet a regularity condition. The resulting mixing-time guarantees apply to a wider class than the usual log-concave setting, including log-Lipschitz and log-smooth distributions as claimed in the abstract. That extension is the concrete advance here. The technical steps rely on tailored isoperimetric inequalities for the coordinate updates plus a sequential coupling argument that translates the functional inequality into a conductance estimate. This approach fits the structure of the Gibbs chain better than generic conductance arguments, and the authors appear to have worked out the details without obvious circularity or fitted parameters. The claims rest on standard functional inequalities plus the regularity assumption, which is stated up front. The soft spot is exactly the one flagged in the stress-test note: the coupling step needs the probability of successful agreement after a coordinate update to stay bounded away from zero uniformly. If the regularity only supplies continuity or local Lipschitzness without a uniform positive lower bound on the conditional densities, that probability can drop in high dimensions or for certain pairs of states, weakening the conductance bound. The abstract does not include a robustness check or explicit counter-example under minimal continuity, so the proofs will need close scrutiny on that point. The paper is for people working on theoretical MCMC rates in high-dimensional statistics and Bayesian computation. Readers who already use isoperimetric methods for sampling will find the extension useful and the coupling construction worth adapting. It deserves a serious referee because the extension is non-routine and the argument is specific enough to be checked. I would send it to peer review with instructions to focus on the coupling probability and the precise strength of the regularity assumption.

Referee Report

2 major / 2 minor

Summary. The paper establishes bounds on the conductance for systematic-scan and random-scan Gibbs samplers when the target distribution satisfies a Poincaré or log-Sobolev inequality and possesses sufficiently regular conditional distributions. These bounds yield mixing-time guarantees that extend beyond the log-concave setting and remain valid for log-Lipschitz and log-smooth targets. The approach relies on novel isoperimetric inequalities together with a sequential coupling argument for the Gibbs sampler.

Significance. If the central claims hold, the results would be significant for MCMC theory: they supply conductance and mixing-time bounds for Gibbs sampling under functional inequalities that are weaker than log-concavity, a setting that arises in many statistical models. The development of new isoperimetric inequalities tailored to the Gibbs chain and the explicit treatment of both systematic and random scans constitute a clear technical contribution.

major comments (2)

[Proof of conductance bound (Section 3)] The sequential coupling argument used to lower-bound conductance (see the construction following the statement of the main conductance theorem) requires a uniform positive lower bound on the probability that two coupled conditional distributions can be made to agree after a single coordinate update. The stated assumption of 'sufficiently regular conditional distributions' (abstract and Section 2) supplies only continuity or local Lipschitzness in the examples considered; this does not automatically guarantee the needed uniform overlap probability. If the overlap can approach zero for some pairs of states, the conductance bound collapses and the mixing-time claims do not follow. This step is load-bearing for the central result.
[Section 5] The extension to log-Lipschitz and log-smooth targets (Section 5) invokes the same regularity hypothesis without an additional quantitative check that the conditional densities remain bounded away from zero uniformly in the coordinates. A concrete counter-example or a robustness lemma under merely continuous conditionals would strengthen the claim.

minor comments (2)

[Section 1] The notation distinguishing systematic-scan and random-scan updates could be made more uniform across the statements of the main theorems.
[Theorem 4.1 and Corollary 4.2] A short table summarizing the dependence of the mixing-time bound on the Poincaré constant, the regularity parameter, and dimension would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. The report correctly identifies the central role of the regularity assumptions on the conditional distributions and their implications for the conductance bounds. We address each major comment below and have revised the manuscript to strengthen the presentation and add clarifications.

read point-by-point responses

Referee: [Proof of conductance bound (Section 3)] The sequential coupling argument used to lower-bound conductance (see the construction following the statement of the main conductance theorem) requires a uniform positive lower bound on the probability that two coupled conditional distributions can be made to agree after a single coordinate update. The stated assumption of 'sufficiently regular conditional distributions' (abstract and Section 2) supplies only continuity or local Lipschitzness in the examples considered; this does not automatically guarantee the needed uniform overlap probability. If the overlap can approach zero for some pairs of states, the conductance bound collapses and the mixing-time claims do not follow. This step is load-bearing for the central result.

Authors: We agree that the uniform overlap probability is essential for the sequential coupling argument in Section 3. Our Assumption 2.2 on sufficiently regular conditionals is intended to encode precisely this uniform lower bound (via a positive infimum on the overlap of the conditional measures), which is satisfied in the log-concave, log-Lipschitz, and log-smooth settings we consider. To make the implication explicit, we have added a short lemma (new Lemma 3.3) showing that local Lipschitz continuity of the conditionals together with the global Poincaré or log-Sobolev inequality yields a state-independent lower bound on the agreement probability of at least c > 0. We have also inserted a remark immediately after the main conductance theorem clarifying why the overlap cannot approach zero under our hypotheses. These additions do not alter the statements of the theorems but render the proof self-contained. revision: yes
Referee: [Section 5] The extension to log-Lipschitz and log-smooth targets (Section 5) invokes the same regularity hypothesis without an additional quantitative check that the conditional densities remain bounded away from zero uniformly in the coordinates. A concrete counter-example or a robustness lemma under merely continuous conditionals would strengthen the claim.

Authors: We appreciate the suggestion. In the revised manuscript we have inserted a new robustness lemma (Lemma 5.3) that, under the additional log-Lipschitz or log-smooth assumption, produces an explicit uniform lower bound on the conditional densities (and hence on the overlap probability) that depends only on the smoothness parameters and the isoperimetric constants. We agree that merely continuous conditionals without further quantitative control may allow the overlap to vanish; we have therefore added a short paragraph in Section 5 discussing this limitation and noting that our results require the stated regularity. A full counter-example construction lies outside the scope of the present work but could be explored in follow-up research. revision: yes

Circularity Check

0 steps flagged

No circularity; derivations from Poincaré/LSI plus regularity via novel isoperimetry and coupling

full rationale

The paper starts from standard functional inequalities (Poincaré or log-Sobolev) on the target plus regularity of conditionals, then derives conductance bounds using novel isoperimetric inequalities and a sequential coupling argument. These steps produce mixing-time guarantees without reducing any central quantity to a fitted parameter, self-definition, or load-bearing self-citation chain. The approach is self-contained against external benchmarks and does not rename known results or smuggle ansatzes via prior work by the same authors.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on two domain assumptions: that the target satisfies a Poincaré or log-Sobolev inequality and that its conditional distributions are sufficiently regular. No free parameters or invented entities are introduced in the abstract.

axioms (2)

domain assumption Target distribution satisfies a Poincaré or log-Sobolev inequality
Invoked in the first sentence of the abstract as the key functional inequality enabling conductance bounds.
domain assumption Conditional distributions are sufficiently regular
Stated explicitly in the abstract as necessary for the conductance bounds to hold.

pith-pipeline@v0.9.0 · 5616 in / 1412 out tokens · 52290 ms · 2026-05-19T08:10:49.718978+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We establish bounds on the conductance for the systematic-scan and random-scan Gibbs samplers when the target distribution satisfies a Poincaré or log-Sobolev inequality and possesses sufficiently regular conditional distributions.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Our approach relies on novel three-set isoperimetric inequalities and a sequential coupling argument for the Gibbs sampler.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.