Complexity of Differentially Private Selection via Federated APIs¶

会议: NeurIPS 2026
arXiv: 2610.38789
领域: 学习理论
关键词: 差分隐私, 联邦学习, 隐私选择机制, 稀疏向量技术, 样本复杂度下界

一句话总结¶

证明了基于高斯噪声聚合API进行私有候选选择必须承受 $\Omega(\sqrt{d}/\varepsilon)$ 的样本复杂度下界，进而提出联邦稀疏向量技术（SVT）API，实现匹配中心化模型最优的 $O(\log(dn)/\varepsilon)$ 加法误差与近线性期望查询复杂度 $O(d\log^* d)$。

研究背景与动机¶

差分隐私（DP）作为保护个体敏感数据的严格数学框架，已成为现代隐私计算与联邦分析的行业金标准。为规避浮点数安全漏洞与复杂算法验证的极高成本，现代工业界隐私系统（如 OpenDP、PINQ、Google DP 构建块）普遍转向模块化 API 架构，通过对少量可信基元（如高斯/拉普拉斯加噪聚合机制）进行组合与隐私账本追踪来构建复杂流水线。在跨设备联邦学习场景中，安全聚合（SecAgg）和洗牌模型（Shuffle DP）作为核心聚合基础设施被广泛部署，支撑了基于梯度聚合的私有模型训练（DP-SGD）。

然而，当面对特征筛选、超参数调优、多臂老虎机以及指数机制等核心的“差分隐私选择问题”（Private Selection）时，基于聚合 API 的现有算法遭遇了严重的效用瓶颈。在中心化差分隐私模型下，从 $d$ 个候选维度中选出近似最优项仅需 $O(\log d / \varepsilon)$ 的样本复杂度；而在联邦聚合与洗牌架构下，已知算法必须消耗 $\Omega(\sqrt{d}/\varepsilon)$ 样本量才能维持有效选择。理论界此前并不清楚这种效用鸿沟是现有算法设计的缺陷，还是聚合 API 算力表达的内在信息论极限；同时，缺乏一种既符合分布式可信执行约束、又能打破此界限的极简 API 抽象。

本文的目标是彻底厘清联邦分布式 API 在隐私选择问题上的理论边界。作者证明了基于任何局部或组合高斯聚合 API 进行自适应查询选择均具有不可逾越的 $\Omega(\sqrt{d})$ 样本复杂度下界，并由此提出将稀疏向量技术引入联邦 API 体系。核心 idea：证明聚合 API 在隐私选择任务上具有内在样本复杂度下界，进而提出轻量且易于安全多方计算/TEE实现的联邦稀疏向量技术（SVT）API，结合几何衰减隐私二分搜索与随机子采样过滤，首次在联邦约束下以近线性期望查询数达成中心化最优的选择误差。

方法详解¶

整体框架¶

本文构建了针对联邦隐私选择的下界证明与上界算法体系。首先，针对黑盒高斯聚合 API 建立信息论下界，证明仅依赖加性聚合无论如何进行自适应查询都无法突破维度诅咒。随后，设计了联邦稀疏向量技术 API（SVT API），该接口支持连续接收加性查询 $(f_j, \tau_j)$，并在检测到首个超过阈值的查询时终止流并扣除固定隐私预算。在此基元之上，算法流水线经历了从粗糙二分搜索、线性扫描、几何衰减二分搜索到近线性子采样过滤选择机制（Algorithm 9）的演进。

整体框架的算法运行与选择流程如下图所示：

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入: d 个候选加性得分与用户数据"] --> B["高斯聚合 API 下界分析<br/>归约为分布式黑盒通讯复杂度"]
    B --> C["联邦 SVT API 抽象<br/>仅在首个超出阈值时消耗固定隐私预算"]
    C --> D["几何衰减隐私二分搜索<br/>早期粗搜低预算+后期精搜高预算"]
    D --> E["随机子采样与阈值过滤<br/>采样概率 1/t 筛选候选并设立动态阈值"]
    E --> F["小规模候选集递归精选<br/>将候选集裁剪至小规模并调用最终搜索"]
    F --> G["输出: 满足 ε-DP 的最优候选索引"]

关键设计¶

