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.

InteractiveEldan (2013); Chen–Eldan (2022), §2

Random measures that average to the target

Hard questions about one distribution π become easier questions about many random distributions πt, each narrower and better behaved than π, provided that πt averages back to π exactly. That averaging property is a martingale, and it is what lets conclusions about the πt transfer back to π.

The idea

Localization process. A family of random probability measures (πt)t≥0 on Rd, with π0=π, such that
  1. for every set A, t↦πt(A) is a martingale, so E[πt(A)]=π(A);
  2. for every set A, πt(A)→0 or 1 almost surely as t→∞.
Property 2 is the localization: every realization ends up concentrated on a single point.
Eldan's construction. Reweight π by a random linear tilt and a deterministic Gaussian factor:
πt(x)=1Ztπ(x)exp(⟨ct,x⟩−t2‖x‖2),
where ct∈Rd is a random vector (specified in Localization as denoising) and Zt normalizes. The Gaussian factor fixes how much mass concentrates; the tilt picks where.

What E[πt]=π means. An expectation is a number, so how can the expectation of a distribution be a distribution? Fix a point x. Then πt(x) is a single real number that depends on the random path of the process, so it is a real-valued random variable, and the claim is E[πt(x)]=π(x) for every x. The randomness being averaged is that of the process, not that of a point drawn from π. Doing this at every x at once gives a deterministic function of x, which is π. (Compare: E[πt(x)] is a number, but the conditional expectation E[πt(x)∣πs]=πs(x), s<t, is again random.)

Why it concentrates. log⁡πt(x)=log⁡π(x)+⟨ct,x⟩−t2‖x‖2+const. The first term does not change with t; the last grows linearly in t. For large t, log⁡π is negligible except near the peak, and πt is a narrow Gaussian bump, whatever π looked like.

Variance is transferred, not lost. If X is drawn by first drawing the random measure πt and then X∼πt, then X∼π, because E[πt]=π. The law of total variance then splits the covariance of π into two parts:
Covπ(X)=E[Cov(πt)]⏟width of each πt+Cov(mt)⏟spread of the centres,mt=Eπt[X].
As t grows, the first term shrinks to 0 and the second grows to all of Covπ(X).

The Gaussian example. For π=N(0,1), completing the square gives πt=N(mt,11+t) with mt=ct/(1+t), and Var(mt)=t1+t. The split is 1=11+t+t1+t.

Explore

Target
six realizations of πt; the average of 400 realizations; the target π (dashed).
Varπ split into EVar(πt) and Var(mt), against t (log scale).

Check your understanding

Fix a point x and a time t>0. What kind of object is πt(x)?

  1. A random number, depending on the path of the process; its expectation is the number π(x).
  2. A fixed number equal to π(x).Only its average is π(x). Individual realizations are far from π(x): most are near 0, a few are huge.
  3. A probability distribution over x.That is πt as a whole. Evaluated at one point it is a single number, random because πt is.
The process is a random function. Pointwise, it is a random variable, and the martingale property says its expectation stays equal to π(x) at every time.

The target puts mass 0.3 on its left bump and 0.7 on its right bump. As t→∞, each realization of πt piles up on one bump. How often on the left one?

  1. With probability 0.3: πt(left) is a martingale that ends at 0 or 1, and its expectation stays 0.3.
  2. Never: the process always prefers the heavier bump.Then E[πt(left)] would drop to 0, breaking the martingale property.
  3. With probability 1/2, by symmetry of the noise.The noise is symmetric but the target is not; the end point is distributed like a sample from π.
A bounded martingale converges, and if its limit is 0 or 1, the probability of 1 equals its starting value. Try it in the figure with Two bumps and large t: the fraction of draws that end on each bump matches the bump's mass.

For π=N(0,1) at t=3, how is the variance 1 split?

  1. 14 for the width of each πt, 34 for the spread of the centres.
  2. 34 width, 14 centres.Width is 1/(1+t), which shrinks as t grows.
  3. All of it is lost: πt has variance 14.The rest moved into the randomness of the centre mt; nothing is lost, since πt averages to π.
Var(πt)=11+t=14 and Var(mt)=t1+t=34.

Practice

Localizing a GaussianThe example that explains everything

Let π=N(0,s2) on R, and suppose ct∼N(0,t2s2+t) (this is what the process of the next module produces). Find the law of πt, and check that EVar(πt)+Var(mt)=s2.

