Eldan's stochastic localization and the KLS conjecture: Isoperimetry, concentration and mixing

被引:0
|
作者
Lee, Yin Tat [1 ,2 ]
Vempala, Santosh S. [3 ]
机构
[1] Univ Washington, Microsoft Res, Seattle, WA 98195 USA
[2] Univ Washington, Paul G Allen Sch Comp Sci & Engn, Seattle, WA 98195 USA
[3] Georgia Inst Technol, Sch Comp Sci, Atlanta, GA USA
关键词
isoperimetry; concentration; KLS; log-Sob olev; mixing of speedy walk; CENTRAL-LIMIT-THEOREM; SOBOLEV INEQUALITIES; LOGCONCAVE FUNCTIONS; RANDOM-WALKS; THIN-SHELL; CONVEX; VOLUME; ALGORITHMS;
D O I
10.4007/annals.2024.199.3.2
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We analyze the Poincar & eacute; and Log-Sob olev constants of logconcave densities in Rn. For the Poincar & eacute; constant, we give an improved estimate of O(root n) for any isotropic logconcave density. For the Log-Sob olev constant, we prove a bound of Omega(1/D), where D is the diameter of the support of the density, and show that this is asymptotically the best possible bound, resolving a question posed by Frieze and Kannan in 1997. These bounds have several interesting consequences. Improved bounds on the thin-shell and Cheeger/KLS constants are immediate. The ball walk to sample an isotropic logconcave density in Rn converges in O*(n2.5) steps from a warm start, and the speedy version of the ball walk, studied by Kannan, Lov & aacute;sz and Simonovits mixes in O*(n2D) proper steps from any start, also a tight bound. As another consequence, we obtain a unified and improved large deviation inequality for the concentration of any L-Lipshitz function over an isotropic logconcave density (studied by many), generalizing bounds of Paouris and Guedon-E. Milman. Our proof technique is a development of stochastic localization, first introduced by Eldan.
引用
收藏
页码:1043 / 1092
页数:50
相关论文
共 3 条
  • [1] Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Improved Lower Bound for Expansion
    Lee, Yin Tat
    Vempala, Santosh S.
    2017 IEEE 58TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2017, : 998 - 1007
  • [2] Bourgain's slicing problem and KLS isoperimetry up to polylog
    Klartag, Bo'az
    Lehec, Joseph
    GEOMETRIC AND FUNCTIONAL ANALYSIS, 2022, 32 (05) : 1134 - 1159
  • [3] On Gilles Pisier's approach to Gaussian concentration, isoperimetry, and Poincaré-type inequalities
    Bobkov, Sergey G.
    Volzone, Bruno
    ELECTRONIC JOURNAL OF PROBABILITY, 2024, 29