Channel Simulation and Distributed Compression with Ensemble Rejection Sampling
Authors: Buu Phan
Ashish J Khisti
Venue: NeurIPS 2025 poster ()
Keywords: Channel Simmulation
Distributed Compression
Probabilistic Method
Primary area: probabilistic_methods
TL;DR: We provide a new channel simulation approach for distributed compression using Ensemble Rejection Sampling

Abstract: We study channel simulation and distributed matching, two fundamental problems with several applications to machine learning, using a recently introduced generalization of the standard rejection sampling (RS) algorithm known as Ensemble Rejection Sampling (ERS). For channel simulation, we propose a new coding scheme based on ERS that achieves a near-optimal coding rate. In this process, we demonstrate that standard RS can also achieve a near-optimal coding rate and generalize the result of Braverman and Garg (2014) to the continuous alphabet setting. Next, as our main contribution, we present a distributed matching lemma for ERS, which serves as the rejection sampling counterpart to the Poisson Matching Lemma (PML) introduced by Li and Anantharam (2021). Our result also generalizes a recent work on importance matching lemma (Phan et al, 2024) and, to our knowledge, is the first result on distributed matching in the family of rejection sampling schemes where the matching probability is close to PML. We demonstrate the practical significance of our approach over prior works by applying it to distributed compression. The effectiveness of our proposed scheme is validated through experiments involving synthetic Gaussian sources and distributed image compression using the MNIST dataset.

