Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2502.10795 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914088572944384 |
|---|---|
| author | Liu, Hongyang Wang, Chunyang Yin, Yitong |
| author_facet | Liu, Hongyang Wang, Chunyang Yin, Yitong |
| contents | Local samplers are algorithms that generate random samples based on local queries to high-dimensional distributions, ensuring the samples follow the correct induced distributions while maintaining time complexity that scales locally with the query size. These samplers have broad applications, including deterministic approximate counting [He, Wang, Yin, SODA '23; Feng et.al., FOCS '23], sampling from infinite or high-dimensional Gibbs distributions [Anand, Jerrum, SICOMP '22; He, Wang, Yin, FOCS '22], and providing local access to large random objects [Biswas, Rubinfield, Yodpinyanee, ITCS '20]. In this work, we present local samplers for Gibbs distributions of spin systems.
Specifically, we design linear-time local samplers for:
- permissive spin systems, including the first local sampler for the Ising model in near-critical regimes;
- truly repulsive spin systems, represented by the first local sampler for uniform proper $q$-colorings, with $q=O(Δ)$ colors on graphs with maximum degree $Δ$.
These local samplers are efficient beyond the "local uniformity" threshold, which imposes unconditional marginal lower bounds -- a key assumption required by all prior local samplers. Our results show that, in general, local sampling is not significantly harder than global sampling for spin systems. As an application, our results also imply local algorithms for probabilistic inference in the same near-critical regimes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_10795 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Local Gibbs sampling beyond local uniformity Liu, Hongyang Wang, Chunyang Yin, Yitong Data Structures and Algorithms Local samplers are algorithms that generate random samples based on local queries to high-dimensional distributions, ensuring the samples follow the correct induced distributions while maintaining time complexity that scales locally with the query size. These samplers have broad applications, including deterministic approximate counting [He, Wang, Yin, SODA '23; Feng et.al., FOCS '23], sampling from infinite or high-dimensional Gibbs distributions [Anand, Jerrum, SICOMP '22; He, Wang, Yin, FOCS '22], and providing local access to large random objects [Biswas, Rubinfield, Yodpinyanee, ITCS '20]. In this work, we present local samplers for Gibbs distributions of spin systems. Specifically, we design linear-time local samplers for: - permissive spin systems, including the first local sampler for the Ising model in near-critical regimes; - truly repulsive spin systems, represented by the first local sampler for uniform proper $q$-colorings, with $q=O(Δ)$ colors on graphs with maximum degree $Δ$. These local samplers are efficient beyond the "local uniformity" threshold, which imposes unconditional marginal lower bounds -- a key assumption required by all prior local samplers. Our results show that, in general, local sampling is not significantly harder than global sampling for spin systems. As an application, our results also imply local algorithms for probabilistic inference in the same near-critical regimes. |
| title | Local Gibbs sampling beyond local uniformity |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.10795 |