论文分析联邦 API 下差分隐私选择问题的复杂度

论文证明在标准噪声聚合原语下，任何隐私选择算法都需要 Ω(√d/ε) 个样本，这是聚合模型固有的限制。作者提出新增一个实现稀疏向量技术（SVT）的原语，并据此给出 ε-差分隐私选择算法，在维度 d 上达到 O(log(dn)/ε) 的加性误差，当 n 相对 d 为多项式有界时与中心模型持平，且期望 SVT 查询次数为 O(d log*d)。