Fast sampling via spectral independence beyond bounded-degree graphs
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 uniquene...
| Asıl Yazarlar: | , , , |
|---|---|
| Materyal Türü: | Conference item |
| Dil: | English |
| Baskı/Yayın Bilgisi: |
Leibniz International Proceedings in Informatics
2022
|
| _version_ | 1826308014357872640 |
|---|---|
| author | Bezakova, I Galanis, A Goldberg, L Stefankovic, D |
| author_facet | Bezakova, I Galanis, A Goldberg, L Stefankovic, D |
| author_sort | Bezakova, I |
| collection | OXFORD |
| description | 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, 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. |
| first_indexed | 2024-03-07T07:11:41Z |
| format | Conference item |
| id | oxford-uuid:02f02282-7166-49e3-ac7c-1f1d2a5b9af7 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:11:41Z |
| publishDate | 2022 |
| publisher | Leibniz International Proceedings in Informatics |
| record_format | dspace |
| spelling | oxford-uuid:02f02282-7166-49e3-ac7c-1f1d2a5b9af72022-07-11T09:57:12ZFast sampling via spectral independence beyond bounded-degree graphsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:02f02282-7166-49e3-ac7c-1f1d2a5b9af7EnglishSymplectic ElementsLeibniz International Proceedings in Informatics2022Bezakova, IGalanis, AGoldberg, LStefankovic, DSpectral 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, 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. |
| spellingShingle | Bezakova, I Galanis, A Goldberg, L Stefankovic, D Fast sampling via spectral independence beyond bounded-degree graphs |
| title | Fast sampling via spectral independence beyond bounded-degree graphs |
| title_full | Fast sampling via spectral independence beyond bounded-degree graphs |
| title_fullStr | Fast sampling via spectral independence beyond bounded-degree graphs |
| title_full_unstemmed | Fast sampling via spectral independence beyond bounded-degree graphs |
| title_short | Fast sampling via spectral independence beyond bounded-degree graphs |
| title_sort | fast sampling via spectral independence beyond bounded degree graphs |
| work_keys_str_mv | AT bezakovai fastsamplingviaspectralindependencebeyondboundeddegreegraphs AT galanisa fastsamplingviaspectralindependencebeyondboundeddegreegraphs AT goldbergl fastsamplingviaspectralindependencebeyondboundeddegreegraphs AT stefankovicd fastsamplingviaspectralindependencebeyondboundeddegreegraphs |