Paper Info
Title
Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning
Abstract
Several recent studies in privacy-preserving learning have considered the trade-off between utility or risk and the level of differential privacy guaranteed by mechanisms for statistical query processing. In this paper we study this trade-off in private Support Vector Machine (SVM) learning. We present two efficient mechanisms, one for the case of finite-dimensional feature mappings and one for potentially infinite-dimensional feature mappings with translation-invariant kernels. For the case of translation-invariant kernels, the proposed mechanism minimizes regularized empirical risk in a random Reproducing Kernel Hilbert Space whose kernel uniformly approximates the desired kernel with high probability. This technique, borrowed from large-scale learning, allows the mechanism to respond with a finite encoding of the classifier, even when the function class is of infinite VC dimension. Differential privacy is established using a proof technique from algorithmic stability. Utility--the mechanism's response function is pointwise epsilon-close to non-private SVM with probability 1-delta--is proven by appealing to the smoothness of regularized empirical risk minimization with respect to small perturbations to the feature mapping. We conclude with a lower bound on the optimal differential privacy of the SVM. This negative result states that for any delta, no mechanism can be simultaneously (epsilon,delta)-useful and beta-differentially private for small epsilon and small beta.
Year
Venue
Keywords
2009
Clinical Orthopaedics and Related Research
support vector machines
DocType
Volume
Citations 
Journal
abs/0911.5
31
PageRank 
References 
Authors
1.66
20
4
Name
Order
Citations
PageRank
Benjamin I. P. Rubinstein148641.87
Peter L. Bartlett254821039.97
Ling Huang32496118.80
Nina Taft42109154.92