Privacy-preserving Prediction

By Cynthia Dwork, Vitaly Feldman. 2018

104 citations recorded by the source corpus.

Ensuring differential privacy of models learned from sensitive user data is an important goal that has been studied extensively in recent years. It is now known that for some basic learning problems, especially those involving high-dimensional data, producing an accurate private model requires much more data than learning without privacy. At the same time, in many applications it is not necessary to expose the model itself. Instead users may be allowed to query the prediction model on their inputs only through an appropriate interface. Here we formulate the problem of ensuring privacy of individual predictions and investigate the overheads required to achieve it in several standard models of classification and regression. We first describe a simple baseline approach based on training several models on disjoint subsets of data and using standard private aggregation techniques to predict. We show that this approach has nearly optimal sample complexity for (realizable) PAC learning of any class of Boolean functions. At the same time, without strong assumptions on the data distribution, the aggregation step introduces a substantial overhead. We demonstrate that this overhead can be avoided for the well-studied class of thresholds on a line and for a number of standard settings of convex regression. The analysis of our algorithm for learning thresholds relies crucially on strong generalization guarantees that we establish for all differentially private prediction algorithms.

Subfields: Artificial Intelligence, Statistics and Probability

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 Statistics and Probability

Citations in the corpus

Cronus: Robust and Heterogeneous Collaborative Learning with Black-Box Knowledge Transfer (2019, background): “In addition, the black-box setting allows us to make use of utility-preserving algorithms to make the knowledge transfer privacy-preserving, as a party only needs to mitigate the privacy risk of sharing its predictions [39], [43], [18].”
A survey of algorithmic recourse: definitions, formulations, solutions, and prospects (2020, background): “Even under partial knowledge of the friend’s attributes, an adversary may use the information about the shared predictions in B Δ 𝒙 F to perform membership inference attacks [163] or infer missing attributes [59].”
When Machine Learning Meets Privacy (2020, background): “ion/Obfuscation DP+Aggregation Distributed [69,94] ✓ Aggregation Federated learning Distributed [12] ✓ Aggregation/Encryption Federated learning + SMC Distributed [118] ✓ Aggregation PATE Centralised [34] ✓ Aggregation/Obfuscation Output aggregation + DP Centralised ME: Model Extraction; FE: Feature”
Adversarial Neural Network Inversion via Auxiliary Knowledge Alignment (2019, methodology): “Secure & Privacy-Preserving ML In the wake of security and privacy threats posed to ML techniques, much research has been devoted to provisioning secure and privacy-preserving training of ML models [58], [59], [60], [61], [62].”
Neural Network Inversion in Adversarial Setting via Background Knowledge Alignment (2019, methodology): “Some research work on protecting the predictions of ML models has also been proposed recently [20, 32].”
Submix: Practical Private Prediction for Large-Scale Language Models (2022, methodology): “We summarize the above discussion in the following R´enyi-DP variant of the deﬁnition for private prediction by Dwork & Feldman (2018).”
Adaptive Machine Unlearning (2021, methodology): “For each prediction request, we privately aggregate the predictions made by the ensemble of models { θ ti } i ; Dwork and Feldman [2018] show several ways to privately aggregate predictions (one simple technique is to use the exponential mechanism to approximate the majority vote).”
Model Reconstruction from Model Explanations (2018, background): “While diﬀerential privacy can help guard against attacks from prediction APIs [7], it is not clear if this is a viable approach for preventing reconstruction from explanations.”
Differentially Private Decoding in Large Language Models (2022, background): “More recently, there has been interest in introducing DP to already trained machine learning models at the prediction stage (Dwork and Feldman, 2018; Dagan and Feldman, 2020) as formalized in the following definition.”
Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses (2020, methodology): “In particular, bounds on the uniform stability of SGD from [20] have been crucial in the design and analysis of new DP-SCO algorithms [36, 12, 17, 2, 16].”
How to Use Heuristics for Differential Privacy (2018, methodology): “…algorithm [PAE + 16] together with more recent theoretical analyses of similar algorithms by Dwork and Feldman, and Bassily, Thakkar, and Thakurta [DF18, BTT18] can be viewed as giving oracle-e ﬃ cient algorithms for an easier learning task, in which the goal is to produce a ﬁnite number of…”
On Provable Copyright Protection for Generative Models (2023, background): “In that sense, our deﬁnition is closer to privacy-preserving prediction [Dwork and Feldman, 2018], which aims to protect the privacy of individual predictions (i.e., outputs) as opposed to protecting the model itself.”