Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds

By Raef Bassily, Adam D. Smith, Abhradeep Thakurta. 2014

364 citations recorded by the source corpus.

In this paper, we initiate a systematic investigation of differentially private algorithms for convex empirical risk minimization. Various instantiations of this problem have been studied before. We provide new algorithms and matching lower bounds for private ERM assuming only that each data point's contribution to the loss function is Lipschitz bounded and that the domain of optimization is bounded. We provide a separate set of algorithms and matching lower bounds for the setting in which the loss functions are known to also be strongly convex. Our algorithms run in polynomial time, and in some cases even match the optimal non-private running time (as measured by oracle complexity). We give separate algorithms (and lower bounds) for $(\epsilon,0)$- and $(\epsilon,\delta)$-differential privacy; perhaps surprisingly, the techniques used for designing optimal algorithms in the two cases are completely different. Our lower bounds apply even to very simple, smooth function families, such as linear and quadratic functions. This implies that algorithms from previous work can be used to obtain optimal error rates, under the additional assumption that the contributions of each data point to the loss function is smooth. We show that simple approaches to smoothing arbitrary loss functions (in order to apply previous techniques) do not yield optimal error rates. In particular, optimal algorithms were not previously known for problems such as training support vector machines and the high-dimensional median.

Subfields: Artificial Intelligence, Optimization & Training

How researchers see this paper

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

In Artificial Intelligence

In Optimization & Training

Citations in the corpus

Towards the Science of Security and Privacy in Machine Learning (2016, background): “privacy analysis, along with references to many of the works intervening in private empirical risk minimization [101]”
Deep Learning with Differential Privacy (2016, methodology): “This approach has been followed in previous works (e.g., [47, 7]); we make several modiﬁcations and extensions, in particular in our privacy accounting.”
Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data (2016, neutral): “Attempts to provide differential privacy for machine learning models led to a series of efforts on shallow machine learning models, including work by Bassily et al. (2014); Chaudhuri & Monteleoni (2009); Pathak et al. (2011); Song et al. (2013), and Wainwright et al. (2012).”
The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation (2021, methodology): “The privacy guarantees ε we report rely on privacy amplification via sampling (Kasiviswanathan et al., 2011; Bassily et al., 2014; Abadi et al., 2016), which is necessary to obtain reasonable privacy-accuracy tradeoffs”
Tempered Sigmoid Activations for Deep Learning with Differential Privacy (2020, methodology): “The choice of architectures is motivated by prior work which showed that training larger architectures is detrimental to generalization when learning with privacy [5].”
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): “In output perturbation techniques, the machine learned model is trained completely and then the final model is appropriately changed by using exponential mechanism [22, 11, 24, 16] or by adding Laplace or Gaussian noise to the final model [25, 10, 12].”
Privacy Amplification by Iteration (2018, background): “In the absence of public data, privacy comes at a provable cost: while the statistical error due to sampling scales as 1/ √ n independently of the dimension, the error of the differentially private version scales as √ d/ √ n [14].”
Subsampled Rényi Differential Privacy and Analytical Moments Accountant (2018, background): “The ﬁrst privacy ampliﬁcation lemma appeared in (Kasiviswanathan et al., 2011; Beimel et al., 2013), with many subsequent improvements in diﬀerent settings.”
Differential Privacy for Growing Databases (2018, methodology): “As in [BST14], we assume δ 1 /t for simplicity.”
Tight Lower Bounds for Differentially Private Selection (2017, background): “We remark that previous fingerprinting-based lower bounds in differential privacy [16], [27], [28], [17], [18], [3] essentially correspond to setting β = O(1) in Theorem 3.”
The Value of Collaboration in Convex Machine Learning with Differential Privacy (2019, background): “These bounds are in line with the lower and the upper bounds in [33] for strongly convex and general convex loss functions.”
Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation (2020, background): “At a high level, LDP-SGD follows the following template of noisy stochastic gradient descent [38], [39], [40].”
SoK: Security and Privacy in Machine Learning (2018, background): “provide improved algorithms and privacy analysis, along with references to many of the works intervening in private learning through cost minimization [92]”
Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo (2015, methodology): “The boundedness on the loss-function (log-likelihood here) is a standard assumption in many DP works (Chaudhuri et al., 2011; Bassily et al., 2014; Song et al., 2013; Kifer et al., 2012).”
Private Stochastic Convex Optimization with Optimal Rates (2019, methodology): “The excess empirical loss of this technique for smooth convex losses was originally analyzed in the aforementioned works, and was shown to be optimal by the lower bound in [BST14].”
Improving the Privacy and Accuracy of ADMM-Based Distributed Algorithms (2018, methodology): “…( δ > 0 ) of violating (cid:15) -differential privacy and adopt a weaker variant ( (cid:15) , δ )-differential privacy, we can adopt methods from works such as (Kifer et al., 2012; Jain & Thakurta, 2014; Bassily et al., 2014), by adding Gaussian noise to achieve tighter bounds on privacy loss.”