on Eldan's stochastic localization and the KLS conjecture

Overview

Lee and Vempala develop Eldan’s stochastic localization into a quantitative method for high-dimensional log-concave measures (Lee & Vempala, 2024). The method replaces one difficult measure by a measure-valued martingale whose time-$t$ members acquire a Gaussian factor. If the covariance of this process remains controlled long enough, the improved isoperimetry of the localized measures can be transferred back to the original law.

For an isotropic log-concave density on ${\mathbb{R}}^n$, this yields a Poincare constant of order $O(\sqrt{n})$ and hence an inverse-Cheeger, or KLS, scale of order $O(n^{1/4})$. A refined covariance argument based on a Stieltjes barrier gives a log-Sobolev constant $\Omega (1/D)$ when the support has diameter $D$. The resulting estimates imply sharper concentration inequalities and faster mixing bounds for the ball walk.

🏷️ Log-Concave Measures and Functional Constants

A probability density $p$ on ${\mathbb{R}}^n$ is log-concave if

$$p(x)=e^{-V(x)}$$

for a convex function $V:{\mathbb{R}}^n\to (-\infty ,+\infty ]$. It is isotropic when

$$\int xp(x)dx=0,\int x{x}^{\mathsf{T}}p(x)dx=I_n.$$

Isotropic position removes affine scaling from the problem: every direction then has variance one.

For a measurable set $S$, define its exterior boundary measure by

$$p^{+}(S)=\underset{\epsilon \downarrow 0}{\mathrm{liminf}}\frac{p(S_{\epsilon })-p(S)}{\epsilon },S_{\epsilon }=\{x:d(x,S)\le \epsilon \}.$$

The Cheeger expansion and its reciprocal are

$$h(p)=\underset{0<p(S)\le 1/2}{\inf }\frac{p^{+}(S)}{p(S)},\psi (p)=\frac{1}{h(p)}.$$

The Kannan-Lovasz-Simonovits conjecture asks whether $\psi (p)$ is bounded by a universal constant for every isotropic log-concave density. This is the isoperimetric formulation of KLS.

The Poincare constant $C_{\mathrm{P}}(p)$ is the least constant satisfying

$${\mathrm{Var}}_p(f)\le C_{\mathrm{P}}(p)\int \Vert \nabla f{\Vert }_2^{2}pdx$$

for all smooth $f$. Cheeger’s inequality gives

$$C_{\mathrm{P}}(p)\le \frac{4}{h(p{)}^2}=4\psi (p{)}^2.$$

This implication runs from isoperimetry to the spectral gap. The reverse direction uses log-concavity: a reverse-Cheeger principle gives

$$\psi (p)\le C\sqrt{C_{\mathrm{P}}(p)}.$$

Thus $\psi (p)\asymp \sqrt{C_{\mathrm{P}}(p)}$ within the log-concave class, and $C_{\mathrm{P}}(p)=O(\sqrt{n})$ implies $\psi (p)=O(n^{1/4})$.

The log-Sobolev constant $\rho (p)$ is normalized here by

$${\mathrm{Ent}}_p(f^2)\le \frac{2}{\rho (p)}\int \Vert \nabla f{\Vert }_2^{2}pdx,$$

where

$${\mathrm{Ent}}_p(f^2)=\int f^2\log \left(\frac{f^2}{\int f^{2}pdx}\right)pdx.$$

Unlike a spectral gap, a log-Sobolev inequality controls entropy and therefore gives Gaussian concentration by the Herbst argument.

Constant conventions

Some sources call $h(p)$ the Cheeger constant, while others call its reciprocal $\psi (p)$ the Cheeger or KLS constant. Likewise, some authors report the square root of the Poincare constant. The statements below always use $C_{\mathrm{P}}$ in the variance inequality and $\psi =1/h$.

🏷️ Analytic and Probabilistic Preliminaries

Affine Normalization

If $X$ has mean $m$ and positive-definite covariance $\Sigma$, then

$$T(X)={\Sigma }^{-1/2}(X-m)$$

is isotropic. Log-concavity is preserved because the transformed density is

$$q(y)=\det (\Sigma {)}^{1/2}p(m+{\Sigma }^{1/2}y).$$

Hence isotropic position is a normalization, not a restriction on full-dimensional measures. If $\Sigma$ is singular, one first restricts the measure to its affine hull.

Strong Log-Concavity

A density $q=e^{-U}/Z$ is $\alpha$-strongly log-concave if

$${\nabla }^{2}U⪰\alpha I_n.$$

