Search papers, labs, and topics across Lattice.
This paper investigates the privacy guarantees of Poisson subsampling in the context of structured participation schemes, which are increasingly adopted in differentially private optimization. By analyzing the negative dependence of participation indicators, the authors establish that under certain conditions, the privacy amplification of these schemes can be effectively compared to that of independent Poisson subsampling. Key findings reveal that while Poisson subsampling dominates at higher R\'enyi orders, this dominance can reverse under specific conditions, providing critical insights into when alternative sampling methods may be preferable.
Negative dependence in structured participation can yield surprising privacy guarantees that challenge the supremacy of Poisson subsampling in differential privacy.
Poisson subsampling is the default sampler in differentially private optimization because its independence makes privacy amplification tractable. Practical systems, however, are moving toward structured participation: random allocation (balls-in-bins), per-epoch allocation, random check-ins, schemes widely believed to be at least as private as Poisson subsampling at the matched rate. We isolate the probabilistic mechanism behind this belief and delimit it exactly, for Gaussian mechanisms up to correlated-noise matrix mechanisms. (1) If the participation indicator vector is negatively associated (NA), then at every integer R\'enyi order $\alpha\ge2$, exactly at all finite parameters, its remove-direction R\'enyi divergence is dominated by that of the marginal-matched independent scheme. For fixed gradient sequences, this extends to the mechanism level whenever the noise strategy's Gram matrix is sign-balanced, an $O(t^2)$-checkable condition. (2) The integer-order restriction is essential. For random allocation with $k=1$, we prove a linear law for the R\'enyi-difference criterion: at large $t$, dominance reverses for every $\alpha<3/2$, including KL divergence, while the crossing order tends to $3/2$ independently of $\sigma$. (3) We also localize the known failure of rate-matched Poisson domination exactly: below $(1-q)^t$, the hockey-stick ordering reverses, so substituting the Poisson pair into composition machinery is unsound. An upper-tail argument yields a finite crossover $\gamma_\star$, connecting this threshold picture to the R\'enyi boundary at $3/2$. Together, these results give a substitution map for privacy accounting: when Poisson-based computations remain sound for structured participation, where they fail, and what sound alternatives cost in deployment.
