Privately Estimating Monotone Statistics in Polynomial Time¶

会议: NeurIPS 2026
arXiv: 2605.27912
OpenReview: https://openreview.net/forum?id=K3GOUY36bZ
领域: others
关键词: 差分隐私、单调统计量、分位数交错、子样本聚合、多项式时间算法、查询复杂度下界

一句话总结¶

本文研究单调统计量的黑盒差分隐私估计，通过建立子样本经验分位数的邻近交错性质，提出了时间复杂度为 $e^{O(t)}\mathrm{poly}(k_{\varepsilon,\delta})$、样本量降低 $t$ 倍的实用多项式时间算法，并给出了匹配的查询复杂度指数下界。

研究背景与动机¶

从非隐私统计估计器中黑盒生成差分隐私（Differentially Private, DP）算法，是隐私计算与可信统计推断领域长期追求的核心目标。虽然针对均值估计、主成分分析（PCA）和线性回归等具体统计问题已存在众多接近最优精确度的定制化专用 DP 算法，但这些方法往往依赖繁复的理论推导与敏感度界定。通用的黑盒私有化范式无需获悉目标函数的内部结构，在统计软件包与工业部署中具备极高的通用性与工程价值。

长期以来，黑盒私有化的工业标准是经典的“子样本聚合”（Subsample-and-Aggregate, S&A）范式：将样本量为 $n$ 的数据集切分为 $\tau \gtrsim \frac{1}{\varepsilon}\log\frac{1}{\delta}$ 个互斥数据块，在每个数据块上独立运行非私有估计器，随后采用鲁棒中心估计算法进行私有聚合。该方法计算极其高效，仅需查询基估计器 $\tau$ 次，然而其样本开销异常严苛——为保证每个数据块上的估计具备统计有效性，块大小必须不低于非隐私基准样本量 $N$，导致整体样本复杂度承受 $N \cdot \frac{1}{\varepsilon}\log\frac{1}{\delta}$ 的乘性放大，在数据受限的高维统计分析中极易失效。近期理论工作虽证明任意黑盒函数均能达到仅需加性样本膨胀 $n \approx N + \frac{1}{\varepsilon}\log\frac{1}{\delta}$ 的极限，但算法的时间与查询复杂度飙升至 $n^{\Theta(\frac{1}{\varepsilon}\log\frac{1}{\delta})}$ 的全数据集子集穷举指数级，无法实际执行。

本文直面这一根本瓶颈，针对在实际统计任务中极其普遍的“单调统计量”（Monotone Statistics，即随新样本加入其取值单调不减的统计量，如经验损失、协方差特征值及极值统计）开展攻关。既有基于单调性的私有化方法同样受限于超多项式甚至指数级子集穷举运行时间，因而理论界始终未阐明：在多项式运行时间内，能否突破子样本聚合的乘性样本瓶颈？核心 idea：利用概率为 $p$ 的独立子样本经验分位数在相邻数据集上的严格交错性质，将私有统计量估计规约为鲁棒分位数聚合问题，在节省 $t$ 倍样本复杂度的同时仅付出 $e^{O(t)}$ 的可调计算代价，并证明该查询复杂度下界本质紧致。

方法详解¶

整体框架¶

本文构建了针对单调统计量的高效黑盒差分隐私估计体系。对于任意满足添加样本不减性质的函数 $f$，算法首先通过以采样率 $p$ 进行 $T$ 次独立伯努利抽样获取子集分布 $f(\mathcal{S}_p(Z))$；核心支撑构件 Quantile-Finder 计算出一组严格保持几何步长间距的经验分位数，并证明相邻数据集在该分位数序列上满足“交错跳跃”（Interleaving）条件。在此基础上，本文分别设计了适配有界范围的分位数中位数机制（Median-of-Quantiles）与适配无界范围的分位数均值机制（Average-of-Quantiles），成功输出兼具高概率集中性与隐私保障的估计结果。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入数据 Z 与单调黑盒函数 f"] --> B["子样本生成与经验分布采集<br/>独立伯努利子抽样 S_t ~ S_p(Z)"]
    B --> C["分位数探测器<br/>构建几何步长经验分位数序列"]
    C --> D{"输出目标与值域类型"}
    D -->|有界离散/紧区间| E["分位数中位数机制<br/>指数机制对齐目标中位数"]
    D -->|无界连续真实值| F["分位数均值机制<br/>稳定性截断均值 + 截断拉普拉斯噪声"]
    E --> G["输出差分隐私统计估计值"]
    F --> G

