Modified log-Sobolev inequalities for strongly log-concave distributions

被引：15
作者：
Cryan, Mary [1 ]
Guo, Heng [1 ]
Mousa, Giorgos [1 ]
机构：
[1] Univ Edinburgh, Sch Informat, Edinburgh, Midlothian, Scotland
来源：
2019 IEEE 60TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2019) | 2019年
关键词：
Matroids; bases-exchange walk; Markov chains; mixing time; concentration of measure; BOUNDS; MODELS;
D O I：
10.1109/FOCS.2019.00083
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We show that the modified log-Sobolev constant for a natural Markov chain which converges to an r-homogeneous strongly log-concave distribution is at least 1/r. Applications include an asymptotically optimal mixing time bound for the bases-exchange walk for matroids, and a concentration bound for Lipschitz functions over these distributions.
引用
收藏
页码：1358 / 1370
页数：13
相关论文
共 30 条
  • [1] Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid
    Anari, Nima
    Liu, Kuikui
    Gharan, Shayan Oveis
    Vinzant, Cynthia
    [J]. PROCEEDINGS OF THE 51ST ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '19), 2019, : 1 - 12
  • [2] Log-Concave Polynomials, Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids
    Anari, Nima
    Gharan, Shayan Oveis
    Vinzant, Cynthia
    [J]. 2018 IEEE 59TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2018, : 35 - 46
  • [3] Anari Nima, 2016, C LEARN THEOR, V49, P103
  • [4] [Anonymous], 1993, Matroid Theory
  • [5] [Anonymous], 2003, LEC MATH
  • [6] [Anonymous], 2016, Concentration Inequalities: A Nonasymptotic Theory of Independence, DOI DOI 10.1093/ACPROF:OSO/9780199535255.001.0001
  • [7] The subgaussian constant and concentration inequalities
    Bobkov, S. G.
    Houdre, C.
    Tetali, P.
    [J]. ISRAEL JOURNAL OF MATHEMATICS, 2006, 156 (1) : 255 - 283
  • [8] Modified logarithmic Sobolev inequalities in discrete settings
    Bobkov, Sergey G.
    Tetali, Prasad
    [J]. JOURNAL OF THEORETICAL PROBABILITY, 2006, 19 (02) : 289 - 336
  • [9] Exponential integrability and transportation cost related to logarithmic sobolev inequalities
    Bobkov, SG
    Götze, F
    [J]. JOURNAL OF FUNCTIONAL ANALYSIS, 1999, 163 (01) : 1 - 28
  • [10] Borcea J, 2009, J AM MATH SOC, V22, P521
123