1 Search Results for "Liu, Kuikui"

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.32

From Coupling to Spectral Independence and Blackbox Comparison with the Down-Up Walk

Authors: Kuikui Liu

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract

We show that the existence of a "good" coupling w.r.t. Hamming distance for any local Markov chain on a discrete product space implies rapid mixing of the Glauber dynamics in a blackbox fashion. More specifically, we only require the expected distance between successive iterates under the coupling to be summable, as opposed to being one-step contractive in the worst case. Combined with recent local-to-global arguments [Chen et al., 2021], we establish asymptotically optimal lower bounds on the standard and modified log-Sobolev constants for the Glauber dynamics for sampling from spin systems on bounded-degree graphs when a curvature condition [Ollivier, 2009] is satisfied. To achieve this, we use Stein’s method for Markov chains [Bresler and Nagaraj, 2019; Reinert and Ross, 2019] to show that a "good" coupling for a local Markov chain yields strong bounds on the spectral independence of the distribution in the sense of [Anari et al., 2020]. Our primary application is to sampling proper list-colorings on bounded-degree graphs. In particular, combining the coupling for the flip dynamics given by [Vigoda, 2000; Chen et al., 2019] with our techniques, we show optimal O(nlog n) mixing for the Glauber dynamics for sampling proper list-colorings on any bounded-degree graph with maximum degree Δ whenever the size of the color lists are at least ({11/6 - ε}) Δ, where ε ≈ 10^{-5} is small constant. While O(n²) mixing was already known before, our approach additionally yields Chernoff-type concentration bounds for Hamming Lipschitz functions in this regime, which was not known before. Our approach is markedly different from prior works establishing spectral independence for spin systems using spatial mixing [Anari et al., 2020; Z. {Chen} et al., 2020; Chen et al., 2021; Feng et al., 2021], which crucially is still open in this regime for proper list-colorings.

Cite as

Kuikui Liu. From Coupling to Spectral Independence and Blackbox Comparison with the Down-Up Walk. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 32:1-32:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{liu:LIPIcs.APPROX/RANDOM.2021.32,
  author =	{Liu, Kuikui},
  title =	{{From Coupling to Spectral Independence and Blackbox Comparison with the Down-Up Walk}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{32:1--32:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.32},
  URN =		{urn:nbn:de:0030-drops-147259},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.32},
  annote =	{Keywords: Markov chains, Approximate counting, Spectral independence}
}

Refine by Author
1 Liu, Kuikui

Refine by Classification
1 Theory of computation → Random walks and Markov chains

Refine by Keyword
1 Approximate counting
1 Markov chains
1 Spectral independence

Refine by Type
1 document

Refine by Publication Year
1 2021

1 Search Results for "Liu, Kuikui"

From Coupling to Spectral Independence and Blackbox Comparison with the Down-Up Walk

Abstract

Cite as

Thanks for your feedback!

Could not send message