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.
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
What was known. Convex bodies can be sampled in time polynomial in
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
Obstruction 2: thinness. A cylinder
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
- A point mass is not
-warm for any : it puts probability 1 on a set of volume 0. - Because
might lie on the boundary.Even an interior point fails: warmness compares probabilities of sets, and has -probability 0. - It can; warmness only matters for convex bodies.Warmness enters the cost bound linearly, through
, for every body.
A long thin cylinder has
- Steps must shrink like
to stay inside, so crossing the cylinder takes about steps. - The sampler gets stuck at one end, as in a dumbbell.There is no bottleneck: the cylinder is convex and isoperimetry stays good.
- 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.
Practice
The thin cylinderGood isoperimetry, bad volume growth
Let
Outline
- 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:
, and apply each factor's inequality to its partial gradient. - The factors are
, with constant , and the ball , with constant .Why?
The interval's constant is attained by
; the ball's comes from its covariance, per coordinate, by the KLS bound for balls. .Why?
Thickening the disk by
inside each slice. Its volume is times that of .
So
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
The general version. To sample a density
Why the budget is not optional. In a sampler the start
Explore
Worked example
A point with local conductance
How many trials does it take on average without a budget?
.What is the chance of failure with the budget?
, about one in six. The bound is close.How many trials are used on average with the budget?
: a little below 4, because the long runs are cut off at 6.How large must
be for failure probability at most ?Need
, i.e. , so . The bound asks for , a little more.
Check your understanding
Rejection sampling with a budget fails with probability
- Yes: given that some trial among the first
succeeds, the first successful trial is still a fresh proposal conditioned on landing in . - 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.
The start
- 2.That is
. The expected cost is , which is larger. - Infinite:
. .The integral diverges at 0.
In the figure, drag
is near 1 inside and tiny far outside. A larger spread helps a point just outside reach , but it also sends proposals from a point inside out of . is always about near the set.That holds only right at a flat piece of boundary; corners and thin parts change it.
Practice
The truncated meanCompute E min(G, N)
Show that
Outline
- For a nonnegative integer variable,
.Why?
; take expectations. for , and for .Why?
means the first trials all failed.- Sum the geometric series
.Why?
It equals
.
Exactness of the general methodAccept with probability p/(Mg)
Let
Outline
.Why?
Condition on the proposal
, then integrate over it.- Take
to get , then divide.Why?
.
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.
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
| order | what it measures | |
|---|---|---|
| the average of | ||
| the variance of the ratio | ||
| the worst ratio: |
What a Rényi bound buys that TV doesn't. TV measures differences in absolute terms:
Explore
Worked example
What is the likelihood ratio
? and , so on and on the rest of .Compute
for every . , so for every . Since takes only the values and , no order of moment can see more than the worst ratio.And the TV and KL?
: one bit of information, “ is in ”. . Pinsker's bound holds.
Check your understanding
In the figure, set
has heavier tails than , so grows like and stops being integrable once is large enough.- Because TV is close to 1.TV is well below 1 here. Infinite Rényi divergence is about tails, not about overall overlap.
- Because KL is infinite.KL is finite (about 0.22 nats). It's the high-order moments of
that blow up.
A sampler guarantees
for every set . for every set .TV allows on a set with astronomically small; only a bound on or controls ratios. .Pinsker goes the other way: KL controls TV, not TV controls KL.
A Markov chain has stationary distribution
and , so it is the data processing inequality.- Because the chain is reversible.Reversibility isn't needed; stationarity of
is. - It can increase for a few steps before decreasing.Not for a chain with stationary
: each step applies the same kernel to both distributions.
Practice
KL and Rényi between GaussiansThe formulas behind the figure
Let
Outline
.Why?
The
factors cancel in the ratio of the two Gaussian densities.- For KL, take
: and .Why?
. - For Rényi,
is a Gaussian integral with quadratic coefficient .Why?
The exponent is
. If the integral diverges. Otherwise complete the square: the integral is , and .
With
Conditioning costs littleProve the conditioning bound
Prove the bound on
Outline
.Why?
On
the two points coincide, and dropping the event can only increase a probability.- So
and .Why?
A pointwise bound on the ratio raised to the power
. - Take
, then use and .Why?
with .
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.
Thickenings and volume growth
Thicken a set by
The idea
Growth rate. Going from
High dimension.
| body | why | ||
|---|---|---|---|
| ball | equality for every | ||
| convex body | Brunn–Minkowski (Lemma 5) | ||
| cylinder | thin in | ||
| star-shaped, core | |||
Explore
Check your understanding
In
- By about 1%.That is the one-dimensional intuition. Volume scales like the radius to the power
. - By about
: . - By about 100.That would need
: .
Cut an open hole
, however irregular the hole: , so .- It depends on how close the hole comes to the boundary.The bound only uses
and the volume ratio.
In the figure, choose the C-shape. Why does the growth curve bend downwards near
- The two arms grow toward each other and the notch fills up, so the layers they add overlap.
- Because the C-shape is convex.It isn't; the bend comes precisely from the dent.
Practice
Nearest points don't crossThe key step of Kneser's inequality
Let
Outline
and .Why?
Both
and are in , and is nearest to , to .- Expanding and adding:
.Why?
The first gives
, the second . The right sides cancel when added. - With
: .Why?
; every term but the middle one is nonnegative.
So the inverse of
Star-shaped bodies grow like dilationsLemma 6, for any star-shaped body
Suppose the segment from any
Outline
- Write
with , , and .Why?
Multiply out: the bracket times
is . - The bracket is on the segment from
to , so it lies in .Why?
It is a convex combination of the two endpoints, with weights
and .
Taking volumes,
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.
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
An interval. For
A dumbbell. Take total volume
Explore
The figure computes the Poincaré constant restricted to functions of the axial coordinate, by solving the one-dimensional eigenproblem
Check your understanding
Fix the neck radius at
- It grows roughly like
: the neck's share of the volume shrinks exponentially in . - It stays about the same, since the geometry in the figure doesn't change.The picture is a 2D section; in
the neck's cross-section scales like and the balls' like . - It shrinks, because high-dimensional balls are small.Both lobes and neck shrink, but the neck much faster.
Doubling the length scale of a body (
.Variance scales with the square of distances while gradients scale inversely: look at the units. . .Volume scales by , but is normalised, so that factor cancels.
Practice
The intervalVerify C = L²/π² from the test function
For
Outline
and .Why?
over a half period averages to 0, and to . , so .Why?
also averages to over a half period.
The ratio is
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
- Out (forward step). Draw
. It may leave . - In (backward step). Draw
until , and set . After failed trials, stop and report failure.
The number of iterations grows like
Explore
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?
- Fewer iterations to mix, but more trials per iteration, since forward steps leave the thin ring more often.
- Faster mixing at no cost.Watch the trials per iteration in the stats.
- Slower mixing, because bigger steps are rejected more.The backward step always ends inside (or fails); the iteration count falls like
.
Why is it legitimate to analyse In-and-Out as the exact proximal sampler, even though it can fail?
- Driven by the same random draws, the two produce identical iterates unless In-and-Out fails, and conditioning on an event of probability
costs at most in . - Because failures never happen in practice.They can, and the analysis must bound their probability.
Halfspaces versus balls: where 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
The idea
Length versus direction. For
Bounding
- Convex
: some halfspace contains and misses . A proposal must cross the hyperplane, a one-dimensional event, so . - Nonconvex
: only the ball is sure to miss (picture inside a notch). A proposal must leave the ball, so , which is close to 1 until .
Where the
Explore
Check your understanding
- The halfspace bound
; the ball bound is essentially 1. - The ball bound, since it uses all
directions.A step's length is about , so it leaves the ball almost surely; the bound says nothing.
Why does the escape lemma require
- Volume growth must be controlled at
, the length of a step, and is bounded only when . - Because the rejection budget
must be polynomial.The budget enters only logarithmically in the step size condition. - Because nonconvex bodies have larger Poincaré constants.
is a separate hypothesis; the step size comes from geometry at the scale of one step.
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
Near and far. Cap the trials at
- near,
: cost at most , a volume growth ratio; - far,
: cost at most , small by the escape lemma.
Choosing
From equilibrium to the chain. If
| body | trials (up to logs) | |||
|---|---|---|---|---|
| ball | ||||
| isotropic convex body | ||||
| star-shaped, core | ||||
| thin cylinder, radius |
The bound depends on the body only through the scale-free product
Check your understanding
Why does the far region need the escape lemma, while the near region needs only volume growth?
- Near points cost
by the key identity. Far points can cost the full budget each, so they must be rare. - Because far points always fail.They might succeed; the bound just charges them the worst case
.
The failure probability per iteration is
, so the union bound gives . .That handles one iteration; there are of them.
Practice
The cost of a regionThe identity behind every cost bound
Show that
Outline
, so the integrand is .Why?
The
factors cancel; integrate over .- The expected trials from
are .Why?
A geometric number of trials capped at
; see Rejection sampling with a budget. - Use
on and off it.Why?
.
Warm starts by annealing
The theorem needs an
The idea
Nested sets and warmness. If
Shrinking thickenings run the wrong way. It is tempting to anneal through
can be sampled exactly, and membership in costs one query to ; , so consecutive volume ratios are at most ;- each
is star-shaped with respect to , so it has -volume growth and with .
Not letting warmness compound. The output of a stage is only approximately uniform, and its warmness can be worse than
Open. For general nonconvex bodies, neither family is known to work.
Explore
Check your understanding
You have an exact sample of
- It may lie outside
: its law puts mass where puts none. - Because the volume ratio is larger than
.Even a ratio of 1.01 doesn't help: the issue is support, not size.
Why does
- So that
(bounded volume ratios), and so each stage stays connected and inherits a Poincaré inequality. - So that membership in
can be tested.That is always possible: one query to and a norm.
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.