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

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