关键设计¶

1. 分位数探测器：利用子样本经验分位数交错性替代全量穷举搜索 传统针对单调函数的私有评估方法需要在所有子集构成的超图格点上进行穷举，以寻找确定性的下界与上界交错序列，导致指数级时间复杂度。本文发现，若对数据集每个样本以概率 $p \in (0, 1/4)$ 独立保留生成子样本 $S \sim \mathcal{S}_p(Z)$，则单调性使得相邻数据集 $Z, Z'$ 诱导的累积分布函数 $F, F'$ 满足全局比值控制：$(1-p)F'(\ell) \le F(\ell) \le \frac{1}{1-p}F'(\ell)$。结合 Dvoretzky-Kiefer-Wolfowitz (DKW) 经验过程集中不等式，以步长比值 $\frac{1+\gamma}{1-p}$ 选取的经验分位数序列 $q(t) = Q_{\widehat{\mathcal{D}}}((\frac{1+\gamma}{1-p})^t \eta)$ 能够以至少 $1-\delta$ 的概率在相邻数据集之间保持二阶交错： $$q'(t) \le q(t+1) \le q'(t+2), \quad \forall t \in [\tau - 2].$$ 该性质不仅消除了遍历高维子集格点的必要性，而且所需抽样总数仅为 $T = O(e^{4p\tau}p^{-2}\log\frac{1}{\delta})$，使分位数提取直接收敛于可控的多项式时间。

2. 分位数中位数机制：基于交错敏感度约束的指数机制输出 针对输出值域受限在离散集合 $[\kappa]$ 的单调函数，本文提出了 Median-of-Quantiles 机制。算法设置分位数序列长度 $\tau = \frac{4}{\varepsilon}\log\frac{\kappa}{\beta}$，定义每个候选输出值 $y \in [\kappa]$ 的得分为其在分位数列表中的经验排名偏离中心中位数阶数的负绝对值：$\mathrm{score}(y; Z) = -|\mathrm{rank}(y; \bar{q}) - \tau/2|$。由于分位数序列 $q(t)$ 与 $q'(t)$ 具备强交错关系，任意单个输入样本替换所引起的经验排名偏移被严格约束在 $\pm 1$ 之内，从而使打分函数的局部敏感度 $\Delta \le 1$。通过标准的指数机制对候选结果进行加权采样，算法不仅在无需强加目标函数平滑性假设的前提下严格满足 $(\varepsilon, \delta)$-DP，而且以至少 $1-\beta$ 的高概率输出落在区间 $[q(\tau/4), q(3\tau/4)] \subseteq [\min f(S_i), \max f(S_i)]$ 内的真实中位数估计。

3. 分位数均值机制：受控直径检验与截断拉普拉斯噪声加噪 针对值域无界的实值单调函数，无法直接采用指数机制划分候选空间。Average-of-Quantiles 机制通过显式控制分位数序列的紧致核心直径来实现。算法首先寻找最小下标 $t^* = \min \{t \le \tau/2 \mid q(\tau-t) - q(t) \le \alpha\}$；通过对 $t^*$ 施加截断拉普拉斯噪声 $\mathrm{TLap}(\frac{1}{\varepsilon}, \frac{\tau}{8})$ 验证该核心直径是否稳定。在验证通过后，计算核心窗口内的分位数经验平均值： $$y = \frac{4}{\tau}\sum_{i \in [\tau/4]} q(t^* + i),$$ 并注入尺度匹配的截断拉普拉斯噪声 $\widehat{y} \sim y + \mathrm{TLap}(\frac{16\alpha}{\tau\varepsilon}, \frac{16\alpha\log(1/\delta)}{\tau\varepsilon})$。利用滑动窗口在交错分位数序列上的对齐抵消特性，证明了均值统计量 $y$ 在相邻数据集上的敏感度严格不超过 $\frac{16\alpha}{\tau}$，在保留无界函数估计能力的同时实现了精准的加性误差界。

