Response to Reviewer rYFn
We thank the reviewer for their response to our rebuttal; we address the reviewers first comment below
> First of all, if exact posterior is used, the the rate shuold be $D_{KL} + \log D_{KL} + \log\log D_{KL} + \dots$ bits. If the current curve of Figure 2 in the rebuttal document, it is wrong, as its rate is $D_{KL}$ bits, which is only true for asymptomatic channel simulation, not one shot channel simulation like this paper. I suggest the author to consider this one-shot overhead and show the correct figure in the later version.
We believe there are two points of slight misunderstanding here, which we address below. Please let us know if we did not interpret the reviewer's comment correctly.
**The reported curve in Figure 2:** We believe the reviewer assumes that the dashed line in Figure 2 is supposed to describe the efficiency of an exact channel simulation protocol, for which the codelength would include some additional overhead terms besides the KL divergence, as the reviewer rightly mentions. However, this is not our intention. As described in Section 3.3 of the paper, we use an approximate protocol such that the codelength is always approximately equal to the KL (within each block). Hence, what we compare in Figure 2 is the quality of approximate samples compared to exact ones at the same coding cost. In other words, the dashed line describes the practically unattainable scenario if our scheme would always yield exact samples instead of approximate ones at the same codelength as before.
We also note that if we included the extra log term in the rate calculation of the idealised sampler, the theoretically ideal curve would look worse since it would shift the curve to the right; thereby making COMBINER look better.
**The overhead terms in exact channel simulation:** We believe the reviewer is referring to the limiting case of Li and Vitanyi's universal prefix-free codes to encode the index returned by the sampler, yielding a codelength bound of approximately $D_{KL} + \log D_{KL} + \log\log D_{KL} + \dots$ in the one-shot case. Via Jensen's inequality, this would yield a bound of approximately $I[\mathcal{D} : w] + \log I[\mathcal{D} : w] + \log\log I[\mathcal{D} : w] + \dots$ in the average case, where $I[\mathcal{D} : w]$ denotes the mutual information between the data $\mathcal{D}$ and the INR weights $w$ that encode it. However, using the zeta distribution approach described in Appendices A and B in Li & El Gamal (2018), we can reduce the average-case bound to approximately $I[\mathcal{D} : w] + \log (I[\mathcal{D} : w] + 1) + 5$, which is a better bound!
## References
M. Li and P. Vitanyi, An Introduction to Kolmogorov Complexity and
Its Applications, 3rd ed. New York: Springer-Verlag, 2008.
C. T. Li and A. El Gamal (2018). Strong functional representation lemma and applications to coding theorems. IEEE Transactions on Information Theory, 64(11), 6967-6978.