Modified log-Sobolev inequalities for strongly log-concave distributions

Mary Cryan; Heng Guo; Giorgos Mousa

doi:10.1109/FOCS.2019.00083

Modified log-Sobolev inequalities for strongly log-concave distributions

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English
Title of host publication	2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
Publisher	Institute of Electrical and Electronics Engineers
Pages	1358-1370
Number of pages	14
ISBN (Electronic)	978-1-7281-4952-3
ISBN (Print)	978-1-7281-4953-0
DOIs	https://doi.org/10.1109/FOCS.2019.00083
Publication status	Published - 6 Jan 2020
Event	60th Annual IEEE Symposium on Foundations of Computer Science - Baltimore, United States Duration: 9 Nov 2019 → 12 Nov 2019 http://focs2019.cs.jhu.edu/

Publication series

Name
ISSN (Print)	1523-8288
ISSN (Electronic)	2575-8454

Conference

Conference	60th Annual IEEE Symposium on Foundations of Computer Science
Abbreviated title	FOCS 2019
Country/Territory	United States
City	Baltimore
Period	9/11/19 → 12/11/19
Internet address	http://focs2019.cs.jhu.edu/

Keywords / Materials (for Non-textual outputs)

math.PR
cs.DS
math.CO

Access to Document

10.1109/FOCS.2019.00083Licence: All Rights Reserved

1903.06081v1Submitted manuscript, 225 KB
Modified Log-Sobolev_CRYAN_DoA240619_AFVAccepted author manuscript, 340 KBLicence: All Rights Reserved

https://ieeexplore.ieee.org/document/8948600Licence: All Rights Reserved

Cite this

@inproceedings{bd86f98ae3ee4005a718bb79927527ab,

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 = "math.PR, cs.DS, math.CO",

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

year = "2020",

month = jan,

day = "6",

doi = "10.1109/FOCS.2019.00083",

language = "English",

isbn = "978-1-7281-4953-0",

publisher = "Institute of Electrical and Electronics Engineers",

pages = "1358--1370",

booktitle = "2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)",

address = "United States",

note = "60th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2019 ; Conference date: 09-11-2019 Through 12-11-2019",

url = "http://focs2019.cs.jhu.edu/",

}

Cryan, M , Guo, H & Mousa, G 2020, Modified log-Sobolev inequalities for strongly log-concave distributions. in 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). Institute of Electrical and Electronics Engineers, pp. 1358-1370, 60th Annual IEEE Symposium on Foundations of Computer Science, Baltimore, Maryland, United States, 9/11/19. https://doi.org/10.1109/FOCS.2019.00083

TY - GEN

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

AU - Cryan, Mary

AU - Guo, Heng

AU - Mousa, Giorgos

PY - 2020/1/6

Y1 - 2020/1/6

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 - math.PR

KW - cs.DS

KW - math.CO

UR - https://ieeexplore.ieee.org/document/8948600

U2 - 10.1109/FOCS.2019.00083

DO - 10.1109/FOCS.2019.00083

M3 - Conference contribution

SN - 978-1-7281-4953-0

SP - 1358

EP - 1370

BT - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)

PB - Institute of Electrical and Electronics Engineers

T2 - 60th Annual IEEE Symposium on Foundations of Computer Science

Y2 - 9 November 2019 through 12 November 2019

ER -

Modified log-Sobolev inequalities for strongly log-concave distributions

Abstract

Publication series

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Other files and links

Fingerprint