Tight Group-Level DP Guarantees for DP-SGD with Sampling via Mixture of Gaussians Mechanisms

Arun GanesharXiv 2024 · DOI · arXiv

Introduction

Standard Differential Privacy (DP) frameworks are primarily designed to protect the data of individual users. However, many practical applications require group-level DP, ensuring privacy for groups of $k$ individuals, such as households or small communities. Historically, calculating these guarantees for the widely used DP-SGD algorithm relied on "black-box" mathematical conversions like Vadhan’s Lemma. These methods are often overly conservative (loose) and numerically unstable, particularly as group sizes increase.

This paper, authored by Arun Ganesh of Google Research, introduces a novel accounting method that treats the sampling process in DP-SGD as a Mixture of Gaussians (MoG) mechanism. This approach provides tight, numerically stable group-level $(\epsilon, \delta)$-DP guarantees, significantly improving upon previous industry standards.

Methodology: The Mixture of Gaussians Framework

The core innovation lies in moving away from generic privacy conversions and instead analyzing the specific mechanics of DP-SGD. During training, a random batch of data is sampled. From a privacy perspective, the sensitivity of the gradient update depends on the number of sensitive users present in that specific batch.

The authors model this distribution of sensitivity as a Mixture of Gaussians. By utilizing Privacy Loss Distributions (PLD), they can track the cumulative privacy loss across thousands of training iterations more accurately than single-point $(\epsilon, \delta)$ tracking. To handle the high-dimensional nature of gradients, the paper proves a "vector-to-scalar" reduction lemma, demonstrating that a one-dimensional analysis provides a valid and tight bound for the multi-dimensional case. The framework supports both Poisson sampling and fixed batch size sampling.

Experimental Evaluation

The proposed method was evaluated using the CIFAR-10 image classification dataset ($n=50,000$). The experimental setup involved training for 20 epochs (2,000 iterations) with a batch size of 500. The analysis compared the new MoG-based approach ("Our analysis") against the traditional Vadhan-based conversion ("Vadhan analysis") and a theoretical lower bound.

Key Results and Discussion

The MoG approach demonstrates two primary advantages: superior tightness and enhanced numerical stability.

Tightness and Linear Growth

A key insight from the research is that the actual privacy loss ($\epsilon$) grows nearly linearly with the group size $k$. Previous black-box methods often suggested exponential growth in certain regimes, which discouraged the implementation of group-level privacy. The MoG analysis closely tracks the theoretical lower bound, proving its tightness.

Privacy loss ($\epsilon$) for $\sigma=5$, demonstrating the tightness of the MoG analysis compared to the lower bound and the loose Vadhan baseline.

Overcoming Numerical Instability

Traditional methods often fail for large groups or low noise levels because they require calculating extremely small intermediate values. For instance, at a noise multiplier of $\sigma=1$, the Vadhan analysis reports an "infinite" privacy loss ($\epsilon = \infty$) for groups larger than 9, a known bug in standard libraries like TensorFlow Privacy. The MoG method remains stable and provides usable guarantees in these scenarios.

Privacy loss ($\epsilon$) as a function of group size for $\sigma=1$. Note the instability of the Vadhan analysis at larger group sizes compared to the stable MoG analysis.

Conclusion

By treating DP-SGD sampling as a Mixture of Gaussians mechanism, this work provides a significant upgrade to group-level privacy accounting. The method is now integrated into the open-source dp_accounting library. Future work includes extending this "every-iterate" analysis to "last-iterate" guarantees, which could potentially offer even tighter bounds for the final released model, though this remains a challenging open problem for non-convex deep learning models.

Summary updated

Abstract

We give a procedure for computing group-level $(ε, δ)$-DP guarantees for DP-SGD, when using Poisson sampling or fixed batch size sampling. Up to discretization errors in the implementation, the DP guarantees computed by this procedure are tight (assuming we release every intermediate iterate).
BibTeX
@misc{ganesh2024tight,
  author = {Arun Ganesh},
  title = {{Tight Group-Level DP Guarantees for DP-SGD with Sampling via Mixture of Gaussians Mechanisms}},
  year = {2024},
  eprint = {2401.10294},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2401.10294},
}
Figure