The near-worst bootstrap - The KLS theorem and its methods

Part of the fixed-cut archive, Chapter The fixed cut: the bootstrap; the reading order is on the full proofs page.

Overview. This dossier proves Lemma 33.1, Lemma 33.2, Theorem 33.1, Lemma 33.3, Corollary 33.1 and Proposition 33.1. It uses two deterministic isoperimetric comparisons to bound the Cheeger-line excess of a near-worst measure along stochastic localization. The covariance overshoot $\Xi_T$ is the only interface quantity. It is then evaluated crudely, and polylogarithmically under Assumption 26.1. Finally, the dossier shows that an all-measure relative-scale bound on $\Xi_T$ would already imply KLS.

Lemma D3.1: concavity and symmetry of the profile give $h_\nu=2I_\nu(1/2)$ .
Lemma D3.2: whitening gives (D3.9), and $\hstar_n$ is nonincreasing in $n$ .
Theorem D3.1: the perimeter supermartingale, Steps 1–2 and a two-case argument prove (D3.12). The second case is needed because the lower bound can be negative. The $L^2$ maximal inequality with (D3.4) gives the exit bound (D3.13). Integration gives (D3.14) and (D3.15).
Lemma D3.3: the trace SDE and the Brascamp–Lieb cap give $\Xi_T\le1+\log(nT)$ . This is recorded only as an insufficient fence.
Corollary D3.1: under Assumption 26.1, which is discharged by Corollary 26.2, $\Xi_T\lesssim1+\log\log n$ (D3.29). Step 3 then gives (D3.30).
Proposition D3.1: if (D3.32) held for all measures, balanced mass would survive, and Lemma 30.1 would give KLS. Only this sufficient implication is claimed.

Setup. For a log-concave probability measure $\nu$ , let

I_\nu(p)=\inf\{\nu^+(E):\nu(E)=p\},\qquad h_\nu=\inf_E\frac{\nu^+(E)}{\min(\nu(E),1-\nu(E))},

(D3.1)

and let $\hstar_n$ be the infimum of $h_\nu$ over isotropic log-concave laws on $\mathbb R^n$ . Along stochastic localization write

p_t=\mu_t(E),\quad q_t=1-p_t,\quad s_t=p_tq_t, \quad A_t=\operatorname{Cov}(\mu_t),

(D3.2)

\bar e_t(E)=\mu_t^+(E)-h_{\mu_t}\min(p_t,q_t),qquad X_t=(\lambda_{\max}(A_t)-1)_+,qquad \Xi_T=\int_0^T\mathbb E X_t\,\dd t.

(D3.3)

For $0<\eta<1/2$ set $\tau_\eta=\inf\{t:|p_t-1/2|>\eta\}$ . The mass martingale satisfies

\dd[p]_t=s_t r_t\,\dd t, \qquad s_t r_t\leq\frac14\lambda_{\max}(A_t) \leq\frac14(1+X_t).

(D3.4)

All stopping and expectation arguments below are first made in the compact smooth class and then passed through the manuscript’s uniform approximation convention. Since $0\leq p_t\leq1$ , the stopped mass martingales are uniformly integrable; no unbounded optional-stopping theorem is being invoked.

1. Two deterministic isoperimetric comparisons¶

Proof D3.1

Work in the affine hull of $\nu$ . In positive affine dimension the log-concave law is absolutely continuous there. Its profile is nonnegative and concave on $(0,1)$ and is symmetric under $p\leftrightarrow1-p$ ; see Corollaries 6.5 and 6.12, with Theorem 1.8 and the Section 6 extension, in Milman, 2009. These conclusions include nonsmooth convex supports and dimension one. For $0<\varepsilon<p<q\le1/2$ , interior concavity and nonnegativity give

I_\nu(p)\ge\frac{p-\varepsilon}{q-\varepsilon}I_\nu(q) +\frac{q-p}{q-\varepsilon}I_\nu(\varepsilon) \ge\frac{p-\varepsilon}{q-\varepsilon}I_\nu(q).

(D3.7)

Letting $\varepsilon\downarrow0$ gives $I_\nu(p)\ge(p/q)I_\nu(q)$ , so $p\mapsto I_\nu(p)/p$ is nonincreasing on $(0,1/2]$ . Assigning $I_\nu(0)=0$ using the empty set does not assert $I_\nu(0+)=0$ : that one-sided limit can be positive. No endpoint continuity or profile minimizer is used. Therefore

\inf_{0<p\leq1/2}\frac{I_\nu(p)}p=2I_\nu(1/2).

(D3.8)

Symmetry gives the same infimum on $[1/2,1)$ after division by $1-p$ , proving the first identity. The second is immediate because $\min(1/2,1/2)=1/2$ . For a Dirac law there are no nontrivial-mass competitors: with the empty-infimum convention both $h_\nu$ and $I_\nu(1/2)$ are $+\infty$ , and the assertion about balanced sets is vacuous.

