提出无需采样的隐私预算计算方法，提升矩阵机制在随机分配下的隐私保障效率。
Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation
- 基于Rényi散度与条件组合的无采样边界方法
- 数值实验显示在多种矩阵机制中均更优
- 适合需要精确隐私保证的研究者和系统开发者
我们研究在随机分配（即球入桶模型）下，基于矩阵分解的差分隐私训练中的隐私放大问题。Choquette-Choo等（2025）提出基于采样的蒙特卡洛方法计算放大参数，但其保证仅以高概率成立，或需机制随机弃权，且所需样本数与δ成反比。相比之下，本文基于Rényi散度与条件组合，构建无采样边界。前者通过动态规划高效计算；后者在小ε时提供更强保障，弥补Rényi散度在该情形下的过估计缺陷。本框架适用于任意带状与非带状矩阵。数值对比表明，该方法在研究与实践中广泛使用的各类矩阵机制中均表现优异。
原文摘要 · Abstract (English)
We study privacy amplification for differentially private model training with matrix factorization under random allocation (also known as the balls-in-bins model). Recent work by Choquette-Choo et al. (2025) proposes a sampling-based Monte Carlo approach to compute amplification parameters in this setting. However, their guarantees either only hold with some high probability or require random abstention by the mechanism. Furthermore, the required number of samples for ensuring $(ε,δ)$-DP is inversely proportional to $δ$. In contrast, we develop sampling-free bounds based on Rényi divergence and conditional composition. The former is facilitated by a dynamic programming formulation to efficiently compute the bounds. The latter complements it by offering stronger privacy guarantees for small $ε$, where Rényi divergence bounds inherently lead to an over-approximation. Our framework applies to arbitrary banded and non-banded matrices. Through numerical comparisons, we demonstrate the efficacy of our approach across a broad range of matrix mechanisms used in research and practice.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。