Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation¶

会议: NeurIPS 2026
arXiv: 2601.21636
OpenReview: https://openreview.net/forum?id=krYjrhQMCu
领域: LLM 安全
关键词: 差分隐私, 矩阵机制, 随机分配, Rényi散度, 条件组合

一句话总结¶

针对带随机分配（小球落桶）子采样的矩阵机制隐私放大分析，提出首个无须蒙特卡洛采样的确定性隐私记账框架，分别构建基于循环带状动态规划的精确 Rényi 记账器与基于反向风险函数的条件组合记账器，彻底消除了蒙特卡洛记账对失效率 $\delta$ 倒数采样的算力开销与概率性松弛。

研究背景与动机¶

差分隐私随机梯度下降（DP-SGD）是深度学习保护训练数据隐私的核心范式，其通常依赖子采样放大机制以较小的加噪量维持强隐私保证。然而，传统理论最常采用的泊松子采样（Poisson Subsampling）在工程落地上存在显著短板：每个 epoch 内数据点是否入选完全独立，导致约 $1/e$（约 36.8%）的样本在一个周期内完全未被访问，造成数据遍历不均匀、批次大小动态波动并增大梯度方差。为了克服这一缺陷，随机分配（Random Allocation，亦称小球落桶 Balls-in-Bins 或平衡迭代子采样）应运而生。它在 epoch 开始前将样本均匀划分至各个固定批次并在多轮中复用，严格保证了每个样本的参与次数，兼具泊松采样的隐私放大红利与确定性划分的工程高效性。

与此同时，引入步间相关噪声的矩阵机制（Matrix Mechanism）通过对高斯噪声进行线性变换 $\mathbf{C}^{-1}\mathbf{Z}$，显著降低了跨迭代累积噪声的方差，并在带状矩阵（BandMF、BSR）与带状逆矩阵（BandInvMF、BISR、BLT）等结构下大幅压缩了显存开销。近期研究尝试将随机分配与矩阵机制相结合，但现存唯一的隐私记账工具完全依赖蒙特卡洛经验采样。这种经验采样存在两大致命缺陷：其一，给出的 $(\varepsilon,\delta)$-DP 保证本质上仅是以高概率成立的统计推断，若要转化为确定性保证则必须迫使训练机制引入随机弃权；其二，为验证失效率 $\delta$，蒙特卡洛所需的采样规模与 $1/\delta$ 成正比。在严格隐私预算（如 $\delta=10^{-8}$）下，验证开销比 $\delta=10^{-3}$ 暴增十万倍，在实际模型训练前期的超参标定中变得不可承受。

尽管近期针对无关联噪声的标准 DP-SGD 提出了确定性解析界，但矩阵机制固有的步间梯度相关性使得输出分布构成了高维非因式分解的高斯混合分布，传统以单步独立卷积为基础的隐私损失分布（PLD）方法完全失效。核心 idea：利用策略矩阵带状结构将主导对分布的 Rényi 散度归结为循环带状 Gram 矩阵的高效前向动态规划，并结合反向风险函数与高斯混合极值尾部界建立条件组合机制，在完全不依赖经验采样的前提下分别攻克低隐私区与高隐私区的确定性紧致隐私记账。

方法详解¶

整体框架¶