Outline
  1. πt(x)∝exp(−12(s−2+t)x2+ctx), so πt=N(ct/(s−2+t), 1/(s−2+t)).
    Why?

    Multiply the two Gaussian factors and complete the square: the precision is s−2+t and the linear coefficient is ct.

  2. Var(mt)=t2s2+t(s−2+t)2=ts41+ts2.
    Why?

    Multiply numerator and denominator by s4: (t2s6+ts4)/(1+ts2)2=ts4(1+ts2)/(1+ts2)2.

  3. s21+ts2+ts41+ts2=s2.
    Why?

    1/(s−2+t)=s2/(1+ts2); add.

The width and the spread trade places at t=1/s2: a wide target needs little time to localize, a narrow one needs a lot.

Where it landsThe martingale picks the end point

Show that if πt(A)→1{the limit point lies in A} almost surely, then the limit point is distributed exactly according to π.

Outline
  1. πt(A)∈[0,1] is a bounded martingale, so E[limtπt(A)]=limtE[πt(A)]=π(A).
    Why?

    Dominated convergence, together with E[πt(A)]=π0(A)=π(A) for every t.

  2. The left side is Pr(limit point∈A).
    Why?

    It is the expectation of an indicator.

So running the process to t=∞ is a sampler for π, if each step can be simulated. That observation is the starting point of algorithmic stochastic localization.

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.
Read and checkEl Alaoui–Montanari (2022); Efron (2011)

Localization as denoising

Draw one hidden point X∼π and watch it through noise that gets weaker over time. Your belief about X is a random distribution, it averages to π, and it collapses onto X as the noise fades. That is a localization process, with no stochastic calculus needed, and its centre is a denoiser of exactly the kind diffusion models learn.

The idea

The Gaussian channel. Draw X∼π once. Observe Yt=tX+Wt, t≥0, where W is a Brownian motion independent of X. Equivalently Yt/t=X+N(0,1tI): the signal-to-noise ratio is t. Bayes' rule gives the posterior
πt(x)=Pr(X∈dx∣(Ys)s≤t)∝π(x)exp(⟨Yt,x⟩−t2‖x‖2),
which is Eldan's πt with ct=Yt. Only the current value Yt matters.

Why it is a localization process. πt(A)=Pr(X∈A∣Ft) is a conditional probability given more and more information, so it is a martingale by the tower property: averaging a later belief over what you will learn returns your current belief. And Yt/t→X as t→∞, so the posterior collapses onto the true X. The point it localizes to is the hidden sample, which explains why that point is distributed as π.

Discrete time. Observe Ai=X+Zi, i=1,…,τ, with independent Zi∼N(0,I). The likelihood ∏ie−‖Ai−x‖2/2 is proportional, as a function of x, to exp⁡(⟨∑iAi,x⟩−τ2‖x‖2). So the posterior depends on the observations only through their sum, a sufficient statistic, and it equals πτ with cτ=∑iAi. This discrete version is the one that generalizes beyond Gaussian noise (Log-Laplace transforms).

The SDE, from the observer's side. The observer does not see X, only Y. Replacing the unknown drift Xdt by its current best guess gives

dct=mtdt+dBt,mt=Eπt[X]=E[X∣Ft],
where B is a Brownian motion for the observer (the innovation). This is the SDE in Eldan's original definition. Itô's formula then gives dπt(x)=πt(x)⟨x−mt,dBt⟩: there is no dt term, which is the martingale property again. (For why the Itô integral, with its left-endpoint convention, makes a driftless SDE a martingale, see Integrating against noise.)

Tweedie's formula. If Y=X+σZ with Z∼N(0,I) independent of X, and p is the density of Y, then
E[X∣Y=y]=y+σ2∇log⁡p(y),Cov(X∣Y=y)=σ2I+σ4∇2log⁡p(y).
The best denoiser is a step up the gradient of the log-density of the noisy data, its score. This is why learning a score (as diffusion models do) is the same as learning to denoise, and why the centre mt of a localization process is a denoiser at noise level σ2=1/t.

Check your understanding

Why is t↦Pr(X∈A∣Ft) a martingale, whatever π is?

  1. Tower property: E[Pr(X∈A∣Ft)∣Fs]=Pr(X∈A∣Fs) for s<t.
  2. Because the noise is Gaussian.Any increasing family of observations gives a martingale of beliefs; Gaussian noise only makes the posterior a Gaussian tilt.
  3. Because πt concentrates.Concentration is the second property of a localization process; it is separate from the martingale property.
Beliefs updated by Bayes' rule are a martingale for any prior and any observation model. This is why the denoising view gives localization processes so cheaply.

