Notes on Sampled Gaussian Mechanism

Nikita P. KalininarXiv 2024 · OpenReview

Abstract

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.

Introduction

In the field of private machine learning, the Sampled Gaussian Mechanism (SGM) serves as a fundamental building block. It operates by selecting a random subset of data (subsampling) and adding Gaussian noise to the resulting computation. This dual process creates a "privacy amplification" effect: because only a fraction of the dataset is accessed, the privacy risk to any single individual is inherently reduced.

However, practitioners face a complex trade-off. Increasing the sampling rate ($q$) provides a more accurate estimate of the true gradient (reducing variance), but it simultaneously diminishes the privacy amplification effect. To maintain a fixed privacy guarantee (defined by $\delta$), one might need to increase the noise level ($\sigma$). A critical question arises: does the benefit of a larger batch size outweigh the cost of the additional noise required?

A 2024 study by R"ais"a et al. argued that larger batch sizes are mathematically superior because the "effective noise"—defined as $\sigma_{\text{eff}} = \sigma/q$—actually decreases as $q$ increases. While their empirical evidence was compelling, their formal proof of Theorem 6.2 rested on an unproven mathematical conjecture. This work provides the rigorous proof for that conjecture, establishing a firm theoretical foundation for the use of large batch sizes in private optimization.

The Mathematical Challenge

The core of the problem lies in proving the monotonicity of the relationship between the sampling rate and the required noise. The author approaches this by defining an auxiliary function, $\Psi_{\epsilon,q}(\sigma)$, which characterizes the relationship between the privacy parameter $\delta$ and the noise level $\sigma$.

To confirm the conjecture, the proof follows a structured analytical path:

  1. Monotonicity Analysis: Through explicit calculus, the author demonstrates that $\Psi_{\epsilon,q}(\sigma)$ is strictly monotonically decreasing. This property is vital as it allows the function to be inverted, enabling a formal bound on the noise level $\sigma$ relative to the other privacy parameters.
  2. Reduction to a Technical Lemma: The complex privacy inequality is reduced to a simpler "technical statement" involving the standard normal cumulative distribution function ($\Phi$).
  3. Derivative Analysis of the Difference Function: To validate the final inequality, the author introduces a difference function $T(z)$. By analyzing its derivative, the proof shows that the function never crosses zero for positive values, thereby confirming that the conjecture holds true under the specified conditions.

Key Insights and Refined Bounds

This proof does more than just validate a previous claim; it offers deeper insights into the mechanics of Differential Privacy:

  • Validation of the "Effective Noise" Metric: The results reinforce that $\sigma_{\text{eff}} = \sigma(q)/q$ is the definitive metric for evaluating the utility of a private mechanism. It confirms the intuition that it is more efficient to use larger batches with slightly higher noise than tiny batches with lower noise.
  • Tightening the Privacy Bounds: The original conjecture assumed a condition of $\epsilon, q \ge 4\delta$. The author's analysis suggests this constant is conservative and could be improved from 4 to approximately 3.8319.
  • Identifying Boundary Failures: The proof highlights that the bound is "tight." If the conditions on $\epsilon, q,$ and $\delta$ are not met—specifically if they are extremely small—the conjecture can fail. The author provides numerical counter-examples to illustrate these edge cases, emphasizing the importance of the specific parameter ranges defined in the proof.

Conclusion

By proving Conjecture 6.3 from R"ais"a et al. (2024), this work completes the theoretical justification for Theorem 6.2. It provides analytical clarity on the interplay between sampling rates, noise levels, and privacy budgets. For the broader machine learning community, this confirms that for Differentially Private Stochastic Gradient Descent (DP-SGD), larger subsampling rates are mathematically preferred for achieving the best possible balance between data privacy and model utility.

Summary updated

Abstract

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.
BibTeX
@misc{kalinin2024notes,
  author = {Nikita P. Kalinin},
  title = {{Notes on Sampled Gaussian Mechanism}},
  year = {2024},
  eprint = {2409.04636},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2409.04636},
}
Figure