On Connecting Stochastic Gradient MCMC and Differential Privacy

Bai Li, Changyou Chen, Hao Liu, Lawrence Carin

Abstract

Concerns related to data security and confidentiality have been raised when applying machine learning to real-world applications. Differential privacy (DP) provides a principled and rigorous privacy guarantee for such applications. This paper explores the synergy between Stochastic Gradient Markov Chain Monte Carlo (SG-MCMC) and DP. We demonstrate that the inherent randomness in Bayesian sampling algorithms naturally satisfies DP requirements. By applying the "Moments Accountant" method, we prove that these algorithms can achieve state-of-the-art accuracy with much larger, more practical stepsizes than previously established, bridging the gap between theoretical privacy guarantees and empirical utility.

Introduction

In the era of large-scale data, machine learning models are prone to memorizing sensitive information from training sets. While Differential Privacy offers a mathematical framework to mitigate this, it often imposes a significant "utility-privacy trade-off." Traditional methods for making Bayesian sampling private—specifically Stochastic Gradient Langevin Dynamics (SGLD)—have relied on loose theoretical bounds requiring extremely small stepsizes. These tiny stepsizes hinder the algorithm's ability to explore complex, non-convex landscapes, leading to poor model performance in deep learning contexts. This work addresses whether strong privacy guarantees can be provided for SG-MCMC while maintaining high accuracy and convergence speed.

Methodology: DP-SGLD and Tighter Bounds

The authors introduce DP-SGLD, which integrates standard SGLD with two critical components for privacy:

  1. Gradient Clipping: A norm-clipping step is implemented to bound the influence of any single data point on the gradient, a fundamental requirement for DP.
  2. Moments Accountant: Instead of standard composition rules, the authors adapt the Moments Accountant method to track privacy loss more precisely across iterations. This allows for a significantly larger privacy budget for a given number of steps.

A key theoretical contribution is the derivation of new upper bounds for the stepsize. As shown in the figure below, the proposed bounds allow for stepsizes that are orders of magnitude larger than those suggested by prior work (e.g., Wang et al.). This increased stepsize is crucial for the algorithm to converge effectively in practical settings.

Comparison of stepsize upper bounds against prior work.

Experimental Evaluation

The efficacy of DP-SGLD was evaluated on benchmarks including the Adult dataset (logistic regression), MNIST, and SVHN.

Utility-Privacy Trade-off

On the Adult dataset, DP-SGLD demonstrated superior performance compared to other private Bayesian methods such as Differential Private Variational Inference (DPVI) and Objective Perturbation (OPS). As illustrated in the following plot, DP-SGLD tracks the non-private baseline much more closely as the privacy budget $\epsilon$ increases, maintaining higher test accuracy across various privacy levels.

Test accuracy vs. privacy budget on the Adult dataset.

Large-Scale Benchmarks

  • MNIST: DP-SGLD achieved 99.21% accuracy at $\epsilon = 0.99$, significantly outperforming DP-SGD, which reached only 97% accuracy at a much higher $\epsilon = 8.0$.
  • SVHN: The method reached 91.89% accuracy ($\epsilon = 2.97$), surpassing the state-of-the-art CGNMax method (91.62% at $\epsilon = 4.96$).

Conclusion

This research establishes that privacy is a "natural" property of SG-MCMC. By providing tighter privacy bounds, the authors enable the use of larger stepsizes that preserve the utility of Bayesian models. While challenges remain—such as the heuristic nature of choosing gradient clipping bounds and the slight performance gap between theoretical decreasing stepsizes and empirical fixed stepsizes—this work paves the way for scalable, private Bayesian deep learning. Future extensions could apply this analysis to more complex samplers like Hamiltonian Monte Carlo (SGHMC).

Summary updated

Abstract

Concerns related to data security and confidentiality have been raised when applying machine learning to real-world applications. Differential privacy provides a principled and rigorous privacy gua...
BibTeX
@inproceedings{li2019connecting,
  author = {Bai Li and Changyou Chen and Hao Liu and Lawrence Carin},
  title = {{On Connecting Stochastic Gradient MCMC and Differential Privacy}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=DgSFyvPGRP},
}
Figure