You see τ=3 noisy copies Ai=X+Zi. Which of these determines the posterior of X?

  1. The sum A1+A2+A3 alone.
  2. The sum and the sample variance of the Ai.The spread of the observations is pure noise here: the noise variance is known, so it carries no information about X.
  3. All three observations, in order.The likelihood depends on the observations only through ⟨∑iAi,x⟩; the rest cancels in Bayes' rule.
For a location family with Gaussian noise, the sum (equivalently the mean) is sufficient. The non-Gaussian generalization replaces Gaussian noise by an exponential family, where the same thing happens.

With prior X∼N(0,1) and Y=X+σZ, what does Tweedie's formula give for E[X∣Y=y]?

  1. y/(1+σ2): the noisy value shrunk toward the prior mean.
  2. y.That ignores the prior; it would be right only if σ=0.
  3. y(1+σ2).Denoising pulls toward the prior mean, not away from it.
Y∼N(0,1+σ2), so ∇log⁡p(y)=−y/(1+σ2) and y+σ2⋅(−y/(1+σ2))=y/(1+σ2).

Practice

Proving Tweedie's formulaDifferentiate the noisy density

Let φσ be the N(0,σ2I) density and p(y)=∫π(x)φσ(y−x)dx. Show E[X∣Y=y]=y+σ2∇log⁡p(y).

Outline
  1. ∇yφσ(y−x)=−y−xσ2φσ(y−x).
    Why?

    φσ(u)∝e−‖u‖2/(2σ2) and its gradient is −u/σ2 times itself.

  2. σ2∇p(y)=∫(x−y)π(x)φσ(y−x)dx.
    Why?

    Differentiate under the integral sign and multiply by σ2.

  3. Divide by p(y): σ2∇log⁡p(y)=E[X−y∣Y=y].
    Why?

    π(x)φσ(y−x)/p(y) is the posterior density of X given Y=y.

Differentiating once more gives the covariance formula. Neither needs any assumption on π: the Gaussian noise does all the work.

Repeated observationsFrom many noisy looks to one

Show that τ independent observations Ai=X+Zi with Zi∼N(0,I) carry exactly the same information about X as the single observation A¯=1τ∑iAi=X+N(0,1τI).

Outline
  1. ∑i‖Ai−x‖2=τ‖A¯−x‖2+∑i‖Ai−A¯‖2.
    Why?

    Expand around A¯; the cross term vanishes because ∑i(Ai−A¯)=0.

  2. The second term does not involve x, so the likelihood is proportional to e−τ‖A¯−x‖2/2, the likelihood of one observation with noise variance 1/τ.
    Why?

    Factors that do not depend on x cancel in Bayes' rule.

So discrete time τ and continuous time t describe the same posteriors at t=τ. Discrete time is only a restriction when the noise is not Gaussian.

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.
InteractiveEldan (2013); Chen–Eldan (2022)

Curvature and conditioning

The Gaussian factor adds tI to the Hessian of the potential. Once t exceeds any negative curvature of the potential, every πt is strongly log-concave, even when π is not log-concave at all, and its condition number falls toward 1. The dimension does not change at all: the gain is in shape, not size.

The idea

Log-concavity. Write π∝e−V. The matrix ∇2V(x)=−∇2log⁡π(x) measures how sharply the density falls off around x. π is log-concave if ∇2V⪰0 everywhere and α-strongly log-concave if ∇2V⪰αI. For N(0,Σ), ∇2V=Σ−1: large curvature means small variance.
The Hessian shift. The localized potential is Vt(x)=V(x)+t2‖x‖2−⟨ct,x⟩+const, so
∇2Vt=∇2V+tI.
The random tilt disappears after two derivatives. If V is convex, every πt is t-strongly log-concave. If V is not convex but ∇2V⪰−λI, every πt with t>λ is (t−λ)-strongly log-concave.

Condition number. For π=N(0,H−1) with the eigenvalues of H in [m,L],

πt=N((H+tI)−1ct, (H+tI)−1),κ=Lm ⟶ κt=L+tm+t.
A large κ means π is long in some directions and thin in others, which forces gradient-based samplers into small steps (stability in the thin directions) and many of them (to cross the long ones). After localization, κt≤1+L/t however small m is.

What localization is used for. In high-dimensional geometry, one proves an inequality for the strongly log-concave πt, where it is easy, and transfers it back to π through the martingale property. This is the route to the recent progress on the Kannan–Lovász–Simonovits conjecture about isoperimetry of convex bodies (see Bottlenecks and the Poincaré constant for what isoperimetry measures). In sampling, the regularized πt are the conditional distributions of the proximal sampler (In-and-Out): one alternates between adding noise and sampling a localized distribution.

The catch. Sampling one πt is not sampling π. A sampler built from πt must also move between them, and the larger t is, the less each step moves. The next module makes this trade-off exact.

