Modified log-Sobolev inequalities for strongly log-concave distributions

Mary Cryan; Heng Guo; Giorgos Mousa

doi:10.1214/20-AOP1453

Modified log-Sobolev inequalities for strongly log-concave distributions

Research output: Contribution to journal › Article › peer-review

Abstract / Description of output

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.

Original language	English
Pages (from-to)	506-525
Number of pages	20
Journal	Annals of Probability
Volume	49
Issue number	1
DOIs	https://doi.org/10.1214/20-AOP1453
Publication status	Published - 22 Jan 2021

Keywords / Materials (for Non-textual outputs)

matroids
bases exchange walk
Markov chains
log-Sobolev inequality

Access to Document

10.1214/20-AOP1453Licence: All Rights Reserved

Log-Sob-matroid-AoP-FinalProof, 389 KBLicence: All Rights Reserved

https://projecteuclid.org/euclid.aop/1611306386Licence: All Rights Reserved

1 Conference contribution

Modified log-Sobolev inequalities for strongly log-concave distributions
Cryan, M., Guo, H. & Mousa, G., 6 Jan 2020, 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). Institute of Electrical and Electronics Engineers (IEEE), p. 1358-1370 14 p.
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Open Access
File

Cite this

@article{2880140ff57a47ac8de8c850171c9d47,

title = "Modified log-Sobolev inequalities for strongly log-concave distributions",

abstract = "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.",

keywords = "matroids, bases exchange walk, Markov chains, log-Sobolev inequality",

author = "Mary Cryan and Heng Guo and Giorgos Mousa",

note = "Date of acceptance: 15/06/2020. We do not have volume numbers or dates for publication at this point. ",

year = "2021",

month = jan,

day = "22",

doi = "10.1214/20-AOP1453",

language = "English",

volume = "49",

pages = "506--525",

journal = "Annals of Probability",

issn = "0091-1798",

publisher = "Institute of Mathematical Statistics",

number = "1",

}

TY - JOUR

T1 - Modified log-Sobolev inequalities for strongly log-concave distributions

AU - Cryan, Mary

AU - Guo, Heng

AU - Mousa, Giorgos

N1 - Date of acceptance: 15/06/2020. We do not have volume numbers or dates for publication at this point.

PY - 2021/1/22

Y1 - 2021/1/22

N2 - 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.

AB - 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.

KW - matroids

KW - bases exchange walk

KW - Markov chains

KW - log-Sobolev inequality

U2 - 10.1214/20-AOP1453

DO - 10.1214/20-AOP1453

M3 - Article

SN - 0091-1798

VL - 49

SP - 506

EP - 525

JO - Annals of Probability

JF - Annals of Probability

IS - 1

ER -

Modified log-Sobolev inequalities for strongly log-concave distributions

Abstract / Description of output

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Research output

Modified log-Sobolev inequalities for strongly log-concave distributions

Cite this