We thank all of the reviewers for their valuable comments and suggestions

We thank all of the reviewers for their valuable comments and suggestions. We have replaced "Iterations" with "Time" in Figure 1 R2: W all-clock time comparison and # of potential functions being evaluated. Please refer to Figure 3. Additionally, R2: Are there problems on which vanilla Gibbs would be prohibitively expensive? R2: Are there problems on which Poisson-Gibbs might fail? Empirically, we did not find a poor initialization issue for Poisson-Gibbs.