Sampling Nonconvex Bodies

How do you pick a uniformly random point from a shape you can't see, when all you can do is ask whether a point is inside? Throw proposals at a notch, watch a thin strip's volume explode under thickening, pinch a dumbbell until its Poincaré constant blows up, run In-and-Out on a ring, see why nonconvex bodies cost a factor of n more than convex ones, and warm-start a sampler by annealing.

Built from the notes of the Uniform Sampling Beyond Convexity project, which studies S. S. Vempala and A. Wibisono, “The Geometry of Efficient Nonconvex Sampling” (COLT 2026, PMLR 336). The algorithm is In-and-Out of Y. Kook, S. S. Vempala and M. S. Zhang (Random Structures & Algorithms 68, 2026), an implementation of the proximal sampler of Y. T. Lee, R. Shen and K. Tian (COLT 2021) analysed by Y. Chen, S. Chewi, A. Salim and A. Wibisono (COLT 2022). Star-shaped bodies follow K. Chandrasekaran, D. Dadush and S. S. Vempala (SODA 2010). The last module follows the project's own draft on warm starts, which has not been peer reviewed. Results from the papers are labelled with their numbering; the questions and examples are written for this page. For how this subject connects to the others, see the roadmap.

Read and checkVempala–Wibisono (2026), §1–2

Sampling a body you can only query

The input is a body you cannot see, only test points against. The output should be a point that is close to uniformly distributed on it. Some hypothesis on the body is unavoidable, and two pictures show which two are needed.

The idea

The problem. X⊂Rn is a body: closed, bounded, with nonempty interior. We may call a membership oracle 1X, which answers “is x∈X?”, and the cost of an algorithm is the number of calls. The target is the uniform distribution
π(x)=1X(x)Vol(X),
and the output law ρT should satisfy Rq(ρT‖π)≤ε for a Rényi divergence (see TV, KL and Rényi divergence).
Warm start. The algorithm starts from x0∼ρ0 with ρ0≤Mπ: it never puts more than M times the uniform probability on any set. A fixed starting point is not a warm start, since a point mass has no density at all.

What was known. Convex bodies can be sampled in time polynomial in n (Dyer, Frieze and Kannan, 1991); the In-and-Out sampler needs O~(n2) queries from a warm start in a well-rounded convex body. Star-shaped bodies, where some convex core sees every point, can be sampled with cost polynomial in 1/ε. For general bodies the problem is intractable in the worst case: a body can hide almost all of its volume behind a tiny opening.

Obstruction 1: a bottleneck. Two balls joined by a thin neck. Any process that moves by small local steps needs a very long time to cross the neck, so its distribution stays lopsided. This is measured by the Poincaré constant CPI of π (Bottlenecks and the Poincaré constant), which is huge for a dumbbell.

Obstruction 2: thinness. A cylinder [0,1]×wBn−1 of length 1 and tiny radius w has no bottleneck: CPI=1/π2 for every w. But a Gaussian step of variance h moves about h(n−1) sideways, so it stays inside only if h≲w2/n. Crossing distance 1 then takes about 1/h≳n/w2 steps. This is measured by volume growth (Thickenings and volume growth): thin sets gain a lot of volume when thickened.

The theorem (Vempala–Wibisono 2026, Theorem 1, informal). If π satisfies a Poincaré inequality with constant CPI, X satisfies (α,β)-volume growth, and the start is M-warm, then In-and-Out reaches Rq(ρT‖π)≤ε with
O~(qCPIαβ2Mn3log4⁡(1/ε))
membership queries in expectation. Convexity is not assumed.

The proof splits into two halves that never interact. The number of iterations comes from the Poincaré inequality alone (In-and-Out). The cost of each iteration comes from volume growth alone (Halfspaces versus balls and What an iteration costs).

Check your understanding

Why can't a sampler simply start at a known point x0∈X and call that its warm start?

  1. A point mass is not M-warm for any M: it puts probability 1 on a set of volume 0.
  2. Because x0 might lie on the boundary.Even an interior point fails: warmness compares probabilities of sets, and {x0} has π-probability 0.
  3. It can; warmness only matters for convex bodies.Warmness enters the cost bound linearly, through M, for every body.
One iteration of a Gaussian sampler spreads a point mass into a density, but a very peaked one, with M exponential in n. Producing a start with small M is a problem of its own: see Warm starts by annealing.

A long thin cylinder has CPI=O(1). What goes wrong for a local sampler as the radius w→0?

  1. Steps must shrink like w/n to stay inside, so crossing the cylinder takes about n/w2 steps.
  2. The sampler gets stuck at one end, as in a dumbbell.There is no bottleneck: the cylinder is convex and isoperimetry stays good.
  3. Nothing: the Poincaré constant controls the cost.It controls the number of iterations at a fixed step size, not how small the steps must be.
The cost depends on two things: how far the walk must travel (isoperimetry) and how small each step must be (thinness, measured by volume growth).

Practice

The thin cylinderGood isoperimetry, bad volume growth

Let Cw=[0,1]×wBn−1. Show that its uniform distribution has CPI=1/π2 once w is small, and that Vol((Cw)t)/Vol(Cw)≥(1+t/w)n−1.

Outline
  1. The uniform law on a product is the product of the uniform laws, and Poincaré constants of products are the maximum of the factors' constants.
    Why?

    Tensorization of variance: Var(ϕ)≤E[Var1ϕ]+E[Var2ϕ], and apply each factor's inequality to its partial gradient.

  2. The factors are [0,1], with constant 1/π2, and the ball wBn−1, with constant O(w2/n).
    Why?

    The interval's constant is attained by cos⁡(πx); the ball's comes from its covariance, w2/(n+1) per coordinate, by the KLS bound for balls.

  3. (Cw)t⊇[0,1]×(w+t)Bn−1.
    Why?

    Thickening the disk by t inside each slice. Its volume is (1+t/w)n−1 times that of Cw.

So β in the volume growth condition must be at least of order 1/w, while CPI stays bounded: the two conditions measure different things.