本文构建了针对随机分配矩阵机制的双轨确定性记账流程。给定下三角策略矩阵 $\mathbf{C} \in \mathbb{R}^{N \times N}$（$N = k \cdot b$ 为总步数，$k$ 为 epoch 数，$b$ 为单 epoch 批次数），系统首先计算各批次高斯混合均值 $\mathbf{m}_i = \sum_{j=0}^{k-1} |\mathbf{C}|_{:, i+jb}$ 及其内积 Gram 矩阵 $\mathbf{G}_{i,j} = \langle \mathbf{m}_i, \mathbf{m}_j \rangle$。随后，针对不同隐私预算区间协同调用两套记账器：在低隐私区（$\varepsilon \ge 2 \sim 4$），基于循环带状动态规划精确计算整数阶 $\alpha$ 的 Rényi 散度并转化为 Hockey-stick 散度；在高隐私区（$\varepsilon \le 1$），通过条件组合将时序相关的高斯混合解耦为单步独立主导对，并结合变分尾部界与 PLD 快速卷积得到紧致界。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：策略矩阵 C 与随机分配参数<br/>N 步迭代 / k 轮 epoch / b 个批次"] --> B["构建混合均值与 Gram 矩阵<br/>m_i = 各轮 C 列绝对值和, G_ij = ⟨m_i, m_j⟩"]
    B --> C["1. 基于循环带状 Gram 矩阵动态规划的精确 Rényi 记账器<br/>前向动态规划打破循环相关，截断处理近带状逆矩阵"]
    B --> D["2. 基于反向风险函数与高斯混合尾部界的条件组合记账器<br/>反向风险检验单步主导，结合 AM-GM 与变分尾部界解耦"]
    C --> E["3. 截断 Gram 矩阵与温度变分尾部界的高效标定加速<br/>线性项剥离摊销噪声标定，FFT 卷积合成最终隐私曲线"]
    D --> E
    E --> F["输出：确定性 (ε, δ)-DP 严格保证与最佳噪声乘子 σ"]

关键设计¶

1. 基于循环带状 Gram 矩阵动态规划的精确 Rényi 记账器：解决多维高斯混合散度指数爆炸与循环依赖难题 在随机分配矩阵机制下，数据集相邻关系（“移除”邻近）对应的主导对分布为 $\hat{P} = \frac{1}{b}\sum_{i=1}^b \mathcal{N}(\mathbf{m}_i, \sigma^2 \mathbf{I}_N)$ 与 $\hat{Q} = \mathcal{N}(\mathbf{0}, \sigma^2 \mathbf{I}_N)$。精确计算整数阶 $\alpha$ 的 Rényi 散度需要对多项式展开的所有多重子集求和： $$R_\alpha(\hat{P}\|\hat{Q}) = \frac{1}{\alpha-1}\log \sum_{(r_1,\dots,r_\alpha)\in[1,b]^\alpha} \exp\left(\sum_{j_1 \ne j_2}^\alpha \frac{\mathbf{G}_{r_{j_1},r_{j_2}}}{2\sigma^2}\right) - \frac{\alpha \log b}{1-\alpha}$$ 对任意稠密 Gram 矩阵 $\mathbf{G}$，论文证明该求和可通过极大团计数归约到 #P-完全问题。然而当策略矩阵 $\mathbf{C}$ 具有带宽 $p$ 时，$\mathbf{G}$ 呈现循环带状（Cyclically Banded）结构。作者通过条件化前 $p-1$ 个时间步的计数值 $\mathbf{l} = (l_0, \dots, l_{p-2})$ 打破首尾循环约束，并利用前向动态规划递推维护状态空间，最后通过 Log-Sum-Exp 缝合首尾边界相互作用。算法运行时间为 $\mathcal{O}(b \cdot p \cdot \alpha^{2p})$，显存为 $\mathcal{O}(\alpha^p + bp)$。特别地，对于标准 DP-SGD（$p=1$），复杂度急剧缩减至 $\mathcal{O}(b \alpha^2)$，彻底推翻了先前 Feldman & Shenfeld (2025) 记账器 $\mathcal{O}(2^\alpha)$ 的指数复杂度。对于“添加”邻近方向，论文证明其解析上界为： $$R_\alpha(\hat{Q}\|\hat{P}) \le \frac{1}{2b\sigma^2}\sum_{j=1}^b \mathbf{G}_{j,j} + \frac{\alpha-1}{2b^2\sigma^2}\sum_{i=1}^b \sum_{j=1}^b \mathbf{G}_{i,j}$$ 数值实验证明“移除”方向的边界始终严格主导“添加”方向，取二者最大值后利用 Canonne 转换公式转化为标准 $(\varepsilon,\delta)$-DP。

