| Paper ID | D7-S2-T4.3 |
| Paper Title |
An MCMC Method to Sample from Lattice Distributions |
| Authors |
Anand Jerry George, Navin Kashyap, Indian Institute of Science, India |
| Session |
D7-S2-T4: Topics in Privacy & Cryptography I |
| Chaired Session: |
Tuesday, 20 July, 22:20 - 22:40 |
| Engagement Session: |
Tuesday, 20 July, 22:40 - 23:00 |
| Abstract |
We introduce a Markov Chain Monte Carlo (MCMC) algorithm to generate samples from probability distributions supported on a $d$-dimensional lattice $\Lambda = \mathbf{B}\Z^d$, where $\mathbf{B}$ is a full-rank matrix. Specifically, we consider lattice distributions $P_\Lambda$ in which the probability at a lattice point is proportional to a given probability density function, $f$, evaluated at that point. To generate samples from $P_\Lambda$, it suffices to draw samples from a pull-back measure $P_{\Z^d}$ defined on the integer lattice. The probability of an integer lattice point under $P_{\Z^d}$ is proportional to the density function $\pi = |\det(\mathbf{B})|f \circ \mathbf{B}$. The algorithm we present in this paper for sampling from $P_{\Z^d}$ is based on the Metropolis-Hastings framework. In particular, we use $\pi$ as the proposal distribution and calculate the Metropolis-Hastings acceptance ratio for a well-chosen target distribution. We can use any method, denoted by \textbf{ALG}, that ideally draws samples from the probability density $\pi$, to generate a proposed state. The target distribution is chosen such that the coordinate-wise rounding of a sample drawn from the target distribution gives a sample from $P_{\Z^d}$. When \textbf{ALG} is ideal, we show that our algorithm is uniformly ergodic if $-\log(\pi)$ satisfies a gradient Lipschitz condition.
|
