提出随机采样隐私放大新理论，实现高效精准的差分隐私分析。
Privacy amplification by random allocation
- 用随机k选t采样替代传统方法，简化隐私分析。
- 证明其隐私界可由独立采样模型上界控制，精度接近最优。
- 提供可高效计算的数值估计算法，适合实际应用。
我们研究一种采样方案的隐私放大特性：用户数据在t个步骤中随机均匀地被选中k次。该方案近期应用于差分隐私优化[Chua et al., 2024a, Choquette-Choo et al., 2025]，也用于通信高效的高维私有聚合[Asi et al., 2025]。现有分析或依赖过保守的洗牌隐私放大，或需计算开销巨大的蒙特卡洛模拟。本文首次给出该采样方案的理论保证与数值估算算法。我们证明，随机k选t分配的隐私界可被独立（或泊松）子采样的隐私界所上界控制，其中每步使用用户数据的概率为(1+o(1))k/t。此外，我们提出两种新分析技术，在多个参数区间实现数值改进。总体而言，我们的边界可高效计算且近乎紧致，适用于高斯噪声添加场景。
原文摘要 · Abstract (English)
We consider the privacy amplification properties of a sampling scheme in which a user's data is used in k steps chosen randomly and uniformly from a sequence (or set) of t steps. This sampling scheme has been recently applied in the context of differentially private optimization [Chua et al., 2024a, Choquette-Choo et al., 2025] and is also motivated by communication-efficient high-dimensional private aggregation [Asi et al., 2025]. Existing analyses of this scheme either rely on privacy amplification by shuffling which leads to overly conservative bounds or require Monte Carlo simulations that are computationally prohibitive in most practical scenarios. We give the first theoretical guarantees and numerical estimation algorithms for this sampling scheme. In particular, we demonstrate that the privacy guarantees of random k-out-of-t allocation can be upper bounded by the privacy guarantees of the well-studied independent (or Poisson) subsampling in which each step uses the user's data with probability $(1+o(1))k/t$. Further, we provide two additional analysis techniques that lead to numerical improvements in several parameter regimes. Altogether, our bounds give efficiently-computable and nearly tight numerical results for random allocation applied to Gaussian noise addition.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。