2. 基于反向风险函数与高斯混合尾部界的条件组合记账器：破解高隐私区 Rényi 散度固有松弛与时间跨步依赖 在严格隐私约束（小 $\varepsilon$）下，Rényi 转换公式会产生不可忽视的过估计，且步间噪声相关性打破了各步主导对的独立性。为此，论文引入条件组合范式：若能在除小概率“坏事件”集合 $E$（概率 $\delta_E$）之外的条件下，证明每一步的条件输出分布都被独立的单步主导对 $(P^{(n)}, Q^{(n)})$ 支配，则整体机制满足： $$H_\gamma(P\|Q) \le H_\gamma\left(\bigotimes_{n=1}^N P^{(n)} \Big\| \bigotimes_{n=1}^N Q^{(n)}\right) + \delta_E$$ 针对混合均值递增序列 $0 \le m_{1,n} \le \dots \le m_{b,n}$，论文证明单步主导成立的充要条件是后验反向风险函数逐点有界：$P(z=i \mid z \le i, \mathbf{y}_{1:n-1}) \le P^{(n)}(z=i \mid z \le i)$。通过贝叶斯展开，该检验等价于三元高斯混合隐私损失函数 $L_i(\mathbf{y}_{1:n-1}) = \log\left(\frac{p(\mathbf{y}_{1:n-1}\mid z<i)}{p(\mathbf{y}_{1:n-1}\mid z=i)}\right)$ 的极值尾部界。论文绕过松弛的 Chernoff 界，直接利用算术-几何均值不等式（AM-GM）推导得出行析正态分布累积分布函数（CDF）的解析闭式尾部界： $$\Pr_{\mathbf{y}\sim Q}[L_i(\mathbf{y}_{1:n-1}) \le \tau_i] \le \Phi\left(\frac{\tau_i - \nu}{\xi}\right)$$ 其中 $\nu, \xi$ 为均值向量的代数统计量。最后通过二分搜索求出阈值 $\tau_i$，自动构造出各步的离散混合权重，使得后续步骤可直接对接成熟的单步 PLD 快速傅里叶变换（FFT）卷积。

3. 截断 Gram 矩阵与温度变分尾部界的高效标定加速：实现任意非严格带状矩阵扩展与超快超参搜索 针对如 BISR、BandInvMF 等逆带状矩阵（$\mathbf{C}^{-1}$ 带状但 $\mathbf{C}$ 稠密）或 BLT 混合矩阵，其 Gram 矩阵虽非严格带状，但对角线外元素呈极速指数衰减。记 $\tau = \max_{\min(|i-j|, b-|i-j|) \ge p} \mathbf{G}_{i,j}$，论文将矩阵分解为带状截断部分与全 1 矩阵之和 $\mathbf{G} \le \mathbf{G}^{(p)} + \tau \mathbf{E}$，并证明只需在 Rényi 散度上补偿一个轻量可算的非负加项 $\frac{\tau \alpha}{2\sigma^2}$ 即可保证确定性上界的严格有效性。同时，论文将三元高斯混合隐私损失尾部界推广至变分概率族 $\Psi$。通过构造基于欧氏距离的温度 Softmax 变分族 $\psi(t) = \text{softmax}(-\|\mathbf{\mu}_i - \mathbf{\mu}_j\|_2^2 / t)$（温度集 $T = \{\infty\} \cup \{10^{-1}, 10^{-0.5}, 1, 10^{0.5}, 10^1\}$），在最小化方差的同时保持与各样本均值间的几何平衡，大幅收紧了多 epoch 下的反向风险跳跃。此外，在针对目标 $(\varepsilon, \delta)$ 反复调节噪声乘子 $\sigma$ 时，由于 $\tau_i$ 中占主导地位的计算量随 $\sigma$ 呈严格线性关系，预计算均值统计量后，后续单步评估的复杂度由 $\mathcal{O}(N^2 b^2)$ 摊销下降至 $\mathcal{O}(N b^2)$（“移除”）与 $\mathcal{O}(N b)$（“添加”），极大加速了训练前超参数搜索。

损失函数 / 训练策略¶

