on an almost constant lower bound in the KLS conjecture

Overview

Chen proves the first subpolynomial-dimensional lower bound for the KLS isoperimetric coefficient (Chen, 2021). For a log-concave density in dimension $d$, the earlier stochastic-localization estimate was $h(p)\gtrsim d^{-1/4}$ in isotropic position. Chen replaces this fixed power by

$$h(p)\ge d^{-C\sqrt{\log \log d/\log d}}=d^{-o_d(1)}.$$

The result is not a dimension-free proof of KLS: the lower bound still tends to zero. Its significance is that it decays more slowly than $d^{-\epsilon }$ for every fixed $\epsilon >0$.

The proof refines Eldan’s stochastic localization in an affine-normalized form. Its main innovation is a bootstrap: any power-law isoperimetric estimate in dimensions at most $d$ improves the covariance control along the localization process, and that improved covariance control feeds back into a better isoperimetric exponent. Iterating the feedback loop yields the almost-constant bound.

🏷️ Isoperimetric Preliminaries

Let $p$ be a probability density on ${\mathbb{R}}^d$. For a measurable set $S$, define

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

The isoperimetric coefficient is

$$h(p)=\underset{0<p(S)<1}{\inf }\frac{p^{+}(S)}{\min \{p(S),p(S^c)\}}.$$

Chen denotes this lower-expansion quantity by $\psi (p)$. This post uses $h(p)$ to remain consistent with on Eldan’s stochastic localization and the KLS conjecture, where $\psi (p)=1/h(p)$ denotes the inverse expansion scale.

A density is log-concave if

$$p(\lambda x+(1-\lambda )y)\ge p(x{)}^{\lambda }p(y{)}^{1-\lambda }$$

for all $x,y\in {\mathbb{R}}^d$ and $\lambda \in [0,1]$. Write

$$A={\mathrm{Cov}}_p(X),r(p)=\Vert A{\Vert }_{\mathrm{op}}.$$

The affine form of the KLS conjecture asserts

$$h(p)\gtrsim \frac{1}{\sqrt{r(p)}}.$$

For an isotropic density, $A=I_d$ and $r(p)=1$, so KLS asks for a universal positive lower bound.

Affine Normalization and Hyperplanes

If $A$ is positive definite, the whitening map

$$T(x)=A^{-1/2}(x-\mathbb{E}X)$$

sends $p$ to an isotropic log-concave density. The factor $\sqrt{r(p)}$ in the affine statement records the largest directional standard deviation before whitening.

For a unit vector $u$ and threshold $a$, let

$$H_{u,a}=\{x:⟨u,x⟩\le a\}.$$

The boundary expansion of $H_{u,a}$ is governed by the one-dimensional log-concave marginal $⟨u,X⟩$, whose expansion scale is its standard deviation. Thus an appropriate half-space has expansion of order $r(p{)}^{-1/2}$. KLS asserts that no arbitrary measurable set has substantially smaller expansion than the best half-space, up to a universal factor. This is the hyperplane formulation.

For log-concave measures, Cheeger expansion and the Poincare constant satisfy

$$C_{\mathrm{P}}(p)\asymp h(p{)}^{-2}.$$

Chen’s theorem can therefore be read either as an isoperimetric lower bound or as a subpolynomial spectral-gap estimate.

Reduction to balanced sets

The isoperimetric profile

$$I_p(s)=\inf \{p^{+}(S):p(S)=s\}$$

is concave for log-concave measures and symmetric under $s\leftrightarrow 1-s$. Consequently, it suffices to control sets with $p(S)=1/2$. This is important because stochastic localization only has to keep one balanced set away from masses $0$ and $1$.

Gaussian Domination

A density $q$ is more log-concave than a Gaussian with precision $B\succ 0$ if

$$q(x)\propto e^{-V(x)-\frac{1}{2}{x}^{\mathsf{T}}Bx}$$

for a convex $V$. Brascamp-Lieb and Gaussian comparison give

$${\mathrm{Cov}}_q(X)⪯B^{-1},h(q)\ge \frac{1}{2}\Vert B^{-1}{\Vert }_{\mathrm{op}}^{-1/2}.$$