Proof D3.2

Let $a_\nu$ be the centroid, $T=A_\nu^{1/2}$ , and $\widetilde\nu=(A_\nu^{-1/2})_\#(\nu-a_\nu)$ . Then $\widetilde\nu$ is isotropic and log-concave, so $h_{\widetilde\nu}\geq\hstar_n$ , and $\nu=T_\#\widetilde\nu+a_\nu$ . Put $L=\|T\|_{\mathrm{op}}$ . For every Borel set $S$ and every $\delta>0$ ,

T^{-1}(S_\delta-a_\nu) \supseteq\bigl(T^{-1}(S-a_\nu)\bigr)_{\delta/L}.

(D3.10)

After subtracting the common mass, dividing by $\delta$ , and taking the lower limit,

\nu^+(S)\geq L^{-1}\widetilde\nu^+(T^{-1}(S-a_\nu)) \geq\frac{\hstar_n}{L}\min(\nu(S),1-\nu(S)).

(D3.11)

Taking the infimum in $S$ and using $L=\lambda_{\max}(A_\nu)^{1/2}$ proves (D3.9). An isotropic starting law is full-dimensional, and the localization density is positive on the same support, so $A_t$ remains nondegenerate at finite $t$ .

For monotonicity, if $m\leq n$ and $\rho$ is isotropic log-concave on $\mathbb R^m$ , then $\rho\otimes\gamma_{n-m}$ is isotropic log-concave on $\mathbb R^n$ . Cylinder competitors give $h_{\rho\otimes\gamma_{n-m}}\leq h_\rho$ . Taking first the infimum over all $\rho$ and then using the definition in dimension $n$ yields $\hstar_n\leq\hstar_m$ .

2. The bootstrap comparison¶

Theorem D3.1 (Bootstrap comparison; Theorem 33.1)

Let $n\geq2$ , $\varepsilon\in(0,1]$ , and let $\mu$ be isotropic log-concave on $\mathbb R^n$ with $h_\mu\leq(1+\varepsilon)\hstar_n$ . Let $E$ be any measurable set with $\mu(E)=1/2$ and $e_0=e_0(E)=\bar e_0(E)$ , and fix $\eta\in(0,1/2)$ . For every $t>0$ ,

\mathbb E[\bar e_t(E)\mathbf 1_{\{t<\tau_\eta\}}] \leq e_0+h_\mu\left( \frac\varepsilon2+\eta+\frac12\mathbb P(\tau_\eta\leq t) +\frac14\mathbb E X_t\right),

(D3.12)

\mathbb P(\tau_\eta\leq t) \leq\frac1{4\eta^2}\left(t+\int_0^t\mathbb E X_s\,\dd s\right).

(D3.13)

Consequently,

\begin{split} \int_0^T\mathbb E[\bar e_t(E)\mathbf 1_{\{t<\tau_\eta\}}]\,\dd t \leq{}&Te_0+h_\mu\left[ \left(\frac\varepsilon2+\eta\right)T+ \frac{T^2}{16\eta^2}+ \frac{T\Xi_T}{8\eta^2}+\frac{\Xi_T}{4}\right]. \end{split}

(D3.14)

If $0<T<1/8$ , $\eta=T^{1/3}$ , and $\varepsilon\leq T^{1/3}$ , then for a universal $C$ ,

\int_0^T\mathbb E[\bar e_t(E)\mathbf 1_{\{t<\tau_\eta\}}]\,\dd t \leq Te_0+C h_\mu(T^{4/3}+\Xi_T).

(D3.15)

Proof D3.3

Write $A=\{t<\tau_\eta\}$ and $P=\mathbb P(A^c)$ . The perimeter supermartingale gives

\mathbb E[\mu_t^+(E)\mathbf 1_A] \leq\mathbb E\mu_t^+(E) \leq\mu^+(E)=\frac{h_\mu}{2}+e_0,

(D3.16)

where the last equality is Lemma D3.1. This uses a deterministic time $t$ ; there is no optional-stopping step for the perimeter process.

On $A$ , $\min(p_t,q_t)\geq1/2-\eta$ . Lemma D3.2 and the elementary inequality

\lambda^{-1/2}\geq1-\frac12(\lambda-1)_+, \qquad \lambda>0,

(D3.17)

give

\begin{split} \mathbb E[h_{\mu_t}\min(p_t,q_t)\mathbf 1_A] &\geq\hstar_n(1/2-\eta) \mathbb E[\lambda_{\max}(A_t)^{-1/2}\mathbf 1_A]\\ &\geq\hstar_n(1/2-\eta)(1-P-\tfrac12\mathbb E X_t). \end{split}

(D3.18)

