Universal Sample Coding
Authors: Szymon Kobus
Tze-Yang Tung
Deniz Gunduz
Venue: NeurIPS 2024 poster (2024)
Keywords: source coding
compression
sampling
channel simulation
federated learning
generative AI
Primary area: other
TL;DR: Communication of multiple samples from an unknown probability distribution and its applications to federated learning and generative inference.

Abstract: In this work, we study the problem of communicating multiple samples from an unknown probability distribution using as few bits as possible. This is a generalization of the channel simulation problem, which has recently found applications and achieved state of the art results in realistic image compression, neural network compression, and communication-efficient federated learning. In this problem, the transmitter wants the receiver to generate multiple independent and identically distributed (i.i.d.) samples from a target distribution $P$, while the transmitter and the receiver have access to independent samples from a reference distribution $Q$. The core idea is to employ channel simulation in multiple rounds while updating the reference distribution $Q$ after each round in order to reduce the KL-divergence between $P$ and $Q$, thereby reducing the communication cost in subsequent rounds. We derive a lower bound on the expected communication cost and construct a practical algorithm that achieves the lower bound up to a multiplicative constant. We then employ this algorithm in communication-efficient federated learning, in which model updates correspond to samples from a distribution, and achieve a 37% reduction in the communication load. To further highlight the potential of sample communication for generative models, we show that the number of bits needed to communicate samples from a large language model can be reduced by up to 16 times, compared to entropy-based data compression.

Universal Sample Coding
Szymon Kobus
Tze- Tze-Yang Tung
Dep. of Electrical and Electronic Engineering Imperial College London
Not Diamond tze aze-yyanggnotddimonn.. ai
szymon kos ac..u
Deniz Gündüz
Department of Electrical and Electronic Engineering Imperial College London
d. gunduz@imperial.comm ac. uk
Abstract
In this work, we study the problem of communicating multiple samples from an unknown probability distribution using as few bits as possible. This a general- ization of the channel simulation problem, which has recently found applications and achieved state of the art results in realistic image compression, neural network compression, and communication--ffiiiee the transmitter wants the receiver to generate multiple independent and identically distributed (i.id.)) samples from target distribution P, while the transmitter and the receiver have access independent samples from reference distribution Q- The core idea is to employ channel simulation in multiple rounds while updating the reference distribution Q after each round in order to reduce the KL-divergence between P and Q, thereby reducing the communication cost in subsequent rounds. We derive a lower bound on the expected communication cost and construct a practical algorithm that achieves the lower bound up multiplicative constant. We then employ this algorithm in communication waaeiiaatnonnofiinntttt efficieft federated learning, in which model updates correspond samples from distribution, and achieve 37% reduction in the communication load. To further highlight the potential of sample communication for generative models, show that the number of bits needed communicate samples from a large language model can be reduced by up to 16 times, compared entropy-based data compression.
federated learning. In this problem,
Introduction
Let P be a probability distribution known to an encoder, and we would like to obtain a sample X ~ P remote decoder what is the minimal number of bits required communicate from the encoder to the decoder? The obvious procedure is to sample from P at the encoder, compress it, and transmit over the network. The minimum number of bits necessary for lossless transmission of this sample is bounded by the entropy of distribution P, H(P) bits per sample. However, unlike in classical source coding theory, our problem, the decoder is interested only drawing of 'an arbitrary' sample from P. and not the particular sample generated at the encoder. If the encoder and decoder have access to samples from another reference distribution Q, then it is possible for the encoder to communicate sample from P using approximately DKr. (PIlQ) bits instead. Thus, if we are able to sample from distribution Q that close to P, the bandwidth required to communicate sample from P can be greatly reduced. This is known as 'channel simulation' or 'reverse Shannon coding' (Bennett et al.) 2002 Cuff 2008 Harsha et al. 2010).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