Stochastic localization increases $B_t$ deterministically while controlling the random covariance $A_t$.

Martingale Time Change

For a continuous scalar martingale $M_t$ with $M_0=0$, the Dambis-Dubins-Schwarz theorem gives a Brownian motion $\tilde{W}$ such that

$$M_t={\tilde{W}}_{[M{]}_t}.$$

The reflection principle then yields

$$\mathbb{P}\left(\underset{0\le s\le T}{\sup }|{\tilde{W}}_s|\ge a\right)\le 4\mathbb{P}({\tilde{W}}_T\ge a).$$

This converts control of a martingale’s quadratic variation into control of the probability that it exits an interval.

The original KLS localization argument gives

$$h(p)\gtrsim \frac{1}{\sqrt{\mathrm{Tr}A}}\ge \frac{1}{\sqrt{d}\sqrt{r(p)}}.$$

Lee and Vempala improved this to

$$h(p)\gtrsim \frac{1}{(\mathrm{Tr}{A}^2{)}^{1/4}}\ge \frac{1}{d^{1/4}\sqrt{r(p)}}.$$

Chen’s theorem starts from this stochastic-localization framework but uses its current isoperimetric estimate recursively.

🏷️ Main Theorem

Almost-constant KLS bound

There is a universal constant $c$ such that, for every log-concave density $p$ on ${\mathbb{R}}^d$ and every integer $\ell \ge 1$,

$$h(p)\ge \frac{1}{[c\ell (\log d+1){]}^{\ell /2}{d}^{16/\ell }\sqrt{r(p)}}.$$

In particular, for sufficiently large $d$, choosing

$$\ell =\lceil \sqrt{\frac{\log d}{\log \log d}}\rceil$$

gives

$$h(p)\ge \frac{1}{d^{C\sqrt{\log \log d/\log d}}\sqrt{r(p)}}.$$

For isotropic $p$, the factor $\sqrt{r(p)}$ disappears. The exponent

$${\epsilon }_d=C\sqrt{\frac{\log \log d}{\log d}}$$

tends to zero, which is the meaning of $d^{-o_d(1)}$.

Optimization of the Iteration Depth

Ignoring universal constants, the logarithm of the theorem’s denominator is

$$\frac{\ell }{2}\log (\ell \log d)+\frac{16\log d}{\ell }.$$

For the relevant range of $\ell$,

$$\log (\ell \log d)\asymp \log \log d.$$

Balancing the two contributions gives

$$\ell \log \log d\asymp \frac{\log d}{\ell },$$

and hence

$$\ell \asymp \sqrt{\frac{\log d}{\log \log d}}.$$

At this choice the total loss is

$$\exp \left(C\sqrt{\log d\log \log d}\right)=d^{C\sqrt{\log \log d/\log d}}.$$

This calculation also explains why taking $\ell$ arbitrarily large is counterproductive: the explicit $d^{16/\ell }$ term improves, but the accumulated factor $[c\ell \log d{]}^{\ell /2}$ worsens.

🏷️ Preconditioned Stochastic Localization

Assume first that $p$ has compact support and nonsingular covariance $A$. Chen fixes the preconditioner

$$C=A^{-1}$$

and defines

$$d{c}_t=C^{1/2}d{W}_t+C{\mu }_{t}dt,d{B}_t=Cdt,c_0=0,B_0=0.$$

Thus $B_t=t{A}^{-1}$. The localized density is

$$p_t(x)=\frac{e^{⟨c_t,x⟩-\frac{1}{2}{x}^{\mathsf{T}}{B}_{t}x}p(x)}{\int e^{⟨c_t,y⟩-\frac{1}{2}{y}^{\mathsf{T}}{B}_{t}y}p(y)dy},$$

with mean and covariance

$${\mu }_t={\mathbb{E}}_{p_t}X,A_t={\mathrm{Cov}}_{p_t}(X).$$

Ito’s formula gives the measure-valued martingale identity

$$d{p}_t(x)=p_t(x)⟨C^{1/2}(x-{\mu }_t),d{W}_t⟩.$$