The Brascamp-Lieb inequality gives

$${\mathrm{Var}}_q(f)\le \int ⟨({\nabla }^{2}U{)}^{-1}\nabla f,\nabla f⟩qdx,$$

so $C_{\mathrm{P}}(q)\le {\alpha }^{-1}$. Strong log-concavity also yields

$$h(q)\gtrsim \sqrt{\alpha },h_{\log }(q)\gtrsim \sqrt{\alpha },\rho (q)\gtrsim \alpha .$$

This is the analytic reason for inserting a Gaussian factor into the localization process.

Ito Calculus

For a continuous martingale $d{M}_t=⟨v_t,d{W}_t⟩$,

$$d[M{]}_t=\Vert v_t{\Vert }_2^{2}dt.$$

Ito’s formula reads

$$dF(M_t)=F^{\prime }(M_t)d{M}_t+\frac{1}{2}{F}^{\prime \prime }(M_t)d[M{]}_t.$$

The second-order term creates the favorable covariance drift $-A_t^{2}dt$, but it also creates positive corrections for nonlinear spectral potentials.

Warm Starts and Conductance

An initial law $\nu$ is $\beta$-warm with respect to $p$ if

$$\nu (S)\le \beta p(S)$$

for every measurable $S$. For a reversible Markov kernel $P$ with stationary law $p$, its conductance is

$$\Phi (P)=\underset{0<p(S)\le 1/2}{\inf }\frac{{\int }_{S}P(x,S^c)p(dx)}{p(S)}.$$

A standard estimate is

$$t_{\mathrm{mix}}(\epsilon )\lesssim \Phi (P{)}^{-2}\log \frac{\beta }{\epsilon }.$$

For the ball walk, local geometry compares $\Phi (P)$ with $h(p)$; this is the route from KLS to sampling.

Functional-inequality hierarchy

For log-concave measures, the relevant scales satisfy

$$\text{log-Sobolev}⟹\text{log-Cheeger}⟹\text{Cheeger}⟺\text{Poincare}.$$

The reverse direction in the last equivalence requires log-concavity.

🏷️ Principal Estimates

Lee-Vempala bounds

Let $p$ be an isotropic log-concave density on ${\mathbb{R}}^n$. There is a universal constant $C$ such that

$$C_{\mathrm{P}}(p)\le C\sqrt{n},\psi (p)\le C{n}^{1/4}.$$

Consequently, the thin-shell standard deviation

$$\sigma (p)={\left({\mathbb{E}}_p{\left(\Vert X{\Vert }_2-\sqrt{n}\right)}^2\right)}^{1/2}$$

and the natural Lipschitz-concentration scale are both $O(n^{1/4})$.

If, in addition, the support of $p$ has Euclidean diameter $D$, then

$$\rho (p)\ge \frac{c}{D}$$

for a universal $c>0$. This improves the earlier diameter dependence $\Omega (D^{-2})$ and is asymptotically sharp.

The theorem does not prove the dimension-free KLS conjecture. Its contribution is the exponent $1/4$: at the time of the work it improved the preceding $O(n^{1/3}\sqrt{\log n})$ inverse-expansion bound and placed Poincare, thin-shell, concentration, and sampling estimates under one stochastic mechanism.

🏷️ The Stochastic Localization Process

Let $p_0=p$, let $(W_t{)}_{t\ge 0}$ be standard Brownian motion in ${\mathbb{R}}^n$, and define a random density

$$p_t(x)=\frac{e^{⟨c_t,x⟩-\frac{t}{2}\Vert x{\Vert }_2^2}p(x)}{\int e^{⟨c_t,y⟩-\frac{t}{2}\Vert y{\Vert }_2^2}p(y)dy},$$

where

$$d{c}_t=d{W}_t+{\mu }_{t}dt,{\mu }_t={\mathbb{E}}_{p_t}X.$$

The density remains log-concave. More importantly, it contains the explicit Gaussian factor

$$e^{-t\Vert x{\Vert }_2^2/2}.$$

Conditioned on the random linear tilt $c_t$, the potential of $p_t$ has Hessian at least $t{I}_n$. Hence $p_t$ becomes increasingly strongly log-concave as $t$ grows.

The normalization and drift in $c_t$ are chosen so that

$$d{p}_t(x)=p_t(x)⟨x-{\mu }_t,d{W}_t⟩.$$

Therefore, for every integrable test function $f$,

$$M_t(f)=\int f(x)p_t(x)dx$$

is a martingale with stochastic differential