Channel Simulation and Distributed Compression with Ensemble Rejection Sampling
Buu Phan' Ashish Khisti
Department of Electrical and Computer Engineering, University of Toronto truong. pww.gmaaaaamllllmm utoronto. ca, akhisti@ece utoronto. ca
Abstract
We study channel simulation and distributed matching, two fundamental prob- lems with several applications to machine learning, using recently introduced generalization of the standard rejection sampling (RS) algorithm known as En- semble Rejection Sampling (ERS). For channel simulation, propose new coding scheme based on ERS that achieves a near-optimal coding rate. this process, we demonstrate that standard RS can also achieve near-optimal coding rate and generalize the result of Braverman and Garg (2014) to the continuous alphabet setting. Next,
main contribution, we present distributed matching lemma for ERS, which serves as the rejection sampling counterpart to the Poisson Matching Lemma (PML) introduced by Li and Anantharam (2021). Our result also generalizes a recent work on importance matching lemma (Phan et al, 2024) and, to knowledge, is the first result distributed matching in the family of rejection sampling schemes where the matching probability is close to PML. We demonstrate the practical significance of our approach over prior works by applying it to distributed compression. The effectiveness of our proposed scheme is validated through experiments involving synthetic Gaussian sources and distributed image compression using the MNIST dataset.
Introduction
One-shot channel simulation is a task of efficiently compressing finite collection of noisy samples. Specifically, this can be described as two-party communication problem where the encoder obtains sample X ~ Px and wants to transmit its noisy version Y Prix to the decoder, with the communication efficiency measured by the coding cost R (bits/sample), see Figure (left). Since the conditional distribution Py x be designed to target different objectives, channel simulation a generalized version of lossy compression. As a result, it has been widely adopted various machine learning tasks such as data/model compression II 4 46 19), differential privacy [37 42) and federated learning [23 While much of the prior work has focused on the point-to-pon poinn setting described above, recent research has extended channel simulation techniques more general distributed compression scenarios [27] 35]. These scenarios often follow canonical setup, shown in Figure [ (middle, right), in which the encoder (party A) and the decoder (party B) each aim to generate samples YA and YR, respectively, according to their own target distributions Pa and PB. using shared source of randomness W. Although their sampling goals may differ, the selection processes are coupled through W, resulting a non-negligible probability that both parties select the same output. We refer this quantity as the distributed matching probability, which can be leveraged to reduce communication overhead in distributed coding schemes. For example, in the Wyner-Ziv setup 45), where the decoder has access to side information unavailable to the encoder, this framework enables the design of efficient ohe- compression protocols B5
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Currently, Poisson Monte Carlo (PMC) [22 and importance sampling (IS) are the two main Monte Carlo methods being applied across both scenarios (29]. Particularly, the Poisson Functional Rep- resentation Lemma (PFRI) 128 provides near-optimal coding cost for channel simulation. The Poisson Matching Lemma (PML.) 27 was later developed for distributed matching scenarios, en- abling the analysis of achievable error rates in various compression settings. However, PMC requires an infinite number of proposals, which can cause certain issues involving termination of samples in a practical scenario when the density functions, typically P are estimated via machine learning. IS- based approaches, including the importance matching lemma (IML) for distributed compression [35, bypass this issue by limiting the number of proposals in W to be finite. Yet, the output distribution from IS is biased [19 [1), and thus not favorable in certain applications. It is hence interesting to see whether Monte Carlo scheme and coding method can be developed to handle both scenarios without compromising sample quality or termination guarantees.
This work studies rejection sampling schemes and its applicability to these two scenarios. We begin by revisiting and improving the coding efficiency of standard rejection sampling (RS) in channel simulation [40 41]. In particular, we introduce new coding scheme based on sorting that attains a near-optimal coding cost, extending the prior achievability result by Braverman and Garg [5) for discrete distributions to broader settings, while employing distinct mechanism. However, our analysis also suggests that the distributed matching probabilities of both RS and its adaptive variant, namely greedy rejection sampling (14) are lower than that of the PML, making them less suitable for distributed compression. Interestingly. we find that by combining RS with IS-a technique known Ensemble Rejection Sampling (ERS) [9] [n] can improve the distributed matching probability without degrading the sample quality. We demonstrate, with provable guarantees, that ERS retains efficient coding performance in channel simulation and can be naturally extended to distributed compression settings where the target distribution pe must be learned using machine learning, typically encountered in nigh-dimenssonal data scenarios.
In summary, our contribution is as follows:
1. We propose a new compression method for RS that achieves a coding cost near the theoretical optimum. However we also argue that RS and its variant GRS do not achieve competitive performance in distributed matching.
2. We analyze ERS and show that it achieves competitive performance in distributed matching compared to PML and IML, while maintaining a coding cost close to the theoretical optimum in channel simulation.
3. We propose a practical distributed compression scheme based on ERS, supported by theo- retical guarantees. We demonstrate the benefits of our approach through experiments on synthetic Gaussian sources and the MNIST image dataset.
Finally, note that the term distributed matching in this paper encompasses settings that differ across communities. Without communication, aligns with the problem of correlated sampling 3 in theoretical computer science, while classical coupling does not capture scenarios with limited communication. To stay consistent with the setups in Li and Anantharam [7], we use distributed matching refer these scenarios, to be discussed in Section 3.2
Related Work
Channel Simulation. Our work introduces novel channel simulation algorithm based on standard RS and ERS [9] Our results enhance the coding efficiency compared to prior works [17 41 40) for standard RS and extend the best-known results for RS [5) continuous settings. A related and more widely studied scheme in channel simulation is greedy rejection sampling (GRS), which can achieve a near-optimal coding cost. However, GRS is also more computationally intensive when applied to continuous distributions [14] [8 [6] as it requires iteratively evaluating complex and potentially intractable integral. Our work studies ERS, the generalized version of standard RS, and shows a new coding scheme to achieve near-optimal bound for a continuous alphabet. The ERS based algorithm can be considered as an extension of the IS-based method for exact sampling setting [35] 41 and serves as a complementary approach to existing exact algorithms, such as the PFRL [28 and its
faster variants 12 15| 21 Finally, there exist other channel simulation methods, though these are
restricted to specific distribution classes [I 24 39

---

Channel Sinvlation: [[([M)]
Distributed Matching
Distributed Matching (witt Communicationl
[without Communicction!!
Shared Randomness W
Shared Randomness W
Shared Randomness W
Encoder f (Party
Decoder g (Party
Encoder f (Party
Decoder (Party
Encoder f (Party
Decoder 9 (Party
M (o,
X ---~0 Px(()
Y- Pyx(-la)
V4 PPL)
Y/ ~ PP(.)
X (xP-)) YA- PP(.)
Vo
Figure 1: Left: Channel simulation setup. Middle: Distributed matching without communication. Right: Distributed matching with communication where the decoder's 's input Z X2 represents side information and/or messages from the encoder.
Distributed Compression. In distributed compression, one requires a generalized form of channel simulation, i.c. distributed matching, to reduce the coding cost, with current approaches include PML (27 and IML (35,, as discussed earlier. Prior work has examined the matching probability of standard RS in various settings, primarily for discrete alphabets 88 (3).. Our method builds ERS,
a new RS-based scheme, and shows that its performance in distributed matching is comparable to PML, enabling practical applications in distributed compression. Other information-theoreiic [30 38 43) and quantization-basee approaches [31 47 for this problem are generally impractical for implementation. Meanwhile, recent work has explored neural networks-based solutions 33
with some provides empirical evidence that neural networks can learn to perform binning
[3]
3 Problem Setup
3.1 Channel Simulation
Let (X, Y) E X' x y be pair of random variables with joint distribution Px,,, with Px and py are their respective marginal distributions. In this setup, see Figure [ (left). the encoder observes X ==a ~ (-) and wants to communicate sample Y ~ (-]x to the decoder, with the coding cost of (bits/sample). Given that both parties share the source common randomness W E W independent of X, we define f and g to be the encoder and decoder mapping as follow:
f: x W - M; g:MxW
where the encoder message M M = {0. 13" is binary string with length E(M) and R == Here, we require that the decoder's 's output follows Prix (.1x), i.c., Y =7=gff (x, W). W) ~ Py)x(-
Depending on the encoding and decoding function f and g. the specification of what W includes varies. A general requirement for a channel simulation scheme to be efficient is that R satisfies:
R S ((; + log(!(X; Y) + 02) + c3:
(1)
where T(X; Y) is the mutual information between X and Y and the theoretical optimal solution attainable in the asymptotic (i.e., infinite blocklength) setting (7). Different techniques may produce slightly different coding costs, characterized by the positive constants C1, C2. and og [18 26), but any approach that fails to achieve the leading term ((xY)) )) is generally considered inefficient.
3.2 Distributed Matching
We describe the two setups, with and without communication. Both setups consider two parties: A (the encoder) and B (the decoder) sharing a source of common randomness W e W.
3.2.1 Distributed Matching Without Communication
In this setup, visualized in Figure (middle), each party A and B aim to generate samples YA and YB from their respective distributions Pa and Pf which are locally available to each party, by selecting values from W. Each party constructs their respective mapping and g follows:
f:W W + y, W + + 3,
with the requirement that YA = /(W) ~ P and YB = (W) ~ P Following prior work on PML [27], we are interested in the lower bound of the conditional probability that both parties select
3

---

the same value, given that Y4 = y, with the following form:
Pr(Ya YB YA y) (V)
(2)
where in the case of PML, we have (XP (1 + P(W))/P(()) For IML,
(y)) where e - as the number of proposals increases.
3.2.2 Distributed Matching With Communication
In practice, communication from the encoder to the decoder is allowed to improve the matching probability. Also, the target distributions each end may depend their respective local inputs. Specifically, let (X, Y Z) E X' x y x Z be a triplet of random variables with joint distribution Px,YZ.. We first define the following mappings, also see Figure (right):
f:Xx W >, g: g:WxZ
where the protocol is as follows:
1. Encoder (party A): given x Px independent of W. the encoder sets its target function p = (- and selects sample YA = far W) Pg.
2. Given X I, YA y, generate Z some noisy version of Ya). Note that the Markov chain Z (X, YA) W holds.
P (- x. y). which can be thought as
3. Decoder (party B): having access Z=z, sets its target distribution P (-) = Priz(-12)) where Pyiz can be arbitrary. It then queries a sample YB =(W, 2) from the source W.
The constraint YB P is not necessarily satisfied, but this not required this setting (27. where the goal is to ensure the decoder selects the same value as the encoder with high probability. As in the case without communication, we are interested establishing the bound with the following form:
Pr(Ya = YB YA = v. =))
P (v)),
where for PML and IML, I(PA (v), PV) (v)) also follows the form discussed in Section 3.2.1
Remark 3.1. Since 2-(X, forms Markov chain and is input to the decoder, the communication in this setting happens by designing P22x,Y' y ( xx,y) include the encoder message. Finally, this setup generalizes the no- oo-communication one by setting (X, Z) to fixed constants.
3.3 Bounding Condition
In this work, we often consider the ratio (y) (y) to be bounded for y. where Py; Qy are the target and proposal distribution, respectively. We formalize this in Definition 3.2
Definition 3.2. A pair of distributions (Py Qr) is said to satisfy bounding condition with constant w 2 if max, Py (y)/ (v) S w. Furthermore, let (X, Y) ~ Px,Y, a triplet (Px, Qy) satisfics an extended bounding condition with constant w 2 1 max Py|x (xlx)//)//Q / (v) S w.
We note that the extended condition is practically satisfied when (Prix=x: Qr) satisfies the bounding condition for every x, and Px has bounded support.
4 Rejection Sampling
We review the existing coding scheme standard RS and introduce a new technique that achieves a bound comparable (I). We then discuss results matching probability bounds for RS and GRS.
Sample Selection. We define the common randomness W = (UU,, Yi), (U2, Y2),... .. }, where each U: Lid. u(00 1) and each Y: iid. Py, and require that the triplet (Px, Py|x, Py) satisfies the extended bounding condition in Definition 3.2 with w. Given X=r, the encoder picks the first index K where (Yx 2)) obtaining Yx-PPyxx(Jlr
UKS
(Yx)
Runtime-Basee Coding. This approach encodes the sample following the entropy of H(K). Since each individual sample Y, has the acceptance probability Pr Pr(Accept) w- we can compress K

---

Group 5kip
Group #2: Send
4.6
Y1
22
Y,
Y
Ys
Yo
Y1
Y,
Yg Y10
W
3.4
U1
U2
U
U4
U.
U6
U1
Us
U,
Uw
0..5
2 2.2
Upper-Bout Boand
Empiriosl
Rejected Samples
Accepted Samples
Sort
Unm $ U+o) s Uni3) s Un0
1.2
1.01
Dxo Dxx((rpc((<))1 PP())
1.8
2.3
2.8
Figure 2: Left: Visualization of our Sorting Method for Standard RS. Right: Empirical results comparing L[] and BBllo(( K)) with their associated theoretical upper-bound across different target distribution. We use Py(() = (00 1.0) and Pyxx (-|xr = (1100, o²) where o² E (.1].
with coding cost of R S H[K]+ this reason, GRS is often preferred, but with practical limitations as discussed in Section 2
S log(w) + 2, which inefficient compared to ((: For
Our Approach. Unlike the previous method, where the coding of K is independent of W, we aim to design a scheme that leverages the availability of W at both parties, thereby reducing the coding cost R through the conditional entropy H [ W). Our Sorting Method operates on this idea, where instead of sending K, we send the rank of UK within a subset in W. Assume that the encoder and decoder agree on the value of w prior communication, we first collect every [w] proposals into one group, [-J, [-] are floor and ceil functions respectively). We encode two messages: one for the group index L and one for the rank K of the selected UK within that group, in particular:
1. Encoding L: The encoder sends the ceiling L = K i.e. L = 2 in Figure (left). The
-
decoder then knows (L [)[ + 1 K s L [[w], i.e. K is in group L.
2. Encoding K: The encoder and decoder sort the list of U, for (L - 1)] +1 w]:
Un(1) Un(2) ... S (n((w)
where (.)) maps the sorted indices with the original ones. The encoder sends the rank of UK within this list, i.e. sends the value R such that K (K), which the decoder uses to retrieve Yx accordingly. This corresponds K- Figure (left).
Coding Cost. In terms of the coding cost at each step, i.e., Ellog L.] and IE [log R1. we have:
Ellog L] < 1 bit, Ellog K] s DRr (1x)) (.)) log(e) bits,
(4)
where Figure (right) shows the empirical results verifying the bounds. The proof for these bounds shown in Appendix B.2, We then perform entropy coding for each message separately using Zipf's distribution and prefix-free coding. Proposition shows their overall coding cost:
Proposition 4.1. Given (X, Y) Px,y and K defined as above. Then we have:
R s ((X;)) + log(T +)+
(5)
Proof: See Appendix 4.4
Note that the approach of Braverman and Garg (5] for discrete distributions can be extended to the continuous case, included Appendix (. for completeness. Our sorting mechanism fundamentally different and can be extended to the more general ERS framework, where incorporating the method of Braverman and Garg is nontrivial
Distributed Matching, In distributed matching setups in Section 3.2 where both parties use standard RS select samples from their respective distributions, we show in Appendix C.2 that RS perfor- mance is not as strong compared to PML and IML. For GRS, we provide an analysis via non-trive non-trivial example in Appendix D.2, where we managed to construct target and proposal distributions such that Pr Pr(YA=Y, B YA=y) + 0.0, even when P4 (y) = P (v). In contrast, this probability is greater than 1/2 for PML, thus concluding that RS and GRS are less efficient compared to PML and IML.
At the time of acceptance, we became aware of a concurrent work by 13 proposing a similar approach; however, their formulation requires communicating additional information, resulting in slightly suboptimal coding cost compared to ours.
5

---

Ensemble Rejection Sampling
We show that E exact sampling scheme that combine RS with IS, can improve the matching probability and maintain a coding cost close to the theoretical optimum in channel simulation.
5.1 Background
Setup and Definitions. We begin by defining the common randomness W, which includes a set of exponential random variables employ the Gumbel-Max trick for IS [35 41, i.e.:
W [(B1, U1) (B2, U2),..), where U, U(0,1)
(6)
B, = ((Yn Sa), (Y2,, S2). ..., (YiN, S,N),, where Yy ~ Pr), ~ Exp(1), (7) where we refer to each B; as a batch. A selected sample YK from W is defined by two indices: the batch index K₁ and the local index in Bk, denoted as K2. Its global index within W is K, where K = (N - K + K2 and we write YK- _ YK,
Sample Selection. Consider the target distribution (r|x(- for each batch B; E W, the ERS algorithm selects candidate index Keand via Gumbel-max IS and decides to accept/reject Y Yygand based on U. This process ensures that the accepted Pxxxyxx (-|az) and denoted for simplicity as: K ERS(W; Py x==, Pr),
where the procedure is shown in Figure (top, left) and Algorithm Din Appendix E. This procedure assumes the bounding condition holds for (Pylx (y|z), Py (v)) with W. The target and proposal distributions be any, e.g., replacing Py with Qr, long the bounding condition holds.
Remark 5.1. Since the accept/reject operation happens on the whole batch Bü, we define the batch average acceptance probability A (see Appendix E. where A + 1.0 as N - Do and N NA -1 as the average number of proposals (or runtime) required for ERS.
5.2 Channel Simulation with ERS
For N 1, ERS becomes the standard RS and thus achieves the coding cost shown in Proposition 4.1
When N - oo, we have the batch acceptance probability A + 1.0, meaning that we mostly accept the first batch and thus achieve the coding cost of Gumbel-max IS schemes [35] which follows (I. This section presents the result for general N, which is more challenging establish discussed below. We assume the extended bounding condition in Definition 3.2 holds for (Px. Pylx,Py)
Encoding Scheme. We view the selection of K₃ as rejection sampling process on whole batch (see Appendix E. and apply the Sorting Method to encode K₁. Specifically, we collect every |A-1 batches into one group of batches, send the group index and the rank of Uk, within this group. For the local index K2, we use the Gumbel-Max Coding approach (35). This process visualized in Figure 3 (middle), detailed as follow:
Encoding K₁: we represent i by two messages L and Ki Here, L the group of batches index K1 belongs to and K₁ is the rank UK, within this tth group, i.c., we sort the list:
Ue( S U@(2) ... < Us( (a())- and send the rank K of UK, i.e. ((Ki) = Ki. Encoding K2: We first sort the exponential random variables within the selected batch K1, i.e. Sa(1) S Sxx2)) _... S*)N) and send the rank R₂ of SK2, i.e. T (K2)) Kg-
Coding Cost. We outline the main results for the coding costs, details in Appendix E Specifically: E[log T.] < 1 bit, K. = Bllog Ki] + Bllog K2) < Dxz ( Py (+I)) log(e)++ +-3 bits, (9)
where the second bound is of the core technical contributions of this work. We empirically validate the bound on K. in Figure 3 Proposition 5.2 shows the overall coding cost for K:
Proposition 5.2. Given (X Px, and K defined as above. For any batch size N, we have: R < I(X:)) 2log(I + 12,
(10)
Proof. See Appendix E.4
Remark 5.3. The upper-bound 10 is expected to be conservative, as evidenced by the evaluation of aciual rates in Figure (right). We further demonstrate the improvements in our proposed method over the boselines in the distributed compression application, be elaborated upon in the subsequent discussion.

---

ERS Sample & Batch Selection Procedure
ERS Coding Scheme for Channel Simulacion
Shee Sall
Elgt Ring/Ro
Batch Bi
30 Kill
UppasBoool
Group Batchee
Culux Ciel
Select: Riadd argmin
Sa Pl PSePat
orgmii Si An
2(Yupr)
58 Pagl 1000
Aucept/Reject: Us S.
Sort Codling Batch Index Ki
Chiiig Catt
where: ((aax)
Edu Au
Gumbel-Max Codlng Local Index K2
2(Yas, K, 2(Yaa)) + Auge
Rejected Batch
Aocepted Batch
Dutch Blso N
Figure 3: Left: Illustration of ERS Selection Method. Middle:
Coding scheme for channel simulation. Right: Empirical results on the coding cost of K , K2 and their theoretical upper-bound (in bits). Both figures use (y)) 1.0), where the first figure sets N = 32 and varies Py|x ((.00=
with o² E [0.1, 5 10 3, The second one fixes 0²=10-3 while varying N.
5.3 Distributed Matching Probabilities
We consider the communication setup described in Section 3.2.2
which generalizes the no- communication one in Section 3.2.1. see Remark 3.1 We use subscripts to distinguish the in- dices selected by each party, e.g.. KA and KB denote the global indices chosen by the encoder (party A) and decoder (party B), respectively. Recall that the encoder observes X X=z~Px and sets P (- I)), while the decoder observes Z= and sets =Prrz 22), not necessarily follow (- z). The target distributions PA. Pž. and the proposal distribution Qy in W must satisfy the bounding conditions outlined in Section 3.3 for the ratio pairs (PA, Qy) and (P Qy). Each party then uses ERS to select their indices:
kA ERS(W; PA, Qy), KB PE:S(W:P&... Qr),
(11)
where the function ERS(.) is defined in 8 and set Yς=YKı and Yg=Yk₂ the values reported by each party. Proposition sh.sshwws a bound on the matching probability in this setting. The bound for the no-communication
naturally follows with appropriate modification, see Appendix F2
Proposition 5.4. Let KA, KB. . P and PΦ defined as above. For N 2 2, have:
(L+A (
(v) (1 (1+ (((()))))) Pf
Pr(YA= YB y. =2)
2
(12)
where 11 (N) and (N) defined in Appendix F:5 are decay coefficients depending on the distributions where p1 (N), 1u1 (N) 0 as N - with rate Nnder mild assumptions the distributions
are
(.), PP( (.) and (.).
Proof: See Appendix
7.6
ERS with Batch Index Communication. In practice, Pf(v) (y) is often learned via deep learning, making difficult to obtain the upper bound for P (v)/Qr (v), thus preventing a well-defined select condition. A practical workaround is for the encoder transmit the selected batch index Ki,A the decoder, limiting the search space to a finite subset. This aligns with Section 3.2.2 by incorporating K1,4 into the construction of YA. Z, and YB. Its matching bound, Appendix G is similar to Proposition 5.4, but with different decaying coefficients.
Remark 5.5. Since the decay coefficients (N) (ar)),(h,))) (N) - 0.0 with the rate N-1, for any small c one can choose N > No(c) such that p2,
(2() c.
Empirical Results. Figure 4 (left, middle) validates and compares ERS matching probability (with and without batch communication) with PML and IML, where we see both ERS approaches converge to PML performance. For the same average number of proposals N Figure (middle) demonstrates that ERS (with batch index communication) achieves consistently higher matching probabilities than unbiased sample distribution. For completeness, Figure (right) shows
IS, while maintaining the bias of IS can remain high even when the number of proposals sufficiently large, i.e. 4w. We discuss the overhead of the batch index in Section 5.3. on application to distributed compression.
7

---

1.0
FALL Munding Prolehiily
1.0
FAIL Mandhin Pholebiii
Cuonc outh
Matching Probebillt
RS Mastiing Prolubiltt
Matching Probsbbilitt
RS Manriing Pestubiiity
Batientol o'
0.8
ERS Fonch Communccation
8.8
ERS- Comminattio
IML
100
0.6
6.6
0.4
0.4
1
100
200
0
01.6
1.
150
200
0.6
100
200
Batch Size N
Average Number of Proposale 2V"
Average Number of Propusals N
Figure 4: (Best viewed in color) We set Qy=N(o, 100), PA=N(0..50077 and Pf=N(- 0.7). Left: Matching probabilities versus the batch size N. Middle: Matching probabilities versus the average number of proposals where the red and black dotted lines correspond to the batch sizes w and 4w shown the left figure. Right: Sample quality of IS, measured by the estimated variance o².
5.3.1 Lossy Compression with Side Information
We apply our matching result with batch index communication to the Wyner-Ziv distributed compres- sion setting [5). where the encoder observes X X=z~~Px and the decoder has access to correlated side information X'~ "> (-1ar) unavailable to the encoder. Let Py (-lar denote the target distribution that the encoder aims to simulate, which, together with X', induces the joint distribution Px.x,,'. For any integer V>5 and (,, 1), we set Yiz=(Y') Vij) in batch B, within W where:
Yg ~ (-) (i.e., the ideal output), Vig ~ Uni (i.e., the hash value for index j)
The main idea is, after selecting the index K^ where YK, "xx~Pr'X the encoder sends its hash VKA along with the batch index K1,4 to the decoder. The decoder, on the other hand, aims to infer Kaa by using the posterior Py"xx'='' The message (VKA- K1,A) from the encoder will further reduce the decoder's 's search space within W and improves the matching probability (details in Appendix H) Proposition 5.6 provides bound on the probability the decoder outputs a wrong index:
Proposition 5.6. Fix any > 0 and let (Px, Pyqxx Qyy) satisfies the extended bounding condition with w. for N 2 maxx(Nolc), where Nolc) is defined in Remark 5.5 we have:
Pr(Yka + Vkn) Ex 1
(1 (1 (1 1200
(13)
where iy (W';x) = log Py (z) -od))loog Py-(y/) is the information density. The coding cost is log(V) + r where r the coding cost of sending the selected batch index KT,A and S bits.
Proof: See Appendix[H]
Remark 5.7. We can reduce the overhead r Proposition b.6 jointly compressing n i.i.d. samples, Le., to 4/n per sample. This also improves the matching probability in practice (see Appendix H
6 Experiments
We study the performance of ERS in the Wyner-Ziv distributed compression setting on synthetic Gaussian sources and MNIST dataset. All experiments are conducted on a single NVIDIA RTX A-4500. We use the batch communication version ERS and encode the index with unary coding. Finally, we the following formula from IS literature [6] as starting point for choosing the batch size: N=22x(Dxu(PPpxx (Iee) Q.)1+ where t24 often gives A20.5, resulting in small overhead
6.1 Synthetic Gaussian Sources
We study and compare the performance of ERS, IML and PML in the Gaussian setting. Let X ~ *N xx) with ox = 1 and is truncated within the range [-2, 2] and the side information NNO, xx and a xxxx = 0.01. The proposal and target distributions are (r- = (O0, of.), (11x) N(xz o (rop))())==) N' fo/ - where - o to &z =o to + x.xx and o is a fixed variance corresponding to the desired distortion level set by the encoder. The expression for Propx-(1aa"" is approximation derived from
X' X + where
8

---

-100
11.51B
Distorion (dB)
Distortton (d8)
N
Target dB
1.0e6
-21.5dB
22.0
IML
22500
1.1e6
-22dB
115-1 54b
-225
ERS
256B
1.5e6
-22.5dB
PME (MM
XXX.1)
1.6e6
-23dB
(Bits)
Figure 5: Left: Comparison of RD performance between different matching results for the Gaussian setting when targeting 23dB distortion (black dotted line), with the average number of proposals N E {1.le6, 1.6e6]. Right: RD curves of different methods. Each group targets the same distortion levels and uses the same average number of proposals N* for ERS and IMI., shown in the right table.
the posterior distribution assuming X is unbounded (i.e., not truncated). We jointly compress i.i.d. samples to improve rate-distortion (RD) performance and average the result over 10 runs.
Figure 5 (left) investigates the RD tradeoff between ERS and IML with similar number of proposals (on average) N* while targeting a distortion level of 23dB i.e. x We observe that ERS outperforms IML distortion regimes close to the target level, i.e. below - -22.6IB as the rate increases, since IML samples are inherently biased. This bias also causes IMI., with N 1.6c to be less effective than ERS, with N = 1.1c for a distortion regime lower than -22.8BB, despite having samples. Also, the batch index conveys information that helps improve the matching probability, similar to Figure 4 (middle). compensating for the overhead. Overall, for appropriately chosen N*, ERS is more effective than IML achieving low distortion levels while remaining competitive compared to PML, which is unbiased and requires no extra overhead.
In Figure (right), plot the RD tradcoff different target distortion levels. We compare the distortion achieved by different methods at the rate where ERS reaches distortion within approximately 0.2 dB of the target. Again, for appropriately chosen batch size N and rate. ERS outperforms IML due to the inherent bias in importance sampling, and achieves performance close to that of PML. Note that PML does not generalize to practical setting when P is estimated via machine learning as the decoder cannot determine the number of samples upfront. In general, all three approaches outperform the asymptotic baseline [(;; Y) in which there no side information. Finally, standard RS achieves 17 dB at 10 bits when targeting -23 dB, falling outside the plotted range.
6.2 Distributed Image Compression
We apply our method in the task of distributed image compression dataset Following the setup in [35), the side information is the cropped bottom-left quadrant of the image and the source is the remaining. To reduce the complexity caused by high dimen- sionality, we use an encoder neural network to project the data into a 3D embedding space. This vector and the side information are input into a decoder network to output the reconstruction X, and the process is trained end-to-end under the B- BAV framework. For each input X x, we set the target distribution "y'xx-11x) N ((((z), (z))) where p(-), (-) are the outputs of the 3-VAE network. Since Py'px is unknown, we employ a neural contrastive estimator [22] learn the ratio between Pyzpx x (y' 3/Qy>(// from data, where Qy 1). Since the upperbound of this ratio is unknown, PML cannot be applied [41]. Models and training details are in Appendix [ [
44 33
with the MNIST
Extending the scope of the previous experiment, we study the interaction between matching schemes and feedback mechanisms for error correction, introduced previous IML work (35). Here, the decoder returns its retrieved index to the encoder, which then confirms corrects it with the cost of 1 plus Log(N/V) for ERS and log(Ni /V) for IML, see Appendix This is relevant when aiming to mitigate mismatching errors or to generate samples that closely follow the encoder's 's target distribution, as in applications such as differential privacy. Since IML produces biased samples, we reduce this bias by setting the number of proposals the maximum feasible value in simulation system, i.e., Ni = 26 ensuring it exceeds the ones used by ERS, denoted N in this experiment.
We train four models, each targeting a different pixel distortion level, and compare their performance in Figure 6 where two samples are compressed jointly. With feedback, ERS consistently outperforms IML in both embedding and pixel domains. This is because the feedback scheme in IML incurs

---

ERS
IML
ERS
(Feedback)
IML (Foedback)
NDIC
Target Pixel
Embedding MSF
10.6
8.070
ERS
Distortion
MSE
8.063
1.5 2
0.066
0.4
1.2 x 2
0.063
0,060
1.2 2
0.061
1.2 x 2
0.058
0.2
8.063
Rate (Bits)
Rate (Bits)
Figure MNIST Rate-distortion comparison for pixels, i.e. || X12 and embeddings domain, i.e.
[|xxX)) l between ERS and IML. Identical markers (from top to bottom) indicate the same target models, with the target distortion levels corresponding to those achieved using feedback.
higher return message due the large NiML: while still introducing slight bias in its output samples. In contrast, ERS operates with a smaller hatch size N, significantly reducing the correction message size without compromising the sample quality. Without feedback, under distortion regime close to the target level, ERS outperforms IML for reasons discussed in the Gaussian experiment, though the performance gap smaller. We include NDIC results -33-a specialized deep learning approach that targets optimal RD performance. On the other hand, our method operates on probabilistic matching nature and can accommodate scenarios with distributional constraints.
Conclusion
This work explores the use of the RS-based family for channel simulation and distributed compression. We focus on ERS where we develop new efficient coding scheme for channel simulation and derive a performance bound for distributed compression that is comparable to PML (27). We validate our theoretical results on both synthetic and image datasets, showing their advantages and adaptability across various setups, including feedback-based error correction schemes. From these results, possible future directions include improving the current runtime efficieney-which is -- incorporating accelcration techniques such as space partitioning [21] or importance sampling methods like Multiple IS | well extending the distributed compression setup to incorporate differential privacy.
Acknowledgment
Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute www.wctoriistiiteaa//aartttsiiii
10

---

References
[1] Eirikur Agustsson and Lucas Theis. Universally quantized neural compression. Advances in neural information processing systems, 33:12367-12376 2020.
[2] Johannes Ballé, David Minnen, Saurabh Singh, Sung Jin Hwang, and Nick Johnston. Variational image compression with scale hyperprior. arXiv preprint arXiv:/802.01 1802.01422. 2018.
[3] Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L Rivest, and Madhu Sudan. Optimality of correlated sampling strategies. arXiv preprint arXiv: 16/2.01041, 2016.
[4] Yochai Blau and Tomer Michaeli. Rethinking lossy compression: The rale-diistottion-perrppioo tradeoff. In International Conference on Machine Learning, pages 675-685, PMLR, 2019.
[5] Mark Braverman and Ankit Garg. Public private coin in bounded-round information. In International Colloquium on Automata, Languages, and Programming, pages 502-513. Springer, 2014.
[6] Sourav Chatterjee and Persi Diaconis. The sample size required in importance sampling. The Annals of Applied Probubility, 109-)1109 2018.
[7] Paul Cuff. Distributed channel synthesis. IEEE Trunsuctions Information Theory, 59(11) 1): 7071-7096, 2013.
[8] Majid Daliri, Christopher Musco, and Ananda Theertha Suresh. Coupling without communica- tion and drafter-invariant speculative decoding. arXiv preprint arXiv:2408.07978, 2024.
[9] George Deligiannidis, Arnaud Doucet, and Sylvain Rubenthaler. Ensemble rejection sampling. arXiv preprint arXiv:2001.09/6 2020.
[10] George Deligiannidis, Pierre E Jacob, El Mahdi Khribch, and Guanyang Wang. On importance sampling and independent metropolis-hastings with an unbounded weight function. arXiv preprint arXiv:2411.09511 2024.
[11] Víctor Elvira, Luca Martino, David Luengo, and Mónica F Bugallo. Generalized multiple importance sampling. 2019.
[12] Gergely Flamich. Greedy poisson rejection sampling. Advances Neural Information Process- ing Systems,
2023.
[13] Gergely Flamich. Data Compression with Relative Entropy Coding. PhD thesis, University of Cambridge (United Kingdom), 2024.
[14] Gergely Flamich and Lucas Theis. Adaptive greedy rejection sampling. arXiv:2304.1044 10407, 2023.
arXiv preprint
[15] Gergely Flamich, Stratis Markou, and José Miguel Hernández-Lobato Fast relative entropy coding with a coding. In International Conference on Machine Learning, pages 6548 6548-6577. 6577. PMLR, 2022.
[16] Gergely Flamich, Stratis Markou, and José Miguel Hernández-Lobato. Faster relative entropy coding with greedy rejection coding, Advances in Neural Information Processing Systems, 36: 50558-50569, 2023.
[17] Gergely Flamich, Sharang M Sriramu, and Aaron B Wagner. The redundancy of non-singular channel simulation. arXiv preprint arXiv:2501.1400 14053, 2025.
[18] Prahladh Harsha, Rahul Jain, David McAllester, and Jaikumar Radhakrishnan. The communica- tion complexity of correlation. In Twenty-Second Annual IEEE Conference on Computational Complexity (CCC*07), pages 10-23. IEEE, 2007.
[19] Marton Havasi, Robert Peharz, and José Miguel Heráández-Lobato. Minimal random code learning: Getting bits back from compressed model parameters. In 7th International Conference on Learning Representations, ICLR 2019, 2019.

---

[20] Jiajun He, Gergely Flamich, Zongyu Guo, and José Miguel Hernández- Recombiner: Robust and enhanced compression with bayesian implicit neural representations. arXiv preprint arXiv:2309.1710 2023.
[21] Jiajun He, Gergely Flamich, and José Miguel Hernández-Lobato. Accelerating relative entropy coding with space partitioning. Advances in Neural Information Processing Systems, 37: 75791-75828, 2024.
[22] Joeri Hermans, Volodimir Begy, and Gilles Louppe. Likelihood free meme with amortized approximate ratio estimators. In International conference on machine learning, pages 4239- 4248. PMLR, 2020.
[23] Berivan Isik, Francesco Pase, Deniz Gunduz, Sanmi Koyejo, Tsachy Weissman, and Michele Zorzi. Adaptive compression federated learning via side information. In International Conference on Artificial Intelligence and Statistics, pages 487-495. PMLR, 2024.
[24] Szymon Kobus, Lucas Theis, and Deniz Gündüz. Gaussian channel simulation with rotated dithered quantization. In 2024 IEEE International Symposium on Information Theory (ISIT), pages 1907-1912. IEFE, 2024.
[25] Yann Lecun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 1):2278-22333 2324, 1998.
[26] Cheuk Ting Li. Pointwise redundancy in one-shot lossy compression via poisson functional representation. International Zurich Seminar on Informaiion and Communication (IZS 2024). Proceedings, pages 28 29. ETH Zürich, 2024.
[27] Cheuk Ting Li and Venkat Anantharam. A unified framework for one-shot achievability via the poisson matching lemma. IEEE Transactions on Information Theory, 6765)2222--2651, 2021.
[28] Cheuk Ting Li and Abbas El Gamal. Strong functional representation lemma and applications to coding theorems. IEEE Transactions on Information Theory, (6616))696776678 2018.
[29] Cheuk Ting Li et al. Channel simulation: Theory and applications to lossy compression and differential privacy. Foundations and Trends@ in Communications and Information Theory, 21 (6):847-1106, 2024.
[30] Jingbo Liu, Paul Cuff. and Sergio Verdú. One-shot mutual covering lemma and marton's 's inner bound with a common message. In 2015 IEEE International Symposium on Information Theory (ISIT), pages 1457-1461. IEEE, 2015.
[31] Zhixin Liu, Samuel Cheng, Angelos D Liveris, and Zixiang Xiong. Slepian-wolf coded nested lattice quantization for wyner-ziv coding: High-rate performance analysis and code design. IEEE Transactions on Information Theory, 32(10):4358-433 2006.
[32] Chris J Maddison. A poisson process model for monte carlo. Perturbation, Optimization, and Statistics, pages 193-232, 2016
[33] Nitish Mital, Ezgi Özyılkan, Ali Garjani, and Deniz Gündüz. Neural distributed image com- pression using common information. In 2022 Data Compression Conference (DCC), pages 182-191. IEBE, 2022.
[34] Ezgi Ozyilkan, Johannes Ballé, and Elza Erkip. Learned wyner-ziv compressors recover binning. arXiv preprint 2305.000000 2023.
[35] Buu Phan, Ashish Khisti, and Christos Louizos. Importance matching lemma for lossy compres- sion with side information. In International Conference Artificial Intelligence and Statistics, pages 1387-1395. PMLR, 2024.
[36] Anup Rao and Amir Ychudayoff. Communication Complexity: and Applications. Cambridge University Press, 2020.
[37] Abhin Shah, Wei-Ning Chen, Johannes Balle, Peter Kairouz, and Lucas Theis. Optimal compression locally differentially private mechanisms. In International Conference on Artificial Intelligence and Statistics, pages 7680-7723. PMLR, 2022.
12

---

[38] Eva C Song, Paul Cuff, and H Vincent Poor. The likelihood encoder for lossy compression. IEEE Transactions on Information Theory, 62(4):1836- 2016.
[39] Sharang Sriramu, Rochelle Barsz, Elizabeth Polito, and Aaron Wagner. Fast channel simulation via error-correcting codes. Advances in Neural Information Processing Systems, 37:107932- 107959, 2024.
[40] Michael Steiner, Towards quantifying non-local information transfer: finite-bit non-locality. Physics Letters A, 270(5):239-25)) 244, 2000.
[41] Lucas Theis and Noureldin Y Ahmed. Algorithms for the communication of samples. In International Conference on Machine Learning, pages 21308-21322 PMLR, 2022.
[42] Aleksei Triasteyn, Matthias Reisser, and Christos Louizos. Dp-rec: Private & communication efficient federated learning. arXiv preprint arXiv:2 110e2//11,0540 1,05454, 2021.
[43] Sergio Verdú, Non-asymptotic achievability bounds in multiuser information theory. 2012 50th Annual Allerton Conference Communication, Control, and Computing (Allerton), pages 1-8. IEEE, 2012.
[44] Jay Whang, Anish Acharya, Hyeji Kim, and Alexandros Dimakis. Neural distributed source coding. arXiv preprint arXiv:2106.022 027977777 2021.
[45] Aaron Wyner and Jacob Ziv. The rate-distortion function for source coding with side information at the decoder. IEEE Transactions on information Theory, 22(1):1-10, 1976.
[46] Yiho Yang, Justus Will, and Stephan Mandt. Progressive compression with universally quantized diffusion models. In The Thirteenth International Conference on Learning Representations, 2025. URL http://ppneeeeeeeeeeeeefooooaaaa
[47] Ram Zamir and Shlomo Shamai. Nested linear/lattice codes for wyner-ziv encoding. In 1998 Information Theory Workshop (Cat. No. 98EX131), pages 92-93. IEEE, 1998.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Yes we support every claim in the abstract with proof and experimental results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See the Conclusion Section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
Every assumption is rigorously stated.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Code will be included for reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [Yes]
Justification:
Code will be available upon acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ //ippe.cc/pullic/guiii wwwiicccguie//eeeeeeeeeis CoodeSubeiiieeee ssi wsionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See the Experiment Section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Every plot is averaged for 10 different random seeds.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
16

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
See the experiment section.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We check and verify the paper follows the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper poses no such societal impacts due to its scope in compression and information theory.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper focuses on probabilistic methods and poses no such risk.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: No assets involved.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No assets involved.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/cooe/mmodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper provides theoretical studies of channel simulation and does not involve related items.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper provides theoretical studies channel simulation and does not involve related items.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
19

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [No]
Justification: No LLM usage was involved.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy (https: hattap///aarrpppeocc///offeerere for what should or should not be described.
20

---

A Runtime of ERS.
We provide analysis of ERS runtime. Let maXe,y Prix (v) (vv() and we max, Pyix (y /QQ))) where x is the target distribution and Qy is the proposal distribution. For the batch size and input æ, we have the following bound on the average batch acceptance probability Az, which we will show in Appendix E.I
N
N N
A
N
(14)
N 1+ we
1+ w
Thus, the expected number batches in ERS
1
N ++
Expected Number of Batches
(15)
which leads to the runtime, ie. the expected number of proposals as:
Expected Runtime
< N - +
(16)
A
In practice, since we typically choose N = Ow)), the expected runtime is also (ww).
B Coding Cost of Standard Rejection Sampling
For the proof, we generalize and use P(.) and Q(.) as the target and proposal distributions. This allows shorthand the notations while also generalizing the results for arbitrary distributions.
B.1 Extension of Braverman and Garg (5's Method for Continuous Setting
This method is extension of the work by Braver- man and Garg [5] to the continuous setting. The core idea is to divide the acceptance region into smaller bins, visualized in Figure Specifically, for each pair (U,, Y2) from W, we denote U, = wU;Q(Y;). The encoder selects the index K according to rejection sampling rule, which is 7 in Figure 7 It then sends the bin index of the first accepted sample, where the bin corresponds the smallest scaled region that Ük belongs to. In Figure 7 this corresponds to the or- ange region and the content of the message is 3. Then the encoder sends another message which indicates the rank of the selected sample within that bin, which 1. The decoder then accordingly. Formally, the two steps are as follow:
Propenal
Arcepedd Dipectad
Binning Scheme
Figure 7: Binning Method for RS.
Üg 1. Upon receiving T, the Binning: The encoder sends to the decoder the ceiling T = Q(xx) decoder collects the set:
ST - ( < U, TQ()))
(17)
Index Selection: The encoder locates the original chosen index K within Sr, says G. and send G to the receiver. We have Ellog G] < 1.
Binning Step. We will show the Ellog 7] < (kz()))Q) + log(e).. adapting the proof for the discrete case presented in (36). First, we note that:
Yk ~ P(), UKlYK ~ (0. (",
P(YK)
(
(18)
21

---

We then have:
ÜK Q(Yk)
E Blog 7 = E
log
(19)
UK
S EE
log
+ Q(Yk)
(20)
E log (1 + wUK)]
(21)
I [E logg (1 + wUk) [Yx]]
(22)
wQ(y)
P(2)//(w)
P(y)
log (1 + wu) du
dy (Due to
18
(23)
P(y)
wQ(
P(()\/QQu)
P(y)
P(y)
log
1+ Q du
dy
(24)
P(y)
wQ(u)
P(y)/Q(w)) P(u)
Q log(e)
P(u)
log
P(u) du
dy
(25)
P(v)
Q
P(y)) Q(v)
P(y) log
dy
Q(y) log(e)dy
(26)
DRL((IIQ) + log(e),
(27)
where we use the following results for the last inequality:
+ log(e)
log(1 + x) S log(2))
(for all -1).
(28)
x
Index Selection Step. We first show that EEG] S 2 by using recursion. We define A as an event
where the first samples is accepted, i.e. Un S P(Y) "Q(") Then, happens then we have G 1, i.e.
E[G|A] 1, since it is also the first sample in Sr.
Before proceeding to the case where A does not happen, i.e. A, we define the following random variable M = 1[1 E Sr]. i.e. M = 1 if the first proposed sample from W stays within the ceiling - ()) < U, < TQ(G) and M = otherwise.
Then have the two following recursion identities:
E G M 0] = E[G] 1+ E[
(29)
B M
For the first equality, given that the first sample U1, Y1 does not stay within Sy does not implies any information about G, since all the samples are i.i.d. For the second equality takes into account the fact that now accept the first sample (U1, Yi) and repeat the counting process. Hence, have:
A = Pr(M = ( A, M = 0] + Pr(M = I/A)EIGIA, M =
(30)
G + Pr(M = 1|
(31)
We now express E[G] follows:
E ([(A))((GAA|
(32)
= PP((A) + (I(A) + Pr(M 1(A))
(33)
Rearranging the terms, obtain:
G = 1+ Pr(M = 1,
(34)
Pr(A)
22

---

We have Pr(A) --x w- w
= =- For Pr(M = A), we have:
Pr(M = 1, A) - Pr(M 1)
(35)
Σ Pr((T - 1)Q(() s (0) (T-1))))
(36)
- 1)Q(() s (t- 1)Q(0) Pr(T t)
(37)
Σ
=
(38)
=0
(39)
Thus, we obtain E[G] < 2 and hence Ellog G| S 1.
B.2
The Sorting Method
The encoding process is follows:
Grouping: the encoder sends the ceiling [ the decoder. The decoder then knows - 1)-
< K < Lw, i.e. K is in range L. We have Ellog L] bit.
The encoder and decoder both sort the uniform random variables U, within the selected range (L - 1)[w| + 1 s i S L[w]. Let the sorted list be Uz(1) S (2(2) S S <U*((=)) where T.) is the mapping between the sorted index and the original unsorted one. The encoder sends the rank of UK within this list, i.e. sends the value K such that
Sorting:
K π (K). The decoder receive K and retrieve Yx accordingly. The coding cost for this step is DxI((P]Q) + log(e).
We provide detail analysis for each step below:
Grouping Step. Since each proposal accepted with probability w-1 this means:
Pr(K [[w]) (1 3 -- BlW]
1
(40)
2
where we will prove the RHS inequality in Appendix B.3 Hence, we have Pr(L > f) < (t) and:
E[L] Σ P)
< + +05 +...= =2
(41)
t=
Finaly, using Jensen's 's inequality, have:
Ellog L] S [og(([(]]]
(42)
Sorting Step. To bound the coding cost in step we first express E[log R] with the rule of conditional expectation as follows:
Ellog R
P(y) Elog R|YK = yydy
(43)
| P(v)
Eloog RIYK = yy UK = upP = =u|Yk = vy)du) dy (44)
Plu) (
Eloog R\YK y, UK = u) wQ(y)
P(y)
du dy.
(45)
p(y)
where the last step, P(Ux u|Yx v) = -((r) for 0 < S Pig)
P(y) is due to the acceptance wQ(x)
condition in rejection sampling. We will show in Section B.3.I that:
Elog R| y. UK = u] < log(uu + 1)
(46)
23

---

Then, combining this with Equation 44
we obtain:
Ply) w((p)
w (Q log(wu + 1)du
I flg K1
P(u)
dy
(47)
P(v)
Piyl WCQUU
(Q())
P(u)
P(u)
log
+1) du dy
(48)
P(u)
Q(v)
P(v) ( log
Q(v) - dy
(Pw))
P(v)
(49)
wQ(U) P(y)
P(()
P(y)
+1 dy
(50)
Q(y)
P(v) log [P(y) log(e)Q(())
<
dy
(51)
((v))
P(y)
000
DKL (PIQ)) + log(e)
(52)
Hence, we have E[log K] S DEL (xl()) + log(e) average.
B.3 Proof for Inequality (4
The proof for this inequality self-contained. We want to prove that for any 2 1, we have:
f(w) = -1-
(53)
Consider the behavior of fw) at every interval [n, n + 1) where E Et 2 1. Since w 2 1, the function fn( (1 - w-1)" is increasing and hence:
sup (w) (1 (1----
n2
T2
for every interval [n, n + 1). will show that sup fn(w) is decreasing for n 2 and thus we have sup f(w) supw fi(w) 2-
Consider the function g(x) we simply need to show h(()) is decreasing. Consider its first derivative:
for 2 1, E R. Let h(x) = In(g(z)) r In x then
2+1
h'(x) In
x 1
+
1
(54)
+
x x+1
since:
x +1 = in (1- )11)=
In
s
(55)
++1
+1
due to the inquality In(1 + y) < y for all y.
B.3.1
Proof for Inequality (46)
We begin by applying Jensen's 's inequality for concave function log(z):
E[og Y|YK= = y, UK = u| - log E = y, UK = u] (by Jensen's Inequality)
(56)
log E, LEIK YK y, UK L C]
(57)
Given K is within the range = and UK = u. we can express K as follows:
K = |[, < (E - 1) [w] + +1s f
(58)
()u, +1
(59)
i.c. the number of U, (plus/ for the ranking) within the range L that has value lesser than u.
24

---

We can see that the the index within the range L satisfying U, < are from the index that are either (1) rejected, i.e. index K or (2) not examined by the algorithm, i.c. index i K. The rest of this proof will show the following upperhound:
E[ Yk y, UK u, u, I. = f) S ww, for any &
(60)
For readability, we split the proof into different proof steps.
Proof Step 1: We condition on the mapped index of x(K) on the original array:
E[K U. u, L =0 c B[K| YK y, UK u, (, = ki]
(61)
E (x))
(62)
B|s(u, E) + 1 Yx = y, UK uu l, (K) = H}]
(A)
(63)
-B((K)
[[S(u,)) () YK UU u.L=L, ki] +1
(64)
[R[S (u, (, Q2 k,): Yx = -..Us UK u, I. T. (,=))
[k]
+ 1
(65)
where Q1 (u, f, S2 & k) are the number of U₂ < within the range L l that occurs before and after the selected index respectively. Specifically:
P (u, k)) HUU < u, (E 1]] + +1 i < (e- 1)| +
(66)
O2 k) = |[U < u, (C - [)]W]
dW]H
(67)
which also naturally gives S2(u, E) Ω (k) (2(
Consider S2z(u, f, k), since each proposal (Y,, U2) is i.dd distributed and the fact that k is the index of the accepted sample, for every i > K, we have:
Proof Step 2:
Pr(U, < YK= y, UK u, L e, (k) = -
=k)= Pr(U, < <)
This gives us:
El k,k) YK= = y, UK = u, L C, (K) = k] = [[w] k) Pr(U < u)
(68)
= ([W) k)u
(69)
S ([w) - k))
(70)
Pr(reject a sample)
(1w) k)uu
(71)
w-
Proof Step 3: For Ω (u, E, k). we do not have such independent property since for every sample with index < K, we know that they are rejected samples, and hence for < k:
-= = e, (R) = k) = -Pr(U, < uuY,, is rejected) Pr(U; < a | YK = y, UK = u, L
(72)
Pr(U, < u, rejected)
(73)
Pr(Y, is rejected)
Pr(U: < u)
(74)
Pr(Y, is rejected)
(75)
which gives us:
(k: 1)u
E[az(u, YK = y, Un = = L = E, (
= k] S - w-
(76)
To prove Equation 72p note that the following events are equivalent:
{Yx = UK = u, I. = E, (R) = k} = (Y= = Ux = u, Yi...-1 are rejected)
(77)
A(u,,,A)
(78)
25

---

Here, we note that Yx. Us denote the value at index &o within W, which is different from Yx, Uk. the value selected by the rejection sampler. Hence:
Pr(U, < u, YI..k-I are rejected|Y - - Uk = w)
Pr(U; < (,,A(,,,Ah)
(79)
Pr(Vi...e- are rejected Y2 y, Uk = u)
Pr(U, < u, k are rejected)
(Since (Y,, U.) are iid)
(80)
Pr(Yi... are rejected)
Pr(U; w/ is rejected),
(81)
Proof Step 4: From the above result from Step 2 and 3, we have I(u, Qu, k,
(2 e, k) & we and as a result:
[w]]
1)u
B[KYYK U. UK u, I. f
(82)
1 w
1)u
w-1 +
(Since|w] S w)
(83)
Wi
(84)
which completes the proof.
B.4 Overall Coding Cost.
We now provide the upperbound on H[] for our Sorting Method. Since the message in the Binning Method also consists two parts, the results are the same. For each part the message, namely and K, we encode it with prefix-code from Zipf distribution [28] For HLL) we have:
H[] < Ex Ellog L|X ==] + log(Ex [E[log L =|] 1) +1
(85)
3 bits
(86)
Hence, the rate for the first message is R1 < H[L] + 4bits.
Similarly, for H [K]]
H|K < Ex[E[log R|x x==== = + log((E R = x| + +1
(87)
= -(X;Y) + log(e) + log(I(XX))) log(e) + 1) +1
(88)
< ((X;Y) + log(I(X:))) + 1) + 2 log(e)++ +1
(89)
Hence, the rate for the second message R2 S H HR] + 1 = T(X:Y) + log(T(X;;>) + 1)
2 log(e) 2bits Also note that:
H[K[W] H L, K[W] (Given W, K and (L, K) are bijective) )
(90)
S H [[] + H[[W]
(91)
< H + H[] [[
(92)
+ (o; + +)+ (bits)
(93)
Since we are compressing two messages separately, we have: ()) + 1) + (bits)
S Rı + Rs T(X;V)
C Matching Probability of Rejection Sampling
C.1 Distributed Matching Probabilities of RS
Follow the setup in Section 3.2. each party independently performs RS using the proposal distribu- tion (-(-) to select indices KA and KB and set (YA, YB) (YK,, YKg). We assume the bounding condition holds for both parties, i.e. max, (p) (v), P (1)) S w, Proposition C.1
shows the probability that they select the same index, given that KA y.
26

---

Proposition C.1. Ler W. (OQ,() and (P(.) defined as above. Then we have:
Pr(Ya = OYYA=Ya|Ya = min(1, PV (v) PA
(94)
1+ 1+TV(PP) .P)
(L1-PP())/PE
Furthermore, we have:
Pr(YKa- -KR)) = 1 TV(PS, 1+ TV(PP. PV)
(95)
where TV P&) is the total variation distance between two distribution Py and Pp-
This matching probability is not as strong, compared to PML as well as IML, details in Appendix C.2 In the case of GRS, we provide an analysis via a non-trivial example in Appendix D.2 possible to construct target and proposal distributions such that Pr(K^=KB YK,- y - 0.0, even when (A(y) p (v). In contrast, this probability is greater than 1/4 for standard RS. In summary, while GRS and RS can achieve a coding cost in 1 its matching probability remains lower than that attainable by PML and IML.
where we demonstrate that
C.1.1 Proof.
We denote by KA, KB the index selected by parties A and B, respectively. We first note that the event {KA- KB = i, Y; = y is equivalent to the event [K A KB K, y). thus:
Pr = KB = =, =y) = Pr(Ka KB = i|y (v)
(96)
PA(2)
where the denominator is due to YKA= (.). Since:
Pr(KA = KB|YKA = =y = Σ Pr(KA= = KB=:(BKKK y)
(97)
(v
P(KA KB =iy;; v)
(98)
Pp(U)
We will later show that:
Pr(KA KKB = i|Y; yy) min( PP()))
1 w
1
PP
(99)
wQy (g)
which gives us:
Pr(KA=KB YK,
(100)
Qrly), min (PP(P) (1), (p),PP(()) Pf()))
Σ
max P (1)))PP.. (v))ddy
1-1
(101)
PV( wQy (3)
min(PA(y), (1)
Σ
1
(P) (2 (2))dd
(102)
wPA(y)
1=0
min P (y), (1))
(103)
wP)(y)
PM)
min(1, PB (v) (p)))())))))))))))))))
(104)
[ (max((24() (PA()), P/ (u))dy
min (P (1(()/PAA/)) (A)
(105)
1+ 1+TV(PAAPP PP)
where (VA PP) is the total variation distance between (A()) and P.(.). Using the inequality min(u, v) 2 wtr and the fact that TV PP) < gives us the latter inequality.
Daaliri et al. 8 also arrives similar conclusion but for discrete case, targeting different problem.
27

---

To show (99). we first compute the following probabilities where A and B both accept/terminate given sample Y y:
<Vy) = Pr(A and B accepts Y y)
(106)
Pr(U I min(P (v), P. (y))))Y y)
(107)
min(PA (y), ( PQ(())
(108)
wQy(y)
and,
{10 = Pr(A and B rejects Y =
(109)
Pr(U max (Pp (v), P (u)))l 9)
(110)
max m (v), Pe (v))
(111)
wQr (y)
Then we have:
Pr(KA = KB = i|V; = yi)
(112)
/ Pr(KA KB =i|Yi:: = y1:: (Yi-1 V1--1 =y)
y)dy1s-1
(113)
/ Pr((KA KB =i/Y = v1 (V1:i-1 = V1:i-1ddyaas-1
(114)
/ Pr(KA KB i|Yi: vy (Y y1i-1)dy
(115)
= =>(1)) /
II (r (1,))ya-1
(116)
j=1
{-1
->(v)) II / 5=1
(117)
min(P/ (v), (P)) PV (v))
max (P),
i-1
Qr Qr(w)dy
(118)
wQy min (P/ ; PP()))
wQy(v)
1
i-1
PB (y(dd
(119)
wQr
Finally, we note that:
Pr(B outputs y| A outputs y) B KAlYKFa =y) + Pr(party B outputs y, KB # KAIVKA=))
(120)
(121)
Finally, note that in the case where PA(., PB()) are continuous distribution, have:
Pr(party B outputs Kpg + KP,lYKe my = 0.0
(122)
This completes the proof.
C.2 Comparision with Poisson Matching Lemma
We will compare the average matching probability Pr(KA KR)) between RS and PMI. in the continuous case. Starting from equation (30) in [27 and assume P (v) I P& (v), have:
28

---

P(YA YB==) = 9)
(123)
= =Pr(KA- - KB\Ya - u)PP(Y> =
(124)
(125)
L max
PV(() ((( PV( (v) du
PA(
(126)
(U), Pp(v) py (v(1) _ max
PP((]
de
PV(U)
(Since we assume PV(U) - PPP(1)) (v))
(127)
_ max (P) (v)) de
PA(U)
(128)
1+ TV P$)
Repeating the same step for P 2 P (v), we have:
min (v), 1+ TV P$)
P(Ya YB 9)
(129)
Taking the integral with respect to y for both sides gives us the desired inequality where the RHS expression is the average matching probability of RS. Finally, the same conclusion holds for IML since the matching probability of IML converges to that PML.
D
Greedy Rejection Sampling.
D.1 Coding Cost
Compared to the standard RS approach described above, GRS is a more well-known tool for channel simulation [14] [8]. its runtime entropy, i.e., [[K]. is significantly lower than that of standard RS. Unlike standard RS, where the acceptance probability remains the same on average at each step, GRS greedily accepts samples from high-density regions early possible (see [14] for more details). Using these properties, Flamich and Theis [14] provide the following upper bound on H HK]] which generalizes the discrete version established by Harsha et al. [18]:
H[K] S 7[X; YJ + log(7[X; YJ + 1)
(130)
which has smaller constant compared to the bound for standard RS. We conclude with a note on the coding cost of GRS, highlighting that, unlike standard RS, which relatively easy to implement in practice, GRS can be more challenging to deploy as it requires repeatedly computing complex and potentially intractable integral.
D.2 Matching Probability in Greedy Rejection Sampling
Setup. Let the proposal distribution Qy be discrete uniform Unif[1, i.c. Qy = 9 = 1/n and U ((, 1) as in standard RS. Then, we define W follow:
W = {(Y, U1), (Y2, U2),...
(131)
Our goal is to show that, for this proposal distribution Qy, there exists the target distributions (.). and P. (.) such that the GRS matching probability Pr(YA = YB YA = y) + 0.0 even when
Pa()) = Pp))). Let n = 2k + 1, we construct the following PA and PS:
++
for 1 < h: +
PV =
PA(YY = i)
(132)
2k +1'
0..0,
fori>
1
++1 1)
1.
fori>
P = = 2k+1'
(133)
2k +1'
(0.0,
forl<isk+1'
29

---

Probability Mass Functions for Qr. Pq. and Py (k=1, n=3)
0.6
PV
Py
Pobalalty
0.
Figure 8: Visualization of example distributions in Section D.2 for k = 1.
where we visualize this in Figure
GRS Matching Probability. Given party A has target distribution PA and party B has target distribution Pf( with each running the GRS procedure to obtain their samples Ya. YB respectively. We want to characterize the probability that party A and party outputs the same value, give party A's output. We denote KA and K n as the index within W that party A and party B select respectively, iee, YK,- = Ya and YKg = Yn-
Consider the event YA 1, with the construction above, we have the following properties:
If party A and party B both the first proposal Y, 1, they will greedily accept it, since PA(Y = =) Pp = 1) 2 Qr (Y = 1). So in this case:
1
Pr(Ka KB 1, YA = 1) = Qy 1Y=
2k +
On the other hand, if the first proposal Y + then either party A or B must accept and output Y1 + since for y + 1, the probability distribution complement each other and equal to Qr(y) 2F+T. For example, for and Y2 2, then party A will accept it while party B must reject it. Therefore, we have:
Pr(Ka Kn 1, Y 1) 0.0.
Finally, from the previous analysis, for any positive integers * j. we have
Pr(KA = i, K3 = Y, = 1, = = 0.0,
Indeed, consider = 1 then Pr(KA 4 = 1, KB = 101x=11Y,, =, = 1) = 0.0 since both of them must accept the first proposal Yi 1. On the other hand, if i > 1 then must have j = 1 since we know that Y, f in this case and thus one of the party must stop. Since has be party B and in this case, YB +
For this reason, we have:
Pr(YA = Yn =)
(134)
=Pr(KA= KB, YA 1,YB = K
(135)
=Pr(KA KB. 1) + Σ Pr(KA= K, K-=K,
1, =)
(136)
Pr(KA Kn,YA 1)
(137)
Pr(KA KB = 1, = 1) + PT(KA = KB > 1,YA=1)
(138)
(Y 1)
(139)
(140)
2k +1
and hence:
1
Pr(YA YoIYA = 1) 1+1
(141)
30

---

which approaches 0.0 as - oc. Overall, due to its greedy selection approach, GRS may yield lower matching probabilities compared to other methods such PML which we provide the analysis below.
Matching Probability of PMI. In PMI., the matching probability is Pr(Ya YB Yı =) =1 1. This results from PML's more global selection process compared to GRS, as it evaluates all candidates comprehensively. In particular, let W (S1, Y1) Yi,,.., (S,, Yn,) where S; ~ Exp(1) and let K B be the value within W that each party respectively select in this case. Note that the construction of W in the discrete case for PML does not require Qy. The selection process according PML is as follows:
S
S PY()))
A = arg min Isin (V.
KB arg min Isisn
(142)
and each party outputs Yι = YK. YB Yk. We see that if KA = 1. then we must have
Kg 1. This because for any 1, we have PA 1) Pf(Y =1) > Pf(Y = and
(Y i) = PY =i + k). Thus, this gives Pr(Ya YB 1==1)=1.
31

---

Algorithm 1: Ensemble Rejection Sampling ERS(W; Py, Qy w = maxy Qr(s) scale = 1)
Py(v)
Input:
Target distribution Py, Proposal distribution Qy, and the source of randomness W (see
(r) Section 5.1 Default value w maxy (2 unless override by some value > w.
Default scaling factor scale = unless override by some value within (0, 1].
Output: Selected Index K and sample Yк Py
1. Observe batch {B, }
2.
Select candidate index Kqand;
K Krand argmin Sik
(Ya)
where: Aa=
ISK5N Ase"
(Y
3. Compute:
3(Y,1:n) Σ Ask
(YiiN Krand) ((Y,i:)) + w A
4. Set Ki = i, K2 = Keand, K = (N- + Keand and return Yx if:
2(Y,,:N)
U, S 7(i,I.N Kgand) scale,
else repeat Step with B,41.
E ERS Coding Scheme
E.1 Prelimaries
We show the standard ERS algorithm in Algorithm following the original version introduced by Deligiannidis et al. [9] with a slight generalization in terms of the scaling factor (0 < scale I 1) that we will use for channel simulation purpose. This section begins by establishing some detailed quantities that will be used repeatedly. For simplicity, we use Pz (.) for the target distribution Py|x=z and (.) for the proposal distribution. Let W/ = max,, (v)))(())) we define the quantities:
N
Po(1)) Q(1))*
(I k) = (v1:)) Px(UK) Quvr.
Ze (vI:N) = Σ
+ Ww
(143)
1=1
and denote the following constants:
N
N =
A EYIN~
(144)
2Y 1)
-1+
where we recall that w max,, Pv(v)/Q(y), by Jensen's inequality we have the following:
N
N 1 W. N-1- A for every æ.
(145)
From this, we can see that as N + co, we achieve A + 1.0. This value A turns out to be the average batch acceptance probability when we scale _. which we elaborate on below.
Scaled Acceptance Probability. For the channel simulation setting in this section, we slightly modify
the acceptance probability in Algorithm (step 4) with a scaling factor scale = A S 1 such that
the average batch acceptance probability is the same, regardless of the target distribution P, In particular, the encoder selects the index according to:
K = ERS(W; Pa, Q, scale
(146)
'This is similar to the case of standard RS where we accept/reject based on the global ratio bound instead of wf.
32

---

which means for a batch i containing samples Y11INN = V1:N, we accept within step 4 if:
Z (V1:N) A
Accept if U/ -
(147)
Z (VI:N. k) A
where modify the scaling scale S. < in Algorithm which is constant and does not affect the resulting output distribution. The value of k is determined via the Gumbel-Max selection procedure in Step The intuition is, within every accepted batch without scaling, we randomly reject (1 scale) of them. Formally, first consider the following ERS proposal distribution:
N
(
II j=1
(11))
(148)
Σ5= (=()s)/((ss))
N
Pa (u()))((U)n
N
II Q(1)).
(149)
where the first product in the RHS is the likelihood we obtain the samples V1:N from the original proposal distribution Qy and the ratio is due to the IS process. Now, the ERS target distribution PY K (VI.N, k; z) where
(W) 1 Qu(u))(((Nn)
(VIIN) A
N II j=1
Q
(150)
(o(IN)
Zo(UINN k) An
(( AUI.N. k)
N
(ww)),
(151)
j=1
which is the batch target distribution that yields Y ~ Pz when no scaling occur (see 99. Section 2.2), since the normalization factor is:
N a
((()))/((vee) (o(NN.N 2
N
Σ
II j=1
(w1s)
dy/1.N
(152)
A
(2lun)/((Uk))
N
II ((v))
dyi:N
(Due to symmetry)
(153)
Zz(viNN
N
A
1
N
dy
(154)
Zz (Z(NNN
(155)
turns out that also the batch acceptance probability since:
A 2o
Pr(Accept batch B) AY).N.AA-G
(156)
A
(11.N
N
(r((n))/((un))
(157)
Zu(ui.N, k)
(Poli)/Q(U)) (ZUNN.
NN ((ss)) [
dyw.N
(158)
(159)
and it can be observed that, without the scaling factor A. the batch acceptance probability is Az- Finally, view the ERS as standard RS procedure with proposal distribution Qyp K and target distribution Pyş.K-
Inequality. We introduce the following inequality (Harris-
FKG/Chebyshev), which will be used in the proof:
33

---

Proposition E.1. For function f,g on Y ~ P()) where f is non non-increasing and g is non non-decreasingg we have:
B[f(Y) & BIX(Y)
Proof. Let 11, P(.) and they are independent. Then we have:
(f(C)) f(X2)llo(X) - 2(2)) < 0
(160)
Hence:
E{f(()) f(X2)llo())) - g(Y2)) 0
(161)
This gives us:
+ (( +())))
(162)
which completes the proof.
E.2
Encoding Ki
We encode K1 the same way the scheme for standard RS. Similar to standard RS, encode K1 into two messages. Specifically:
Step I: the encoder sends the ceiling == [
Ki [- to the decoder. The decoder then knows
(L - 1) -- batches. We have [[] S bit.
L A -1]-1,11-0 i.c. K1 is in chunk L that consists of |A [A-
Step 2: The encoder and decoder both sort the uniform random variables U/ within the selected chunk (L 1) + < -[ Let the sorted list be Uz(1) s U2(2) I < U where T.) is the mapping between the sorted index and the original unsorted one. The encoder sends the rank of UK, within this list, i.e. sends the value T such that K₁ = (K)). The decoder receive K; and retrieve Bx, accordingly.
Section E.2.2 shows the coding cost for this step.
We provide the detail analysis in Section E.2. and E.2.2 Notice that the role A plays here is similar to that of w in standard RS.
E.2.1 Coding Cost of L
Similar to RS, since each batch is accepted with probability A (see (19)). this means:
Pr(K1 > (A-1) = (1 - A) 0.5
which is equivalent Pr(L f) 0.5 - Note that we reuse the inequality in Appendix B.3 We have:
20
[IL] = Σ Pr(L < 0.5 + =2
(163)
8=
implying Ellog L] < 1.
E.2.2 Coding Cost of K
We will show that:
N Exnaa
(a(Yi)/(()) log (YIN..1
(YiN)
E Blog Ki <
(164)
Ag
(Y..,)
where we provide the result of (164 in Section E.4.2
34

---

E.3
Encoding K2.
Given an accepted batch ((Y,. have:
S
Pp = min S 151SN X
K₂ = arg min
(165)
ISIN X;
where we have the weights X; defined as:
P(Y))
X
(166)
Q(Yi)
After communicating the selected batch index K1, the encoder and decoder sort the exponential random variables (S I.....
Skz,z(1) S Sk2,((2) S... S (K2,=(N)>
(167)
and send the sorted index K2 of K2, i.e. T(K2) K2. The decoder also performs the sorting operation and retrieve 2₂ accordingly. Since K2 are obtained from the batch selected by ERS, we analyze E Eloo K2 V are selected), where K2 and K22 are defined the same as K₂ and K2 (follows the same Gumbel-Maa procedure) but for arbitrary N Li.d. proposals YI.N Q(.). In this case:
Ellog K2] Ellog K2 Yi:N selected]
Notice the following identity:
P(y (.AN,k2:)) k2;z) = P(Y.. = V1.N Ni:N are selected, K2 = 122) Pr(K2 = 12 are selected)
where P(y k2; ()) the ERS target distribution described previously in Appendix E.1 Then, obtain the following likelihood:
P(YIN VI.N VYN selected, K2- 1)
(168)
P(y1.N. j:z)
(169)
Pr(KG = INN are selected)
Pa (w) N
II (Qu)
(170)
A, Z3 1)
With this, we now bound the expectation term of interest E(log K2] as follows:
Eloog K2)
(171)
Eloo R2 YI.N are selected]
(172)
=
Ellog R₂ YIAN are selected, Kº = (Due to Symmetry)
(173)
BYL. [E[log K2 ViN selected, K2 1, YI.N V1.N]]
(174)
N / Do Pz(y))/(uv) Eilog R2 are selected, VIAN = 31.N, K2 1]
NN
(v.) dyl:N
D (
(175)
N = N f (c(1))((11)) Elog KILL VI,N, K²=11 1] [| ((w))) dyl.N. A, 1)
(176)
where the last equality is because, given (YINNVVN,, K3=1), the event (Yi.N selected} and the random variable K2 are independent. In particular, the decision whether accept batch not does not depends on the rank of Sky, that is:
Pr(Y are selected Yi.N = VI.N, K2 1, K2g kz)
(177)
Pr(YN.N are selected| 91.N, K2 1)
(178)
2a(MnN) A
(179)
Zu(yINN, 1) A
35

---

We then have:
Elog R2 VY:N are selected]
(180)
0 N
II (w.) Pa (a()))((un) A. 1)
(f,² E' of
=N
p-= dyi.N,
(181)
since, given YI.N, Op is independent of K2 and (1)(x)( (see [35,, Appendix 18). We now pro- vide an upperbound of Ellog K2 YI.N-WI.N, =2=1, pp=0J, which follows the argument presented [35], and is repeated here. Applying Jensen's 's inequality, we have:
E log K2 YI.N = VL.N K2 = 1, Up = 0) E[g = BUN, K3 = 1, = 0], (182)
We then rewrite R/ as the following:
R2 1(S: < SkyHl +1,
(183)
which gives us:
E[ I.N = VI.N, K3- = 1, = 8]
(184)
=1+ =[|B < &k; H = VI:N: K2 = 11 = =0)
(185)
P,(Yks)/Q(Kss)
=1+B
S <
YI,N VIN K
(186)
(YIN)
S /
=1+ + Σ
Pr
VI.N -INN, =2= 1, =0
(187)
(YIN))
St < (2(())Q((1))
S 2 for j
S
++
Σ
Pr
YI.N VI.N, Pa(p:)/Q(v. (2(11x)
(Y
(2) ( (Q
1=2
(M(
(188)
N
S < 0 Pa(X1)/((M))
S P Z. (.(1)N)
S
11 Σ
Pr
VI.N-1
0 for j$1,
0
(Y1NN))
Pa Q/Q()))
1=2
2 (u1.))
(189)
N
S, < 0 QX()))(((X))
S
11
Pr
VI.N = VI (a 1Q
2 0
(190)
(Y1NN))
1=2
Z- (11.8)
Note that:
S < Q(()))(((K))
S
Pr
YIN = MI,N Pz(g:)/Q(v.)
(191)
20(VEN)
0 P2 (2(()/Q(()))
(Y)))(((Y)))
}
| 11-csp exp
(
2rd (VI.N)
(3(:N))
(x1.))
(192)
Polvi)/((1n) - P(()))(((H))
< 1 exp
(193)
20(U1:))
((r((()))((v)) - Pr(ui)/((r))
(194)
(P)()))/((11)
(195)
36

---

As such:
N 51
OP, (v))))((
B|Kg|Y -IN, - 1,0p 11
(196)
2z (UI:N)
i=2
< 1
(197)
(2(NN)
and thus:
Bllog K K| - VIN, K2 = 1, 0ld0
(198)
(OP2(11)/((m)))
c
log
1+
(199)
(o(1N)
NNP((n))((un))
+1)
log
(200)
Zx (21.N)
which is due Jensen's 's inequality for concave function log(.). Finally, we have:
Eloog K2]
(201)
(Y)((1)(((M)) log
NP.(M)/((M))
+1)
B)))~(()
(202)
(YIN.1)
(Y(NN)
NP. (Y))(((((M)))) log
(N)((1))(((M))
(Y1.e)2,(Y1:N)) NP.((1)/(()))
Ag (XIN..)
Zx (Y(Nn)
(X)((I)/((XI)) A 1)
(203)
(Y)Q(())( log
(
]
= =()
+ log(e)
(204)
A (YIN..1
(YIN)
The last inequality is due to the FKG inequality:
log(e) 2n (Yin))
Ey,x~Q))
(205)
Au 2 (YINN1).
[1+ 1+ Σ PY(Y))
(
= =log(e)Ey xvQ((())
(206)
Q(Y:)
Az (YIN,,1)
i=2
N 1 PYtY
1
< <log(e) (oog(e) ~(6)
Byz~o()
(207)
Q(Y))
2=2
= log(e)
(208)
So have the bound on Efllog( K2)] as:
(Y,
log NP,((i)/((X))
)
Eloog(<>) < [v)))((()
log(e)
(209)
A (Y.N,1
Z,.Y
E.4 Total Coding Cost of K
We now provide upperbound on the total coding cost of K. We have:
H(K[W)= HT, K1, k2(W)
(210)
< H(L[W) + H (KK]WW) + HK))WW
(211)
< H(L) + H(K) + H(K,)
(212)
37

---

For each of the message, we encode using Zipf distribution. Since [[log[L)] - 1, then:
H(L) 3
For HK1)), we have:
H(Ri) S Ex(Bolg (Ri)] logoBx(B(log( K1)]] + +1)
(213)
and H(2)), we have:
1(K2) s 144 + 1) +
(214)
and thus we have:
[K))))
(215)
$ (Ex [og Elogg( BB [Elg [2]]]
+))
(216)
By AM-GM inequality, have:
(1 (1: + +
log((EE [Eloo(|[
(217)
S log( (Ex
K2)]l + 1)2)
(218)
-o Ex E log
+x
1x K2 )I] + + -
(219)
We will show Ellog #[log])l D ( Q2) + + 2log(e) at the end of this section.
Given this, we have:
HKK(W)
+lgg + 5 2logee) 2 +
(220)
< <((XY)) 2 8) +
(221)
Since we are encoding messages separately, we add bit overhead for each message and thus arrive the constant 12 the original result.
The rest is to bound B[log( [2)] B[log( [2)], note that:
E[log( K1) + Ellog( R2)]
(222)
(Y)(())/((M)))
NYP((:)/Q(Y))
<2log(e) (lllge))+Evi.veee)
log
+ +log
(YIN..)
A Z. (YI:N,
(x
(223)
(N))())((MI)) log
NNP((Y)/((X1))
=2log(e) + BYLNNQQ))
(224)
(YIN,
NP, (X)((/Q((X)))
log P.(Y) Q(Yi)
N
2ogg(e) + (En.N~Q())
log
(225)
A 1)
A A, 1)
N
N
log(() + DKL (Pa [Q)) + Ey,
log
(226)
A (YIN,,
A 121:, 1)
log(() + DKL (Px [Q) Fy
(227)
where:
N
N Za (A.
E Ey By,N~~()
log
(228)
A ZY
We will show in Appendix
E.4. that:
Ei 53
(229)
and thus:
Ellog (ki) E[log K2)] 2 llg((e) + DxI (Pal))
(230)
38

---

E.4.1 Bound on E1
We consider cases, when the batch size N S Two and when N 7a7n.
Case 1: S Twz
Recall that (YIN, 1) > We and A. 2
N I-1+ we have:
N
N
N - 1 + wi
(231)
An (01,(YY1,,,)) II,,, 1)
We
8w/
( Since N S 7w)
(232)
We
8
(233)
Thus, we have:
N
N
E1 -EEy Ev
log
(234)
D Zz (YEN, 1)
An (YIZa(YiN)))
N
log (8)
(235)
(YI.N, 1)
N
=3 (Since A. = Q)))
(236)
Z (Yi.N, 10,
and hence E1 S 3 bit.
Case 2: N > Tw
To upper-bound Eg this regime, first note that:
N
A = (YYNN~Q)
= Pr((Aceet batch B) S 1
(237)
(YE.NN..1)
Another way to see this through the following arguments:
N
Bv)N)Q())
(238)
Z (Y 1)
(Y)((1))((M)))
-EY
(239)
Zo(YN.N.1)
(P2((1)((M)) (V1:))
EYnN~QQ)
(240)
Zx(NN))
Zo(YN.N11) 1)
(P)(())Q(MM))
2x1N::)
< [Y..)QQ))
Since
S
(241)
(YIN))))
Zz (YI,,,11
(Y3))(Q((Y))
By)
(Due to symmetry)
(242)
(YIN)
(243)
and as a consequence (which we will using later), we have:
N +1
Byix~(())
(244)
+ 2n (Vin)
N +1
= =EyN++aQ()
(245)
Wr + 2 (Yi.))
< 1.
(246)
39