1. 高斯聚合 API 下界的分布式模拟与信息论割裂 为了证明黑盒高斯聚合 API 无法高效完成隐私选择，作者将通用自适应高斯聚合预言机 $\mathcal{G}(S)$ 归约到分布式加噪协议。由于每个用户在本地加入方差缩放为 $\sigma^2/n$ 的高斯噪声求和后在统计分布上严格等价于中心化高斯机制，因此任意满足组合 $\rho$-zCDP 的聚合算法均可转化为局部 $n\rho$-zCDP 协议。接着，作者构造了稀疏布尔区分问题（Problem 4.3），要求算法区分全体坐标均值为 $1/2$ 的纯均匀分布与某一秘密坐标均值为 $1$ 的单峰分布。利用 Jayram 的 Hellinger 剪切-粘贴不等式（Cut-and-Paste Inequality）与互信息链式法则，证明了任何成功率为 $2/3$ 的黑盒协议其通信记录必须满足 $I(M; X^{\leq n} \mid V, Z) = \Omega(d)$，而局部 DP 约束下的互信息上界为 $n^2 \rho$。两式联立立即可得样本复杂度必须满足： $$n = \Omega\left(\sqrt{\frac{d}{\rho}}\right) = \Omega\left(\frac{\sqrt{d\log(1/\delta)}}{\varepsilon}\right)$$ 这一理论严格封死了仅依靠标准加噪聚合构建高精度私有选择的途径。

2. 状态化联邦稀疏向量 API（SVT API）机制构建 针对上述局限，作者提出了状态化的联邦稀疏向量接口。在传统聚合中，每一次标量查询都必须支付一次独立的噪声方差与隐私预算。而 SVT API 内部维护一个私有拉普拉斯阈值扰动 $\text{S.n} \sim \text{Lap}(2/\varepsilon)$；对于输入的每个加性函数 $f_j(x) = \sum_{i} \text{clip}_{[0,1]}(f_j(x_i))$ 与阈值 $\tau_j$，系统通过独立扰动 $\nu_j \sim \text{Lap}(4/\varepsilon)$ 判断是否满足 $f_j(x) + \nu_j \ge \tau_j + \text{S.n}$。所有低于阈值的“No”回答完全不额外消耗隐私预算，仅在输出首个“Yes”时关闭流并结清 $\varepsilon$。在工程实现上，由于加性求和可通过成熟的两方安全计算（Prio / Two-Server）或受信执行环境（TEE）在外部高效聚合并秘密共享，只需对最后的标量加噪比较进行微型电路计算，避免了安全多方计算在全候选集上运行巨大 Argmax 算子的严重开销。

3. 几何衰减隐私分配二分搜索（Geometric Binary Search） 单纯在得分区间 $[0, n]$ 上进行标准二分搜索需要 $R = O(\log n)$ 轮，平均分配隐私预算会导致每轮预算稀释为 $\varepsilon / (2R)$，使得加法误差退化至 $O(\frac{\log d \log n}{\varepsilon})$。作者设计了带有几何衰减权重的二分搜索机制（Algorithm 8）。核心洞察在于二分搜索前期区间宽度极大，测量误差容忍度高，而每经历一轮，前一轮残留的区间误差在后续迭代中会被折半收缩（$W_{t+1} \le W_t / 2 + \alpha_t$）。因此，作者设定衰减比率 $\gamma = 3/4$，第 $t$ 轮分配预算 $\varepsilon_t \propto \varepsilon \gamma^{T-t}$。误差级数求和满足： $$\sum_{t=1}^T \frac{\alpha_t}{2^{T-t}} = \frac{32 Z}{\varepsilon} \log\left(\frac{2|P|T}{\beta}\right) \sum_{k=0}^{T-1} (2\gamma)^{-k} \le \frac{384}{\varepsilon} \log\left(\frac{2|P|T}{\beta}\right)$$ 由于 $2\gamma = 3/2 > 1$，前序轮次的误差被指数级衰减，总体累积误差完全由最后一轮的高隐私预算决定，从而完全消除了误差中额外多出的 $\log n$ 因子，使加法误差重回中心化下限 $O(\frac{\log d}{\varepsilon})$。