$$d{M}_t(f)=⟨\int f(x)(x-{\mu }_t)p_t(x)dx,d{W}_t⟩.$$

In particular,

$$\mathbb{E}\int f(x)p_t(x)dx=\int f(x)p(x)dx.$$

Stochastic localization is thus a random decomposition of $p$ into better-conditioned densities without changing their average.

Gaussian initial law

If $p$ is standard Gaussian, completing the square gives

$$p_t(x)\propto \exp \left(-\frac{1+t}{2}\Vert x{\Vert }^2+⟨c_t,x⟩\right).$$

Consequently,

$${\mu }_t=\frac{c_t}{1+t},A_t=\frac{1}{1+t}{I}_n.$$

The covariance contracts deterministically and the random tilt only moves the mean. For a general log-concave density, this contraction competes with a random third-moment term.

Proof: The Measure-Valued Martingale Identity

Write

$$F_t(x)=e^{⟨c_t,x⟩-t\Vert x{\Vert }^2/2}p(x),Z_t=\int F_t.$$

Ito’s formula and $d{c}_t=d{W}_t+{\mu }_{t}dt$ give

$$\frac{d{F}_t(x)}{F_t(x)}=⟨x,d{W}_t⟩+⟨x,{\mu }_t⟩dt.$$

The quadratic variation of $⟨c_t,x⟩$ cancels the explicit term $-t\Vert x{\Vert }^2/2$. Integrating in $x$ yields

$$\frac{d{Z}_t}{Z_t}=⟨{\mu }_t,d{W}_t⟩+\Vert {\mu }_t{\Vert }^{2}dt.$$

Applying Ito’s quotient rule to $p_t=F_t/Z_t$ cancels the remaining drift and leaves

$$d{p}_t(x)=p_t(x)⟨x-{\mu }_t,d{W}_t⟩.$$

Integrating this identity against $f$ proves the martingale formula.

🏷️ Mean and Covariance Dynamics

Set

$$A_t={\mathrm{Cov}}_{p_t}(X)=\int (x-{\mu }_t)(x-{\mu }_t{)}^{\mathsf{T}}{p}_t(x)dx.$$

Applying the martingale identity first to $x$ gives

$$d{\mu }_t=A_{t}d{W}_t.$$

Applying it to $x{x}^{\mathsf{T}}$ and subtracting the Ito differential of ${\mu }_t{\mu }_t^{\mathsf{T}}$ gives

$$d{A}_t=\left(\int (x-{\mu }_t)(x-{\mu }_t{)}^{\mathsf{T}}⟨x-{\mu }_t,d{W}_t⟩p_t(x)dx\right)-A_t^{2}dt.$$

The matrix martingale term contains third centered moments. The negative drift $-A_t^{2}dt$ is stabilizing, but the martingale can create a large eigenvalue. Quantitative stochastic localization is therefore a covariance problem: one must prevent $\Vert A_t{\Vert }_{\mathrm{op}}$ from growing before the Gaussian factor becomes useful.

This point separates the argument from the deterministic needle decomposition in on KLS localization lemma. Classical localization collapses a high-dimensional inequality to one-dimensional weighted segments. Stochastic localization instead preserves dimension and evolves the measure continuously, trading geometric dimension reduction for matrix-valued martingale control.

🏷️ Transfer of Isoperimetry Along the Martingale

Fix a measurable set $S$ with $p(S)\le 1/2$, and let

$$g_t=p_t(S).$$

Then

$$d{g}_t=⟨{\int }_S(x-{\mu }_t)p_t(x)dx,d{W}_t⟩,$$

so $g_t$ is a bounded martingale. If $A_t$ is controlled, its quadratic variation is controlled as well. Consequently, for a suitable time interval, a set that initially has nontrivial mass retains nontrivial mass with positive probability rather than immediately collapsing to mass zero or one.

Indeed, set

$$v_t(S)={\int }_S(x-{\mu }_t)p_t(x)dx.$$

Then

$$d[g{]}_t=\Vert v_t(S){\Vert }_2^{2}dt.$$

Covariance Cauchy-Schwarz gives, for every $u\in {\mathbb{R}}^n$,

$$⟨u,v_t(S){⟩}^2\le g_t(1-g_t)u^{\mathsf{T}}{A}_{t}u.$$

Taking the supremum over unit $u$ yields

$$d[g{]}_t\le \Vert A_t{\Vert }_{\mathrm{op}}{g}_t(1-g_t)dt.$$

This is the quantitative reason covariance control prevents the set mass from reaching $0$ or $1$ too quickly.