The last lower bound may be negative. The manuscript’s abbreviated proof silently multiplied it by a lower bound for $\hstar_n/h_\mu$ , which is only legitimate when its bracket is nonnegative. We now record the required two-case argument.

Set $Y=\mathbb E X_t$ , $a=1/2-\eta$ , and $\rho=\hstar_n/h_\mu$ . Near-worstness and the definition of $\hstar_n$ give

\frac1{1+\varepsilon}\leq\rho\leq1, \qquad\text{hence}\qquad \rho\geq1-\varepsilon.

(D3.19)

If $1-P-Y/2\geq0$ , combine (D3.16)–(D3.19) to obtain

\begin{split} \mathbb E[\bar e_t\mathbf 1_A]-e_0 &\leq h_\mu\{1/2-(1-\varepsilon)a(1-P-Y/2)\}\\ &\leq h_\mu(\eta+P/2+Y/4+\varepsilon/2). \end{split}

(D3.20)

Indeed, $1/2-a(1-P)=\eta+aP\leq\eta+P/2$ , the $Y$ contribution is at most $Y/4$ , and the $\varepsilon$ contribution is at most $\varepsilon/2$ .

If $1-P-Y/2<0$ , use only the nonnegativity of $h_{\mu_t}\min(p_t,q_t)\mathbf 1_A$ in (D3.16). The case assumption gives $P/2+Y/4>1/2$ , and therefore

\mathbb E[\bar e_t\mathbf 1_A]-e_0 \leq h_\mu/2 <h_\mu(\eta+P/2+Y/4+\varepsilon/2).

(D3.21)

Thus (D3.12) holds in both cases.

For the exit estimate, stop the bounded continuous martingale $M_u=p_{u\wedge\tau_\eta}-1/2$ . On $\{\tau_\eta\leq t\}$ , continuity gives $\sup_{u\leq t}|M_u|\geq\eta$ . The $L^2$ maximal inequality, the martingale isometry for the bounded stopping time, and (D3.4) yield

\begin{split} \mathbb P(\tau_\eta\leq t) &\leq\eta^{-2}\mathbb E M_t^2 =\eta^{-2}\mathbb E[p]_{t\wedge\tau_\eta}\\ &\leq\frac1{4\eta^2}\int_0^t \mathbb E[\mathbf 1_{\{s<\tau_\eta\}}(1+X_s)]\,\dd s\\ &\leq\frac1{4\eta^2}\left(t+\int_0^t\mathbb E X_s\,\dd s\right). \end{split}

(D3.22)

This proves (D3.13). All integrands are nonnegative, so Tonelli gives

\begin{split} \int_0^T\mathbb P(\tau_\eta\leq t)\,\dd t &\leq\frac1{4\eta^2}\left\{ \frac{T^2}{2}+\int_0^T(T-s)\mathbb E X_s\,\dd s\right\}\\ &\leq\frac1{4\eta^2}\left(\frac{T^2}{2}+T\Xi_T\right). \end{split}

(D3.23)

Integrating (D3.12) and inserting this estimate gives exactly (D3.14), including the constants $1/16$ , $1/8$ , and $1/4$ .

Finally, $T<1/8$ ensures $\eta=T^{1/3}<1/2$ . With $\varepsilon\leq T^{1/3}$ ,

(\varepsilon/2+\eta)T\leq\tfrac32T^{4/3},\qquad \frac{T^2}{16\eta^2}=\frac1{16}T^{4/3},\qquad \frac{T\Xi_T}{8\eta^2}=\frac18T^{1/3}\Xi_T\leq\frac18\Xi_T.

(D3.24)

Together with the remaining $\Xi_T/4$ , this proves (D3.15), for example with $C=2$ .

3. Evaluating the interface¶

Proof D3.4

Taking the trace in the covariance SDE gives

\dd\operatorname{Tr}A_t=\dd N_t-\operatorname{Tr}(A_t^2)\,\dd t

(D3.26)

for a continuous local martingale $N$ . After localization, expectation kills $N$ and the drift is nonpositive. Since $\operatorname{Tr}A_t\geq0$ , Fatou on removing the localization gives $\mathbb E\operatorname{Tr}A_t\leq\operatorname{Tr}A_0=n$ . Hence $\mathbb E X_t\leq\mathbb E\lambda_{\max}(A_t)\leq n$ .

For $t>0$ , the Brascamp–Lieb covariance cap $A_t\preceq t^{-1}I$ gives $X_t\leq(t^{-1}-1)_+\leq t^{-1}$ . Therefore

\mathbb E X_t\leq\min(n,t^{-1}),

(D3.27)

and, because $T\geq1/n$ ,

\Xi_T\leq\int_0^{1/n}n\,\dd t+ \int_{1/n}^T\frac{\dd t}{t} =1+\log(nT).

(D3.28)

This is only the crude upper fence. In accordance with rem:crude-insufficient, it is not used as a dimension-free KLS input.