This result has recently been used in various neural compression problems, such as compression of images and neural networks (Havasi et al. 2019 Flamich al., 2020 Agustsson and Theis 2020 Theis et al. 2022), where non-differentiable quantization operation is replaced with reverse channel coding, which provides a differentiable step by utilizing the reparameterization trick. Another recent application of channel simulation is in federated learning (FI.). Many communication efficient FL methods require sending a sample from a client-only distribution after local training. Instead of deterministic weights, the models can be parameterized with probability distribution and the central server samples realizations from each client's ' updated model to construct the global model update. Recently, it was shown in Isik et al. (2023 2024) that the overall communication cost of sending the model updates from the clients to the parameter server can be greatly reduced using channel simulation, achieving state-of-the thrt results. In each iteration, the client can enable the parameter server to sample from its locally updated distribution while using the global model distribution as the common reference distribution. As the client's local distribution is typically close to the global model, the communication cost, proportional to the KL--divergence between the two, will will extremely low compared to deterministic alternatives. Channel simulation can also help in enabling differential privacy of the communicated models (Triastcyn et al.) [002]] Hasircioglu and Gunduz (024:) Hegazy al. 2024, Shahmiri et al., 2024) since allows for shaping the distribution of the noise.
In all the above works, the single-shot version of channel simulation is utilized; that is, a single sample is to be generated at the receiver with the desired distribution. In this work, are interested in studying the communication cost of sending multiple samples from the same distribution. This problem can directly find application in the FL framework, where the global model is estimated from samples of local models. A procedure to efficiently communicate more samples would allow the parameter server approximate the global model more accurately, which would reduce the noise and variance in its estimation, and speed up training.
Additionally, would like to point to strong conceptual connection between generative models and channel simulation, and propose an avenue of future research. Generative models are one of the most successful examples among the recent advances in machine learning. They include various modalities such as text (Touvron et al. 2023), images (Ho et al. 2020), video, and many more. They are trained to mimic some data distribution P based on samples X P drawn from it, and allow to generate novel samples from the learned distribution. With growing popularity and deployment of generative Al across a wide variety of applications, communicating the outputs of these models (particularly for image, audio and video modalities) will put an increasing burden on the underlying communication network infrastructure. However, instead of generating and then compressing a sample the cloud server, we can exploit channel simulation to enable the users to locally generate samples at a much lower communication cost. Drawing multiple samples is a common use case for generative models. For instance, in text to image models, such as DALL-E or Midjourney, multiple images are often generated and communicated to the user based on single prompt to allow the user choose the desired one. Other instances include translation (Lee et al.) 2021 Eikema and Aziz (2022). code generation (Chen et al., (202I) and planning (Yao et al., (023). which can be improved by discriminating among multiple generated samples.
The contributions of this work are summarized as follows:
We formulate a novel universal sample coding problem, which defines the problem of communicating multiple samples from an arbitrary discrete distribution unknown to the receiver.
We highlight the relationship between the redundancy in universal source coding and the communication of samples, and show that the optimal redundancy for universal source coding is a lower bound on the communication cost of universal sample coding.
We propose a coding scheme for the universal sample coding problem, providing an upper bound on its communication cost that is within a multiplicative factor from the lower bound.
We employ our algorithm in FL achieving a 37% reduction in the communication load compared to the current of-tee art commuuncaation-effccii FL algorithm.
We adapt our algorithm for the remote generation problem, where the goal is to sample at a remote user from generative model hosted on cloud server, while communicating the least number of bits from the server to the user. We demonstrate the potential benefits of sample communication in this setting through numerical experiments.
2

---

Table Rate required to communicate a given/any sample from
matched
mismatched
source coding
(P))
H(P) DKL, (PlIQ)
sample communication
0
DKL (P)
2 Notation
We x (X1, .,, to denote sequence of n elements and log(-) denotes logarithms of base 2. Let P and Q denote discrete probability distributions. The entropy of P is given by HP)) & Ex~P [log P(=)], while the relative entropy from P to Q, or the KL-divergence, is defined as (kl(P) & Eg'P log P(x)
Q(w)
3 Background
The problem of communicating samples from a desired distribution a version of the channel simulation problem, also known the reverse Shannon theorem, reverse channel coding. Given a sample from a probability distribution Pz at the encoder, channel simulation entails generating sample from the conditional distribution Px|ž== the decoder, using the fewest number of bits. was posed in Cuff (2008), where the solution was characterized the asymptotic regime, where infinite sequence of samples is considered, while earlier results appeared in the quantum communication literature (Bennett et al.) [2002] Winter] (2002). The non-asymptotic results were shown in Harsha et (2010) using common randomness, and then further refined in Li and Anantharam (2021), where was shown that to communicate a sample X from distribution Pxiz=; with joint distribution Pxz, it is sufficient transmit
[(x; 2) + log(I(X:;)) + 1) + 4.732 bits
(1)
on average, where
1 2x; & E [DL (Px1=====))))
2~22
the mutual information between X and This result close to optimal was shown in Li and El Gamal 2018). i.e., there exist distributions Px,z where the minimal number of communication required for reverse channel coding is on average
((;; 2) + log (o; (Xx 1) bits.
As pointed out and shown in Theis and Yosri (2022). the sample communication bound does not rely on using the exact marginal distribution Px. and still holds for other reference distributions Q. In general, to generate a sample at the decoder from distribution P, with reference distribution Q, is enough to communicate average of
DEL + log(DKL(PIIQ)) 1) + 4.732 bits.
While efficient in terms of communication cost, the sample communication method in Li and El Gamal (2018) might be prohibitively expensive computationally. There have been increasing efforts in creating algorithms with reduced complexity by constraining the distributions P and Q (Flamich et al., 2022; Flamich, (023). An overview of the methods and trade-off between communication, computation, and sample accuracy is provided in Theis and Yosri (2022). The problem of communicating multiple samples from an unknown distribution was also addressed in Choi and Li (221), where the authors considered setting without common randomness and achieved sublinear, yet superlogarithnic, communication rates.
Communication of samples
4.1 Source coding
Lossless source coding the problem of describing the realizations of a random variable with the least number of bits on average. Each outcome X' is assigned different sequence of bits, called

---

a codeword, with length ((x). The optimal average codeword length is obtained by Huffman coding (Huffman 1952). where (z)) I [ -log P(z)] and
H S
E [.E((()) H(P)+I.
For n independent and identically distributed random variables X" (X1, X2....,, "......,,,)....... X; ~ P. it is straightforward to show that using Huffman code, the expected codeword length per symbol HP)) I Een [(x") ]] & H(P) + 1. As n + xo this quantity converges to the entropy, which provides fundamental limit for compression.
We call the code mismatched if designed for source distribution of Q while the true source distribution is P. Then the expected codeword length is given by:
P(x)
E [o(x)]
<
E [ log Q(x)] x
E
log (z) + +1+ log
(6)
P(x)
log P(x)
E log P(x)
+
E
+ +1 H(P) + (KL(())Q) + 1. (7)
Z-P
(zz)
For the n-ary case, the rate converges to H(P) + (PI()) (Cover and Thomas 2006), where the Kl.-divergence the penalty for using a mismatched source distribution when designing the code.
However, there exist source coding methods called universal source coding with an average codeword length that converges H(P) for any underlying distribution P known the encoder. They can be thought of as empirically estimating (often implicitly) the underlying distribution of the data. The classic and widely used example of such an algorithm is LZ78 (Ziv and Lempel, 1978). For
any distribution P the average number of bits needed to compress samples is H(P) + O v
(Savari 1997). which converges much slower than Huffman coding for known distributions. This excess factor for any universal source code I is known as per letter redundancy, defined as:
rr(n) = sup E PEP =">P [aa"())) H(P),
(8)
where Py. is k-dimensional probability simplex. It was shown in Davisson et al. (198] that for k-dimensional distribution, the minimal per letter redundancy for any universal source code is:
inf (r) (k: 1)g logn + O(n")).
2n The log n factor is the penalty for universality of the code (Krichessky and Trofimov 1981 A more useful quantity for our analysis will be the total redundancy, defined nry. In the remainder of the paper, when we refer to redundancy, we mean the total redundancy.
4.2 Sample communication
As mentioned in Section 3 reverse channel coding involves simulating samples from a joint distribu- tion. Sample communication is similar problem where the aim is draw samples at the decoder from distribution P, which is only known at the encoder, while both the encoder and the decoder have access to samples from common distribution Q. This common randomness in practice, a seed to initialize pseudorandom number generator allows both to draw the same sequence of samples from Q. Using any sample communication method with cost specified in Equation (4) a sequence of independent and identically distributed (i.i.d.) samples X", X;; ~ P. can be encoded using:
DKL. (P (1 (og( (pt0n 1 (m)) + 1) + 4.732
DKL (PI))) + log(n (PIl)) + 1) + 4.732
(10)
expected number of bits, and the per sample cost converges to DKL (PIlQ) as 00.
Characterizations of the rate of source coding and sample communication in both matched and mismatched cases are presented in Table where we can see that 'moving' to source coding adds H(P) the required rate, while using a mismatched distribution Q contributes DkL(PIIQ) The natural question to ask is whether the results of universal source coding can be extended to sample communication. Firstly, does the rate approach when n > oc, and secondly, what the total communication cost of communicating n samples? In the next section, we show that the answer to the first question positive, and that the total communication cost the same order as the minimal redundancy, and the two quantitics share common lower bound.

---

Algorithm Universal Sample Coding
Input: P.
Parameter:
с >>0
1: Send sample X1 ~ P.
2: Let
G(1)
3: while i S [log1+< +
4: Let G(i) = c)
5: Let Qi = (x(((i1)) be probability estimated with all previous samples (estimator Lemma
5.2).
6:
Let g(i) G(i) - G(i 1).
Jointly send g(i) samples x x-
G(1-1)+1 ~ poo(i) using Q, (0)(s) (Equ. 10
7:
8:
9:
end while
Universal sample coding
The core idea is that, after observing t samples, the decoder estimate P. and use this estimate as the reference distribution Q. As more samples are transmitted, the KL-divergence between the decoder's 's estimate and the true distribution P will diminish, which will translate into lower communication cost for later samples. The proposed scheme consists of multiple rounds; in each round, batch of samples sent jointly, then the reference probability Q is updated.
Theorem 5.1 (Universal sample coding). There exists randomized encoding function f Pk x + N, and a randomized decoding function g : x + X", such that for any k-dimensional discrete distribution P Pk over alphabet X and random string Z Z 1] 10 such that g(f(P, Z), 2) = X ~ pmm and
E H(((P.Z)ZZ) L(m) S Vc(c) + o log(n));
where the expectation is over all random strings Z. and
In k-1 2ln + +1) + +5m2
Vi((c) A c In(1 +c)
(11)
In(1 + +
for any > O.
The random string Z is the common randomness shared between the encoder and decoder. The expected number of bits needed to communicate n samples from the any distribution P is similar to the redundancy of universal source coding, with some additional factors and per sample cost log.n
+ 0 as + xc.
5.1 Probability estimation
As the samples are drawn independently, their order does not reveal any information about P. Thus, any estimator, without loss of optimality, can be based only on the count of each symbol in the observed sequence. One of the canonical estimators is the add-1 or Laplace estimator. As the name suggests, the estimated probability of any symbol is its count in the sequence plus normalized to form a probability distribution. Laplace estimator belongs to a family of add-3 3 estimators, which rely adding constant 3 to each count. Although add-3 estimator achieves the optimal minmax KL- divergence rate (Krichevskiy 1998), there exists an estimator (Braess and Sauer (004)) that combines add- add- 3 and add-1 estimators, and achieves the optimal and universal decay of KL-diveegeecee
Lemma 5.2. Braess and Sauer 2004)] Given i.i.d. samples X Xi, P from any distribution P E Pk. there exists estimator Q("") such that:
E X
DRu(PI(((x*))
k-1
o(n o(n-1)).
(12)
2ln 2.
5

---

10
1024
inf. Vi(c)
512
x=1
1
256
128
64
4-
3
8
2
1
0.5
2
4
8
16
32 64
128
2
2
2
2
4
16
32 (dimension)
64
128
2
2
2
2
(dimensian)
Figure 1: The optimal universal sample coding factor inf Va(c). optimized over the choice of c > 0 for k-dimensional distributions, along with the lower bound factor
Figure 2: The optimal universal sample coding factor inf (c),), normalized by k-1 optimized over the choice of c >> 0 for k-dimensional distri- butions.
5.2 Universal sample coding algorithm
If we could communicate single sample with (Plll) average bits, then alternating between sending a single sample and estimating P would be the best strategy. The algorithm would take n communication rounds and the total expected communication cost of this hypothetical algorithm would be:
k 1-1 Σ
k --1 log(n) o(logn))
[log k1
2hn.. t i=1
oi S
(13)
where [log A the cost of sending the first sample. However, the real cost of sending a sample, as shown in (4), includes a constant, which would dominate the total cost n increases, making linear instead of logarithmic. We propose a solution that requires only O (logn) communication rounds, where in each round, exponentially more samples are sent. Algorithm Iillustrates the pseudo code for the proposed solution. The proof Theorem 5. presented Appendix B We first upper bound the number of bits communicated in each round. Then show that the total number of bits communicated over all rounds is V& (x(c) log(n) + ollog n). where parameter e controls the size of the groups communicated at each round. The optimal choice of depends on k.
We have plotted the infimum of (c) for different values of in Figure 1 The value of the first term $2 which is equal
of (c), that is In(1+e) k-1 is minimized as e approaches 0 and converges to the optimal redundancy factor. As we show in the next section, it is also the lower bound for any universal sample communication algorithm. The ratio between the optimal value Vi(c) and k-1 is shown in Figure 2 where it starts at around 9 and converges to 1 as k grows; this is the multiplicative gap between the upper bound on the communication cost the proposed algorithm and the lower bound presented in the next section.
5.3 Lower bound
The connection between universal source coding and universal sample coding highlighted in the following theorem, where the lower bound of redundancy of universal source coding is the same the communication cost of universal sample coding. This is not a coincidence, we can prove this theorem using exactly the same steps the proof of optimality for the redundancy of universal source coding in Davisson et al. (198T).
Theorem 5.3 (Universal sample coding lower bound). For any universal sample coding algorithm (Theorem 5.1 there exists k-dimensional distribution P, such that, the expected number of bits L(n) required to communicate n samples from P satisfies:
k-1 log(n) O(1)
L(n) 2
(14)
2

---

10
expected
empirical
10"
empirical
expected
10-1
10
Du(PI()
PalP
10
10-2
10
10a3
10
21
27
29
2
2
2
23
[nnumerr communicated samples)
K (dimennionn
Figure KL-divergence between the true and estimated probabilities for dimension & = 8, for range number of communicated samples n. Solid line indicates the mean, while the shaded area shows the 20th to 80th percentiles.
Figure 4: KL-divergence between true and es- timated probabilities for n 128 samples, for different number of dimensions k. Solid line in- dicates the mean, while shaded area 20th 80th percentiles.
communication [bitss
10
20a
empirical
upper bound Vilogin)
lower bound log(n)
23
2
2
2
2
2
2
2
(number of communicated samples)
Figure 5: Communication cost of communicating samples from an 8-dimensional distribution
(k 8). Solid line indicates the mean, while shaded area shows the 20th to 80th percentiles.
Proof. Theorem 5.3 states that the claim holds for some distribution P, thus it holds for the supremum over all k-dimensional distributions supp L(n). We will consider P as random variable distributed according to Ω. Let be any distribution of k-dimensional distributions, then
sup L(n) Z E [n)],,
(15)
P~2
since the maximum is always greater than equal the average. The right hand side in Equation (15) corresponds to the expected number of bits required to communicate sample X" from p&n where P is sampled from Ω. This is exactly the reverse channel coding problem, where the lower bound on the communication cost was shown in Harsha et al. (2010) to be the mutual information between the two random variables
E PWf
[(n) 2 I(P,X").
(16)
This quantity was bounded in Davisson et al. 1981
k-1
I(P.X") >
log(n) + O11).
(17)
To show
17 Davisson et al. (1981) considers Markov chain P + X - Ô. where Q is reconstruction of P based samples X By data processing inequality, this Markov chain implies [(P,"") 2 I(P, Q). The quantity I(P, Q) describes the minimum amount of information needed to compress in lossy source coding, and can be bounded using Shannon lower bound Shannon (1959). The final lower bound is obtained by choosing appropriate distribution Q and distortion measure between distributions P and Q.
7

---

6
Empirical evaluation
To corroborate the claims about universal sample coding made in Theorem 5.1 we compare the KI--divergence and total communication cost between the theory and numerical evaluations for different number of samples and dimensions. Each experiment is repeated 1000 times, where a probability distribution P is sampled from a k-dimensional Dirichlet distribution with concentration parameters a IR* ag 1. Then, n samples are communicated using universal sample coding (Algorithm[I) [T. We consider ordered random coding (Theis and YoSri, (022). shown in Appendix [ as the underlying sample communication method (line | Algorithm D. In Figure [] we observe that the measured KL-divergence DKL (Pll)) between the true probability P and the estimate Q from the estimator in Lemma 5.2 follows the predicted values across range of communicated samples. In Figure c we fix the number of samples to n = 128, but vary the dimension k, and show that the KL-divergence lies below the bound from Lemma [.2] In Figure we plot the total communication cost for various number of samples, which is contained between the asymptotic upper and lower bounds, (c) log(n) (Theorem 5.1 and k=1 log(n) (Theorem 5.3). respectively.
2
7 Federated learning (FL)
To show the efficacy of the universal sample coding in practice, we first apply it to the Federated Probabilistic Mask Training (FedPM) algorithm proposed in [sik et al. (2024). In FedPM, the weights of the neural network w E M are randomly initialized, fixed, and known both to the clients and the central server. Each weight wy has associated probability 0, of that weight being masked. The training of the network consists of finding the suitable mask probabilities O E [0, M for all the weights using gradient descent. To test the network, binary mask is sampled, and the effective weights of the network become w, Bern (ern( In a single learning round, the server broadcasts the global mask 0 to each client, which then trains an updated version o' using its local data and communicates a sample Bern (0') from its updated mask distribution back to the central server. The new global mask probability 0 is then estimated from all the received samples. The sample from P = 0' is communicated using the coding probability Q = 0, which is known to both the client and the server, thereby achieving communication cost of approximately D DKL (0' [0). To achieve more accurate estimate of the global mask probability, we propose communicating multiple mask samples per client using universal sample coding, along with the addition of the global prior A.
For the experiments, we follow the same setup as Isik et al. 2024) using their CONV-6 architecture on classification of CIFAR-10 images, where the data is distributed among 10 clients. A challenging scenario considered in that work is of congested clients, where only a fraction of clients contribute in each learning round. The results of our experiments are summarized in Table 2 The FL training was conducted on two Nvidia RTX 3090 GPUs, each with 25 GB of memory, with each experiment taking approximately 12 hours. The training, including preliminary experiments, took 30 days of gpu-time. If all the clients participate in each learning round the final test accuracy is around 80%. However, when only 1 out of 10 clients participate in the learning round the accuracy decreases to 75%. By communicating multiple samples in each round, we can achieve test accuracy close to the fully uncongested case. However, as argued in this work, sending multiple samples from the same distribution can be made more communication efficient by estimating the true probability from previous samples. Indeed, we observe 37% reduction in communication cost by employing universal sample coding with prior 8, compared to only using the prior B.
To incorporate the prior into the proposed coding scheme, we use Bayesian estimator. Although the mask is binary, we describe a general case with k possible outcomes. Let w E Ps be the prior probability, and w' be random variable distributed according to the Dirichlet distribution with parameters a E TRR for j E (O....,
... k 1}: aj = يwر + + 1 (1-th sample = =}}, where 1(.} is the indicator function, is the number of samples communicated so far, and μr E IR is a hyperparameter controlling the reliance on the prior. The optimal coding probability Q Eurm w', i... for E {0.... ..., A 1}. Q2 E. replaces the one in line 5 in Algorithm I
For the binary
mask case, where k = 2, we have w = [1- - 0, 0), and 0' is characterized by a 2-dimensional Dirichlet distribution (or equivalently, Beta distribution).
8

---

Table Accuracy and communication cost of FedPM for different simulation scenarios. Values are averaged over 20 runs, with standard deviation bellow 0.003.
FedPM
FL scheme
FedPM
FedPM
FedPM
W. USC
# clients per round
# samples per client
1
7
7
final test accuracy # bits per parameter 0.6058
0.8025
0.7516
0.8028
0.8039
0.0340
0.3955
0.2482
#bits per parameter
0.0606
0.0340
0.0565
0.0355
client & sample
Table 3: Per token cost of sending samples from 13B model. Entropy is a lower bound for source coding, while the KL-diivegeecc serves as bound for sample communication.
# bits per token
plain text
15.617
(P1s))
4.315
DRL 112MM
1.014
(Raa Qasum)
0.824
( QIaa))
0,420
DEL (Paa Pia Q2.70)
0.330
DEL (Pts Q6.7D)
0.266
Limitations and further work
include a factor kethe cardinality of the sample space. Consequently, universal sample coding cannot be directly applied to continuous random variables, as goes to infinity so does the required communication. Universal sample coding consists of two main components: sample communication and probability estimation. While sample communication can be applied to continuous distributions, the estimation component fails because finite number of samples can fully specify unrestricted continuous distribution.
Both the lower and upper bounds of communication rate (Theorems 5.1 5.3)
We propose two potential avenues for extending universal sample coding for continuous variables. Firstly, by imposing additional assumptions on the probability distribution, we could substitute counting-basee estimation with Bayesian approach. The reference distribution Q would be the posterior, updated continually with each new sample. Second, we could explore a model-base bbased approach where common model deseribes Q. This model would be incrementally fine-tuned with the communicated samples to more accurately reflect their underlying distribution. As evidence for the potential this idea, we apply sample communication for generating samples from large language model on server, using smaller reference model at the client. While the space of text is not continuous, is too large to estimate using count-based methods. The experimental setup and further discussion are detailed in Appendix D As demonstrated in Table 3 the application of sample communication results in a 4- to 16-fold reduction in communication rate, depending on the auxiliary model employed. This motivates further exploration into model fine-tuning effects. Although this research currently focuses on text generation, future work will aim to extend these results to image and video generation, which represent substantial portion of network traffic. Furthermore, determining the optimal use of new samples in the learning process presents a compelling challenge, potentially linking advancements in online learning methods.
The universal sample communication problem, introduced in this work, involves communicating multiple samples drawn from the same probability distribution P, which is unknown to the decoder. An alternative but related problem would involve generating multiple samples, each from a different conditional distribution Px|z=a- In such case, the optimal coding distribution would be the marginal distribution Q Px, and the optimal per-sample communication cost would be T(X; Z). In the universal setting, the decoder would not know this marginal distribution. Thus, similar estimation and sample communication approach, as demonstrated in this work, could be applied to address this

---

problem. However, further analysis is required to validate the communication performance of such scheme.
Conclusion
As Al tools become ever more prevalent, it becomes increasingly important to consider the resources they consume. This paper analyzes the communication cost of transmitting samples from probability distributions, which can be seen as sending the outcomes of generative models, and show that by leveraging the fact that many generative Al upplications only seek communicate generic samples from a distribution rather than a specific sample, we can reduce the associated communication cost significantly. In this paper, we proposed universal sample coding for transmitting multiple samples from distribution, which achieves the information theoretic lower bound by up to a multiplicative constant. We also applied it to a FL framework showing a communication cost reduction of 37%. and to remote text generation problem using large language models, showing an up to 16-fold communication cost reduction compared to sample-wise entropy coding methods.
Acknowledgements
This research was supported by the United Kingdom Engineering and Physical Sciences Research Council (EPSRC) for the projects AIR (ERC Consolidator Grant, EP/X030806/1) and INFORMED- AI (EP/Y028732/1).
We would like to thank Francesco Pase for sharing the federated learning codebase of Isik al. (2024).
References
Agustsson, E. and Theis, L. (2020). Universally Quantized Neural Compression. In Advances in Neural Information Processing Systems, volume 33, pages 12367-12376. Curran Associates, Inc.
Bennett, C., Shor, P., Smolin, J., and Thapliyal, A. (2002). Entanglement-assisted capacity of quantum channel and the reverse Shannon theorem. IEEE Transactions Information Theory, 48(10):2637-2655.
Braess, D. and Sauer, T. (2004). Bernstein polynomials and learning theory. Journal of Approximation Theory, 128(2):187-206.
Chen, M., Tworek, J., Jun, H., Yuan, Q., Pinto, H. P. d. O., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., Ray, A., Puri, R., Krueger, G., Petrov, M., Khlaaf, H., Sastry, G., Mishkin, P., Chan, B., Gray, S., Ryder, N., Pavlov, M., Power, A., Kaiser, L., Bavarian, M., Winter, C., Tillet, P., Such, F. P., Cummings, D., Plappert, M., Chantzis, F., Barnes, E., Herbert-Voss, A., Guss, W. H., Nichol, A., Paino, A., Tezak, N., Tang. J., Babuschkin. I., Balaji. S., Jain, S., Saunders, W., Hesse, C., Carr, A. N., Leike, J., Achiam, J., Misra, V., Morikawa, E., Radford, A., Knight, M., Brundage, M., Murati, M., Mayer, K., Welinder, P., McGrew, B., Amodei, D., McCandlish, S.. Sutskever, I., and Zaremba, W. (2021). Evaluating Large Language Models Trained on Code.
Choi, C. F. and Li, C. T. (2021). Multiple-output channel simulation and lossy compression of probability distributions. In 202/ IEEE Information Theory Workshop (ITW), pages 1-6.
Cover, M. and Thomas, J. (2006). Bounds on the optimal code length Theorem 5.4.3. In Elements of Information Theory 2nd Edition (Wiley Series in Telecommunications and Signal Processing). page 115. Wiley-Intersciencee
Cuff, P. (2008). Communication requirements for generating correlated random variables. In 2008 IEEE International Symposium on Information Theory. pages 1393-1397. ISSN: 2157-8117.
Davisson, L.., McEliece, R., Pursley, M., and Wallace, M. (1981). Efficient universal noiseless source codes. IEEE Transactions Information Theory, 27()):269 279..
Eikema, B. and Aziz, W. (2022). Sampling-Based Approximations to Minimum Bayes Risk Decoding for Neural Machine Translation. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 10978-10993. Association for Computational Linguistics.
10

---

Flamich, G. (2023). Greedy poisson rejection sampling. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S., editors, Advances in Neural Information Processing Systems, volume 36, pages 37089-37127, Curran Associates, Inc.
Flamich, G., Havasi, M., and Hernández-Lobato, J. M. (2020). Compressing Images by Encoding Their Latent Representations with Relative Entropy Coding. In Advances in Neural Information Processing Systems, volume 33, pages 16131-16141. Curran Associates, Inc.
Flamich, G., Markou, S., and Hernandez-Lobato, J. M. (2022). Fast Relative Entropy Coding with A coding. In Proceedings of the 39th International Conference on Machine Learning, pages 6548 6577. PMLR.
Harsha, P., Jain, R., McAllester, D., and Radhakrishnan, J. (2010). The Communication Complexity of Correlation. IEEE Transactions on Information Theory, 56(1):438-449
Hasircioglu, B. and Gunduz, D. (2024). Communication efficient private federated learning using dithering. In IEEE International Conference on Acoustics, Speech and Signal Processing.
Havasi, M., Peharz, R., and Hernandez- Lobatoo M. (2019). Minimal Random Code Learning: Getting Bits Back from Compressed Model Parameters. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019.
Hegazy, M., Leluc, R., Ting Li, C., and Dieuleveut, A. (2024). Compression with exact error distribution for federated learning. In Dasgupta, S., Mandt, S., and Li, Y., editors, Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 613 PMLR.
Ho, J., Jain, A., and Abbeel, P. (2020). Denoising Diffusion Probabilistic Models. In Advances in Neural Information Processing Systems, volume 33, pages 6840 6851. Curran Associates, Inc.
Huffman, D. A. (1952). A Method for the Construction of Minimum ciciimum-Redundancy Codes. Proceedings of the IRE, 40(9): 10981110..
Isik, B., Pase, F., Gunduz, D., Koyejo, S., Weissman, T., and Zorzi, M. (2024). Adaptive compression in federated learning via side information. In The 27th International Conference on Artificial Intelligence and Statistics (AISTATS).
Isik, B.. Pase, F., Gunduz, D., Weissman, T., and Michele, Z. (2023). Sparse random networks for communication-efficcenn federated learning. In The Eleventh International Conference on Learning Representations.
Krichevskiy, R. (1998). Laplace's law of succession and universal encoding. IEEE Transactions on Information Theory, 44(1):296-3033
Krichevsky, R. and Trofimov, V. (1981). The performance of universal encoding. IEEE Transactions on Information Theory, 2992)219
Lee, A., Auli, M., and Ranzato, M. (2021). Discriminative Reranking for Neural Machine Translation. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the / 1thh International Joint Conference on Natural Language Processing ( (Volume I: -Long Pupers), pages 7250-7264. Association for Computational Linguisties.
Li, C. T. and Anantharam, V. (2021). A Unified Framework for One-Shot Achievability via the Poisson Matching Lemma. IEEE Transactions on Information Theory, 6765):262--2651
Li, C. Т. and El Gamal, A. (2018). Strong Functional Representation Lemma and Applications to Coding Theorems. IEEE Transactions Information Theory,
Mihaylov, T.. Clark, P., Khot, T., and Sabharwal, A. (2018). Can Suit of Armor Conduct Electricity? A New Dataset for Open Book Question Answering. In Proceedings of the 2018 Conference on Em- pirical Methods in Natural Language Processing, pages 2381-2391. Association for Computational Linguistics.
Savari, (1997). Redundancy of the Lempel-Ziv incremental parsing rule. IEEE Transactions on Information Theory, 43(1):9-21.

---

Shahmiri, A. M.. Ling, C. W., and Li, C. T. (2024). Commumication efficient laplace mechanism for differential privacy via random quantization. In ICASSP 2024 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4550-4554.
Shannon, C. E. (1959), Coding Theorems for Discrete Source With a Fidelity Criterion. In Claude E. Shannon: Collected Papers, volume 7, pages 142-163. IRE International Convention Record.
Theis, L., Salimans, T., Hoffman, M. D., and Mentzer, F. (2022). Lossy Compression with Gaussian Diffusion.
Theis. L. and Yosri, N. (2022). Algorithms for the Communication of Samples. In Proceedings of the 39th International Conference on Machine Learning, pages 21308-21332 21328. PMLR.
Touvron, H., Martin. L.. Stone, K.. Albert, P., Almahairi, A., Babaei, Y., Bashlykov. N., Batra, S.. Bhargava, P., Bhosale, S., Bikel, D., Blecher, L.., Ferrer, C. C.,, Chen, M., Cucurull, G., Esiobu, D., Fernandes, J., Fu, J., Fu, W., Fuller, B., Gao, C., Goswami, V., Goyal, N., Hartshom, A., Hosseini, S., Hou, R., Inan, H., Kardas, M., Kerkez, V., Khabsa, M., Kloumann, I., Korenev, A., Koura, S., Lachaux, M.-A., Lavril, T., Lee. J., Liskovich, D., Lu, Y., Mao, Y., Martinet, X., Mihaayov, T., Mishra, P., Molybog, I., Nie, Y., Poulton, A., Reizenstein, J., Rungta, R., Saladi, K., Schelten, A., Silva, R., Smith, E. M., Subramanian, R., Tan, X. E., Tang, B., Taylor, R., Williams, A., Kuan, X., Xu, P., Yan, Z., Zarov, I., Zhang, Y., Fan, A., Kambadur, M., Narang, S., Rodriguez, A., Stojnic, R., Edunov, S., and Scialom, T. (2023). Llama 2: Open Foundation and Fine-Tuned Chat Models.
Triastcyn, A., Reisser, M., and Louizos, C. (2021). DP-REC: Private & Communication--ffiiieeen Federated Learning.
Winter, A. (2002). Compression of sources of probability distributions and density operators.
Yao, S., Yu, D., Zhao, J., Shafran, I, Griffiths, T., Cao, Y., and Narasimhan, K. (2023). Tree of thoughts: Deliberate problem solving with large language models. In Advances in Neural Information Processing Systems, volume 36, pages 11809-11822 Curran Associates, Inc.
Zhang. S., Roller, S., Goyal, N., Artetxe, M., Chen, M., Chen, S., Dewan, C., Diab, M., Li, X., Lin, X. V., Mihaylov, T., Ott, M., Shleifer, S., Shuster, K., Simig, D., Koura, P. S., Sridhar, A., Wang, T., and Zettlemoyer, L. (2022). OPT: Open Pre-trained Transformer Language Models.
Ziv, J. and Lempel, A. (1978). Compression of individual sequences via variable-rate coding. 1EEE Transactions Information Theory, 24(5):530-536.
12

---

A Universal Estimation
The form of the universal estimator (Braess and Sauer 2004) is provided in Algorithm 2 where denotes the size of the alphabet and c|²j represents the number of occurrences symbol in the observed sequence. Notably, when the sequence is empty, the estimator produces uniform distribution over all symbols.
Algorithm 2 Universal Estimator
Require: c
I/ Count of occurrences of symbols in the sequence.
1: Initialize array Q of size k
2: for e {1, ..., k} do
3: c = 0 then
4: Qli] + c|i] + 2
5:
else cli] then
6:
@ < c[i +
7:
else
8:
Q + ciil +
9:
end if
10:
end for
11: W + -> 1= Q1
// Normalize the distribution.
for Q[i]+ + Q1i] / W
(1. do
13:
14: end for
15: return Q
B Universal Sample Coding proof
Proof. Theorem 5.1
Universal Sample Coding
Let > and G(i) be the number samples communicated up to and including round 1:
G(1) = [(1 +c) (1 +
(18)
Let g(i) be the number of samples communicated round g.1(1) G(1) for 2 2:
((1) = -()-
+1- =d1+0)-2+11
(19)
At round i, g(i) samples will be coded jointly, using estimate Q based on previous G(i 1) samples. The cost of sending the first sample is [log k. For rounds 2 2, using cost from Equation
I0 (with the constant upper bounded by 5) round i, with the estimator from Lemma 5.2 the
13

---

expected number of communicated bits is upper bounded by:
E
g())
D
log(g(i) DKL|P + +1) 11++ +5
(20)
1-1
I g())
to
(21)
G(i-1)a 1)2
G(i - 1)
h-1
G(i - 1) )
+ +og g(1)
+o
+1 +5
G(( - 1)2
k
< (c (1 (1+c) cc)
+ +o(1)
(22)
2ln
1-1
+ log
(c+ (1 + c) 4+3
+ +0(1)
+ +5
2ln2
1
1
1 cl 2ln 2
+ (1 (1+cc)
c) -1+2
+ log
(23)
2 2
2ln
2 In 2
+ log
c + (1 + c) (42
5 d(1)
k
In line 20 we used Lemma 5.2 and Jensen's inequality. line 21 the inequality a(i-1) S
960)
e+ (1 for i 2 is used. In [logie<(n) (n)] + 1 rounds, there G((log1+a(1) + 1) 2 samples communicated, and the total expected number communicated bits, denoted by L(n, c). is given by:
[log te (1))+1 (n]]+1
1
L(n, c) = =[log k] +
Σ
+ log
+ + o11++
(24)
2
2hn
2
k
2 2
+ (1 i+2
1+2
log
c+ (1+ (1+c)))-++
21n
1: --1
k -
1
[log k1 + [log (1)
+ log
+ +5 + o(1)
(25)
21n
2ln2
[log
k:
2 2n
(1 (1+c)=
+ log
c
(1+ (1+c)=+ +
k +x-1)
2 2
log(n)
1:
h
+ 1 1 !
1
c
+ log
+ 5
(26)
log(1 c)
21n
2n 2
2
In(1 k-1
2n
+ +log(n)
1
+
+ log
1 c
+ o(log n)
In(1 + cc)
k-1
log(n)
k-1
2
+ In
+ In(1 +
+ 5 5l
+ +lgg(n) + o(log n)
In(1
2
2 2
k k-
(27)
k-11 1
In 2ln
1) + 5lm 2
log(n)
+ 1
+ +ologg)
(28)
In(1 + c)
2
In (1 + +c)
Vc((c) log(n) + o(log n)
(29)
where the upper bound of terms dependent on round i in line 3.
25 lemmas
B.2
This proves
Lemma B.1. For 0 < c, n.n2
[log
(x)) (x))-1
1 I = -c +1.
(1+c)-'s < 1 (1 c1
(30)
14

---

Thus,
[1o814c (n]]-1
(1+c)-i (b-1)
k
- ((
(31)
2lm2
2ln
Lemma B.2. For 0 < C, 2 1, and h: 2 2:
(1)
21n
log c+ (1+))) + k k-1
(32)
( 2ln2
s [logi- log
(33)
-
log n
+1 log c+c+ 2
s [ ( + c)
(34)
k --1
In 1
21n2 R-1
21n 2
log(n)
+ log c1+c+
(35)
In(1 +c)
In(1 In(1+c)++ + In (1
2ln2
= log((n)
[A 18-1)(1-)
+ log (1 c
21n 2
(36)
In(1
k
In [ + 2lm
k-1
2ln k--
< <lo((n)(1 +
log 1 +++
(37)
In
C
Channel simulation
The channel simulation method used throughout this work ordered random coding from Theis and Yosri (202) reproduced in Algorithm 3 for convenience.
Algorithm 3 Ordered Random Coding
Require: P, P.Q.N N
1: n' 1,
2: w min, ((x)/Q(x))
3: repeat
4:
2 + sample P
5:
v u+ N/(N +1 1)
6:
8 8 1- P(=)/Q(z)
7:
if s* then
8:
s* +
9:
17" n
10:
end if
n 4- n +
12:
until s* < st-w or nr N
13:
return n1
D Generative models
The idea behind the universal sample communication is based on two ingredients: samples can be efficiently communicated if the decoder has access to similar distribution, and the distribution can be estimated based on observed samples. Hence, as the receiver acquires more samples, the marginal communication cost decreases. In machine learning, many models, such as classifiers or generative models, describe (conditional) probability distributions. Thus, this recipe straightforwardly translates to such scenarios, where samples from a model can be communicated in the same way, and the estimation step can be replaced by an auxiliary model that learns based on communicated samples. Specifically, let there be server and client, where the client wants to model located at the
15

---

server for instance an artificial neural network. The model represents a conditional probability distribution Pxiz= where is the input to the model. In addition. both the client and the server have access to an auxiliary model describing Qx The client sends to the server, and then a sample x ~ PxIz== generated by the server's model can be communicated back with approximately [xiz==>) bits. Then, the data point 2)), can be used for updating the common reference model x If models P and Q are of the same size, this scheme could be understood as model compression, where P is communicated by using samples from it, and then reconstructed at the client as Q. However, if model P is much bigger than Q, then presumably the clients' model could not fit the same distribution perfectly, and the distributions may differ significantly. As such, there is trade-off between computation/ complexity at the client and the required communication. Additionally, the model at the server might be capable at the whole range of E 2, while the client might only be interested in some smaller subset of values of 2 E Z' C Z. In this case, even less powerful model Q could learn good approximation of Px|z== for the desired input space.
(x
To demonstrate the validity of the idea, we perform numerical experiments in which we compare the expected number of bits required to communicate a text sample from a large language model (LLM). Instead of the estimation/learning step. we use models of different sizes from the family of Open Pre-train Transformer (OPT) models Zhang et al. (2022) (MIT license). In particular, we use the 13 billion (13B) parameter model to represent the desired conditional probability P. while Q is represented by one of the smaller OPT models with {125M, 350M, 1.3B, 2.7B, 6.7B) parameters, where M denotes million, and B billion. The classical way to communicate such samples is to generate the distribution at the server, sample from it, and then encode and transmit the result- - we refer to this method source coding, and, mentioned before, it has the minimal cost H(P), while the sample communication approach would have an approximate cost of DKL (Pl()) (per sample).
In LLMs, text is represented as a sequence of tokens, where each token is short string of characters for instance phrase "nocturnal animals" would be parsed into tokens ("no", "ct", "urnal", "animals"). A LLM describes the probability of the next token conditioned on the all the previous ones. This is enough to describe any distribution over sequence, as can be factorized in an autoregressive way To sample from such distributions, we can sample the first element, then conditioned on sample the second one, and so on so forth. The entropy of sequence of random variables can be decomposed as H(P") Σ H( ). Conditioned on a specific xf we can get an exact entropy (XXx, as the model outputs probability of each token given .r.. However, the OPT models use 50265 possible tokens, and thus to calculate the entropy of sequence of length n, one would have to calculate the entropy of 50265" different sequences which is infeasible. Instead, we estimate the entropy by sampling M 50000 different random sequences of length N = 128 according to the model. To increase variety and simulate user prompts we condition the answers on questions from OpenbookQA dataset Mihayyov et al. (0188. Then the entropy of single token is estimated as
P(X*) IT=
M N Σ
1
H(P)
H(
(38)
MN J=1 1=1
x
We can similarly estimate the KL-divergence as
M
N DRL(PxIXX--= 1 11 1Qx 1).
(kl()) = MN
(39)
j=1==
The experiments were performed on 4 Nvidia RTX A6000 GPUs with 4SGB of memory and PyTorcl version 2.1, totalling 10 hours of wall-clock-ting
The estimated expected communication cost per token is shown in Table 3 Even the smallest 125M model allows us to decrease the communication requirement by more than times. As the auxiliary model gets bigger, the communication cost decreases by up to 16-times. These results are asymptotic, and do not include the overhead for shorter sequences. Thus, we also present upper bounds for communication of groups of B E 2,,2,44 4, 8, 16, 32, 64, 128} tokens jointly in Figure 6 For sample communication, the upper bounds are calculated by including the logarithmic and constant terms from Equation (4). For source coding, we use the upper bound from Equation (5). The sample communication approach beats source coding even for group size 2 2 for any of the auxiliary models. Only for B- = 1 source coding is more efficient, as the constant overhead from equation
16

---

3
cost per token
code 13B
0.6
sample 125M
sample 350M
sample 1.3B
sample 2.7B
0.3
sample 6.7B
1
2
4
8
16
32
64
128
0
group size
Figure 6: Communication cost per token function of the group size. The solid lines depict the mean, while the shaded areas correspond to the 25th to 75th percentiles. The 'code 13B' indicates the source coding approach, whereas 'sample Z' pertains to sample communication with the auxiliary model Z.
5, which greater than the source coding cost. Even for small group sizes of B = 8, the sample communication approach achieves 4 times reduction the communication cost.
17

---

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: The abstract and introduction clearly articulate the main claims and contribu- tions of the paper, including the development of a universal sample coding problem (section 5p. the derivation of bounds on communication costs (section [5). and the application of these
methods in federated learning (section] 7 and remote generation of samples from generative models (section g and appendix D
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:
The paper addresses its limitations in section 8 highlighting constraints on
applying universal sample coding to continuous variables and scalability issues for large distributions.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are 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 vell-specifiiattin, asymptotic approximations only holding locally). The authors should reflect on 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 few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails 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, worse outcome might be that reviewers discover limitations that aren't acknowledged 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.
18

---

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]
The paper includes complete proofs with assumptions for theoretical result. Proofs and necessary theoretical details are provided in section 5 and detailed further in the supplemental material under B Each theorem and lemma properly numbered and cross-referenced.
Justification:
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 if they appear in the supplemental material, the authors are encouraged to provide a 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 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 of whether the code and data are provided or not)?
Answer: [Yes]
The paper provides descriptions for reproducing its experiments. It follows the setup for federated learning from Isik et al. (2024) and specifies any modifications in section 7 For the LLM experiments, which involve only inference, all necessary details are available appendix [
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
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, descríbing the architecture fully might suffice, or if the contribution is 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 to accomplish this, but reproducibility can also be provided instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be 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).
19

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it 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 to 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?
Answer: [No]
Justification: Code implementing Universal Sample Coding, well the large language model experiments, is released. Code for federated learning is based on a yet-unreleased codebase shared by the authors of lsik al. (2024). We are in ongoing discussions with the authors on the best way to release this code, but it will not be publicly available at the time of publication.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https //nips.ccl liliiss.cc/publicguuuueee
for more details.
The authors should provide instructions on data access and preparation, including how to 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. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as 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: The experimental setups, including the universal sample coding empirical evaluation and the large language model simulations, to the federated learning setup outlined in Isik et al. (2044). Any modifications due to changes in the scenario documented in section 7
described in section We adhere
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 a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, 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?
20

---

Answer: [Yes]
Justification: For the federated learning experiments, report maximum standard devi- ations for all metrics, which are low, indicating consistency across runs. For experiments involving large language models and the direct evaluation of universal sample coding, we include data for the top and bottom 20th or 25th percentiles.
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, least for the experiments that support the 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, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to 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.
It is OK to report 1-sigma error bars, but 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 errors 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 error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures 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 execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The paper provides information the computational resources used for each experiment in the description of each experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or 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 or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httpppp//.aarrppp.cc///aaa//a/aa
Answer: [Yes]
The study does not involve human subjects sensitive data, and all computa- tional methods and experiments comply with ethical standards for responsible Al research and development.
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
21

---

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 their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
The paper focuses on improving the efficiency of existing technologies and does not introduce new applications: thus, it does not directly discuss broader societal impacts.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (c.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.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as 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 to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
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:
The paper does not release any data models.
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. Licenses for existing assets
22

---

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: [Yes]
We ensure that all external assets used in our research, such as code and datasets, are properly credited to their original creators.
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.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 in the package should be provided. For popular datasets, paperssi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors 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]
The paper does not introduce release any new assets such as datasets, code, or models; therefore, no documentation related to new assets is provided at this stage. However, when the code released, full documentation will be provided.
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is 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 as details about compensation (if any)?
Answer: [NA].
Justification:
The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in 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 in the main paper.
23

---

According to the NeurlPS Code of 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 equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA].
Justification: The paper does not involve research with human subjects crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on 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 adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
24


Reviews:
[{"review_id": "ywHmSg38mc", "reviewer": "Reviewer_RwEb", "summary": "The paper proposes a new problem called \"Universal Sample Coding\". This is related to a problem called reverse channel coding (or channel simulation) where the receiver must generate samples from a target distribution (P) that is known to the sender but not the receiver. In addition, the receiver and sender have shared randomness which is used to generate samples from a reference distribution Q. The goal is to characterize the communication complexity i.e., the number of information bits that must be transmitted from the sender to the receiver to generate the target sample(s). \n\nAs far as I understand the authors propose a new problem setting where  (at least) the decoder also does not know the reference distribution Q, but estimates it. The paper provides upper and lower bounds on the communication complexity in this variant that have the same scaling in terms of the number of target samples.", "questions": "please see the weakness section above..", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Please see the summary above. Although the setup considered in the paper is potentially new, I did not fully understand it.", "weaknesses": "The setup and results need clarification.\n\n1. Can you clarify your problem setup? Is it that both the encoder and decoder do not know the samples?  Who generates the samples $X_1, \\ldots, X_n$ generated from the reference distribution and how are they known to the encoder/decoder?   In the reverse channel coding/channel simulation settings that I am familiar with, both the sender and receiver know the reference distribution $Q$ and use common randomness to generate identical samples.  I wasn't sure how the samples are generated.\n\n2. The statement of Thm 5.1 is not clear to me. Usually the rate bound should be on $H(f(P,Z)|Z)$  as $Z$ is known to both the encoder and decoder. Why do you consider $H(f(P,Z))$ as your rate?\n\n3.Theorem 5.1 is for \"some c\", but in the numerical bounds you are optimizing over $c$. Should the statement be for every $c$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Our problem setting is indeed very similar to conventional channel simulation as described by the reviewer, with the following difference: instead of a single sample, the goal of the decoder is to generate multiple samples from the target distribution $P$, which is known only to the encoder. To be precise, our goal is to identify the average number of bits that need to be communicated to the decoder so that it can generate $n$ samples from $P$. Our solution relies on the idea that as the decoder generates samples from $P$, it can also estimate it, and its estimate can be used as the reference distribution $Q$ for the remaining samples. As the decoder generates more samples, it will have a better and better estimate of $P$, and hence, it will cost fewer and fewer bits to generate new samples from $P$. To the best of our knowledge, this is a new problem formulation that was not studied before and is also relevant for many practical scenarios, as we argue in the paper.\n\nWe thank the reviewer for pointing out the two typos. Theorem 5.1 should read as $H(f(P,Z)|Z)$, and does indeed hold for `any $c$'. We have corrected both in the manuscript.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rTaBmZlbgK", "reviewer": "Reviewer_YZzm", "summary": "This paper studies the problem of communicating multiple samples from an unknown distribution using as few bits as possible. The authors provide upper and lower bounds on its communication cost that are within a multiplicative factor from each other. The upper bound is derived from analysing the communication cost of an universal sample coding algorithm, which the authors design based on the reverse channel coding results in information theory. The lower bound is derived based on analysing the connection between universal source coding and universal sample coding. Experiments show that the universal sample coding algorithm can reduce the communication cost in a Federated Learning scenario (up to $37\\%$) or for generating samples from a Large Language Model (LLM) on a server (up to $16$ times).", "questions": "+ Please address the weakness comments above. Please explain how to generate the share source of randomness in practice. \n+ What is the distribution of the random string $Z \\in \\mathcal{Z}=\\\\{0,1\\\\}^{\\infty}$ in Theorem 5.1?\n+ What are the definitions of $I(P,X^n)$ and $I(P,\\hat{P})$ in (16)?", "limitations": "This is a theoretical research paper, hence the negative society impact of this work is not direct. The authors mention some technical limitations of this work in Section 8.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "+ The problem setting looks interesting. \n+  Experiment shows that communicating multiple samples can improve the test accuracy (Table 2).", "weaknesses": "+ The gap between lower and upper bounds (the ratio between $\\inf_c V_k(c)$ and $(k-1)/2$) is quite large for not very large $k$ (See Fig. 1 and Fig. 2). \n+  Algorithm 1 requires a shared source of randomness between the encoder and decoder.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The gap between the upper and lower bounds quickly diminishes as the dimension increases. In our approach, we focus on minimizing the upper bound by choosing an appropriate constant $c$. However, a different $c$ might work better empirically, although lacking optimality in the derived upper bounds. Federated learning experiments validate the competitiveness of the proposed scheme in practice.\n\nFrom a mathematical perspective, common randomness is an infinite list of fair coin flips - that is $Z_i\\sim$ Bernoulli(0.5). Equivalently it can be understood as a binary expansion of a single uniform random variable from interval $[0,1)$. This shared randomness can then be used to draw a common list of random variables characterized by $Q$ using, for instance, inverse transform sampling.\nIn practice, it is sufficient that the encoder and decoder have a common seed combined with pseudo-random number generation, which is then used to draw common samples in tandem. Availability of unlimited common randomness is a standard assumption in the channel simulation literature.\n\nThe reviewer was rightfully confused with our abuse of notation in the mutual information expressions. Here, we will write it more explicitly to dispel any confusion. Let $\\Omega$ denote the set of all $k$-dimensional discrete distributions (i.e., distributions over a discrete alphabet of size $k$). Let $\\Pi$ denote a random variable taking values in set $\\Omega$. Here, $P$ denotes the particular realization of $\\Pi$. \n\nTheorem 5.3 states that the claim holds for some distribution $P$; thus, it holds for the supremum over all distributions in $\\Omega$. Then, \n\n$$\\sup_{P \\in \\Omega} L(n) \\geq \\mathbf{E}_{\\Pi}[L(n)],$$ \n\nsince the maximum is always greater than or equal to the average. Note that $\\Pi$ and $X^n$ are correlated random variables, and the right hand side of Equation (15) corresponds to the expected number of bits required to communicate a sample $X^n$ conditioned on $\\Pi = P$. This is exactly the reverse channel coding problem, where the lower bound on the communication cost was shown in Harsha et al. (2010) to be the mutual information between the two random variables\n$$\\mathbf{E}_{\\Pi} L(n) \\geq I(\\Pi; X^n).$$\nThis quantity was bounded in Davisson et al. (1981) as\n$$I(\\Pi; X^n) \\geq \\frac{k-1}{2}\\log(n)+O(1).$$", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TMp8z6mput", "reviewer": "Reviewer_NNh9", "summary": "This paper introduces Universal Sample Coding. This is a simple but significant extension to channel simulation where the sender and receiver communicate $N$ ($N>>1$) samples. The authors prove that the expected codelength per sample will be negligible when $N\\rightarrow \\infty$, and verify with toy examples. The authors also demonstrate the application of this coding scheme in federated learning and the communication of generated samples from generative models.", "questions": "Besides Weaknesses, I have one further question:\nLemma 2 says an estimator exists for any distribution but does not provide the form for this estimator. \nDo you use this estimator for all of the experiments? In Fig 5, I can observe that the empirical results in this toy example obey the bounds very well. But do you think this will always be the case for the FL and LLM settings? Is there any potential caveat?", "limitations": "adequately addressed", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1.  The author formulated the universal sample coding problem and proposed a practical method to handle it. The idea of extending channel simulation to multiple samples is simple yet can have significant influence, and the methods described in this paper are practical and directly applicable to (perhaps small-scale) discrete distributions. \n2. The authors also demonstrate a suitable application of the proposed method: in federated learning and the communication of generated samples from generative models. I suspect that in practice, we will want to communicate so many samples to ensure the per-sample cost vanishes in the latter scenario, but this idea is neat and supportive of the proposed method itself.", "weaknesses": "My major concern with this method is the runtime.\nTo ensure the per-sample cost is asymptotically 0, the authors propose a solution in which exponentially more samples are sent in each communication round. This means that when the problem scale is large, the $D_{KL}[P||Q]$ in some rounds can be large. \nFor order random coding the author used in this paper, to achieve a low biased sample, the total sample size will be $O(2^{D_{KL}[P||Q]})$. \n$D_{KL}[P||Q]$ will, in the end, go to 0, but it will happen only after enough samples are sent. \nTherefore, I kindly ask the author to provide the sample size and the KL divergence for each problem and each round, which can provide more hints on how well this method can scale.\n\n\n\nThis is overall a good paper and I will be happy to further raise my score if the questions and weakness are addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Complexity:**\nTo answer the reviewer's question about the occurrence of outliers in KL divergence between P and its estimate we have plotted it for every round of sending $n=2^{14}$ samples from $k\\in\\{3,8\\}$-dimensional distribution $P$. In every run $P$ is sampled from a Dirichlet distribution parameterized by $\\alpha=(1,\\dots,1)$. The plot is appended in the global rebuttal.  The blue dots show the KL-divergence in every round for every run and red line shows the mean KL-divergence. Yellow lines show proportion of total runs at or below specified value of KL divergence, that is every 10-th percentile, as well as 95th and 98th percentiles, while black line shows the upper bound on expected KL (ignoring some minor terms). We indicate the number of samples sent in each round below the x-axis. \nWe can see that most of the samples concentrate around the mean. KL values up to 20 are reasonable, which is more than $90$\\% of the time, and up to 30 is still computationally feasible (above $98$\\%). For the few outliers we can either accept the high bias samples or incorporate a simple feedback mechanism - if the KL does not decrease enough, keep the number of samples the same as in the previous round. This marginally increases the rate by adding one bit of information for every round, totaling $\\log(n)$ bits.\n\n**Estimator:**\nThe estimator in Theorem 5.2 assigns a weight to each symbol based on the number of occurrences observed in the samples communicated so far plus some small bias, and the estimated probabilities are obtained by normalizing these weights. The exact form of this estimator will be included in the Appendix. The importance of this estimator is that it achieves a min-max lower bound in KL divergence between any distribution $P$ and its estimate. \nWe use this optimal 'P-agnostic' estimator for the numerical experiments, except in the federated learning example, where we use a Bayesian estimator, which works in the same way except for the bias constants.\nKnowing that the Bernoulli parameters -- by which the neural network is characterized --should not change significantly between training rounds we bias the initial estimate / prior ($Q$) to be close to its value before the training epoch. We cannot claim the optimality of this estimator for an arbitrary $P$, but since we know that in reality $P$ will be correlated to its previous value we see a reduction in the number of communicated bits.\nIn the LLM example, the state space is too large to be estimated directly with count-based methods. In that scenario, we would like to investigate fine-tuning a small language model or potentially conditioning one on all text samples communicated so far. This is left for further study.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4L8tSOOMWM", "reviewer": "Reviewer_Jywa", "summary": "The authors consider the problem of efficiently encoding a sequence of $n$ iid realisations $X_i \\sim P$ using as few bits as possible. This scenario is different from one-shot channel simulation because it involves multiple rounds of communication. Between these rounds, the encoder and decoder adjust their coding distribution, leading to substantial improvements in compression performance. Using techniques and results from universal source coding, the authors characterise the optimal lower bound for this task and propose a scheme that achieves the lower bound within a multiplicative constant. They conduct experiments on a toy federated learning problem, showing that their technique could make federated learning significantly more robust when only a fraction of the clients participate in each communication round while reducing communication costs.", "questions": "- Could we perhaps extend the result to continuous spaces by using KDE, or is there something fundamentally different about the continuous case?\n - \"However, the real cost of sending a sample, as shown in (4), includes a constant, which would dominate the total cost as n increases, making it linear instead of logarithmic.\" - Does it? In the authors' case, since the approximating distribution converges to the true target, the ORC index distribution should converge to (approximately) the delta on 1. Hence, I would imagine that the overhead the authors mention would vanish if we used a universal source code to compress the ORC indices.\n - What is the long-term behaviour of the approximating distribution? My initial estimate would be that we have $O(k^{-1}n^{-1/2}) $ convergence to the target by the CLT; could we say something more precise? Is there a good way to speed up the convergence, maybe?", "limitations": "The authors should address the three main points I laid out in the Weaknesses section.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, I found the paper quite enjoyable to read. The motivation and problem set-up are clear. While at a high level, the authors' solution to the problem is \"the obvious one,\" it has many subtleties, e.g. choosing the \"right\" probability estimator in Section 5.1. Thus, this solution, combined with the analysis, provides interesting new insights for the efficient communication of samples. I have checked all the proofs in detail, and they are correct. I also liked the federated learning experiments, as they present a scenario in which the authors' method brings concrete benefits.", "weaknesses": "There are three major points that, if clarified, would make the paper significantly stronger:\n\n1. **What is the sample complexity/run time of the authors' proposed solution?** \nSince Algorithm 1 calls an arbitrary channel simulation algorithm a subroutine, it should be relatively easy to calculate the total runtime in terms of the subroutine's runtime and state it as an accompanying result to Thm 5.1. Such a result would benefit people wishing to build on the authors' work, as the general issue with channel simulation algorithms with target $P$ and proposal $Q$ is that their runtime scales with $\\Vert dP/dQ \\Vert_\\infty \\geq \\exp(KL[P \\Vert Q])$.\n2. **Clarifying the relationship between universal source coding, universal sample coding and channel simulation.** The authors' framework has key differences compared to channel simulation as well as universal source coding, which should be illustrated better. First, they switch to a streaming/multi-round communication setting, where the encoder and decoder can update their coding distribution, which differs from one-shot channel simulation as, in the latter case, there is only a single round of communication. Second, they fix the target distribution of the elements of the sequence, which is equivalent to assuming a delta distribution on the source in channel simulation. Similarly, the analogous setting in universal source coding would be to have a delta distribution as the source: for an alphabet of $K$ symbols, we wish to encode $n$ copies of the same fixed symbol. This can be done by encoding which symbol is repeated using $\\log K$ bits and then encoding the number of repeats, which can be done using $\\log n + O(\\log\\log n)$ bits with Elias delta coding. Therefore, the authors' setting and solution are closer to a universal code (a prefix code on the integers with a certain universality property) than a universal source code (a code which doesn't need to be prefix, but the ratio of the actual and optimal expected codelengths must go to one as the number of symbols increases). I realise that this terminology is annoyingly similar. Still, pointing this out/fixing this would enhance the clarity of the paper, especially given that in the current version, the authors seem to use the terms universal code and universal source code interchangeably. Furthermore, in the same way, that a universal code can be used to create a universal source code, I believe we could use the authors' proposed method to create a closer analogue of universal source coding: Assume we have two correlated variables $X, Y \\sim P_{X, Y}$ with unknown marginal $P_Y$, if Alice receives $X \\sim P_X$ and wants to communicate $Y \\sim P_{Y \\mid X}$. We could apply the authors' method of updating the counting distribution such that the approximating distribution converges to the marginal $P_Y$ so that the scheme's expected codelength will asymptotically be $n \\cdot I[X; Y]$.\n3. **The authors only state results assuming a uniform initial distribution.** There are two reasons why I put this as a major issue: 1) this assumption is not explicitly stated in the paper, but the authors make use of it both in the explanations as well as the proofs. 2) At the end of section 7, the authors suggest using a different initial distribution, whose performance is thus not covered by the theoretical statements, even though this setting is of the greatest practical relevance. I would conjecture that the initial choice should only affect the results up to a constant additive factor.\n\nI have a few more minor issues as well:\n\n1. It would be good to report the scheme's overhead compared to the theoretical lower bound in the FL scenario, akin to Figure 5.\n2. I would need some clarification on the FL experimental setup and results: how did the authors set mu in the FL scenario? Why did the authors specifically pick seven samples per client? How does the performance change as a function of the number of samples sent per client and the fraction of participating clients?\n3. \"We consider ordered random coding Theis and Ahmed (2022) as the underlying sample communication method\" - The authors should clarify (possibly by giving pseudocode in the appendix) what exact implementation of ORC they used. I imagine that the authors did the \"right thing\" and used the discrete version by drawing samples without replacement, and they either ran ORC until the sample space was exhausted or used a more sophisticated early termination criterion. In any case, it would be crucial to state this, as ORC is usually regarded as an approximate sampling scheme (and is usually used for continuous distributions).\n\nFinally, I found some typos/issues with the notation and writing:\n\n - line 99: \"non-asymptomatic\"\n - \"the sample communication bound does not rely on using the exact marginal distribution P, and still holds for other reference distributions Q\" - I'm not sure what this sentence means.\n - Nitpick: the authors state in section 2 that all logs are in base 2, but then they use ln (eg in eq 11)\n - Theis and Ahmed (2022)—The reference is incorrect; the second author is Noureldin Yosri, so it should be Theis and Yosri (2022).\n - \"In a single learning round, the server broadcasts the global mask θ to each client, which trains an updated version θ′ using their local data and then communicates a sample Bern(θ′) from its updated mask distribution to the central server, where the new global mask probability θ is estimated from all the samples\" - It is quite difficult to parse this sentence; please split it in two.\n - I believe that $\\hat{P}$ (in Section 6 and Figures 3 and 4) and $\\hat{Q}$ (everywhere else) mean the same thing. Please update them to be consistent if so.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Computational Complexity:**\nAs pointed out by the reviewer, the complexity of all currently known methods for exact channel simulation is proportional to $|\\frac{dP}{dQ}|_\\infty$. Thus, the proposed method has computational complexity \n\n$$\\sum_{i=2}^{\\lfloor\\log_{1+c} (n)\\rceil+1} \\left(\\left\\Vert\\frac{dP}{dQ(X^{G(i-1)})}\\right\\Vert_\\infty\\right)^{g(i)}.$$\nTo describe the complexity in a more informative way the behavior of the ratio infinity norm between $P$ and its estimate is required.\nWe do not have such results, besides some preliminary calculations suggesting that it might be bounded by $(1+\\epsilon)+O(e^{-n}n^{1/\\epsilon})$ in expectation if $n$ symbols are communicated.\nIn practice, we used the ordered random coding algorithm with a limited number of samples, at or above $2^{D_{KL}}$. This could have negative implications for the estimation accuracy, as samples do not exactly follow the true distribution $P$. However, from our experiments, we did not observe such negative outcomes.\n\n**Naming and generalization:**\nWe agree with the reviewer's perspective about the generalization of channel simulation to multiple samples, where each sample is drawn from a different distribution $P$. Then, the same counting-based estimation could be applied to achieve an optimal asymptotic rate by learning the marginal $Q$. Our formulation generalizes the classical channel simulation to generating multiple samples from the same distribution, while the proposed framework further generalizes this to varying the target distribution at each sample. This setting can be called as 'Universal Channel Simulation', which we believe is a great avenue for further research. \nOn the other hand, universal source coding aims to answer the question \"How to send $n$ samples from an unknown distribution $P$?,\" while the universal sample coding can be understood as \"How to remotely generate $n$ samples from an unknown distribution $P$?\". Moreover, the redundancy of universal source coding and the rate of universal sample coding coincide, in a natural way.\n\nWe agree with the reviewer that the relationship between universal source coding, universal coding, channel simulation, and universal sample communication can lead to confusion. Thus, we have replaced all references to 'universal coding' with 'universal source coding'.\nWe have added a comment explaining the channel simulation generalization to n-letter case proposed by the reviewer. \n\n**Prior distribution:**\nThe uniform prior distribution is a consequence of the way the estimator of Lemma 5.2 is defined - assigning a weight to each symbol based on the number of its occurrences so far. Thus, without any observations, it assigns equal weights to all symbols, and consequently a uniform prior. For the federated learning experiment, we have switched this estimator to a Bayesian one since we had access to side information - the Bernoulli parameter value in the previous step. If the distribution of $P$ follows that implied by the prior this is an optimal estimator, and therefore performs better for any finite $n$ than the agnostic one from Lemma 5.2.\nInfluence of such prior diminishes with samples with rate $n^{-1}$, additionally, we know that the concentration of the estimator is of order $n^{-1/2}$. Thus, asymptotically, the prior does not change the asymptotic behavior of the estimator (barring extreme cases of having infinite-weight prior). We conjecture that, the influence of such prior decreases exponentially as more samples are communicated. \n\nTo clarify, we will provide the exact form of the estimator in Theorem 5.2 in the Appendix, and state in the main text that the default prior for the first sample is uniform. Additionally, we changed the wording in the federated learning section to highlight that a Bayesian estimator is used.\n\n**Federated learning:**\nFor the federated learning experiment, we have run an experiment with $10, 4, 2$, and $1$ active clients, and tested the effects of sending different number of samples (up to around 16). As expected, the performance was robust to the choice of $\\mu$. For the experiments we used $\\mu=4$, but $\\mu\\in[3,10]$ resulted in a similar communication cost, while larger values were converging to the cost of independently sending all the samples. Due to time limitations, we were unable to provide the gap to optimality for the federated learning scenario in this rebuttal.\n\n**Questions:**\n1. Yes, extension to the continuous case using kernel density estimation is possible. We are unaware of the convergence rate of such methods, but it would be an interesting future direction.\n2. By describing the cost of sending each sample separately as linear, we were referring to the upper bound on the communication rate implied by Poisson functional representation. However, we admit that if the samples are sent jointly this cost could be sublinear.\n3. Our understanding is that the estimator does indeed converge at the rate dictated by the central limit theorem. We are unaware of any more precise statements or ways to speed up convergence.\n\nWe agree with all the other issues pointed out by the reviewer and will revise the manuscript accordingly.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all the reviewers for their feedback, most of our rebuttals are specific to the reviews, and thus we respond to each individually.


To answer the question by reviewer NNh9, we plot the empirical KL-divergence.

Meta-review: This paper makes a significant advancement on the classical channel simulation problem in which the reference distribution $Q$ is only known via samples. The authors derive information-theoretic bounds on the expected communication cost and also derive a practical algorithm that achieves the lower bound up to a multiplicative constant. Applications to federated learning are presented. This paper makes significant contributions and is enjoyable to read. I believe it will be of interest to the NeurIPS audience.
Decision: Accept (poster)