Proof: Cancellation of the Density Drift

Define

$$G_t(x)=e^{⟨c_t,x⟩-\frac{1}{2}{x}^{\mathsf{T}}{B}_{t}x}p(x),Z_t=\int G_t(x)dx.$$

The bracket of $⟨c_t,x⟩$ is

$$d[⟨c,x⟩{]}_t=x^{\mathsf{T}}Cxdt.$$

In Ito’s formula for $G_t$, this correction cancels the derivative of $-x^{\mathsf{T}}{B}_{t}x/2$ because $d{B}_t=Cdt$. One obtains

$$\frac{d{G}_t(x)}{G_t(x)}=⟨C^{1/2}x,d{W}_t⟩+⟨Cx,{\mu }_t⟩dt.$$

After integration,

$$\frac{d{Z}_t}{Z_t}=⟨C^{1/2}{\mu }_t,d{W}_t⟩+{\mu }_t^{\mathsf{T}}C{\mu }_{t}dt.$$

Applying Ito’s product rule to $p_t=Z_t^{-1}{G}_t$ introduces a cross-variation term that cancels the remaining drift. Hence

$$d{p}_t(x)=p_t(x)⟨C^{1/2}(x-{\mu }_t),d{W}_t⟩.$$

The fixed preconditioner makes the argument affine normalized from the outset. Define the dimensionless covariance process

$$Q_t=A^{-1/2}{A}_t{A}^{-1/2}.$$

Since $Q_0=I_d$, controlling $\Vert Q_t{\Vert }_{\mathrm{op}}$ measures precisely how much the current covariance has grown relative to the initial covariance.

The mean and normalized covariance satisfy

$$d{\mu }_t=A_t{A}^{-1/2}d{W}_t$$

and

$$d{Q}_t=\left(\int z_t(x)z_t(x{)}^{\mathsf{T}}⟨z_t(x),d{W}_t⟩p_t(x)dx\right)-Q_t^{2}dt,$$

where $z_t(x)=A^{-1/2}(x-{\mu }_t)$. The martingale part is a normalized third centered moment. The negative drift comes from the bracket

$$d[\mu ,{\mu }^{\mathsf{T}}{]}_t=A_t{A}^{-1}{A}_{t}dt.$$

Proof: Covariance Differential

Use

$$A_t=\int x{x}^{\mathsf{T}}{p}_t(x)dx-{\mu }_t{\mu }_t^{\mathsf{T}}.$$

The first term inherits the martingale differential from $d{p}_t$. Ito’s product rule gives

$$d({\mu }_t{\mu }_t^{\mathsf{T}})=d{\mu }_t{\mu }_t^{\mathsf{T}}+{\mu }_{t}d{\mu }_t^{\mathsf{T}}+A_t{A}^{-1}{A}_{t}dt.$$

Re-centering the martingale integrand therefore yields

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

Conjugation by $A^{-1/2}$ gives the SDE for $Q_t$.

At time $t$, the density $p_t$ is more log-concave than the Gaussian with precision

$$B_t=t{A}^{-1}.$$

The comparison Gaussian has covariance $A/t$, so its largest variance is $r(p)/t$. Gaussian isoperimetry therefore gives

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

The remaining problem is to run the process long enough for this lower bound to become useful without allowing the mass of the test set to degenerate.

🏷️ Evolution of a Balanced Set

Fix $E$ with $p(E)=1/2$ and put

$$g_t=p_t(E).$$

Integrating the density SDE over $E$ gives

$$d{g}_t=⟨{\int }_E{A}^{-1/2}(x-{\mu }_t)p_t(x)dx,d{W}_t⟩.$$

Consequently,

$$d[g{]}_t={\Vert {\int }_E{A}^{-1/2}(x-{\mu }_t)p_t(x)dx\Vert }_2^{2}dt.$$

Cauchy-Schwarz implies

$$d[g{]}_t\le \Vert Q_t{\Vert }_{\mathrm{op}}dt,$$

and hence

