One-Shot Private Confidence Regions via Resampling¶

会议: NeurIPS 2026
arXiv: 2610.08460
OpenReview: https://openreview.net/forum?id=ZueKmUuWjT
领域: 其他
关键词: 差分隐私, 高斯差分隐私, 重抽样, 置信区域, 平滑敏感度

一句话总结¶

针对传统差分隐私重抽样方法因多重估计量加噪导致隐私损失随重抽样次数呈 $\sqrt{B}$ 累积的难题，本文提出“一次性”加噪机制，仅对最终的分位数半径施加高斯扰动，实现隐私损失对重抽样次数仅呈对数级依赖甚至完全独立。

研究背景与动机¶

参数估计与不确定性量化（Uncertainty Quantification）是统计推断的核心支柱。在参数渐近正态分布未知、解析方差公式难以推导或经典非参数 Bootstrap 失效的场景下，无放回子抽样（Subsampling）与 $m$-out-of-$n$ 有放回重抽样成为了构建置信区间与置信区域的标准非参数工具。通过在规模为 $m \ll n$ 的辅助子样本上反复计算统计量并经验估计枢轴量（Pivot）的分位数，重抽样方法能够绕过复杂的渐近理论假定，为目标参数提供渐近有效的覆盖保证。

然而，当这些推断程序部署于涉及敏感个体数据的差分隐私（Differential Privacy, DP）场景时，面临着根本性的隐私与计算瓶颈。为了控制重抽样引起的经验估计误差，蒙特卡洛重抽样次数通常需要达到 $B \approx 10^3 \sim 10^4$。既有私有重抽样框架（如 Bag of Little Bootstraps 或各类私有子抽样机制）通常选择对每一个重抽样样本上计算的中间统计量分别实施隐私化加噪，随后通过高级组合定理或阈值搜索（AboveThreshold）汇聚结果。这种逐次加噪策略使得总隐私损失不可避免地随重抽样次数 $B$ 呈 $\sqrt{B}$ 形式剧烈累积；或者为了强行控制敏感度而引入两阶段候选网格搜索，使计算开销激增 $O(\sqrt{n})$ 倍。

这一失效的核心矛盾在于：下游推断任务实际上仅需要一到两个分位数来确定最终置信区间的端点或半径，而现有方案却耗费大量隐私预算去逐个披露全部 $B$ 个中间经验分布点。核心 idea：抛弃对每个中间重抽样统计量逐一加噪的传统思路，转向仅对最终经验重抽样分位数实施一次性高斯加噪；通过严密界定有放回抽样下的最大重复采样重数与光滑敏感度上界，将隐私开销对重抽样次数的依赖彻底降为对数级 $\mathcal{O}(\log(Bn))$ 甚至常数级。

方法详解¶

整体框架¶

本文构建了一套在有限样本高斯差分隐私（GDP）保障下的一次性私有置信区域推断框架，包含两套核心算法：面向全局敏感度受限统计量的 CR-GS（Algorithm 2）以及面向局部敏感度光滑可界定统计量的 CR-SS（Algorithm 4）。算法的整体流程自上而下分为四个主要阶段：子抽样索引生成与重数控制、全样本与重抽样点估计、经验缩放分位数构造、以及中心估计与分位数半径的一次性扰动发布。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：数据集 D、目标统计量 θ、子抽样规模 m、重采样次数 B"] --> B["阶段 1：重数受限子抽样生成<br/>无放回抽样 κ⋆=1 / 有放回抽样通过 MCS 检验"]
    B --> C["阶段 2：全样本与重采样点估计<br/>全样本 θ^n 与重采样估计 {θi*} 仅保留在内存内部"]
    C --> D["阶段 3：经验缩放分位数构造<br/>计算枢轴距离并在置信水平 1-α 下求分位数 Qn,m"]
    D --> E["阶段 4：一次性私有发布<br/>中心加噪 θ~n 与分位数半径截断加噪 Q~n,m"]
    E --> F["输出：最终差分隐私置信区域 Cn,α"]

关键设计¶

