acceptodds
Under review as a conference paper at ICLR 2027

Scalable Discrete-to-Continuous Channel Simulation for Compression and Privacy

Abstract

Channel simulation has recently emerged as a useful component in machine learning systems where samples from a prescribed probability distribution are to be compressed. We study the simulation of discrete-to-continuous channels and present a scheme which performs exact simulation using a fixed-size shared random pool containing one or more samples from each potential target distribution. Unlike sampling-based schemes which generate a potentially unbounded sequence of independent samples from a proposal distribution, the number of samples used by our algorithm is finite and fixed in advance. To the best of our knowledge, this is the first exact scheme with such a property for general discrete-to-continuous channels. The key ingredient in our approach is a latent permutation which hides the correspondence between the shared random samples and their generating distributions. We also provide a flexible tradeoff between the number of generated samples and the compression rate. Exploiting the structure exposed by our algorithm, we use polar and multilevel coding to scale to long blocklengths in time to benefit from reduced per-symbol overhead. In our experiments, exact simulation remains fast at large blocklengths, and for input alphabet sizes up to ; for larger alphabets our approach further admits a Sinkhorn-Knopp approximation of the posterior induced by the latent permutation. We give applications to variable-rate compression with stochastic VQ-VAEs and differentially private distributed mean estimation via exact simulation of the Gaussian mechanism, showing gains over baselines in both wall-clock speed and communication rate.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Channel simulation, Sampling, Information theory, Polar codes, Compression, Privacy

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_V1dUOpenReview ↗
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
AuthorsOpenReview ↗

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(nlog⁡n)O(n \log n) 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∣XP_{Y^n \mid X^n} = \prod_{i=1}^{n} P_{Y \mid X} and iid inputs XnX^n, 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)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)I(X;Y \mid \bar{U}^N) in our Theorem 1:

E[ℓ(M)]≤I(X;Y∣UˉN)+log⁡(I(X;Y∣UˉN)+2)+3.\mathbb{E}[\ell(M)] \leq I(X;Y \mid \bar{U}^N) + \log(I(X;Y \mid \bar{U}^N) + 2) + 3.

To simulate nn symbols through the channel, the overhead would therefore grow linearly in nn, and the overhead per symbol would be constant. To amortize the per-symbol overhead, we instead seek to jointly encode the nn simulated channel outputs. The overhead in our Theorem 1 can then apply only once across the entire block of nn 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.\mathbb{E}[\ell(M)] / n \leq I(X;Y \mid \bar{U}^N) + \log(n I(X;Y \mid \bar{U}^N) + 2) / n + 3 /n.

