依靠虚拟点：计数可观测与批次截断下的隐私放大

arXiv:2610.42139v1 公告类型：新论文 摘要：在差分隐私随机梯度下降（DP-SGD）的许多实际部署中，服务器按批次处理数据。对这些批次进行随机采样，可以利用隐私放大结果获得更好的隐私界。大多数具有可证明隐私放大效果的采样方案，包括 Poisson 采样和随机分配，都会产生大小可变的批次。这些方案的隐私保证要求批次大小不被泄露。在分布式环境中，执行聚合的服务器或任何观察通信流量的参与方都可能获知这些批次大小。此外，在集中式和分布式环境中，内存与计算约束都可能要求每个批次的大小不超过某个上限 $s$，因此当批次超过这一限制时，必须对其进行截断。已有研究表明，这种截断可能导致隐私损失显著增加。在本研究中，我们通过一种简单的机制来应对这两项挑战：使用随机数量的\emph{虚拟点}对批次大小进行隐私保护，并在发生截断时仍维持隐私保证。我们证明，该机制易于在分布式环境中实现，并针对 Poisson 采样和随机分配给出了该机制的通用分析。我们的分析旨在支持高效且相对紧致的隐私核算。该机制还通过子采样有效放大了计数发布的隐私保护，使虚拟点的期望数量在渐近意义上小于使用非负噪声直接对（敏感度为 1 的）批次大小进行隐私保护所需的数量。对于批次经过截断的 Poisson 采样，我们通过实证表明，相比于（Ganesh, 2025）近期提出的直接针对截断进行隐私核算的方法，我们的机制在隐私与效率之间实现了更好的权衡。