1. 重数受限子抽样生成：控制有放回采样下的最大重合频次 在无放回子抽样（WOR）模式下，任意被修改的数据点在单个子样本中最多出现一次，两相邻数据集在任意子抽样上的对称差至多为 1；但当采用有放回的 $m$-out-of-$n$ 重抽样（WR）时，单个数据点可能在某一子样本中被重复抽中多次，导致局部敏感度被成倍放大。为解决该问题，论文提出了“重数受限抽样”（MCS, Algorithm 1）：首先利用 Lambert-$W$ 函数显式推导在所有 $B$ 个子样本中任意样本点出现频次的上界 $\kappa_\star$： $$\kappa_\star(n,m,B,\rho) := \min\left\{m, \left\lceil \log\frac{Bn}{\rho} \cdot \left(W_0\left(\frac{n}{me}\log\frac{Bn}{\rho}\right)\right)^{-1} \right\rceil - 1\right\}$$ 当且仅当所有 $B$ 个重抽样中各数据点的最大频次均不超过 $\kappa_\star$ 时才接受该批索引，否则直接拒绝并报错 $\bot$。该过滤机制以至多 $\rho = o_n(1)$ 的概率触发失败，从而将最坏情况下的敏感度严格锁死在 $\kappa_\star \Delta_m$ 级别，且理论证明 $\kappa_\star = \mathcal{O}(\log(Bn/\rho))$，在隐私预算膨胀项中仅引入对数阶代价。

2. 经验缩放分位数构造：基于枢轴距离的 1-Lipschitz 分位数压缩 在获取全样本估计量 $\widehat{\theta}_n = \theta(D)$ 与各个重抽样估计量 $\theta_i^\star = \theta(D[S_i])$ 后，既有方法往往尝试直接发布各个 $\theta_i^\star$ 的经验测度。本文转而在算法内部私密计算各重抽样估计量相对于全样本中心估计的欧氏距离 $\|\theta_i^\star - \widehat{\theta}_n\|_2$，并乘上重抽样尺度因子 $\tau_m$： $$Q_{n,m} = \tau_m \cdot \text{Quantile}_{1-\alpha}\left(\|\theta_1^\star - \widehat{\theta}_n\|_2, \ldots, \|\theta_B^\star - \widehat{\theta}_n\|_2\right)$$ 由于一维顺序统计量与分位数算子对于输入数组中任意单个分量的最大扰动具备内在的 $1$-Lipschitz 连续性，修改数据集中的任意一个原始记录，使得任何单个子样本距离 $\|\theta_i^\star - \widehat{\theta}_n\|_2$ 的改变量绝不超过 $\kappa_\star \Delta_m + \Delta_n$。因此，聚合后的经验分位数 $Q_{n,m}$ 的全局敏感度天然被严格束缚在 $\tau_m (\kappa_\star \Delta_m + \Delta_n)$ 之内，无需对中间的 $B$ 个统计量分别施加独立隐私预算。

3. 一次性私有发布：分位数半径与中心点的 GDP 高斯扰动 基于分位数全局敏感度上界，算法仅在发布阶段执行一次性独立加噪。全样本点估计量 $\widehat{\theta}_n$ 与分位数半径 $Q_{n,m}$ 分别加入独立高斯噪声： $$\widetilde{\theta}_n = \widehat{\theta}_n + \nu_n Z_2, \quad \widetilde{Q}_{n,m} = \max\left\{Q_{n,m} + \sigma_m Z_1, 0\right\}$$ 其中 $Z_1 \sim \mathcal{N}(0, 1)$，$Z_2 \sim \mathcal{N}(0, \mathbf{I}_d)$，噪声尺度严格校准为 $\nu_n = \frac{\sqrt{2}\Delta_n}{\mu}$，$\sigma_m = \frac{\sqrt{2}\tau_m(\kappa_\star\Delta_m + \Delta_n)}{\mu}$。最终发布的置信区域为以 $\widetilde{\theta}_n$ 为球心、以 $\tau_n^{-1}\widetilde{Q}_{n,m}$ 为半径的欧氏球 $\mathcal{C}_{n,\alpha} = \{u \in \mathbb{R}^d : \|u - \widetilde{\theta}_n\|_2 < \tau_n^{-1}\widetilde{Q}_{n,m}\}$。在 GDP 组合定理下，中心估计与半径估计各自消耗 $\mu/\sqrt{2}$ 的隐私预算，整体严格保证 $\mu$-GDP，且有效覆盖率满足 $\mathbb{P}(\theta \in \mathcal{C}_{n,\alpha}) = 1 - \alpha + o_n(1)$。

