面向压缩与隐私的可扩展离散到连续信道模拟

核心问题是：离散输入、连续输出的信道能否用固定个数的共享随机样本做精确模拟，并在长块长上以 O(n log n) 时间运行。

• 场景：信道模拟中，编码器观察 X∼P_X，借助共享随机性 W 向解码器发消息 M，使输出 Y 服从给定信道 P_{Y|X}，同时尽量减小 E[ℓ(M)]。作者认为它是神经网络压缩（确定性量化不利于训练）和隐私机制的组件。
• 现有不足：作者称 PFR、基于拒绝采样的方案以及重要性采样近似，可能慢、运行时间高度可变，或在样本数较少时输出有偏；已知精确通用方法最坏需要生成无限个样本。离散输出可用 EFR 在 O(|Y|) 时间内精确模拟，但本文关心的是 X 离散、Y 连续。多发时 PFR 一类方法的样本复杂度随联合互信息指数增长；基于 polar 码的多发模拟目前限于离散或二元输出。
• 目标量：无限制共享随机性下的下界是 I(X; Y)。把 n 次独立使用摊到每个样本后，PFR 的超额项为 log(n I(X; Y)+2)/n + 3/n，随 n→∞ 趋于该下界，但时间随 n 指数增长。
• 本文提出：作者提出 permuted scheme（置换方案），用 2|X| 个随机样本精确模拟任意离散输入、连续输出信道，运行时间不依赖输入和 P_{Y|X}。大字母表用 Sinkhorn-Knopp 近似。再用 polar 码与多层编码（MLC）把维数扩到长块长，复杂度 O(n log n)。应用是不重训的变速率随机 VQ-VAE，以及用高斯机制精确模拟做通信高效的中心差分隐私（CDP）分布式均值估计（DME）。

作者在第 2 节按一次模拟、多次模拟和应用分组讨论。

• 一次信道模拟
  • Bennett 等（2002）与 Winter（2002）——在无限共享随机性下给出信道模拟的性能界，下界为 I(X; Y)。
  • Harsha 等（2010）的贪心拒绝采样（GRS）——离散信道上达到接近最优的编码代价；Flamich 等（2023）、Flamich & Theis（2023）将其推广到一般概率空间。
  • Li & Gamal（2018）的 Poisson functional representation（PFR）——以共享泊松点过程为公共随机性，精确模拟且速率达到互信息加对数冗余；Phan & Khisti（2025）、Hill 等（2026）给出基于标准拒绝采样、具有类似理论保证的方案。
• 多次信道模拟
  • 一次算法可把 X^n 当成一个高维符号来处理多次任务，但作者称一般基于采样的方案样本复杂度随联合互信息指数增长（Li, 2024）。Flamich 等（2022）、Flamich（2023）、Hegazy & Li（2022）只在特殊情形改进一次模拟。
  • Sriramu 等（2024）的 PolarSim——针对二元输出，用 polar 码在 O(n log n) 时间做多次模拟。Zhao & Li（2026）把 polar 及其他线性码扩到有限域上可加可交换噪声；Ozyilkan 等（2026）推广到非平稳情形。作者指出这些方法目前限于离散输出，长块长 polar 构造限于二元输出。
• 神经压缩与隐私
  • Winter（2002）、Li & Gamal（2018）建立信道模拟与有损压缩的联系。Havasi 等（2019）、Flamich 等（2020）、Theis 等（2022）、Vonderfecht & Feng（2025）、Phan 等（2024）用近似或 PFR 做参数或图像压缩；作者称连续潜空间（β-VAE、高斯扩散）受通用信道模拟代价限制，实际限于短块长。
  • 差分隐私方面，Feldman & Talwar（2021）、Shah 等（2022）用拒绝采样或重要性采样降低本地差分隐私（LDP）通信，但是近似、不保持目标噪声分布。Hasırcıoğlu & Gündüz（2024）、Hegazy 等（2024）在可信聚合器下用抖动量化精确实现一维加性噪声。Liu 等（2024）把 PFR 推广为可精确模拟任意 LDP 或 CDP 机制，同时继承 PFR 的代价与非确定停止时间。