---

Then, observe that:
N
N
E Br.
log
(247)
A Zz (VEN, 1)
19,2o(Yi:N) 1)
1 By)
N log
N
1
log
(248)
Az
(z(YN,,,1)
2,(Yi,N,
A
S 3 bits
(249)
where, to show the inequality at the end, we will prove the following two inequalities:
log
I log
(250)
A
7
]
E
Q()
log
s 7
(251)
A
Zz (YIN,
Zz (Y 1)
and hence Eg S 3 (bits). For the first inequality, we have:
N (YI:N. 1)
A. B()
(252)
N
2 Ey Exn,N~Q
( (Jensen's 's Inequality)
(253)
[Z (YIN,,
N
(254)
N + Wr
N
(Since N 7wx)
(255)
N
1 + N/7
(256)
hence, we have:
8/7,
(257)
A
which yields the first inequality after taking the log(.) in both sides.
For the second inequality, we begin by establishing the following key inequality:
N
2N
(258)
(YIN. 1)
Za (YIN)) + Wwz
which is due to:
N
N
(259)
Z, (YEN, 1)
We + Σ> Di=2 Q(1)
(.())
N
(Since PY
2 0 for all i)
(260)
Ww + 1 Dim
P.(Y)) 2 Q(Y.)
Q(Y,)
2N
(261)
2w Em²
P.(Y)) 2im2 Q(Y
2N
(Since Pa Q(Y,
Sw for all i)
(262)
N
(X())
W. + Σi= Q(X)
2N
(263)
(Y Wa
40

---

Then, we have:
1
N Z (YiN: 1)
N
Ax
Q(xx)(1))
log
Zz (Vi:,, 1)
(264)
8
N
N
7
log
(Since A. 2
from (256)
(265)
7
(YI.N.N
Z Zx(YINN
8
N
BYIN)QQ))
log
(266)
Zx(NN,N;1)
Z2INN 1)
8
NP, (Y))))))((1))) log
N
+1 +1)
BYIN~Q()
(267)
(Y(N..111
Z 1)
8 BYiN=Q())
NP. (Y)(())((M))))
(YI:)) + +wx + =11
2N
log
(Due to Inequality 258
Zz 1YI,,,,1
(268)
8
Ey (()
(P)((1)(((1))) log
(YI.)) +w2 we +1
2N
(Since 2
1))
7
(x(Nn)))
(269)
8
Pa(G)/Q(M)) log
2N
B()
+1
(Due symmetry)
(270)
7
(YIN))
(YIi)) + ww
8
(2(Y))/Q(Y)) -==1
N
(YIN:: + we +1)
2N
log
(271)
7
(Y1NN)))
8
2N
Ey BV.
log
(YI.)) ww +11 111
(272)
7
8
2N
log
BYIN~Q())
+
(Jensen's Inequality)
(273)
7
Z (YI:)) + +we
))
8
2N
N +
log
1
(()))Q())
(274)
7
N
(YI.N) ) + Ww
8
2N
N +
log
1
(Since Ey)x~~())
< 1 due to Inequality 246
(275)
N +1)
(Yin) - Wr.
8
1og(4)
(276)
16
(bits)
(277)
which completes the proof for this part.
E.4.2 Proof of Inequality (164)
We first express the quantity [o[log Ki] with conditional expectation. The accepted batch and selected local index K2 are distributed according to YKT,IN, K2 PYL., then:
Ellog Ki]
(278)
E [log R2|YK,,, IIN MI.N.KK K2 kell
(279)
Pu( Zz (vr.N. b)
Q(1s)
E(log K2 KI/YK,NI 91.N K2
keldy1.N
(280)
00
(a()1) Ellog K YYK,IN K2 1]dy1.N
N
((v))
(281)
Z (vIN, 1)
41

---

Notice that, since we accept a batch when Uj S 2- 2=(N))) A Z (2 A="
we have that:
Z Z31.N. 1) A (z(1NN) A
P(UK. =||KLNN-= ULN K2 1)
then conditioning on UK, for the last expectation term above:
Ellog Ki (iKK,,,,:N = VI,N, K2 = k]
(282)
Ellog KIlYKI,INN = VI,N K2 1, = w/P(UK = =u/KK,,INN = -INN, K2 1)du
(283)
2a
Ellog K₂ YY,, VI:N, K2 1, 1,UK, u] (V1.N 1) A (2(21 A
du
(284)
2o(vIN)
(1 25
(yIIN, log
u du
1
(See the Sort Coding bound below.) (285)
J
2a(vi
1) (1
(y1:N)
log
1 +
du
(286)
Jo
(VI.N)
A Zz (V1:N.11
(31.N)
log
+
(287)
Au Zn (VIIN,
Finally, we have:
Ellog Ki]
(288)
Pa(y1)
(2(:N)
N
II Q(1)) 1=2
log 1
dy1:N
(289)
(VIIN, 1)4r
A, ( 1)
P2(11)
(2(-N)
A.Z.
N
(wv))
log
+ log
dy
ZN(INN 1)4r
Ao (VL:N.1)
Zu (VI:N)
(290)
P1( log
(x(:N)
N
II Q(ui)
dyi. + log(e)
(291)
ZZ(INN 1)Ar
AoZo(VINN. 1)
N
(
(YI:))
Exiaa
log
(292)
A
(..N,, 1)
AY,N,(Y
We show the proof for (255 below.
Sort Coding Bound. To bound the expectation term, we first apply Jensen's inequality and condi- tioning on the accepted chunk of batches I, =
Ellog R K.lY..NNN VI,N K2 1, U,K u]
(293)
< (og((E(( KC IK, VI:N K2 1,UK, =2])
(294)
(EE KN YK,IINN VI.N, K2 1,UK, u|)
(295)
= log [ K VKK,I.N = VI,N, K2 = U,K,, u, = {I)
(296)
We now repeat the previous argument in standard RS. Specifically, given Kr within the range = and UK,- = u, we can express K as follows:
k -U. < u, (f 1)AA +
(297)
= =((u,))+
(298)
42

---

L.c. the number of U, (plus for the ranking) within the range L that has value lesser than u. We can see that the the index i within the range I. satisfying U+ are from the indices that either (1) rejected, i.e. index i < K₁ or (2) not examined by the algorithm, i.. index >> K1. The rest of this proof will show the following bound:
(j E) = VI:N, K₂ U,U,- - u, o) - u,, for any &
(299)
For readability, we split the proof into different proof steps.
Proof Step 1: We condition on the mapped index of x()) on the original array:
B[K] Y K1.1 VI.N, K2 1,UK, u, f]
(300)
E[K] YKI,I.N VI:N, K₂ = 1, UK. =u, = (K1) ki1]
1 (
(301)
E ((()))
E[ E) +1 YKIENN VI.N, K₂ 1,UK, =u l, (iT(Ki) = kii]
(302)
(a(k))
E[(((,,) 0) YKR,EN= = -VNN, K2 = 1,K,, =u, L. l, Tr (Ki) =kil] +
(303)
[ESSi (u, e, k1) (2(u,,,11)) YK -I.N, K2 L, UKK u, e, (K1) ki]
1,
(304)
where 22 (u, k,k,), (,, k1) are the number of U; < a within the range L = E that occurs before and after the selected index ki respectively. Specifically:
S2 (u l, k1) - {U: < u, (e- (1-1)-A-1) + +isi < (8 (6- 1)1-- K l2 l, k1) = [(U, < u, th
(305)
(306)
which also naturally gives 22u, Ωi (u, + 92 f,
Proof Step 2: Consider Q2 l, ki), since each proposal (Yr,I.n, U.) is i.i.d distributed and the fact that k is the index of the first accepted batch, for every > ki, we have:
Pr(U,- <u| PLLN= = VINN K2 = 1, UK. = u, L = l, (Ki) = k1) = Pr(UU u)
This gives us:
E E[0g(u, E, k1) YKI,I:N = VI,N K2 = 1,UK, = u, L = e, (,T(Ki) = ki]
(307)
= =(1 JJ - -k1) Pr(U < <u)
(308)
-(1-- kı)u
(309)
(310)
Pr(Batch is rejected)
A kI
(311)
1-A
Proof Step 3: For 21 f, k1), we do not have such independent property since for every batch with index < ki, we know that they are rejected batches, and hence for i < ki:
Pr(U,
YKK,INN VI,N K2 k. UK. = u. e, ((TiK, k1)
(312)
= -Pr(U, < u|(Y...N is rejected)
(313)
Prr(U, < u, Yr... is rejected)
(314)
Pr(Yi,IN is rejected)
Pr(U, < u)
(315)
Pr(Y,,uo is rejected)
(316)
which gives us:
(ki 1)u
E[Zz(u, e, ki)
YKG,ON = -VNN,
K2 = 1,UN, u, L
(,
=1]s
=
(317)
1-A A
43

---

To prove Equation B13,, note that the following events are equivalent:
(YK,IN WI,N, K2 1,UK, =u, k1 (VK,,IN = V1,N K2 = 1,Ux = u, BI....k1 are rejected)
(318)
(319)
(I)
(320)
Here, we note that Yk,, Uk, denote the value at batch index k within W, which is different from YK, UK. the value selected by the rejection sampler. Hence:
Pr(U, < u/A(u, V, k1)
(321)
Pr(U, < u, Bi..k -1 are rejected YA,INN = VI,N UR u, K2 =1
(322)
Pr(BI... -1 are rejected VI.N Un u, K2 = 1)
Pr(U; < B are rejected) (Since U,, are i.i.d)
(323)
Pr(BI... 1...1 rejected)
-Pr(U, < B; is rejected),
(324)
Proof Step 4:
From the above result from Step 2 and we have s(u, O2g (u, e, k))
a2(u,l,h) < 1-1'1-1u and result:
Eloog K2IYKi,IN = VI,N K2 = 1,U,, - 5 (14-1
1)u
+1
(325)
A
(A
1)u
+1
(Since
A A-1
S A-11)
1 A
(326)
#+11
(327)
which completes the proof.
44

---

ERS Matching Lemmas
F.1 Preliminaries
We begin by providing the following bounds on inverse moments of averages. Proposition F.I. Let Yi, Y,,..., YN Qr),) and suppose the larget distribution Py satifies:
Qr
d2(2r11P)) - Ey~
< 00,
(328)
Pr
then we have:
N EE
E Nvv))
S d2(Qr)1Pr).
(329)
Proof. Applying the Cauchy-Schwarz inequality, we have:
N
QY)
(330)
Σ N PY (X)
j=1
Taking the expectation of both sides yield the desired inequality.
Remark F.2. In general, stronger results on the inverse moments of averages exist under weaker moment assumptions, specifically:
Ey [ "
"
is finite for some < O. The resulting bound has similar form (some power terms involved) to that of Proposition F. but requires mild threshold on N. For further details, see Proposition A.l in (1O].
We show application of Proposition B.T. which will repeatly:
Corollary F3. Let Y1, Y2,... YN ~ Qx(.) and suppose the target distributions Pd, Pd satisfy:
QQ(Y))
and Pf(y) Pe Py() Qy Qy (v)
d2(Qx11PA) A Ey)@y())
< oo,
I w for all y. (331)
PY(
Then, for any N 2 1,
N PP j= (Y()
(y())
I I1NNww, (dd(:r))dd(QQ11111)))
(332)
N PY(X)
EE= (v
where we define (ww i) A (21lsss + wll N=i).
Proof. For 1, applying the conditions for Pa and P. gives us an upper- upper-bound bound of wdz (odz(Qy\\Pp))
For N > 1, we have:
(P (F()
j== [YJ
Ey By
NNEYIN~QV()
(Due to symmetry)
(333)
N (()
N (A))))
Ei=l (v.).
Σi= (x.)
P$)))) Qr(
PA
< NEv
(since
20 0) QY
(334)
P((
(X.
N EXTiNQy
(335)
(Y M
Qv
< (d2(Qr))PP))
(Proposition F. and N > 1),
(336)
which completes the proof.
45

---

F.2 Distributed Matching Without Batch Communication
Before the proof, we outline the details of each case in Section 3.2 covering scenarios without and with communication between the encoder and decoder.
In this scenario, let PA(.) and (P( be the target distributions at the encoder and decoder respectively, where we use the same shared randomness W as in Section 5.1 where we use the proposal distribution Qr (-). Furthermore,
assume that:
P
(P(()) (v) = WB. max
(P) PV(U) I w, Qy Qr(y)
max
Qv WA+
max
Qv
(337)
Using the ERS procedure, the encoder and decoder select the indices KA and K respectively.
KA ERS(W; Qy), Kв PP,
(338)
The ERS(.) function follows Algorithm]] [ without requiring any specific scaling factor. During the selection process, the calculation of in Step 3 of this algorithm, which determines the acceptance probability, uses the ratio upper bounds WA and w/ for parties A and B, respectively. Proposition F.4 establishes the bound on the probability that both parties produce the same output, conditioned on YKa- y.
Proposition F... Let KA, KB and PA.PY defined as above and N 2 2, we have:
Pr(YKA = =YKelVKa = (1N + (O( (1 (1+
(339)
PE())
where H1 (N) and (N( are defined in Appendix F3 and note that μ (2)).)2((N) - 0 as N + oo under mild assumptions on the distributions pg py and Qr.
Proof. See Appendix F.4
With Communication. Following the setup described in Section 5.3 in the communication case as below:
we define the ratio upperbounds
max (Pre((ule) = Way Q3)
(ri2(wlz)) Qy
Prix(ulx)) Priz(uiz) Qy
max
Way
max H.a
S w,
5
Qr
and similar to the case without communication, the ERS(.) selection process at the encoder and decoder also follows Algorithm [ with the calculation of in Step 3 uses the upperbound we and w, respectively for the encoder and decoder. The bound for this case is shown below. Proposition F.5.
For N 2 2 and X, Y, Z defined above, we have:
(Lpnfon(N)) (N)+ Pylx(ulz) Priz(
Pr(YKı =YKe IYA y,, X=x,
(otpgoud(N)) (340)
where 1 (N) and 1s (N) are defined as in Appendix F.5 and we note that (omd(NN, ( (N)
as N - oo under mild assumptions on the distributions Pr|x(11z)) Prlz)) (r(z( and Q.)...
Proof. See Appendix F.6
F3 Coefficients in Proposition F.4
We first define the coefficient in (N) and (2(N) in Proposition
F.4
1
w
(NNN)
+ 22)( +
(2(2r
(341)
N
N N
1
w
(N
+ will 2)dx
+ N (2(0r11P7))
(342)
N
where we define Il (w, A (2INsF wIN=) in Proposition
E3
46

---

F.4 Proof of Proposition F4
We prove the matching probability for the case of ERS. We note that in this proof, we will use the global index for the proposals YI....Nv ~ Q(.) instead of i1. Y.N unless otherwise stated. First, consider:
PY(YKA- YKnAYKA vn)
(343)
2
Pr(K(=Ks (ka=
(344)
Pr(KA Kg =N|YK= = v1)
(345)
N
2
Pr(KA = Kg = =A = v1)
(346)
PN = KB= = 1| = (1)
(347)
(Q) Pr(K2Z1= = K2 = 1, K1, = K1 = 1|2 = y1)
(348)
(V()))
(Q)
Pr(K22 = K2 = 1, K1,A = KI = 1, Y2.x = 12:N = yn 3dyd2.
(349)
NQy(W)
Pr(K2A = = 1, L K = I JQr (22.N)dy2.N
(350)
(1))
(Q)
(in)
(351)
(QI
Ey
(1))))
x 1 YI.
(352)
where (48) is due to the following fact that:
[KA Kg KKY = =n} (KA Kg 1, = vn
(353)
and thus:
Pr(KA Kg 1|VKA = =v1 PI(KA Kg 1|11 = y1 QQ (11)
(354)
P(YK, = 1/)
Pr(KA KB = 1 yn (v))
(355)
P+(11)
(356)
Define:
(A()))
PB (b(()) (U:)
2(PA.
2(PP.1EN) = Σ
(357)
(V:)
Now, we note that:
(358)
Pr K2,1 = 1)
K2,4 = 1)
(359)
(rr
(360)
ΣN PT()))/Qr()
PA(y))/Y((u)
(a))) 2(P8 ,1NN)
(1+
1+
(361)
2(P4, V1NN)
(31)
2PP y1:N)
47

---

where we denote 2(P 11INN = -E Py(vi)/ (1i) and the last inequality is due to Proposition
1 in 35). Also:
YINN-IIN)
(362)
((PP..1.N)
(PP. (1.8.
PV(v) Pf(U) Qv)) @r(v))
2 min
SSince w 2 max
(363)
(7(P&V22N) +
Z(PP. .V2.N) + w
((PP.WI:)) (PP V2:N) +w
,(P4,
(364)
(PP y2.N) + w
where we use the inequality min(a, b) ab for 0 S <a,b S 1. Plug both in (352). we have:
Pr(Ka=KBlYKa -
(365)
N (PA 32:N
Z(P B1.N)
>By2N~Qr()
P. (1s)
21P M.NN
Em= Z(P8 NVy.2)N
N
py (va)
2(P -(P .VLN))
(()))
(366)
1+ (vL) 2(P m (v1) ((PAA)))))
munntn N
2(P u2. Now 2(P .V.N))
(
1+ (M1) (1n) (PP V1:N) 2(PP)Vi:N)
2(P 12.N) 2
)
L(P N2.NN w+
2 [VaN)Qu()
Pf (v1) Z(PA, BINN)
N
(PP ,yIN))
(367)
Ps (11) (111
= -BVYN~QU()
S1 + Pf (v1) C2
(368)
where we use Jensen's inequality for the convex function 1/x in line (367) and set:
(22N) ) N
2(P Jw
(369)
2(Pp. v1..)
Z(PA, C.PA.12.0 V22NN. - (PP vV2.N)
2(P4. v2:N)
2(P v2:N))
w2
+ N 2(P (1:N)
+
NP V1:N)
N 2(PB VL.N) N 2(P7) VI.N)
Z(PA. v2:N)
w2
< N 2(P4. N2NN++ + N 7(P8, .2.NN)
W
+
(370)
N Nº v2.)
with the last inequality due to ΣM 24 2 Eiz zi for any positive z. We then have:
E yo SyaN Qr
(371)
((PA (2.N)
2(PA, U2:N)
2
S (x)))
(372)
N
N
2(P y2:N)
N N2
V2.N)
N
w
w
2(PAA .2.N)
1
+
BuziNNQu (.)
N y2 Qx(()
E
(373)
N
N
N
(PP V2.N)
2(P v2.N))
1
2(P .22.N)
S 1 +
w + WE U2 Qv(()
+ W Eg)
(374)
N
@(P2.V2.N
((PB.yaN)
1
w²
S 1 + N
w + +.WIN (w. 2)d2(Qr + N d2(Qr11PB)
(375)
= 1 + (N),
(376)
where the last inequality is due to Proposition F.I and Corollary
F3
For the other term, we have:
48

---

((P M.N)
2(P 32.N) -w
2(Pp V2..N
(377)
2(P (WIN))))
N
2(P :1INN)
2(PA V2.N)
(2(PP, + +w)
(378)
N
2(P4 V1.N)
Z(P B1:N)
(2(P (2-)) + +w)
1+
(379)
N
2(P y2.N)
P
V2.N)
w2(Pp V2.N)
w
(380)
N
N
Z(PA, 92:N)
ZPP v2.N)
where we again repeatly use the inequality Ei=
2 Ei= 21 for any positive 2. This gives us:
E Bya (r)n)Qr())
(381)
$
N
1
w + WB Qr
2(PA) (2:N)
2(PF,
1LPy,32.1 V2.N)
+ +w waN
2(P (2.N)
(.PA.WENN)
(382)
1 S N
w²
+ WT 2)d2
N-1 d2(Qr11P())
(383)
(NV)
(384)
where the last inequality is due to Proposition F.1 and Corollary F3
This completes the proof.
F.5 Coefficients in Proposition R5
We define the coefficient unonn (N) and u2 wgond (N) in Proposition F.5
w²
good (N) = N
w + www(w, 20000uu.))d(00/1111111000 + - d2(0r
(385)
1
w²
42
cond (N)
w + (w) (0d +
N - de (--1d((11lBBBii(((()))
(386)
N
where we define NN (wo, i) A (21N>) + w as in Proposition F3
F.6 Proof of Proposition F5
We will use the global index for the proposals Vi,...Yn Q(-) instead of Yi, unless otherwise stated. For the communication version, we have:
Pr(YKa YKol (YKA = yı, X = = ==)
(387)
2 Pr(K KK VKA- -1, X = xx 2)
(388)
- Pr(KA = Kg = k\YKa. = 1/, X = x. ==
(389)
>
Pr(KA = KB = KYKKA V1, V1, = x, x=)
(390)
k=1
= -NPr(KA = KB = 1|KK, = =V,, X = =x =)
(391)
= PP K1 1, K2,1 = K2 =1 = y/, X x. ==)
(392)
Define:
N
Pyix(u(1))
N Priz(uilz)
2(Pr - Vi:N) Σ
2(Pr)Zee Σ
(393)
Qr(v.)
Qr
49

---

Now consider the following terms:
E1 = 1|KKa y,, Y2. = =
x P(Y2NN = 12:N = 11, X = =x)
(394)
(x, 21, 2) Qr ( Pr(K2, 1/11NN VI.N. =2)
x Pr(Ki,d = 1| = VI,N, X x, K2.1 1) VINNX= = KA = 1) (395)
Pxxx((I,B1,, 21, Px())
= 1|11 = VIN. 2)
Pr(KI,A = 1/ = VI,,, X = x; K2.1 = 11
(396)
Qr(v1.))
= 1/ Pr(K2, -I,N, X ===) x)
x Pr(K1,A = 1|V = -1:N, X =
x= x, K2,1 = 1)
(397)
(v(NIN)) (Txxv//x//Qy/ (2/1)
(398)
(vi((vi ( B2.NN Wx
Qy(U2:N)
(399)
((P)X== (2:N) + wr
and:
E2
(400)
Pri(K2, 1|KA = 1, = BIN, = x, =zZ==1 =2)
(401)
PP + 1 1 1, YIN VI,N, X x, 2 =2)
(402)
S
S
-1- Pr
min j
KA 11=1, -V,,,
(uyl=)
(r12())
Z(P 1 Wii.v
7(Pr (=
(403)
S
S
1 Pr
min
KA = 1, 1,NI. = V
(404)
Py x Cws (x) 10112=1 2
Py (=)
P(Pyiz--a (
S
S
=1- Pr
min i
K2,A = 12,A11YY. = VI.N, X = x x=
(405)
Py a (wy (s) P 10 M1.N)
PVix (y1 (x) ((Pr Bl:N)
1
(406)
Priz(11lz) 2(PY)x=n: 81:N)
where (404) is due to the Markov condtion Z - (x.(X - W. 4405 is due to the fact that the uniform random variable U is independent of SNN and (406) is due to the conditional importance matching lemma 35 We note the following events are equivalent:
(KA- = 1,Y = VIIN, X = x, 2 = 2, K2, =1}
(407)
4 U 2(PrIx=M VINN)
YI. = MINNN X x, YK. = = 2 =
(408)
7(PyIx= V2.N) + Wx
A 2z =
(409)
50

---

where 3 = { 8 2(Pr)x-1:BUN) (( YI:N = VI:N X = =2 YKA = =v1). Then, we have:
E3 Pr(KI, 1|KA 1,
VINN, X =x, 2, K2,
(410)
2(Pr)Z=2:XINN VINN
Pr
U 5 ((PYiZ= V2:N) + W2
E,Z=z
(411)
U ((P M1.N)
Pr
E
(412)
\ mm 12.1) ) + We
1, (( YI:N)
((Pr\x=2 V2:N) + Wzs ( V1:N)
= min
(413)
(Pr 12.) w/
where the second to last equality is due to the Markov condition Z - (X, Y) - W.
Combining all three terms Fr, F.,, F&g and continue from step 392 we have:
Pr(YKa- YKg YKA V1, = I, =2)
(414)
1 (1+ Prix(v111) (x) 2(Py == V1:N)
2 N /
Qr(U2:N)
((Py)x=NV B2iN) We
(uiz(ur(z) 2(P xx= x B1.N)
2(Priz=2: YI:N)
2(Prix = V2:N) Ww
min
1, 2(PrIZ=z: Y2:N) + W.
dy2..
(415)
2(Py (PP(x==:M1:N))
=N /
1+ (u)x(ul 2(Py (1Py12zz31100 WI:N) 2(Pr BI:N)
Qv(22.N)
Priz(y1lz) 2(Pr)x x-x V1:N)
X(Pr)x==. VILN)
2(PP Z(Prizz=e> V1.N)
min
dy2:N
(416)
2(Pr 2(Py)X=x: V2NN) + w2 2(Pr Y2.N) ) +
(12
Prix (v1 (111z) 2( 12= B1:N)) (1+ (1+
X( VI-N)
P (Py X= V1:N)
((PYIX=D VINN)
((P 12= Y1:N)
X
dyz:N
(417)
(P B2.N) w
((Priz=2, Y2.N)
with the last inequality follows the fact that w > max(wa, Wz). The rest of the proof follows similar steps as in the proof of Proposition F4 This completes the proof.
51

---

G ERS Matching with Batch Communication
Setup. We first describe the setup in the case where the selected batch index is communicated from the encoder the decoder. The main difference between this and the setup Section [533 is that the decoder (party B) will use the Gumbel-Max selection method instead of the ERS one, since it knows which batch the encoder index belongs to. Furthermore, we note this scheme requires a noiseless channel between the encoder and decoder, which is available in the distributed compression scenario. Similarly to Section 3.2.2 let (X, Y, 2) E X x y x Z with a joint distribution Px,Y.z. We use the same common randomness W in Section 5.3 with the proposal distribution Qy requiring that the bounding condition hold for the tuple (PyIX= Qy). The protocol is as follows:
1. The encoder receives the input = x ~ Px and selects its value using ERS procedure:
kA ERS(W; Pr|x=a Qy);
(418)
and sends the batch index 1IA to the decoder. It then sets YA = YKa
2. Given X z, YA y. we generate
Pz x, y) and note that the Markov
chain Z X YA) W holds.
3. The decoder receives the batch index KI.A and Z = will use the Gumbel Max process to queries a sample from the common randomness W:
Ki = KI,A K2,8 = (Gumbel(BR.... Priz=z, KB = (Ki,a- 18.-11am 1)N + K2,n,
and output YB YKg- The procedure Gumbel(.) corresponds to Step 1,2 in Algoirhm 1
Given the above setup, we have the following bound on the matching event (VA YB}: Proposition G.1. Let KA, Kn, (y x) and Priz(-12) defined above and set PA
Py|x=s; Pf = Pr|zz=- For 2 2, we have:
PZ(v) (1 (1+1(N))) (V())
Pr(VA= YB\Va = V = (1+1((N)+
(419)
where 14 (N) and p (N) are defined as in Appendix G.I and we note that (N), (N) + 0 as
N 00 with rate N under mild assumptions on the distributions Py|x (y) and Qr
Proof.
See Appendix G.2
G.1 Coefficients in Proposition G.1
We define the coefficient μú (N) and (N) in Proposition G.1
3w
(((N)= N
(420)
Pb(N)= = N
IN (w, 2)dz(Qr ||
(421)
where we define [w, A (21N>i + w1 N=t) as in Proposition F3 and w = max, Q2())
Pvix(sla)
G.2 Proof of Proposition G.1
We now formally prove the bound Proposition G.I First, we define:
N
(
Priz(ui>>) Qr(v))
2(Prix -x: V1:N) Σ
2(Pr) 21:N)
(422)
Qy(v.)
52

---

Recall that K2,4 is the local index within the selected batch by party A and Yx, A.1.W are the samples within the selected batch, we have:
Pr(Ya= = Yn = y, X = z, 2 = 2)
(423)
Pr((YA =KKnIKA -11 I. Z 2)
(424)
2 Pr((22, = K2,B\Kk -91, x=
= I, Z = 2)
(425)
N
Σ P K2 = =iYKk = =,1, X = 2, =
(426)
==1
= N Pr(K2,11 = K2,B = KY = y1, X == =x, =
(Due to Symmetry)
(427)
N PP((K2, K2, = 111, K2,1 =
x Pr((2,,1 = =K = =,,, x2,
(428)
Pr(K2, KK, 91, K2,1 =1,X= x,7=
1,x=
(429)
[ P(YKLA...N 12:N YYA V1, K2,4 1,X = xx =2
x PI(K22, K2,B\KK, 11, K2A 1, 2. N, X x, 2)dy2NN, (430)
where 429 is due to Pr(K2, = 1|YK,, = 1/1 X = 8, 2 = =) = N-1 Let VI:N ~ Q are N i.i.d.
proposal samples, then (YKA,I:N V1.N) {Yi:N -1:N. accepts Y1.V3 and we have:
Pr(K2.A = K2 VKA- = 81, K2. = 1, A, = ; X = 2, = 2)
(431)
Pr(K2,B # A = VI,N, K2,1 1, YK.- = y1, X x, = 2)
Sj
S
Pr(min 1#1
VE:N VI:N, A selects 1st index,
Priz(ug12)
(r))(u]
(2x:8L)))
(Pyizzznl W1NN)
A accepts Y1:N YK. = 1/1 X = x, 2 =)
(432)
S
S1
Pr(min
Y1:N = 1/1.N, A selects 1st index,
141
Priz(1:13)
Priz (x)
P(Py n=
Z (
A accepts YI.N YRA- - V1, x))
(433)
S
S Priz(en
1 Pr
min j+l
VYN V1:N, A selects 1st index, X
Py 2 (=))=)
Z Pr 12 M..N)
2(Py (8mm11111
(434)
Prix (v1 (z)) ((Py)Z=e.B1.) W1:N)
2 1+
(435)
Pr12(1112) ( (Prix==x V1.N)
where (43 due to Markov property Z Y) W.i.. has no effects on the statistics of the exponential random variables. Line (444 is due to the fact that conditioning on A selected the 1st index, whether A selects Yi.N or not depends only on U. The final inequality is due conditional matching lemma from 35
Recall that w max,
Prix(vla) we have: Qr())
P(KRAANN U2.N -/ K2, 1,X xx, =,,=,, x
(436)
P(YKIAZNN = V2.N/YKa 91, -1, K2.4 = =1,
(437)
PY.KaAIX(UI.. (UIN, 1/x0)
(438)
Prix (V11z)N-1
N2y()
(439)
APriXEr (2 V2.N) + +w)
where PY,K,, lx (VIN, 1/x) is the ERS target distribution 151
where we use 2r]x(112) as the target distribution and A Aprxxze is the normalized constant. We now shorthand Pd & Pr|x=z
53

---

Pp A P(Y|Z Z = 2) and A rg - P and combining the two expressions, we have:
Pr(YA YBLYA y1, X 2, I =)
(440)
N
2 Qr
(441)
(2(PA. V2.N) + w R2 1
P (vn) Z(P M1.11
pp (vl) Z(PG.ML.N)
N
2 Ev
(Since pg S 1)
(442)
(2(PA. (2:4) +w) 11+
(V)) 2(PF.OLN) .ULN)) (v1) 2(P 2(PA.0riN)
(2(PA, 12:N) + +w) N
1+ (v11) 2(PP, ((PP.VEN))
(v/1 2(P4, (.NN) ))
Qy
By Jensen's 's Inequality)
(443)
Since:
Z(P 12.NN +
N N-1
BvaiN~Qv
(444)
N
N
and:
(PA (2.N) +w N
2(P vIAN)
(445)
2(P V1.N)
İ(PA U2:N)
[(P V1:N)
(PP v1:N)
=EYNN~QV
(446)
N
Z(PA.2IN)
N ((PA,NINN)
N 1
( + EYaNN
2(PB .
(447)
S(PA,yinn)
where we have:
2(P8 v1:N) (PA )1NN)
P9(er)/Qr(1) (1r)
2(P v22N)
E EYnNoQQ
Eva.~Qu
(448)
Z(PØ 2(PA.VIN) VIIN)
(P M1NN)
(r(
2(PB y2.N)
S EvaNN~
(x))))(((n))
7(P%) (2:N)
(449)
Pf 2x)
(450)
(+())
Then, combining (450) into 447
then combine with (444) into the term 443 we have:
Pr(Y = Y V1,
X
xx 2 2)
(451)
1+ w (v1)
N
(f(r))/Qi Q
w
(P1)
+Ix(w, 2,d0212))((111123)
N P#(v1)
N
N
N (11)
(452)
-11 1+ w (in)
NN-1 PB
(
(1)(1) (Pt)))
+
w
+IN 2)x(w.)dd,(0r11P))
N
P+(())
N
N N
(453)
1 3w
+ (a(
(1+ w 1 (1W.2))(0)111
2
(454)
N
Pd (v1)
1 + uh (N) + Pf(mn
(1 (1+
(455)
where we repeatly use the fact that (v) (v) S w. This completes the proof.
54

---

H Proof of Proposition 5.6
Algorithm 2: Wyner-Ziv Ziv Distributed Compression Protocol
Encoder: Receives X and W, performs:
1. Select A P Qy:); 2. Sends (K1,A, VKA) ) to the decoder.
Decoder: Receives Z (VKA= Ki,,, X') and W, performs:
Keep batch K1,4; 2. Remove all j where VKi,a.5 + VKai
Select Kg with Prrx'
Main Proof. We remind the protocol in Algorithm
2 The encoder and decoder's target distribution
for this case are:
(u = (ylx(()
(456)
For sufficient large batch size N and apply Proposition G. we have:
Pr(Yka # YY KYKK VRA) ( x, = (I',
(457)
Pr((YKA VRA) + (Ykm, VKK) VK,) (v' v), x, 2 -='', ()',
(458)
1 1+c+ (v)
(V'') (1+
(459)
Py Pr(x(11)) < [+E+V- (1+
(460)
(
( (+))
(1++) (v) (1)x))))
(461)
11--11 (1+c+V- (/ bxx bo (
(462)
Finally, taking the expectation of both sides yields the final result.
Coding Cost. In terms the bound on r, recall the following bound on batch acceptance probability:
N
N
Ex))) 7(1 L:N
(463)
By LN Py
()) [(1]
+
Here for = w, we have A 1 and thus the chunk size I. A in the ERS coding scheme is and thus do not need to send K₁. Using the fact that Bllog L] < 1, we have r < H[L] + 1 = 4bits by entropy coding with Zipf distribution 28
Compressing Multiple Samples. When compressing n samples jointly, let the rate per sample (without the overhead for batch communication) be where log(V)= nr' consider the following approximation:
Σ i(y/ix.) - i(y/ax)) x xI((X)
Then we have:
2 Ei (100:=))--)(((()))))))
(464)
2m(((x>'1'')->)
(465)
and thus, r' > I(X;Y' by increasing n we reduces the mismatching probability while maintaining the compression rate per sample. We visualize this in the experimental results with N = 29 in Figure 9
55

---

Matching Probahilities
1.0
0.8
30.6
d
2
0.4
Rate (bits)
Figure 9: Matching Probabilities with N 2 and jointly compressing 1,2,3 i.i.d samples respectively. Target distortion dy-1x = 0.008 for every samples.
I Feedback Scheme
In distributed compression, decoding errors can lead to significant average reconstruction distortion. To address this, feedback communication from the decoder can be employed to correct errors and enhance rate-distortion performance, as proposed [35). The feedback mechanism is identical for both ERS and IML, except that ERS additionally transmits the batch index to the decoder.
We recall that K 1,A and K2,A denote the batch index and local index, respectively, of samples selected by party A through the ERS sample selection. On the other hand, party B uses Gumbel-Max selection process to output its selected local index K2,B within the K1,4 batch, then the ERS process can be described as follows:
1. Index Selection. After transmitting the batch index KI,A, the encoder sends the loga least significant bits (LSBB of the selected index K2,4 the decoder.
2. Decoding and Feedback. The decoder outputs K2,8 3 and sends the loga (Ng/(N/V) most signifi- cant bits (MSB) of KB to the encoder.
3. Re-transmission. Based on the received MSB feedback, the index is correct, the encoder responds with an acknowledgment bit, say 1. Otherwise, it sends O along with the MSB of its selection to the decoder.
We note that, in this context, using LSB instead of random bits in step does not yield noticeable difference in performance. For the rate-distortion analysis, the rate is computed based on the total length of messages transmitted during index selection and re-transmission. including any acknowledgment messages. However, the rate of the feedback message is excluded from this calculation, which can be justified in scenarios with asymmetric communication costs the forward and reverse directions, such as in wireless channels.
J Neural Contrastive Estimator
our ERS scheme, the selection rule requires estimating the following ratio at the decoder side:
Si (gl where = K1,A.
KB argmin
(466)
ISKEN
Qy(Va)V-
where the normalization term can be ignored as it is the same for every sample in the batch Ki,A- Our goal is learn the ratio (Yuxla))//))) (Yx) from data. particular, we can access the data samples from the joint distribution Px,xx".
To this end, we construct a binary neural classifier N' T+exp h(y.z) which classifies if
input (y. xx) is distributed according to the marginal distribution Qy ) x (x) (positive samples) or the joint Py,x' (negative samples). Once converged, we can use the logits value h(y, x²) to compute
the log of the ratio of interest [22]. In particular:
h(y,x') x llog Prix (Ymlo')
(467)
Qr
56

---

This allows us to estimate the ratio without needing to obtain the exact ratio's iiio's value. Finally, to generate the positive samples, we simply generate Y ~ (.) and get random X' from the training data. For negative samples, we generate the data according to the Markov sequence X" - X Y. The ratio between the two labels should be the same.
K
Distributed Compression with MNIST
K.1 Training Details
3- VAE Architecture. We adopt setup similar to 35 Our neural encoder-decoder model comprises an encoder network y = enc(æ), a projection network proj(='), and a decoder network & = dec(y, proj(x')), as detailed in Table 1 The encoder network converts an image into two vectors of size 3 (total 6D output), with the first vector representing the output mean ju(z)) and the second representing the output variance o² (x)). Here, we define py1x (-|ær) = =N((()), of (ar) and use the prior distribution (.). = (O, 1). At the decoder side (party B), the projection network first maps the side information image X'
228ddimensional vector, which is then combined with a 3- 3-dimensional vector from the encoder. This concatenated vector is input to the decoder network, producing a reconstructed output of size 28 x 28.
Table I: Architecture of the encoder, projection network, and decoder for distributed MNIST image compression. Convolutional and transposed convolutional layers are denoted as "conv" and "upconv," " respectively, with specifications for the number of filters, kemel size, stride, and padding. For "upcoovv" an additional output padding parameter is included.
(a)onee Input 28 x 28 x 1
(b)Projection Network
(c)Decoder Network
Input 14 x 14 X
Input-(3-+129
conv (128:3:1:1), ReLUU
conv (32:3:1:1), ReLU
Linear-(132,5))) 512), ReLU
conv (128:3:2:1), ReLU
conv (64:3:2:1), ReLU
upconv (64:3:2:1:1), ReLU
conv (128:3:2:1), ReLU
conv (128:3:2:1), ReLU
upconv (32:3:2:1:1), ReLU
Flatten
Flatten
upconv (1:3:1:1), Tanh
Linear (6272, 512), ReLU Linear (512, 6)
Linear (2048, 512), ReLU
Linear (512, 128)
Loss Function We train our 3-VAE network by optimizing the following rate-distortion loss function: L= 3 x²2 + Ex (Px
(468)
where we vary 3 for different rate-distortion Eadcoff.EEchh model is trained for 30 epochs on an NVIDIA RTX A4500, requiring approximately 30 minutes per model. We use random hor- izontal flipping and random rotation within the range +15". We use the following values of
e (0.225, 0.28, 0.31, 0.4) that corresponds to the target distortions f6.6, 6.1,5.8) 10-2 in
Figure 6
Neural Contrastive Estimator Network. The neural estimator network comprises two subnetworks. The first subnetwork projects the side information into a 128-dimensional embedding. The second subnetwork combines this 128D embedding with 4D embedding, derived from either py or the prior py, and outputs the probability that X', Y originate from the joint or marginal distributions. The model is trained for 100 epochs.
Table 2: Neural Estimator Networks for Distributed Image Compression.
(a)Projection Network
(b) Combine and Classify
Input 14 x 14 x
Input 128 Linear (132, 128), I-ReLU
conv (32:3;1:1), ReLU
conv (64:3:2:1), ReLU
Linear (128, 128), 1-ReLU
conv (128:3:2:1), ReLU
Linear 122), I-ReLU Linear (128, 1)
Flatten
Linear (2048, 512), ReLU Linear (512, 128)
57

---

Rate (bits/image)
Model
Embedding MSE
Pixel MSE
8.75
Gaussian Regressor
0.7300
0.0696
ERS (NCE)
0.6024
0.0683
9.60
Gaussian Regressor
0.5260
0.0660
ERS (NCE)
0.4807
0.0647
10.10 10
Gaussian Regressor
0.4310
0.0638
ERS (NCE)
0.3616
0.0623
10.60
Gaussian Regressor
0.3600
0.0626
ERS (NCE)
0.2930
0.0606
Table Comparison of Gaussian regressor vs. ERS (with NCE) under different rates. Distortion is reported as MSE (lower is better).
log V
N
Target dB
9.6
0.6e6
1.0e6
-21.5dB
10.6
0.7e6
1.1e6
-22dB
11.6
0.8e6
1.5e6
22..5BB
12.6
1.04
1.6e6
-23dB
Table 4: Details for ERS Gaussian Experiment Figure (right)
K.2 Decoder Estimation with Neural Contrastive Estimator: Gaussian Assumption for PML
In experiment, the decoder uses NCE to directly estimate the likelihood ratio without assuming a specific form-suchh as Gaussian- for the posterior. Consequently, computing the local constant needed for PML becomes intractable. If we instead assume a Gaussian form, PML becomes feasible; however, our experimental results show that this assumption introduces a mismatch that worsens the rate-distortion tradeoff.
Table 3 reports the distortion results across different rates. Here, Embedding MSE refers to the error measured with respect to the encoder's neural network output, while Pixel MSE captures the distortion at the image level. Lower values indicate better performance.
L Wyner-Ziv Gaussian Experiment
In Figure 5 (left), the batch size of ERS N E {219, 220) respectively for the average number of proposals N E {1.1, 1.6} x 10 For Figure (right), details for ERS are shown Table 4
M Additional Experiment on CIFAR-10 Dataset
We conduct experiments the CIFAR-10 dataset and compare our method with implicit neural representations [20]. the quantization approach (2), and the IML (35). We use Mean Squared Error (MSE) as the distortion metric across all schemes, where lower values indicate better performance. Our approach consistently achieves lower distortion by leveraging side information within the encoding scheme.
Table 5: Comparison of distortion (MSE) on CIFAR- 10 at different rates (bits/image). Lower is better.
Rate (bits/image)
Ballé et al. [2]
RECOMBINER 20
IML [35]
ERS Ours
0.0972
0.0968
0.0711
0.0703
10
0.0915
0,0912
0.0668
0.0659
0.0802
0.0810
0.0621
0.0606
58


Reviews:
[{"review_id": "WNael7eqC0", "reviewer": "Reviewer_AAcC", "summary": "This paper introduces a new framework for channel simulation and distributed compression using Ensemble Rejection Sampling (ERS), a generalization of standard rejection sampling (RS). It addresses two central problems: сhannel simulation and distributed matching.\nKey contributions include:\n- A novel RS-based compression method achieving coding costs close to the mutual information bound.\n- A distributed matching lemma for ERS, extending prior work like the Poisson Matching Lemma (PML) and Importance Matching Lemma (IML).\n- Bounds and empirical validation on synthetic data (Gaussian sources) and MNIST image compression tasks.", "questions": "- Channel simulation. What is the main task? Communicate a sample $Y$ or generate it from $P_{Y|X}$?\n- Distributed matching. Please mention why the probability (2) is of the most interest. Am I right that $P_A$ and $P_B$ are discrete distributions? \n- How does the choice of batch size N in ERS affect practical runtime and memory usage in large-scale settings?\n- Can ERS be directly extended to domains beyond images, such as video or NLP, where the proposal and target distributions may be more complex?\n- How would ERS perform in scenarios requiring privacy-preserving sampling (e.g., differential privacy)?", "limitations": "The experiments are limited to synthetic Gaussian sources and MNIST. Including more complex or real-world datasets (e.g., CIFAR, ImageNet) could strengthen the empirical claims.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\nThe paper is well-written and clearly outlines its contributions in a structured manner, supported by theory and experiments. Also I would emhasize the presence of theoretical justification and well-structured proofs.\n\nWeaknesses\n- While the theoretical complexity is discussed, practical runtime and memory overhead for ERS (especially in high-dimensional settings) could be elaborated further.\n- The experiments are limited to synthetic Gaussian sources and MNIST. Including more complex or real-world datasets (e.g., CIFAR, ImageNet) could strengthen the empirical claims.\n- Broader potential implications (e.g., in privacy-preserving communication or edge AI) could have been mentioned.\n- There are several typos, e.g. simmulation", "was_revised": true, "final_justification": "The authors carried out more experiments and addressed all my questions", "rebuttal": "Thank you for your thoughtful review and positive feedback. We appreciate your recognition of the theoretical justification, well-structured proofs, and clear presentation of our contributions. You can find your questions addressed below.\n\n**(1) Additional Experiment on CIFAR-10 Dataset**\n We conduct the experiments on the CIFAR-10 dataset and compare our method with the implicit neural representations [A3] , quantization approach [A7] and Importance Matching Lemma (IML). We use Mean Squared Error (MSE) as the distortion metric across all schemes, where lower values indicate better performance. Our approach consistently achieves lower distortion by leveraging side information within the encoding scheme.\n\n| Rate (bits/image) | Balle (2018) [A7] | RECOMBINER (He 2023) [A3] | IML (Phan 2024) [33] | ERS (Ours) |\n|-------------------|--------------|------------------------|------------------|------------|\n| ~9                | 0.0972       | 0.0968                 | 0.0711           | **0.0703** |\n| ~10               | 0.0915       | 0.0912                 | 0.0668           | **0.0659** |\n| ~11               | 0.0802       | 0.0810                 | 0.0621           | **0.0606** |\n\n**(2) Details about Channel Simulation**\nIn the context of our work, the main task of channel simulation is compressing a noisy sample $Y \\sim P_{Y|X=x}$ of the input $X = x $ from the encoder , which will be then transmitted to the decoder. In the setting we consider, both parties share a source of common randomness $W $, which corresponds to a shared random seed in practice. The encoder employs a sampling algorithm—such as (ensemble) rejection sampling, importance sampling, or Poisson functional representation—to select the sample $ Y $ using $ W $. Once $Y$ is selected, the goal is to encode the index of $Y$ in $W$ to be close to the theoretical limit $I(X;Y)$ and communicate this message to the decoder. Since the decoder has access to $W$, it can retrieve the value $Y$ after decoding the index from the message.\n\n**(3) Details about Distributed Matching Quantity**\nThe probability in (2) is of interest because it quantifies how likely both parties are to select the same index, given their respective target distributions $P_A$ and $P_B$. This quantity plays a central role in the distributed compression setting. Since many distributed compression and communication problems can be characterized as specific instances of distributed matching (Figure 1.c), this quantity can be used to derive one-shot achievability results for a range of compression and communication settings [25]. We further note that this setup is related to the coupling problems in statistics and computer science and have found many applications therein.\n\n**(4) The choice of batch size N in ERS**\n\nIn the context of distributed compression using ERS, setting the batch size as $N = 2^{\\mathbb{E}[D_{\\mathrm{KL}}(p_{Y|X}(\\cdot|x) \\,\\|\\, q_Y(\\cdot))] + 4} $ is sufficient to ensure a low $ \\mathcal{O}(1) $ coding cost for the batch index. This choice is motivated by the analysis of the number of samples required in importance sampling [6]. Empirically, the algorithm typically terminates within 2 to 4 batches, resulting in a constant $\\mathcal{O}(1)$ coding cost. This enables efficient encoding of the batch index using unary coding. Notably, this choice is more efficient than relying on the global constant $\\omega$ from Proposition 5.6, which provides a conservative bound for the general achievability result. Importantly, the validity of the output samples is preserved regardless of the specific value of $N$.\n\nIn our experiments, when jointly compressing a 4D Gaussian vector as described in Section 6, this configuration requires approximately $ 2^{24}$ proposals, which are parallelized and executed on a single A4500 GPU with 20GB of memory. The average encoding time is under one second per sample. Further improvements can be achieved by incorporating techniques such as space partitioning [19]. Since larger values of $N$ reduce the overhead in batch index encoding, it is beneficial in practice to increase $N$ as much as GPU capacity allows, in order to maximize parallelism.\n\n**(4) ERS on domains beyond images**\n\nThere are several existing works showing promise in scaling channel simulation techniques to high-dimensional data, which we believe can benefit ERS. For example, [A1, A2] demonstrate how to compress high-fidelity images using channel simulation methods applied to diffusion models. In particular, [A2] introduces a custom CUDA kernel that exploits parallelism to encode images in under 10 seconds. These methods outperform traditional quantization techniques by better preserving perceptual realism. An additional advantage is their natural compatibility with diffusion models, a leading approach in image generation. Given the strong performance of diffusion models in video generation, we believe similar extensions of channel simulation techniques to video are feasible. Beyond diffusion models, channel simulation has also been applied to implicit neural representation methods for image compression, demonstrating promising results. For example, [A3] applied channel simulation techniques to video compression problems, and such approaches may potentially be extended to other modalities as well.\n\n**(5) ERS in privacy-preserving setting**\n\nSeveral existing works have applied channel simulation techniques to differential privacy problems [A4, A5], suggesting that our ERS framework can also be extended in this direction. Moreover, since our scheme is inherently designed for distributed compression with distribution preservation, it opens up the possibility of incorporating differential privacy into distributed compression—an exciting direction for future research, particularly in practical settings such as vertical or clustered federated learning [A6].\n\n\nWe hope that our rebuttal address your concerns. Please let us know if you have any additional questions.\n\n\n**References**\n\n\n[A1] Vonderfecht, J., & Liu, F. Lossy Compression with Pretrained Diffusion Models. In The Thirteenth International Conference on Learning Representations.\n\n[A2] Yang, Yibo, Justus Will, and Stephan Mandt. \"Progressive Compression with Universally Quantized Diffusion Models.\" The Thirteenth International Conference on Learning Representations.\n\n[A3] He, Jiajun, et al. \"RECOMBINER: Robust and Enhanced Compression with Bayesian Implicit Neural Representations.\" The Twelfth International Conference on Learning Representations.\n\n[A4] Shah, Abhin, et al. \"Optimal compression of locally differentially private mechanisms.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2022.\n\n[A5] Liu, Yanxiao, et al. \"Universal exact compression of differentially private mechanisms.\" Advances in Neural Information Processing Systems 37 (2024): 91492-91531.\n\n[A6] Kim, Heasung, Hyeji Kim, and Gustavo De Veciana. \"Clustered federated learning via gradient-based partitioning.\" Forty-first international conference on machine learning. 2024.\n\n[A7] Ballé, Johannes, et al. \"Variational image compression with a scale hyperprior.\" International Conference on Learning Representations. 2018."}, {"review_id": "9TFety18KA", "reviewer": "Reviewer_VjgP", "summary": "This paper studies problems of channel simulations and (distributed) matching probabilities. Although PFRL and PML-based coding schemes can achieve near-optimal coding rates for these problems, they are impractical as they require an infinite number of proposals (unbounded termination time). To address this issue, the authors have developed a new coding technique for RS (for distributed matching) and ERS (for both channel simulation and distributed matching), demonstrating that it can achieve near-optimal performance for the considered problems. The practicality of the proposed approach is demonstrated through experiments.", "questions": "-\tAs mentioned by the authors, the main pitfall of PMC-based approach is their termination time. However, when using RS or ERS in practice, it is also necessary to choose a maximum termination time.\n\nTo better explain this; consider Proposition 4.1. that establishes a bound that is independent of $\\omega$. This means that letting $\\omega \\to \\infty$ does not induce any (considerable) penalty for the coding rate. However, this comes at the cost of a larger $K$; hence more common randomness and larger delays. For example, even when the intended $K$ is found, in this scheme to send $\\hat{K}$, one must wait until end of the group (of size $\\lceil \\omega \\rceil$) in which $K$ is located, in order to sort them. Thus, in practice, for large values of $\\omega$, an upper limit must be set. The question then is what effect such a limit has on the quality of the simulated sample.\n\n-\tIt is unclear what benefit ERS has over RS for channel simulation problems. In other words, what benefit does the analysis offer for general $N$? As mentioned by authors, the analysis for $N=1$ and $N=\\infty$ is similar to that in previous works.\n\n-\tIn [39], the issue of unbounded termination time in PFRL for channel simulation is addressed using a simple Gumbel-max trick. Could a similar approach be used for PML-based coding schemes and the distributed matching problem?\n\n-\tThe definition of $\\mu_1'$ is deferred to Appendix F.5. Is it referred to as $\\mu_1^{cond}$ therein? If so; they do not only depend on $N$; but also on $\\omega$ and distributions. It would be better to at mention this.\n\n-\tAs he authors mentioned, the main contribution of the paper is the analysis of ERS for matching probability. However, if I understand correctly, it has not been used or verified in the experimental part. Moreover, I do not fully understand why, in the context of 'lossy compression', one would be interested in matching probability in Proposition 5.6. Instead, one should be interested in the incurred distortion, as considered in the experiments.\n\n-\tI am also concerned about the practicality of these approaches in real life, for example in image compression, where the distributions are unknown and the data is high-dimensional. In the experimental section of the paper, an example is given of a neural contrastive estimator being used to approximate the ratio. However, such approaches perform poorly in the high-dimensional regime. This limitation is not specific to this paper, but to similar papers as well. Do the authors have any suggestions for how such approaches could be used in real-life applications?\n \nSome of the typos: some mispelled words such as `Simmulation`, missing space at line 318, many places $\\ldot$ should be replaced by $\\cdot$, e.g. $\\mu(\\cdot)$ in line 323.\n\n=======================\n\nPOST REBUTTAL:\n\nThis is a rather interesting paper. There are still some minor concerns on the computability of the log density ratio in high dimension; but given the clear nature of this paper, which is theoretic, and the technical novelty, I vote for acceptance.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "On the strong points:\n\n-\tThe new coding technique and its analysis for RS are novel and interesting.\n\n-\tSimilarly, the analysis for ERS, particularly for distributed matching problem is involved and novel.\n\n-\tThe proofs appear correct and rigorous to me. (I have not gone through all the proofs; but even those over which I could not go in details I have glanced over them.)\n\nOn the weak points:\n\nFor details, please refer to the below `Questions' section.\n\n-\tThe benefits of ERS and the proposed coding schemes require further elaboration.\n\n-\tThe application of the proposed approach to machine learning problems is not discussed in detail and remains unclear. For a paper submitted to a top-tier ML conference I feel that this aspect should be largely improved. For the moment the paper appears to be more suitable for a conference such as ISIT or the Info. Theory Transactions.\n\n-\tThe boundedness of the ratio can be restrictive in practice; as one needs to ensure this by using a very large $\\omega$; which results in longer delays.", "was_revised": true, "final_justification": "This is a rather interesting paper. There are some concerns on the computability of the log density ratio in high dimension; but given the clear nature of this paper, which is theoretic, and the technical novelty, I vote for acceptance if room.", "rebuttal": "Thank you for your thoughtful review and for highlighting the novelty and rigor of our RS and ERS coding techniques, as well as the strength of our theoretical analysis. Please find the answer to your questions below.\n\n**(1) Sample Quality for Truncated $\\omega$** \n\nWhen the constant $\\omega$ is truncated, we believe it is possible to characterize the quality of the generated samples. In particular, it suffices to consider inputs $x$ where the local constant $\\omega_x = \\max_y P_{Y|X}(y|x)/Q_Y(y)\\geq \\omega$, as sample quality remains unaffected otherwise. To the best of our knowledge, the effect of truncating the upper bound $\\omega$ has been studied in the contexts of rejection sampling (RS) and importance sampling (IS), but not for PMC. For $N = 1$, which corresponds to standard RS, existing early stopping techniques [A6] can be applied to derive bounds on sample quality. When $N > 1$, ERS incorporates an IS step, allowing similar analyses from [6,39] to be adapted for bounding the sample quality under ERS. We note that PMC remains the primary competitor for generating unbiased samples with high matching probability and this point showcase another advantage of our scheme over PMC that we will put a discussion in the revision.\n\nFinally, in terms of terminating condition in the distributed compression application there is an important practical advantage that ERS has over PMC as discussed in reponse to Question 1 for Reviewer MpW9 (answered in points (3) and (4) in our rebuttal to their). \n\n**(2) Benefits of ERS over prior methods and RS**\nThe motivation for developing ERS is to improve the matching probability of RS and its greedy variant, i.e. Greedy Rejection Sampling (GRS), which alone are not competitive, also demonstrated in the examples of Figure 4 and Appendix D.2. To address this, ERS integrates RS with IS—an approach known for achieving high matching probabilities, albeit with biased output samples. In this sense, ERS combines the best of both worlds: high matching probability and unbiased output samples. We highlight several advantages of the ERS scheme over existing approaches:\n- Compared to the Importance Matching Lemma [33], ERS generates exact output samples, leading to improved performance in low-distortion regimes for distributed compression, as shown in Section 6.\n - Compared to GRS  and standard RS scheme [12], ERS consistently achieves higher distributed matching probabilities.\n- Compared to the PML scheme for distributed compression with high-dimensional data, our ERS-based coding scheme with neural networks effectively addresses the decoder-side termination issue, which the original PML scheme does not fully resolve.\n\nIn channel simulation, ERS has the potential to offer additional advantages over standard RS. There exists a substantial body of research aimed at improving the sample efficiency of IS, such as multiple IS and quasi-Monte Carlo. As ERS incorporates an IS within its procedure, we believe these advances could be effectively integrated to further enhance the efficiency of the ERS framework. \n\n**(3) The choice of $N$**\n\nFor the distributed compression, the choice of $N$ is crucial for the performance. If $N=1$, we will have a low matching probability. On the other hand, setting $N$ very large will lead to high computational overheads. For any $N$, the scheme is feasible and the right choice of $N$ is to obtain the balance between matching probability and computational complexity. Our experiments suggest that setting the batch size as $N=2^{\\mathbb{E}[D_{\\mathrm{KL}}(p_{Y|X}(\\cdot|x) \\,\\|\\, q_Y(\\cdot))]+4} $ is sufficient to achieve low coding costs for the batch index. This choice is not arbitrary—it aligns with the number of samples typically required to ensure low bias in IS [6]. With this, ERS usually terminates within just 2--4 batches. Thanks to this $\\mathcal{O}(1)$ coding cost, the batch index can be efficiently encoded using unary coding and is more practical than relying on the global constant $\\omega$ introduced in the theoretical analysis of Proposition 5.6, which primarily serves to make the rate analysis tractable. Importantly, the correctness of the generated samples is maintained for any choice of $N$.\n\n**(4) Gumbel-Max trick and Matching Lemmas**\n\nIn  [39], the technique known as Ordered Random Coding utilizes the Gumbel-max trick to address termination time. However, this method inherently produces biased samples due to its reliance on IS (see Corollary 3.2 in [39]). In contrast PFRL is an exact sampling scheme that generates unbiased samples (unlike the approach in [39]). An extension of this approach to matching scenarios as you described was introduced by Phan et al. [33], known as the Importance Matching Lemma (IML), which also produces biased samples. Our work directly extends the work by Phan et al. [33], which serves as a baseline we compared against in Section 6. The primary distinction of our approach compared to those in [33, 39] lies in our method of generating unbiased samples by combining IS with RS, and achieving better empirical performance in the Section 6. In particular, the results in Section 6 demonstrate that ERS outperforms IML in distributed compression scenarios.\n\n**(5) Definitions of $\\mu$** Thank you for pointing this out. We will revise and adjust this.\n\n**(6) Verification of Matching Probability and Implication in Lossy Compression.** We verify of the general matching probability in Proposition 5.4 with empirical comparisons of different methods presented in Figure 4. For Proposition 5.6, we report empirical matching probabilities under joint compression of multiple samples in Figure 9 (Appendix), which also illustrates the phenomenon described in Remark 5.7. We note that the matching probability is a central quantity in distributed compression, directly influencing the rate-distortion tradeoff. Our experiments involving distributed compression are designed to validate the performance gains attributed to improved matching probabilities. Schemes that fail to achieve high matching probability—despite being efficient for channel simulation such as RS and GRS—do not yield competitive rate-distortion performance in the distributed setting.\n\nFinally, result in Proposition 5.6 can be translated into related quantities, such as the probability of excess distortion, as discussed in [25]. This can be used to derive bounds on the expected distortion for bounded inputs, which we will incorporate in the revision. Since matching probability is a central quantity in the distributed compression setting, we characterize it in Proposition 5.6. This is consistent with the IML/PML baseline  and Proposition 5.6 serves as a counterpart result within our framework.\n\n**(7) Scaling Channel Simulation-Based Approaches**\n\nChannel simulation is increasingly applied to high-dimensional datasets. In image compression, [A1, A2] use it within diffusion models to achieve competitive performance on 512×512 images with < 10 second encoding, outperforming traditional quantization in perceptual quality. It is also effectively combined with implicit neural representations, which have shown superior results over quantization-based methods [A8].\n\nFurthermore, the application of channel simulation extends beyond lossy image compression. It has been explored in areas such as differential privacy [A3] and quantum communication [A9]. Recent works  [A4, A5] also apply similar distributed-matching techniques to accelerate inference in large language models, showcasing the growing interest of using such techniques for machine learning problems.\n\nRegarding the scaling of the neural contrastive estimator to higher dimensional data, a practical workaround is to partition the input into smaller chunks and train a separate neural contrastive estimator on each subset. Furthermore, state-of-the-art methods for density estimation are still rapidly evolving, as demonstrated by recent advances in multimedia generative models. Nonetheless, in applications such as vertical federated learning—where feature dimensionality does not increase as quickly as in image-based tasks—channel simulation-based approaches remain both practical and directly applicable. Overall, scaling channel simulation to high-dimensional data is an active and promising research direction (see [37], [A7]).\n\nWe hope the reviewer is convinced about the strength of our scheme over prior methods.\n\n**References**\n\n[A1] Vonderfecht, J., & Liu, F. Lossy Compression with Pretrained Diffusion Models. ICLR 2025.\n\n[A2] Yang, Yibo, et al. \"Progressive Compression with Universally Quantized Diffusion Models.\". ICLR 2025\n\n[A3] Liu, Yanxiao, et al. \"Universal exact compression of differentially private mechanisms.\". NeurIPS 2024\n\n[A4] Kobus, Szymon, and Deniz Gündüz. \"Speculative sampling via exponential races.\" arXiv preprint arXiv:2504.15475 (2025).\n\n[A5] Rowan, Joseph, Buu Phan, and Ashish Khisti. \"List-Level Distribution Coupling with Applications to Speculative Decoding and Lossy Compression.\" arXiv preprint arXiv:2506.05632 (2025).\n\n[A6] Block, Adam, and Yury Polyanskiy. \"The sample complexity of approximate rejection sampling with applications to smoothed online learning.\" PMLR, 2023.\n\n[A7] Jiajun He, et al.  \"Accelerating relative entropy coding with space partitioning.\" NeurIPS 2024\n\n[A8] He, Jiajun, et al. \"RECOMBINER: Robust and Enhanced Compression with Bayesian Implicit Neural Representations.\" ICLR 2024\n\n[A9] Steiner, Michael. \"Towards quantifying non-local information transfer: finite-bit non-locality.\" Physics Letters 2000."}, {"review_id": "oiup7zjmpT", "reviewer": "Reviewer_MpW9", "summary": "The authors propose a new coding scheme for channel simulation based on standard Rejection Sampling (RS) and extend this analysis to Ensemble Rejection Sampling (ERS). They derive the coding cost for both methods, showing that they are first-order optimal. The paper then applies ERS to the problem of distributed matching, for which the authors derive a new bound on the matching probability, establishing a counterpart to the Poisson Matching Lemma (PML) and Importance Matching Lemma (IML). The practical utility of the proposed ERS-based method is verified in a distributed compression setting on both synthetic Gaussian sources and the MNIST image dataset.", "questions": "1.  **Practicality of PML as a Baseline in the MNIST Experiment:** In the distributed image compression experiment, you argue that PML is inapplicable because the upper bound of the density ratio $p_{Y'|X'}(y'|x')/q_{Y'}(y')$ is unknown when learned by a neural network. However, this seems to warrant more discussion:\n\n    **1a.** PML, like PFR or GRS, only requires the *local* constant $\\omega_{B,x'} = \\sup_{y'} p_{Y'|X'}(y'|x')/q_{Y'}(y')$ at the decoder for a given side information $x'$. Since the decoder has access to the neural network representing these distributions (in this case a Gaussian), why can it not compute or tightly bound this local constant on the fly for each sample and use a PML-based scheme?\n\n    **1b.** Furthermore, your ERS scheme operates with a chosen group size, which is directly related to the density ratio. Could you clarify why the information implicit in the choice of group size cannot be used to parameterize a PML-based competitor for a direct comparison?\n\n2.  **Computational Cost of the Sorting-Based Coding:** The rejection sampling coding scheme has some similarities to PFR, where uniform random variables serve as arrival times (though it's not quite a Poisson process since $N$ is fixed). Can you think of a more computationally efficient method for coding the sample--ideally on the order of $\\omega_x$ ? Or must all the uniforms in the group be drawn every time? Finally, is there any downside, in terms of rate, to making groups larger than $\\omega$?\n\n\n### Minor Suggestions for Presentation:\n\n*   **Clarity of Indices:** The use of same letters for different indices (e.g., group index, batch index, local index) can be slightly confusing to follow.\n*   **Figure Readability:** The font size in the figures is smaller than the main text and can is difficult to read. Font size should be at least as large as the main text, ideally larger, to ensure clarity.\n*   **Context in RD Plots:** In Figure 5 (Right), adding a curve for the theoretical Wyner-Ziv rate-distortion bound would provide valuable context. It would help to assess the gap between all the practical methods and the theoretical limit.", "limitations": "Yes, the authors briefly mention improving runtime efficiency as a future direction. However, the paper would benefit from a more direct discussion of its two key limitations and their practical context:\n1.  The computational complexity can be significantly higher than competing methods since it depends on the global density ratio bound not a local one.\n2.  The requirement for this global bound to be known by both parties is a stricter assumption than that of several existing channel simulation schemes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "## Strengths:\n\n- **New Rejection Sampling Channel Simulation:** The paper introduces a novel coding scheme for standard Rejection Sampling (RS) based on grouping and sorting proposals. It bypasses the suboptimality of naive runtime-based coding for RS, achieving a near-optimal rate of $I(X;Y) + O(\\log I(X;Y))$.\n- **New Ensemble Rejection Sampling Channel Simulation** The authors extend the RS coding technique to Ensemble Rejection Sampling (ERS) and also show it to be near-optimal.\n- **New Distributed Matching Lemma:** A major theoretical strength is the derivation of a distributed matching lemma for ERS. This result serves as a new tool for one-shot distributed information theory, alongside existing Poisson Matching Lemma (PML) and the Importance Matching Lemma (IML). Its existence expands the toolkit available for analyzing distributed compression and communication problems.\n- **ERS Distributed Compression:** Authors show how ERS matching can be used for distributed compression with decoder-only side information, mirroring IML scheme. Unlike in IML, which produces biased samples, the chosen sample $Y$ comes from exact distribution.\n\n## Weaknesses:\n\n- **Dependence on Global Bounding Constant:** A practical limitation of the proposed RS and ERS schemes is the requirement that both the encoder and decoder know the global worst-case density ratio $\\omega = \\sup_{x,y} \\frac{p_{Y|X}(y|x)}{q_Y(y)}$ beforehand. This contrasts with schemes like Poisson Functional Representation (PFR) or Greedy Rejection Sampling (GRS) which do not require such a global constant to be known to the decoder. For PFR and GRS only the local constant is needed $\\omega_x = \\sup_y \\frac{p_{Y|X}(y|x)}{q_Y(y)}$ and exclusively at the encoder.\n- **Computational Complexity:** The average computational complexity of the proposed methods scales with the global constant $\\omega$, rather than the instance-specific ratio $\\omega_x = \\sup_y \\frac{p_{Y|X}(y|x)}{q_Y(y)}$. This can lead to significant inefficiency. Consider the following example: $p(y|x=0)=Unif[0,1), p(y|x=1)=Unif[0,c), p(x=1)=c$; average PFR/GRS computation $<2$, while average RS and ERS computation $>1/(2c)$ can be arbitrarily large.\n- **Looser Rate Bounds:** While the coding rates for both RS and ERS are shown to be asymptotically optimal (i.e., achieving the leading term $I(X;Y)$), the upper bounds contain larger logarithmic and constant terms compared to the current channel simulation methods, such as those shown by PFR ($I(X;Y) + \\log(I(X;Y)+1) + 4$).", "was_revised": true, "final_justification": "I maintain my 'Accept' rating.\n\nDiscussion with the authors clarified my misunderstanding about the different distributions required for distributed compression.\n\nThe limitations of the proposed scheme do not negate its valuable contribution. These include:\n1) an upper bound on excess functional information that is worse than PFR, and\n2) a computational complexity dependent on a global bounding constant, versus a local one for PFR and GRS--for channel simulation. For distributed matching, we do not know of a good alternative when utilising neural networks at decoder side.", "rebuttal": "Thank you for your thoughtful and detailed review. We appreciate your recognition of our theoretical contributions—including the new RS and ERS coding schemes and the distributed matching lemma—as well as the practical value of ERS in distributed compression tasks. Please find your concerns addressed below.\n\n**(1) Dependence on Global Bounding Constant/Computational Complexity** \n\nYour observation is indeed correct for the current scheme based on standard rejection sampling, where both parties must share knowledge of $\\omega$. In practice, the encoder can transmit this information prior to sending the actual samples, allowing the coding cost of $\\mathcal{O}(\\log(\\omega))$ to be amortized over time. \n\nMoreover, ERS provides several benefits compared to existing methods:\n- Compared to the Importance Matching Lemma, ERS delivers exact output samples, resulting in improved performance in low-distortion scenarios for distributed compression, as shown in Section 6. \n- Compared to the Greedy Rejection Sampling scheme, ERS also achieves better distributed matching probabilities, where GRS falls short. \n- Compared to the original PML scheme for distributed compression with high-dimensional data, our ERS-based coding scheme with neural networks effectively addresses the decoder-side termination issue, which the original PML scheme does not fully resolve (also see the answer for Question 1 below). \n\nWe further note that, in the context of distributed compression using ERS, choosing the batch size as $N = 2^{\\mathbb{E}[D_{\\mathrm{KL}}(p_{Y|X}(\\cdot|x) \\,\\|\\, q_Y(\\cdot))] + 4}$ is sufficient to ensure a low coding cost for the batch index. Empirically, the algorithm tends to terminate within 2 to 4 batches. This leads to a constant $\\mathcal{O}(1)$ coding cost, allowing the batch index to be efficiently encoded via unary coding. This is practically more efficient than using the global constant $\\omega$ described in Proposition 5.6, which serves as a conservative bound for the general achievability result. Importantly, the validity of the output samples is maintained regardless of the specific value of $N$.\n\n**(2) Looser Rate Bounds** \n\nOur experiments in Figures 2 and 3, conducted with actual distributions, indicate that the coding cost bounds stated in Proposition 4.1 and Proposition 5.1 tend to overestimate the cost observed in practice. This suggests that the theoretical bounds—particularly the one for ERS—can likely be tightened and the higher constants could be the consequences of our bounding techniques.\n\n\n**(3) Practicality of PML: Compute Local Constant On The Fly**\n\nIn our scheme using ERS, the encoder requires an upper bound $\\omega_x$, which depends on the target distribution $p_{Y|X}$ and the proposal $q_Y$, to guarantee termination. Importantly, this constant is local to the encoder, and the scheme does not rely on $\\omega_{x'}$, the corresponding constant on the decoder’s side. In contrast, PML requires the decoder to compute $\\omega_{x'}$ to ensure termination, which demands further assumptions on $p_{Y|X'}$ and can degrade performance. This asymmetry highlights a key practical advantage of ERS over PML.\n\nIn our experiment, the decoder uses a neural contrastive estimator to directly estimate the likelihood ratio $\\frac{p_{Y'|X'}(y'|x')}{q_{Y'}(y')}$ without assuming a specific form---such as Gaussian---for the posterior $p_{Y'|X'}$. Consequently, computing the local constant $\\omega_{B,x'}$ needed for PML becomes intractable. If we instead assume a Gaussian form, $\\mathcal{N}(\\mu(x'), \\sigma(x'))$, PML becomes feasible; however, our experimental results show that this assumption introduces a mismatch that worsens the rate-distortion tradeoff. See the table below for further details, note that we are presenting MSE distortion for different schemes  and lower is better. Embedding MSE refers to the error measured with respect to the encoder's neural network output, while pixel MSE captures the distortion at the image level.\n\n\n| Rate  | Model              | Embedding MSE | Pixel MSE |\n|-------|--------------------|------------|-------------|\n| 8.75  | Gaussian Regressor | 0.7300     | 0.0696      |\n|       | ERS (NCE)          | **0.6024**     | **0.0683**      |\n| 9.60  | Gaussian Regressor | 0.5260     | 0.0660      |\n|       | ERS (NCE)          | **0.4807**     | **0.0647**      |\n| 10.10 | Gaussian Regressor | 0.4310     | 0.0638      |\n|       | ERS (NCE)          | **0.3616**     | **0.0623**      |\n| 10.60 | Gaussian Regressor | 0.3600     | 0.0626      |\n|       | ERS (NCE)          | **0.2930**     | **0.0606**      |\n\n**(4) Implicit Information in the choice of group size and PML**\n\nWe understand you are referring to the batch size $N$, chosen such that $N > \\omega$, where $\\omega$ denotes the global upper bound of the encoder’s density ratio. Please let us know if this interpretation is incorrect. Since $\\omega$ serves as a global constant for the encoder’s target distributions, we are not aware of any existing methods for inferring the decoder’s local constant $\\omega_{B,x’}$ based solely on $\\omega$. This is because $\\omega_{B,x’}$ requires an explicit knowledge of $p_{Y|X’}$, which is complex/intractable in general.  We will clarify this difference and add the presented experimental results above to clarify the advantage of our scheme over PML.\n\n**(5) Computational Cost of the Sorting-Based Coding**\n\nA key challenge is that the decoder does not know the value of $x$, and therefore the group size $\\omega_x$ is also unknown. As a result, encoding the sample using its runtime complexity $\\omega_x$ remains an open problem. While explicitly transmitting $\\omega_x$ would incur a high communication cost, exploring strategies where the sampling complexity adapts to $\\omega_x$ is a promising direction for future work, which we will highlight in the paper.\n\n**(6) Downside of making groups larger than $\\omega$**\n\nIn the proposed protocol, where each sample has an acceptance probability of $\\frac{1}{\\omega}$, the group size is set to $\\omega $ (or its floor value). If the group size exceeds $\\omega$, for instance, approaching infinity, the coding cost for $\\hat{K}$ will increase since there will be more uniform random variables whose value is smaller than the one selected by the rejection sampler (in terms of expectation). Technically, this is evident in equations (82-84) of the proof in the appendix, where replacing $\\lfloor \\omega \\rfloor$ (the group size) with extreme values will show the effect.\n\n**(7) Minor Suggestions for Presentation** \n\nThank you for your comment. We will incorporate these in the revised version.\n\nWe hope this clarify your concerns. Let us know if you have further questions."}, {"review_id": "EkFNrWULzS", "reviewer": "Reviewer_2a3z", "summary": "This paper proposes Ensemble Rejection Sampling (ERS) for channel simulation and distributed compression. Theoretically, ERS achieves near-optimal coding rates matching for channel simulation and distributed matching probabilities competitive with the Poisson Matching Lemma (PML) as batch size increases. Experiments on Gaussian sources and MNIST validate ERS’s advantages over importance sampling (IML) in bias reduction and distortion control.", "questions": "refer to Strengths And Weaknesses.", "limitations": "limitations and potential negative societal impact are not discussed.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. The paper provides significant theoretical advancements, including a new coding scheme for RS that achieves near-optimal rates and extends prior discrete results to continuous settings. \n\n2. Synthetic experiments show ERS outperforms IML in low-distortion regimes, and MNIST confirms lower MSE with unbiased samples.\n\n**Weaknesses:**\n\n1. Only simple datasets are tested and no high-dimensional or real-world benchmarks are adopted. The scaliability of ERS is unclear. Moreover, comparision to SOTA compression methods is missed.\n\n2. While the ERS matching lemma is new, core mechanisms, such as batching and Gumbel tricks, build heavily on prior IS/RS work.", "was_revised": true, "final_justification": "My concerns have been addressed. I will maintain my initial score.", "rebuttal": "Thank you for your review and encouraging comments. We're glad you appreciated the theoretical advancements of our ERS and RS-based coding scheme and the empirical benefits of ERS in both synthetic and real-data experiments. Please find your concerns answered below.\n\n**(1) Extra Experiments and Comparison to other Compression Method**  We conduct experiments on the CIFAR-10 dataset, comparing our ERS approach against the quantization baseline [A1], the implicit neural representation method [A2] (which is one of the recent state-of-the-art image compression method), and the Importance Matching Lemma (IML) [33]. We use Mean Squared Error (MSE) as the distortion metric across all schemes, where lower values indicate better performance. By effectively leveraging side information in the encoding process, ERS  consistently achieve lower distortion across all settings. \n\n| Rate (bits/image) | Balle (2018) [A1] | RECOMBINER (He 2023) [A2]| IML (Phan 2024) [33] | ERS (Ours) |\n|-------------------|--------------|------------------------|------------------|------------|\n| ~9                | 0.0972       | 0.0968                 | 0.0711           | **0.0703** |\n| ~10               | 0.0915       | 0.0912                 | 0.0668           | **0.0659** |\n| ~11               | 0.0802       | 0.0810                 | 0.0621           | **0.0606** |\n\n**(2) Technical Contributions** \n\nThe core technical contribution of our work is the development of new encoding schemes within the RS/ERS framework, which offer several key advantages over existing methods:\n- Compared to the Importance Matching Lemma (IML): ERS produces exact output samples rather than approximate ones, resulting in better performance, particularly in low-distortion regimes (see Section 6).\n- Compared to Greedy Rejection Sampling (GRS): ERS achieves substantially higher distributed matching probabilities.\n\n- Compared to the original Poisson Matching Lemma (PML): Our ERS-based framework, integrated with neural networks, overcomes the decoder-side termination issue that remains a challenge in the original PML design for high-dimensional data.\n\n\nBesides the development of new coding schemes, our contribution also includes substantial technical novelty in the analysis, with each core proof spanning over 10 pages. In particular, the achievability proof for channel simulation with ERS at an arbitrary batch size $N$ involves bounding a complex probabilistic integral arising from self-normalized importance sampling, without assuming any specific form for the target or proposal distributions [A3]. This derivation notably relies on a symmetry-based argument, rather than standard concentration tools such as Hoeffding’s or log-Sobolev inequalities, allowing us to establish an upper bound that holds uniformly over all values of $N$. The challenges of handling self-normalized importance sampling terms also arise in our analysis of the matching lemmas. Specifically, proving the bounds in Propositions 5.4 and 5.6 requires substantial analytical effort, involving intricate combinations of probabilistic reasoning as well as set-theoretic arguments.\n\n\n**(3) Limitations and Impact** We will include a more detailed discussion of the limitations and potential impact of our work in the main paper. Channel simulation techniques are commonly used in privacy-preserving applications, such as secure data sharing and communication, which contributes positively to societal impact.\n\n\nLet us know if you have additional concerns and we will address them. \n\n**References**\n\n[A1] Ballé, Johannes, et al. \"Variational image compression with a scale hyperprior.\" International Conference on Learning Representations. 2018.\n\n[A2] He, Jiajun, et al. \"RECOMBINER: Robust and Enhanced Compression with Bayesian Implicit Neural Representations.\" The Twelfth International Conference on Learning Representations.\n\n[A3] Agapiou, Sergios, et al. \"Importance sampling: Intrinsic dimension and computational cost.\" Statistical Science (2017): 405-431."}]

Author rebuttal:

Meta-review: This paper uses a generalization of standard rejection sampling, called ensemble rejection sampling, to improve the performance of "channel simulation" and "distributed compression", two communication problems. 

The paper is well received by the reviewer who favor acceptance and are happy with the answers provided by the authors.  Overall this is an interesting paper. My main concern is that the problems are disconnected with machine learning - however there is potential that the technique may be useful, because it is rather basic. So I recommend acceptance.
Decision: Accept (poster)