Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning

By Benjamin I. P. Rubinstein, Peter L. Bartlett, Ling Huang, Nina Taft. 2009

301 citations recorded by the source corpus.

The ubiquitous need for analyzing privacy-sensitive information—including health records, personal communications, product ratings and social network data—is driving significant interest in privacy-preserving data analysis across several research communities. This paper explores the release of Support Vector Machine (SVM) classifiers while preserving the privacy of training data. The SVM is a popular machine learning method that maps data to a high-dimensional feature space before learning a linear decision boundary. We present efficient mechanisms for finite-dimensional feature mappings and for (potentially infinite-dimensional) mappings with translation-invariant kernels. In the latter case, our mechanism borrows a technique from large-scale learning to learn in a finite-dimensional feature space whose inner-product uniformly approximates the desired feature space inner-product (the desired kernel) with high probability. Differential privacy is established using algorithmic stability, a property used in learning theory to bound generalization error. Utility—when the private classifier is pointwise close to the non-private classifier with high probability—is proven using smoothness of regularized empirical risk minimization with respect to small perturbations to the feature mapping. Finally we conclude with lower bounds on the differential privacy of any mechanism approximating the SVM.

Subfields: Artificial Intelligence, Computer Science Applications, Statistical Learning Theory, Privacy & Security

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 Computer Science Applications

In Statistical Learning Theory

In Privacy & Security

Citations in the corpus

Red Teaming Language Models with Language Models (2022, neutral): “LM-based red teaming complements training methods that minimize data leakage, e.g., differential privacy (Chaudhuri and Monteleoni, 2009; Rubinstein et al., 2012; Shokri and Shmatikov, 2015; Abadi et al., 2016).”
Membership Inference Attacks Against Machine Learning Models (2016, background): “Differential privacy [12] has been applied to linear and logistic regression [8], [37], support vector machines [28], risk minimization [5], [9], [34], deep learning [1], [30], learning an unknown probability distribution over a discrete population from random samples [10], and releasing hyper-param”
Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning (2017, background): “However, it is still an open issue to understand whether and to which extent randomization may be used to make it harder for the attacker to learn a proper surrogate model, and to implement privacy-preserving mechanisms [100] against model inversion and hill-climbing attacks [28, 62, 67–70].”
Differentially Private Learning Needs Better Features (or Much More Data) (2020, background): “Unfortunately, private learning with non-linear kernels is intractable in general (Chaudhuri et al., 2011; Rubinstein et al., 2012).”
Real-World Image Datasets for Federated Learning (2019, methodology): “So far, federated learning has been implemented with many state-of-the-art algorithms such as long short-term memory (LSTM) networks [McMahan et al. , 2017], support vector machines (SVMs) [Rubinstein et al. , 2009], gradient boosting trees [Cheng et al. , 2019], etc..”
AdaCliP: Adaptive Clipping for Private SGD (2019, methodology): “In output perturbation techniques, the machine learned model is trained completely and then the ﬁnal model is appropriately changed by using exponential mechanism [22, 11, 24, 16] or by adding Laplace or Gaussian noise to the ﬁnal model [25, 10, 12].”
Privacy Aware Learning (2012, background): “…comes in pairs x = ( a, b ) , where a ∈ R d is the set of regressors and b ∈ {− 1 , 1 is the label; the losses are By computing (sub)gradients, we may verify that each of these belong to the class of ( L, p ) -losses if and only if the data a satisﬁes a p ≤ L , which is a common assumption [7, 24].”
Functional Mechanism: Regression Analysis under Differential Privacy (2012, methodology): “For instance, the exponential mechanism has been applied for the publication of audition results [21], coresets [10], frequent patterns [3], decision trees [11], support vector machines [25], and synthetic datasets [7,16].”
Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, background): “[11] and [41] showed that strongly convex functions have low-sensitivity minimizers, and hence that one can release the minimum of a strongly convex function with Laplace noise (with total Euclidean length about ρ = p ∆ n if each loss function is ∆-strongly convex).”
Security Evaluation of Support Vector Machines in Adversarial Environments (2014, methodology): “We omit the proof, which is available in the original paper [59] and which follows closely the previous measurements for algorithmic stability.”
Differentially Private Model Publishing for Deep Learning (2019, methodology): “Differential privacy (DP), a defacto standard for privacy that offers provable privacy guarantees, has been applied for privacy-preserving machine learning [8], [10], [11], [32], [42].”
Multi‐center machine learning in imaging psychiatry: A meta‐model approach (2017, unknown): “…al., 2010; van Erp et al., 2015) 2) Legal or ethical issues – sharing sensitive information about patients and controls, such as the images themselves (Rubinstein et al., 2009; Sarwate et al., 2014) 3) Computational complexity – increasing with large number of subjects, especially in cases when…”