A mixing time bound for Gibbs sampling from log-smooth log-concave distributions

Neha S. Wadia

REVIEW 2 major objections 4 minor 1 cited by

A mixing time bound for Gibbs sampling from log-smooth log-concave distributions

T0 review · 2 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read The paper proves that lazy Gibbs sampling on log-smooth log-concave targets is rapidly mixing, with an explicit $\tilde{O}(\kappa^2 n^{7.5})$ iteration bound from an $M$-warm start.

desk verdict A new isoperimetric proof of rapid mixing for Gibbs sampling, worth refereeing despite being dominated by a concurrent linear-in-n bound and having a few localized, repairable gaps. read the letter →

arxiv 2412.17899 v1 pith:T4P2SASE submitted 2024-12-23 math.ST cs.DSstat.MLstat.TH

Neha S. Wadia This is my paper · ORCID

classification math.STcs.DSstat.MLstat.TH MSC 60J2260D0565C05

keywords Gibbssamplercoordinatehit-and-runlog-concavesamplingmixingtimeconductanceisoperimetricinequalitylog-smoothstrongly

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 a polynomial upper bound on how long the Gibbs sampler—the Markov chain that at each step picks one coordinate at random and resamples it from its conditional distribution—needs to run before it is close to a target distribution with density proportional to $e^{-f(x)}$, where $f$ is strongly convex with Lipschitz gradients. Starting from an $M$-warm initial distribution, the lazy sampler reaches total-variation error at most $\gamma$ in at most $\tilde{O}\left(\kappa^2 n^{7.5}\left(\max\{1,\sqrt{(1/n)\log(2M/\gamma)}\}\right)^2\log(2M/\gamma)\right)$ iterations, with $\kappa$ the ratio of the smoothness and strong-convexity constants of $f$. A curious reader should care because this shows that a simple, hyperparameter-free coordinate-resampling scheme mixes rapidly on a broad and practically common class of high-dimensional targets, complementing existing rapid-mixing results for the ball walk and hit-and-run. The paper's main technical contribution is an isoperimetric inequality for the target measure restricted to a mode-centered Euclidean ball, which controls the sampler's conductance and thereby the mixing time.

What carries the argument

The load-bearing mechanism is a cube-tiling isoperimetric argument. The proof embeds a mode-centered Euclidean ball in a grid of axis-aligned cubes of side $\delta$, chosen so that a Taylor bound using the global smoothness constant $L$ guarantees $f$ varies by at most $\log(6/5)$ across any cube; on such a cube the target density is nearly uniform. That near-uniformity lets the proof import a known isoperimetric inequality for the uniform distribution on a cube, apply it to each cube, and then correct for boundary cubes using a strongly log-concave isoperimetric inequality that bounds the measure of the internal boundary of the tiled set. The assembled inequality lower-bounds the conductance of the sampler, and the final iteration count follows from the conductance-to-mixing-time theorem.

What would settle it

For a concrete strongly log-concave family such as an anisotropic Gaussian with a chosen condition number $\kappa$, compute the maximum variation of $f$ over every axis-aligned cube of the side length $\delta$ defined in Eq. (36) that intersects the mode-centered ball $K$; if for any $n$ this variation exceeds $\log(6/5)$, the paper's Fact 4.1 fails on that configuration and the proof of Lemma 1.2 cannot proceed.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: for a target density proportional to $e^{-f(x)}$ with $f$ $\mu$-strongly convex and $L$-smooth, $\kappa=L/\mu$, and an $M$-warm start, the lazy Gibbs sampler satisfies $d_{\mathrm{TV}}(\pi_\tau,\pi)\le\gamma$ once $\tau \le C\kappa^2 n^{7.5}\log^2 n\left(\max\{1,\sqrt{(1/n)\log(2M/\gamma)}\}\right)^2\log(2M/\gamma)$ for a universal constant $C$. The engine behind this bound is Lemma 1.2, an axis-disjoint isoperimetric inequality: within a Euclidean ball centered at the mode and carrying at least $1-\varepsilon$ of the target mass, any partition into two axis-disjoint sets $S_1,S_2$ and a remainder $S_3$ satisfies $\Pi(S_3)\ge\Psi\min\{\Pi(S_1)/(5-\varepsilon),\Pi(S_2)/(5-\varepsilon)\}$ with $\Psi\ge C/(\kappa n^{2+3/4}\log n\max\{1,\sqrt{(1/n)\log(1/\varepsilon)}\})$. Because the sampler cannot cross between axis-disjoint sets in one step, this inequality is exactly the kind of lower bound on escape probability that a conductance argument needs, and it yields the stated mixing time when combined with the standard s-conductance-to-mixing-time theorem.