损失函数 / 训练策略¶

本方法属于黑盒元算法（Meta-algorithm），无需参数梯度更新或内部迭代训练。算法的超参数调节遵循样本量与计算时间的对偶折中： - 子采样概率与权衡参数 $t$：选取子采样概率 $p = \frac{t}{k_{\varepsilon,\delta}}$（其中 $k_{\varepsilon,\delta} = \frac{1}{\varepsilon}\log\frac{1}{\delta}$），在样本开销与运行时间之间形成连续插值谱。当 $t = \log(k_{\varepsilon,\delta})$ 时，在计算时间为 $\mathrm{poly}(k_{\varepsilon,\delta})$ 的严格多项式时间内，样本量相较于 S&A 显著节省 $\log(k_{\varepsilon,\delta})$ 倍；当允许运行时间放宽至准多项式或亚指数时，可节省高达 $O(k_{\varepsilon,\delta})$ 倍的样本开销。 - 噪声截断机制：截断拉普拉斯噪声采用对称有界支撑分布 $\mathrm{TLap}(b, \tau_0)$，保证在以 $1-\delta$ 概率满足差分隐私的同时，截断界绝对排除了重尾拉普拉斯噪声引入灾难性极值的风险。

实验关键数据¶

主实验¶

论文对理论渐近阶进行了严格推导，并在协方差矩阵特征值估计与高维线性回归单参数推断任务中建立了精确收敛界。

估计任务 / 统计量	评价指标	本文算法 (Ours)	传统子样本聚合 (S&A)	穷举下局部算法 [36]
通用单调统计量估计	样本复杂度 $n$	$O\big(\frac{N \log(1/\delta)}{t\varepsilon}\big)$	$O\big(\frac{N \log(1/\delta)}{\varepsilon}\big)$	$N + O\big(\frac{\log(1/\delta)}{\varepsilon}\big)$
通用单调统计量估计	运行时间/查询数	$e^{O(t)} \cdot \mathrm{poly}\big(\frac{\log(1/\delta)}{\varepsilon}\big)$	$\mathrm{poly}\big(\frac{\log(1/\delta)}{\varepsilon}\big)$	$n^{\Theta(\frac{1}{\varepsilon}\log\frac{1}{\delta})}$
协方差第 $i$ 特征值 $\lambda_i(\Sigma)$	相对误差区间	$[1-\alpha, 1+\alpha]$	$[1-\alpha, 1+\alpha]$	$[1-\alpha, 1+\alpha]$
特征值估计样本需求	样本量 $n$	$\Omega\big(\frac{d\log(1/\delta)}{\alpha^2 t\varepsilon}\big)$	$\Omega\big(\frac{d\log(1/\delta)}{\alpha^2 \varepsilon}\big)$	$\Omega\big(\frac{d}{\alpha^2} + \frac{\log(1/\delta)}{\varepsilon}\big)$
线性回归单参数测试 $\theta_1$	样本量 $n$	$\Omega\big(\frac{d\log(1/\delta)}{t\varepsilon} + \mathrm{poly}(\cdot)\big)$	$\Omega\big(\frac{d\log(1/\delta)}{\varepsilon}\big)$	不适用 / 超多项式时间

消融实验¶

通过改变折中调谐参数 $t$ 的取值配置，算法展现出在样本复杂度与运行时间之间的清晰相变特性（如下表所示）：

