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

DOI10.1145/3188745.3188866MaRDI QIDQ5230367zbMATH OpenOpenAlexFDO

Authors Yin Tat Lee, Santosh S. Vempala

Publication date 22 August 2019

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

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

zbMATH Keywords

ball walklog-Sobolev constantlogconcave densitiesStieltjes barrierstochastic localization

Mathematics Subject Classification ID

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

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.

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

Cited in

(17)

• Bourgain's slicing problem and KLS isoperimetry up to polylog
• Improved bounds for Hadwiger's covering problem via thin-shell estimates
• Constrained convex bodies with extremal affine surface areas
• Bounds on optimal transport maps onto log-concave measures
• Modified log-Sobolev inequalities for strongly log-concave distributions
• Dimension-free log-Sobolev inequalities for mixture distributions
• Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions: continuous dynamics
• Thin-shell concentration for random vectors in Orlicz balls via moderate deviations and Gibbs measures
• Poincaré and logarithmic Sobolev inequalities for nearly radial measures
• Fast MCMC sampling algorithms on polytopes
• Fast mixing of Metropolized Hamiltonian Monte Carlo: benefits of multi-step gradients
• On the Poincaré constant of log-concave measures
• A generalized central limit conjecture for convex bodies
• Tyler's and Maronna's M-estimators: non-asymptotic concentration results
• Analysis of high-dimensional distributions using pathwise methods
• Sharp concentration phenomena in high-dimensional Orlicz balls
• Extreme eigenvalues of log-concave ensemble

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)