Notes on Sampled Gaussian Mechanism
This work resolves a theoretical gap in differential privacy for machine learning, but it is incremental as it completes a proof from prior research.
The authors tackled the problem of proving a conjecture about the Sampled Gaussian Mechanism in differential privacy, specifically showing that the effective noise level decreases with larger subsampling rates, which improves privacy-utility trade-offs.
In these notes, we prove a recent conjecture posed in the paper by Räisä, O. et al. [Subsampling is not Magic: Why Large Batch Sizes Work for Differentially Private Stochastic Optimization (2024)]. Theorem 6.2 of the paper asserts that for the Sampled Gaussian Mechanism - a composition of subsampling and additive Gaussian noise, the effective noise level, $σ_{\text{eff}} = \frac{σ(q)}{q}$, decreases as a function of the subsampling rate $q$. Consequently, larger subsampling rates are preferred for better privacy-utility trade-offs. Our notes provide a rigorous proof of Conjecture 6.3, which was left unresolved in the original paper, thereby completing the proof of Theorem 6.2.