$$[g{]}_t\le {\int }_0^t\Vert Q_s{\Vert }_{\mathrm{op}}ds.$$

Balanced-mass control

For every $t>0$,

$$\mathbb{P}\left(\frac{1}{4}\le g_t\le \frac{3}{4}\right)\ge \frac{9}{10}-\mathbb{P}\left({\int }_0^t\Vert Q_s{\Vert }_{\mathrm{op}}ds\ge \frac{1}{64}\right).$$

Proof: Brownian Time Change

On the event

$${\int }_0^t\Vert Q_s{\Vert }_{\mathrm{op}}ds\le \frac{1}{64},$$

the bracket estimate gives $[g{]}_t\le 1/64$. Since $g_0=1/2$, Dambis-Dubins-Schwarz implies

$$g_t-\frac{1}{2}={\tilde{W}}_{[g{]}_t}.$$

Leaving $[1/4,3/4]$ therefore requires

$$\underset{0\le s\le 1/64}{\sup }|{\tilde{W}}_s|>\frac{1}{4}.$$

Brownian scaling gives the standardized threshold

$$\frac{1/4}{\sqrt{1/64}}=2.$$

The reflection principle bounds the exit probability by

$$4\mathbb{P}(N(0,1)>2)<\frac{1}{10}.$$

Adding the probability that the bracket-control event fails proves the result.

The Dambis-Dubins-Schwarz theorem represents $g_t-g_0$ as a Brownian motion evaluated at time $[g{]}_t$. If the covariance integral is at most $1/64$, the martingale has accumulated too little Brownian time to leave $[1/4,3/4]$ except with a fixed small probability.

On the balanced event, Gaussian isoperimetry for $p_t$ gives

$$p_t^{+}(E)\gtrsim \sqrt{\frac{t}{r(p)}}\min \{p_t(E),p_t(E^c)\}\gtrsim \sqrt{\frac{t}{r(p)}}.$$

Averaging the boundary inequality back to time zero yields

$$p^{+}(E)\gtrsim \sqrt{\frac{t}{r(p)}}\mathbb{P}\left(\frac{1}{4}\le g_t\le \frac{3}{4}\right).$$

Thus an integrated bound on $\Vert Q_s{\Vert }_{\mathrm{op}}$ immediately becomes a lower bound on $h(p)$.

🏷️ Schatten Potential and Two Time Regimes

Directly controlling the largest eigenvalue of $Q_t$ is difficult. For an integer $q\ge 2$, Chen uses the differentiable potential

$${\Gamma }_t=\mathrm{Tr}(Q_t^q).$$

Since $Q_t$ is positive semidefinite,

$$\Vert Q_t{\Vert }_{\mathrm{op}}\le {\Gamma }_t^{1/q}.$$

Write its Ito differential as

$$d{\Gamma }_t=v_t^{\mathsf{T}}d{W}_t+{\delta }_{t}dt.$$

For $\Gamma (X)=\mathrm{Tr}(X^q)$,

$$D\Gamma (X)[H]=q\mathrm{Tr}(X^{q-1}H)$$

and

$$D^2\Gamma (X)[H_1,H_2]=q\sum _{a=0}^{q-2}\mathrm{Tr}\left(X^a{H}_2{X}^{q-2-a}{H}_1\right).$$

Matrix Ito calculus therefore decomposes $d{\Gamma }_t$ into

$$\underset{\text{martingale}}{\underbrace{q\mathrm{Tr}(Q_t^{q-1}d{Q}_t^{\mathrm{mart}})}}-\underset{\text{stabilizing drift}}{\underbrace{q\mathrm{Tr}(Q_t^{q+1})dt}}+\underset{\text{positive Ito correction}}{\underbrace{\frac{q}{2}\sum _{a=0}^{q-2}\mathrm{Tr}\left(Q_t^{a}d{Q}_t^{\mathrm{mart}}{Q}_t^{q-2-a}d{Q}_t^{\mathrm{mart}}\right)}}.$$

The central tensor estimate controls the positive correction without discarding the stabilizing drift.

Suppose inductively that, in every dimension $k\le d$,

