- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This paper studies a new encoding and decoding method for channel simulation on a discrete-to-continuous channel. They present an encoding/decoding scheme ("the permuted scheme") that achieves exact channel simulation using a finite, fixed number of samples. The permuted scheme permutes the samples using a shared permutation, which brings the communication cost close to the ideal I(X;Y). They use an approximate simulation scheme for larger alphabets. They demonstrate their channel simulation scheme on vector-quantized variational autoencoders and on distributed mean estimation with differential privacy.
Critical strengths
S1. The channel simulation scheme presented in the paper seems to be novel and a material improvement over previous methods, in terms of the number of samples required. I am not familiar with the channel compression literature but this was my understanding based on the presentation in the paper.
S2. They expand their scheme to higher channel dimensions using prior techniques (polar coding and multilevel coding). This expansion increases the usability of their scheme for long blocklengths.
S3. They empirically test their scheme in two settings.
Critical weaknesses
My main problem with this paper was the writing and exposition. I found it extremely dense with jargon that hadn't been defined and techniques mentioned off-hand that weren't explained. Overall the paper assumes a very high familiarity with coding schemes and channel simulation.
For example, some specific omissions
- The motivation for O(nlogn) multi-shot channel simulation wasn't clear (in particular why simulating n independent channels uses more than O(n) time)
- The setup of the encoder and decoder (e.g. a shared permutation)
- PolarSim is assumed to be familiar to the reader and is never defined or explained
- The exponential race method is used but no intuition is given
- Differential privacy isn't defined
- The decentralized DP model isn't defined (it's not the standard central model, though that's the privacy threat model you use).
Questions for authors
I don't have specific questions
4 comments
Response (2/3)
3. The exponential race method:
We agree that more background could be provided on the exponential race, which we use as a coordinated sampling technique leveraging shared exponential random variables. This technique has previously been used to control one-shot communication rates in both the information theory literature [3], and ML and learned compression applications [4]. Intuitively, with a discrete distribution , , and given independent , the index satisfies . To reduce communication, the encoder and decoder also construct a common ordering of the indices using a prior distribution which is known by the decoder. This is done by sorting in increasing order. When and are similar, the selected index tends to appear early in this ordering, so its rank in the sorted list can be communicated more efficiently than the original unsorted index. In our method we set and , leading to the conditional mutual information bound in Theorem 1. The analysis of the exponential race to derive this bound, which we do not repeat in our paper, is given in [3], and has also been used as a key component of related works including [4].
In the updated paper, we have expanded the explanation preceding Algorithm 1 in Section 3.1 to better describe how the exponential race is used for sampling. We provide intuition on how the shared exponential random variables and sorting described in the preceding paragraph help reduce the communication rate.
4. The PolarSim algorithm:
PolarSim [5] is an existing method for jointly simulating uses of a memoryless binary-output channel using polar coding, and introduced the idea of using a polar transform and shared randomness to reduce the communication overhead of channel simulation and approach the ideal rate of I(X;Y). Intuitively, the polar transform, which was originally introduced in the channel coding literature [1], is a bijection which combines many channel uses recursively in such a way that the transformed channels appearing at its output are eventually separated into high- and low-entropy sets. It can be implemented in time. PolarSim then exploits the entropy-separation property to simulate the transformed channels cheaply with an near-optimal communication rate, and applies the polar transform again in reverse to recover the desired outputs. However, the original form of PolarSim is limited to channels with binary outputs and a uniform () marginal distribution.
To clarify our contribution, in Appendix D (Algorithm 2 and Theorem 4), we first extend PolarSim to handle side information shared by the encoder and the decoder. In our scheme, the sample pool is the specific side information which we consider. Second, our modification also extends PolarSim to the case where our discrete input has a non-uniform prior, which in turn implies a non-uniform prior on the output index , as explained in Section 3.2. In its structure and other respects, however, our Algorithm 2 is very similar to the original PolarSim from [5]. Our third key extension to PolarSim is the use of multilevel coding to handle larger alphabets in Section 4.2.
We have revised the paper to include a brief background on PolarSim and why it is useful for simulating binary-output channels, before it is first mentioned in Section 4. This outlines how the polar transform and shared randomness used in PolarSim enable efficient joint channel simulation at long blocklengths, and follows into our discussion of the limitations of the basic PolarSim algorithm and our necessary extensions to handle side information, non-uniform priors and multilevel coding. We have also included some more explanation regarding our extended PolarSim in Section 4.1 before referring the reader to Appendix D where it is fully developed.
Response (3/3)
5. Differential privacy and the privacy model:
As correctly noted, our application uses the standard central differential privacy (CDP) model, with a trusted aggregator. We would first like to highlight that we formally define -CDP in Appendix E.4, Definition 1, in the standard way with respect to the estimated mean, following for example [6]. The trust assumptions are also stated earlier in Section 5.2. We have moved the formal definition into the main paper to clarify.
The distributed or decentralized aspect does not concern the privacy model, which remains the standard central model, but rather only the way in which the clients communicate with the aggregator. While the aggregator is trusted, we wish to reduce the communication cost for each client when it sends its data to the aggregator. Therefore, rather than adding noise at the aggregator after the fact, which would require each client to spend bits to send its vector , each client can instead use (exact) channel simulation to send a compressed representation of its vector after it has been perturbed by the required Gaussian noise. The lower bound on the communication rate then becomes , where each with being the appropriately calibrated Gaussian noise. This problem, sometimes framed as exploiting compression for free in distributed mean estimation under DP, has been explored in prior work including [6,7,8]. Importantly, since our channel simulator exactly reproduces the correct Gaussian distribution (by Proposition 1), the released mean has the same distribution, and therefore the same privacy and utility guarantees, as the central Gaussian mechanism implemented in the conventional way. We finally emphasize that we do not claim local DP for individual client messages, as these are decoded using randomness shared with the trusted aggregator.
In the updated paper, we have clarified the privacy model at the beginning of Section 5.2, emphasizing the standard CDP setting and distinguishing this from the distributed communication between clients and the trusted aggregator. We have also pointed out more clearly in Appendix E.4 that the privacy guarantees relate to the released mean estimate , not the individual client vectors. As stated above, the formal definition of -CDP has been moved from Appendix E.4 into Section 5.2.
We hope these clarifications help make the contributions and their motivation easier to appreciate, and the relevant settings easier to follow.
References
[1] E. Arıkan. Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE TIT, 2009
[2] C. T. Li. Channel simulation: theory and applications to lossy compression and differential privacy. Foundations and Trends in Communications and Information Theory, 2024
[3] C. T. Li and A. El Gamal. Strong functional representation lemma and applications to coding theorems. IEEE TIT, 2018
[4] B. Phan, A. J. Khisti and C. Louizos. Importance matching lemma for lossy compression with side information. AISTATS 2024
[5] S. M. Sriramu, R. Barsz, E. Polito and A. B. Wagner. Fast channel simulation via error-correcting codes. NeurIPS 2024
[6] W. Chen, D. Song, A. Özgür and P. Kairouz. Privacy amplification via compression: achieving the optimal privacy-accuracy-communication trade-off in distributed mean estimation. NeurIPS 2023
[7] M. Hegazy, R. Leluc, C. T. Li and A. Dieuleveut. Compression with exact error distribution for federated learning. AISTATS 2024
[8] Y. Liu, W. Chen, A. Özgür and C. T. Li. Universal exact compression of differentially private mechanisms. NeurIPS 2024
Thank you again for your detailed review. As the discussion period is coming to a close, we would like to check whether your concerns have been adequately addressed.
We believe our rebuttal and the corresponding revisions to the manuscript, as indicated above, provide all the necessary clarifications requested in your review, and hope that the additional explanations have helped make the motivation, technical approach, and setting of our paper easier to grasp.
We would be happy to provide any further information during the remaining discussion period if needed, and would appreciate it if you could reconsider your assessment in light of our response.
Response (1/3)
We thank you for the thoughtful feedback on our manuscript and for recognizing the novelty of our channel simulation scheme and its improvement over prior approaches, as well as the usefulness of its expansion to longer blocklengths using polar and multilevel coding. We appreciate the concerns regarding exposition and agree that some of the underlying concepts could benefit from additional intuition. We hope the following clarifications, in response to the listed concerns, help motivate and explain the ideas behind our approach. They have also been incorporated into our revised paper to improve readability in line with the provided suggestions, as we detail in our response below.
1. Motivation for multi-shot simulation and O(nlogn) time complexity:
We appreciate the opportunity to clarify in response to this point an important distinction in channel simulation between independent channel uses and independent applications of a one-shot channel simulation scheme. While in our setting the target channel is memoryless, with PYn∣Xn=∏i=1nPY∣X and iid inputs Xn, this does not require the simulation algorithm itself to operate independently on each channel use. As rightly pointed out, performing the channel simulation in this way would indeed take O(n) time. However, it would retain the one-shot communication overhead for each symbol, i.e. the logarithmic and constant overhead above I(X;Y∣UˉN) in our Theorem 1:
E[ℓ(M)]≤I(X;Y∣UˉN)+log(I(X;Y∣UˉN)+2)+3.
To simulate n symbols through the channel, the overhead would therefore grow linearly in n, and the overhead per symbol would be constant. To amortize the per-symbol overhead, we instead seek to jointly encode the n simulated channel outputs. The overhead in our Theorem 1 can then apply only once across the entire block of n symbols giving us, as in Eq. (6), a per-symbol cost satisfying
E[ℓ(M)]/n≤I(X;Y∣UˉN)+log(nI(X;Y∣UˉN)+2)/n+3/n.
Unfortunately, as mentioned in Section 4 of our paper, jointly encoding n N-ary indices naively would require choosing between Nn candidate index vectors, making this approach computationally infeasible. The advantage of our polar coding construction is to attain the same asymptotic communication cost of I(X;Y∣UˉN) per channel use with only O(nlogn) time complexity, similar to the motivation for using polar codes in channel coding [1]. Thus, the purpose of the multi-shot construction is not to simulate a channel with dependent outputs or accelerate independent applications of the one-shot scheme, but to exploit joint coding to reduce communication overhead while preserving the desired memoryless channel distribution.
We have added some additional discussion in our Introduction which captures the points made above by distinguishing independent repetitions of a one-shot simulation scheme from joint coding across multiple channel uses, and explaining more clearly why the latter is necessary to reduce per-symbol overhead.
2. Encoder and decoder setup and the shared permutation:
In our paper, we have adopted the standard setup of channel simulation with unlimited shared randomness as laid out in [2, Section 2] --- only the encoder sees the channel input X=x, while the encoder and decoder share a pseudorandom generator (PRNG) from which they can construct shared random numbers. Practically speaking, they agree on a random seed ahead of time. Using the shared PRNG, they can then both reproduce the same random permutation Π and sample pool UˉN, as needed for our algorithm. This is the setup shown in more detail in Fig. 1 of the paper, and the use of the shared PRNG to generate the permutation and sample pool is also specified in Algorithm 1.
More specific to our algorithm, the encoder samples an index K, conditional on X=x and the samples UˉN. It then encodes this index into the message M and communicates it to the decoder as shown in Algorithm 1. In turn, the decoder outputs Y=UˉK. Therefore the index K is the only quantity which needs to be communicated. In our revised manuscript, we have more explanation to Section 3.1 on the roles of the encoder, decoder and shared PRNG, in particular how the encoder and decoder generate the shared permutation and sample pool using the PRNG.