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

# 可扩展的离散到连续信道模拟用于压缩与隐私  
来源：https://arxiv.org/html/2609.12067  
Buu Phan, Ashish J. Khisti  
隶属部门：多伦多大学电气与计算机工程系  
邮箱：{joseph.rowan,truong.phan}@mail.utoronto.ca, [email protected]  

###### 摘要  
信道模拟近来已成为机器学习系统中一个有用的组件，用于压缩来自指定概率分布的样本。然而，通用信道模拟算法通常计算成本高昂、存在随机停止时间，或在最坏情况下可能需要生成无限多个共享随机样本。本文提出一种用于精确和近似模拟离散到连续信道的方案，该方案反而使用固定数量的随机样本，因此运行时时间与信道和输入无关。不同于现有方案从提议分布生成独立样本序列，我们的方法针对每个潜在目标分布生成一个样本，或固定数量的样本。随后在使用指数竞赛进行样本选择前，对样本应用潜在排列。该方案在生成样本数量与压缩率之间提供了灵活的权衡。通过采用极化编码和多级编码，我们将方法扩展至处理长分组长度，时间复杂度为 \(O(n \log n)\)，从而降低每符号开销。最后，我们展示了该方案在两个应用中的效果：通过随机VQ-VAEs实现变率压缩，以及通过精确模拟高斯机制实现通信高效的差分隐私分布式均值估计。  

## 1 引言  
在信道模拟中，一方称为*编码器*，观察源 \(X \in \mathcal{X}\)，其中 \(X \sim P_X\)，并向另一方（*解码器*）发送消息 \(M\)。解码器利用该消息输出随机变量 \(Y\)。此处，\(Y\) 必须遵循指定的条件分布 \(P_{Y|X}(\cdot \mid X)\)（称为*信道*），而 \(M\) 的期望比特长度 \(\mathbb{E}[\ell(M)]\) 应尽可能小。为协助降低通信成本，我们假设编码器和解码器均可访问共享随机变量 \(W\)。从这个角度看，信道模拟提供了一种通用方法，将 \(X\) 的噪声版本压缩为二进制表示，其中添加到 \(X\) 的噪声量和类型由 \(P_{Y|X}\) 的选择控制。它也可被视为有损压缩方法（如量化）的随机推广，这些方法同样扰动源并产生离散表示。因此，它已成为神经压缩架构中的关键构建模块，因为量化的确定性在训练期间可能带来困难 (Flamich and Gündüz, 2026)，并已应用于隐私领域 (Liu et al., 2024)。  

\(X\) 和 \(Y\) 的性质直接影响信道模拟任务的难度。虽然已有许多针对任意概率空间的构造，特别是泊松泛函表示 (PFR, Li and Gamal, 2018)、基于拒绝采样的方案 (Flamich et al., 2023; Phan and Khisti, 2025) 以及利用重要性采样的近似方法 (Havasi et al., 2019; Phan et al., 2024)，但这些方法可能因 \(P_{Y|X}\) 缺乏额外限制而速度缓慢、运行时间高度可变，或在样本数较少时产生有偏输出。最关键的是，已知的精确通用方法在最坏情况下需要生成无限多个样本，使其在实际应用中吸引力降低。相比之下，当 \(Y\) 离散时，指数泛函表示 (EFR, Li and Gamal, 2018) 可用于在 \(O(|\mathcal{Y}|)\) 时间内精确模拟任何信道，共享随机性由 \(|\mathcal{Y}|\) 个指数随机变量组成。我们关注互补情况：\(\mathcal{X}\) 离散但 \(\mathcal{Y}\) 连续（这自然出现在连续噪声扰动离散输入数据的情况下），并探究此问题是否也能用*固定数量*的共享随机性样本解决。本文的首要目标是通过引入一种我们称之为*置换方案*的方法来肯定回答，该方案使用 \(2|\mathcal{X}|\) 个随机样本实现任何离散输入、连续输出信道的通信高效模拟。  

