Notes on Sampled Gaussian Mechanism
<|reference_start|>Notes on Sampled Gaussian Mechanism: In these notes, we prove a recent conjecture posed in the paper by R\"ais\"a, 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, $\sigma_{\text{eff}} = \frac{\sigma(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.<|reference_end|>
@article{kalinin2024notes,
    title={Notes on Sampled Gaussian Mechanism},
    author={Nikita P. Kalinin},
    journal={arXiv preprint arXiv:2409.04636},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.04636},
    primaryClass={cs.LG stat.ML}
}