$$h_k\ge \frac{1}{\alpha k^{\beta }},0<\beta \le \frac{1}{2},\alpha \ge 1,$$

where

$$h_k=\underset{p}{\inf }h(p)\sqrt{r(p)}$$

over compactly supported log-concave densities in ${\mathbb{R}}^k$. Set

$$q=\lceil \frac{1}{\beta }\rceil +1.$$

The tensor estimates in the paper give

$$\Vert v_t{\Vert }_2\le 16q{\Gamma }_t^{1+1/(2q)}$$

and the crucial two-sided choice of drift bounds

$${\delta }_t\le \min \left\{64q^2{\alpha }^2\log d{d}^{2\beta -1/q}{\Gamma }_t^{1+1/q},\frac{2q^2}{t}{\Gamma }_t\right\}.$$

The first estimate contains the inductive isoperimetric hypothesis. It is strongest near the start of the process. The second estimate is independent of $\alpha$ and has a singular but decaying coefficient $1/t$; it becomes effective after a positive initial time. Using the minimum rather than one estimate globally is the mechanism that extends the useful localization horizon.

The factor $d^{2\beta -1/q}$ is the quantitative gain from the inductive hypothesis. Choosing $q>1/\beta$ ensures

$$2\beta -\frac{1}{q}<2\beta .$$

The proof obtains this saving from tensor inequalities that bound the third-moment contractions using the assumed lower-dimensional isoperimetric constants. The choice of $q$ converts those inequalities into the displayed power saving; the accompanying estimates contribute the factor $\log d$.

Initial-Time Control

For

$$H(a)=-(a+1{)}^{-1/q},$$

Ito’s formula, the first drift bound, and martingale concentration control the maximum of ${\Gamma }_t$ up to

$$T_1\asymp \frac{1}{q{\alpha }^2\log d{d}^{2\beta }}.$$

With high probability,

$$\underset{0\le t\le T_1}{\sup }{\Gamma }_t\lesssim 3^{q}d.$$

The negative-power transform is useful because large potential values are compressed into a bounded interval while its derivatives counteract the superlinear powers of ${\Gamma }_t$ in the SDE.

Later-Time Control

For

$$F(a)=a^{1/q},$$

the second drift estimate yields

$$\mathbb{E}{\Gamma }_{t_2}^{1/q}\le \mathbb{E}{\Gamma }_{t_1}^{1/q}{\left(\frac{t_2}{t_1}\right)}^{2q},t_2>t_1>0.$$

This permits growth after $T_1$, but only at a controlled polynomial rate. Combining the two regimes extends the time to

$$T_2\asymp \frac{1}{q{\alpha }^2\log d{d}^{2\beta -\beta /(4q)}}$$

while retaining

$$\mathbb{P}\left({\int }_0^{T_2}\Vert Q_t{\Vert }_{\mathrm{op}}dt\ge \frac{1}{64}\right)<\frac{4}{10}.$$

The balanced-set lemma then gives a fixed positive probability that $p_{T_2}(E)$ remains between $1/4$ and $3/4$.

🏷️ The Isoperimetric Bootstrap

Substituting $T_2$ into the Gaussian boundary scale gives

$$h(p)\gtrsim \sqrt{\frac{T_2}{r(p)}}\gtrsim \frac{1}{\sqrt{q}\alpha \sqrt{\log d}{d}^{\beta -\beta /(8q)}\sqrt{r(p)}}.$$

Taking the infimum over $p$ proves the inductive improvement

$$h_d\gtrsim \frac{1}{\sqrt{q}\alpha \sqrt{\log d}{d}^{\beta -\beta /(8q)}}.$$

Feedback loop

The proof closes the following cycle:

$$\text{isoperimetry in dimensions }\le d⟹\text{third-moment bounds}⟹\text{covariance control}⟹\text{longer localization time}⟹\text{better isoperimetry in dimension }d.$$

The original KLS estimate supplies the starting exponent $\beta =1/2$. At each round, choosing $q\simeq 1/\beta$ changes the exponent to

$${\beta }^{\prime }=\beta -\frac{\beta }{8q}<\beta .$$