At time $t$, the density $p_t$ is $t$-strongly log-concave. Gaussian isoperimetry, transferred through the Brascamp-Lieb principle, gives the scale

$$h(p_t)\gtrsim \sqrt{t}.$$

Boundary measure also averages correctly under the localization process. Formally, and rigorously after approximation by neighborhoods,

$$p^{+}(S)\ge \mathbb{E}{p}_t^{+}(S).$$

For $\epsilon >0$, the martingale identity gives

$$\mathbb{E}\left[\frac{p_t(S_{\epsilon })-p_t(S)}{\epsilon }\right]=\frac{p(S_{\epsilon })-p(S)}{\epsilon }.$$

Fatou’s lemma yields the inequality as $\epsilon \downarrow 0$; equality is unnecessary. On the event that $g_t$ remains balanced,

$$p_t^{+}(S)\gtrsim \sqrt{t}\min \{g_t,1-g_t\}.$$

Taking expectations therefore transfers a fraction of the time-$t$ Gaussian expansion back to $p$.

The covariance estimates allow the argument to run to the scale

$$t\asymp n^{-1/2}.$$

Substitution into $h(p_t)\gtrsim \sqrt{t}$ gives

$$h(p)\gtrsim n^{-1/4},\psi (p)\lesssim n^{1/4}.$$

The fourth-root exponent is not accidental: it is the square root of the longest time for which the covariance martingale can be kept under control.

Covariance potential

The proof does not attempt to control every eigenvalue separately. It applies Ito calculus to a spectral potential built from $A_t$, such as a Schatten-moment quantity. The martingale part is estimated through log-concave moment inequalities, while the negative drift $-A_t^2$ absorbs the dangerous positive terms. This converts third-moment estimates into a time interval on which the covariance remains usable.

🏷️ Stieltjes Barrier and the Log-Sobolev Bound

The log-Sobolev theorem requires sharper control of the top covariance eigenvalue and of very small set masses. Lee and Vempala introduce a Stieltjes-type barrier. For an integer $q$ and fixed level $\Phi$, define $u_t>{\lambda }_{\max }(A_t)$ implicitly by

$$\mathrm{Tr}(u_{t}I-A_t{)}^{-q}=\Phi .$$

If an eigenvalue of $A_t$ approaches $u_t$, its contribution to the trace diverges. The potential is therefore highly sensitive to the spectral edge but averages the remaining directions. Ito’s formula for the implicit process $u_t$ gives a drift-martingale decomposition in which the barrier can be shown to move slowly.

Writing $R_t=(u_{t}I-A_t{)}^{-1}$, the constraint becomes

$$\mathrm{Tr}(R_t^q)=\Phi .$$

Since

$$(u_t-{\lambda }_{\max }(A_t){)}^{-q}\le \Phi \le n(u_t-{\lambda }_{\max }(A_t){)}^{-q},$$

one has

$${\Phi }^{-1/q}\le u_t-{\lambda }_{\max }(A_t)\le {\left(\frac{n}{\Phi }\right)}^{1/q}.$$

Taking $q\asymp \log n$ makes $n^{1/q}$ universal, so $u_t$ tracks the spectral edge at controlled resolution.

At first order, implicit differentiation in a matrix direction $H$ gives

$$du=\frac{\mathrm{Tr}(R^{q+1}H)}{\mathrm{Tr}(R^{q+1})}.$$

When $H=d{A}_t$, Ito’s formula adds resolvent-weighted quadratic-variation terms. The proof chooses the barrier parameters so that these corrections and the martingale fluctuations remain controlled.

The relevant isoperimetric quantity for entropy is the log-Cheeger constant

$$h_{\log }(p)=\underset{0<p(S)\le 1/2}{\inf }\frac{p^{+}(S)}{p(S)\sqrt{\log (1/p(S))}}.$$

For log-concave measures, the log-Sobolev and log-Cheeger scales satisfy

$$\rho (p)\asymp h_{\log }(p{)}^2$$

up to universal constants. A $t$-strongly log-concave density has

$$h_{\log }(p_t)\gtrsim \sqrt{t}.$$

The Stieltjes barrier keeps the localized covariance controlled until a time of order $D^{-1}$, with the stopping argument adapted to the initial mass of $S$. Transferring the localized log-isoperimetry back to the initial measure yields

$$h_{\log }(p)\gtrsim D^{-1/2}$$

and hence

$$\rho (p)\gtrsim D^{-1}.$$