基线与基准：压缩实验比较固定码本的确定性 VQ-VAE，以及同一变速率模型上的 coupled importance sampling（IS，Phan 等，2024；与 ordered random coding 相关），数据为上采样到 64×64 的 CIFAR-10。隐私实验以 PFR 为信道模拟基线，并在附录与抖动量化比较；设置是高斯机制下的 CDP 分布式均值估计。

作者把本文定位为：对离散输入、连续输出这一更窄但实用的类，用固定样本数做精确或近似模拟，并用 polar 与多层编码扩到长块长；相对 Liu 等（2024），提供可精确且较快模拟、作用于至多 16 元字母的 CDP 机制的互补做法。

整体思路是 permuted scheme：不为每个候选输出抽一串独立提议样本，而是从每个潜在目标分布各抽固定个样本，随机置换后再用指数竞赛选出要发送的索引。

问题设定与朴素方案为何失败

• 设定：X 取有限字母表，不失一般性 X=[N]，每个 x 上密度 p_{Y|X}(·|x) 存在。编码器与解码器共享伪随机数发生器。目标是精确（或大 N 时近似）实现 P_{Y|X}，并使 E[ℓ(M)] 接近互信息而非 H(X)。
• 朴素方案：共享 Ū_i ∼ P_{Y|X}(·|i)，编码器直接发送 K=X，解码器输出 Ū_K。输出分布正确，但通信量至少 H(X)，一般远大于 I(X; Y)。
• 只随机化索引不够：附录 A 以 BI-AWGN 为例说明，在样本分布固定时，保持输出分布的唯一解是 K=X。必须再对样本池 Ū^N 做额外随机化。

一次置换方案与指数竞赛

• 三步：先抽 [N] 上的均匀随机置换 Π，再令 Ū_{π(i)} ∼ P_{Y|X}(·|i)。编码器观察 X=x 后，按 P_{K|X,Ū^N}(k|x,u^N)=Pr[Π(x)=k | Ū^N=u^N] 抽样 K；该分布在给定 Ū^N 后与 Π 条件独立。再把 K 无损编码成 M，解码器输出 Y=Ū_K。
• 精确性：Proposition 1 称该方案精确模拟 P_{Y|X}（证明在附录 B.1）。置换用完后，编码器与解码器都把样本当作边缘同分布，不再使用 Π（Figure 1）。
• 编码：用共享的独立 Exp(1) 序列 S^N 做指数竞赛（EFR）。按 S_i/q_i 排序得到 σ，其中 q 是解码器先验 P_{K|Ū^N}；编码器取 K=arg min S_i/p_i，发送其在排序中的位置 K̄。Theorem 1 给出 E[log K̄] ≤ I(X; Y | Ū^N)+1，以及 E[ℓ(M)] ≤ I(X; Y | Ū^N)+log(I(X; Y | Ū^N)+2)+3。附录 C 讨论该上界与 PFR、GRS 的差别，核心是条件互信息 I(X; Y | Ū^N) 而非 I(X; Y)。
• 后验：由似然矩阵 L_{ij}=p_{Y|X}(u_i|j) 写成永久式之比，见式 (4)。永久式是 #P-完全的，作者称 N 到大约 16 仍快，CDP 实验用精确永久式。N=256 的 VQ-VAE 用 Sinkhorn-Knopp 迭代近似，牺牲精确性；细节在附录 E.1。

每模式 m 个样本

• 推广：每个模式抽 m 个独立样本，索引 K_m 取在 [Nm] 上，目标分布是该模式被分配到的 m 个下标的均匀份额，见式 (6)。Proposition 2 称仍精确模拟。
• 速率：通信代价由 I(X; Y | Ū^{Nm}) 决定。由 I(X; Y | Ū^N)=I(X; Y)+I(X; Ū^N | Y)，增大样本池可减小给定 Y 时 X 与被拒样本的依赖。Theorem 2 只对 N=2 证明：m→∞ 时 lim sup E[ℓ_m(M)] ≤ I(X; Y)+log(I(X; Y)+2)+3。作者称一般 N 留待以后，并预期结论可推广；第 4、5 节实验取 m=1。

用 polar 码与多层编码扩展块长

