Fast Sampling via Spectral Independence Beyond Bounded-degree Graphs
ACM Transactions on Algorithms · 31.01.2024 · 20 (1) · 1-26
DOI: 10.1145/3631354 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 22.01.2024. Verfasst von Ivona Bezáková und 3 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 40 Literaturangaben. Gefördert von: NSF.
Abstract (Originalsprache)
Spectral independence is a recently developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal O(n log n) sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Ising-model configurations. Our main contribution is to relax the bounded-degree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on using L p -norms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, and Yin, FOCS’13). The non-linearity of L p -norms is an obstacle to applying these results to bound spectral independence. Our solution is to capture the L p -analysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to bounded-degree graphs. As a main application of our techniques, we consider the random graph G (n, d/n) , where the previously known algorithms run in time n O (log d ) or applied only to large d . We refine these algorithmic bounds significantly, and develop fast nearly linear algorithms based on Glauber dynamics that apply to all constant d , throughout the uniqueness regime.
Förderung
- NSF
Zitieren
APA
Bezáková, I., Galanis, A., Goldberg, L. A., & Štefankovič, D. (2024). Fast Sampling via Spectral Independence Beyond Bounded-degree Graphs. ACM Transactions on Algorithms, 20(1), 1-26. https://doi.org/10.1145/3631354
Vancouver
Bezáková I, Galanis A, Goldberg LA, Štefankovič D. Fast Sampling via Spectral Independence Beyond Bounded-degree Graphs. ACM Transactions on Algorithms. 2024;20(1):1-26. doi:10.1145/3631354
BibTeX
@article{Bezkov2024,
author = {Bezáková, Ivona and Galanis, Andreas and Goldberg, Leslie Ann and Štefankovič, Daniel},
title = {Fast Sampling via Spectral Independence Beyond Bounded-degree Graphs},
journal = {ACM Transactions on Algorithms},
year = {2024},
volume = {20},
number = {1},
pages = {1--26},
doi = {10.1145/3631354}
}
EUVIMED