配置设定 ($t$)	样本复杂度阶数 $n$	查询与运行时间复杂度	说明
$t = 1$ (等价 S&A 基线)	$N \cdot k_{\varepsilon,\delta}$	$O(k_{\varepsilon,\delta})$	对应极小计算代价，样本需求最大
$t = \log(k_{\varepsilon,\delta})$ (多项式效率点)	$N \cdot \frac{k_{\varepsilon,\delta}}{\log(k_{\varepsilon,\delta})}$	$\mathrm{poly}(k_{\varepsilon,\delta})$	保证严格多项式时间下的最优样本削减
$t = \sqrt{k_{\varepsilon,\delta}}$ (中等平衡点)	$N \cdot \frac{k_{\varepsilon,\delta}}{\sqrt{k_{\varepsilon,\delta}}}$	$\exp(O(\sqrt{k_{\varepsilon,\delta}}))$	亚指数级计算时间，换取显著样本优化
$t = k_{\varepsilon,\delta}$ (加性样本极限)	$N + k_{\varepsilon,\delta}$	$(1/\delta)^{1/\varepsilon} \cdot \mathrm{poly}(k_{\varepsilon,\delta})$	达到最少样本需求，时间等同于穷举阶

关键发现¶

样本-时间折中的普适边界：本文证明了单调函数黑盒私有化存在连续的连续折中曲线——节省 $t$ 倍的样本复杂度必须以时间开销上浮 $e^{O(t)}$ 为代价，消除了以往算法非黑即白（极慢的加性膨胀 vs 极耗数据的乘性膨胀）的割裂局面。
信息论查询复杂度紧致性：定理 6.2 证明了对于任何能够从 $N/p$ 个样本中恢复单调统计量的私有机制，其查询复杂度下界必为 $\exp(\Omega(p\tau))$。这表明本文构造的基于子样本分位数的算法在渐近阶上是信息论最优的，无法在不牺牲隐私或样本量的前提下进一步压低指数底数。
高维单参数推断的维度解耦：在高维线性回归与 M-估计任务中，利用经验损失在子抽样下的典型有界差分性质，算法检验单参数显著性所需的样本量主导项为 $\frac{d\log(1/\delta)}{t\varepsilon}$，避免了将整套全参数私有化机制带来的维度二次方开销。

亮点与洞察¶

从离散格点遍历到概率分位数交错的视角转换：以往单调函数私有化工作依赖于确定性子集格点枚举，计算极其笨重。本文创新性地引入独立伯努利抽样诱导的经验分布分位数，利用统计极限不等式将格点包含关系转化为概率上的分位数交错，设计极其优雅且易于实现。
弱精度保证下的刚性下界技术：在下界证明中，本文将性质测试领域的适应性-非适应性转换技术（Proposition 6.6）与群隐私破坏机制相结合，在仅要求算法输出结果落在常量误差范围内的极弱假设下，严格导出了指数级查询复杂度下界，理论穿透力极强。
即插即用的单调性校正：针对经验损失最小化等不可导或仅有近似数值求解器的场景，论文设计了增加与数据集大小成比例微扰的简单重构技巧 $f(Z) = L_{\mathrm{approx}}(Z) + \gamma |Z|$，在无需修改基础求解器的情况下自动恢复严格单调性并维持理论精度。

局限与展望¶