• 直接扩展的瓶颈：n 次独立使用时，式 (8) 的每符号上界随 n 趋于 I(X; Y | Ū^N)，但二元信源的似然矩阵大小为 2^n，Sinkhorn 近似同样很快不可行。
• N=2：后验等价于交叉概率 δ(u^2) 随共享样本变化的 BSC，见式 (9)–(12)。作者不在 polar 变换内交织自定义置换，而把 w_i=u_i^2 视为双方已知的边信息，(x_i, w_i) 为独立同分布。附录 D 的 Algorithm 2 与 Theorem 4 称，修改后的 PolarSim 在 n 增大时每用信道的通信代价趋于 I(X; Y | Ū^2)。
• 更大字母表：令 m=log N，把 K 写成比特 B^m，用链式法则拆成 m 个二元抽样。第 l 层的交叉概率由式 (13) 从后验归并子集得到。每层边信息为 w_i=(u_i^N, b_i^{l-1})。式 (14)(15) 称，各层代价在 n→∞ 时相加等于 I(X; Y | Ū^N)。

两个应用中的信道

• 随机 VQ-VAE：编码器得到离散索引 k_i^*=arg min ‖f(W)_i−c_k‖_2。作者把固定码字换成各向同性高斯 N(μ_k, diag(σ_k^2))，并用损失条件训练（Dosovitskiy & Djolonga, 2020）让标量 λ 在推理时缩放方差、调节解码器，从而一个检查点覆盖一段速率–失真，无需重训。送入模拟器的符号是这些索引，信道为上述高斯。
• CDP 均值估计：C 个客户端各持 X_i，可信聚合器要估计均值，对不可信第三方发布。对每个 X_i 施加同一高斯机制得到 Y_i。隐私参数给定后，目标是减小 E[‖μ̂−μ‖_2^2]。精确模拟保证与未压缩高斯机制在给定 ε 下有相同的期望 MSE。噪声尺度由 Rényi DP accountant（Mironov, 2017）计算。

实验设置

• 压缩模型与数据：所有模型共用 van den Oord 等（2017）的 VQ-VAE 结构。图像为 CIFAR-10，上采样到 64×64。字母表 N=256。每批 32 张图像给出 8192 个离散 latent，用第 4 节 polar-MLC 联合压缩，信道为 N(μ_x, diag(σ_x^2))，离散后验用 Sinkhorn-Knopp 近似。
• 压缩基线：分别训练的、码本更小的确定性 VQ-VAE（Figure 2 图例写 7 models）；同一变速率随机模型上，用 coupled IS（Phan 等，2024）替换 polar-MLC，chunk size 为 4、2、1。指标是 Rate（bits/latent）与 MSE（×10^{-3}），并给出 P05–P95 失真。
• 隐私设置：高斯机制实现 (ε, δ)-CDP，δ=10^{-6}。C=10^5 个客户端，本地向量维数 D=512。每个坐标在 [−1, 1] 上 16 个等间隔值上均匀分布，故 N=16。B=8 个 DME 实例联合编码，块长至 BD=4096。ε 取 [0.05, 30]。指标是 bits/sample、相对 I(X; Y) 与 I(X; Y | Ū^{16}) 的位置，以及编码时间。
• 隐私基线与实现：PFR；作者注明 Poisson private representation（Liu 等，2024）的期望编码代价高于 PFR，且 CDP 不需要它。Figure 3 右侧时间为 128 块、每块 4096 个样本的编码秒数及标准差；PFR 把客户端向量切成 8 样本的块。两种方法都不计入最后的算术/熵编码阶段。附录另与 Hasırcıoğlu & Gündüz（2024）的抖动量化比较，使用 3 个随机种子。
• 精确性差异：CDP 实验用精确永久式以保持隐私；VQ-VAE 的 N=256 使用近似后验。两种被测算法都做精确模拟，因此作者称在给定 ε 下与未压缩高斯机制有相同期望 MSE。
• 论文未报告：压缩实验的测试图像张数、训练步数、λ 的取值表，以及隐私实验中每个 ε 的速率是多少次重复的均值。Figure 3 右侧给出了时间的标准差，但未写重复次数。

主结果

压缩主结果在 Figure 2，隐私速率与时间在 Figure 3。Figure 2 的曲线没有逐点数值表，正文只给出速率区间和两端标注。

表格较宽，可左右滑动