在机器学习应用中，另一个挑战是待模拟的信道通常涉及高维空间，例如潜在向量、梯度或网络权重。一方面，增加信道维度（也称为分组长度）有助于摊销通信开销。例如，PFR 实现的消息期望长度最多为 \(I(X;Y) + \log(I(X;Y)+2)+3\) 比特 (Li, 2024)；将 \(n\) 次独立使用扩展至信道可得每样本 \(I(X;Y) + \log(nI(X;Y)+2)/n+3/n\) 比特，当 \(n \to \infty\) 时趋近于下界 \(I(X;Y)\)。不幸的是，PFR 及类似通用信道模拟方案的时间复杂度随 \(n\) 指数增长，使其在高维信道中不可行。近期工作转向现代编码理论技术，以加速跨多个独立维度的信道模拟 (Sriramu et al., 2024; Zhao and Li, 2026; Ozyilkan et al., 2026)，但其适用性仍限于二进制或其他离散输出。因此，我们的第二个目标是展示如何将极化编码框架同样融入置换方案，以实现长分组长度下可扩展的离散到连续信道模拟。  

总之，我们的贡献如下：  
1. 我们引入一种模拟通用离散输入、连续输出信道的方法，该方法使用固定数量的共享随机性样本，运行时时间与输入和 \(P_{Y|X}\) 的选择无关。我们进一步展示如何基于Sinkhorn-Knopp算法 (Sinkhorn, 1964; Knight, 2008) 的近似方法，使我们的方法在神经压缩等应用中扩展至大输入字母表（此时精确输出分布可能非必需）。  
2. 通过采用基于极化码 (Arıkan, 2009) 和多级编码 (MLC, Wachsmann et al., 1999) 的构造，我们扩展了置换方案可模拟的信道维度。该算法复杂度随信道维度增长为 \(O(n \log n)\)，使其在 \(n\) 较大时仍实用，并允许在长分组长度下操作（此时每符号开销降低）。  
3. 我们将方案部署于两个应用：首先，展示我们的离散到连续信道模拟如何用于实现VQ-VAEs (van den Oord et al., 2017) 的变率有损压缩（无需重训练）；其次，提出一种通过精确模拟高斯机制 (Dwork and Roth, 2014) 实现具有中心差分隐私 (CDP) 的通信高效分布式均值估计 (DME) 的方案。  
全文除特别说明外，对数底为2。熵、互信息和KL散度同底。序列 \(\{x_i\}_{i=1}^n\) 记为 \(x^n\)，\([n] = \{1,\ldots,n\}\)。  

## 2 背景与相关工作  
#### 单次信道模拟  
在*单次*设置中，编码器观察单个符号 \(X\)，解码器输出对应的 \(Y\)。由于 \(X\) 和 \(Y\) 不要求是标量，而可以是随机序列、向量或任何其他对象，单次设置最具一般性。Bennett et al. (2002) 和 Winter (2002) 在无限共享随机性下确立了信道模拟的理论性能界限，其下界为 \(I(X;Y)\)。Harsha et al. (2010) 引入了早期称为贪婪拒绝采样 (GRS) 的离散信道模拟算法，实现了近最优编码成本，后扩展至一般概率空间 (Flamich et al., 2023; Flamich and Theis, 2023)。采用共享泊松点过程作为公共随机性，Li and Gamal (2018) 提出了PFR（一种流行的精确信道模拟算法），其速率也达到互信息并具有对数冗余。近期，基于标准拒绝采样的方案也作为替代出现，具有类似理论保证 (Phan and Khisti, 2025; Hill et al., 2026)。  

