Secure Systems Group
Menu×

Wiki Home

Deep Learning with Differential Privacy

Paper: ACM CCS 2016

High-level overview

A trained model’s parameters can encode fine details of individual training examples, and that data may be sensitive. This paper trains deep networks under differential privacy, a guarantee on the training algorithm: removing or adding any single example changes the distribution over trained models by at most a bounded factor (epsilon, with slack delta, the run’s “privacy budget”). Its algorithm, now universally called DP-SGD, modifies stochastic gradient descent in two places: each example’s gradient is clipped to a fixed norm, bounding any one example’s sensitivity, and calibrated Gaussian noise is added before each update (the Gaussian mechanism).

The second contribution is the moments accountant, a tighter bound on the privacy budget spent across the thousands of noisy steps a deep model takes. Earlier accounting forced training to exhaust its budget long before the model was useful; the moments accountant tracks privacy loss tightly enough to keep budgets in the single digits. Implemented in TensorFlow, the paper reports 97% test accuracy on MNIST and 73% on CIFAR-10 at single-digit budgets ((8, 10^-5)-differential privacy, with 90% on MNIST at epsilon as small as 0.5), against non-private baselines near 98.3% and 80%. The CIFAR-10 model trains only its fully connected layers privately, on convolutional layers pre-trained on a dataset treated as public.

Threat Model: A defense paper, and the guarantee is attack-agnostic: it does not name an adversary strategy, it bounds what any adversary can learn. The protected secret is one training record’s presence and content; adjacent datasets differ in a single image-label pair. The adversary is as strong as the definition allows: white-box access to the released model parameters, full knowledge of the training mechanism, arbitrary auxiliary information, and possibly control of every other training record. The defender claims (epsilon, delta)-differential privacy for the entire released parameter vector, which then bounds the success of any present or future attack, including membership inference. The guarantee says nothing about secrets shared across many records, and its strength degrades as epsilon grows.

Basic Background

Training neural networks

Training minimizes the average loss over the training set, the empirical risk minimization objective, using stochastic gradient descent: estimate the gradient on a batch of examples, step against it, repeat. For deep networks the loss is non-convex, so training finds a local minimum, and no tight characterization exists of how the final parameters depend on any one training example. Noise added to the finished model must therefore be scaled to a loose worst case, which destroys the model’s utility; enforcing privacy inside the training loop avoids this.

Why trained models leak

A network’s capacity lets it memorize individual training examples, and what is memorized can be recovered: model inversion reconstructs recognizable face images from a facial recognition model’s outputs (Fredrikson et al., 2015), and membership inference predicts whether a specific record was trained on. Regularization may reduce such leakage but provides no guarantee.

Differential privacy

Differential privacy is a property of a randomized algorithm: for any two adjacent datasets (differing in one record) the probability of any output set changes by at most a factor of e^epsilon, plus slack delta (Dwork et al., 2006a; Dwork et al., 2006b). Three properties of the definition are used throughout this literature: composability (private components compose into a private system), group privacy (graceful degradation for correlated records), and robustness to auxiliary information (the guarantee does not depend on what the adversary already knows). The standard reference is Dwork and Roth (2014).

Sensitivity and the Gaussian mechanism

The basic recipe for making a function private is additive noise scaled to its sensitivity, the most any single record can change its output; adding Gaussian noise calibrated this way yields the Gaussian mechanism (Dwork et al., 2006b). A gradient has no a priori sensitivity bound, which is the gap gradient clipping closes: rescaling every example’s gradient to a maximum norm C makes C the sensitivity by construction.

The privacy budget and composition

Each noisy step leaks a little, and the leaks accumulate. Composition theorems bound the total: the basic theorem adds the epsilons, and the strong composition theorem does better over many steps (Dwork et al., 2010; Kairouz et al., 2015). A privacy accountant tracks the accumulated budget during execution (McSherry, 2009). Random sampling of each batch amplifies privacy, since a record absent from a batch leaks nothing in that step. How tightly the accountant adds up thousands of sampled Gaussian steps decides how long a network can train before its budget is exhausted.

Reading guidance

  • Section 3.1, Algorithm 1: the clipping step is what bounds any single example’s influence on the update, and every privacy claim downstream rests on that bound. The threshold C has no closed form; note how Section 5.2 settles on a value.
  • Theorem 1 with Figure 2: the moments accountant, and the factor of sqrt(log(T/delta)) it saves over the strong composition theorem. Figure 2 puts a number on that saving, as epsilon against training epochs.
  • Section 5.3: the CIFAR-10 numbers. The convolutional layers are pretrained on CIFAR-100, which the paper declares public, and only the softmax layer and one or both fully connected layers are trained privately. Note what the reported epsilon therefore covers.

Paper Context

