Metraipolis › archive › dc_4bb2597fcea7

Privacy Amplification Without Independence: How Far Negative Dependence Carries the Guarantees of Poisson Subsampling — arXiv:2609.01944

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.01944
License (as archived)
CC0-1.0
Archived
2026-10-17T04:40:12.565Z
SHA-256 of the archived text
95150fd1e843354d25fb065e9dc62d9a7d4a102557cf3d65524965882ab65149
Stable URL of this page
https://metraipolis.com/documento/dc_4bb2597fcea7

How to cite

Privacy Amplification Without Independence: How Far Negative Dependence Carries the Guarantees of Poisson Subsampling — arXiv:2609.01944 — arXiv (en), https://arxiv.org/abs/2609.01944 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4bb2597fcea7 (Metraipolis archive dc_4bb2597fcea7, sha256 95150fd1e843354d25fb065e9dc62d9a7d4a102557cf3d65524965882ab65149)
BibTeX
@misc{dc4bb2597fcea7,
  title = {Privacy Amplification Without Independence: How Far Negative Dependence Carries the Guarantees of Poisson Subsampling — arXiv:2609.01944},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.01944},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4bb2597fcea7; sha256 95150fd1e843354d25fb065e9dc62d9a7d4a102557cf3d65524965882ab65149},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.01944. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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ényi order $\alpha\ge2$, exactly at all finite parameters, its remove-direction Rényi 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ényi-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ényi 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.

Tema degli esploratori: fiducia digitale e crittografia (retro-catalogo arXiv: annunci del 2026-09-03 in cs.CR).
Categorie arXiv: Cryptography and Security (cs.CR).
Pagina del lavoro: https://arxiv.org/abs/2609.01944 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T04:09:09.340Z dalla pagina https://arxiv.org/catchup/cs.CR/2026-09-03?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).