#### 多次信道模拟  
多次设置指模拟信道 \(n\) 个独立同分布副本的任务，即乘积信道 \(P_{X|Y}^{\otimes n}\)。原则上，任何单次模拟算法都可通过将输入 \(X^n\) 视为一个高维符号扩展到多次情况。然而，虽然已有算法在特殊情况下改进单次模拟性能 (Flamich et al., 2022; Flamich, 2023; Hegazy and Li, 2022)，现有通用基于采样的方案无法良好扩展到长分组长度，因为其样本复杂度随联合互信息指数增长 (Li, 2024)。通过关注二进制输出信道，Sriramu et al. (2024) 设计了基于极化码 (Arıkan, 2009) 的多次算法，以 \(O(n \log n)\) 时间运行，从而利用长分组长度下降低的每符号开销。随后，Zhao and Li (2026) 引入了一族基于极化码和其他线性码的算法，将多次模拟扩展至有限域上的加性可交换噪声信道，而Ozyilkan et al. (2026) 推广至非平稳设置。然而，这些方法目前限于离散输出，或在长分组长度极化码构造下限于二进制输出，无法用于需要更丰富输出空间的情况。  

#### 在神经压缩与隐私中的应用  
信道模拟与有损压缩的联系由Winter (2002) 确立：任何信道模拟算法都可转换为有损压缩器 (Li and Gamal, 2018)。实践方面，Havasi et al. (2019) 使用近似模拟压缩网络参数，而Flamich et al. (2020) 将类似方法应用于图像。Theis et al. (2022) 定义了扩散模型的信道，并用PFR模拟以实现实约束下的图像压缩，Vonderfecht and Feng (2025) 使用近似构造加速至实用速度。Phan et al. (2024) 采用信道模拟作为具有解码器侧信息的图像压缩基础。这些方法通常使用来自\(\beta\)-VAEs或高斯扩散的连续潜在空间，因此受制于模拟通用信道的高计算成本，且实际限于短分组长度。通过改用我们的离散到连续方案和VQ-VAE的离散潜在空间，我们保留了基于信道模拟压缩的灵活性，同时通过联合处理多达8192个潜在变量块来减少编码开销。  

信道模拟也已应用于差分隐私 (DP, Dwork et al., 2006; Dwork and Roth, 2014)，该机制为向不可信方发布用户数据提供了一种有原则的保护方式。DP机制对数据 \(X\) 应用随机化隐私保护扰动，典型例子是加性高斯或拉普拉斯噪声，因此可被视为一个信道 (Li, 2024)。Feldman and Talwar (2021) 使用基于拒绝采样和伪随机性的近似模拟来降低本地差分隐私 (LDP) 机制的通信成本。Shah et al. (2022) 开发了基于重要性采样 (IS) 的方法。然而，这些方法是近似的，因为它们不保持目标噪声分布。在可信聚合器下，Hasırcıoğlu and Gündüz (2024) 和Hegazy et al. (2024) 使用抖动量化实现一维加性噪声机制的精确实现。Liu et al. (2024) 提出了一种通用方法，扩展PFR以精确模拟任何LDP或CDP机制，代价是继承PFR的成本和非确定性停止时间。我们提供了一种互补方法，可用于精确快速地模拟作用于离散输入（多达16进制字母表）的CDP机制。  

## 3 单次离散到连续信道模拟  
我们关注模拟从 \(X \in \mathcal{X}\) 到 \(Y \in \mathcal{Y}\) 的信道 \(P_{Y|X}\)，其中 \(\mathcal{X}\) 是有限集，同时要求共享随机性包含固定数量的样本。不失一般性，设 \(\mathcal{X} = [N]\)；为简便起见，我们假设对于每个实现 \(X=x\)，密度 \(p_{Y|X}(\cdot \mid x)\) 存在。满足我们要求的天真方案如下：  
1. 生成共享随机性 \(\bar{U}^N\)，其中 \(\bar{U}_i \sim P_{Y|X}(\cdot \mid i)\)。  
2. 在编码器处，观察 \(X=x\) 并选择索引 \(K=x\)。  
3. 选择