[论文] Counting on Dummies: Privacy Amplification with Observable Counts and ...

论文概要

研究领域: ML 作者: Vitaly Feldman, Audra McMillan, Kunal Talwar 发布时间: 2026-10-30 arXiv: 2610.42139

中文摘要

在差分隐私随机梯度下降（DP-SGD）的许多实际部署中，服务器以批次方式处理数据。随机采样这些批次可通过隐私放大结果获得更好的隐私界限。大多数具有可证明隐私放大的采样方案，包括泊松采样和随机分配，都会产生可变的批次大小。这些方案的隐私保证要求不泄露批次大小。在分布式设置中，执行聚合的服务器或任何观察通信流量的参与方都可能获知这些批次大小。此外，在集中式和分布式设置中，内存和计算约束可能要求每个批次具有某个最大大小s，需要在批次超过此限制时进行截断。已知这种截断可能导致隐私损失的显著增加。在本工作中，我们通过一个简单的机制解决了这两个挑战：使用随机数量的"虚拟点"（dummy points）对批次大小进行隐私化，即使在截断情况下也能维持隐私保证。我们证明了该机制在分布式设置中易于实现，并为泊松采样和随机分配提供了该机制的一般性分析。我们的分析旨在支持高效且相对紧凑的隐私核算。它还通过子采样有效放大了计数发布的隐私，使得虚拟点的期望数量渐近地小于直接用非负噪声对（敏感度为一的）批次大小进行隐私化所需的数量。对于带截断批次的泊松采样，我们通过实证证明该机制比最近由（Ganesh, 2025）提出的截断直接核算实现了更好的隐私-效率权衡。

原文摘要

In many practical deployments of Differentially Private Stochastic Gradient Descent (DP-SGD), the server processes data in batches. Randomly sampling these batches allows for better privacy bounds via privacy amplification results. Most sampling schemes with provable privacy amplification, including Poisson sampling and random allocation, result in variable batch sizes. The privacy guarantee of these schemes requires that the batch sizes are not revealed. In distributed settings, the server performing the aggregation or any party observing the communication traffic may learn these batch sizes. Furthermore, in both centralized and distributed settings, memory and computation constraints may require each batch to be of some maximum size \(s\), necessitating truncation of the batch when it exce...

#论文 #arXiv #ML #小凯