An almost constant lower bound of the isoperimetric coefficient in the KLS conjecture

Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Length, area, volume and convex sets (aspects of convex geometry) (52A38) Inequalities and extremum problems involving convexity in convex geometry (52A40) Probability distributions: general theory (60E05)

Abstract: We prove an almost constant lower bound of the isoperimetric coefficient in the KLS conjecture. The lower bound has the dimension dependency

d^{- o_{d} (1)}

. When the dimension is large enough, our lower bound is tighter than the previous best bound which has the dimension dependency

d^{- 1 / 4}

. Improving the current best lower bound of the isoperimetric coefficient in the KLS conjecture has many implications, including improvements of the current best bounds in Bourgain's slicing conjecture and in the thin-shell conjecture, better concentration inequalities for Lipschitz functions of log-concave measures and better mixing time bounds for MCMC sampling algorithms on log-concave measures.

Review text

A probability density function \(p\): \(\mathbb{R}^d \to \mathbb{R}\) is log-concave if its logarithm is concave. Common probability distributions such as normal, exponential and logistic are log-concave. The isoperimetric coefficient \(\psi(p)\) of a density \(p\) in \(\mathbb{R}^d\) is defined as \(\psi(p) = \inf\limits_{S\subset\mathbb{R}^d} \frac{p^+(\partial S)} {\min(p(S), p(S^c))}\), where \(S^c\) is the complement of \(S\), \(p(S) = \int_{x\in S} p(x)\,dx\), and the boundary measure of the subset is \(p^+(\partial S) = \liminf\limits_{\varepsilon\to 0^+} \frac{p(\{x: d(x, S)\le \varepsilon\}) - p(S)}{\varepsilon}\), where \(d(x, S)\) is the Euclidean distance between \(x\) and the subset \(S\). Kannan, Lovàsz and Simonovits (KLS) conjecture is stated as follows: There exists a universal constant \(c\), such that for any log-concave density \(p\) in \(\mathbb{R}^d\), we have \(\psi(p) \ge \frac{c}{\sqrt{\rho(p)}}\), where \(\rho(p)\) is the spectral norm of the covariance matrix of \(p\) [\textit{R. Kannan} et al., Discrete Comput. Geom. 13, No. 3--4, 541--559 (1995; Zbl 0824.52012)]. Proving the lower bound on \(\psi(p)\) up to some small factors is the main goal of the present paper. Additionally, improving the lower bound in the KLS conjecture also improves concentration inequalities for Lipschitz functions of log-concave measures. It also leads to faster mixing time bounds of Markov chain Monte Carlo (MCMC) sampling algorithms on log-concave measures.

Recommendations

Cites work

Cited in

(78)

This page was built for publication: An almost constant lower bound of the isoperimetric coefficient in the KLS conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2035530)