Explore

π=N(0,H−1) (dashed) with H of eigenvalues 1/κ and 1; one realization of πt; its centre mt. Contours at 1 and 2 standard deviations.
κt=(L+t)/(m+t) against t, log–log; the current t.

Check your understanding

π lives on R1000. On what space does πt live?

  1. R1000: same space, better shape.
  2. A lower-dimensional subspace that shrinks with t.πt has a positive density on all of R1000; it is narrower, not flatter.
Localization does not reduce dimension. What improves is conditioning, which is what controls the step size and the number of steps of a sampler.

L=100, m=0.01. What is κt at t=1?

  1. 101/1.01=100, down from 104.
  2. 104: the tilt cannot change the shape.The tilt can't, but the Gaussian factor adds t to every eigenvalue.
  3. 1.That is the limit as t→∞; at t=1 the large eigenvalue still dominates.
Adding t helps the small eigenvalues a lot and the large ones hardly at all, which is exactly what improves the ratio.

V(x)=x4/4−x2 on R is a double well, so π∝e−V is not log-concave. For which t is πt guaranteed to be strongly log-concave?

  1. t>2: V″(x)=3x2−2≥−2, so Vt″≥t−2.
  2. Never: a double well stays bimodal.The Gaussian factor eventually overwhelms the dip; for t>2, Vt is strictly convex.
  3. Every t>0.For t<2, Vt″=3x2−2+t is negative near 0, so Vt is not convex and πt is not log-concave.
A lower bound ∇2V⪰−λI is all that is needed. This is why localization is useful for non-log-concave targets too.

Practice

How long until the shape is fixed?A one-line design calculation

Find the smallest t with κt≤2, in terms of m≤L. What happens as m→0?

Outline
  1. L+tm+t≤2⟺t≥L−2m.
    Why?

    Multiply out: L+t≤2m+2t.

So t≈L suffices, independently of how small m is. The bad direction is cured by the regularizer, not by the target.

Localizing a Gaussian in d dimensionsComplete the square with matrices

Show that for π=N(0,H−1), πt=N((H+tI)−1ct,(H+tI)−1).

Outline
  1. log⁡πt(x)=−12xT(H+tI)x+⟨ct,x⟩+const.
    Why?

    Add the exponents of π and of the localization factor.

  2. −12xTAx+⟨c,x⟩=−12(x−A−1c)TA(x−A−1c)+12cTA−1c.
    Why?

    Expand the right side; the last term does not depend on x.

The precision H+tI is deterministic; only the mean is random. Every realization has the same shape, which is why the condition number is a property of t alone.

SimulationChen–Eldan (2022); Rényi (1959); Caputo–Chen–Gu–Polyanskiy (2025)

Two-block Gibbs samplers

To sample a pair (X,Y), alternately resample each one given the other. The proximal sampler is this scheme with Y a noisy copy of X. How fast it mixes is governed by a single number, the maximal correlation between the two blocks, and the same number controls both half-steps.

The idea

Two-block Gibbs. Given a joint law π~(x,y), repeat: draw y∼π~(⋅∣x), then x′∼π~(⋅∣y). If x has the x-marginal π, so does x′: each half-step resamples one coordinate from its exact conditional, which keeps the joint law invariant. So π is stationary, with no tuning and no rejections.

Two operators. Write (Kg)(x)=E[g(Y)∣X=x] and (K∗f)(y)=E[f(X)∣Y=y]. They are adjoint in L2: E[f(X)(Kg)(X)]=E[f(X)g(Y)]=E[(K∗f)(Y)g(Y)]. One full step from x to x′ is the operator P=KK∗.

Maximal correlation (Hirschfeld, Gebelein, Rényi).
ρ(X,Y)=sup{corr(f(X),g(Y)): f,g with finite, nonzero variance}.
It is the norm of K (and of K∗) on mean-zero functions. For jointly Gaussian (X,Y), ρ is the ordinary correlation, attained by linear f and g; in general it can be much larger than the linear correlation.
Variance contraction. For every f,
Var(Pf)≤ρ4Var(f),soχ2(μk‖π)≤ρ4kχ2(μ0‖π).
Each half-step contracts variance by ρ2, and the backward half-step contracts exactly as much as the forward one, because adjoint operators have equal norms. Proving a bound for the easier of the two channels is enough.

The proximal sampler as Gibbs. Take π=N(0,1/m) and the joint law Y=τX+τZ (that is, τ unit-variance noisy observations, summed). The correlation is ρ2=τ/(m+τ), and E[Xk+1∣Xk]=τm+τXk. Larger τ makes each conditional X∣Y easier (it is the localized πτ), but makes Xk+1 more correlated with Xk: mixing takes about τ/m steps. This is the trade-off promised in Curvature and conditioning.