Load-bearing premise

The load-bearing premise is that each cube in the tiling is small enough that the target density is nearly uniform on it, a condition the proof checks only through a Taylor bound using the global smoothness constant; if the chosen cube size fails to keep the log-density variation within $\log(6/5)$ on every cube that matters, the isoperimetric bound, and with it the mixing-time theorem, does not follow.

Editorial extensions

If this is right

For any log-smooth strongly log-concave target, lazy Gibbs sampling from a warm start is provably rapidly mixing, so the number of coordinate resamplings needed stays polynomial in the dimension and the condition number.
Because each iteration resamples a single coordinate from a known one-dimensional conditional, the bound converts directly into a polynomial total-work guarantee whenever those conditionals can be sampled efficiently.
The warm-start assumption is mild: the paper cites a procedure that computes a warm start for any log-concave target in $O(\sqrt{n})$ iterations, so the overall algorithm remains polynomial even when initialized away from the target.
The axis-disjoint isoperimetric inequality applies to any log-smooth strongly log-concave measure and can be reused as a building block for other coordinate-constrained samplers, not only the specific chain analyzed here.
Under extra assumptions the dimension dependence improves: the paper notes that a sharper log-concave isoperimetric coefficient yields roughly $n^7$ for large $n$, and an isotropic-target variant gives an $n^{6.5}$ bound, so the proof framework supports refinements.

Reading between the lines

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

The same local-near-uniformity trick would likely extend to blocked Gibbs samplers that resample groups of coordinates, since the argument only uses axis-disjointness and cube tiling; the paper does not pursue this extension.
The large gap between the $n^{7.5}$ exponent here and the linear-in-$n$ dependence reported for the contemporaneous entropy-contraction approach suggests the true worst-case mixing time of Gibbs sampling on this class is probably far below the bound proved here.
Because the bound depends only logarithmically on $M$ and $1/\gamma$, the iteration budget degrades slowly when one asks for very accurate samples or starts far from the target; this practical feature is implicit in the bound but not highlighted.
A direct numerical study of the lazy Gibbs sampler on high-dimensional anisotropic Gaussians over a grid of $n$ and $\kappa$ could estimate the empirical exponent of $n$ in the mixing time; if it is well below $7.5$, that would support the paper's suspicion that the bound is not tight.

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.

Desk Editor's Note

read the letter

First, you should know: the paper gives a polynomial mixing time bound for Gibbs sampling from log-smooth strongly log-concave distributions, using a new isoperimetric inequality. It is a genuine technical advance, but the headline mixing time is dominated by the concurrent linear-in-n result of Ascolani, Lavenant, and Zanella, which the authors themselves cite. So the practical value of the main theorem is modest; the isoperimetric lemma is the more interesting piece.

The paper does well in its structure and use of existing tools. Lemma 1.2, the cube tiling isoperimetric inequality for log-concave measures, is genuinely new as far as I can tell. The idea of using local uniformity of smooth f to transfer Laddha-Vempala's uniform cube isoperimetry to a non-uniform measure is clever and worth developing. The proof is self-contained, uses standard results (Lovász-Simonovits, Dwivedi et al., Lee-Vempala) appropriately, and I see no circularity or fitting.

The soft spots are localized but real. First, Theorem 1.1 states the bound as 'tau is no more than ...' which is backwards; it should be 'at least'. That is a typo but it will confuse readers. Second, in Lemma 3.2 the displayed equality has a missing factor of 1/n; the conclusion is right if you insert it, but as written it is wrong. Third, the stress-test concern about Eq. (79) is valid: the concentration bound (57) is applied to the cube union C2, which need not lie inside the ball K. The step Pi(I) > Pi(C2) - epsilon is unsupported as written. That said, the gap is easily repaired by applying (57) to C2 ∩ S1, which is inside K, giving the same lower bound Pi(I) ≥ (1/2)Pi(S1) - epsilon. So this is a minor revision, not a fatal flaw. I should also note the paper does not explicitly say the theorem is for the lazy chain, though the proof uses laziness; that is fine up to a constant factor but should be stated.