4. 随机子采样与高吞吐阈值过滤（Near-Linear Algorithm） 几何二分搜索在每轮仍需扫描全体候选集合 $P$，总查询次数仍为 $O(d \log n)$。为了使查询复杂度逼近线性的 $O(d)$，算法 9 引入分阶段子采样与阈值过滤。在每一阶段中，候选区间长度为 $x\alpha$（令 $t = \lceil\log_2 x\rceil$），算法首先以概率 $1/t$ 独立采样候选子集 $P'$；在包含当前见证坐标的子集 $P$ 上运行 $t$ 轮几何二分搜索以获取局部最高分的无偏估计 $\ell_P$。接着设定安全过滤阈值 $\tau = \ell_P + 50 a$，并在全体候选集上发起单次 SVT 阈值扫描。根据极端值理论，超过该阈值的候选数量服从几何分布且期望仅为 $t$，超出 $t^2$ 的极端概率至多为 $e^{-t}$。若触发早停（$|Y|=t^2$），则回退全量扫描；否则仅需在极小候选集 $C = Y \cup \{j_P\}$ 上耗费至多 $t^3$ 次查询完成精炼。每一阶段使区间长度从 $x$ 锐降至 $64 \log_2^3 x$，仅需 $O(\log^* n)$ 个阶段即可收敛到常数宽度，将总体期望查询数成功压制在 $O(d \log^* n + \log^3 n)$。

复杂度下界与联邦机制分析¶

通过将分布式黑盒加噪信道与通信信息论紧密结合，本文划定了三大主流联邦隐私 API 范式的复杂度界限： 1. 聚合模型（SecAgg / Gaussian Aggregation）：在对数隐私损失下必须使用 $\Omega(\sqrt{d}/\varepsilon)$ 样本；对于自适应查询机制，信息泄露量与查询轮数紧密耦合，无法以更少样本区分微小优势候选。 2. 洗牌模型（Shuffle DP）：已有文献（Chen et al., 2021; Cheu & Ullman, 2021）针对单轮或强鲁棒洗牌协议证明了私有选择同样需要 $\Omega(d/m)$ 或 $\Omega(\sqrt{d}/(\alpha\varepsilon))$ 的样本下界。 3. 联邦 SVT 模型（本文模型）：在纯 $\varepsilon$-DP 保证下，仅需单次初始化与 $O(d \log^* d)$ 次轻量加性比较，即可达成与完全不受限中心化差分隐私同等量级的 $O(\frac{\log d}{\varepsilon})$ 误差。

实验关键数据¶

论文为纯理论密码学与差分隐私理论奠基之作，给出了严格的数学渐近证明与针对各类学习任务的解析界对比。以下整理核心的理论对比表与消融/算法演进分析表。

主实验：不同联邦计算范式下的隐私选择复杂度对比¶

隐私与信任架构	隐私语义保证	选择任务样本复杂度下限 $n$	期望选择加法误差	查询复杂度 (API Calls)	核心通信瓶颈 / 瓶颈算子
中央化差分隐私 (Central DP)	纯 $\varepsilon$-DP	$O(\frac{\log d}{\varepsilon})$	$O(\frac{\log d}{\varepsilon})$	不适用 (直接访问全库)	信任中心化服务器
联邦安全聚合 (SecAgg API)	组合 $(\varepsilon,\delta)$-DP	$\Omega\left(\frac{\sqrt{d\log(1/\delta)}}{\varepsilon}\right)$ (本文下界)	$\Omega(\sqrt{d}/\varepsilon)$	任意有限轮次	每轮高维向量全量聚合加噪
单轮洗牌模型 (Shuffle DP)	$(\varepsilon,\delta)$-DP	$\Omega\left(\frac{d}{m}\right)$ 或 $\Omega\left(\frac{\sqrt{d}}{\varepsilon}\right)$	$\Omega(\sqrt{d}/\varepsilon)$	$O(d)$	洗牌混淆器开销大且多轮困难
联邦朴素二分搜索 (Alg. 6)	纯 $\varepsilon$-DP	$O(\frac{\log d \log n}{\varepsilon})$	$O\left(\frac{\log d \log n}{\varepsilon}\right)$	$O(d \log n)$	隐私预算均分导致误差放大
联邦线性扫描选择 (Alg. 7)	纯 $\varepsilon$-DP	$O(\frac{\log (dn)}{\varepsilon})$	$O\left(\frac{\log (dn)}{\varepsilon}\right)$	$O(dn)$	逐整数扫描导致查询数过多
联邦几何二分搜索 (Alg. 8)	纯 $\varepsilon$-DP	$O(\frac{\log (dn)}{\varepsilon})$	$O\left(\frac{\log (dn)}{\varepsilon}\right)$	$O(d \log n)$	每一轮均需遍历全体 $d$ 候选
联邦近线性过滤选择 (Alg. 9)	纯 $\varepsilon$-DP	$O(\frac{\log (dn)}{\varepsilon})$	$O\left(\frac{\log (dn)}{\varepsilon}\right)$ (达中心化最优)	*$O(d \log^ n + \log^3 n)$**	轻量标量阈值比较，近线性最优