单调性假设的适用边界：核心理论体系强依赖于单调函数性质，对于目标函数缺乏单调结构的通用统计量（如高阶矩、非单调损失或多聚类中心），算法无法直接泛化，仍需依赖代价高昂的非单调黑盒机制。
高维全参数联合估计的扩展阻碍：当前单参数估计依赖候选区间离散化切分与多次私有选择（PSPC），当扩展到多维参数或全模型向量时，候选网格规模随维度呈现指数爆炸，需探索更紧凑的高维切分策略。
实际常数因子的工程优化空间：尽管时间复杂度在大 $O$ 意义下为多项式阶，但在极端严苛的隐私预算（如 $\varepsilon = 0.1, \delta = 10^{-6}$）下，分位数采样数 $T$ 中的常数项依然相对偏大，工程落地仍需结合启发式提前终止策略。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 建立了子样本经验分位数交错理论，巧妙打通了单调统计量黑盒私有化的高效求解路径。
实验充分度: ⭐⭐⭐⭐☆ 理论推导完备自洽，涵盖通用单调统计、协方差特征值估计及 M-估计任务，但缺乏真实业务数据集上的实测开销消融。
写作质量: ⭐⭐⭐⭐⭐ 结构组织严谨，由浅入深铺陈分位数引理与下界证明，数学推导极其清晰流畅。
价值: ⭐⭐⭐⭐⭐ 为差分隐私黑盒估计领域补全了关键的多项式时间可行性拼图，确立了样本-计算折中的基础理论基准。

估计任务 / 统计量	评价指标	本文算法 (Ours)	传统子样本聚合 (S&A)	穷举下局部算法 [36]
通用单调统计量估计	样本复杂度 \(n\)	\(O\big(\frac{N \log(1/\delta)}{t\varepsilon}\big)\)	\(O\big(\frac{N \log(1/\delta)}{\varepsilon}\big)\)	\(N + O\big(\frac{\log(1/\delta)}{\varepsilon}\big)\)
通用单调统计量估计	运行时间/查询数	\(e^{O(t)} \cdot \mathrm{poly}\big(\frac{\log(1/\delta)}{\varepsilon}\big)\)	\(\mathrm{poly}\big(\frac{\log(1/\delta)}{\varepsilon}\big)\)	\(n^{\Theta(\frac{1}{\varepsilon}\log\frac{1}{\delta})}\)
协方差第 \(i\) 特征值 \(\lambda_i(\Sigma)\)	相对误差区间	\([1-\alpha, 1+\alpha]\)	\([1-\alpha, 1+\alpha]\)	\([1-\alpha, 1+\alpha]\)
特征值估计样本需求	样本量 \(n\)	\(\Omega\big(\frac{d\log(1/\delta)}{\alpha^2 t\varepsilon}\big)\)	\(\Omega\big(\frac{d\log(1/\delta)}{\alpha^2 \varepsilon}\big)\)	\(\Omega\big(\frac{d}{\alpha^2} + \frac{\log(1/\delta)}{\varepsilon}\big)\)
线性回归单参数测试 \(\theta_1\)	样本量 \(n\)	\(\Omega\big(\frac{d\log(1/\delta)}{t\varepsilon} + \mathrm{poly}(\cdot)\big)\)	\(\Omega\big(\frac{d\log(1/\delta)}{\varepsilon}\big)\)	不适用 / 超多项式时间

配置设定 (\(t\))	样本复杂度阶数 \(n\)	查询与运行时间复杂度	说明
\(t = 1\) (等价 S&A 基线)	\(N \cdot k_{\varepsilon,\delta}\)	\(O(k_{\varepsilon,\delta})\)	对应极小计算代价，样本需求最大
\(t = \log(k_{\varepsilon,\delta})\) (多项式效率点)	\(N \cdot \frac{k_{\varepsilon,\delta}}{\log(k_{\varepsilon,\delta})}\)	\(\mathrm{poly}(k_{\varepsilon,\delta})\)	保证严格多项式时间下的最优样本削减
\(t = \sqrt{k_{\varepsilon,\delta}}\) (中等平衡点)	\(N \cdot \frac{k_{\varepsilon,\delta}}{\sqrt{k_{\varepsilon,\delta}}}\)	\(\exp(O(\sqrt{k_{\varepsilon,\delta}}))\)	亚指数级计算时间，换取显著样本优化
\(t = k_{\varepsilon,\delta}\) (加性样本极限)	\(N + k_{\varepsilon,\delta}\)	\((1/\delta)^{1/\varepsilon} \cdot \mathrm{poly}(k_{\varepsilon,\delta})\)	达到最少样本需求，时间等同于穷举阶