矩阵机制通过修改 DP-SGD 梯度聚合步骤注入相关噪声。设输入批次被裁剪至 $\ell_2$ 范数上限 $\Delta=1$。在第 $n$ 步迭代中，标准 DP-SGD 计算前缀和 $\mathbf{E}(\mathbf{G}+\mathbf{Z})$，而矩阵机制输出 $\mathbf{E}(\mathbf{G} + \mathbf{C}^{-1}\mathbf{Z})$，其中 $\mathbf{Z} \sim \mathcal{N}(\mathbf{0}, \sigma^2 \mathbf{I}_{N \times d})$ 为多维高斯噪声。由于线性变换矩阵 $\mathbf{E}\mathbf{C}^{-1}\mathbf{Z}$ 具有定制的相关性，使得跨步累积噪声方差远低于独立白噪声。机制标定目标是在给定用户隐私预算 $(\varepsilon, \delta)$（实验默认 $\delta=10^{-5}$）下，通过所提确定性记账器高效反解出最小合法噪声倍率 $\sigma$。CIFAR-10 验证采用标准 ConvNet，总步数 $N=970$步（$k=10$ epoch，批次大小 512），在保证确定性 DP 约束的同时优化端到端分类准确率。

实验关键数据¶

主实验¶

论文在标准 DP-SGD（$\mathbf{C}=\mathbf{I}$）及带状相关矩阵 BSR ($p=4, 64$)、BISR、BandMF、BandInvMF、BLT 等机制下系统评测了所提记账器（Rényi 记账器与条件组合记账器 Cond Comp）相对于蒙特卡洛采样记账器（MC Accountant，Choquette-Choo et al., 2025）的标定噪声乘子 $\sigma$ 及实际模型效用。

评估配置 ($N, k, p, \delta=10^{-5}$)	隐私预算 $\varepsilon$	Rényi 记账器 $\sigma$	条件组合记账器 $\sigma$	蒙特卡洛参考 $\sigma$	采样免除/确定性状态
DP-SGD ($N=1000, k=1$)	$\varepsilon = 0.5$ (高隐私)	14.82	9.12	8.85 (经验采样)	确定性紧致上界 (小 $\varepsilon$ 优势明显)
DP-SGD ($N=1000, k=1$)	$\varepsilon = 2.0$ (中隐私)	3.65	3.78	3.61 (经验采样)	确定性上界紧密贴合经验值
DP-SGD ($N=1000, k=1$)	$\varepsilon = 8.0$ (低隐私)	1.21	1.34	1.20 (经验采样)	Rényi 与 MC 几乎完全重合
BSR ($N=1000, k=10, p=4$)	$\varepsilon = 0.5$ (高隐私)	16.40	11.05	10.62 (经验采样)	成功抑制多轮步间相关性松弛
BSR ($N=1000, k=10, p=4$)	$\varepsilon = 2.0$ (中隐私)	4.85	4.98	4.79 (经验采样)	保持确定性理论保证
BSR ($N=1000, k=10, p=4$)	$\varepsilon = 8.0$ (低隐私)	1.62	1.80	1.61 (经验采样)	完美重合大偏差渐近线
CIFAR-10 准确率 (BSR, $\varepsilon=4$)	$\varepsilon = 4.0$ (测试准确率)	68.7% ± 0.4	68.3% ± 0.5	68.9% ± 0.4 (非严格)	捕获相关噪声相比 DP-SGD 的显著收益

消融实验¶

消融实验重点验证了：(1) Rényi 记账器在逆带状矩阵截断带宽 $p$ 时的精度与耗时平衡；(2) 条件组合记账器中不同变分分布对反向风险界及 $\sigma$ 的优化效果；(3) “添加”与“移除”邻近关系的边界活跃度。

消融配置项	变化维度 / 取值	记账指标影响	计算耗时 / 资源开销	核心机理与结论
Gram 矩阵截断 $p$ (BSR, $p=64$)	$p=64$ (无截断)	$R_\alpha = 0.428$ (基准)	耗时相对值 $1.0\times$	精确全宽求和，无额外加项
Gram 矩阵截断 $p$ (BSR, $p=64$)	截断至 $p=4$	$R_\alpha = 0.435$ (误差 <1.6%)	耗时下降至 $0.08\times$	非对角快速衰减，$\tau \alpha / 2\sigma^2$ 代价极小
Gram 矩阵截断 $p$ (BSR, $p=64$)	截断至 $p=1$	$R_\alpha = 0.492$ (误差 ~15%)	耗时下降至 $0.01\times$	截断过于激进，残差界开始变松
条件组合变分族	Option 1 ($T=\infty$ 几何均值)	后验上界 $\bar{\lambda}_b = 0.41$	基础耗时	仅利用均匀分布消除 KL 项
条件组合变分族	Option 2 (最大化均值)	后验上界 $\bar{\lambda}_b = 0.41$	基础耗时 $+15\%$	距离优化对均值偏移无明显收益
条件组合变分族	Option 3 ($T$ 距离变分 Softmax)	后验上界 $\bar{\lambda}_b = \mathbf{0.32}$	基础耗时 $+5\%$	成功压低高维方差，显著收紧小 $\sigma$ 区间
邻近方向比较	“添加”界 vs “移除”界	“添加”界始终严格低于“移除”界	“添加”界解析计算 $\mathcal{O}(1)$	证实“移除”方向全局主导，动态规划绝无浪费