Interactivevon Neumann (1951); Kook–Vempala–Zhang (2026), §3.3

Rejection sampling with a budget

To sample from a distribution restricted to a set you can only test membership in, propose from the unrestricted distribution and throw away proposals that miss. The result is exact. The cost is random, and averaging that cost over many starting points can make it infinite.

The idea

The task. Given a point y, a step size h and a set X⊂Rn that you can query (“is x∈X?”), draw from N(y,hI) conditioned on landing in X. Rejection sampling repeats: propose x′∼N(y,hI); if x′∈X, stop and output x′; otherwise try again. Each trial succeeds independently with probability

ℓ=Pr(y+hZ∈X),Z∼N(0,In).

The output has exactly the right law. Summing over the trial k at which the first success happens,
Pr(output∈A)=∑k≥1(1−ℓ)k−1Pr(x′∈A∩X)=Pr(x′∈A∩X)ℓ=Pr(x′∈A∣x′∈X).
The number of trials G is geometric. Pr(G=k)=(1−ℓ)k−1ℓ, with mean EG=1/ℓ. A point just outside a thin part of X can have tiny ℓ and an enormous expected cost.
A budget of N trials. Stop after N failures and declare failure. Then
Pr(failure)=(1−ℓ)N≤e−Nℓ,Emin{G,N}=1−(1−ℓ)Nℓ≤min{1ℓ,N}.
The budget trades a small chance of failure for a guaranteed bound on the work.

The general version. To sample a density p using proposals from a density g with p≤Mg, accept a proposal x with probability p(x)/(Mg(x)). The acceptance probability is 1/M, and accepted points have density exactly p. Restricting to a set is the case p=g1X/ℓ, M=1/ℓ, where the acceptance test is just “is x∈X?”.

Why the budget is not optional. In a sampler the start y is itself random. The expected cost is then E[1/ℓ(y)], which can be infinite even though every single ℓ(y) is positive. That happens when y lands in regions of tiny conductance with probability comparable to that conductance. On the Sampling Nonconvex Bodies page this is exactly what happens: the average of 1/ℓ over a stationary forward step equals Vol(Rn)/Vol(X)=∞.

Explore

Drag y. proposals inside X (accepted) and outside (rejected). The dashed circle has radius 2h, the typical length of a step in the plane.
Pr(G=k) for the current ℓ. the bars beyond the budget N: their total is the failure probability.

Worked example

A point with local conductance ℓ=14 and a budget of N=6 trials.

  1. How many trials does it take on average without a budget?

    EG=1/ℓ=4.

  2. What is the chance of failure with the budget?

    (3/4)6≈0.178, about one in six. The bound e−Nℓ=e−1.5≈0.223 is close.

  3. How many trials are used on average with the budget?

    (1−(3/4)6)/14≈3.29: a little below 4, because the long runs are cut off at 6.

  4. How large must N be for failure probability at most 10−3?

    Need (3/4)N≤10−3, i.e. N≥ln⁡(1000)/ln⁡(4/3)≈24.0, so N=25. The e−Nℓ bound asks for N≥4ln⁡1000≈27.6, a little more.

Check your understanding

Rejection sampling with a budget fails with probability 0.01. Conditioned on succeeding, is the output still exactly distributed as N(y,hI) restricted to X?

  1. Yes: given that some trial among the first N succeeds, the first successful trial is still a fresh proposal conditioned on landing in X.
  2. No: the budget biases the output towards points that are easy to reach.Every trial has the same law, so which trial succeeds first is independent of where it lands.
Truncation changes how often you get an output, not what the output looks like. Bias appears only later, when y is random and failures are more likely from some y than others.

The start y is random with ℓ(y) uniform on (0,1]. What is the expected number of trials without a budget?

  1. 2.That is 1/E[ℓ]. The expected cost is E[1/ℓ], which is larger.
  2. Infinite: E[1/ℓ]=∫01du/u=∞.
  3. ln⁡2.The integral ∫01du/u diverges at 0.
Every individual y has finite expected cost, but rare y with tiny ℓ cost so much that the average diverges. A budget N caps the cost at ∫01min(1/u,N)du=1+ln⁡N.

In the figure, drag y deep inside the set and then far outside it. What happens to ℓ, and why does a larger spread h not always help?

  1. ℓ is near 1 inside and tiny far outside. A larger spread helps a point just outside reach X, but it also sends proposals from a point inside out of X.
  2. ℓ is always about 12 near the set.That holds only right at a flat piece of boundary; corners and thin parts change it.
This tension is why samplers tie the step size to how thin the set is: here, to the arm width.

Practice

The truncated meanCompute E min(G, N)

Show that Emin{G,N}=(1−(1−ℓ)N)/ℓ for G geometric with success probability ℓ.

Outline
  1. For a nonnegative integer variable, EM=∑k≥0Pr(M>k).
    Why?

    M=∑k≥01{M>k}; take expectations.

  2. Pr(min{G,N}>k)=(1−ℓ)k for k<N, and 0 for k≥N.
    Why?

    G>k means the first k trials all failed.

  3. Sum the geometric series ∑k=0N−1(1−ℓ)k.
    Why?

    It equals (1−(1−ℓ)N)/ℓ.

Exactness of the general methodAccept with probability p/(Mg)

Let p≤Mg. Propose x∼g and accept with probability p(x)/(Mg(x)). Show that the acceptance probability is 1/M and that accepted points have density p.

Outline
  1. Pr(accept,x∈A)=∫Ag(x)p(x)Mg(x)dx=1M∫Ap.
    Why?

    Condition on the proposal x, then integrate over it.

  2. Take A=Rn to get Pr(accept)=1/M, then divide.
    Why?

    Pr(x∈A∣accept)=∫Ap.

Key terms in plain words

The ideas above without the symbols. Switch to Quiz me to test yourself: you see an explanation and pick the term it describes.