设置	Polar-MLC	PFR	出处
ε=0.05，128×4096 编码时间（秒）	3.06 ± 0.32	58.7 ± 7.8	Figure 3
ε=2.19，同上	2.96 ± 0.12	182.2 ± 40.0	Figure 3
ε=4.33，同上	2.93 ± 0.03	1852.8 ± 75.5	Figure 3
ε=6.47，同上	3.03 ± 0.24	13148.9 ± 299.0	Figure 3
ε=8.61，同上	2.93 ± 0.03	59890.6 ± 1801.4	Figure 3

• 压缩：作者称单个随机模型在推理时选择速率，可在高速率处接近分别训练的固定码本模型；平滑达到 1.6 到 7.8 bits/latent，优于不同 chunk size 的 IS，相对固定速率模型只有较小的失真代价。Figure 2 右侧在 2.9 bits 与 7.8 bits 两档并列展示固定速率 VQ-VAE 与该变速率模型的 CIFAR-10 重建。MSE 的逐点数值论文未在正文列表。
• 隐私速率：作者称 Polar-MLC 在整个工作区间速率更低，主要因为能以实用速度联合编码每个客户端向量中的全部 4096 个样本。Figure 3 左图还画出 I(X; Y) 与 I(X; Y | Ū^{16})，并给出 P05–P95 速率带；各 ε 的 bits/sample 数值论文未在正文列表。
• 时间：表中 Polar-MLC 约在 2.93–3.06 秒，PFR 从 ε=0.05 的 58.7±7.8 秒增至 ε=8.61 的 59890.6±1801.4 秒。作者比较的是编码时间，且双方都不含最终熵编码。

与抖动量化的比较

• 测了什么：附录把 Polar-MLC 与 Hasırcıoğlu & Gündüz（2024）在同一 Figure 3 设置下比较。标量协议对 Y∼N(x, σ_ε^2)：抽 gamma 样本决定量化步长，加均匀抖动后量化，再用固定长度码，每坐标 b=⌈log_2(2⌊1/Δ+1⌋)⌉ 比特；4096 维是逐坐标重复再拼接。另设 N=16 但星座为边长 1 的 4 维超立方体顶点，以保持均值的 ℓ_2 敏感度，ε∈[0.05, 3]，3 个随机种子。Figure 9 给出 P05–P95 速率，正文未列表点数值。
• 结果：作者称固定长度构造在 ε→0 时不趋于 0 bits/sample，每坐标至少 1 比特。坐标逐维处理时，维数升高会增加开销；polar-MLC 与星座几何无关，可直接用于 4 维情形。
• 作者的说明：Kobus 等（2024）一类高维抖动目前做不到精确模拟，因而不能靠高斯机制的通常性质保证隐私。标量上也可改用 Elias gamma 等变长码；作者称在本问题中它不如固定长度码。条件于共享随机性的熵编码理论上可以更好，但每个实现都要新建码本，作者称实践中可能不可行，并留给以后。

其他消融与分析

• IS chunk size：Figure 2 比较 chunk size 1、2、4；作者称 polar-MLC 优于这些 IS 变体，未给出逐点速率差。
• m 的理论：Theorem 2 仅 N=2，且实验聚焦 m=1；作者称 m=1 已足以得到有竞争力的压缩速率，论文未报告 m>1 的实验数字。
• BI-AWGN 例：附录 A 的式 (29) 与 Figure 5 比较 I(X; K | Ū^2)、I(X; Y) 与 H(X)=1，SNR 从 −20 dB 到 15 dB；作者称低、高 SNR 两端 I(X; K | Ū^2) 变得非常接近信道容量。图中没有逐点读数。
• PFR 分块：隐私实验中 PFR 以 8 个样本为块，polar-MLC 以最多 4096 为块；这是实现设置，不是同一分块下的消融。
• 近似的代价：作者称大字母表必须近似，但 N 足够小时长块长仍可精确模拟，并在第 5.2 节用 N=16 演示。附录 E.1 讨论近似及其经验表现，正文未给出近似误差的数值。
• 负面结果：作者明确写出，只随机化索引不能在低于 H(X) 的速率上保持任意目标分布；抖动量化的固定长度码在 ε→0 时每坐标至少 1 比特，且逐坐标处理在 4 维星座上开销更大。

作者指出的局限与后续方向

