Differentially Private Empirical Risk Minimization

By Kamalika Chaudhuri, Claire Monteleoni, Anand D. Sarwate. 2009

1,610 citations recorded by the source corpus.

Privacy-preserving machine learning algorithms are crucial for the increasingly common setting in which personal data, such as medical or financial records, are analyzed. We provide general techniques to produce privacy-preserving approximations of classifiers learned via (regularized) empirical risk minimization (ERM). These algorithms are private under the ε-differential privacy definition due to Dwork et al. (2006). First we apply the output perturbation ideas of Dwork et al. (2006), to ERM classification. Then we propose a new method, objective perturbation, for privacy-preserving machine learning algorithm design. This method entails perturbing the objective function before optimizing over classifiers. If the loss and regularizer satisfy certain convexity and differentiability criteria, we prove theoretical results showing that our algorithms preserve privacy, and provide generalization bounds for linear and nonlinear kernels. We further present a privacy-preserving technique for tuning the parameters in general machine learning algorithms, thereby providing end-to-end privacy guarantees for the training process. We apply these results to produce privacy-preserving analogues of regularized logistic regression and support vector machines. We obtain encouraging results from evaluating their performance on real demographic and benchmark data sets. Our results show that both theoretically and empirically, objective perturbation is superior to the previous state-of-the-art, output perturbation, in managing the inherent tradeoff between privacy and learning performance.

Subfields: Safety, Robustness & Interpretability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Safety, Robustness & Interpretability

Citations in the corpus

On The Impact of Machine Learning Randomness on Group Fairness (2023, background): “For example, data augmentation to increase dataset size [31], dropout to perform regularization [58], gradient noise for private training [14], etc.”
Towards the Science of Security and Privacy in Machine Learning (2016, methodology): “Chaudhuri et al. show that objective perturbation , i.e. introducing random noise—drawn from an exponential distribution and scaled using the model sensitivity 5 —in the cost function minimized during learning, can provide ε -differential privacy [100].”
Deep Learning with Differential Privacy (2016, background): “privacy is a class of convex optimization problems amenable to a wide variety of techniques [20, 12, 36].”
Membership Inference Attacks Against Machine Learning Models (2016, methodology): “Regularization is also used for objective perturbation in differentially private machine learning [9].”
Deep Models Under the GAN: Information Leakage from Collaborative Deep Learning (2017, background): “Several works have adopted DP as an efficient defense mechanism such as [5, 7, 11, 12, 18, 23, 24, 37, 53, 60, 65, 72, 86].”
Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data (2016, background): “However, intuition is not sufﬁcient because privacy properties can be surprisingly hard to reason about; for example, even a single data item can greatly impact machine learning models trained on a large corpus (Chaudhuri et al., 2011).”
Certified Robustness to Adversarial Examples with Differential Privacy (2018, methodology): “Significant work has focused on making ML algorithms DP to preserve the privacy of training sets [39], [1], [9].”
Practical and Private (Deep) Learning without Sampling or Shuffling (2021, background): “Differentially private empirical risk minimization (ERM) and private online learning are well-studied areas in the privacy literature [1, 2, 3, 6, 7, 14, 29, 35, 37, 38, 43, 51, 57, 58, 65, 67, 68, 74] 7 .”
Differentially Private Learning Needs Better Features (or Much More Data) (2020, methodology): “The utility of private learning typically degrades as the model’s dimensionality increases (Chaudhuri et al., 2011; Bassily et al., 2014).”
Training Production Language Models without Memorizing User Data (2020, background): “Many prior works in DP machine learning (ML) [CMS11], [BST14], [ACG + 16], [PAE + 16], [WLK + 17], [PSM + 18], [INS + 19] deal with example-level privacy, i.e., providing privacy guarantees for any single example in a dataset.”
Tempered Sigmoid Activations for Deep Learning with Differential Privacy (2020, methodology): “…al. (2016) introduced DP-SGD as a method for training deep neural networks with differential-privacy guarantees that was able to achieve better privacy and utility than previous efforts (Chaudhuri, Monteleoni, and Sarwate 2011; Song, Chaudhuri, and Sarwate 2013; Bassily, Smith, and Thakurta 2014).”
Learning discrete distributions: user vs item-level privacy (2020, neutral): “…et al., 2015, Kamath et al., 2019, Acharya et al., 2020, Kamath et al., 2020, Acharya et al., 2019a,b], learning machine learning models [Chaudhuri et al., 2011, Bassily et al., 2014, McMahan et al., 2017, Dwork et al., 2014], hypothesis testing [Aliakbarpour et al., 2018, Acharya et…”
Privacy in Deep Learning: A Survey (2020, methodology): “In the table, the following abbreviations have been used: ERM for Empirical Risk Minimization, GM for Generative Model, AE for Auto Encoder, LIR for Linear Regression, LOR for Logistic Regression, LM for Linear Means, FLD for Fisher’s Linear Discriminant, NB for Naive Bayes and RF for Random Forest.”
Generative Models for Effective ML on Private, Decentralized Datasets (2019, background): “Most prior work on differentially private ML (e.g. Chaudhuri et al. (2011); Bassily et al. (2014); Abadi et al. (2016); Wu et al. (2017); Papernot et al. (2017)) deals with example-level privacy: two datasets d and d′ are defined to be adjacent if d′ can be formed by adding or removing a single…”
AdaCliP: Adaptive Clipping for Private SGD (2019, methodology): “Differential privacy for machine learning has been studied in various models including models with convex objectives [10, 11, 12] and more recently deep learning methods [13, 14, 15].”
Learning Privately over Distributed Features: An ADMM Sharing Approach (2019, methodology): “In this paper, we propose an ADMM algorithm to solve the empirical risk minimization (ERM) problem, a general optimization formulation of many machine learning models visited by a number of recent studies on distributed machine learning Ying et al. (2018); Chaudhuri et al. (2011).”
Differentially Private Learning with Adaptive Clipping (2019, neutral): “In example-level DP, datasets are considered neighbors when they differ by the addition or removal of a single example (Chaudhuri et al., 2011; Bassily et al., 2014; Abadi et al., 2016b; Papernot et al., 2017; Wu et al., 2017; Papernot et al., 2018; Iyengar et al., 2019).”
Data Poisoning against Differentially-Private Learners: Attacks and Defenses (2019, methodology): “dient descent to search for effective training examples to corrupt against speciﬁc learning algorithms. We evaluate attack on two private learners: objective perturbation [11] and output perturbation [5]. Our evaluation conﬁrms the theoretical prediction that private learners are vulnerable to data ”