消融实验：SVT 选择机制各演化版本效能与特性剖析¶

算法版本	核心演进组件	误差界分析	查询开销分析	机制权衡与优缺点评价
算法 6 (Private Binary Search)	固定划分区间，均分隐私预算 $\varepsilon/(2R)$	$O\left(\frac{\log n \log(d\log n)}{\varepsilon}\right)$	$O(d \log n)$ 确定性查询	实现直观，但因预算被 $O(\log n)$ 轮切碎造成精度受损
算法 7 (Private Linear Scan)	单一流降序扫描，首个命中即停	$O\left(\frac{1 + \log(d(n+1))}{\varepsilon}\right)$	$O(d(n+1))$ 最坏情况查询	误差逼近中心最优，但在样本量 $n$ 较大时查询通信开销无法承受
算法 8 (Geometric Binary Search)	几何缩放加权预算 $\varepsilon_t \propto \gamma^{T-t}$，残留误差折半	$O\left(\frac{\log(d\log n)}{\varepsilon}\right)$	$O(d \log n)$ 确定性查询	成功抹除 $\log n$ 误差放大项；每轮须全量遍历 $d$ 维得分
算法 9 (Sampling & Filtering)	采样估计参考值 + 阈值单次扫描过滤 + 稀疏集二次精搜	$O\left(\frac{1}{\varepsilon}\log\frac{d\log n}{\beta}\right)$	$O(d \log^* n + \log^3 n)$ 期望查询	综合效用最高：保持纯 $\varepsilon$-DP 与中心化误差，查询次数压至几乎与维度 $d$ 线性一致

关键发现¶

根本性信息鸿沟：通过构建高斯聚合到局部通讯协议的投影，严格证明了在无额外状态或非线性机制辅助下，标准加噪聚合 API 解决高维稀疏选择任务必定面临 $\Omega(\sqrt{d})$ 的样本障碍。
误差收缩与预算分配的几何匹配：二分搜索的区间收缩特性天然契合几何衰减预算分配，后期的精准度比前期更重要。$\gamma = 3/4$ 的收敛比率完美抵消了累积误差，使多轮交互无需借助高级组合定理即达最优纯隐私界。
阶段性超几何收敛：通过以 $1/t$ 比例构建参考候选集，SVT 阈值过滤不仅将留存候选集期望大小压至 $t$ 以下，且通过 $O(\log^* n)$ 轮迭代即可跨越双指数级搜索空间，极大拓展了超大规模特征与高维词表在联邦环境下的可用性。

亮点与洞察¶

证明黑盒聚合在选择任务上的信息论硬下界：通过将自适应高斯聚合转化为局部 zCDP 协议并利用 Jayram 割裂不等式，确立了 $\Omega(\sqrt{d})$ 的严格极限，解决了理论界长久以来关于聚合 API 表达能力的悬而未决之问。
极小化可信计算基（TCB）的实用哲学：相较于在 TEE 或 MPC 中直接实现沉重、易受侧信道和状态连续性攻击的通用 Argmax 算法，SVT API 仅需维护单标量状态与单次阈值判断，将复杂的决策优化全部移到不可信分析端执行，兼顾了数学可证明性与密码学部署轻量性。
通用下流算法适配能力：该基元能直接无缝赋能带类别的 Top-$k$ Heavy-Hitters 挖掘、高维稀疏高斯均值估计（Sparse Mean Estimation，误差仅 $O(\sqrt{\frac{\log d}{n}} + \frac{k\sqrt{\log(nd)}}{n\varepsilon})$）、以及分布式乘性权重与指数机制合成数据生成（MWEM）。

局限与展望¶

针对非加性得分函数的限制：当前联邦 SVT API 强依赖于得分函数可分解为各个体贡献之和（即 $\sum_i f_j(x_i)$）的形式；对于不可拆分的复杂非线性目标（如依赖样本间高阶相关性的全局统计量），仍需进一步探索低敏感度非加性接口。
异步参与与掉线鲁棒性机制：在实际大规模跨设备联邦系统中，客户端存在异构掉线与网络延迟。算法 9 的多阶段过滤机制需要多轮协调，在长尾不可靠网络环境下需要设计抗丢包与自适应批量过滤机制。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次确立了自适应高斯聚合 API 在选择任务上的理论下界，并提出了轻量完备的联邦 SVT API 体系。
理论完备性: ⭐⭐⭐⭐⭐ 证明从信息论不等式到近线性期望算法层层递进，推导严密且常数显式封闭。
写作质量: ⭐⭐⭐⭐⭐ 逻辑结构严谨清晰，从 API 抽象背景到密码学实现方案阐述详实。
价值: ⭐⭐⭐⭐⭐ 为解决联邦差分隐私系统核心瓶颈（选择与稀疏估计）提供了极具实用价值的标准基元指导。