The dependence on $D$ is essential. Isotropy fixes average directional variance but does not prevent a convex support from containing a long, thin direction. The barrier argument detects this geometric obstruction while improving the quadratic diameter loss from earlier estimates to a linear one.

Boundary and support edge cases

The liminf in $p^{+}(S)$ accommodates nonsmooth sets. The proof works with neighborhood enlargements before passing to the limit. When $D=\infty$, the diameter theorem supplies no log-Sobolev lower bound. Lower-dimensional measures must first be restricted to their affine hull.

🏷️ Concentration and Sampling Consequences

For an $L$-Lipschitz function $f$ and $X\sim p$, the paper obtains the two-level deviation estimate

$$\mathbb{P}\left(|f(X)-\mathrm{med}f(X)|\ge Lt\right)\le C\exp \left(-\frac{c{t}^2}{t+\sqrt{n}}\right).$$

The median may be replaced by the mean after changing universal constants. There are two regimes:

$$\frac{t^2}{t+\sqrt{n}}\asymp \{\begin{array}{ll}{t}^2/\sqrt{n},& 0<t\le \sqrt{n},\\ t,& t\ge \sqrt{n}.\end{array}$$

Thus moderate deviations have a Gaussian profile at variance scale $\sqrt{n}$, while large deviations have exponential decay. This functional concentration complements the information-content concentration for log-concave densities discussed in on concentration of information and log-concave distributions: the present result controls every Lipschitz observable, whereas that note studies the particular nonlinear observable $-\log p(X)$.

The same isoperimetric estimates control local random walks used to sample log-concave densities.

Ball-walk consequences

For an isotropic log-concave density in ${\mathbb{R}}^n$, the ball walk mixes from a warm start in

$$O^{\ast }(n^{5/2})$$

steps. Here $O^{\ast }$ suppresses logarithmic factors and dependence on the accuracy and warmness parameters.

If the support has diameter $D$, the speedy ball walk with step size

$$\delta =\Theta (n^{-1/2})$$

mixes from any starting point in

$$O^{\ast }(n^{2}D)$$

proper steps. A proper step counts a proposed move conditioned on remaining in the support, so this statement must be distinguished from an unconditional iteration bound for an implementation with rejections.

The bridge from geometry to algorithms is conductance. Isoperimetry lower-bounds the conductance of the walk, and a conductance inequality converts this into decay of the distance to stationarity. The warm-start result uses the improved KLS scale; the arbitrary-start result uses the stronger small-set control supplied by log-Sobolev and log-isoperimetric estimates.

For the speedy walk, a proper step samples from the intersection of the local ball with the support. Translating proper steps into ordinary ball-walk iterations additionally requires control of the local acceptance probability.

🏷️ Structure of the Method

The argument can be summarized as a reusable analytic scheme:

1. Normalize the log-concave measure to isotropic position.
2. Tilt it by Brownian motion while adding a deterministic Gaussian penalty.
3. Use the measure-valued martingale identity to preserve averages.
4. Track the covariance through a spectral potential or Stieltjes barrier.
5. Wait until the localized densities have useful Gaussian isoperimetry.
6. Prove that set masses have not degenerated before that time.
7. Average the improved boundary inequality back to the original measure.
8. Convert isoperimetry into Poincare, log-Sobolev, concentration, or mixing estimates.

The central insight is that localization need not immediately reduce dimension. It is enough to produce a random family of strongly log-concave measures while retaining sufficient control of their covariance and set masses. This perspective also connects to the curvature-driven functional inequalities in on curvature-dimension geometry of metric measure spaces, because the Gaussian factor creates a positive Hessian lower bound to which Bakry-Emery and Brascamp-Lieb mechanisms apply.

🔗 See Also

• on KLS localization lemma --- compares stochastic localization with the classical deterministic reduction to one-dimensional needles used in convex-geometric inequalities.
• on an almost constant lower bound in the KLS conjecture --- explains Chen’s recursive covariance bootstrap, which improves the $n^{-1/4}$ expansion estimate to a subpolynomial loss.
• on concentration of information and log-concave distributions --- studies a different concentration phenomenon for the information content $-\log p(X)$ and explains how log-concavity substitutes for independence.
• on curvature-dimension geometry of metric measure spaces --- provides the geometric framework relating curvature lower bounds, Poincare inequalities, log-Sobolev inequalities, and concentration.

📚 References

🐻  Lee, Y.T. & Vempala, S.S. 2024. Eldan’s Stochastic Localization and the KLS Conjecture: Isoperimetry, Concentration and Mixing. Annals of Mathematics 199(3), 1043–1092.