Stochastic localization + Stieltjes barrier = tight bound for log-Sobolev

DOI10.1145/3188745.3188866zbMATH Open1429.65028arXiv1712.01791OpenAlexW2963464622MaRDI QIDQ5230367FDOQ5230367

Santosh S. Vempala, Yin Tat Lee

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: Logarithmic Sobolev inequalities are a powerful way to estimate the rate of convergence of Markov chains and to derive concentration inequalities on distributions. We prove that the log-Sobolev constant of any isotropic logconcave density in $R^n$ with support of diameter $D$ is $1/D$, resolving a question posed by Frieze and Kannan in 1997. This is asymptotically the best possible estimate and improves on the previous bound of $1/D^2$ by Kannan-Lov'asz-Montenegro. It follows that for any isotropic logconcave density, the ball walk with step size $delta=(1/sqrtn)$ mixes in $O(n^{2}D)$ proper steps from any starting point. This improves on the previous best bound of $O(n^2{D}^2)$ and is also asymptotically tight. The new bound leads to the following refined large deviation inequality for any L-Lipschitz function g over an isotropic logconcave density p: for any t > 0, ${\displaystyle }$P(|g(x)- �ar{g}(x)| ge c . L. t) le exp(-frac{t^2}{t+sqrt{n}})${\displaystyle }$ where $$ is the median or mean of $g$ for $xsimp$; this generalizes/improves on previous bounds by Paouris and by Guedon-Milman. The technique also bounds the "small ball" probability in terms of the Cheeger constant, and recovers the current best bound. Our main proof is based on stochastic localization together with a Stieltjes-type barrier function.

Full work available at URL: https://arxiv.org/abs/1712.01791

Recommendations

• Modified log-Sobolev inequalities for strongly log-concave distributions
• Log-Sobolev inequalities and sampling from log-concave distributions
• Modified logarithmic Sobolev inequalities for some models of random walk
• Dimension-free log-Sobolev inequalities for mixture distributions
• scientific article; zbMATH DE number 1405932

zbMATH Keywords

log-Sobolev constantball walklogconcave densitiesstochastic localizationStieltjes barrier

Mathematics Subject Classification ID

Numerical analysis or methods applied to Markov chains (65C40) Inequalities; stochastic orderings (60E15)

Cited In (12)

• Bounds on optimal transport maps onto log-concave measures
• Tyler's and Maronna's M-estimators: non-asymptotic concentration results
• Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions: continuous dynamics
• Title not available (Why is that?)
• Title not available (Why is that?)
• Constrained convex bodies with extremal affine surface areas
• Thin-shell concentration for random vectors in Orlicz balls via moderate deviations and Gibbs measures
• On the Poincaré Constant of Log-Concave Measures
• Bourgain's slicing problem and KLS isoperimetry up to polylog
• Poincaré and logarithmic Sobolev inequalities for nearly radial measures
• Improved bounds for Hadwiger's covering problem via thin-shell estimates
• A Generalized Central Limit Conjecture for Convex Bodies

This page was built for publication: Stochastic localization + Stieltjes barrier = tight bound for log-Sobolev

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