Overall, the paper deserves a serious referee. The isoperimetric lemma is a real contribution, and the proof strategy may be useful even if the final n-dependence is not competitive. I would send it to peer review, with the expectation that the author tightens Eq. (79), fixes the typographical issues, and clarifies the lazy-chain framing. If those are addressed, it is publishable as a technical result.

Referee Report

2 major / 4 minor

Summary. The paper establishes an upper bound on the mixing time of the Gibbs sampler (coordinate hit-and-run) for log-smooth, strongly log-concave target distributions on R^n. The main theorem (Theorem 1.1) states that, from an M-warm initial distribution and for any γ in (0,1/2), the total variation distance to the target is at most γ within O*(κ^2 n^{7.5} max{1, ((1/n) log(2M/γ))^{1/2}}^2) iterations. The proof combines the Lovász-Simonovits s-conductance mixing time bound with a new isoperimetric inequality (Lemma 1.2) for subsets of a high-probability Euclidean ball. The isoperimetric inequality is proved by a cube-tiling argument that exploits the approximate local uniformity of the density, building on the cube isoperimetry of Laddha and Vempala and the log-concave isoperimetric theorem of Lee and Vempala. The paper also discusses an improved bound for large n using Chen's isoperimetric estimate and an isotropic-position variant.

Significance. If correct, this is the first explicit polynomial mixing time bound for the Gibbs sampler on unbounded strongly log-concave targets with a clear n^7.5 dependence, complementing the uniform-distribution results of Laddha-Vempala and Narayanan-Srivastava. The proof strategy is coherent and builds on independently established results; it does not assume its own conclusion. The main technical contribution is the cube-based isoperimetric inequality for log-smooth log-concave measures, which is likely to be of independent interest. The paper is honest about the relation to the contemporaneous KL-contraction result of Ascolani, Lavenant, and Zanella. However, the proof as written contains a gap in the application of the concentration bound in Case 2 of Lemma 1.2 and an unstated normalization assumption about the smoothness constant; these need to be repaired before the result can be considered fully justified.

major comments (2)

[Section 4.2.2, Eq. (79)] The inequality Π(I) = Π(K' ∩ C2) > Π(C2) − ε applies the concentration bound (57) with X = C2, but (57) is derived only for subsets of K. The set C2 is a union of grid cubes that intersect S1, and these cubes may cross the boundary of K, so C2 is not necessarily contained in K. Consequently the displayed inequality is unsupported. This lower bound on Π(I) is used in (82) to obtain min{Π(I), Π(K'\I)} ≥ (1/5)Π(S1) − ε, which feeds directly into the final isoperimetric bound (83). A possible repair is to apply (57) to C2 ∩ S1 (which is contained in K) and use K' ∩ C2 ∩ S1 ⊆ I, giving Π(I) ≥ Π(C2 ∩ S1) − ε ≥ (1/2)Π(S1) − ε, and then re-verify the minimization leading to (82). The proof should be corrected along these lines or by another valid argument.
[Section 4.2.2, Eqs. (53)-(54) and Section 4.1.1, Eq. (37)] The proof appears to rely on an unstated normalization of the smoothness constant. With the stated choice δ = (8c√κ L n^{1+σ} M)^{-1}, the Taylor bound (34) gives a first term proportional to r(ε)/(√L n^σ), not 1/(c n^σ) as claimed in (37); the displayed bound (38) is therefore only valid if L = 1 or a scaling reduction is made. Relatedly, the paper claims in (54) that L > max{1/(n log^2 n), μ} ensures α ≤ 1/2, but α = 1/(4√κ L√n log n M) and the stated lower bound on L does not imply L ≥ 1/(2√n log n) for n ≥ 10, so α can exceed 1/2 and even exceed 1. The proof should either state the standard reduction to L = 1 by scaling coordinates (which preserves the mixing time in number of steps and the warmness parameter) or carry the dependence on L through all subsequent inequalities. As written, the proof does not cover the full parameter range stated in Theorem 1.1.

minor comments (4)