Variance is not entropy. For KL divergence, data processing still gives KL(μP‖π)≤KL(μ‖π), but the adjoint argument has no analogue: a strong contraction of one half-step does not imply the same for the other, and there are counterexamples (Caputo, Chen, Gu and Polyanskiy, 2025). KL rates for Gibbs samplers need both channels handled separately.

Explore

Gibbs on N(0,(1rr1)): the path, alternating x∣y∼N(ry,1−r2) and y∣x∼N(rx,1−r2); the current point.
Correlation between xj and xj+k against the lag k: estimated from a long run; the prediction r2k.

Check your understanding

In the 2D Gaussian with r=0.99, roughly how many sweeps does it take for the correlation between x0 and xk to fall to 1/e?

  1. About 50: r2k=0.9801k≈e−0.02k.
  2. 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.
  3. About 10,000.That would be 1/(1−r)2. The relevant quantity is 1/(1−r2)≈1/(2(1−r))=50.
Mixing time scales like 1/(1−ρ2). Strongly coupled blocks make Gibbs slow; this is the price of a large localization time.

X∼N(0,1) and Y=X2. The linear correlation of X and Y is 0. What is their maximal correlation?

  1. 1: take f(x)=x2 and g(y)=y.
  2. 0, since they are uncorrelated.Uncorrelated is not independent. Maximal correlation is 0 exactly when X and Y are independent.
A Gibbs sampler on this pair would never mix: Y determines |X| completely. Linear correlation can badly underestimate how coupled two blocks are; maximal correlation can't.

You have proved that one half-step of a two-block Gibbs sampler contracts variance by a factor β. What do you get for a full step?

  1. β2: the other half-step is the adjoint, which has the same norm.
  2. Only β, until the other half-step is analysed separately.For variance the adjoint argument covers it. That shortcut is what fails for KL.
The norm of K on mean-zero functions equals the norm of K∗. This is the step that makes variance (and χ2) analyses of Gibbs samplers so much easier than entropy analyses.

Practice

The zigzag contracts by r2One sweep of the 2D Gaussian

For the Gibbs sampler on N(0,(1rr1)), show E[xk+1∣xk]=r2xk and deduce corr(x0,xk)=r2k at stationarity.

Outline
  1. E[y∣xk]=rxk and E[xk+1∣y]=ry.
    Why?

    For a standard bivariate Gaussian with correlation r, each conditional mean is r times the other coordinate.

  2. Tower property: E[xk+1∣xk]=rE[y∣xk]=r2xk.
    Why?

    Condition on y first, then on xk; the chain is Markov.

  3. Cov(x0,xk)=r2kVar(x0).
    Why?

    Iterate: E[x0xk]=E[x0E[xk∣x0]]=r2kE[x02], and the variance is 1 at stationarity.

The figure on the right checks this against a simulation. Here the maximal correlation of (x,y) is ρ=r, and the bound Var(Pf)≤r4Var(f) is attained by f(x)=x: E[xk+1∣xk]=r2xk has variance r4. Linear functions are the slowest to mix.

Why the two half-steps contract equallyAdjoint operators have equal norms

Let K and K∗ be as above, restricted to mean-zero functions. Show ‖K‖=‖K∗‖=ρ.

Outline
  1. ‖K‖=supf,gE[f(X)g(Y)] over mean-zero f,g with Ef2=Eg2=1.
    Why?

    ‖Kg‖=sup‖f‖=1E[f(X)(Kg)(X)], and E[f(X)(Kg)(X)]=E[f(X)g(Y)]. Constants can be removed because K maps mean-zero functions to mean-zero functions.

  2. The same supremum computes ‖K∗‖, with the roles of f and g swapped.
    Why?

    E[(K∗f)(Y)g(Y)]=E[f(X)g(Y)].

  3. That supremum is ρ(X,Y).
    Why?

    For mean-zero unit-variance f,g, E[f(X)g(Y)] is their correlation.

Hence Var(KK∗f)≤ρ2Var(K∗f)≤ρ4Var(f). For entropy there is no adjoint identity of this kind, which is why KL analyses must treat each half-step on its own.

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.
InteractiveGopi–Lee–Liu–Shen–Tian (2023); Gu–Shi–Tian (2026), §2–3

Log-Laplace transforms and tilts