Unfortunately, as mentioned in Section 4 of our paper, jointly encoding nn NN-ary indices naively would require choosing between NnN^n 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)I(X;Y \mid \bar U^N) per channel use with only O(nlog⁡n)O(n \log n) 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=xX = 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 Π\Pi and sample pool UˉN\bar{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 KK, conditional on X=xX = x and the samples UˉN\bar{U}^N. It then encodes this index into the message MM and communicates it to the decoder as shown in Algorithm 1. In turn, the decoder outputs Y=UˉKY = \bar{U}_K. Therefore the index KK 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.

AuthorsOpenReview ↗

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 PP, P(i)=piP(i) = p_i, and given independent Si∼Exp⁡(1)S_i \sim \operatorname{Exp}(1), the index K=arg⁡min⁡iSi/piK = \arg\min_i S_i / p_i satisfies K∼PK \sim P. To reduce communication, the encoder and decoder also construct a common ordering of the indices using a prior distribution QQ which is known by the decoder. This is done by sorting Si/qiS_i / q_i in increasing order. When PP and QQ 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 P=PK∣X,UˉNP = P_{K \mid X, \bar{U}^N} and Q=PK∣UˉNQ = P_{K \mid \bar{U}^N}, 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 nn 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 O(nlog⁡n)O(n \log n) 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 (Ber⁡(1/2)\operatorname{Ber}(1/2)) 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 UˉN\bar{U}^N is the specific side information which we consider. Second, our modification also extends PolarSim to the case where our discrete input XX has a non-uniform prior, which in turn implies a non-uniform prior on the output index KK, 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.

AuthorsOpenReview ↗

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 (ε,δ)(\varepsilon, \delta)-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 H(X)H(X) bits to send its vector XiX_i, 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 I(X;Y)≤H(X)I(X;Y) \leq H(X), where each Yi=Xi+ZiY_i = X_i + Z_i with ZiZ_i 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 μ^\hat{\mu}, not the individual client vectors. As stated above, the formal definition of (ε,δ)(\varepsilon, \delta)-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.

Reviewer_U5FSOpenReview ↗
Rating
3
Confidence
2(+1)
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies discrete-to-continuous channel simulation, where existing exact methods may require an unbounded number of random samples and are difficult to scale to long blocklengths. To address these problems, the authors propose a permuted scheme that uses a latent permutation and a fixed number of shared random samples to achieve exact simulation. They further adopt polar coding and multilevel coding to support long blocklengths with O(nlog⁡n)O(n\log n) complexity, and use a Sinkhorn-Knopp approximation for larger input alphabets. Experiments on variable-rate compression with stochastic VQ-VAEs and distributed mean estimation with central differential privacy demonstrate improvements in communication rate and encoding time over the compared baselines.

Critical strengths
  1. The permuted scheme addresses a meaningful limitation of existing exact channel simulation methods. It enables exact simulation of general discrete-to-continuous channels using a finite, fixed number of shared random samples, supported by a mathematical proof. This provides a clear technical advantage over existing sampling methods that may require an unbounded number of samples.

  2. By adopting polar coding and multilevel coding, the proposed method scales to long blocklengths with O(nlog⁡n)O(n\log n) complexity for a fixed input alphabet size. Experiments on variable-rate compression with stochastic VQ-VAEs and distributed mean estimation demonstrate improvements in communication rate and encoding time over the compared baselines, supporting the practical value of the proposed method.

Critical weaknesses

The practical advantage of the permuted scheme is not fully demonstrated. In Fig. 2, the proposed method uses polar coding over 8192 latents, while the importance sampling baseline uses much smaller chunks. Appendix E.5 introduces importance sampling with polar coding, but does not compare it with the proposed method in the same compression experiment. Therefore, it remains unclear how much of the improvement in rate and encoding time comes from the permuted scheme itself.

Questions for authors
  1. We would like the authors to provide a direct comparison with the polar coding based importance sampling method introduced in Appendix E.5, using the same VQ-VAE and blocklength. Comparing the compression rate, distortion, and encoding time would help clarify how much of the improvement in Fig. 2 comes from the permuted scheme itself rather than from polar coding.
6 comments
AuthorsOpenReview ↗

Response (1/4)

Thank you for your insightful comments and feedback on our work. We are glad that you found the theoretical novelty of our permuted scheme, in particular its ability to achieve exact channel simulation with a fixed number of random samples, compelling and distinct from prior works. We also appreciate your mention of the practical value of our multilevel polar construction for channel simulation and its applications at long blocklengths.

Please find your concerns addressed below. In particular, we would like to take this opportunity to clarify some aspects of the comparison in Fig. 2 with the established importance sampling (IS) baseline, and the exploratory note on polar-coded IS raised in Appendix E.5.

AuthorsOpenReview ↗

Response (2/4)

1. Comparison with the importance sampling baseline and chunk sizes:

In Fig. 2, the IS baseline under consideration, which we refer to as "coupled IS" or simply "IS" in the figure, represents the established approach used in [1], where it is referred to as "communication efficient importance sampling based compression" (CE-ISC). This existing scheme is very closely related to ordered random coding (ORC), earlier introduced in [2]. It is conceptually and operationally distinct from the polar-coded IS construction in Appendix E.5, which is our own separate exploratory contribution, not an established baseline or ablation, and will be further discussed in our second point to follow below.

In the Fig. 2 comparison, both the CE-ISC baseline and our polar-coded permuted scheme (which we will call polar-permuted for short) need to encode all 8192 latents to transmit one batch of (upscaled) CIFAR-10 images. This number of latents is fixed by the VQ-VAE architecture, which downsamples the inputs to produce 64 latents for each input image, and the two channel simulation schemes are evaluated using the same trained VQ-VAE network. The key difference is that the baseline divides the latents into chunks of B=1,2,4B = 1,2,4, and only applies joint encoding within each chunk. Crucially, the small chunk sizes are not an arbitrary restriction, but rather an inherent limitation of the CE-ISC and ORC schemes, which our polar-permuted method overcomes in order to realize the gains made possible by operating at a longer blocklength. Indeed, this favorable scaling is the second key contribution of our work which we list in the Introduction. For CE-ISC, the number of importance samples required to faithfully simulate a chunk of BB independent channel uses scales exponentially with the total mutual information in the chunk, and hence with BB. This exponential complexity is common to one-shot sampling-based channel simulation schemes in general, as we mention in Section 1; a more detailed discussion of related sample complexity results may be found in [3, Section 3.5]. The complexity limitation also applies to the PFR baseline used for the privacy experiment in Section 5.2.

We provide a small additional experiment to further clarify the choice of chunk size, where we test the CE-ISC baseline on 40 batches at sample counts S=214,216,218S = 2^{14}, 2^{16}, 2^{18}, chunk sizes B=2,4,8,16B = 2, 4, 8, 16 and a representative mid-range operating point with λ=0.015\lambda = 0.015. In the table, we show the time/batch and standard deviation, along with the average MSE and rate. Recall that in the paper, we choose to use 2162^{16} 64-dimensional importance samples per chunk to evaluate the CE-ISC baseline. Increasing BB at a fixed sample count leads to a poor approximation of the target distribution, reflected in the rapid increase in reported distortion when BB goes beyond 4. On the other hand, increasing the sample count above 2162^{16} severely increases the compute and memory costs of the CE-ISC baseline and only provides a limited benefit in terms of how large BB can be made before worsening rate-distortion performance. On an L40S GPU, we run out of memory above 2182^{18} samples.

Time/batch (s)Avg. MSEAvg. rate (bits/latent)
S=214S=2^{14}, B=2B=25.379 ± 0.0060.0014974.58
S=214S=2^{14}, B=4B=45.041 ± 0.0040.0020323.71
S=214S=2^{14}, B=8B=84.861 ± 0.0030.0059722.15
S=214S=2^{14}, B=16B=164.774 ± 0.0020.0145221.10
S=216S=2^{16}, B=2B=220.002 ± 0.0070.0014814.60
S=216S=2^{16}, B=4B=419.662 ± 0.0050.0017293.95
S=216S=2^{16}, B=8B=819.483 ± 0.0030.0046472.43
S=216S=2^{16}, B=16B=1619.394 ± 0.0030.0123351.25
S=218S=2^{18}, B=2B=277.199 ± 0.0140.0014814.60
S=218S=2^{18}, B=4B=476.857 ± 0.0090.0015894.08
S=218S=2^{18}, B=8B=876.671 ± 0.0080.0037392.70
S=218S=2^{18}, B=16B=1676.576 ± 0.0070.0104991.40

On the other hand, our polar-permuted scheme achieves an MSE of 0.001479 using 3.54 bits/latent on average and, as reported in Table 3, Appendix E.3, takes just 0.59 ± 0.18 s/batch. It does not require tuning sample counts or chunk sizes. Indeed, the CE-ISC baseline is more expensive despite operating on much smaller chunks, while our method's ability to incorporate the polar coding framework developed in Section 4 to jointly encode all 8192 latents efficiently is a primary reason why it outperforms in terms of rate and encoding speed.

Our new results and remarks on this point have been added to Appendix E.3 in our revised PDF.

AuthorsOpenReview ↗

Response (3/4)

2. Clarification and evaluation of polar-coded importance sampling in Appendix E.5 (part 1/2):

We appreciate the interest in our preliminary treatment of a polar-coded IS construction (which we will call polar-IS) in Appendix E.5. We would first like to clarify that this scheme is not an ablation of the permuted scheme. Instead, it is a different algorithm for approximate channel simulation which combines IS and multilevel polar coding with side information, as developed in Section 4 of this paper, intended to highlight potential wider applications of those techniques. Its sampling mechanism differs significantly from the permuted scheme, and it cannot achieve exactness with a finite number of samples. In contrast, our Proposition 1 is a key part of our theoretical contribution and shows that the permuted scheme can perform exact simulation. Moreover, we have not developed theoretical rate guarantees for the polar-IS scheme as its inclusion was intended as an exploratory remark and a potential direction for future work, rather than an established baseline or component of the proposed method.

It is also fundamentally different from the established CE-ISC baseline used for Fig. 2, rather than being a one-for-one replacement of the entropy code with polar coding. In conventional IS-based channel simulation, when scaling to nn channel uses, a single index KK selects one length-nn candidate vector from a set of proposals sampled according a joint proposal distribution Q×nQ^{\times n}, and KK is transmitted using a one-shot method like EFR. In contrast, Appendix E.5 proposes selecting a separate index KiK_i for each output coordinate, yielding an independent sequence KnK^n. These indices are then viewed as outputs of an induced memoryless discrete-output channel with side information and transmitted by our polar coding framework. This allows the new polar-IS construction to exploit long coding blocklengths without performing importance sampling on an exponentially large candidate pool.

We agree however that a direct comparison of these two polar-coded constructions would be interesting, and have scaled up our Appendix E.5 polar-IS method to provide this comparison using the same settings as Fig. 2. In this new experiment, polar-IS uses 282^8 samples per latent, equal to that used by the permuted scheme; higher sample counts run out of memory on our L40S GPU, and incur many high-dimensional Gaussian mixture likelihood evaluations for the IS prior. For both schemes, the VQ-VAE model is the same checkpoint used to generate Fig. 2 and the blocklength is 8192. We evaluate each scheme at 25 values of λ\lambda, which are geometrically spaced between 0.1 and 0.0005 as in Fig. 2. Results are shown in the table below, where we report comparable operating points to each deterministic baseline (Det.) with N=4,8,16,32,64,128,256N = 4, 8, 16, 32, 64, 128, 256 embeddings. Rates are in bits/latent and 3 random seeds are used. The standard error of the mean is less than 10−310^{-3} for the rate and 10−510^{-5} for the MSE for all operating points in the table, and is hence omitted for clarity. Note that due to the different sampling constructions, the required λ\lambda parameter to obtain a comparable rate may differ between the polar-permuted and polar-IS schemes, as reported in the table. Timings and remarks will follow in the next comment.

Rate (Det.)MSE (Det.)λ\lambda (Polar-Permuted)Rate (Polar-Permuted)MSE (Polar-Permuted)λ\lambda (Polar-IS)Rate (Polar-IS)MSE (Polar-IS)
7.800.000340.00057.800.000390.00057.230.00078
6.840.000460.00236.890.000530.00156.980.00076
5.870.000600.00365.960.000650.00365.720.00082
4.920.000780.00575.070.000830.00574.940.00095
3.900.001120.01103.920.001250.01103.870.00131
2.850.001730.02662.780.002180.02662.750.00221
1.850.003090.08021.780.004270.08021.770.00427
Reviewer_bfw1OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies channel simulation, where the goal is to design a protocol so that an encoder and decoder can simulate a channel (a conditional probability map) using a finite number of bits. The encoder and decoder have access to a shared random seed. The authors design a new protocol that requires finite sampling in the worst case and scales to the setting where we want to simulate multiple independent uses of the channel.

Critical strengths
  1. The authors design a new protocol that only uses finite random samples and scales nicely to the multishot setting, which is a notable improvement prior works.
  2. The authors demonstrate the effectiveness of the protocol in image compression, neural compression of VQ-VAE, and differential privacy applications.
Critical weaknesses
  1. CIFAR-10 is a small-scale dataset, both in terms of image resolution and dataset size. Experimental results on larger datasets will further support the scalability of the proposed protocol.
Questions for authors

Can the proposed algorithm scale to larger datasets like ImageNet?

3 comments

We thank you for your helpful comments, suggestions and assessment of our paper. We are happy to hear that you consider the finite-sample nature of the construction and its multi-shot scaling a notable improvement over prior works, and found the experiments to demonstrate the advantages of our protocol.

We also agree that demonstrating our proposed algorithm on a larger, higher-resolution dataset would be valuable, as it would further strengthen the case for polar-coded permuted scheme's scalability. To this end, we provide a new experiment on ImageNet at 128x128 resolution using the same VQ-VAE architecture, communication protocol and experimental setting discussed in Section 5.1 of our manuscript. Each image therefore yields 4x as many latent variables as in our upscaled CIFAR-10 experiment. We jointly compress 16 images at a time to give a longer blocklength of 16384 discrete latent variables, compared to 8192 in the original experiment which encoded 32 CIFAR-10 images.

In the table below we show the rate-distortion performance of our scheme (Ours) and the deterministic baseline (Det.). We evaluate our protocol on 1562 batches from the ImageNet validation set at 25 different values of the rate parameter λ\lambda and report below comparable operating points to each deterministic baseline with N=4,8,16,32,64,128,256N = 4, 8, 16, 32, 64, 128, 256 embeddings. Interestingly, the MSE disadvantage of our stochastic encoder at low rates on CIFAR-10, which was seen in Fig. 2 in the paper, does not show up on ImageNet. Rates are in bits/latent and 3 random seeds are used. The standard error of the mean is less than 10−310^{-3} for the rate and 10−610^{-6} for the MSE for all operating points in the table, and is hence omitted for clarity.

Rate (Det.)MSE (Det.)λ\lambda (Ours)Rate (Ours)MSE (Ours)
7.570.001930.00057.940.00197
6.670.002200.00366.810.00226
5.750.002580.00575.780.00251
4.810.003050.00884.740.00288
3.870.003650.01373.820.00341
2.900.004570.02662.740.00455
1.980.006160.05162.010.00607

Below, we also report batch timings and standard deviation for the end-to-end image encoding and decoding system using our protocol on ImageNet, corresponding to the CIFAR-10 timings in Table 3, Appendix E.3. While the VQ-VAEs take longer to train on ImageNet, the time taken for our protocol to encode and decode the images at test-time is only slightly larger than that observed for CIFAR-10, showing that the method scales well to the more demanding setting.

CIFAR-10 (32 images, 8192 latents)ImageNet (16 images, 16384 latents)
Time/batch (s)0.585 ± 0.1830.781 ± 0.091

The new experiment has been incorporated into the revised Appendix E.3, including a full rate-distortion plot in Fig. 10.

Thank you for incorporating new experiments. My assessment remains positive for this paper.

Thanks again for your positive assessment of our work and your suggestions. We appreciate that you found the new experiment useful, as we also feel it has strengthened the paper.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Response Summary

We thank all reviewers for their thoughtful feedback and constructive suggestions, and appreciate that reviewers collectively recognized the novelty of the permuted scheme, its improvements over prior channel simulation approaches, and the practical value of scaling the method to long blocklengths along with our applications to neural compression and differential privacy.

We have taken the questions and concerns raised into careful consideration and have provided new experiments and clarifications to address them. Full details are provided in our individual responses to each review below, while here we summarize the main additions and revisions:

  1. Larger-scale validation: We have extended our VQ-VAE neural compression experiment from Section 5.1 to ImageNet at 128x128 resolution while simultaneously increasing the blocklength to 16384 latents. The new rate-distortion and runtime results support the scalability and practical effectiveness of our approach. These results are included in the revised PDF in Appendix E.3.

  2. Additional comparisons and clarifications on importance sampling: We clarified aspects of the importance sampling baseline in Fig. 2, in particular the choice of chunk size. We added an experiment further demonstrating the limitations of the baseline as the chunk size and sample count increase, in terms of computational cost and rate-distortion performance, which motivates the choices made for our Fig. 2 comparison. This new material has also been inserted into the updated Appendix E.3.

    We have also clarified the role of the exploratory polar-coded importance sampling idea from Appendix E.5 as distinct from the importance sampling baseline, and substantially expanded its experimental evaluation to consider image compression with the same VQ-VAE and blocklength as our proposed permuted scheme, as in Fig. 2. As requested, this comparison clarifies the distinct contributions of the permuted sampling scheme and polar coding to our speed and rate-distortion gains. In particular, it shows that the multilevel polar coding techniques we develop in Section 4 are crucial for encoding speed and scalability, while the use of the permuted scheme itself achieves lower distortion at medium-to-high rates. Results and discussion are added to the revised PDF in Appendix E.5.

  3. Improved exposition and clarifications: We have expanded the explanations of the motivation for O(nlog⁡n)O(n \log n) multi-shot simulation, the encoder-decoder setup with shared randomness and the shared permutation, the exponential race, and PolarSim. We have also clarified the central differential privacy model, moving the formal definition into the main paper, and the distributed communication model used in Section 5.2. These changes appear in the revised PDF in Sections 1, 3.1, 4, 5.2 and Appendix E.4.

We believe that the additional evidence and clarifications strengthen our paper, and hope they satisfactorily address all reviewers' concerns. We respectfully invite the reviewers to reconsider their assessments and scores in light of these additions, and would be happy to address any further questions during the discussion period.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.