[Lemma 3.2, proof] The displayed equality P_y(ℓ_j ∩ A2) + P_z(ℓ_j ∩ A1) = Π(ℓ_j ∩ A2|y_{−j}) + Π(ℓ_j ∩ A1|z_{−j}) = Π(ℓ_j) = 1/n is not correct as written: P_x(A) includes the factor 1/n for the random coordinate choice, and Π(ℓ_j), the marginal probability of a single line, is zero rather than 1/n. The intended identity is P_y(ℓ_j ∩ A2) + P_z(ℓ_j ∩ A1) = (1/n)[Π(ℓ_j ∩ A2|y_{−j}) + Π(ℓ_j ∩ A1|y_{−j})] = 1/n, and the contradiction argument can be fixed by inserting the missing 1/n factors.
[Eq. (30)] The constant 25102 in the display τ < 25102 n^2/Ψ^2 log(2M/γ) appears to be a typographical error; substituting φ_s > Ψ/(40n) into (29) yields a factor of 2·40² = 3200, not 25102.
[Eq. (36) and surrounding text] The definition of δ is hard to parse because of the formatting of the superscript -1; the expression should be written explicitly as δ = (8c√κ L n^{1+σ} M)^{-1} with M = max{1, ((1/n) log(1/ε))^{1/2}}, to avoid ambiguity.
[Section 4.2.2, paragraph before Eq (55)] The proof defines K' as the α-shrinkage of K and then separately assigns R' = r(ε)√(n/μ); since R' = (1−α)R, these two statements determine α from R. The ordering of the choices (R, α, R') should be clarified, e.g., by choosing R' = r(ε)√(n/μ) first and then setting α = 1 − R'/R, which is consistent with the interval condition on R.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the mixing-time theorem follows from external conductance and isoperimetric results and explicit constant choices, not from its own conclusion.

full rationale

The derivation is self-contained in the relevant sense. Theorem 1.1 is obtained by combining Lovasz-Simonovits's mixing-time bound (Theorem 2.1), the Dwivedi-Chen-Wainwright-Yu concentration lemma (Lemma 3.1), the Laddha-Vempala and Fernandez cube isoperimetry (Lemma 4.4), and the Lee-Vempala log-concave isoperimetric theorem (Theorem 4.6), none of which is supplied by this paper or presupposes its conclusion. The new ingredient, Lemma 1.2, is proved from Taylor expansion: Eq. (38) controls |f(y)-f(x)| on cubes of side delta chosen explicitly in Eq. (36), and Fact 4.1 converts this into a uniformity ratio. The constants sigma and c are then chosen (sigma = log log n / log n, c = 8) only to satisfy the inequality |f(y)-f(x)| <= log(6/5), and the final Psi is assembled from the universal constants psi_c and psi_pi. No parameter is fitted to the quantity being bounded, and no load-bearing citation is to the author's own prior work. The skeptically noted concern about Eq. (79) - namely, that (57) is stated for X subset K while C2 may cross the boundary of K - is a potential correctness gap in the Case 2 conductance argument, not a circularity, since the missing step would use the same concentration lemma rather than assuming the mixing-time conclusion. That concern therefore does not change the circularity score.

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

The proof introduces no new physical or mathematical entities. It relies on external isoperimetric and concentration theorems from the cited literature. The constants c, sigma, and h are proof parameters fixed to make inequalities hold, not empirical fits; they do not create circularity because the final bound is derived from conductance, not from the target quantity.

free parameters (3)

c = 8
Universal constant chosen in Eq. (36) so that |f(y)-f(x)| <= log(6/5) on each cube; not fitted to data.
sigma = log log n / log n
Exponent chosen to balance the approximation error in Eq. (37) against the final mixing-time dependence; universal and n-dependent, not data-fitted.
h = 1/3
Threshold in the cube-neighbor argument (Eqs. (72)-(73)), chosen as a constant below 125/324; universal, not data-fitted.

assumptions (7)