4. 平滑敏感度与 PTR 扩展：覆盖非均值型与退化 U 统计量 对于样本分位数（中位数）及退化 $U$ 统计量等全局敏感度过大或无界的非均值型泛函，论文进一步拓展出了 CR-SS 架构，将提出-测试-释放（Propose-Test-Release, PTR）思想引入 GDP。算法利用对数平滑敏感度在邻近数据集之间的 Lipschitz 性质，设计了 PTR-GDP 机制（Algorithm 3），并通过乘积系数将单个子样本平滑敏感度缩放组合为经验分位数的综合平滑敏感度上界： $$s(D) := \max_{i \in [B]} \text{SS}_\beta(\theta, D[S_i]) \cdot \frac{e^{\kappa_\star \beta} - 1}{e^\beta - 1} + \text{SS}_\beta(\theta, D)$$ 在选定平滑参数 $\beta = \frac{1}{2\kappa_\star}\min\{1, \frac{\mu}{4\sqrt{\log(B/(\delta\rho))}}\}$ 条件下，证明了 $\tau_m s(D)$ 恰为经验分位数的 $\kappa_\star\beta$-平滑上界，从而在 $(\mu, \delta)$-GDP 保障下成功推导出第一阶退化 $U$ 统计量与总体中位数的有效渐近置信区间。

损失函数 / 训练策略¶

本方法属于纯推断阶段的无参数统计推断与非参数扰动机制，不涉及模型反向传播或经验损失优化。在实现策略上，推荐子抽样规模取 $m \approx \lceil n / \log n \rceil$（或 $m \approx n^\eta, \eta \in [0.7, 0.8]$），重采样数取 $B = 500 \sim 1000$，拒绝采样失效率取 $\rho = 1/n$；在 GDP 与 $(\varepsilon, \delta)$-DP 转换中直接复用对偶高斯转化关系式 $\delta_\mu(\varepsilon) = \Phi(-\frac{\varepsilon}{\mu} + \frac{\mu}{2}) - e^\varepsilon \Phi(-\frac{\varepsilon}{\mu} - \frac{\mu}{2})$。

实验关键数据¶

主实验¶

论文在 Bernoulli 均值、总体中位数以及一阶退化 $U$ 统计量（核函数 $h(x, y) = xy$，数据服从 $\text{Unif}[-1/2, 1/2]$）三个典型任务上进行了全面评测。基线包括基于小 Bootstrap 袋（BLB）的 BLBQuant（Chadha et al., 2024）与基于 GDP 渐近重抽样的 Dette-Graw（Dette & Graw, 2025）。名义覆盖率设定为 $1 - \alpha = 0.90$，总隐私预算固定为 $\mu = 8$，独立测试试验 400 次。

下面展示样本量 $n \in \{2000, 10000, 50000\}$ 下有界均值（Bernoulli(0.05)）与第一阶退化 $U$ 统计量的主对比结果：