The quadratic t2‖x‖2 in Eldan's construction is the log-normalizer of Gaussian noise. Use noise from any exponential family instead and the quadratic becomes that family's log-normalizer, its log-Laplace transform. Its gradient is a mean, its Hessian a covariance, and it adds up under convolution. Which multiples of it are allowed turns out to be a question about infinite divisibility.

The idea

Log-Laplace transform and tilt. For convex φ with ∫e−φ=1, so that e−φ is the density of a random vector Y,
ψ(x)=φ♯(x)=log⁡∫e⟨x,y⟩−φ(y)dy=log⁡Ee⟨x,Y⟩,Txe−φ(y)=e⟨x,y⟩−φ(y)−ψ(x).
ψ is the cumulant generating function of Y, and the tilts Txe−φ, x∈Rd, form an exponential family with log-partition function ψ (as on Information Geometry).
Derivatives are cumulants. Wherever ψ is finite,
∇ψ(x)=ETxe−φ[Y],∇2ψ(x)=CovTxe−φ(Y),∇3ψ(x)[h,h,h]=E[⟨Y−∇ψ(x),h⟩3].
So ψ is smooth and convex, and tilting further in direction h moves the mean by ∇2ψ(x)h: a family with large variance responds strongly to tilting.

Curvature duality. If mI⪯∇2φ⪯LI, then 1LI⪯∇2ψ⪯1mI: the upper bound is Brascamp–Lieb and the lower is Cramér–Rao, both in the next module. This mirrors the Fenchel conjugate φ∗, whose Hessian is exactly the inverse of ∇2φ. More generally, smoothness of φ in a norm gives strong convexity of ψ in the dual norm, which makes LLTs usable as mirror maps for non-Euclidean geometries such as ℓp (Gopi, Lee, Liu, Shen and Tian, 2023).

LLT versus Fenchel conjugate. φ∗(x)=supy(⟨x,y⟩−φ(y)) keeps only the largest term of the integral that defines ψ. Laplace's method gives

ψ(x)≈φ∗(x)−12log⁡det∇2φ(yx)+d2log⁡2π,yx=∇φ∗(x),
exactly for quadratics. At large scales the LLT behaves like the convex conjugate, with a logarithmic correction from the curvature.

Convolution adds LLTs. If Y1,…,Yτ are independent copies of Y, then log⁡Ee⟨x,Y1+⋯+Yτ⟩=τψ(x). Writing e−φ∗τ for the density of the sum, (φ∗τ)♯=τψ.

Localization with non-Gaussian noise. Observe A1,…,Aτ independently from TXe−φ, with X∼π. The likelihood of each is e⟨x,ai⟩−φ(ai)−ψ(x), so the posterior is

πτ(x)∝π(x)exp(⟨∑iAi,x⟩−τψ(x)),
a localization process exactly as in Localization as denoising, with the regularizer τψ in place of τ2‖x‖2.

Which multiples are allowed? tψ is the cumulant generating function of some law for every t>0 exactly when the law of Y is infinitely divisible: for each n it is the law of a sum of n i.i.d. pieces. Gaussian, Gamma and Laplace laws are infinitely divisible. No law with bounded support is, apart from point masses, so for a uniform Y only integer multiples τψ are guaranteed. That is why the general construction runs in discrete time τ∈N: a continuous-time version built from infinitesimal convolutions would be pushed back to Gaussian noise by the central limit theorem.

Explore

Base density
e−φ (dashed) and the tilt Txe−φ, with its mean ψ′(x).
ψ(x)−ψ(0) and the Fenchel conjugate φ∗(x)−φ∗(0) (dashed); the current tilt.

Check your understanding