• 多样本分析只做了二元输入：第 3.3 节写明，Theorem 2 出于技术原因限制在 N=2，一般情形留给以后，尽管作者预期结果可推广到更大的 N。（第 3.3 节）
• 条件熵编码未做：附录对抖动量化的比较写明，条件于共享随机性的熵编码以及离散到连续设定中可能的简化，留待以后；并为每个实现重建码本在实践中可能不可行。（附录，Figure 9 所在讨论）
• 更窄的信道类：结论写明，一般信道模拟在计算上仍然困难；在更窄但实际相关的信道类上寻找可扩展构造，作者认为是有希望的后续方向。（第 6 节）
• 高维精确高斯模拟不在本次实验范围：同一附录写明，带内层拒绝采样的更复杂方案计算更重，超出本次实验范围；Kobus 等（2024）的高维抖动变体目前不能精确模拟。（附录）

实验覆盖范围

• 压缩：一个随机 VQ-VAE 检查点，结构来自 van den Oord 等（2017），数据为上采样到 64×64 的 CIFAR-10；N=256，每批 8192 个 latent，信道为对角高斯，后验用 Sinkhorn-Knopp；对照是 7 个固定码本 VQ-VAE 以及 chunk size 为 1、2、4 的 coupled IS。速率约 1.6–7.8 bits/latent（第 5.1 节、Figure 2）。
• 隐私：高斯机制，(ε, δ)-CDP，δ=10^{-6}，C=10^5，D=512，每坐标 16 个等间隔值，B=8 因而块长至 4096；ε∈[0.05, 30]；对照为按 8 样本分块的 PFR。时间表覆盖 ε=0.05、2.19、4.33、6.47、8.61（第 5.2 节、Figure 3）。
• 另一几何：附录在 N=16 的 4 维超立方体顶点上比较抖动量化，ε∈[0.05, 3]，3 个随机种子（Figure 9）。
• 精确与近似的分工：永久式用于 N 大约到 16 的精确模拟；N=256 使用近似。实验中的 polar-MLC 取 m=1（第 3.2、3.3、5 节）。
• 论文未报告：Figure 2 各速率点的 MSE 数值、Figure 3 左图各 ε 的 bits/sample 数值、压缩实验的测试集张数，以及隐私速率曲线的重复次数。编码时间的标准差有报告，重复次数未写。

Rowan、Phan 与 Khisti 研究离散输入、连续输出信道的模拟：共享随机样本数固定，长块长用 polar 码与多层编码降到 O(n log n)。

信道模拟要让解码器的 Y 服从 P_{Y|X}，同时把消息长度压向 I(X; Y)。通用精确方法最坏需要无限样本，多次模拟的时间又随维数变差；已有 polar 加速限于离散或二元输出。

permuted scheme 从每个输入模式抽一个（或 m 个）样本，用均匀随机置换打乱索引，再按后验做指数竞赛，只发送获胜下标在排序中的位置。Proposition 1、2 给出精确模拟。一次上界是 I(X; Y | Ū^N) 加对数冗余，而不是 I(X; Y)；N=2 时 m→∞ 可使该上界回到以 I(X; Y) 为中心的形式。后验含矩阵永久式，N 大约到 16 可精确计算，更大则用 Sinkhorn-Knopp。多发时把问题看成带边信息的 BSC，再用 MLC 拆比特层，块长趋于无穷时每符号代价趋于 I(X; Y | Ū^N)。

在上采样 CIFAR-10 上，一个 N=256 的随机 VQ-VAE 于推理时选速率，覆盖约 1.6–7.8 bits/latent，作者称优于 chunk size 为 1、2、4 的 IS，相对分别训练的固定码本模型失真代价较小。在 (ε, 10^{-6})-CDP、10^5 个客户端、16 元坐标、块长 4096 的均值估计中，Polar-MLC 与 PFR 都精确模拟高斯机制；作者称前者在整个 ε 区间速率更低。编码 128 个这样的块时，ε=0.05 的时间是 3.06±0.32 秒，分块 PFR 为 58.7±7.8 秒；ε=8.61 时 PFR 为 59890.6±1801.4 秒，Polar-MLC 仍约 2.93±0.03 秒（Figure 3）。

作者的结论是：一般信道模拟仍然难，但在离散到连续这一更窄的类上，固定样本数加上 polar 与多层编码，已经能服务变速率潜变量压缩和通信高效的 CDP 均值估计。一般字母表的多样本速率极限，以及按共享随机性重做的熵编码，作者留作以后的工作。