Corollary D3.1 (Polylogarithmic evaluation; Corollary 33.1)

Under Assumption 26.1, for $t_1(n)=c_0(\log n)^{-C_2}$ , $\mathbb E\|A_t\|_{\mathrm{op}}\leq C_1$ on $[0,t_1(n)]$ . If $t_1(n)\leq T\leq1$ , then

\Xi_T(\mu)\leq C_1t_1(n)+\log(T/t_1(n)) \leq C(1+\log\log n).

(D3.29)

If also $T<1/8$ , $\varepsilon\leq T^{1/3}$ , and $\mu,E$ satisfy the hypotheses of Theorem D3.1, then

\int_0^T\mathbb E[\bar e_t(E)\mathbf 1_{\{t<\tau_\eta\}}]\,\dd t \leq Te_0+C h_\mu(T^{4/3}+1+\log\log n), \qquad \eta=T^{1/3}.

(D3.30)

Proof D3.5

On $[0,t_1]$ , $X_t\leq\|A_t\|_{\mathrm{op}}$ , so the assumed expectation bound contributes at most $C_1t_1$ . On $[t_1,T]$ , Brascamp–Lieb gives $X_t\leq t^{-1}$ . Integration proves the first inequality in (D3.29). Since $T\leq1$ and $t_1=c_0(\log n)^{-C_2}$ ,

\log(T/t_1)\leq C_2\log\log n-\log c_0,

(D3.31)

and the fixed low-dimensional cases can be absorbed into the universal constant. This proves the second inequality. Substitution into (D3.15) proves (D3.30). The published discharge Corollary 26.2 establishes Assumption 26.1 with $C_2=2$ ; no numerical evidence is used here.

4. The all-measure relative-scale ceiling¶

Proof D3.6

For every positive semidefinite $A$ , $\lambda_{\max}(A)\leq1+(\lambda_{\max}(A)-1)_+$ . Hence (D3.32) gives

\int_0^{T_0}\mathbb E\lambda_{\max}(A_t)\,\dd t \leq(1+\kappa)T_0.

(D3.33)

Fix a balanced cut, $p_0=1/2$ , and let $\tau=\inf\{t:p_t\notin[1/3,2/3]\}$ . The stopped mass martingale is bounded. If $\tau\leq T_0$ , its displacement reaches $1/6$ , so the $L^2$ maximal inequality and the martingale isometry give

\begin{split} \mathbb P(\tau\leq T_0) &\leq36\,\mathbb E[p]_{T_0\wedge\tau}\\ &\leq9\int_0^{T_0}\mathbb E[\mathbf 1_{\{t<\tau\}} \lambda_{\max}(A_t)]\,\dd t\\ &\leq9(1+\kappa)T_0\leq\frac12, \end{split}

(D3.34)

where the second line is (D3.4) without the last replacement by $X_t$ , and the third is (D3.33). Therefore, with probability at least $1/2$ , $\min(p_{T_0},q_{T_0})\geq1/3$ . The balanced-survival lemma (Lemma 30.1) now supplies a universal lower bound for the perimeter of every balanced cut and hence proves KLS.

Finally, (D3.15) bounds the bootstrap error by $C h_\mu(T^{4/3}+\Xi_T)$ . Making this particular certificate no larger than $\kappa h_\mu T$ at a sufficiently small universal time asks, term by term, for $\Xi_T\lesssim\kappa T$ (as well as $T^{1/3}\lesssim\kappa$ ). The implication just proved shows that such an all-measure input, with constants and time satisfying its smallness condition, is sufficient for KLS. The bootstrap itself applies to near-worst measures; it does not require an all-measure estimate as a logical necessity. A large value of this upper certificate gives no lower bound on the actual excess. This is the precise certificate-specific meaning of the proposition’s final sentence: neither a converse nor a general propagation impossibility follows, and seeking a proof of the sufficient covariance bound is not automatically circular. The term $Te_0$ is separate and must also be controlled when the desired estimate concerns the total integrated excess.

Obstructions respected. Theorem D3.1 respects rem:profile-circularity: its profile lower bound comes from the external worst-case constant $\hstar_n$ and the explicit near-worst assumption $h_\mu\leq(1+\varepsilon)\hstar_n$ , not from an assumed lower bound on the random localized profile. Lemma D3.3 respects rem:crude-insufficient by proving and labeling the $\log n$ estimate only as an insufficient fence; the actual corollary uses the published small-time covariance input. Proposition D3.1 proves only the sufficient implication that generates rem:relative-ceiling; it does not claim an equivalence and does not confuse the all-measure condition with the near-worst route.

References¶

Milman, E. (2009). On the Role of Convexity in Isoperimetry, Spectral Gap and Concentration. Inventiones Mathematicae, 177(1), 1–43. 10.1007/s00222-009-0175-9