Universal Sample Coding

Complexity: To 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. We 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.

Estimator: The 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. We 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. Knowing 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. In 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.

Computational Complexity: As 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

$\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)}.$ To describe the complexity in a more informative way the behavior of the ratio infinity norm between $P$ and its estimate is required. We 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. In 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.

Naming and generalization: We 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. On 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.

We 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'. We have added a comment explaining the channel simulation generalization to n-letter case proposed by the reviewer.

Prior distribution: The 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. Influence 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.

To 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.

Federated learning: For 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.

Questions:

1. 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.
2. 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.
3. 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.

We agree with all the other issues pointed out by the reviewer and will revise the manuscript accordingly.

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.

From 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. In 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.

The 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$.

Theorem 5.3 states that the claim holds for some distribution $P$; thus, it holds for the supremum over all distributions in $\Omega$. Then,

$\sup_{P \in \Omega} L(n) \geq \mathbf{E}_{\Pi}[L(n)],$

since 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 $\mathbf{E}_{\Pi} L(n) \geq I(\Pi; X^n).$ This quantity was bounded in Davisson et al. (1981) as $I(\Pi; X^n) \geq \frac{k-1}{2}\log(n)+O(1).$

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.

We 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.

Thank you for helping me better understand your contributions. I will keep my score as it is.