Adaptive Greedy Rejection Sampling
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909202331467776 |
|---|---|
| author | Flamich, Gergely Theis, Lucas |
| author_facet | Flamich, Gergely Theis, Lucas |
| contents | We consider channel simulation protocols between two communicating parties, Alice and Bob. First, Alice receives a target distribution $Q$, unknown to Bob. Then, she employs a shared coding distribution $P$ to send the minimum amount of information to Bob so that he can simulate a single sample $X \sim Q$. For discrete distributions, Harsha et al. (2009) developed a well-known channel simulation protocol -- greedy rejection sampling (GRS) -- with a bound of ${D_{KL}[Q \,\Vert\, P] + 2\ln(D_{KL}[Q \,\Vert\, P] + 1) + \mathcal{O}(1)}$ on the expected codelength of the protocol. In this paper, we extend the definition of GRS to general probability spaces and allow it to adapt its proposal distribution after each step. We call this new procedure Adaptive GRS (AGRS) and prove its correctness. Furthermore, we prove the surprising result that the expected runtime of GRS is exactly $\exp(D_\infty[Q \,\Vert\, P])$, where $D_\infty[Q \,\Vert\, P]$ denotes the Rényi $\infty$-divergence. We then apply AGRS to Gaussian channel simulation problems. We show that the expected runtime of GRS is infinite when averaged over target distributions and propose a solution that trades off a slight increase in the coding cost for a finite runtime. Finally, we describe a specific instance of AGRS for 1D Gaussian channels inspired by hybrid coding. We conjecture and demonstrate empirically that the runtime of AGRS is $\mathcal{O}(D_{KL}[Q \,\Vert\, P])$ in this case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_10407 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Adaptive Greedy Rejection Sampling Flamich, Gergely Theis, Lucas Information Theory 94A40 (Primary) 68Q11, 68Q17 (Secondary) E.4; H.1.1 We consider channel simulation protocols between two communicating parties, Alice and Bob. First, Alice receives a target distribution $Q$, unknown to Bob. Then, she employs a shared coding distribution $P$ to send the minimum amount of information to Bob so that he can simulate a single sample $X \sim Q$. For discrete distributions, Harsha et al. (2009) developed a well-known channel simulation protocol -- greedy rejection sampling (GRS) -- with a bound of ${D_{KL}[Q \,\Vert\, P] + 2\ln(D_{KL}[Q \,\Vert\, P] + 1) + \mathcal{O}(1)}$ on the expected codelength of the protocol. In this paper, we extend the definition of GRS to general probability spaces and allow it to adapt its proposal distribution after each step. We call this new procedure Adaptive GRS (AGRS) and prove its correctness. Furthermore, we prove the surprising result that the expected runtime of GRS is exactly $\exp(D_\infty[Q \,\Vert\, P])$, where $D_\infty[Q \,\Vert\, P]$ denotes the Rényi $\infty$-divergence. We then apply AGRS to Gaussian channel simulation problems. We show that the expected runtime of GRS is infinite when averaged over target distributions and propose a solution that trades off a slight increase in the coding cost for a finite runtime. Finally, we describe a specific instance of AGRS for 1D Gaussian channels inspired by hybrid coding. We conjecture and demonstrate empirically that the runtime of AGRS is $\mathcal{O}(D_{KL}[Q \,\Vert\, P])$ in this case. |
| title | Adaptive Greedy Rejection Sampling |
| topic | Information Theory 94A40 (Primary) 68Q11, 68Q17 (Secondary) E.4; H.1.1 |
| url | https://arxiv.org/abs/2304.10407 |