关键发现¶

双轨互补特性极其显著：Rényi 记账器在大偏差（低隐私/大 $\varepsilon \ge 4$）区间紧致度极高，能够以极低算力逼近理论下界；条件组合记账器在小 $\varepsilon \le 1$ 区间克服了 Rényi 转换固有松弛，标定出的噪声乘子明显优于 Rényi 散度基准。
DP-SGD 算力跨代提升：对于无相关噪声的 DP-SGD，循环带状动态规划算法将计算复杂度从先前业界最先进的 $\mathcal{O}(2^\alpha)$ 降至 $\mathcal{O}(b \alpha^2)$。当需要高阶 $\alpha > 30$ 以验证极小 $\delta$ 时，原方法产生指数级爆炸崩溃，而本文方法在毫秒级内完成计算。
免采样彻底粉碎 $\mathcal{O}(1/\delta)$ 算力屏障：蒙特卡洛记账的采样规模严格正比于 $1/\delta$。当 $\delta$ 从 $10^{-3}$ 提高至严格的 $10^{-8}$ 时，蒙特卡洛耗时暴增 100,000 倍且仅提供概率性置信区间；本文两种方法计算时间与 $\delta$ 完全解耦，提供了坚实可靠的无条件确定性保证。

亮点与洞察¶

将连续高斯混合卷积转化为有限状态动态规划：在随机分配下，多步重叠的高斯混合看似极其棘手，但作者巧妙洞悉了带状相关矩阵在二阶统计量上的循环带状对称性，通过前向 DP 截断环路，完成了看似不可能的解析求解。
利用反向风险函数桥接时序依赖与独立卷积：面对长程噪声相关的时序过程，不强求直接计算全联合分布，而是借助反向风险函数的随机占优性质构建单步主导对，并结合变分尾部界将高维相关问题安全“降维”至标准 PLD 独立卷积。
工业级实用的噪声标定摊销：将反向风险二分搜索中耗时的均值计算剥离为与噪声大小无关的先验常量，使得在调参过程中评估不同 $\sigma$ 时的边际开销骤降一个数量级，真正具备了大规模工业部署实用性。

局限与展望¶

带宽度数引发的指数依赖不可避免：Rényi 记账器的算法复杂度对于矩阵带宽呈 $\mathcal{O}(\alpha^{2p})$ 指数依赖。当策略矩阵带宽 $p \ge 8$ 且需要较大 $\alpha$ 时，动态规划状态空间急剧膨胀，必须依靠带宽截断近似。作者在理论上证明了在一般 Gram 矩阵下该计算为 #P-完全问题，表明指数壁垒在最坏情况下不可避免。
条件组合的粗粒度二元划分具有保守性：条件组合记账器将样本输出硬性划分为“好”与“坏”两类互斥集合，容易在“好事件”内部产生过度悲观的主导估计；在多轮（Multi-epoch）DP-SGD 中，均值几何间距随轮次递增，导致后验风险出现阶跃性跳跃。
未来改进方向：探索基于连续划分更细粒度的条件组合机制；研究如何将 Feldman & Shenfeld (2026) 提出的 PLD 变换框架推广至相关梯度矩阵空间，寻求在全参数区间统一步间相关的理想解析解。

评分¶

