Stochastic Localization
To understand a complicated distribution, replace it by a random family of simpler, more concentrated ones that average back to it exactly. Watch random densities collapse onto a point while their average stays put, recover the clean signal from a noisy one with Tweedie's formula, cut a condition number of 10,000 down to 2, watch a Gibbs sampler zigzag through a narrow Gaussian, tilt an exponential family, and squeeze a variance between Cramér–Rao and Brascamp–Lieb.
Built from the notes of the Functional Stochastic Localization project, which studies A. Gu, B. Shi and K. Tian, “Functional Stochastic Localization” (COLT 2026, PMLR 336). The page keeps to background that is useful beyond that paper. Stochastic localization is due to R. Eldan (Geometric and Functional Analysis 23, 2013); the posterior-sampling view follows A. El Alaoui and A. Montanari (IEEE Trans. Inf. Theory 68, 2022), and localization schemes follow Y. Chen and R. Eldan (FOCS 2022). The proximal sampler is treated in detail on the Sampling Nonconvex Bodies page, Itô integrals on Diffusion Models, and exponential families on Information Geometry. Results from the literature are labelled with their source; the questions and examples are written for this page. For how this subject connects to the others, see the roadmap.
Random measures that average to the target
Hard questions about one distribution
The idea
- for every set
, is a martingale, so ; - for every set
, or almost surely as .
What
Why it concentrates.
The Gaussian example. For
Explore
Check your understanding
Fix a point
- A random number, depending on the path of the process; its expectation is the number
. - A fixed number equal to
.Only its average is . Individual realizations are far from : most are near 0, a few are huge. - A probability distribution over
.That is as a whole. Evaluated at one point it is a single number, random because is.
The target puts mass
- With probability
: is a martingale that ends at 0 or 1, and its expectation stays . - Never: the process always prefers the heavier bump.Then
would drop to 0, breaking the martingale property. - With probability
, by symmetry of the noise.The noise is symmetric but the target is not; the end point is distributed like a sample from .
For
for the width of each , for the spread of the centres. width, centres.Width is , which shrinks as grows.- All of it is lost:
has variance .The rest moved into the randomness of the centre ; nothing is lost, since averages to .
Practice
Localizing a GaussianThe example that explains everything
Let
Outline
, so .Why?
Multiply the two Gaussian factors and complete the square: the precision is
and the linear coefficient is . .Why?
Multiply numerator and denominator by
: . .Why?
; add.
The width and the spread trade places at
Where it landsThe martingale picks the end point
Show that if
Outline
is a bounded martingale, so .Why?
Dominated convergence, together with
for every .- The left side is
.Why?
It is the expectation of an indicator.
So running the process to
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.
- Localization process
- A random family of distributions that starts at the target, stays equal to it on average, and ends up concentrated at a single point.
- Martingale
- A random quantity whose expected future value, given everything seen so far, equals its current value.
- Exponential tilt
- Reweighting a distribution by an exponential of a linear function, which shifts its mass in one direction.
- Law of total variance
- Total variance equals the average variance within groups plus the variance of the group averages.
Localization as denoising
Draw one hidden point
The idea
Why it is a localization process.
Discrete time. Observe
The SDE, from the observer's side. The observer does not see
Check your understanding
Why is
- Tower property:
for . - Because the noise is Gaussian.Any increasing family of observations gives a martingale of beliefs; Gaussian noise only makes the posterior a Gaussian tilt.
- Because
concentrates.Concentration is the second property of a localization process; it is separate from the martingale property.
You see
- The sum
alone. - The sum and the sample variance of the
.The spread of the observations is pure noise here: the noise variance is known, so it carries no information about . - All three observations, in order.The likelihood depends on the observations only through
; the rest cancels in Bayes' rule.
With prior
: the noisy value shrunk toward the prior mean. .That ignores the prior; it would be right only if . .Denoising pulls toward the prior mean, not away from it.
Practice
Proving Tweedie's formulaDifferentiate the noisy density
Let
Outline
.Why?
and its gradient is times itself. .Why?
Differentiate under the integral sign and multiply by
.- Divide by
: .Why?
is the posterior density of given .
Differentiating once more gives the covariance formula. Neither needs any assumption on
Repeated observationsFrom many noisy looks to one
Show that
Outline
.Why?
Expand around
; the cross term vanishes because .- The second term does not involve
, so the likelihood is proportional to , the likelihood of one observation with noise variance .Why?
Factors that do not depend on
cancel in Bayes' rule.
So discrete time
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.
- Posterior
- What you believe about a hidden quantity after combining your prior belief with what you observed.
- Sufficient statistic
- A summary of the data that keeps everything the data say about the unknown, so the rest can be thrown away.
- Score
- The gradient of the log-density: the direction in which the density increases fastest, relative to its size.
- Tweedie's formula
- The best guess of a clean signal equals the noisy observation plus the noise variance times the score of the noisy data.
Curvature and conditioning
The Gaussian factor adds
The idea
Condition number. For
What localization is used for. In high-dimensional geometry, one proves an inequality for the strongly log-concave
The catch. Sampling one
Explore
Check your understanding
: same space, better shape.- A lower-dimensional subspace that shrinks with
. has a positive density on all of ; it is narrower, not flatter.
, down from . : the tilt cannot change the shape.The tilt can't, but the Gaussian factor adds to every eigenvalue. .That is the limit as ; at the large eigenvalue still dominates.
: , so .- Never: a double well stays bimodal.The Gaussian factor eventually overwhelms the dip; for
, is strictly convex. - Every
.For , is negative near 0, so is not convex and is not log-concave.
Practice
How long until the shape is fixed?A one-line design calculation
Find the smallest
Outline
.Why?
Multiply out:
.
So
Localizing a Gaussian in dimensionsComplete the square with matrices
Show that for
Outline
.Why?
Add the exponents of
and of the localization factor. .Why?
Expand the right side; the last term does not depend on
.
The precision
Two-block Gibbs samplers
To sample a pair
The idea
Two operators. Write
The proximal sampler as Gibbs. Take
Variance is not entropy. For KL divergence, data processing still gives
Explore
Check your understanding
In the 2D Gaussian with
- About 50:
. - About 1: each sweep resamples everything.Each half-step resamples one coordinate given the other, and when the coordinates are nearly equal that conditional barely moves.
- About 10,000.That would be
. The relevant quantity is .
- 1: take
and . - 0, since they are uncorrelated.Uncorrelated is not independent. Maximal correlation is 0 exactly when
and are independent.
You have proved that one half-step of a two-block Gibbs sampler contracts variance by a factor
: the other half-step is the adjoint, which has the same norm.- Only
, until the other half-step is analysed separately.For variance the adjoint argument covers it. That shortcut is what fails for KL.
Practice
The zigzag contracts by One sweep of the 2D Gaussian
For the Gibbs sampler on
Outline
and .Why?
For a standard bivariate Gaussian with correlation
, each conditional mean is times the other coordinate.- Tower property:
.Why?
Condition on
first, then on ; the chain is Markov. .Why?
Iterate:
, and the variance is 1 at stationarity.
The figure on the right checks this against a simulation. Here the maximal correlation of
Why the two half-steps contract equallyAdjoint operators have equal norms
Let
Outline
over mean-zero with .Why?
, and . Constants can be removed because maps mean-zero functions to mean-zero functions.- The same supremum computes
, with the roles of and swapped.Why?
. - That supremum is
.Why?
For mean-zero unit-variance
, is their correlation.
Hence
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.
- Gibbs sampler
- A sampler that updates one block of variables at a time by drawing it from its exact distribution given all the others.
- Maximal correlation
- The largest correlation you can create between two variables by transforming each of them separately; zero exactly when they are independent.
- Mixing time
- How many steps a sampler needs before its output is close to the target, whatever it started from.
- Adjoint
- The operator that does the same job in the opposite direction, so that pairing it with one side gives the same answer as pairing the original with the other.
Log-Laplace transforms and tilts
The quadratic
The idea
Curvature duality. If
LLT versus Fenchel conjugate.
Localization with non-Gaussian noise. Observe
Explore
Check your understanding
Why is every log-Laplace transform convex, with no assumption on
- Its Hessian is a covariance matrix, which is positive semidefinite.
- Because
is convex and the transform preserves convexity.Convexity of is not needed: is convex for every measure (Hölder's inequality also shows it).
- No: a law with bounded support is not infinitely divisible, so some fractional multiples
are not cumulant generating functions. - Yes: every
is still convex.Convexity is necessary but not sufficient; being a CGF also needs to be the Laplace transform of a probability measure.
In the figure, choose
- It shrinks: the tilt sits near
, where the curvature is large, so the variance is about . - It stays 1, as in the Gaussian case.Only the Gaussian has constant curvature, hence constant tilt variance.
- It grows without bound.That happens for
, whose curvature decays: there the tilts get wider.
Practice
The Gaussian LLTComplete the square once more
Let
Outline
.Why?
Expand the right side; the cross terms reproduce
.- Integrating over
leaves .Why?
The remaining Gaussian integral equals the normalizing constant already absorbed in
.
So
Two uniforms make a triangleConvolution adds LLTs
Let
Outline
.Why?
. .Why?
Either compute the integral directly, or note that the triangle is the density of
and the moment generating function of an independent sum is the product.
Taking logarithms,
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.
- Log-Laplace transform
- The logarithm of the normalizing constant of a distribution after exponential reweighting, as a function of the reweighting direction.
- Cumulant
- The quantities read off from derivatives of the log of the moment generating function: the mean, the covariance, then higher-order shape.
- Infinitely divisible
- A distribution that can be written, for every n, as the sum of n independent identical pieces.
- Fenchel conjugate
- For each slope, the largest gap between a straight line of that slope and the graph of a convex function.
Poincaré, log-Sobolev and mirror geometry
Two inequalities control how fast samplers forget their start: a Poincaré inequality controls variance and
The idea
Where the asymmetry is. Call
| start is | contraction in | needs | steps to reach | |
|---|---|---|---|---|
| a PI | ||||
| KL | an LSI |
Feasible starting points are often only
A caution from numerics. In the Functional Stochastic Localization project, exact one-dimensional computations with a regularizer
Explore
Check your understanding
A sampler starts
- About 1450 for
, about 17 for KL. - About the same: both contract by
.The rate is the same, but the starting value is not: starts near , KL near . - About 7 for both.
needs halvings.
- An
- -Poincaré inequality, by Brascamp–Lieb; an - -log-Sobolev inequality does not follow in general. - Both, by Bakry–Émery.Bakry–Émery is a Euclidean statement (curvature against the identity metric). Its mirror analogue fails in general.
- Neither, unless
is quadratic.The Poincaré inequality transfers directly: inverts to .
When is the Cramér–Rao bound
- Exactly when
is quadratic, i.e. is Gaussian. - Whenever
is convex.Try in the figure: the variance sits strictly above .
Practice
Cramér–Rao by integration by partsThe lower end of the sandwich
Let
Outline
, where .Why?
, so after integrating by parts. .Why?
Integrate by parts the same way:
.- Cauchy–Schwarz:
.Why?
Combine with the previous step.
Convexity was never used: the bound needs only
log-Sobolev implies PoincaréLinearize near the constant function
Show that a
Outline
- Apply the LSI to
with .Why?
Small perturbations of a constant probe the inequality near equality, where entropy behaves like variance.
.Why?
Expand
around : , with ; the linear terms cancel against .- The right side is
. Divide by and let .Why?
.
The same argument works in any metric, so a
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.
- Log-Sobolev inequality
- A bound on how much information a function can carry relative to how fast it changes; it controls how quickly KL divergence decays.
- Brascamp–Lieb inequality
- Variance is at most the average of the inverse curvature of the log-density: sharply curved distributions are narrow.
- Cramér–Rao bound
- Variance is at least the inverse of the average curvature of the log-density, with equality only for Gaussians.
- Mirror geometry
- Measuring lengths and gradients with the Hessian of a convex function instead of the usual Euclidean ruler.
- Relative strong convexity
- A function is strongly convex relative to another if subtracting a multiple of the other still leaves it convex.
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.