The exponent improves only slightly, and each round introduces factors involving $q$, $\alpha$, and $\sqrt{\log d}$. Careful bookkeeping over the iteration packages the accumulated losses into

$$[c\ell (\log d+1){]}^{\ell /2}{d}^{16/\ell },$$

which is the parameterized form of the main theorem.

First Bootstrap Round

The initial KLS estimate has exponent

$${\beta }_0=\frac{1}{2}.$$

The prescription gives

$$q_0=\lceil \frac{1}{{\beta }_0}\rceil +1=3.$$

After one application of the inductive lemma,

$${\beta }_1=\frac{1}{2}-\frac{1/2}{8\cdot 3}=\frac{23}{48}.$$

Thus the first round replaces $d^{-1/2}$ by $d^{-23/48}$, apart from the new factor involving $\sqrt{q_0\log d}$. This intermediate estimate is still weaker than Lee and Vempala’s separate $d^{-1/4}$ bound; the example illustrates the internal induction rather than the best bound after one round. Repeated rounds eventually cross the $1/4$ threshold and then produce the subpolynomial exponent. Each round treats its new exponent as input to the next covariance estimate, while the prefactors accumulate.

🏷️ Removal of Compact Support

Compact support ensures standard existence and uniqueness for the localization SDE and uniform control of its coefficients. The final theorem applies to arbitrary log-concave densities by truncation. Intersect the support with expanding Euclidean balls and renormalize:

$$p_R(x)=\frac{p(x)1_{\{\Vert x\Vert \le R\}}}{p(\Vert X\Vert \le R)}.$$

The densities $p_R$ remain log-concave, their covariance matrices converge to that of $p$, and the relevant boundary estimates pass to the limit through neighborhood approximations. Degenerate covariance is handled by restricting to the affine hull.

🏷️ Consequences and Scope

For isotropic log-concave densities, the theorem gives

$$h(p)\ge d^{-o_d(1)},C_{\mathrm{P}}(p)\le d^{o_d(1)}.$$

Through the known comparison principles among KLS, thin-shell, and slicing constants, this replaces fixed polynomial losses by subpolynomial ones. It likewise yields subpolynomial concentration scales for Lipschitz observables and improved conductance-based bounds for log-concave sampling algorithms.

Meaning of almost constant

The expression $d^{-o_d(1)}$ does not mean $1-o_d(1)$ and does not imply a universal positive lower bound. It means that the logarithmic loss is $o(\log d)$. The result beats every fixed negative power of $d$ asymptotically, but it does not prove the dimension-free KLS conjecture.

Technical scope

Compact support is used to construct the SDE with globally controlled coefficients; truncation removes it from the final theorem. Positive-definite covariance is also temporary, since singular measures are treated on their affine hull. The choice involving $\log \log d$ is intended for sufficiently large $d$, while the theorem parameterized by $\ell$ remains valid in every dimension.

The conceptual advance is broader than the numerical exponent. Earlier localization arguments inserted a Gaussian component and controlled covariance using a fixed collection of moment bounds. Chen makes the current isoperimetric knowledge itself an input to covariance control, creating a self-improving inequality. The two-regime potential estimate prevents this recursion from losing the gain before the Gaussian factor becomes strong enough.

🔗 See Also

• on Eldan’s stochastic localization and the KLS conjecture --- develops the measure-valued martingale, covariance dynamics, and $d^{-1/4}$ expansion bound that Chen bootstraps.
• on KLS localization lemma --- presents the deterministic needle decomposition underlying classical log-concave isoperimetry and Gaussian comparison arguments.
• on concentration of information and log-concave distributions --- treats concentration for the nonlinear observable $-\log p(X)$, complementary to the Lipschitz concentration consequences of KLS.
• on curvature-dimension geometry of metric measure spaces --- explains the functional-inequality links among curvature, Cheeger expansion, Poincare inequalities, and concentration.

📚 References

🐻  Chen, Y. 2021. An Almost Constant Lower Bound of the Isoperimetric Coefficient in the KLS Conjecture. Geometric and Functional Analysis 31(1), 34–61.