数据集 / 统计量	样本量 $n$	算法配置	经验覆盖率 (cov)	区间平均宽度 ($10^3 \times \text{len}$)	运行耗时 (ms)
Bernoulli(0.05) 均值	2000	BLBQuant	0.93	16.39	32.21
Bernoulli(0.05) 均值	2000	Dette-Graw	0.66	11.39	1.35
Bernoulli(0.05) 均值	2000	CR-GS (WR, 本文)	0.90	15.92	9.91
Bernoulli(0.05) 均值	2000	CR-GS (WOR, 本文)	0.90	14.90	5.23
Bernoulli(0.05) 均值	10000	BLBQuant	0.89	7.18	145.11
Bernoulli(0.05) 均值	10000	Dette-Graw	0.82	6.63	1.40
Bernoulli(0.05) 均值	10000	CR-GS (WR, 本文)	0.89	7.12	31.47
Bernoulli(0.05) 均值	10000	CR-GS (WOR, 本文)	0.88	6.76	15.31
Bernoulli(0.05) 均值	50000	BLBQuant	0.91	3.18	812.03
Bernoulli(0.05) 均值	50000	Dette-Graw	0.89	3.12	1.81
Bernoulli(0.05) 均值	50000	CR-GS (WR, 本文)	0.91	3.18	156.78
Bernoulli(0.05) 均值	50000	CR-GS (WOR, 本文)	0.89	3.04	73.74
退化 $U$ 统计量 ($h=xy$)	2000	BLBQuant	1.00	1.124 ($10^4 \times$)	21.77
退化 $U$ 统计量 ($h=xy$)	2000	Dette-Graw	1.00	0.737 ($10^4 \times$)	2.76
退化 $U$ 统计量 ($h=xy$)	2000	CR-SS (WR, 本文)	0.90	0.408 ($10^4 \times$)	22.43
退化 $U$ 统计量 ($h=xy$)	2000	CR-SS (WOR, 本文)	0.81	0.148 ($10^4 \times$)	13.65
退化 $U$ 统计量 ($h=xy$)	10000	BLBQuant	1.00	0.263 ($10^4 \times$)	134.81
退化 $U$ 统计量 ($h=xy$)	10000	Dette-Graw	1.00	0.123 ($10^4 \times$)	6.63
退化 $U$ 统计量 ($h=xy$)	10000	CR-SS (WR, 本文)	0.86	0.056 ($10^4 \times$)	46.92
退化 $U$ 统计量 ($h=xy$)	10000	CR-SS (WOR, 本文)	0.88	0.029 ($10^4 \times$)	25.52
退化 $U$ 统计量 ($h=xy$)	50000	BLBQuant	1.00	0.059 ($10^4 \times$)	656.71
退化 $U$ 统计量 ($h=xy$)	50000	Dette-Graw	1.00	0.021 ($10^4 \times$)	32.79
退化 $U$ 统计量 ($h=xy$)	50000	CR-SS (WR, 本文)	0.84	0.007 ($10^4 \times$)	155.00
退化 $U$ 统计量 ($h=xy$)	50000	CR-SS (WOR, 本文)	0.92	0.006 ($10^4 \times$)	108.17

消融实验¶

论文通过对比有放回抽样（WR）与无放回抽样（WOR）以及不同重采样机制对理论误差与计算开销的影响，进行了深入的机制分析与消融对比：

抽样与隐私架构机制	理论方差额外隐私惩罚项	敏感度参数依赖	对重采样数 $B$ 的敏感度依赖	计算额外开销因子	核心适用与边界限制
CR-GS/SS (WOR, 无放回)	$\frac{4 \ell^2}{mn \mu^2}$	$\kappa_\star = 1$	0（完全独立）	$1 \times$	要求 $m \ll n$ 且可随机划分；隐私代价最低
CR-GS/SS (WR, 有放回)	$\frac{4 \kappa_\star^2 \ell^2}{mn \mu^2}$	$\kappa_\star = \mathcal{O}(\log(Bn/\rho))$	对数依赖 $\mathcal{O}(\log^2(Bn))$	$1 \times$（仅增微小重数过滤）	适用更广泛的 $m$-out-of-$n$ Bootstrap 理论生态
BLBQuant (Chadha et al.)	$\widetilde{\mathcal{O}}(\frac{\sqrt{d}}{\varepsilon n^{3/2}} + \frac{d}{\varepsilon^2 n^2})$	逐块加噪	依赖分块数与网格精度	$\mathcal{O}(\sqrt{n})$ 网格遍历	依赖候选区间离散化搜索，计算代价随 $n$ 暴增
Dette-Graw (2025)	$\frac{B m d}{n^3 \mu^2}$	线性累积	线性依赖 $B$	$1 \times$	仅具渐近有效性，小样本下严重欠覆盖

关键发现¶