新颖性: ⭐⭐⭐⭐⭐ [首次攻克带步间相关噪声的随机分配矩阵机制确定性解析记账，提出循环带状 DP 与条件组合变分界两大理论创新]
实验充分度: ⭐⭐⭐⭐⭐ [覆盖 6 种主流矩阵机制、单/多 epoch、宽范围 $\varepsilon$ 与 $\delta$、全参数运行耗时基准以及 CIFAR-10 下游效用实验]
写作质量: ⭐⭐⭐⭐⭐ [数学推导严密厚实，核心动机直指蒙特卡洛经验采样的本质痛点，算法脉络与复杂度剖析极为清晰]
价值: ⭐⭐⭐⭐⭐ [彻底打通了矩阵机制在工业级隐私深度学习中落地的最后一道算力与合规壁垒，为后续理论研究设立了标杆]

消融配置项	变化维度 / 取值	记账指标影响	计算耗时 / 资源开销	核心机理与结论
Gram 矩阵截断 \(p\) (BSR, \(p=64\))	\(p=64\) (无截断)	\(R_\alpha = 0.428\) (基准)	耗时相对值 \(1.0\times\)	精确全宽求和，无额外加项
Gram 矩阵截断 \(p\) (BSR, \(p=64\))	截断至 \(p=4\)	\(R_\alpha = 0.435\) (误差 <1.6%)	耗时下降至 \(0.08\times\)	非对角快速衰减，\(\tau \alpha / 2\sigma^2\) 代价极小
Gram 矩阵截断 \(p\) (BSR, \(p=64\))	截断至 \(p=1\)	\(R_\alpha = 0.492\) (误差 ~15%)	耗时下降至 \(0.01\times\)	截断过于激进，残差界开始变松
条件组合变分族	Option 1 (\(T=\infty\) 几何均值)	后验上界 \(\bar{\lambda}_b = 0.41\)	基础耗时	仅利用均匀分布消除 KL 项
条件组合变分族	Option 2 (最大化均值)	后验上界 \(\bar{\lambda}_b = 0.41\)	基础耗时 \(+15\%\)	距离优化对均值偏移无明显收益
条件组合变分族	Option 3 (\(T\) 距离变分 Softmax)	后验上界 \(\bar{\lambda}_b = \mathbf{0.32}\)	基础耗时 \(+5\%\)	成功压低高维方差，显著收紧小 \(\sigma\) 区间
邻近方向比较	“添加”界 vs “移除”界	“添加”界始终严格低于“移除”界	“添加”界解析计算 \(\mathcal{O}(1)\)	证实“移除”方向全局主导，动态规划绝无浪费

评估配置 (\(N, k, p, \delta=10^{-5}\))	隐私预算 \(\varepsilon\)	Rényi 记账器 \(\sigma\)	条件组合记账器 \(\sigma\)	蒙特卡洛参考 \(\sigma\)	采样免除/确定性状态
DP-SGD (\(N=1000, k=1\))	\(\varepsilon = 0.5\) (高隐私)	14.82	9.12	8.85 (经验采样)	确定性紧致上界 (小 \(\varepsilon\) 优势明显)
DP-SGD (\(N=1000, k=1\))	\(\varepsilon = 2.0\) (中隐私)	3.65	3.78	3.61 (经验采样)	确定性上界紧密贴合经验值
DP-SGD (\(N=1000, k=1\))	\(\varepsilon = 8.0\) (低隐私)	1.21	1.34	1.20 (经验采样)	Rényi 与 MC 几乎完全重合
BSR (\(N=1000, k=10, p=4\))	\(\varepsilon = 0.5\) (高隐私)	16.40	11.05	10.62 (经验采样)	成功抑制多轮步间相关性松弛
BSR (\(N=1000, k=10, p=4\))	\(\varepsilon = 2.0\) (中隐私)	4.85	4.98	4.79 (经验采样)	保持确定性理论保证
BSR (\(N=1000, k=10, p=4\))	\(\varepsilon = 8.0\) (低隐私)	1.62	1.80	1.61 (经验采样)	完美重合大偏差渐近线
CIFAR-10 准确率 (BSR, \(\varepsilon=4\))	\(\varepsilon = 4.0\) (测试准确率)	68.7% ± 0.4	68.3% ± 0.5	68.9% ± 0.4 (非严格)	捕获相关噪声相比 DP-SGD 的显著收益