Rejection sampling
Drawing from an easy distribution and keeping a draw only if it passes a test, so that the kept draws follow the harder distribution exactly.
Local conductance
The chance that one proposal from a given point lands inside the set: the success probability of each trial.
Geometric distribution
The number of independent tries needed until the first success; its average is one over the success probability.
Trial budget
A cap on the number of tries, after which the procedure gives up, making the work bounded at the price of a small failure probability.
Interactivevan Erven–Harremoës (2014); Cover–Thomas, §2.3 and §11.6

TV, KL and Rényi divergence

To say a sampler is “close to uniform” you need a way to measure how far apart two distributions are. Total variation, Kullback–Leibler and Rényi divergence answer that question differently, and the differences decide which one a proof can use.

The idea

Everything is a function of one ratio. Let ρ and π be distributions with ρ≪π: ρ puts no mass where π puts none. Their likelihood ratio is f=dρ/dπ, which for densities is just f(x)=ρ(x)/π(x). It satisfies f≥0 and Eπ[f]=∫ρ=1, and ρ=π exactly when f≡1. Each divergence below measures how far f is from the constant 1, with a different emphasis.

Total variation. TV(ρ,π)=supA|ρ(A)−π(A)|=12∫|ρ(x)−π(x)|dx. If you are handed one sample, from ρ or π with probability 12 each, the best guess of which is right with probability 12(1+TV).
Kullback–Leibler divergence. KL(ρ‖π)=Eρ[ln⁡f]=∫ρln⁡ρπ. It is the average evidence, in nats, that one sample from ρ gives for “ρ” over “π”. It is also the extra code length paid for using a code built for π on data from ρ. It is ≥0, with equality only at ρ=π (Gibbs' inequality). It is written D(ρ‖π) on the Information Theory page.
Rényi divergence of order q>1.
Rq(ρ‖π)=1q−1ln⁡Eπ[fq].
By Jensen, Eπ[fq]≥(Eπf)q=1, so Rq≥0. The order q sets how hard places where ρ overloads π (large f) are penalised.
orderRq becomeswhat it measures
q→1KL(ρ‖π)the average of ln⁡f under ρ
q=2ln⁡(1+χ2(ρ‖π)), with χ2=Varπ(f)the variance of the ratio
q→∞R∞=ln⁡supxf(x)the worst ratio: ρ is M-warm iff R∞≤ln⁡M
The chain of inequalities. Rq is nondecreasing in q, and Pinsker's inequality 2TV2≤KL completes
2TV(ρ,π)2 ≤ KL(ρ‖π) ≤ R2(ρ‖π) ≤ Rq(ρ‖π) ≤ R∞(ρ‖π)(q≥2).
A bound on a divergence further right implies a bound on everything to its left.

What a Rényi bound buys that TV doesn't. TV measures differences in absolute terms: TV≤ε allows ρ to put probability ε on a set where π puts 10−100. Rényi divergence controls every event relative to π. By Hölder's inequality with exponents q and q/(q−1),

ρ(A)=Eπ[f1A]≤Eπ[fq]1/qπ(A)1−1/q=(eRqπ(A))1−1/q.
Events that are rare under π stay rare under ρ. As q→∞ this becomes the warm-start bound ρ(A)≤Mπ(A).

Processing cannot increase divergence. If the same random map (a Markov kernel P) is applied to both distributions, then Rq(ρP‖πP)≤Rq(ρ‖π), and the same holds for KL and TV. Whoever is trying to tell ρ from π could have applied P themselves. In particular, a Markov chain with stationary distribution π never moves further from π in any of these divergences.
Conditioning on a likely event. Suppose x=x~ on an event E with Pr(E)≥1−η. Let ρ~ be the law of x~ and ρ the law of x given E. Then ρ≤ρ~/(1−η), so
Rq(ρ‖π)≤Rq(ρ~‖π)+qq−1ln⁡11−η.
This is how an algorithm that can fail is compared with an idealised one that can't.

Explore

ρ=N(m,s2) and π=N(0,1). Each shaded region has area TV.
Rq(ρ‖π) against q, starting from KL at q=1. the current q. where Rq becomes infinite.

Worked example

π is uniform on a body X, and ρ is uniform on a piece A⊆X with half the volume.

  1. What is the likelihood ratio f?

    ρ=1A/Vol(A) and π=1X/Vol(X), so f=Vol(X)/Vol(A)=2 on A and 0 on the rest of X.

  2. Compute Rq(ρ‖π) for every q.

    Eπ[fq]=π(A)⋅2q=12⋅2q=2q−1, so Rq=1q−1ln⁡2q−1=ln⁡2 for every q. Since f takes only the values 0 and 2, no order of moment can see more than the worst ratio.

  3. And the TV and KL?

    KL=Eρ[ln⁡2]=ln⁡2≈0.69: one bit of information, “x is in A”. TV=ρ(A)−π(A)=1−12=12. Pinsker's bound KL/2≈0.59 holds.

Check your understanding

In the figure, set m=0 and s=1.5. Why does Rq become infinite for q≥1.8?

  1. ρ has heavier tails than π, so f=ρ/π grows like ecx2 and fqπ stops being integrable once q is large enough.
  2. Because TV is close to 1.TV is well below 1 here. Infinite Rényi divergence is about tails, not about overall overlap.
  3. Because KL is infinite.KL is finite (about 0.22 nats). It's the high-order moments of f that blow up.
ln⁡f(x)=x22(1−1/s2)+const, so fqπ∝exp⁡(x22(q(1−1/s2)−1)). This is integrable only if q(1−1/s2)<1, i.e. q<s2/(s2−1)=1.8 for s=1.5.

A sampler guarantees TV(ρT,π)≤0.01. Which statement is safe?

  1. |ρT(A)−π(A)|≤0.01 for every set A.
  2. ρT(A)≤2π(A) for every set A.TV allows ρT(A)=0.01 on a set with π(A) astronomically small; only a bound on Rq or R∞ controls ratios.
  3. KL(ρT‖π)≤0.0002.Pinsker goes the other way: KL controls TV, not TV controls KL.
TV is the largest absolute difference in probability over all events, and nothing more.

A Markov chain has stationary distribution π and starts from ρ0. Why can R2(ρt‖π) never increase with t?

  1. ρt+1=ρtP and π=πP, so it is the data processing inequality.
  2. Because the chain is reversible.Reversibility isn't needed; stationarity of π is.
  3. It can increase for a few steps before decreasing.Not for a chain with stationary π: each step applies the same kernel to both distributions.
Monotonicity is free; what makes the divergence actually decrease, and how fast, is a functional inequality such as a Poincaré inequality.

Practice

KL and Rényi between GaussiansThe formulas behind the figure

Let ρ=N(m,s2) and π=N(0,1) on R. Show that KL(ρ‖π)=12(s2+m2−1)−ln⁡s, and that for q>1 with a=q/s2+1−q>0,

Rq(ρ‖π)=1q−1(−qln⁡s−12ln⁡a)+qm22s2a,
while Rq=∞ if a≤0.

Outline
  1. ln⁡f(x)=−ln⁡s−(x−m)22s2+x22.
    Why?

    The 2π factors cancel in the ratio of the two Gaussian densities.

  2. For KL, take Eρ: Eρ(x−m)2=s2 and Eρx2=s2+m2.
    Why?

    −ln⁡s−12+12(s2+m2).

  3. For Rényi, Eπ[fq]=∫ρqπ1−q is a Gaussian integral with quadratic coefficient a/2.
    Why?

    The exponent is −12(ax2−2qms2x+qm2s2). If a≤0 the integral diverges. Otherwise complete the square: the integral is s−qa−1/2exp⁡(−12(qm2s2−q2m2s4a)), and qm2s2−q2m2s4a=q(1−q)m2s2a.

With s=1 both reduce to the familiar KL=m2/2 and Rq=qm2/2: for equal variances, the Rényi divergence grows linearly in the order.

Conditioning costs littleProve the conditioning bound

Prove the bound on Rq(ρ‖π) after conditioning on E, and show that the extra term is at most 4η when q≥2 and η≤12.

Outline
  1. ρ(A)=Pr(x∈A,E)/Pr(E)=Pr(x~∈A,E)/Pr(E)≤ρ~(A)/(1−η).
    Why?

    On E the two points coincide, and dropping the event E can only increase a probability.

  2. So f≤f~/(1−η) and Eπ[fq]≤(1−η)−qEπ[f~q].
    Why?

    A pointwise bound on the ratio raised to the power q.

  3. Take 1q−1ln, then use qq−1≤2 and ln⁡11−η≤η1−η≤2η.
    Why?

    ln⁡(1+u)≤u with u=η/(1−η).

Key terms in plain words

The ideas above without the symbols. Switch to Quiz me to test yourself: you see an explanation and pick the term it describes.

Likelihood ratio
How many times more probability one distribution puts near a point than another does; every divergence here is an average of some function of it.
Total variation
The largest difference, over all events, between the probabilities two distributions assign; it measures differences in absolute terms only.
Kullback–Leibler divergence
The average log of the likelihood ratio under the first distribution: the evidence per sample for one distribution over another, or the bits wasted by using the wrong code.
Rényi divergence
A family of divergences built from higher moments of the likelihood ratio, running from KL at one end to the log of the worst-case ratio at the other.
Data processing inequality
Applying the same random transformation to two distributions can only make them harder to tell apart.
Warm start
A starting distribution that never puts more than a fixed multiple of the target's probability on any set.
InteractiveVempala–Wibisono (2026), §2.3; Kneser (1951)

Thickenings and volume growth

Thicken a set by t and measure how much its volume grows. Thin sets grow fast and fat sets slowly, and in high dimension even a ball's volume grows very fast. This growth rate is the second hypothesis of the theorem.

The idea

Thickening. The Minkowski sum A⊕B={a+b:a∈A,b∈B} places a copy of B at every point of A. With Bt the ball of radius t, the t-thickening is
Xt=X⊕Bt={y: dist(y,X)≤t}.
Thickenings compose, (Xs)t=Xs+t, because Bs⊕Bt=Bs+t. Thickening fills dents and closes narrow gaps.

Growth rate. Going from Xt to Xt+dt adds a layer of thickness dt over the boundary, so ddtVol(Xt)=area(∂Xt). At t=0 the relative growth rate is the outer isoperimetry ξ(X)=area(∂X)/Vol(X): thin sets have a lot of boundary per unit of volume.

High dimension. Vol(BR+t)/Vol(BR)=(1+t/R)n≈ent/R. Thickening a ball by R/n multiplies its volume by about e, and by R/n by about en. Equivalently, most of a high-dimensional ball lies within O(R/n) of its surface. The natural thickening scale of a body of radius R is R/n.

Volume growth (Vempala–Wibisono, Definition 2). X satisfies the (α,β)-volume growth condition if
Vol(Xt)Vol(X)≤α(1+tβ)nfor all t>0.
The right side is how a ball of radius 1/β grows, inflated by a constant factor α. So 1/β acts like an inner radius, and the condition has teeth at t≲1/(nβ), where it says that thickening multiplies the volume by O(α).
bodyαβwhy
ball BR11/Requality for every t
convex body1ξ(X)/n≤1/rinBrunn–Minkowski (Lemma 5)
cylinder [0,1]×wBn−11≈1/wthin in n−1 directions
star-shaped, core ⊇Br11/rXt⊆(1+t/r)X (Lemma 6)
Y with a hole cut outαYVol(Y)Vol(X)βYXt⊆Yt (Lemma 8)
Kneser's inequality. For every compact X, every s>0 and λ≥1,
Vol(Xλs)≤λnVol(Xs).
Consequently every thickening Xs of every compact set satisfies (1,1/s)-volume growth, with no convexity at all. Proof idea: move each point y of Xλs toward its nearest point p(y)∈X, to Φ(y)=p(y)+(y−p(y))/λ∈Xs. The nearest-point inequalities give ⟨p(y)−p(y′),y−y′⟩≥0, hence ‖Φ(y)−Φ(y′)‖≥‖y−y′‖/λ. So Φ shrinks volume by at most λn.

Explore

Shape
X and the added layer Xt∖X.
Vol(Xt)/Vol(X) against t (area, since n=2); a disk of the same area, for comparison.

Check your understanding

In R100, thicken the unit ball by t=0.01. By roughly what factor does its volume grow?

  1. By about 1%.That is the one-dimensional intuition. Volume scales like the radius to the power n.
  2. By about e≈2.7: 1.01100≈2.70.
  3. By about 100.That would need t≈0.047: 1.047100≈100.
Thickening by R/n multiplies a ball's volume by about e. This is why the volume growth condition matters only for t≲1/(nβ).

Cut an open hole Z out of a ball Y=BR, leaving X=Y∖Z with half the volume. What volume growth constants does X get?

  1. (2,1/R), however irregular the hole: Xt⊆Yt, so Vol(Xt)≤(1+t/R)nVol(Y)=2(1+t/R)nVol(X).
  2. It depends on how close the hole comes to the boundary.The bound only uses X⊆Y and the volume ratio.
Volume growth is cheap to keep under removing holes. Isoperimetry is not: cutting Y into disconnected slabs keeps (2,1/R)-volume growth but makes CPI infinite. The two hypotheses really are independent.

In the figure, choose the C-shape. Why does the growth curve bend downwards near t=0.2?

  1. The two arms grow toward each other and the notch fills up, so the layers they add overlap.
  2. Because the C-shape is convex.It isn't; the bend comes precisely from the dent.
Once the gap of width 0.4 closes at t=0.2, the inside of the notch adds no more volume. For a convex shape the growth Vol(X)+perimeter⋅t+πt2 never slows down like this.

Practice

Nearest points don't crossThe key step of Kneser's inequality

Let a be a nearest point of X to y and b a nearest point to y′. Show ⟨a−b,y−y′⟩≥0, and deduce ‖Φ(y)−Φ(y′)‖≥‖y−y′‖/λ.

Outline
  1. ‖y−a‖2≤‖y−b‖2 and ‖y′−b‖2≤‖y′−a‖2.
    Why?

    Both a and b are in X, and a is nearest to y, b to y′.

  2. Expanding and adding: 2⟨y−y′,b−a⟩≤0.
    Why?

    The first gives 2⟨y,b−a⟩≤‖b‖2−‖a‖2, the second 2⟨y′,a−b⟩≤‖a‖2−‖b‖2. The right sides cancel when added.

  3. With μ=1/λ: ‖Φ(y)−Φ(y′)‖2=(1−μ)2‖a−b‖2+μ2‖y−y′‖2+2μ(1−μ)⟨a−b,y−y′⟩≥μ2‖y−y′‖2.
    Why?

    Φ(y)−Φ(y′)=(1−μ)(a−b)+μ(y−y′); every term but the middle one is nonnegative.

So the inverse of Φ is λ-Lipschitz on the image, and a λ-Lipschitz map increases volume by at most λn. This gives Vol(Xλs)≤λnVol(Xs).

Star-shaped bodies grow like dilationsLemma 6, for any star-shaped body

Suppose the segment from any x∈X to any point of Br lies in X. Show Xt⊆(1+t/r)X.

Outline
  1. Write z=x+w with x∈X, ‖w‖≤t, and z=(1+tr)[rr+tx+tr+t⋅rtw].
    Why?

    Multiply out: the bracket times (r+t)/r is x+w.

  2. The bracket is on the segment from x to rtw∈Br, so it lies in X.
    Why?

    It is a convex combination of the two endpoints, with weights rr+t and tr+t.

Taking volumes, X satisfies (1,1/r)-volume growth.

Key terms in plain words

The ideas above without the symbols. Switch to Quiz me to test yourself: you see an explanation and pick the term it describes.

Minkowski sum
The set you get by placing a copy of one shape at every point of another and taking everything covered.
Thickening
All points within a given distance of a set: the set with a collar added around it.
Outer isoperimetry
Boundary area divided by volume: how fast a set starts to grow when thickened, large for thin sets.
Volume growth condition
A promise that thickening the body never inflates its volume faster than it would inflate a ball of a fixed radius, up to a constant factor.
Kneser's inequality
Thickening by a larger amount inflates volume at most as much as dilating by the same ratio would, for any compact set at all.
InteractiveVempala–Wibisono (2026), §2.2; Chen–Chewi–Salim–Wibisono (2022)

Bottlenecks and the Poincaré constant

A Poincaré inequality says that a function which changes slowly can't vary much. It fails badly for a dumbbell, and its constant sets how long any diffusion takes to mix.

The idea

Poincaré inequality. π satisfies a Poincaré inequality with constant CPI if
Varπ(ϕ)≤CPIEπ‖∇ϕ‖2for every smooth ϕ.
CPI has units of length², and 1/CPI is the spectral gap: for π uniform on X, the smallest nonzero eigenvalue of −Δ with Neumann boundary conditions.

An interval. For π uniform on [0,L], CPI=L2/π2, attained by ϕ(x)=cos⁡(πx/L). Its variance is 12 and its mean squared derivative is 12(π/L)2. Other constants: O(D2) for a convex body of diameter D, and O(D2/γ2) for a star-shaped body whose convex core has a fraction γ of the volume.

A dumbbell. Take total volume V and a neck of length ℓ and cross-section a. The test function ϕ=−1 on one lobe, +1 on the other, linear along the neck has variance about 1. Its gradient is 2/ℓ, but only on the neck, which has probability aℓ/V. So E‖∇ϕ‖2≈4a/(ℓV) and

CPI≳ℓV4a.
In Rn a neck of radius w has a∝wn−1, so even a moderately narrow neck makes CPI exponential in n.

Why it controls mixing. For the diffusion with stationary distribution π (Brownian motion reflected at ∂X) and Ptϕ(x)=E[ϕ(Xt)∣X0=x],
ddtVarπ(Ptϕ)=−2Eπ‖∇Ptϕ‖2≤−2CPIVarπ(Ptϕ),
so variances decay like e−2t/CPI. Applied to the likelihood ratio, this says χ2(ρt‖π) decays at that rate. The discrete-time proximal sampler with step h contracts Rq by the factor (1+h/CPI)−1/q per iteration once Rq≤1 (Chen et al. 2022, Theorem 4).

Explore

Two unit balls in Rn joined by a neck, coloured by the slowest axial mode ϕ, from negative to positive.
ϕ along the axis. The shaded band is the neck, where all of ϕ's change happens once the neck is narrow.

The figure computes the Poincaré constant restricted to functions of the axial coordinate, by solving the one-dimensional eigenproblem −(aϕ′)′=λaϕ with cross-section area a(x)∝r(x)n−1. That is a lower bound on CPI, and for a narrow neck the slowest mode is axial, so it is the true bottleneck.

Check your understanding

Fix the neck radius at w=0.4 and raise the dimension from 3 to 20. What happens to CPI, and why?

  1. It grows roughly like (1/w)n−1: the neck's share of the volume shrinks exponentially in n.
  2. It stays about the same, since the geometry in the figure doesn't change.The picture is a 2D section; in Rn the neck's cross-section scales like wn−1 and the balls' like 1.
  3. It shrinks, because high-dimensional balls are small.Both lobes and neck shrink, but the neck much faster.
The dumbbell bound ℓV/(4a) has a∝wn−1 and V of the order of the unit-ball volume, so the ratio is exponential in n for any fixed w<1.

Doubling the length scale of a body (X↦2X) multiplies CPI by…

  1. 2.Variance scales with the square of distances while gradients scale inversely: look at the units.
  2. 4.
  3. 2n.Volume scales by 2n, but π is normalised, so that factor cancels.
CPI has units of length². In the main theorem it appears as CPIβ2, which is scale-free since β has units of 1/length.

Practice

The intervalVerify C = L²/π² from the test function

For π uniform on [0,L] and ϕ(x)=cos⁡(πx/L), compute Varπ(ϕ) and Eπ[ϕ′2], and conclude CPI≥L2/π2.

Outline
  1. Eπϕ=0 and Eπϕ2=12.
    Why?

    cos over a half period averages to 0, and cos2 to 12.

  2. ϕ′=−πLsin⁡(πx/L), so Eϕ′2=π22L2.
    Why?

    sin2 also averages to 12 over a half period.

The ratio is L2/π2. Equality holds because ϕ is the first nonconstant Neumann eigenfunction, −ϕ″=(π/L)2ϕ with ϕ′(0)=ϕ′(L)=0.

SimulationKook–Vempala–Zhang (2026); Vempala–Wibisono (2026), Algorithm 1 and Lemma 9

In-and-Out: a proximal sampler

Step out with Gaussian noise, then step back in by rejection sampling. Each iteration is an exact Gibbs update of a two-variable distribution whose first marginal is the target, and a Poincaré inequality makes it mix.

The idea

In-and-Out with step size h, T iterations and a trial budget N. Start from x0∈X, and for i=0,…,T−1:
  1. Out (forward step). Draw yi∼N(xi,hI). It may leave X.
  2. In (backward step). Draw x′∼N(yi,hI) until x′∈X, and set xi+1=x′. After N failed trials, stop and report failure.
Each trial is one membership query plus O(n) arithmetic.
The two-variable picture. Let πXY(x,y)∝1X(x)exp⁡(−‖y−x‖2/(2h)). Fixing x, the y-slice is N(x,hI): the forward step. Fixing y, the x-slice is N(y,hI) restricted to X: the backward step. Integrating out y leaves 1X/Vol(X)=π. So In-and-Out is the Gibbs sampler for πXY, also called the proximal sampler for π. Each update keeps πXY invariant, and the auxiliary point y lets the chain jump across holes in X.
The key identity. The y-marginal is πh=π∗N(0,hI), the uniform distribution blurred by Gaussian noise. Its density is
πh(y)=1Vol(X)∫XNh(y−x)dx=ℓh(y)Vol(X),ℓh(y)=Pr(y+hZ∈X).
Where forward steps tend to land is exactly where backward trials tend to succeed. Every cost estimate is a calculation with this identity.
Number of iterations (Lemma 9). If π satisfies a Poincaré inequality with CPI≥1 and In-and-Out succeeds with probability ≥1−η, then conditioned on success
Rq(ρT‖π)≤(1+h/CPI)−(T−T0)/q+4η,
where T0≤(2qCPI/h)ln⁡M burn-in iterations bring Rq from ln⁡M down to 1. In total about (2qCPI/h)ln⁡(M/ε) iterations suffice. The 4η is the cost of conditioning on success (see TV, KL and Rényi divergence): on success, In-and-Out makes exactly the moves of the exact proximal sampler.

The number of iterations grows like CPI/h. So the whole question becomes how large the step h can be while each iteration stays cheap and rarely fails. That is decided by the geometry of X at the scale of one step.

Explore

Body
300 independent chains, all started at the same point. their current positions; one chain's recent path.
fraction of chains with x1>0, against iteration. the uniform value, the fraction of the area with x1>0.

Check your understanding

On the ring, the chains start on the left and must reach the right half. What does increasing the step size do?

  1. Fewer iterations to mix, but more trials per iteration, since forward steps leave the thin ring more often.
  2. Faster mixing at no cost.Watch the trials per iteration in the stats.
  3. Slower mixing, because bigger steps are rejected more.The backward step always ends inside (or fails); the iteration count falls like CPI/h.
This is the trade-off the analysis optimises: iterations ≈CPI/h, trials per iteration bounded only while h is small compared with the body's thinness.

Why is it legitimate to analyse In-and-Out as the exact proximal sampler, even though it can fail?

  1. Driven by the same random draws, the two produce identical iterates unless In-and-Out fails, and conditioning on an event of probability ≥1−η costs at most 4η in Rq.
  2. Because failures never happen in practice.They can, and the analysis must bound their probability.
The truncation only removes runs; it never changes where an accepted step lands.
InteractiveVempala–Wibisono (2026), Lemma 10; Kook–Vempala–Zhang (2026), Lemma 13

Halfspaces versus balls: where n3 comes from

A forward step can land outside the body. For a convex body a whole halfspace separates that point from the body; for a nonconvex body only a ball is guaranteed to. A Gaussian step crosses a hyperplane rarely but leaves a ball easily, and that costs a factor of n in the step size.

The idea

Length versus direction. For Z∼N(0,In), E‖Z‖2=n, and ‖Z‖ concentrates near n. But its component along any fixed unit vector is N(0,1). A step hZ is long (≈hn) but makes progress only ≈h in any direction chosen in advance. Write Qm(s)=Pr(‖Z‖≥s) for Z∼N(0,Im).

Bounding ℓh(y) for y at distance u from X.

  • Convex X: some halfspace contains y and misses X. A proposal must cross the hyperplane, a one-dimensional event, so ℓh(y)≤Q1(u/h).
  • Nonconvex X: only the ball B(y,u) is sure to miss X (picture y inside a notch). A proposal must leave the ball, so ℓh(y)≤Qn(u/h), which is close to 1 until u≈hn.
Stationary escape (Lemma 10). If X satisfies (α,β)-volume growth and h≤1/(2n3β2), then for all r≥0,
πh(Xr∁)≤α(n+1)Q2n(r/h).
A forward step from a uniform point rarely lands farther than a few multiples of 2hn from X.

Where the n3 appears. The proof writes πh(Xr∁) as an integral over the level sets of the distance to X (the coarea formula). Integration by parts then turns it into an average of Vol(Xt)/Vol(X) against the chi density, which peaks at t≈hn. Volume growth bounds that ratio by α(1+βhn)n≈αeβn3/2h. This is O(α) only when h≲1/(β2n3). With a halfspace, only the progress h matters, (1+βh)n=O(1) needs only h≲1/(β2n2), and the iteration count ∝1/h is a factor n smaller.

Explore

Chance that one proposal from distance u gets back: crossing a hyperplane, Q1(u/h); leaving a ball, Qn(u/h). Log scale.
The factor (1+βhn)n at the scale of one step, for h=1/(2β2n2) and h=1/(2β2n3), against n. Log scale; the dot is the current n.

Check your understanding

y is at distance u=2h from X, in dimension n=100. Which bound on ℓh(y) is informative?

  1. The halfspace bound Q1(2)≈0.046; the ball bound Q100(2) is essentially 1.
  2. The ball bound, since it uses all n directions.A step's length is about 100=10≫2, so it leaves the ball almost surely; the bound says nothing.
Leaving a small ball is easy for a long step; crossing a fixed hyperplane is not. Without convexity, only the ball is available.

Why does the escape lemma require h≲1/(β2n3) rather than 1/(β2n2)?

  1. Volume growth must be controlled at t≈hn, the length of a step, and (1+βhn)n is bounded only when βhn≲1/n.
  2. Because the rejection budget N must be polynomial.The budget enters only logarithmically in the step size condition.
  3. Because nonconvex bodies have larger Poincaré constants.CPI is a separate hypothesis; the step size comes from geometry at the scale of one step.
βhn≤1/n means h≤1/(β2n3). In the second figure, the 1/n2 curve grows like en/2 while the 1/n3 curve stays below e1/2≈2.03.
Read and checkVempala–Wibisono (2026), Lemmas 11–13 and Theorem 1

What an iteration costs, and the theorem

Without a budget, one iteration has infinite expected cost even in equilibrium. Splitting space into near and far shows how volume growth and the escape bound together make it cheap.

The idea

An infinite average. At stationarity y∼πh, and the expected number of trials from y is 1/ℓh(y). By the key identity,

Eπh[1/ℓh]=∫Rn1ℓh(y)⋅ℓh(y)Vol(X)dy=Vol(Rn)Vol(X)=∞.
Restricted to a set A, the same computation gives Eπh[1A/ℓh]=Vol(A)/Vol(X): the expected cost of forward steps landing in A is the volume of A in units of Vol(X).

Near and far. Cap the trials at N and split at radius r:

  • near, y∈Xr: cost at most Vol(Xr)/Vol(X)≤α(1+rβ)n, a volume growth ratio;
  • far, y∉Xr: cost at most Nπh(Xr∁), small by the escape lemma.

Choosing r=8hmax{n,ln⁡((n+1)αS)} makes r≤2/(nβ), so the near part is at most 8α, and the far part at most N/S. With N=8αSln⁡S, the expected number of trials is at most 16αln⁡S and the failure probability at most 3/S (Lemmas 11–12). For the failure bound, near points with low conductance are harmless: the forward step lands there with probability proportional to that same low conductance.

From equilibrium to the chain. If ρi≤Mπ, then ρi∗Nh≤Mπh, and the exact backward step maps πh back to π. So warmness is preserved, and every stationary bound holds along the chain with an extra factor M (Lemma 13). The law conditioned on success is only M/Pr(success)-warm; tracking the sub-probability measure A↦Pr(xi∈A, no failure yet) repairs this without changing the theorem.

Theorem 1. With T≈(2qCPI/h)ln⁡(M/ε) iterations, h≈1/(2β2n3), S=3TM/η and N=8αSln⁡S, In-and-Out succeeds with probability ≥1−ε, outputs Rq(ρT‖π)≤ε, and uses
O~(qCPIβ2n3)⏟iterations×O~(Mα)⏟trials per iteration=O~(qCPIαβ2Mn3log4⁡(1/ε))
trials in expectation.
bodyαβCPItrials (up to logs)
ball BR11/R≍R2/nn2
isotropic convex body1O(1)O(log⁡n)n3
star-shaped, core ⊇Br, diameter D11/rO(D2/γ2)n3D2/(γr)2
thin cylinder, radius w1≈1/w1/π2n3/w2

The bound depends on the body only through the scale-free product CPIβ2 and the constant α. The ball row is a factor n better because its CPI is itself of order R2/n.

Check your understanding

Why does the far region need the escape lemma, while the near region needs only volume growth?

  1. Near points cost Vol(Xr)/Vol(X) by the key identity. Far points can cost the full budget N each, so they must be rare.
  2. Because far points always fail.They might succeed; the bound just charges them the worst case N.
The identity Eπh[1A/ℓh]=Vol(A)/Vol(X) is useful only for bounded A; far away the budget takes over.

The failure probability per iteration is 3M/S. How is S chosen so that all T iterations succeed with probability ≥1−η?

  1. S=3TM/η, so the union bound gives T⋅3M/S=η.
  2. S=3M/η.That handles one iteration; there are T of them.
S enters the cost only through ln⁡S, so making it polynomially large is cheap. The budget N∝S is large, but it is rarely used.

Practice

The cost of a regionThe identity behind every cost bound

Show that Eπh[1A/ℓh]=Vol(A)/Vol(X) for any measurable A, and use it to bound the expected number of trials of an iteration started at stationarity by Vol(Xr)/Vol(X)+Nπh(Xr∁).

Outline
  1. πh(y)=ℓh(y)/Vol(X), so the integrand is 1A(y)/Vol(X).
    Why?

    The ℓh factors cancel; integrate over y.

  2. The expected trials from y are μ(y)≤min{1/ℓh(y),N}.
    Why?

    A geometric number of trials capped at N; see Rejection sampling with a budget.

  3. Use 1/ℓh on Xr and N off it.
    Why?

    Eπhμ≤Eπh[1Xr/ℓh]+Nπh(Xr∁).

SimulationVempala–Wibisono (2026), §4; the project's draft on warm starts

Warm starts by annealing

The theorem needs an M-warm start, and M enters the cost linearly. The standard way to get one is annealing: sample a sequence of bodies, each a warm start for the next. Which sequence to use, and in which direction, matters.

The idea

Nested sets and warmness. If Y⊆Y′, then Unif(Y)≤Vol(Y′)Vol(Y)Unif(Y′): the uniform law on the smaller set is warm for the larger one. The reverse fails completely. Unif(Y′) puts mass on Y′∖Y, where Unif(Y) has none, so it is not M-warm for any M. So annealing must run upward, through growing sets.

Shrinking thickenings run the wrong way. It is tempting to anneal through Xt0⊃Xt1⊃⋯⊃X, since Kneser's inequality bounds every consecutive ratio: with tk+1=tk/(1+1/n), Vol(Xtk)≤eVol(Xtk+1). But the warmness goes the wrong way. Fixing it by rejection (keep only samples that land in the next set) multiplies costs from stage to stage. Also, a membership oracle for X cannot test membership in Xt: it cannot certify that a ball misses X.

Upward annealing for star-shaped bodies (project draft). Let X be star-shaped with respect to a known ball Br, with diameter D. Use Xk=X∩Bρk with ρk=r(1+1/n)k:
  • X0=Br can be sampled exactly, and membership in Xk costs one query to X;
  • X∩Bλρ⊆λ(X∩Bρ), so consecutive volume ratios are at most (1+1/n)n≤e;
  • each Xk is star-shaped with respect to Br, so it has (1,1/r)-volume growth and CPI=O(D2/γr2) with γr=Vol(Br)/Vol(X).
Running In-and-Out at each of the K≈nln⁡(D/r) stages gives a complete sampler with total variation error ε and polylogarithmic dependence on 1/ε.

Not letting warmness compound. The output of a stage is only approximately uniform, and its warmness can be worse than M. Multiplying warmness factors over K stages would be exponential. Instead, couple each stage's start with an exact sample of the previous body. On the coupling event the stage starts e-warm, so the theorem applies, and the total variation errors simply add up over the stages.

Open. For general nonconvex bodies, neither family is known to work. X∩Bρ can be disconnected. Thickenings need a stronger oracle and a Poincaré inequality at every scale, which has been proved for star-shaped bodies and for very large thickenings but is open in between.

Explore

Start
A cross, star-shaped with respect to its central square. 300 chains; the current ball Bρ when annealing.
Fraction of chains in each part of the cross: empirical, exact (proportional to area).

Check your understanding

You have an exact sample of Unif(Xt) and want to start a sampler for Xt′ with t′<t. Why is the sample not a warm start?

  1. It may lie outside Xt′: its law puts mass where Unif(Xt′) puts none.
  2. Because the volume ratio is larger than e.Even a ratio of 1.01 doesn't help: the issue is support, not size.
The ratio Vol(Xt)/Vol(Xt′) bounds the warmness of Unif(Xt′) with respect to Unif(Xt): the useful direction for an increasing schedule.

Why does X∩Bρ need X to be star-shaped around the ball's center?

  1. So that X∩Bλρ⊆λ(X∩Bρ) (bounded volume ratios), and so each stage stays connected and inherits a Poincaré inequality.
  2. So that membership in X∩Bρ can be tested.That is always possible: one query to X and a norm.
For a general body, X∩Bρ might be two far-apart pieces, or might gain most of its volume in a single step.

Key terms in plain words

The ideas above without the symbols. Switch to Quiz me to test yourself: you see an explanation and pick the term it describes.

Annealing
Reaching a hard target through a sequence of easier ones, each close enough to the next that a sample of one is a good start for the next.
Star-shaped body
A body containing a region from which every point of the body can be seen along a straight line.
Coupling
Running two random processes on shared randomness so that they agree except on a small event, which lets errors add instead of multiply.
Proximal sampler
A sampler that alternately adds Gaussian noise and removes it by drawing from the target tilted towards the noisy point.