重采样数自由扩展：由于加噪仅发生于最终经验分位数上，CR-GS/SS 即使将蒙特卡洛重采样数 $B$ 从 500 扩展至上万次，隐私代价也不发生恶化，彻底摆脱了既有差分隐私重抽样方法因多重机制复合导致的方差爆炸。
退化 U 统计量自适应性极佳：对于渐近非正态且传统 Bootstrap 失效的一阶退化 $U$ 统计量，CR-SS 自然适配了 $\tau_n = n$ 的超快收敛速率，给出的置信区间宽度仅为 BLBQuant 的 $1/10 \sim 1/3$，且紧致地贴合 0.90 的名义覆盖率，避免了基线方法严重的过覆盖（100% 覆盖但区间过宽冗余）。
计算吞吐优势显著：相比 BLBQuant 随着样本量 $n$ 增加所需庞大的候选区间网格搜索耗时（$n=50000$ 时单次耗时达 $42 \sim 45$ 秒），CR-GS/SS 耗时控制在数百毫秒内，提速超 200 倍。

亮点与洞察¶

一次性分位数扰动机制：打破了对每个子样本估计量分别进行差分隐私化并用高级组合定理聚合的惯性思维，证明了分位数算子的 1-Lipschitz 特性可以直接传递局部敏感度控制，以极具启发性的极简设计规避了复合定理带来的隐私预算流失。
重数条件采样的巧妙界定：将有放回抽样中的重复采样瓶颈精确抽象为极值占优问题，借助 Lambert-$W$ 函数给出确凿的紧致尾界，为有放回抽样在差分隐私领域的严谨应用奠定了基础。
理论体系无缝连接 GDP：在假设检验 trade-off 函数视阈下构建理论保证，同时提出了基于对数平滑敏感度的 PTR-GDP 框架，使非正态与非均值型复杂估计量在平滑敏感度范式下获得了严格且非渐近的隐私证明。

局限与展望¶

极端尾部分位数估计受限：若目标是估计置信水平极高（如 $\alpha = 0.001$）的极端尾部置信界，经验重抽样分位数附近的概率密度可能接近于零，导致次序统计量间距过大，平滑敏感度急剧膨胀，进而破坏私有区间的有效覆盖。
重抽样子样本规模依赖先验调优：参数 $m$ 的选取（通常经验推荐 $m \approx n/\log n$ 或 $n^{0.75}$）直接影响渐近偏差与分位数方差的折中，缺乏一种完全差分私有的自适应数据驱动调参算法。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 颠覆了既有逐次加噪私有重采样范式，提出一次性分位数扰动方案，理论优美。
实验充分度: ⭐⭐⭐⭐⭐ 涵盖有界均值、总体中位数与退化 U 统计量，严密验证了覆盖率、区间宽度与计算耗时。
写作质量: ⭐⭐⭐⭐⭐ 理论推导严密自洽，从全局敏感度到平滑敏感度层层递进，结构清晰。
价值: ⭐⭐⭐⭐⭐ 为差分隐私机器学习与统计推断领域提供了一个通用的高效率不确定性量化工具箱。

抽样与隐私架构机制	理论方差额外隐私惩罚项	敏感度参数依赖	对重采样数 \(B\) 的敏感度依赖	计算额外开销因子	核心适用与边界限制
CR-GS/SS (WOR, 无放回)	\(\frac{4 \ell^2}{mn \mu^2}\)	\(\kappa_\star = 1\)	0（完全独立）	\(1 \times\)	要求 \(m \ll n\) 且可随机划分；隐私代价最低
CR-GS/SS (WR, 有放回)	\(\frac{4 \kappa_\star^2 \ell^2}{mn \mu^2}\)	\(\kappa_\star = \mathcal{O}(\log(Bn/\rho))\)	对数依赖 \(\mathcal{O}(\log^2(Bn))\)	\(1 \times\)（仅增微小重数过滤）	适用更广泛的 \(m\)-out-of-\(n\) Bootstrap 理论生态
BLBQuant (Chadha et al.)	\(\widetilde{\mathcal{O}}(\frac{\sqrt{d}}{\varepsilon n^{3/2}} + \frac{d}{\varepsilon^2 n^2})\)	逐块加噪	依赖分块数与网格精度	\(\mathcal{O}(\sqrt{n})\) 网格遍历	依赖候选区间离散化搜索，计算代价随 \(n\) 暴增
Dette-Graw (2025)	\(\frac{B m d}{n^3 \mu^2}\)	线性累积	线性依赖 \(B\)	\(1 \times\)	仅具渐近有效性，小样本下严重欠覆盖