Why is every log-Laplace transform convex, with no assumption on φ?

  1. Its Hessian is a covariance matrix, which is positive semidefinite.
  2. Because φ is convex and the transform preserves convexity.Convexity of φ is not needed: log⁡∫e⟨x,y⟩μ(dy) is convex for every measure μ (Hölder's inequality also shows it).
Convexity of φ buys more: self-concordance of ψ, and a log-concave family of tilts.

Y is uniform on [−1,1], with LLT ψ(x)=log⁡sinh⁡xx. Is tψ the LLT of some distribution for every real t>0?

  1. No: a law with bounded support is not infinitely divisible, so some fractional multiples tψ are not cumulant generating functions.
  2. Yes: every tψ is still convex.Convexity is necessary but not sufficient; being a CGF also needs etψ to be the Laplace transform of a probability measure.
Integer multiples are always fine: 2ψ is the LLT of the sum of two independent uniforms, a triangular law. This asymmetry between integer and real multiples is the whole reason for discrete time.

In the figure, choose y4/4 and push the tilt up. What happens to the variance ψ″(x) of the tilt?

  1. It shrinks: the tilt sits near y≈x1/3, where the curvature 3y2 is large, so the variance is about 1/(3x2/3).
  2. It stays 1, as in the Gaussian case.Only the Gaussian has constant curvature, hence constant tilt variance.
  3. It grows without bound.That happens for 23|y|3/2, whose curvature decays: there the tilts get wider.
The geometry ∇2ψ varies from point to point, unlike the Euclidean I. That is what makes these regularizers able to fit non-Euclidean problems, and what makes their analysis harder.

Practice

The Gaussian LLTComplete the square once more

Let e−φ be the N(μ,Σ) density. Show ψ(x)=⟨x,μ⟩+12xTΣx and that every tilt is N(μ+Σx,Σ).

Outline
  1. ⟨x,y⟩−12(y−μ)TΣ−1(y−μ)=−12(y−μ−Σx)TΣ−1(y−μ−Σx)+⟨x,μ⟩+12xTΣx.
    Why?

    Expand the right side; the cross terms reproduce ⟨x,y⟩.

  2. Integrating over y leaves exp⁡(⟨x,μ⟩+12xTΣx).
    Why?

    The remaining Gaussian integral equals the normalizing constant already absorbed in φ.

So ∇ψ=μ+Σx and ∇2ψ=Σ=(∇2φ)−1: for Gaussians the LLT and the Fenchel conjugate agree up to a constant.

Two uniforms make a triangleConvolution adds LLTs

Let Y be uniform on [−1,1]. Compute ψ, and check that 2ψ is the LLT of the triangular density 14(2−|y|)+ of Y1+Y2.

Outline
  1. EexY=12∫−11exydy=sinh⁡xx.
    Why?

    ∫−11exydy=(ex−e−x)/x.

  2. ∫14(2−|y|)+exydy=(sinh⁡xx)2.
    Why?

    Either compute the integral directly, or note that the triangle is the density of Y1+Y2 and the moment generating function of an independent sum is the product.

Taking logarithms, 2ψ is an LLT. For large x, ψ(x)=|x|−log⁡(2|x|)+o(1): the Fenchel conjugate |x| of the uniform's indicator potential, minus a logarithmic correction, as Laplace's method predicts.

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.
InteractiveBrascamp–Lieb (1976); Bakry–Émery (1985); Bobkov–Ledoux (2000)

Poincaré, log-Sobolev and mirror geometry

Two inequalities control how fast samplers forget their start: a Poincaré inequality controls variance and χ2, a log-Sobolev inequality controls entropy and KL. Curvature gives both in Euclidean geometry. In a curved (mirror) geometry curvature still gives the first, but not the second, and that gap is the difference between needing log⁡M and log⁡log⁡M steps from an M-warm start.

The idea

Two inequalities. For π∝e−V on Rd and all smooth f:
Poincaré (PI):Varπ(f)≤1αEπ‖∇f‖2,log-Sobolev (LSI):Entπ(f2)≤2ρEπ‖∇f‖2,
with Entπ(g)=Eπ[glog⁡g]−Eπglog⁡Eπg. A ρ-LSI implies a ρ-PI, but not conversely. For what a Poincaré constant measures geometrically, see Bottlenecks and the Poincaré constant.
Curvature gives both (Euclidean case). If ∇2V⪰αI, then π satisfies an α-LSI (Bakry–Émery), hence an α-PI. More precisely, for strictly convex V there is a two-sided bound on the covariance:
(Eπ∇2V)−1⏟Cramér–Rao ⪯ Covπ(X) ⪯ Eπ[(∇2V)−1]⏟Brascamp–Lieb,
and Brascamp–Lieb holds for every function: Varπ(f)≤Eπ[∇fT(∇2V)−1∇f]. Both ends are equalities for Gaussians.
Mirror versions. Fix a convex ψ and measure gradients in the local metric ∇2ψ instead of the identity:
Varπ(f)≤1αEπ[∇fT(∇2ψ)−1∇f](α-ψ-PI),Entπ(f2)≤2ρEπ[∇fT(∇2ψ)−1∇f](ρ-ψ-LSI).
For ψ=12‖x‖2 these are the usual inequalities. They are the natural hypotheses for samplers that move in the geometry of ψ: mirror Langevin, and the localization samplers with regularizer τψ.

Where the asymmetry is. Call V α-strongly convex relative to ψ if V−αψ is convex. Then ∇2V⪰α∇2ψ, and Brascamp–Lieb immediately gives an α-ψ-PI. There is no entropic Brascamp–Lieb inequality in general (Bobkov and Ledoux, 2000), so relative strong convexity does not give an α-ψ-LSI. Variance results transfer to mirror geometry for free; entropy results do not.

start is M-warm, socontraction inneedssteps to reach ε, up to the rateM=e1000
χ2(μ0‖π)≤M−1χ2a PIlog⁡(M/ε)≈1000
KL(μ0‖π)≤log⁡MKLan LSIlog⁡(log⁡M/ε)≈7

Feasible starting points are often only eO(d)-warm, so the difference between the two rows is a factor of the dimension. (For the divergences themselves and the meaning of warmness, see TV, KL and Rényi divergence.)

A caution from numerics. In the Functional Stochastic Localization project, exact one-dimensional computations with a regularizer ψ growing like |x|3 showed KL contracting strictly more slowly than the χ2 rate under relative strong convexity alone, at a rate matching the target's mirror-LSI constant. This is a numerical observation, not a theorem, but it is what the asymmetry above predicts.

Explore

Potential
the density ∝eyx−V(x) and the curvature V″(x) (right scale).
The variance squeezed between Cramér–Rao 1/EV″ and Brascamp–Lieb E[1/V″].

Check your understanding

A sampler starts M-warm with M=e1000. It contracts χ2 by 1/2 per step, or alternatively KL by 1/2 per step. Roughly how many steps does each need to reach ε=0.01?

  1. About 1450 for χ2, about 17 for KL.
  2. About the same: both contract by 1/2.The rate is the same, but the starting value is not: χ2 starts near e1000, KL near 1000.
  3. About 7 for both.χ2 needs log2⁡(e1000/0.01)≈1450 halvings.
log2⁡(e1000⋅100)≈1450 versus log2⁡(1000⋅100)≈17. This is why entropic (LSI-based) rates are worth fighting for.

V−αψ is convex. Which of these follows for π∝e−V, in general?

  1. An α-ψ-Poincaré inequality, by Brascamp–Lieb; an α-ψ-log-Sobolev inequality does not follow in general.
  2. Both, by Bakry–Émery.Bakry–Émery is a Euclidean statement (curvature against the identity metric). Its mirror analogue fails in general.
  3. Neither, unless ψ is quadratic.The Poincaré inequality transfers directly: ∇2V⪰α∇2ψ inverts to (∇2V)−1⪯1α(∇2ψ)−1.
For ψ=12‖x‖2 both hold. The gap only opens in a genuinely curved geometry.

When is the Cramér–Rao bound Var(X)≥1/E[V″(X)] an equality, for a density e−V on R?

  1. Exactly when V is quadratic, i.e. X is Gaussian.
  2. Whenever V is convex.Try x2/2+x4/4 in the figure: the variance sits strictly above 1/EV″.
The proof is Cauchy–Schwarz applied to V′(X) and X−EX (see Practice); equality forces V′ to be linear.

Practice

Cramér–Rao by integration by partsThe lower end of the sandwich

Let X have density e−V on R, with V smooth and e−V decaying fast enough at ±∞. Show Var(X)E[V″(X)]≥1.

Outline
  1. E[V′(X)(X−m)]=1, where m=EX.
    Why?

    V′e−V=−(e−V)′, so ∫(x−m)V′(x)e−V(x)dx=∫e−V=1 after integrating by parts.

  2. E[V′(X)2]=E[V″(X)].
    Why?

    Integrate by parts the same way: ∫V′⋅V′e−V=∫V″e−V.

  3. Cauchy–Schwarz: 1=E[V′(X)(X−m)]2≤E[V′2]Var(X).
    Why?

    Combine with the previous step.

Convexity was never used: the bound needs only EV″>0. Brascamp–Lieb, the upper end, genuinely needs V″>0 everywhere; try the double well in the figure.

log-Sobolev implies PoincaréLinearize near the constant function

Show that a ρ-LSI implies Varπ(g)≤1ρEπ‖∇g‖2.

Outline
  1. Apply the LSI to f=1+εg with Eπg=0.
    Why?

    Small perturbations of a constant probe the inequality near equality, where entropy behaves like variance.

  2. Entπ((1+εg)2)=2ε2Eπg2+O(ε3).
    Why?

    Expand ulog⁡u around u=1: ulog⁡u=(u−1)+12(u−1)2+O((u−1)3), with u=(1+εg)2; the linear terms cancel against Eulog⁡Eu.

  3. The right side is 2ρε2Eπ‖∇g‖2. Divide by 2ε2 and let ε→0.
    Why?

    ∇f=ε∇g.

The same argument works in any metric, so a ρ-ψ-LSI implies a ρ-ψ-PI. The converse is where the difficulty lies.

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.
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.