domain assumption f is mu-strongly convex and has L-Lipschitz gradients, with L >= mu > 0
This is the class of target distributions studied; it is the setting of Theorem 1.1.
domain assumption The initial distribution pi0 is M-warm with respect to pi
Warmness appears in the theorem statement and in the Lovasz-Simonovits bound (15).
standard math Lovasz-Simonovits s-conductance to mixing time theorem (Theorem 2.1)
Used to convert the s-conductance lower bound into the mixing time estimate; cited from [21].
standard math Dwivedi-Chen-Wainwright-Yu concentration bound for strongly log-concave measures (Lemma 3.1)
Used to choose the high-probability ball K; cited from [25].
standard math Laddha-Vempala cube isoperimetry with Fernandez's improved coefficient (Lemma 4.4)
The base isoperimetric bound on axis-aligned cubes; cited from [16] and [26].
standard math Lee-Vempala log-concave isoperimetric theorem (Theorem 4.6)
Provides the boundary-measure lower bound Psi_pi in Lemma 1.2; cited from [27].
standard math Chen's improved isoperimetric bound used in the discussion (Eq. (84))
Used only for the improved large-n bound in the discussion; cited from [28].

how reviews work

0 comments

Cite this review

Pith. "Pith review of A mixing time bound for Gibbs sampling from log-smooth log-concave distributions." pith.science (2026). https://pith.science/paper/T4P2SASE

@misc{pith2026241217899,
  author       = {Pith},
  title        = {Pith review of: A mixing time bound for Gibbs sampling from log-smooth log-concave distributions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/T4P2SASE}},
  note         = {Machine review of arXiv:2412.17899}
}

abstract

The Gibbs sampler, also known as the coordinate hit-and-run algorithm, is a Markov chain that is widely used to draw samples from probability distributions in arbitrary dimensions. At each iteration of the algorithm, a randomly selected coordinate is resampled from the distribution that results from conditioning on all the other coordinates. We study the behavior of the Gibbs sampler on the class of log-smooth and strongly log-concave target distributions supported on $\mathbb{R}^n$. Assuming the initial distribution is $M$-warm with respect to the target, we show that the Gibbs sampler requires at most $O^{\star}\left(\kappa^2 n^{7.5}\left(\max\left\{1,\sqrt{\frac{1}{n}\log \frac{2M}{\gamma}}\right\}\right)^2\right)$ steps to produce a sample with error no more than $\gamma$ in total variation distance from a distribution with condition number $\kappa$.

Figures

Figures reproduced from arXiv: 2412.17899 by the authors.

**Figure 1.** Illustrated here is a partition A1 ∪ A2 of R 2 such that for some s ∈ (0, 1/2), s < Π(A1) ≤ 1/2. The Euclidean ball K is centered at the mode x ⋆ of π and is large enough so that its measure differs from unity by a fraction of s. A′ 1 (in light pink) and A′ 2 (in light blue) are subsets of A1 and A2, respectively. A′ 1 and A′ 2 are axis disjoint. S1 ∪S2 ∪S3 is a partition of K such that Si = K ∩ A′ i for i = 1, 2. Π… view at source ↗

**Figure 2.** Pictured here is a cube of side δ. β, shaded in light yellow, is a facet normal to the e3 coordinate axis. βa, shaded in gray, is the set that results from translating β along the e3 axis to x3 = a. ω is the subset of β shaded in a darker yellow, and ωa is the subset of βa shaded in a darker gray. Outlined in black is the extension B of ω along e3 in the cube. Fact 4.2. Let w ≡ arg minx∈C f(x). For any S ⊆ C ⊂ K, we… view at source ↗