隐私与信任架构	隐私语义保证	选择任务样本复杂度下限 \(n\)	期望选择加法误差	查询复杂度 (API Calls)	核心通信瓶颈 / 瓶颈算子
中央化差分隐私 (Central DP)	纯 \(\varepsilon\)-DP	\(O(\frac{\log d}{\varepsilon})\)	\(O(\frac{\log d}{\varepsilon})\)	不适用 (直接访问全库)	信任中心化服务器
联邦安全聚合 (SecAgg API)	组合 \((\varepsilon,\delta)\)-DP	\(\Omega\left(\frac{\sqrt{d\log(1/\delta)}}{\varepsilon}\right)\) (本文下界)	\(\Omega(\sqrt{d}/\varepsilon)\)	任意有限轮次	每轮高维向量全量聚合加噪
单轮洗牌模型 (Shuffle DP)	\((\varepsilon,\delta)\)-DP	\(\Omega\left(\frac{d}{m}\right)\) 或 \(\Omega\left(\frac{\sqrt{d}}{\varepsilon}\right)\)	\(\Omega(\sqrt{d}/\varepsilon)\)	\(O(d)\)	洗牌混淆器开销大且多轮困难
联邦朴素二分搜索 (Alg. 6)	纯 \(\varepsilon\)-DP	\(O(\frac{\log d \log n}{\varepsilon})\)	\(O\left(\frac{\log d \log n}{\varepsilon}\right)\)	\(O(d \log n)\)	隐私预算均分导致误差放大
联邦线性扫描选择 (Alg. 7)	纯 \(\varepsilon\)-DP	\(O(\frac{\log (dn)}{\varepsilon})\)	\(O\left(\frac{\log (dn)}{\varepsilon}\right)\)	\(O(dn)\)	逐整数扫描导致查询数过多
联邦几何二分搜索 (Alg. 8)	纯 \(\varepsilon\)-DP	\(O(\frac{\log (dn)}{\varepsilon})\)	\(O\left(\frac{\log (dn)}{\varepsilon}\right)\)	\(O(d \log n)\)	每一轮均需遍历全体 \(d\) 候选
联邦近线性过滤选择 (Alg. 9)	纯 \(\varepsilon\)-DP	\(O(\frac{\log (dn)}{\varepsilon})\)	\(O\left(\frac{\log (dn)}{\varepsilon}\right)\) (达中心化最优)	*\(O(d \log^ n + \log^3 n)\)**	轻量标量阈值比较，近线性最优

算法版本	核心演进组件	误差界分析	查询开销分析	机制权衡与优缺点评价
算法 6 (Private Binary Search)	固定划分区间，均分隐私预算 \(\varepsilon/(2R)\)	\(O\left(\frac{\log n \log(d\log n)}{\varepsilon}\right)\)	\(O(d \log n)\) 确定性查询	实现直观，但因预算被 \(O(\log n)\) 轮切碎造成精度受损
算法 7 (Private Linear Scan)	单一流降序扫描，首个命中即停	\(O\left(\frac{1 + \log(d(n+1))}{\varepsilon}\right)\)	\(O(d(n+1))\) 最坏情况查询	误差逼近中心最优，但在样本量 \(n\) 较大时查询通信开销无法承受
算法 8 (Geometric Binary Search)	几何缩放加权预算 \(\varepsilon_t \propto \gamma^{T-t}\)，残留误差折半	\(O\left(\frac{\log(d\log n)}{\varepsilon}\right)\)	\(O(d \log n)\) 确定性查询	成功抹除 \(\log n\) 误差放大项；每轮须全量遍历 \(d\) 维得分
算法 9 (Sampling & Filtering)	采样估计参考值 + 阈值单次扫描过滤 + 稀疏集二次精搜	\(O\left(\frac{1}{\varepsilon}\log\frac{d\log n}{\beta}\right)\)	\(O(d \log^* n + \log^3 n)\) 期望查询	综合效用最高：保持纯 \(\varepsilon\)-DP 与中心化误差，查询次数压至几乎与维度 \(d\) 线性一致