Privacy-preserving learning is older than deep learning. Privacy-preserving data mining was posed around 2000, in both randomization and cryptographic forms (Agrawal and Srikant, 2000; Lindell and Pinkas, 2000). The then-dominant data-release notion, k-anonymity (Sweeney, 2002), generalizes and suppresses identifying attributes; on high-dimensional data, achieving it destroys most of the data’s mining utility for little privacy gain (Aggarwal, 2005; Brickell and Shmatikov, 2008). Differential privacy emerged from the theory community as the rigorous alternative: privacy as a property of the computation rather than of the released data, with noise calibrated to sensitivity (Dwork et al., 2006a), the (epsilon, delta) relaxation (Dwork et al., 2006b), and a decade of supporting machinery, including strong composition (Dwork et al., 2010; Kairouz et al., 2015), the privacy accountant (McSherry, 2009), and a textbook treatment (Dwork and Roth, 2014).

Differentially private machine learning then developed almost entirely on convex problems. Private empirical risk minimization was solved by output and objective perturbation (Chaudhuri et al., 2011; Kifer et al., 2012) and by noisy gradient methods with tight error bounds (Bassily et al., 2014), including a direct DP-SGD precursor (Song et al., 2013). The first end-to-end differentially private learning system was a recommender built on the Netflix Prize data, which worked by privatizing sufficient statistics of the task (McSherry and Mironov, 2009), a route unavailable for models with no such statistics.

Deep networks fall outside the assumptions of this line of work: the loss is non-convex, parameters number in the millions, and training takes many passes over datasets that are increasingly crowdsourced and sensitive. Model inversion demonstrated the leakage on such models, recovering recognizable images from a face recognition model (Fredrikson et al., 2015). The one attempt at private deep learning before this paper, a distributed protocol perturbing shared gradient updates, spent its budget per parameter, and its total privacy loss per participant exceeded several thousand epsilon (Shokri and Shmatikov, 2015). No published method trained a deep network to useful accuracy at a single-digit budget. Tighter accounting tools, concentrated differential privacy among them, were in concurrent development (Dwork and Rothblum, 2016; Bun and Steinke, 2016).

Additional Readings

References

Entries read off the paper’s bibliography (arXiv 1607.00133v2, pages 10-11).

  • Aggarwal, C. C. “On k-Anonymity and the Curse of Dimensionality.” VLDB, 2005.
  • Agrawal, R. and Srikant, R. “Privacy-Preserving Data Mining.” ACM SIGMOD, 2000.
  • Bassily, R., Smith, A. D., and Thakurta, A. “Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds.” IEEE Symposium on Foundations of Computer Science (FOCS), 2014.
  • Brickell, J. and Shmatikov, V. “The Cost of Privacy: Destruction of Data-Mining Utility in Anonymized Data Publishing.” ACM SIGKDD (KDD), 2008.
  • Bun, M. and Steinke, T. “Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds.” Theory of Cryptography Conference (TCC-B), 2016 (cited by the paper as concurrent work).
  • Chaudhuri, K., Monteleoni, C., and Sarwate, A. D. “Differentially Private Empirical Risk Minimization.” Journal of Machine Learning Research, 12, 2011.
  • Dwork, C., McSherry, F., Nissim, K., and Smith, A. “Calibrating Noise to Sensitivity in Private Data Analysis.” Theory of Cryptography Conference (TCC), 2006. (2006a)
  • Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., and Naor, M. “Our Data, Ourselves: Privacy via Distributed Noise Generation.” EUROCRYPT, 2006. (2006b)
  • Dwork, C. and Roth, A. “The Algorithmic Foundations of Differential Privacy.” Foundations and Trends in Theoretical Computer Science, 9(3-4), 2014.
  • Dwork, C. and Rothblum, G. N. “Concentrated Differential Privacy.” arXiv:1603.01887, 2016.
  • Dwork, C., Rothblum, G. N., and Vadhan, S. “Boosting and Differential Privacy.” IEEE Symposium on Foundations of Computer Science (FOCS), 2010.
  • Fredrikson, M., Jha, S., and Ristenpart, T. “Model Inversion Attacks that Exploit Confidence Information and Basic Countermeasures.” ACM Conference on Computer and Communications Security (CCS), 2015.
  • Kairouz, P., Oh, S., and Viswanath, P. “The Composition Theorem for Differential Privacy.” International Conference on Machine Learning (ICML), 2015.
  • Kifer, D., Smith, A. D., and Thakurta, A. “Private Convex Optimization for Empirical Risk Minimization with Applications to High-Dimensional Regression.” Conference on Learning Theory (COLT), 2012.
  • Lindell, Y. and Pinkas, B. “Privacy Preserving Data Mining.” CRYPTO, 2000.
  • McSherry, F. D. “Privacy Integrated Queries: An Extensible Platform for Privacy-Preserving Data Analysis.” ACM SIGMOD, 2009.
  • McSherry, F. and Mironov, I. “Differentially Private Recommender Systems: Building Privacy into the Netflix Prize Contenders.” ACM SIGKDD (KDD), 2009.
  • Shokri, R. and Shmatikov, V. “Privacy-Preserving Deep Learning.” ACM Conference on Computer and Communications Security (CCS), 2015.
  • Song, S., Chaudhuri, K., and Sarwate, A. “Stochastic Gradient Descent with Differentially Private Updates.” IEEE GlobalSIP, 2013.
  • Sweeney, L. “k-Anonymity: A Model for Protecting Privacy.” International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 10(5), 2002.