**Figure 3.** The Euclidean ball K is embedded in a grid of cubes of side δ. Shaded in purple is the set of cubes in the bulk set C2 covering S1. In orange is the boundary set C1. Summing (61) over all c ∈ C ′ 1 , we have Π(S3) ≥ X c∈C′ 1 Π(c ∩ S3) ≥ ψc 4 e −ν X c∈C′ 1 Π(c ∩ S1) = ψc 4 e −νΠ(C ′ 1 ∩ S1). To lower bound Π(C ′ 1 ∩ S1), note that while C ′ 1 may not be fully contained in K′ , the set C1 ∩ K′ is, and therefore Π(C ′ … view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: The part of β underneath the dashed line is Pβ(S1 ∩ v), the projection of S1 ∩ v onto β. The part of u underneath the dashed line is Eu(Pβ), the extension of Pβ(S1 ∩ v) in u along the coordinate direction normal to β. The subset of this region shaded with lines is the …

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

Mixing-Free and Signal-Optimal Learning of Gaussian Graphical Models from Glauber Dynamics
stat.ML 2026-07 accept novelty 7.0 of 10

Exact graph recovery from one Glauber trajectory is provably achievable at the information-theoretic κ^{-2} sample rate without mixing or stationarity assumptions, via a dueling-neighborhood search with two local traj...

Reference graph

Works this paper leans on

29 extracted references · 27 canonical work pages · cited by 1 Pith paper

[1]

Rosenbluth, Marshall N

Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. Equation of state calculations by fast computing machines. J. Chem. Phys. 21, 1087, 21:1087–1092, 1953

work page 1953
[2]

W. K. Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57:97–109, 1970

work page 1970
[3]

Random walks and an O∗(n5) volume algorithm for convex bodies

Ravi Kannan, L´ aszl´ o Mikl´ os Lov´ asz, and Mikl´ os Simonovits. Random walks and an O∗(n5) volume algorithm for convex bodies. Random Struct. Algorithms , 11:1–50, 1997

work page 1997
[4]

The geometry of logconcave functions and sampling algorithms

Laszl´ o Lov´ asz and Santosh Vempala. The geometry of logconcave functions and sampling algorithms. Random Structures & Algorithms , 30:307–358, 2007

work page 2007
[5]

M. Dyer, A. Frieze, and R. Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the Association for Computing Machinery , 38(1):1–17, 1991

work page 1991
[6]

Lov´ asz and S

L. Lov´ asz and S. Vempala. Simulated annealing in convex bodies and an O ∗(n4) volume algo- rithm. Journal of Computer and System Sciences , 72:392–417, 2006

work page 2006
[7]

Preduce — a probabilistic algorithm identifying redundancy by a random feasible point generator (RFPG)

Arnon Boneh. Preduce — a probabilistic algorithm identifying redundancy by a random feasible point generator (RFPG). In Redundancy in Mathematical Programming, pages 108–134, Berlin, Heidelberg, 1983. Springer Berlin Heidelberg

work page 1983
[8]

Robert L. Smith. Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions. Operations Research, 32(6):1296–1308, 1984

work page 1984

Show all 29 references

[9]

Hit-and-Run from a corner.SIAM Journal on Computing , 35:310–314, 2004

L´ aszl´ o Lov´ asz and Santosh Vempala. Hit-and-Run from a corner.SIAM Journal on Computing , 35:310–314, 2004

2004
[10]

Santosh S. Vempala. Geometric random walks: a survey. Combinatorial and Computational Geometry, 52, 2005

2005
[11]

V. F. Turchin. On the computation of multidimensional integrals by the Monte-Carlo method. Theory of Probability & Its Applications , 16(4):720–724, 1971. 21

1971
[12]

Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images

Stuart Geman and Donald Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI- 6(6):721–741, 1984

1984
[13]

Gelfand and Adrian F

Alan E. Gelfand and Adrian F. M. Smith. Sampling-based approaches to calculating marginal densities. Journal of the American Statistical Association , 85:398–409, 1990

1990
[14]

Kannan, L

R. Kannan, L. Lov´ asz, and M. Simonovits. Isoperimetric problems for convex bodies and a localization lemma. Discrete & Computational Geometry , 13:541—-559, 1995

1995
[15]

Lectures on glauber dynamics for discrete spin models

Fabio Martinelli. Lectures on glauber dynamics for discrete spin models. In Pierre Bernard, editor, Lectures on Probability Theory and Statistics: Ecole d’Et´ e de Probailit´ es de Saint-Flour XXVII - 1997 , pages 93–191. Springer Berlin Heidelberg, Berlin, Heidelberg, 1999

1997
[16]

Aditi Laddha and Santosh S. Vempala. Convergence of Gibbs sampling: Coordinate hit-and-run mixes fast. Discrete Comput. Geom. , 70(2):406–425, apr 2023

2023
[17]

On the mixing time of coordinate hit-and-run

Hariharan Narayanan and Piyush Srivastava. On the mixing time of coordinate hit-and-run. Combinatorics, Probability and Computing , 31(2):320—-332, 2022

2022
[18]

Sampling from convex sets with a cold start using multiscale decompositions

Hariharan Narayanan, Amit Rajaraman, and Piyush Srivastava. Sampling from convex sets with a cold start using multiscale decompositions. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , STOC 2023, pages 117—-130, New York, NY, USA,

2023
[19]

Entropy contraction of the Gibbs sampler under log-concavity

Filippo Ascolani, Hugo Lavenant, and Giacomo Zanella. Entropy contraction of the Gibbs sampler under log-concavity. arXiv:2410.00858, 2024

2024
[20]

Altschuler and Sinho Chewi

Jason M. Altschuler and Sinho Chewi. Faster high-accuracy log-concave sampling via algorith- mic warm starts. J. ACM, 71:1–55, 2024

2024
[21]

Lov´ asz and M

L. Lov´ asz and M. Simonovits. Random walks in a convex body and an improved volume algorithm. Random Structures & Algorithms , 4(4):359–412, 1993

1993
[22]

Conductance and the rapid mixing property for Markov chains: the approximation of permanent resolved

Mark Jerrum and Alistair Sinclair. Conductance and the rapid mixing property for Markov chains: the approximation of permanent resolved. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing , STOC ’88, page 235–244, New York, NY, USA,
[23]

A lower bound for the smallest eigenvalue of the laplacian

Jeff Cheeger. A lower bound for the smallest eigenvalue of the laplacian. In Problems in Analysis, pages 195–199. Princeton University Press, 1970

1970
[24]

Random walks on graphs: A survey

L´ aszl´ o Lov´ asz. Random walks on graphs: A survey. InCombinatorics, Paul Erd˝ os is Eighty, volume 2, pages 1–46. J´ anos Bolyai Mathematical Society, 1993

1993
[25]

Wainwright, and Bin Yu

Raaz Dwivedi, Yuansi Chen, Martin J. Wainwright, and Bin Yu. Log-concave sampling: Metropolis-Hastings algorithms are fast. Journal of Machine Learning Research , 20(183):1– 42, 2019

2019
[26]

On the ℓ0 isoperimetric coefficient of measurable sets

Manuel Fernandez V. On the ℓ0 isoperimetric coefficient of measurable sets. arXiv:2312.00015, 2024

2024 arXiv
[27]

Yin Tat Lee and Santosh S. Vempala. Eldan’s stochastic localization and the KLS conjecture: Isoperimetry, concentration and mixing. Annals of Mathematics , 199:1043–1092, 2024

2024
[28]

An almost-constant lower bound of the isoperimetric coefficient in the KLS conjecture

Yuansi Chen. An almost-constant lower bound of the isoperimetric coefficient in the KLS conjecture. Geometric and Functional Analysis , 31:34–61, 2021. 22

2021
[1988]

Association for Computing Machinery

Pith tools

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

[1] [1]

Rosenbluth, Marshall N

Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. Equation of state calculations by fast computing machines. J. Chem. Phys. 21, 1087, 21:1087–1092, 1953

work page 1953

[2] [2]

W. K. Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57:97–109, 1970

work page 1970

[3] [3]

Random walks and an O∗(n5) volume algorithm for convex bodies

Ravi Kannan, L´ aszl´ o Mikl´ os Lov´ asz, and Mikl´ os Simonovits. Random walks and an O∗(n5) volume algorithm for convex bodies. Random Struct. Algorithms , 11:1–50, 1997

work page 1997

[4] [4]

The geometry of logconcave functions and sampling algorithms

Laszl´ o Lov´ asz and Santosh Vempala. The geometry of logconcave functions and sampling algorithms. Random Structures & Algorithms , 30:307–358, 2007

work page 2007

[5] [5]

M. Dyer, A. Frieze, and R. Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the Association for Computing Machinery , 38(1):1–17, 1991

work page 1991

[6] [6]

Lov´ asz and S

L. Lov´ asz and S. Vempala. Simulated annealing in convex bodies and an O ∗(n4) volume algo- rithm. Journal of Computer and System Sciences , 72:392–417, 2006

work page 2006

[7] [7]

Preduce — a probabilistic algorithm identifying redundancy by a random feasible point generator (RFPG)

Arnon Boneh. Preduce — a probabilistic algorithm identifying redundancy by a random feasible point generator (RFPG). In Redundancy in Mathematical Programming, pages 108–134, Berlin, Heidelberg, 1983. Springer Berlin Heidelberg

work page 1983

[8] [8]

Robert L. Smith. Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions. Operations Research, 32(6):1296–1308, 1984

work page 1984